ウィルキンソンの多項式

数値解析において、ウィルキンソンの多項式は、多項式の根を求める際の難しさを説明するために 1963 年にJames H. Wilkinsonによって使用された特定の多項式です。根の位置は、多項式の係数の摂動に非常に敏感になる可能性があります。

多項式は 、ウィルキンソンの多項式 という用語は、ウィルキンソンの議論に登場する他のいくつかの多項式を指すために使用されることもあります。 $${\displaystyle w(x)=\prod _{i=1}^{20}(xi)=(x-1)(x-2)\cdots (x-20).}$$

ウィルキンソンの多項式は、多項式の根を求めるアルゴリズムの研究で生まれました 。係数c _iからp の根を求める問題が条件付きであるかどうかを尋ねるのは、数値解析における自然な疑問です。つまり、係数の小さな変化が根の小さな変化につながることを期待します。残念ながら、この場合は当てはまりません。 $${\displaystyle p(x)=\sum _{i=0}^{n}c_{i}x^{i}.}$$

多項式に多重根がある場合、問題は悪条件になります。たとえば、多項式x ^2はx = 0に二重根を持ちます 。ただし、多項式x ² − ε (サイズεの摂動 ) は±√ εに根を持ち、 εが小さい場合はεよりもはるかに大きくなります。

したがって、多項式の零点が非常に近い場合にも悪条件が発生すると予想するのは当然です。ただし、零点が十分に離れた多項式の場合も、この問題は極めて悪条件になる可能性があります。ウィルキンソンは、この点を説明するために多項式w ( x ) を使用しました(Wilkinson 1963)。

1984 年に彼はこの発見が個人的に与えた影響について次のように語っています。

私自身のことを言えば、これは数値分析家としての私のキャリアの中で最もトラウマ的な経験だったと思います。^[1]

ウィルキンソンの多項式は、行列の特性多項式の係数を最初に計算し、次にその根を見つけることによって行列の固有値を単純に計算することの望ましくないことを示すためによく使用されます。これは、係数を中間ステップとして使用すると、元の問題が適切に条件付けされていたとしても、極端に条件付けが悪くなる可能性があるためです。^[2]

ウィルキンソンの多項式には 明らかに 20 個の根があり、x = 1, 2, ..., 20にあります。これらの根は離れています。しかし、多項式はまだ非常に悪条件です。 $${\displaystyle w(x)=\prod _{i=1}^{20}(xi)=(x-1)(x-2)\cdots (x-20)}$$

多項式を展開すると、 $${\displaystyle {\begin{aligned}w(x)={}&x^{20}-210x^{19}+20615x^{18}-1256850x^{17}+53327946x^{16}\\&{}-1672280820x^{15}+40171771630x^{14}-756111184500x^{13}\\&{}+11310276995381x^{12}-135585182899530x^{11}\\&{}+1307535010540395x^{10}-10142299865511450x^{9}\\&{}+63030812099294896x^{8}-311333643161390640x^{7}\\&{}+1206647803780373360x^{6}-3599979517947607200x^{5}\\&{}+8037811822645051776x^{4}-12870931245150988800x^{3}\\&{}+13803759753640704000x^{2}-8752948036761600000x\\&{}+2432902008176640000.\end{aligned}}}$$

x ¹⁹の係数が −210 から 2 ⁻²³ずつ減少して−210.0000001192 になると、多項式の値w (20) は 0 から −2 ⁻²³ 20 ¹⁹  = −6.25×10 ¹⁷に減少し、x = 20の根はx ≈ 20.8に増えます。 x = 18とx = 19の根はx ≈ 18.62で二重根に衝突し、摂動がさらに大きくなるとx ≈ 19.5 ± 1.9 iで複素共役根のペアになります。 20 個の根は (小数点以下 5 桁まで) $${\displaystyle {\begin{array}{rrrrr}1.00000&2.00000&3.00000&4.00000&5.00000\\[8pt]6.00001&6.99970&8.00727&8.91725&20.84691\\[8pt]10.09527\pm {}&11.79363\pm {}&13.99236\pm {}&16.73074\pm {}&19.50244\pm {}\\[-3pt]0.64350i&1.65233i&2.51883i&2.81262i&1.94033i\end{array}}}$$

係数の変化はごくわずかで、元の根の間隔が広いように見えますが、根の一部は大きくずれています。ウィルキンソンは、次のセクションで説明する安定性解析によって、この動作は、一部の根α ( α  = 15など) には、| α  −  β | が | α | よりも小さいという意味で「近い」根βが多数あるという事実に関連していることを示しました。

^{ウィルキンソンが 2 −23}の摂動を選択したのは、彼のPilot ACEコンピュータが 30 ビットの浮動小数点 仮数部を持っていたため、210 付近の数値については、 2 ^{−23 は}コンピュータで表現されない最初のビット位置のエラーだったからである。2 つの実数、−210 と −210 − 2 ⁻²³は同じ浮動小数点数で表される。つまり、2 ^{−23は、そのコンピュータ上で −210 に近い実係数を浮動小数点数で表現する際に}避けられないエラーである。摂動解析により、30 ビットの係数精度ではウィルキンソンの多項式の根を分離するには不十分である ことが示された。

多項式c ( x )の小さな倍数t · c ( x )を加えることで、 根α _jを持つ多項式p ( x ) = Π ( x − α _j )を摂動させ、これが根α _{j に}どのような影響を与えるかを尋ねるとします。第一に、根の変化は導関数によって制御されます。 導関数が小さい場合、根はt の変化に対してより安定し、逆にこの導関数が大きい場合は根は不安定になります。特に、α _jが多重根である場合、分母はゼロになります。この場合、 α _{j は通常}tに関して微分可能ではなく( c が偶然そこでゼロになる場合を除く)、根は非常に不安定になります。 $${\displaystyle {d\alpha _{j} \over dt}=-{c(\alpha _{j}) \over p^{\prime }(\alpha _{j})}.}$$

tの値が小さい場合、摂動根はtのべき級数展開によって与えられ 、| t | がこのべき級数の収束半径より大きい場合に問題が発生することが予想されます。この収束半径は、根α _jが倍数になるような | t | の最小値によって与えられます。この半径の非常に大まかな推定値は、 α _jから最も近い根までの距離の半分を取り、上記の導関数で割ります。 $${\displaystyle \alpha _{j}+{d\alpha _{j} \over dt}t+{d^{2}\alpha _{j} \over dt^{2}}{t^{2} \over 2!}+\cdots }$$

20 次ウィルキンソン多項式の例では、根はα _j = j （ j = 1, ..., 20 ）で与えられ、c ( x ) はx ¹⁹に等しくなります。したがって、導関数は次のように与えられます。これは 、 α _jに近い根α _{k が}多数ある場合 、つまりそれらの間の距離 |α _j  − α _{k | が |α j} |よりも小さい場合、 根α _{j は}安定性が低くなることを示しています。 $${\displaystyle {d\alpha _{j} \over dt}=-{\alpha _{j}^{19} \over \prod _{k\neq j}(\alpha _{j}-\alpha _{k})}=-\prod _{k\neq j}{\alpha _{j} \over \alpha _{j}-\alpha _{k}}.\,\!}$$

例: 根 α ₁  = 1 の場合、導関数は 1/19! に等しく、非常に小さい値です。この根はtが大きく変化しても安定しています。これは、他のすべての根β がこの値から大きく離れているためです。つまり、 | α ₁  −  β | = 1, 2, 3, ..., 19 は | α ₁ | = 1より大きい値です。たとえば、tが –10000000000 と大きくても、根α _{1 は1 から約 0.99999991779380 までしか変化しません (これは、1 次近似 1 +} t /19! ≈ 0.99999991779365に非常に近い値です )。同様に、ウィルキンソンの多項式の他の小さな根はtの変化の影響を受けません 。

例。一方、根α ₂₀  = 20 の場合、導関数は −20 ¹⁹ /19! に等しく、これは非常に大きい (約 43000000) ため、この根はtの小さな変化に非常に敏感です。他の根βは、| β  −  α _{20 | = 1, 2, 3, ..., 19 が |} α ₂₀ | = 20より小さいという意味で、α ₂₀に近いです。t = −2  ^{− 23}の場合、摂動根 20.84... の1 次近似 20 −  t ·20 ¹⁹ /19! = 25.137... はひどいものです。これは、摂動根の虚数部が大きいが、 1 次近似 (およびすべての高次近似) が実数である根α ₁₉の場合はさらに明白です。この食い違いの理由は、| t | ≈ 0.000000119 が、前述のべき級数の収束半径 (約 0.0000000029 で、大まかな推定値である 0.00000001 よりいくらか小さい) より大きいため、線形化理論は適用されないためです。t = 0.000000001 のように、この収束半径より大幅に小さい値の場合、 1 次近似値 19.9569... は、ルート 19.9509... にかなり近くなります。

一見すると、ウィルキンソンの多項式の根α ₁ = 1 とα ₂₀ = 20 は、対称的な根の線の反対側の端にあり、他の根から同じ距離のセット 1、2、3、...、19 を持っているため、似ているように見えます。しかし、上記の分析は、これが非常に誤解を招くことを示しています。根α ₂₀ = 20 は、α _{1 = 1 よりも (} x ¹⁹の係数の小さな摂動に対して) 20 ¹⁹ = 5242880000000000000000000倍不安定です。

ウィルキンソンが考察した 2 番目の例は、 この多項式の 20 個の零点は公比 2 の等比数列になっているため、商は 大きくなりません。実際、 w ₂ の零点は係数の 相対的な大きな変化に対して非常に安定しています。$${\displaystyle w_{2}(x)=\prod _{i=1}^{20}(x-2^{-i})=(x-2^{-1})(x-2^{-2})\cdots (x-2^{-20}).}$$$${\displaystyle \alpha _{j} \over \alpha _{j}-\alpha _{k}}$$

展開は、 多項式を特定の基底、すなわち単項式の基底で表現します。多項式が別の基底で表現されると、その根を求める問題は悪条件ではなくなる可能性があります。たとえば、ラグランジュ形式では、1つ（または複数）の係数を少し変更しても、根はそれほど変化しません。実際、点0、1、2、...、20での補間の基底多項式は、 $${\displaystyle p(x)=\sum _{i=0}^{n}c_{i}x^{i}}$$$${\displaystyle \ell _{k}(x)=\prod _{i=0,\ldots ,20 \atop i\neq k}{\frac {x-i}{k-i}},\qquad {\text{for}}\quad k=0,\ldots ,20.}$$

すべての多項式（20 次以下）は、次の基底で表現できます。 $${\displaystyle p(x)=\sum _{i=0}^{20}d_{i}\ell _{i}(x).}$$

ウィルキンソンの多項式については、 $${\displaystyle w(x)=(20!)\ell _{0}(x)=\sum _{i=0}^{20}d_{i}\ell _{i}(x)\quad {\text{with}}\quad d_{0}=(20!),\,d_{1}=d_{2}=\cdots =d_{20}=0.}$$

ラグランジュ基底多項式ℓ ₀ ( x )の定義によれば、係数d ₀の変化はwの根に変化をもたらさない。しかし、他の係数（すべてゼロ）の摂動は根をわずかに変化させる。したがって、ウィルキンソンの多項式はこの基底において条件付きである。

ウィルキンソンは「彼の」多項式について論じた。

• JH Wilkinson (1959). 悪条件多項式の零点の評価。第1部。Numerische Mathematik 1 :150–166。
• JH Wilkinson (1963)。代数プロセスにおける丸め誤差。ニュージャージー州イングルウッドクリフス：Prentice Hall。

数値解析の標準的な教科書には次のように記載されています。

• FS Acton, Numerical methods that work、ISBN 978-0-88385-450-1、p. 201。 

その他の参考資料:

• ロナルド・G・モシエ（1986年7月）。多項式の根近傍。計算数学 47（175）：265–273。
• JH Wilkinson (1984)。The perfidious polynomial。数値解析研究、GH Golub 編、pp. 1–28。(数学研究、第 24 巻)。ワシントン DC: アメリカ数学協会。

高精度の数値計算は次のように提示されます。

• Ray Buvel、「多項式と有理関数」、RPN Calculator ユーザー マニュアル(Python 用) の一部、2006 年 7 月 29 日に取得。