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$ で、相対条件数は根の尺度によらない。固有値を特性多項式の根として求める危うさを示す例である。
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)を示す。
$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$ であることをいう。根の動きを調べる問題の設定は次のとおりである。
$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$ 動く。
$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)
$$
が成り立つ。
根がちょうど 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 は 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$ の何倍になりうるかを表す量で、誤差(数値解析) の相対条件数をこの問題に当てたものである。
$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 ⇒ 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$ を基底とする係数の表示で大きな係数どうしが打ち消し合っていることにある。
多項式の根を係数から求めるとき、結果がどれだけ信用できるかを次の手順で見積もる。
$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アソシエイト)の紹介料で運営されています。 支援について / 寄付する