ジェンキンス・トラウブアルゴリズム

次数nの現在の多項式P ( X )から始めて、最小の根を計算することが目的です。${\displaystyle \alpha }$P(x)の多項式は、線形因子と残りの多項式因子に分解できます。$${\displaystyle P(X)=(X-\alpha ){\bar {H}}(X)}$$他の根探索法は、主に根、ひいては第一因子を改善することを目的としている。ジェンキンス・トラウブ法の主な考え方は、第二因子を段階的に改善することである。

そのため、いわゆるH多項式の列が構築される。これらの多項式はすべて次数がn - 1であり、係数に収束すると想定されている。  $\displaystyle {\bar {H}}(X)}$P ( X )には、残りのすべての根の (線形因子) が含まれています。H 多項式の列は2 つのバリアントで現れます。1 つは簡単に理論的な洞察を可能にする非正規化バリアント、もう 1 つは正規化されたバリアントです。${\displaystyle {\bar {H}}}$係数を数値的に妥当な範囲に維持する多項式。H多項式の構成${\displaystyle \left(H^{(\lambda )}(z)\right)_{\lambda =0,​​1,2,\dots }}$複素数列によって導かれる${\displaystyle (s_{\lambda })_{\lambda =0,​​1,2,\dots }}$シフトと呼ばれる。これらのシフト自体は、少なくとも第 3 段階では、前のH多項式に依存する。H多項式は、暗黙の再帰の解として定義される。 $${\displaystyle H^{(0)}(z)=P^{\prime }(z)}$$そして$${\displaystyle (X-s_{\lambda })\cdot H^{(\lambda +1)}(X)\equiv H^{(\lambda )}(X){\pmod {P(X)}}\ .}$$ この陰方程式の直接解は $${\displaystyle H^{(\lambda +1)}(X)={\frac {1}{X-s_{\lambda }}}\cdot \left(H^{(\lambda )}(X)-{\frac {H^{(\lambda )}(s_{\lambda })}{P(s_{\lambda })}}P(X)\right)\,,}$$ ここで、多項式の除算は正確である。

アルゴリズム的には、ホーナー法やルフィニ法のように線形因子による長除法を用いて多項式を評価する。$s_{\lambda }}$そして同時に商も得る。得られた商p ( X ) とh ( X ) を中間結果として用いると、次のH多項式は次のように得られる。 $${\displaystyle \left.{\begin{aligned}P(X)&=p(X)\cdot (X-s_{\lambda })+P(s_{\lambda })\\H^{(\lambda )}(X)&=h(X)\cdot (X-s_{\lambda })+H^{(\lambda )}(s_{\lambda })\\\end{aligned}}\right\}\implies H^{(\lambda +1)}(z)=h(z)-{\frac {H^{(\lambda )}(s_{\lambda })}{P(s_{\lambda })}}p(z).}$$ 最高次係数はP(X)から得られるので、${\displaystyle H^{(\lambda +1)}(X)}$は${\displaystyle -{\tfrac {H^{(\lambda )}(s_{\lambda })}{P(s_{\lambda })}}}$これを割り切ると、正規化されたH多項式は次のようになります 。$${\displaystyle {\begin{aligned}{\bar {H}}^{(\lambda +1)}(X)&={\frac {1}{X-s_{\lambda }}}\cdot \left(P(X)-{\frac {P(s_{\lambda })}{H^{(\lambda )}(s_{\lambda })}}H^{(\lambda )}(X)\right)\\[1em]&={\frac {1}{X-s_{\lambda }}}\cdot \left(P(X)-{\frac {P(s_{\lambda })}{{\bar {H}}^{(\lambda )}(s_{\lambda })}}{\bar {H}}^{(\lambda )}(X)\right)\,.\end{aligned}}}$$

させて${\displaystyle \alpha _{1},\dots ,\alpha _{n}}$P ( X )の根は、 P(X)のいわゆるラグランジュ因子であり、これらの根の余因子である。 $${\displaystyle P_{m}(X)={\frac {P(X)-P(\alpha _{m})}{X-\alpha _{m}}}.}$$すべての根が異なる場合、ラグランジュ因子は次数が最大でn − 1 の多項式の空間の基底を形成する。再帰手順の解析により、H多項式は座標表現を持つ ことがわかる。  $${\displaystyle H^{(\lambda )}(X)=\sum _{m=1}^{n}\left[\prod _{\kappa =0}^{\lambda -1}(\alpha _{m}-s_{\kappa })\right]^{-1}\,P_{m}(X)\ .}$$ 各ラグランジュ因子の最高次係数は1であるため、H多項式の最高次係数は係数の和となる。したがって、正規化されたH多項式は次のようになる。 $${\displaystyle {\bar {H}}^{(\lambda )}(X)={\frac {\sum _{m=1}^{n}\left[\prod _{\kappa =0}^{\lambda -1}(\alpha _{m}-s_{\kappa })\right]^{-1}\,P_{m}(X)}{\sum _{m=1}^{n}\left[\prod _{\kappa =0}^{\lambda -1}(\alpha _{m}-s_{\kappa })\right]^{-1}}}={\frac {P_{1}(X)+\sum _{m=2}^{n}\left[\prod _{\kappa =0}^{\lambda -1}{\frac {\alpha _{1}-s_{\kappa }}{\alpha _{m}-s_{\kappa }}}\right]\,P_{m}(X)}{1+\sum _{m=1}^{n}\left[\prod _{\kappa =0}^{\lambda -1}{\frac {\alpha _{1}-s_{\kappa }}{\alpha _{m}-s_{\kappa }}}\right]}}\ .}$$

条件が${\displaystyle |\alpha _{1}-s_{\kappa }|<\min {}_{m=2,3,\dots ,n}|\alpha _{m}-s_{\kappa }|}$ほぼすべての反復において、正規化された H 多項式は少なくとも幾何級数的に収束する。${\displaystyle P_{1}(X)}$。

以下の条件の下で $${\displaystyle |\alpha _{1}|<|\alpha _{2}|=\min {}_{m=2,3,\dots ,n}|\alpha _{m}|}$$ 漸近推定値を得る

• ステージ1：$${\displaystyle H^{(\lambda )}(X)=P_{1}(X)+O\left(\left|{\frac {\alpha _{1}}{\alpha _{2}}}\right|^{\lambda }\right).}$$
• ステージ 2 の場合、sが十分に近い場合${\displaystyle \alpha _{1}}$:$${\displaystyle H^{(\lambda )}(X)=P_{1}(X)+O\left(\left|{\frac {\alpha _{1}}{\alpha _{2}}}\right|^{M}\cdot \left|{\frac {\alpha _{1}-s}{\alpha _{2}-s}}\right|^{\lambda -M}\right)}$$そして$${\displaystyle s-{\frac {P(s)}{{\bar {H}}^{(\lambda )}(s)}}=\alpha _{1}+O\left(\ldots \cdot |\alpha _{1}-s|\right).}$$
• そしてステージ3では：$${\displaystyle H^{(\lambda )}(X)=P_{1}(X)+O\left(\prod _{\kappa =0}^{\lambda -1}\left|{\frac {\alpha _{1}-s_{\kappa }}{\alpha _{2}-s_{\kappa }}}\right|\right)}$$そして$${\displaystyle s_{\lambda +1}=s_{\lambda }-{\frac {P(s)}{{\bar {H}}^{(\lambda +1)}(s_{\lambda })}}=\alpha _{1}+O\left(\prod _{\kappa =0}^{\lambda -1}\left|{\frac {\alpha _{1}-s_{\kappa }}{\alpha _{2}-s_{\kappa }}}\right|\cdot {\frac {|\alpha _{1}-s_{\lambda }|^{2}}{|\alpha _{2}-s_{\lambda }|}}\right)}$$2次収束次数を超える${\displaystyle \phi ^{2}=1+\phi \approx 2.618}$、 どこ${\displaystyle \phi ={\tfrac {1}{2}}(1+{\sqrt {5}})}$は黄金比です。

ジェンキンス・トラウブ複素アルゴリズムのすべての段階は、特殊な行列の固有値を決定する線形代数問題として表現できます。この行列は、次数がn − 1 以下の多項式のn次元空間における線形写像の座標表現です。この写像の主なアイデアは、因数分解を解釈することです。   $${\displaystyle P(X)=(X-\alpha _{1})\cdot P_{1}(X)}$$ 根付き${\displaystyle \alpha _{1}\in \mathbb {C} }$そして${\displaystyle P_{1}(X)=P(X)/(X-\alpha _{1})}$変数Xとの乗算の固有ベクトル方程式として次数n − 1の残りの因子、続いて除数P ( X ) による剰余計算、   $${\displaystyle M_{X}(H)=(X\cdot H(X)){\bmod {P}}(X)\,.}$$ これは次数が最大n − 1 の多項式を次数が最大n − 1の多項式に写像します。この写像の固有値はP ( X )の根です。固有ベクトル方程式は次のようになります。     $${\displaystyle 0=(M_{X}-\alpha \cdot id)(H)=((X-\alpha )\cdot H){\bmod {P}}\,,}$$ これはつまり${\displaystyle (X-\alpha )\cdot H=C\cdot P(X)}$つまり、${\displaystyle (X-\alpha )}$はP ( X )の線形因子です。単項式基底では、線形写像は${\displaystyle M_{X}}$は、多項式Pのコンパニオン行列によって表される。 $${\displaystyle M_{X}(H)=\sum _{m=0}^{n-1}H_{m}X^{m+1}-H_{n-1}\left(X^{n}+\sum _{m=0}^{n-1}a_{m}X^{m}\right)=\sum _{m=1}^{n-1}(H_{m-1}-a_{m}H_{n-1})X^{m}-a_{0}H_{n-1}\,,}$$ 結果として得られる変換行列は $${\displaystyle A={\begin{pmatrix}0&0&\dots &0&-a_{0}\\1&0&\dots &0&-a_{1}\\0&1&\dots &0&-a_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&\dots &1&-a_{n-1}\end{pmatrix}}\,.}$$ この行列に対して、アルゴリズムの3つの段階において、シフトなし、定数シフト、および一般化レイリーシフトの3つのバリアントで逆べき乗反復法が適用されます。線形代数演算は行列演算ではなく多項式演算で行う方が効率的ですが、逆べき乗反復法の特性は変わりません。