アバース法

アベルト法、またはアベルト・エーリッヒ法、エーリッヒ・アベルト法は、オリバー・アベルト^[1]とルイス・W・エーリッヒ^{[2]にちなんで名付けられ、1967年に開発された、}単変数多項式のすべての根を同時に近似する根探索アルゴリズムです。

この方法は3次収束します。これは、すべての根を一度に近似する別のアルゴリズムであるデュラン・ケルナー法の改良版で、2次収束します。 ^{[1] [2] （ただし、両方のアルゴリズムは}複数のゼロ で線形収束します。^[3]）

この方法は、多項式のすべての根を任意の精度で近似するためのリファレンス ソフトウェアである MPSolveで使用されます。

を実数または複素係数を持つ次数 の単変数多項式とします。このとき、の根である複素数 が存在し、 を因数分解します。 ${\displaystyle p(x)=p_{n}x^{n}+p_{n-1}x^{n-1}+\cdots +p_{1}x+p_{0}}$${\displaystyle n}$${\displaystyle z_{1}^{*},\,z_{2}^{*},\dots ,z_{n}^{*}}$${\displaystyle p(x)}$

${\displaystyle p(x)=p_{n}\cdot (x-z_{1}^{*})\cdot (x-z_{2}^{*})\cdots (x-z_{n}^{*}).}$

これらの数は未知ですが、その絶対値の上限と下限は多項式の係数から計算できます。これで、複素平面で、ランダムまたは均等に分布した異なる数を選択して、その絶対値が同じ範囲内に収まるようにすることができます。(また、ゼロが対称である場合、開始点は同じ軸に沿って正確に対称であってはなりません。そうしないと、収束が妨げられる可能性があります。) ^[1] このような数の集合は、の根の集合の初期近似と呼ばれます。この近似は、次の手順を使用して反復的に改善できます。 ${\displaystyle n}$${\displaystyle p(x)}$

を の零点の現在の近似値とする。するとオフセット数は次のように計算される。 ${\displaystyle z_{1},\dots ,z_{n}\in \mathbb {C} }$${\displaystyle p(x)}$${\displaystyle w_{1},\dots ,w_{n}\in \mathbb {C} }$

${\displaystyle w_{k}={\frac {\frac {p(z_{k})}{p'(z_{k})}}{1-{\frac {p(z_{k})}{ p'(z_{k})}}\cdot \sum _{j\neq k}{\frac {1}{z_{k}-z_{j}}}},}$

ここで、 は点 で評価されたの多項式導関数です。 ${\displaystyle p'(z_{k})}$${\displaystyle p}$${\displaystyle z_{k}}$

の根の次の近似集合は です。多項式の値またはオフセットのサイズによって、現在の近似の品質を測定できます。 ${\displaystyle p(x)}$${\displaystyle z_{1}-w_{1},\dots ,z_{n}-w_{n}}$

概念的には、この方法は静電気のアナロジーを採用しており、近似零点を可動の負の点電荷としてモデル化し、固定の正の点電荷で表される真の零点に向かって収束します。^[1] ニュートン法を各近似​​零点に直接適用すると、複数の開始点が誤って同じ根に収束することがよくあります。アベルト法では、可動電荷が互いに及ぼす反発効果もモデル化することでこれを回避します。このように、可動電荷が零点に収束すると、それらの電荷は打ち消されるため、他の可動電荷はその場所に引き寄せられなくなり、他の「空いている」零点に収束するように促されます。(スティルチェスは、静電気の問題の解として多項式の零点の位置もモデル化しました。)

アベルト法の公式の中には、ニュートン法とデュラン・ケルナー法の要素が含まれています。効率的な実装、特に適切な初期近似値の選択に関する詳細は、Bini (1996) に記載されています。^[3]

根の更新は、最初にすべての新しい近似値が古い近似値から計算される同時ヤコビ型反復として実行されるか、または計算された時点から新しい近似値を使用する順次ガウス-ザイデル型反復として実行されます。

非常によく似た方法は、ニュートン・マーリー法です。この方法では、ゼロを次々に計算しますが、明示的なデフレーションの代わりに、すでに取得されている線形因子でその場で割ります。アバース法は、他の根をすでに見つけているかのようにして最後の根を計算するという点で、ニュートン・マーリー法に似ています。^[4]

反復式は関数に対する一変量ニュートン反復である。

${\displaystyle F(x)={\frac {p(x)}{\prod _{j=1;\,j\neq k}^{n}(x-z_{j})}}}$

値がすでに の根に近い場合、有理関数はに近い優勢根を持つほぼ線形であり、の極はニュートン反復を、それに近いp(x)の根から遠ざける方向に向けます。つまり、対応する吸引域はかなり小さくなりますが、 に近い根は広い吸引領域を持ちます。 ${\displaystyle z_{1},\dots ,z_{n}}$${\displaystyle p(x)}$${\displaystyle F(x)}$${\displaystyle z_{k}}$${\displaystyle z_{1},\dots ,z_{k-1},z_{k+1},\dots ,z_{n}}$${\displaystyle z_{k}}$

単変量の場合のニュートンステップは対数微分に対する逆数値である。 ${\displaystyle {\tfrac {F(x)}{F'(x)}}}$

${\displaystyle {\begin{aligned}{\frac {F'(x)}{F(x)}}&={\frac {d}{dx}}\ln |F(x)|\\&={\frac {d}{dx}}{\big (}\ln |p(x)|-\sum _{j=1;\,j\neq k}^{n}\ln |x-z_{j}|{\big )}\\&={\frac {p'(x)}{p(x)}}-\sum _{j=1;\,j\neq k}^{n}{\frac {1}{x-z_{j}}}\end{aligned}}}$

したがって、新しい近似値は次のように計算される。

${\displaystyle z_{k}'=z_{k}-{\frac {F(z_{k})}{F'(z_{k})}}=z_{k}-{\frac {1}{ {\frac {p'(z_{k})}{p(z_{k})}}-\sum _{j=1;\,j\neq k}^{n}{\frac {1}{z_{k}-z_{j}}}}\,,}$

これはAberth-Ehrlich法の更新式です。

• MPSolve多項式の根の数値計算用パッケージ。科学的な目的であれば無料で使用できます。