Wilkinsonの多項式

同義語:ウィルキンソンの多項式Wilkinson's polynomialWilkinson polynomial

概要

Wilkinsonの多項式(Wilkinson's polynomial)とは、$1,2,\dots,20$ を根にもつ多項式 $w(x)=(x-1)(x-2)\cdots(x-20)$ のことで、根は互いに離れているのに、$x^{19}$ の係数を $2^{-23}$ 変えると根の 10 個が複素数になる。単根 $r$ は摂動 $\varepsilon g$ で 1 次の近似で $-\varepsilon g(r)/p'(r)$ 動き、根 $16$ の $x^{19}$ の係数に対する感度は約 $2.4\times10^9$ になり、点を根にするのに要る係数の相対的な変化は $\lvert p(z)\rvert/\sum_j\lvert a_j\rvert\lvert z\rvert^j$ で、相対条件数は根の尺度によらない。固有値を特性多項式の根として求める危うさを示す例である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 多項式, Rouchéの定理, 条件数, 誤差(数値解析)

Wilkinsonの多項式(Wilkinson's polynomial)は、$1,2,\dots,20$ を根にもつ 20 次の多項式
$$ w(x)=\prod_{k=1}^{20}(x-k)=(x-1)(x-2)\cdots(x-20) $$
である。根は互いに十分離れた整数なのに、展開した係数を少し変えるだけで根が大きく動く。$x^{19}$ の係数 $-210$ を $-210-2^{-23}$(相対的にはおよそ $6\times10^{-10}$ の変化)に変えると、根のうち 10 個が実数でなくなり、$16$ と $17$ のあたりの根は $16.73\pm2.81i$ になる。
この現象を Wilkinson は 1959 年の論文で示し、行列の固有値を特性多項式の根として計算することの危うさを論じた(Wil59 §3–§4)。数値計算では、問題の答えが入力の小さな変化にどれだけ敏感か(条件数)を、計算の方法の良し悪しと区別して考える。Wilkinson の多項式は「根そのものはよく分かれていても、係数から根を求める問題は条件が悪いことがある」ことを示す標準の例である。
この記事では、単根が係数の摂動で 1 次の近似でどう動くかを示す定理(thm-wp-first-order)を証明し、そこから根の条件数の式を導いて Wilkinson の多項式で計算する。さらに、ある点が「係数をどれだけ変えれば根になるか」を正確に与える後退誤差の公式(thm-wp-backward)を証明し、条件数が根の位置の尺度によらないこと(prop-wp-scale)を示す。

定義と使える条件

Wilkinson の多項式と係数

$n\ge1$ について $w_n(x):=\prod_{k=1}^{n}(x-k)$ とおき、$w:=w_{20}$ を Wilkinson の多項式 という。展開した係数を
$$ w(x)=\sum_{j=0}^{20}a_jx^j\qquad(a_{20}=1) $$
と書く。

係数は整数で、$a_{19}=-(1+2+\cdots+20)=-210$、$a_{18}=\sum_{1\le i< j\le20}ij=20615$、$a_0=20!\approx2.43\times10^{18}$ である。係数の絶対値は $a_{20}=1$ から $\lvert a_2\rvert\approx1.4\times10^{19}$($\lvert a_3\rvert\approx1.3\times10^{19}$)まで 19 桁にわたる。
この記事では、多項式 $p(x)=\sum_{j=0}^na_jx^j$($a_j\in\mathbb C$、$a_n\ne0$)の根 $r$ が 単根 であるとは、$p(r)=0$ かつ $p'(r)\ne0$ であることをいう。根の動きを調べる問題の設定は次のとおりである。

  1. 係数の摂動は、多項式 $g$ と複素数 $\varepsilon$ による $p_\varepsilon:=p+\varepsilon g$ の形で与える。係数 $a_j$ だけを $\delta$ 変えるのは $g=x^j$、$\varepsilon=\delta$ の場合である。
  2. 1 次の近似(thm-wp-first-order)は単根についてだけ成り立つ。重根では根の動きは $\varepsilon$ について 1 次ではない(反例の表)。
  3. 1 次の近似は $\varepsilon\to0$ の極限の主張であり、与えられた大きさの $\varepsilon$ で近似がよいかどうかは別の問題である。Wilkinson の多項式では $\varepsilon=2^{-23}$ ですでに 1 次の近似は使えない(ex-wp-complex)。
    Wilkinson の原論文は根が $-1,\dots,-20$ の多項式 $(x+1)\cdots(x+20)$ を使っている(Wil59 p. 152、式 (10))。$x$ を $-x$ に替えると次数が偶数なので $(x+1)\cdots(x+20)$ は $w(-x)$ になり、奇数次の係数($x^{19}$ の係数を含む)の符号が変わる。この記事の数値は、原論文の数値の符号を変えたものである。

公式の表

$r_k=k$ を $w$ の根とする。

量式条件根拠
根の 1 次の動き$\dfrac{dr}{d\varepsilon}\Big\vert_{\varepsilon=0}=-\dfrac{g(r)}{p'(r)}$$r$ は $p$ の単根thm-wp-first-order
係数 $a_j$ に対する感度$\dfrac{\partial r}{\partial a_j}=-\dfrac{r^j}{p'(r)}$同上cor-wp-condition
根の相対条件数$\kappa(r)=\dfrac{\sum_j\lvert a_j\rvert\lvert r\rvert^j}{\lvert r\,p'(r)\rvert}$同上、$r\ne0$cor-wp-condition
$w$ の導関数の値$w'(k)=(-1)^{20-k}(k-1)!\,(20-k)!$$1\le k\le20$prop-wp-derivative
$a_{19}$ に対する感度$\Bigl\lvert\dfrac{\partial r_k}{\partial a_{19}}\Bigr\rvert=\dfrac{k^{19}}{(k-1)!\,(20-k)!}$同上prop-wp-derivative
後退誤差$\eta(z)=\dfrac{\lvert p(z)\rvert}{\sum_j\lvert a_j\rvert\lvert z\rvert^j}$$z\ne0$ または $a_0\ne0$thm-wp-backward

$a_{19}$ に対する感度の値(prop-wp-derivative の式で計算したもの)は次のとおりである。

根 $k$$1$$5$$10$$14$$15$$16$$17$$20$
$\lvert\partial r_k/\partial a_{19}\rvert$$8.2\times10^{-18}$$0.61$$7.6\times10^6$$1.3\times10^9$$2.1\times10^9$$2.4\times10^9$$1.9\times10^9$$4.3\times10^7$

最大は $k=16$ で、$a_{19}$ を $10^{-9}$ 変えただけで根 $16$ は 1 次の近似でおよそ $2.4$ 動く。

主定理と証明

単根の 1 次の動き

単根の 1 次の動き

$p,g$ を複素係数の多項式とし、$r$ を $p$ の単根とする。$\delta>0$ を、閉円板 $\overline D:=\{z\mid\lvert z-r\rvert\le\delta\}$ が $p$ のほかの根を含まないようにとる。このとき $\eta>0$ があって、$\lvert\varepsilon\rvert< \eta$ なら $p_\varepsilon=p+\varepsilon g$ は $\lvert z-r\rvert< \delta$ にちょうど 1 つの根 $r(\varepsilon)$ をもち(重複度を込めて 1 つ)、
$$ r(\varepsilon)=r-\frac{g(r)}{p'(r)}\,\varepsilon+o(\varepsilon)\qquad(\varepsilon\to0) $$
が成り立つ。

Rouché の定理で根を 1 つに絞り、等式 $p(r(\varepsilon))=-\varepsilon g(r(\varepsilon))$ を展開する

根がちょうど 1 つあること。 円周 $\Gamma:=\{\lvert z-r\rvert=\delta\}$ の上で $p$ は $0$ にならない($\overline D$ の中の $p$ の根は $r$ だけで、$r$ は円周の上にない)。$m:=\min_\Gamma\lvert p\rvert>0$、$M:=\max_\Gamma\lvert g\rvert$ とし、$\eta:=m/(M+1)$ とおく。$\lvert\varepsilon\rvert< \eta$ なら $\Gamma$ の上で $\lvert\varepsilon g\rvert\le\lvert\varepsilon\rvert M< m\le\lvert p\rvert$ なので、Rouchéの定理 により $p+\varepsilon g$ と $p$ は $\lvert z-r\rvert< \delta$ に重複度を込めて同じ個数の根をもつ。$p$ の根は単根 $r$ の 1 つだけなので、$p_\varepsilon$ の根もちょうど 1 つで、それを $r(\varepsilon)$ とおく。
$r(\varepsilon)\to r$ であること。 $0< \delta'< \delta$ について同じ議論を半径 $\delta'$ で行うと、$\lvert\varepsilon\rvert$ が十分小さければ $p_\varepsilon$ は $\lvert z-r\rvert< \delta'$ にも根を 1 つもつ。それは $\lvert z-r\rvert< \delta$ のただ 1 つの根 $r(\varepsilon)$ に等しいので、$\lvert r(\varepsilon)-r\rvert< \delta'$ である。$\delta'$ は任意なので $r(\varepsilon)\to r$ である。
1 次の項。 $h(\varepsilon):=r(\varepsilon)-r$ とおく。$p(r)=0$ なので、多項式の展開により $p(r+h)=p'(r)h+h^2q(h)$ と書ける($q$ は $r$ と $h$ の多項式)。$p_\varepsilon(r(\varepsilon))=0$ から
$$ h\bigl(p'(r)+h\,q(h)\bigr)=-\varepsilon\,g\bigl(r(\varepsilon)\bigr) $$
である。$\varepsilon\to0$ で $h\to0$ なので $p'(r)+hq(h)\to p'(r)\ne0$、$g(r(\varepsilon))\to g(r)$ であり、$\varepsilon\ne0$ で割って
$$ \frac{h}{\varepsilon}=-\frac{g(r(\varepsilon))}{p'(r)+h\,q(h)}\longrightarrow-\frac{g(r)}{p'(r)} $$
を得る。これが主張である。$\square$

この定理は「根の動きの速さは $g(r)$ に比例し、$p'(r)$ に反比例する」と述べる。$p'(r)=a_n\prod_{s\ne r}(r-s)$($s$ はほかの根)なので、ほかの根が近くになくても、ほかの根が多数あって積 $\prod\lvert r-s\rvert$ が係数の大きさに比べて小さいと、根は敏感になる。

根の条件数

$r\ne0$ を $p=\sum_ja_jx^j$ の単根とする。

  1. 係数 $a_j$ だけを $\delta$ 変えたとき、根は 1 次の近似で $-\delta\,r^j/p'(r)$ 動く。
  2. 各係数を $\lvert\delta a_j\rvert\le\epsilon\lvert a_j\rvert$ の範囲で変えたとき、根の相対的な変化の 1 次の項の最大値は $\epsilon\,\kappa(r)$、
    $$ \kappa(r):=\frac{\sum_{j=0}^n\lvert a_j\rvert\,\lvert r\rvert^j}{\lvert r\rvert\,\lvert p'(r)\rvert} $$
    である。

1 は thm-wp-first-order で $g=x^j$ とした場合である。2 は $g=\sum_j\gamma_jx^j$($\lvert\gamma_j\rvert\le\lvert a_j\rvert$)、$\varepsilon=\epsilon$ とした場合で、1 次の項 $-\epsilon g(r)/p'(r)$ を $r$ で割った大きさは $\epsilon\lvert\sum_j\gamma_jr^j\rvert/\lvert rp'(r)\rvert\le\epsilon\kappa(r)$ である。等号は $\gamma_j:=\lvert a_j\rvert\,\overline{r^j}/\lvert r^j\rvert$ でとれる(このとき $\sum_j\gamma_jr^j=\sum_j\lvert a_j\rvert\lvert r\rvert^j$)。$\square$

$\kappa(r)$ は、係数を一様な相対誤差 $\epsilon$ で丸めたとき、根の相対誤差が $\epsilon$ の何倍になりうるかを表す量で、誤差(数値解析) の相対条件数をこの問題に当てたものである。

Wilkinson の多項式での値

導関数の値と最も敏感な根

$1\le k\le20$ について $w'(k)=(-1)^{20-k}(k-1)!\,(20-k)!$ である。とくに根 $k$ の $a_{19}$ に対する感度は
$$ s_k:=\Bigl\lvert\frac{\partial r_k}{\partial a_{19}}\Bigr\rvert=\frac{k^{19}}{(k-1)!\,(20-k)!} $$
で、$s_k$ は $k\le16$ で増加し $k\ge16$ で減少する。最大は $s_{16}=\frac{16^{19}}{15!\,4!}\approx2.41\times10^9$ である。

積の微分と隣どうしの比

積の微分法により $w'(x)=\sum_{i=1}^{20}\prod_{j\ne i}(x-j)$ で、$x=k$ では $i\ne k$ の項はどれも因子 $x-k$ を含んで $0$ になるので、$w'(k)=\prod_{j\ne k}(k-j)$ である。$j< k$ の因子の積は $(k-1)(k-2)\cdots1=(k-1)!$、$j>k$ の因子の積は $(-1)(-2)\cdots(-(20-k))=(-1)^{20-k}(20-k)!$ である。$s_k$ の式は cor-wp-condition の 1 で $j=19$ とした値の絶対値である。
$1\le k\le19$ で隣どうしの比は
$$ \frac{s_{k+1}}{s_k}=\Bigl(1+\frac1k\Bigr)^{19}\frac{20-k}{k} $$
である。$k\le15$ では $(1+\frac1k)^{19}\ge(1+\frac1{15})^{19}$ で、$(1+\frac1{15})^{19}\ge1+\frac{19}{15}+\binom{19}2\frac1{225}=1+\frac{19}{15}+\frac{171}{225}>3$(二項展開の最初の 3 項)、$\frac{20-k}k\ge\frac13$ なので比は $1$ より大きい。$k\ge16$ では $\frac{20-k}k\le\frac14$ で、$(1+\frac1k)^{19}\le e^{19/k}\le e^{19/16}< e^{1.19}< 3.3< 4$ なので比は $1$ より小さい。よって $s_k$ は $k=16$ で最大である。$\square$

$\lvert a_{19}\rvert=210$ なので、$a_{19}$ を相対的に $\epsilon$ 変えたときの根 $16$ の相対的な動きは 1 次でおよそ $210\times2.41\times10^9/16\,\epsilon\approx3.2\times10^{10}\epsilon$ である。すべての係数の相対誤差を許した条件数 $\kappa(r_k)$ はさらに大きく、$\kappa(10)\approx5.6\times10^{12}$、$\kappa(14)\approx5.4\times10^{13}$、$\kappa(16)\approx3.5\times10^{13}$、$\kappa(20)\approx1.4\times10^{11}$ で、小さい根でも $\kappa(1)\approx420$、$\kappa(5)\approx8.2\times10^8$ である。

後退誤差

条件数は「係数を変えたら根がどれだけ動くか」を測る。逆向きに、「点 $z$ を根にするには係数をどれだけ変えればよいか」は、次の式で正確に分かる。

根の後退誤差

$p(x)=\sum_{j=0}^na_jx^j$ を複素係数の多項式、$z\in\mathbb C$、$\eta\ge0$ とし、$S(z):=\sum_j\lvert a_j\rvert\lvert z\rvert^j>0$ とする。次は同値である。

  1. 各 $j$ で $\lvert\tilde a_j-a_j\rvert\le\eta\lvert a_j\rvert$ を満たす複素数 $\tilde a_j$ で、$\tilde p(x):=\sum_j\tilde a_jx^j$ が $\tilde p(z)=0$ となるものがある。
  2. $\lvert p(z)\rvert\le\eta\,S(z)$。
    とくに、1 を満たす $\eta$ の最小値は $\eta(z):=\lvert p(z)\rvert/S(z)$ である。$p$ の係数と $z$ がどちらも実数なら、1 の $\tilde a_j$ は実数にとれる。
摂動を $z^j$ の偏角にそろえる

1 ⇒ 2。 $\tilde p(z)=0$ なので $p(z)=p(z)-\tilde p(z)=\sum_j(a_j-\tilde a_j)z^j$ で、三角不等式から $\lvert p(z)\rvert\le\sum_j\eta\lvert a_j\rvert\lvert z\rvert^j=\eta S(z)$ である。
2 ⇒ 1。 $z^j\ne0$ のとき $\theta_j:=\overline{z^j}/\lvert z^j\rvert$、$z^j=0$($z=0$、$j\ge1$)のとき $\theta_j:=0$ とおき、
$$ \tilde a_j:=a_j-\frac{p(z)}{S(z)}\,\lvert a_j\rvert\,\theta_j $$
とおく。$\theta_jz^j=\lvert z\rvert^j$($z^j=0$ のときも両辺 $0$)なので
$$ \tilde p(z)=p(z)-\frac{p(z)}{S(z)}\sum_j\lvert a_j\rvert\lvert z\rvert^j=p(z)-p(z)=0 $$
であり、$\lvert\tilde a_j-a_j\rvert\le\frac{\lvert p(z)\rvert}{S(z)}\lvert a_j\rvert\le\eta\lvert a_j\rvert$ である。$a_j$ と $z$ が実数なら $\theta_j=\pm1$ または $0$ で、$p(z)/S(z)$ も実数なので $\tilde a_j$ は実数である。
最小値の主張は、2 を満たす $\eta$ の最小値が $\lvert p(z)\rvert/S(z)$ であることから従う。$\square$

近似の根 $\hat r$ を計算したとき、$\eta(\hat r)$ が丸めの単位(倍精度で約 $1.1\times10^{-16}$)程度なら、$\hat r$ は「係数を丸めの程度だけ変えた多項式の正確な根」であり、計算は後退安定と言える。そのとき実際の誤差は、cor-wp-condition の 2 で $\epsilon=\eta(\hat r)$ とすると、1 次で高々 $\kappa\cdot\eta(\hat r)$ 程度の相対誤差である(誤差(数値解析) の命題「前進誤差は条件数と後退誤差の積で決まる」と同じ考え方)。条件数が $10^{13}$ なら、後退誤差が $10^{-16}$ でも相対誤差は $10^{-3}$ になりうる。

尺度によらないこと

根が $1,2,\dots,20$ と大きいから敏感なのではない。根を一斉に縮めても、相対条件数は変わらない。

相対条件数は根の尺度によらない

$p(x)=\sum_{j=0}^na_jx^j$($a_n\ne0$)、$c\in\mathbb C\setminus\{0\}$ とし、$q(x):=c^{-n}p(cx)$ とおく。$r\ne0$ が $p$ の単根なら $r/c$ は $q$ の単根で、cor-wp-condition の条件数について $\kappa_q(r/c)=\kappa_p(r)$ である。

$q(x)=\sum_jb_jx^j$、$b_j=c^{j-n}a_j$ であり、$q'(x)=c^{1-n}p'(cx)$ なので $q(r/c)=0$、$q'(r/c)=c^{1-n}p'(r)\ne0$ である。よって
$$ \kappa_q(r/c)=\frac{\sum_j\lvert c\rvert^{j-n}\lvert a_j\rvert\,\lvert r\rvert^j\lvert c\rvert^{-j}}{\lvert r/c\rvert\,\lvert c\rvert^{1-n}\lvert p'(r)\rvert}=\frac{\lvert c\rvert^{-n}\sum_j\lvert a_j\rvert\lvert r\rvert^j}{\lvert c\rvert^{-n}\lvert r\rvert\,\lvert p'(r)\rvert}=\kappa_p(r) $$
である。$\square$

$c=20$ とすると、根が $0.05,0.10,\dots,1$ の多項式 $\prod_{k=1}^{20}(x-\frac k{20})$ は $w$ とまったく同じ相対条件数をもつ(Wil59 p. 153 が同じことを注意している)。悪さの原因は、根の数が多く、根がすべて正の実軸の片側に並んでいるために、$x^j$ を基底とする係数の表示で大きな係数どうしが打ち消し合っていることにある。

計算の手順

多項式の根を係数から求めるとき、結果がどれだけ信用できるかを次の手順で見積もる。

  1. 根の近似 $\hat r$ を求める(たとえば 同伴行列 の固有値として)。
  2. $\hat r$ での $p'(\hat r)$ と $S(\hat r)=\sum_j\lvert a_j\rvert\lvert\hat r\rvert^j$ を計算し、条件数 $\kappa(\hat r)$ を見積もる(cor-wp-condition)。
  3. 後退誤差 $\eta(\hat r)=\lvert p(\hat r)\rvert/S(\hat r)$ を計算する(thm-wp-backward)。$p(\hat r)$ の計算自体にも丸めがあるので、桁数の多い計算か、Horner 法の誤差の上界を併せて使う。
  4. 相対誤差の見積もりは $\kappa(\hat r)\,\eta(\hat r)$ である。係数そのものに相対誤差 $\epsilon$ があるなら、$\kappa\,\epsilon$ が根の精度の限界になる。
  5. 見積もりが大きすぎるときは、問題の立て方を変える。根を固有値とする行列がもともと与えられているなら、特性多項式を経由せずに行列の固有値を直接計算する。区間の上の多項式なら、$x^j$ でなく区間に合った基底(Chebyshev 多項式など)で表す(Tre11 の Myth 6)。
    手順 4 の見積もりは 1 次の近似であり、$\kappa\epsilon$ が $1$ に比べて小さくないときは当てにならない(ex-wp-complex)。

例題

$x^{19}$ の係数を $2^{-23}$ 減らす

$w_\varepsilon(x):=w(x)-\varepsilon x^{19}$、$\varepsilon:=2^{-23}\approx1.19\times10^{-7}$ の根を求める。$a_{19}=-210$ が $-210-2^{-23}$ に変わり、相対的な変化は約 $5.7\times10^{-10}$ である。
答え:根は $1,2,3$(小数点以下 10 桁まで変わらない)、$4.0000000003$、$4.99999993$、$6.0000069$、$6.9996972$、$8.0072676$、$8.9172502$、$20.8469081$ の 10 個の実根と、
$$ 10.0952661\pm0.6435009i,\quad11.7936339\pm1.6523297i,\quad13.9923581\pm2.5188301i,\quad16.7307375\pm2.8126249i,\quad19.5024394\pm1.9403303i $$
の 5 組の共役な複素根である。これは Wil59 p. 153 の Example 1 の値(原論文の多項式は $(x+1)\cdots(x+20)+2^{-23}x^{19}$ なので符号が逆)と一致する。
1 次の近似では、根 $k$ は $\varepsilon\,k^{19}/w'(k)$ だけ実軸の上を動くはずである(cor-wp-condition の 1 で $\delta=-\varepsilon$)。根 $20$ では予測は $20+\varepsilon\cdot20^{19}/19!\approx25.14$ だが、実際の根は $20.85$ で、$16$ から $19$ の根は実軸を離れて複素数の対になっている。この大きさの $\varepsilon$ ではもう 1 次の近似は使えない。$20$ より大きい実根があることは計算せずに分かる:$w_\varepsilon(20)=-\varepsilon\cdot20^{19}< 0$ で、$x\to\infty$ で $w_\varepsilon(x)\to+\infty$ なので、中間値の定理により $(20,\infty)$ に根がある。

摂動が十分小さい場合

$\varepsilon:=2^{-55}\approx2.8\times10^{-17}$ とし、$w(x)-\varepsilon x^{19}$ の根を求める。
答え:根はすべて実数で、根 $k$ の動きは 1 次の近似 $\varepsilon k^{19}/w'(k)$ と相対誤差 $10^{-7}$ 以下で一致する。最も動くのは根 $16$ で、動きは $\varepsilon\cdot2.41\times10^9\approx6.7\times10^{-8}$ である(Wil59 p. 153 の Example 2 と同じ)。

読み方を開く

ex-wp-complex と合わせると、根の動きが $\varepsilon$ について線形とみなせるのは $\varepsilon s_{16}$ が根の間隔 $1$ よりずっと小さい範囲で、$\varepsilon\approx10^{-7}$ ではもう線形でない。

後退誤差の値

thm-wp-backward の $\eta(z)=\lvert w(z)\rvert/\sum_j\lvert a_j\rvert\lvert z\rvert^j$ を計算する。
答え:$\eta(15.5)\approx4.7\times10^{-16}$、$\eta(20.5)\approx6.5\times10^{-13}$、$\eta(16.73+2.81i)\approx7.2\times10^{-13}$、$\eta(1.5)\approx4.4\times10^{-5}$ である。
$15.5$ は $w$ の 2 つの根のちょうど中間にあるが、係数を相対的に $5\times10^{-16}$(倍精度の丸めの単位の数倍)だけ変えた実係数の多項式の正確な根になる。倍精度の係数から計算する限り、根 $15$・$16$ の近くの点を根として区別できない。一方 $1.5$ を根にするには係数を相対的に $4\times10^{-5}$ 変える必要があり、小さい根はよく決まる。

次数とともに悪くなる

$w_n=\prod_{k=1}^n(x-k)$ で、$x^{n-1}$ の係数に対する根の感度の最大値 $\max_k\frac{k^{n-1}}{(k-1)!\,(n-k)!}$(prop-wp-derivative と同じ計算)を比べる。
答え:$n=5$ で $43$、$n=10$ で $1.3\times10^4$、$n=15$ で $5.4\times10^6$、$n=20$ で $2.4\times10^9$ である。

読み方を開く

次数が 5 増えるごとにおよそ $300$ 倍から $450$ 倍になる。根の間隔は $n$ によらず $1$ なので、悪さは根が近いことではなく、次数が高いことから来る。

同じ根をもつ行列の固有値は動かない

$D:=\operatorname{diag}(1,2,\dots,20)$ の固有値は $w$ の根である。$D$ に誤差 $E$ を加えた対称行列 $D+E$ の固有値はどれだけ動くか。
答え:Weylの不等式(固有値) により、$E$ が対称なら固有値は大きさの順に対応させて $\|E\|_2$ 以下しか動かない($\|\cdot\|_2$ は 作用素ノルム)。$\|E\|_2=10^{-10}$ なら固有値の誤差は $10^{-10}$ 以下である。

特性多項式を経由した場合を開く

同じ固有値を特性多項式 $w$ の係数から求めると、係数の相対誤差 $10^{-10}$ で根は ex-wp-complex と同じ程度に大きくずれる。固有値の問題自体は条件がよいのに、特性多項式の係数に移す段階で条件の悪い問題に作り替えてしまう。これが Wil59 §4(pp. 153–155)が論じた点である。

使える条件と反例

外した仮定反例成り立たなくなる結論
根が単根(thm-wp-first-order)$p=(x-1)^2$、$g=-1$$p_\varepsilon$ の根は $1\pm\sqrt\varepsilon$ で、$r(\varepsilon)=r+O(\varepsilon)$ の形の 1 次の展開がない($\varepsilon>0$ で $\lvert r(\varepsilon)-1\rvert/\varepsilon=\varepsilon^{-1/2}\to\infty$)
$\varepsilon\to0$ の極限(thm-wp-first-order の 1 次の近似を固定の $\varepsilon$ で使う)$w$、$g=-x^{19}$、$\varepsilon=2^{-23}$(ex-wp-complex)近似 $r(\varepsilon)\approx r-\varepsilon g(r)/p'(r)$ が成り立たない:根 $20$ の予測 $25.14$ に対し実際は $20.85$、予測では実数のままの根 $16$〜$19$ が複素数になる
実数の摂動でよいという但し書きの仮定 $z\in\mathbb R$(thm-wp-backward。実係数の $p$ と実数でない $z$)$p=x-1$、$z=i$2 ⇒ 1 が実数の摂動では成り立たない:$\lvert p(i)\rvert=\sqrt2=\eta S(i)$($\eta=1/\sqrt2$)だが、$\lvert\tilde a_j-a_j\rvert\le\eta\lvert a_j\rvert$ の実数の $\tilde a_j$ では $i$ は根にならない
表の確かめを開く

1 行目:$(x-1)^2-\varepsilon=0$ は $x=1\pm\sqrt\varepsilon$ で、$\varepsilon\to0$ で $\sqrt\varepsilon/\varepsilon\to\infty$ なので、根の動きは $\varepsilon$ の 1 次で抑えられない。cor-wp-condition の式でも $p'(1)=0$ で条件数は定義されない。2 行目は ex-wp-complex の計算による。3 行目:$S(i)=\lvert1\rvert\lvert i\rvert+\lvert-1\rvert=2$ である。実数の摂動は $\tilde p=(1+\alpha)x-(1+\beta)$($\lvert\alpha\rvert,\lvert\beta\rvert\le1/\sqrt2$)で、$1+\alpha\ne0$ なので根は実数 $(1+\beta)/(1+\alpha)$ だけである。thm-wp-backward の「実係数・実数の $z$ なら実数の摂動でよい」という但し書きは、$z$ が実数でないときには外せない。

よくある誤り

誤り正しくはなぜ
根どうしが離れていれば根は係数に鈍感である離れていても敏感なことがある感度は $1/\lvert p'(r)\rvert=1/\prod_{s\ne r}\lvert r-s\rvert$ と係数の大きさの比で決まる(cor-wp-condition)
根が大きい($1$〜$20$)から悪いので、縮めればよい縮めても相対条件数は同じprop-wp-scale
計算した根で $p(\hat r)$ が小さければ根は正確である後退誤差が小さいだけで、前進誤差は条件数倍になりうるthm-wp-backward と ex-wp-backward
悪いのは根を求めるアルゴリズムである係数から根への写像そのものの条件が悪いどのアルゴリズムでも、係数の丸めだけで ex-wp-complex 程度の誤差が生じうる
固有値は特性多項式の根として求めればよい行列から直接求めるex-wp-eigen

補足

Wilkinson は、行列の固有値を特性多項式の根として計算する方法を検討する中でこの例を挙げ、行列の要素の誤差が固有値をほとんど動かさなくても、特性多項式の係数を桁数の足りない計算で求めると根が大きく狂うことを示した(Wil59 §4、pp. 153–155)。今日では、多項式の根を求めるのに 同伴行列 の固有値を QR法(固有値) で計算するのが標準で、根を固有値として求める向きの計算はこの例と矛盾しない。悪いのは、固有値の問題を係数の問題に移すことである。
単位円の近くにある根は $x^j$ の係数に対して条件がよく、区間 $[-1,1]$ に並ぶ根は条件が悪くなりうる。区間の上の多項式を Chebyshev 多項式の 1 次結合で表すと、区間の近くの根はその係数に対して条件がよくなる(Tre11 の Myth 6。この記事では証明しない)。Wilkinson の多項式の悪さは、多項式そのものではなく「$x^j$ の係数で表す」という表し方に付いている。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する