逆反復

この手法の収束速度を分析してみましょう。

べき乗法は、より正確には次の極限に線形収束することが知られている。

$${\displaystyle \mathrm {距離} (b^{\mathrm {理想} },b_{\mathrm {べき乗法} }^{k})=O\left(\left|{\frac {\lambda _{\mathrm {劣優勢} }}{\lambda _{\mathrm {優勢} }}}\right|^{k}\right),}$$

したがって、逆反復法の場合、同様の結果は次のようになります。

$${\displaystyle \mathrm {距離} (b^{\mathrm {理想} },b_{\mathrm {逆~反復} }^{k})=O\left(\left|{\frac {\mu -\lambda _{\mathrm {最も近い~} \mu }}{\mu -\lambda _{\mathrm {2番目~最も近い~} \mu }}}\右|^{k}\右)。}$$

これは、この方法の収束を理解するための重要な公式です。これは、もし${\displaystyle \mu }$ある固有値に十分近い値が選択されます ${\displaystyle \lambda }$、 例えば${\displaystyle \mu -\lambda =\epsilon }$各反復処理により精度が向上します${\displaystyle |\epsilon |/|\lambda +\epsilon -\lambda _{\mathrm {closest~to~} \lambda }|}$ 時間。（私たちはそれを十分に小さい場合に使用します。）${\displaystyle \epsilon }$「最も近い${\displaystyle \mu }$「そして「最も近い${\displaystyle \lambda }$（同じです。）十分に小さい場合 ${\displaystyle |\epsilon |}$それはほぼ同じです ${\displaystyle |\epsilon |/|\lambda -\lambda _{{\text{最も近い}}\lambda }|}$したがって、もし見つけることができれば${\displaystyle \mu }$それによって${\displaystyle \epsilon }$十分に小さければ、ごく少数の反復で十分な結果が得られるかもしれない。

逆反復アルゴリズムでは、線形システムを解くか、逆行列を計算する必要があります。非構造化行列（疎行列でもトープレッツ行列でもない）の場合、これには${\displaystyle O(n^{3})}$業務。

この式は次のように書き換えることができます。 $${\displaystyle (A-\mu I)b_{k+1}={\frac {b_{k}}{C_{k}}},}$$

次の近似値を見つけるために強調する ${\displaystyle b_{k+1}}$線形方程式系を解く必要がある。選択肢は2つある。線形方程式系を解くアルゴリズムを選択するか、逆関数を計算するかのどちらかだ。${\displaystyle (A-\mu I)^{-1}}$そしてそれをベクトルに適用します。どちらのオプションも計算量はO ( n³ )で、正確な数値^は選択した方法によって異なります。

選択は反復回数にも依存します。単純に考えると、各反復で線形システムを解く場合、計算量はk O ( n ³ ) になります。ここでkは反復回数です。同様に、逆行列を計算して各反復に適用する場合も、計算量はk O ( n ³ ) になります。ただし、固有値推定値が${\displaystyle \mu }$が一定のままであれば、どちらの方法でも複雑さをO ( n ³ ) + k O ( n ^{2 ) に削減できます。逆行列を一度計算し、それを保存して各反復で適用する場合の複雑さは}O ( n ³ ) + k O ( n ² )です。LU 分解を保存すると、${\displaystyle (A-\mu I)}$また、各反復で前進代入と後退代入を使用して連立方程式を解く場合も、計算量はO ( n ³ ) + k O ( n ² ) となります。

行列の逆行列を求める場合、通常は初期コストは高くなりますが、反復計算ごとにコストは低くなります。逆に、連立一次方程式を解く場合は、通常は初期コストは低くなりますが、反復計算ごとに多くの演算が必要になります。

多数の反復処理（または少数の反復処理だが多数の固有ベクトル）が必要な場合は、まず行列を上位ヘッセンベルグ形式に変換するのが賢明かもしれません（対称行列の場合は三重対角形式になります）。これにはコストがかかります。${\textstyle {\frac {10}{3}}n^{3}+O(n^{2})}$ハウスホルダー変換に基づく手法を用いた算術演算）と、直交相似変換の有限列を組み合わせたもので、両側QR分解にやや似ています。^{[ 2 ] [ 3 ]} （QR分解では、ハウスホルダー回転は左側のみに掛けられますが、ヘッセンベルグ変換では左右両方に掛けられます。） 対称行列の場合、この手順のコストは${\textstyle {\frac {4}{3}}n^{3}+O(n^{2})}$ハウスホルダー還元法に基づく手法を用いた算術演算。^{[ 2 ] [ 3 ]}

三重対角行列コストに関する連立一次方程式の解${\displaystyle O(n)}$操作が増えるため、複雑さは次のように増大します。${\displaystyle O(n^{3})+kO(n)}$、 どこ${\displaystyle k}$は反復回数であり、直接逆変換を行うよりも優れています。ただし、反復回数が少ない場合は、このような変換は実用的ではない可能性があります。

また、ヘッセンベルク形式への変換には平方根と除算演算が含まれますが、これらはハードウェアで必ずしもサポートされているとは限りません。

汎用プロセッサ（例えば、Intel製）では、加算、乗算、除算の実行時間はほぼ同じです。しかし、組み込みハードウェアや低消費電力ハードウェア（デジタル信号プロセッサ、FPGA、ASIC）では、除算がハードウェアでサポートされていない場合があるため、避けるべきです。${\displaystyle C_{k}=2^{n_{k}}}$明示的なハードウェアサポートなしで高速な除算が可能になる。2 のべき乗による除算は、ビットシフト(固定小数点演算の場合) または減算のいずれかで実装できるからである。${\displaystyle k}$指数から（浮動小数点演算の場合）。

固定小数点演算を使用してアルゴリズムを実装する場合、定数の選択${\displaystyle C_{k}}$は特に重要です。小さな値は、規範の急速な成長につながります。${\displaystyle b_{k}}$そしてオーバーフローする。大きな値${\displaystyle C_{k}}$ベクトルを引き起こす${\displaystyle b_{k}}$ゼロに近づく傾向にある。

通常、この方法は近似固有値を求める他の方法と組み合わせて使用​​されます。標準的な例としては二分法による固有値アルゴリズムがあり、別の例としてはレイリー商反復法があります。これは実際には、反復の前のステップで得られたベクトルに対応するレイリー商を近似固有値として選択した逆反復法と同じです。

この方法を単独で使用できる状況もいくつかあるが、それはごくまれなケースである。

任意の行列に対して、支配的な固有値を容易に推定できます。任意の誘導ノルムに対して、次のことが成り立ちます。${\displaystyle \left\|A\right\|\geq |\lambda |,}$任意の固有値に対して${\displaystyle \lambda }$したがって、行列のノルムを近似的な固有値として用いると、この方法は支配的な固有ベクトルに収束することがわかります。

リアルタイムアプリケーションの中には、毎秒数百万個の行列の速度で固有ベクトルを求める必要があるものがあります。このようなアプリケーションでは、通常、行列の統計情報は事前に分かっているため、大きな行列サンプルの平均固有値を近似固有値として用いることができます。より良い方法としては、固有値と行列のトレースまたはノルムとの比率の平均を計算し、その比率の平均値にトレースまたはノルムを乗じることで平均固有値を推定する方法があります。もちろん、このような方法は慎重に、かつ高い精度が求められない場合にのみ使用できます。平均固有値を推定するこの方法は、過度に大きな誤差を避けるために、他の方法と組み合わせることができます。