ランチョスアルゴリズム

ランチョス法は、コーネリウス・ランチョスが考案した反復法であり、べき乗法を応用して、エルミート行列の「最も有用な」（極端に高い/低い傾向にある）固有値と固有ベクトルを見つけるものである。ここで、 はより小さいことが多いが、必ずしも より小さいとは限らない。^{[1]原理的には計算効率は良いが、当初定式化された方法は}数値的に不安定であるため、有用ではなかった。 ${\displaystyle m}$${\displaystyle n\times n}$ ${\displaystyle m}$${\displaystyle n}$

1970年、オジャルボとニューマンは、この方法を数値的に安定させる方法を示し、動的荷重を受ける非常に大規模な工学構造物の解法に適用しました。^[2]これは、ランチョスベクトルを精製する方法（つまり、新しく生成された各ベクトルを以前に生成されたすべてのベクトルと繰り返し再直交化すること）^[2]を使用して達成されましたが、これを実行しなかった場合、最も低い固有振動数に関連するベクトルによって大幅に汚染された一連のベクトルが生成されました。

オリジナルの研究で、これらの著者は、開始ベクトルの選択方法（つまり、開始ベクトルの各要素を選択するために乱数ジェネレータを使用する）と、ベクトルの削減数を決定するための経験的に決定された方法（つまり、必要な正確な固有値の数の約1.5倍になるように選択する必要がある）も提案しました。その後すぐに、Paigeが彼らの研究に続き、誤差分析も提供しました。^{[3] [4]} 1988年に、Ojalvoはこのアルゴリズムのより詳細な歴史と効率的な固有値誤差テストを作成しました。^[5]${\displaystyle m}$

サイズ のエルミート行列 を入力し、オプションで反復回数を指定します (デフォルトでは とします)。 ${\displaystyle A}$${\displaystyle n\times n}$${\displaystyle m}$${\displaystyle m=n}$

• 厳密に言えば、アルゴリズムは明示的な行列にアクセスする必要はなく、行列と任意のベクトルの積を計算する関数だけが必要です。この関数はほとんどの場合呼び出されます。${\displaystyle v\mapsto Av}$${\displaystyle m}$

正規直交列を持つ行列と、サイズの三重対角実対称行列を出力します。 の場合、 はユニタリとなり、 となります。${\displaystyle n\times m}$${\displaystyle V}$${\displaystyle T=V^{*}AV}$${\displaystyle m\times m}$${\displaystyle m=n}$${\displaystyle V}$${\displaystyle A=VTV^{*}}$

警告Lanczos 反復法は数値的に不安定になりやすい傾向があります。非正確な計算で実行する場合は、結果の妥当性を確保するために追加の対策 (後のセクションで概説) を講じる必要があります。

1. ユークリッドノルムを持つ任意のベクトル とします。${\displaystyle v_{1}\in \mathbb {C} ^{n}}$ ${\displaystyle 1}$
2. 省略された初期反復ステップ:
   1. させて。${\displaystyle w_{1}'=Av_{1}}$
   2. させて。${\displaystyle \alpha _{1}=w_{1}'^{*}v_{1}}$
   3. させて。${\displaystyle w_{1}=w_{1}'-\alpha _{1}v_{1}}$
3. 行う場合: ${\displaystyle j=2,\dots ,m}$
   1. （ユークリッドノルムともいう）とします。${\displaystyle \beta _{j}=\|w_{j-1}\|}$
   2. ならば、 とします。 ${\displaystyle \beta _{j}\neq 0}$${\displaystyle v_{j}=w_{j-1}/\beta _{j}}$

      それ以外の場合は、のすべてに直交するユークリッドノルムを持つ任意のベクトルとして選択します。${\displaystyle v_{j}}$${\displaystyle 1}$${\displaystyle v_{1},\dots ,v_{j-1}}$

   3. させて。${\displaystyle w_{j}'=Av_{j}}$
   4. させて。${\displaystyle \alpha _{j}=w_{j}'^{*}v_{j}}$
   5. させて。${\displaystyle w_{j}=w_{j}'-\alpha _{j}v_{j}-\beta _{j}v_{j-1}}$
4. を列を持つ行列とします。 とします。${\displaystyle V}$${\displaystyle v_{1},\dots ,v_{m}}$${\displaystyle T={\begin{pmatrix}\alpha _{1}&\beta _{2}&&&&0\\\beta _{2}&\alpha _{2}&\beta _{3}&&&\\&\beta _{3}&\alpha _{3}&\ddots &&\\&&\ddots &\ddots &\beta _{m-1}&\\&&&\beta _{m-1}&\alpha _{m-1}&\beta _{m}\\0&&&&\beta _{m}&\alpha _{m}\\\end{pmatrix}}}$

に関する注意事項。${\displaystyle Av_{j}=w_{j}'=\beta _{j+1}v_{j+1}+\alpha _{j}v_{j}+\beta _{j}v_{j- 1}}$${\displaystyle 2<j<m}$

反復手順を記述する方法は、原理的には4つあります。ペイジと他の研究は、上記の演算順序が最も数値的に安定していることを示しています。^{[6] [7]} 実際には、初期ベクトルは手順の別の引数として取られ、数値の不正確さの指標が追加のループ終了条件として含められます。 ${\displaystyle v_{1}}$${\displaystyle \beta _{j}=0}$

行列とベクトルの乗算を除いて、各反復では算術演算が行われます。行列とベクトルの乗算は算術演算で実行できます。ここで、は行内の非ゼロ要素の平均数です。したがって、全体の計算量は、またはの場合です。Lanczos アルゴリズムは、疎行列に対して非常に高速です。数値安定性を向上させるスキームは、通常、この高いパフォーマンスに対して評価されます。 ${\displaystyle O(n)}$${\displaystyle O(dn)}$${\displaystyle d}$${\displaystyle O(dmn)}$${\displaystyle O(dn^{2})}$${\displaystyle m=n}$

ベクトルは、ランチョス ベクトルと呼ばれます。ベクトルは、が計算された後には使用されず、ベクトルは、が計算された後には使用されません。したがって、3 つすべてに同じストレージを使用できます。同様に、三角行列のみを求める場合は、を計算した後は生の反復は必要ありませんが、数値安定性を向上させるためのいくつかのスキームでは、後で必要になることがあります。後続のランチョス ベクトルは、必要に応じて から再計算されることがあります。 ${\displaystyle v_{j}}$${\displaystyle w_{j}'}$${\displaystyle w_{j}}$${\displaystyle w_{j}}$${\displaystyle v_{j+1}}$${\displaystyle T}$${\displaystyle v_{j-1}}$${\displaystyle w_{j}}$${\displaystyle v_{1}}$

ランチョス アルゴリズムは、行列の固有値と固有ベクトルを求める文脈で最もよく取り上げられますが、通常の行列の対角化では固有ベクトルと固有値が検査によって明らかになりますが、ランチョス アルゴリズムによって実行される三重対角化では同じことが当てはまりません。つまり、1 つの固有値または固有ベクトルを計算するだけでも、重要な追加手順が必要になります。それでも、ランチョス アルゴリズムを適用すると、固有分解の計算において大きな前進となることがよくあります。

が の固有値であり、その固有ベクトル ( ) である場合、 は同じ固有値を持つ の対応する固有ベクトルです。${\displaystyle \lambda}$${\displaystyle T}$${\displaystyle x}$${\displaystyle Tx=\lambda x}$${\displaystyle y=Vx}$${\displaystyle A}$

$${\displaystyle {\begin{aligned}Ay&=AVx\\&=VTV^{*}Vx\\&=VTIx\\&=VTx\\&=V(\lambda x)\\&=\lambda Vx\\&=\lambda y.\end{aligned}}}$$

したがって、Lanczos アルゴリズムは、 の固有値分解問題を の固有値分解問題に変換します。 ${\displaystyle A}$${\displaystyle T}$

1. 三角行列の場合、多くの特殊なアルゴリズムが存在し、多くの場合、汎用アルゴリズムよりも計算複雑度が低くなります。たとえば、が三角対称行列 である場合、次のようになります。${\displaystyle T}$${\displaystyle m\times m}$
   • 継続的再帰により、操作における特性多項式を計算し、操作中のある時点でそれを評価することができます。${\displaystyle O(m^{2})}$${\displaystyle O(m)}$
   • 分割統治固有値アルゴリズムは、操作におけるの固有値分解全体を計算するために使用できます。${\displaystyle T}$${\displaystyle O(m^{2})}$
   • 高速多重極法^[8]は、たったの操作ですべての固有値を計算できる。${\displaystyle O(m\log m)}$
2. いくつかの一般的な固有値分解アルゴリズム、特にQR アルゴリズムは、一般行列よりも三角行列の方が収束が速いことが知られています。三角 QR の漸近的複雑性は、分割統治アルゴリズムと同じです (定数係数は異なる場合があります)。固有ベクトルには要素が一緒にあるため、これは漸近的に最適です。${\displaystyle O(m^{2})}$${\displaystyle m^{2}}$
3. べき乗法や逆反復法など、収束率がユニタリ変換の影響を受けないアルゴリズムでも、元の行列 ではなく三重対角行列 に適用することで、低レベルのパフォーマンス上の利点を享受できる場合があります。 は非常にスパースで、すべての非ゼロ要素の位置が非常に予測しやすいため、キャッシュと比較して優れたパフォーマンスでコンパクトな格納が可能です。同様に、はすべての固有ベクトルと固有値が実数である実数行列ですが、一般には複素要素と複素固有ベクトルを持つことができるため、 の固有ベクトルと固有値を求めるには実数演算で十分です。${\displaystyle T}$${\displaystyle A}$${\displaystyle T}$${\displaystyle T}$${\displaystyle A}$${\displaystyle T}$
4. が非常に大きい場合、 を扱いやすいサイズに縮小しても、 のより極端な固有値と固有ベクトルを見つけることができます。領域では、ランチョス アルゴリズムは、極端な固有値の保存に重点を置いたエルミート行列の非可逆圧縮方式と見なすことができます。${\displaystyle n}$${\displaystyle m}$${\displaystyle T}$${\displaystyle A}$${\displaystyle m\ll n}$

疎行列に対する優れたパフォーマンスと、いくつかの（すべての固有値を計算せずに）固有値を計算できる機能の組み合わせが、Lanczos アルゴリズムの使用を選択する主な理由です。

ランチョス法を適用する動機は固有値問題であることが多いが、この法が主に行う演算は行列の三角対角化であり、数値的に安定したハウスホルダー変換が1950 年代から好まれてきた。1960 年代にはランチョス法は無視された。カニエル・ペイジ収束理論と数値的不安定性を防ぐ方法の開発によってランチョス法への関心が再燃したが、ランチョス法はハウスホルダー法が満足のいくものでない場合にのみ試される代替法として残っている。^[9]

2 つのアルゴリズムの相違点は次のとおりです。

• Lanczos は疎行列であることの利点を活用しますが、Householder はそれを利用せず、埋め込み を生成します。${\displaystyle A}$
• Lanczos は最初から最後まで元の行列を操作します(暗黙的にのみ認識されることに問題はありません)。一方、生の Householder は計算中に行列を変更しようとします (ただし、これは回避できます)。${\displaystyle A}$
• Lanczos アルゴリズムの各反復では、最終的な変換行列 の別の列が生成されますが、Householder の反復では、のユニタリ因数分解の別の因子が生成されます。ただし、各因子は単一のベクトルによって決定されるため、両方のアルゴリズムのストレージ要件は同じであり、時間内に計算できます。${\displaystyle V}$${\displaystyle Q_{1}Q_{2}\dots Q_{n}}$${\displaystyle V}$${\displaystyle V=Q_{1}Q_{2}\dots Q_{n}}$${\displaystyle O(n^{3})}$
• Householder は数値的に安定していますが、生の Lanczos はそうではありません。
• Lanczos は高度に並列化されており、同期ポイント(およびの計算)のみがあります。Householder は並列化が低く、計算されるスカラー量のシーケンスはそれぞれシーケンス内の前の量に依存します。${\displaystyle O(n)}$${\displaystyle \alpha_{j}}$${\displaystyle \beta_{j}}$${\displaystyle O(n^{2})}$

Lanczos アルゴリズムに至る推論はいくつかあります。

行列の最大の大きさの固有値とそれに対応する固有ベクトルを求めるべき乗法は、おおよそ次のようになる。 ${\displaystyle A}$

1. ランダムなベクトルを選択します。${\displaystyle u_{1}\neq 0}$
2. （の方向が収束するまで）次のようにします。 ${\displaystyle j\geqslant 1}$${\displaystyle u_{j}}$
   1. させて${\displaystyle u_{j+1}'=Au_{j}.}$
   2. させて${\displaystyle u_{j+1}=u_{j+1}'/\|u_{j+1}'\|.}$

• 大きな極限では、最大の大きさの固有値に対応するノルムされた固有ベクトルに近づきます。${\displaystyle j}$${\displaystyle u_{j}}$

この方法に対して挙げられる批判は、無駄が多いというものです。行列 から情報を抽出するために多くの作業 (ステップ 2.1 の行列とベクトルの積) を費やしますが、最後の結果のみに注意を払います。実装では通常、すべてのベクトル に同じ変数を使用し、新しい反復ごとに前の反復の結果を上書きします。代わりに、すべての中間結果を保持してデータを整理することが望ましい場合があります。 ${\displaystyle A}$${\displaystyle u_{j}}$

ベクトルから自明に得られる情報の1つは、クリロフ部分空間の連鎖である。アルゴリズムに集合を導入せずにそれを述べる1つの方法は、次のように計算すると主張することである。 ${\displaystyle u_{j}}$

の基底の部分集合であり、すべての${\displaystyle \{v_{j}\}_{j=1}^{m}}$${\displaystyle \mathbb {C} ^{n}}$${\displaystyle Ax\in \operatorname {span} (v_{1},\dotsc ,v_{j+1})}$${\displaystyle x\in \operatorname {span} (v_{1},\dotsc ,v_{j})}$${\displaystyle 1\leqslant j<m;}$

これは、 が から線形独立である限り、 によって自明に満たされます(そして、そのような依存関係がある場合には、 から線形独立な任意のベクトルとして を選択することによってシーケンスを継続することができます)。ただし、ベクトルを含む基底は、このベクトルシーケンスが の固有ベクトルに収束するように設計されているため、数値的に悪条件になる可能性があります。これを回避するには、べき乗反復をグラム–シュミット過程と組み合わせることで、代わりにこれらのクリロフ部分空間の正規直交基底を生成することができます。 ${\displaystyle v_{j}=u_{j}}$${\displaystyle u_{j}}$${\displaystyle u_{1},\dotsc ,u_{j-1}}$${\displaystyle v_{j}}$${\displaystyle u_{1},\dotsc ,u_{j-1}}$${\displaystyle u_{j}}$${\displaystyle A}$

1. ユークリッドノルムのランダムなベクトルを選択します。 とします。${\displaystyle u_{1}}$${\displaystyle 1}$${\displaystyle v_{1}=u_{1}}$
2. 行う場合: ${\displaystyle j=1,\dotsc ,m-1}$
   1. させて。${\displaystyle u_{j+1}'=Au_{j}}$
   2. すべてについて とします。(これらは基底ベクトル に対するの座標です。)${\displaystyle k=1,\dotsc,j}$${\displaystyle g_{k,j}=v_{k}^{*}u_{j+1}'}$${\displaystyle Au_{j}=u_{j+1}'}$${\displaystyle v_{1},\dotsc ,v_{j}}$
   3. とします。(に含まれるの成分を消去します。)${\displaystyle w_{j+1}=u_{j+1}'-\sum _{k=1}^{j}g_{k,j}v_{k}}$${\displaystyle u_{j+1}'}$${\displaystyle \operatorname {span} (v_{1},\dotsc ,v_{j})}$
   4. ならば、とし、 ${\displaystyle w_{j+1}\neq 0}$${\displaystyle u_{j+1}=u_{j+1}'/\|u_{j+1}'\|}$${\displaystyle v_{j+1}=w_{j+1}/\|w_{j+1}\|}$

      それ以外の場合は、 のすべてに直交するユークリッドノルムの任意のベクトルとして を選択します。${\displaystyle u_{j+1}=v_{j+1}}$${\displaystyle 1}$${\displaystyle v_{1},\dotsc ,v_{j}}$

べき乗反復ベクトルと直交ベクトルの関係は、 ${\displaystyle u_{j}}$${\displaystyle v_{j}}$

${\displaystyle Au_{j}=\|u_{j+1}'\|u_{j+1}=u_{j+1}'=w_{j+1}+\sum _{k=1}^{j}g_{k,j}v_{k}=\|w_{j+1}\|v_{j+1}+\sum _{k=1}^{j}g_{k,j}v_{k}}$。

ここで、これらの を計算するためにベクトルは実際には必要ないことに気づくかもしれない。なぜなら、 であり、したがって との差はにあり、これは直交化プロセスによって相殺されるからである。したがって、クリロフ部分空間の連鎖に対する同じ基底は次のように計算される。 ${\displaystyle u_{j}}$${\displaystyle v_{j}}$${\displaystyle u_{j}-v_{j}\in \operatorname {span} (v_{1},\dotsc ,v_{j-1})}$${\displaystyle u_{j+1}'=Au_{j}}$${\displaystyle w_{j+1}'=Av_{j}}$${\displaystyle \operatorname {span} (v_{1},\dotsc ,v_{j})}$

1. ユークリッドノルムのランダムなベクトルを選択します。${\displaystyle v_{1}}$${\displaystyle 1}$
2. 行う場合: ${\displaystyle j=1,\dotsc ,m-1}$
   1. させて。${\displaystyle w_{j+1}'=Av_{j}}$
   2. すべて とします。${\displaystyle k=1,\dotsc ,j}$${\displaystyle h_{k,j}=v_{k}^{*}w_{j+1}'}$
   3. させて。${\displaystyle w_{j+1}=w_{j+1}'-\sum _{k=1}^{j}h_{k,j}v_{k}}$
   4. させて。${\displaystyle h_{j+1,j}=\|w_{j+1}\|}$
   5. ならば、 ​${\displaystyle h_{j+1,j}\neq 0}$${\displaystyle v_{j+1}=w_{j+1}/h_{j+1,j}}$

      それ以外の場合は、 のすべてに直交するユークリッドノルムの任意のベクトルとして を選択します。${\displaystyle v_{j+1}}$${\displaystyle 1}$${\displaystyle v_{1},\dotsc ,v_{j}}$

事前に係数は以下を満たす ${\displaystyle h_{k,j}}$

${\displaystyle Av_{j}=\sum _{k=1}^{j+1}h_{k,j}v_{k}}$すべてに対して;${\displaystyle j<m}$

この定義は少し奇妙に思えるかもしれないが、一般的なパターンに当てはまる。 ${\displaystyle h_{j+1,j}=\|w_{j+1}\|}$${\displaystyle h_{k,j}=v_{k}^{*}w_{j+1}'}$

${\displaystyle v_{j+1}^{*}w_{j+1}'=v_{j+1}^{*}w_{j+1}=\|w_{j+1}\|v_{j+1}^{*}v_{j+1}=\|w_{j+1}\|.}$

この再帰から除去されたべき乗反復ベクトルは、ベクトルと係数がをすべて計算するのに十分な情報を含んでいることを満たすため、ベクトルを切り替えることで何も失われません。(実際、ここで収集されたデータは、べき乗法で同じ回数の反復から得られるものよりも、最大固有値の近似値として大幅に優れていることがわかりますが、この時点では必ずしも明らかではありません。) ${\displaystyle u_{j}}$${\displaystyle u_{j}\in \operatorname {span} (v_{1},\ldots ,v_{j}),}$${\displaystyle \{v_{j}\}_{j=1}^{m}}$${\displaystyle h_{k,j}}$${\displaystyle A}$${\displaystyle u_{1},\ldots ,u_{m}}$

この最後の手順は、アーノルディ反復法です。 がエルミートである場合に自明であることが判明した計算ステップを排除することで得られる簡略化として、ランチョス アルゴリズムが生まれます。特に、係数のほとんどがゼロになります。 ${\displaystyle A}$${\displaystyle h_{k,j}}$

基本的に、がエルミートならば ${\displaystyle A}$

${\displaystyle h_{k,j}=v_{k}^{*}w_{j+1}'=v_{k}^{*}Av_{j}=v_{k}^{*}A^{*}v_{j}=(Av_{k})^{*}v_{j}.}$

というのは、 であることが分かっており、 は構成上この部分空間に直交するので、この内積はゼロでなけれ ばならない。（これは本質的に、直交多項式の列に常に3項再帰関係が与えられる理由でもある。）${\displaystyle k<j-1}$${\displaystyle Av_{k}\in \operatorname {span} (v_{1},\ldots ,v_{j-1})}$${\displaystyle v_{j}}$${\displaystyle k=j-1}$

${\displaystyle h_{j-1,j}=(Av_{j-1})^{*}v_{j}={\overline {v_{j}^{*}Av_{j-1}}}={\overline {h_{j,j-1}}}=h_{j,j-1}}$

後者はベクトルのノルムであるので実数である。 ${\displaystyle k=j}$

${\displaystyle h_{j,j}=(Av_{j})^{*}v_{j}={\overline {v_{j}^{*}Av_{j}}}={\overline {h_{j,j}}},}$

つまりこれも本物だということです。

より抽象的に言えば、 が列を持つ行列である場合、数値は行列 の要素として識別でき、行列の場合、は上ヘッセンベルクである。 ${\displaystyle V}$${\displaystyle v_{1},\ldots ,v_{m}}$${\displaystyle h_{k,j}}$${\displaystyle H=V^{*}AV}$${\displaystyle h_{k,j}=0}$${\displaystyle k>j+1;}$${\displaystyle H}$

${\displaystyle H^{*}=\left(V^{*}AV\right)^{*}=V^{*}A^{*}V=V^{*}AV=H}$

この行列はエルミート行列です。これは、も下ヘッセンベルグ行列であることを意味します。したがって、この行列は実際には三重対角行列でなければなりません。エルミート行列であるため、この行列の主対角要素は実数であり、この行列の最初の副対角要素は構成上実数であるため、この行列の最初の上対角要素についても同じことが言えます。したがって、この行列は実数の対称行列であり、これはLanczos アルゴリズム仕様の行列です。 ${\displaystyle H}$${\displaystyle H}$${\displaystyle H}$${\displaystyle T}$

エルミート行列の固有ベクトルを特徴付ける一つの方法は、レイリー商の定常点として表すことである。${\displaystyle A}$

${\displaystyle r(x)={\frac {x^{*}Ax}{x^{*}x}},\qquad x\in \mathbb {C} ^{n}.}$

特に、最大の固有値はのグローバル最大値であり、最小の固有値は のグローバル最小値です。 ${\displaystyle \lambda _{\max }}$${\displaystyle r}$${\displaystyle \lambda _{\min }}$${\displaystyle r}$

の低次元部分空間内では、 の最大値と最小値を見つけることは可能です。 増加チェーンについてこれを繰り返すと、2つのベクトル列が生成されます。およびであり、 および ${\displaystyle {\mathcal {L}}}$${\displaystyle \mathbb {C} ^{n}}$${\displaystyle x}$${\displaystyle y}$${\displaystyle r}$${\displaystyle {\mathcal {L}}_{1}\subset {\mathcal {L}}_{2}\subset \cdots }$${\displaystyle x_{1},x_{2},\ldots }$${\displaystyle y_{1},y_{2},\dotsc }$${\displaystyle x_{j},y_{j}\in {\mathcal {L}}_{j}}$

${\displaystyle {\begin{aligned}r(x_{1})&\leqslant r(x_{2})\leqslant \cdots \leqslant \lambda _{\max }\\r(y_{1})&\geqslant r(y_{2})\geqslant \cdots \geqslant \lambda _{\min }\end{aligned}}}$

次に、これらのシーケンスが最適な速度で収束するようにサブスペースをどのように選択するかという疑問が生じます。

から、 のより大きな値を求める最適な方向は勾配の方向であり、同様に から、のより小さな値を求める最適な方向は負の勾配 の方向である。一般に、 ${\displaystyle x_{j}}$${\displaystyle r}$ ${\displaystyle \nabla r(x_{j})}$${\displaystyle y_{j}}$${\displaystyle r}$${\displaystyle -\nabla r(y_{j})}$

${\displaystyle \nabla r(x)={\frac {2}{x^{*}x}}(Ax-r(x)x),}$

したがって、関心のある方向は行列演算で簡単に計算できますが、 と の両方を改良したい場合は、次の 2 つの新しい方向を考慮する必要があります。およびは線形独立ベクトルになる可能性があるため(実際、 は直交に近い)、 と が一般に平行であるとは期待できません。 をクリロフ部分空間とすると、すべてのに対して になるため、すべてのステップでによっての次元を増やす必要はありません。したがって、特にと の両方に対して です。 ${\displaystyle x_{j}}$${\displaystyle y_{j}}$${\displaystyle Ax_{j}}$${\displaystyle Ay_{j};}$${\displaystyle x_{j}}$${\displaystyle y_{j}}$${\displaystyle Ax_{j}}$${\displaystyle Ay_{j}}$${\displaystyle {\mathcal {L}}_{j}}$${\displaystyle 2}$${\displaystyle \{{\mathcal {L}}_{j}\}_{j=1}^{m}}$${\displaystyle Az\in {\mathcal {L}}_{j+1}}$${\displaystyle z\in {\mathcal {L}}_{j},}$${\displaystyle z=x_{j}}$${\displaystyle z=y_{j}}$

言い換えれば、任意の初期ベクトルからベクトル空間を構築する ことができる。${\displaystyle x_{1}=y_{1},}$

${\displaystyle {\mathcal {L}}_{j}=\operatorname {span} (x_{1},Ax_{1},\ldots ,A^{j-1}x_{1})}$

そして、 ${\displaystyle x_{j},y_{j}\in {\mathcal {L}}_{j}}$

${\displaystyle r(x_{j})=\max _{z\in {\mathcal {L}}_{j}}r(z)\qquad {\text{and}}\qquad r(y_{j})=\min _{z\in {\mathcal {L}}_{j}}r(z).}$

べき乗法反復はに属しているため、とを生成する反復はべき乗法よりも遅く収束することはなく、両方の固有値の極値を近似することでより多くの成果が得られます。上の最適化の部分問題では、このベクトル空間の正規直交基底があると便利です。したがって、クリロフ部分空間のシーケンスの基底を反復的に計算するという問題に再び直面します。 ${\displaystyle j}$${\displaystyle u_{j}}$${\displaystyle {\mathcal {L}}_{j},}$${\displaystyle x_{j}}$${\displaystyle y_{j}}$${\displaystyle r}$${\displaystyle {\mathcal {L}}_{j}}$${\displaystyle \{v_{1},\ldots ,v_{j}\}}$

アルゴリズムのダイナミクスを分析する場合、 の固有値と固有ベクトルは、ユーザーには明示的に知らされていなくても、既知であるとみなすと便利です。表記を固定するには、を固有値（これらはすべて実数であることがわかっているため、順序付けが可能です）とし、 をすべての に対してとなるような固有ベクトルの正規直交集合とします。 ${\displaystyle A}$${\displaystyle \lambda _{1}\geqslant \lambda _{2}\geqslant \dotsb \geqslant \lambda _{n}}$${\displaystyle z_{1},\dotsc ,z_{n}}$${\displaystyle Az_{k}=\lambda _{k}z_{k}}$${\displaystyle k=1,\dotsc ,n}$

また、この固有基底に関する初期ランチョス ベクトルの係数の表記を固定することも便利です。すべての について とし、 となるようにします。開始ベクトルから一部の固有成分が失われると、対応する固有値への収束が遅れます。これは誤差範囲の定数因子としてしか出てこないとしても、依然として失われることは望ましくありません。これに常に悩まされることを避ける一般的な手法の 1 つは、まず平均 の同じ正規分布に従って要素をランダムに抽出して選択し、次にベクトルをノルム に再スケーリングすることです。再スケーリングの前は、これにより係数も同じ正規分布からの独立した正規分布の確率変数になり (座標の変更はユニタリであるため)、再スケーリング後はベクトルはの単位球面上に一様分布します。これにより、たとえば となる確率を制限できます。 ${\displaystyle v_{1}}$${\displaystyle d_{k}=z_{k}^{*}v_{1}}$${\displaystyle k=1,\dotsc ,n}$${\displaystyle \textstyle v_{1}=\sum _{k=1}^{n}d_{k}z_{k}}$${\displaystyle v_{1}}$${\displaystyle v_{1}}$${\displaystyle 0}$${\displaystyle 1}$${\displaystyle d_{k}}$${\displaystyle (d_{1},\dotsc ,d_{n})}$${\displaystyle \mathbb {C} ^{n}}$${\displaystyle |d_{1}|<\varepsilon }$

Lanczos アルゴリズムは座標に依存しない (演算ではベクトルの内積のみが考慮され、ベクトルの個々の要素は考慮されない) ため、既知の固有構造を持つ例を簡単に作成してアルゴリズムを実行できます。対角線上に目的の固有値を持つ対角行列を作成します。開始ベクトルに十分な数の非ゼロ要素がある限り、アルゴリズムは一般的な三重対角対称行列を として出力します。 ${\displaystyle A}$${\displaystyle v_{1}}$${\displaystyle T}$

ランチョス法の反復ステップの後、は実対称行列となり、上記と同様に固有値を持つ。収束とは、第一に、 が大きくなるにつれてが に収束すること（およびが に対称的に収束すること）を意味し、第二に の固有値のある範囲がの対応するに収束することである。ランチョス法の収束は、べき乗反復法の収束よりも桁違いに速いことが多い。^{[9] : 477}${\displaystyle m}$${\displaystyle T}$${\displaystyle m\times m}$${\displaystyle m}$${\displaystyle \theta _{1}\geqslant \theta _{2}\geqslant \dots \geqslant \theta _{m}.}$${\displaystyle \theta _{1}}$${\displaystyle \lambda _{1}}$${\displaystyle \theta _{m}}$${\displaystyle \lambda _{n}}$${\displaystyle m}$${\displaystyle \theta _{1},\ldots ,\theta _{k}}$${\displaystyle T}$${\displaystyle \lambda _{1},\ldots ,\lambda _{k}}$${\displaystyle A}$

に対する境界は、固有値をレイリー商 の極値として解釈することから得られます。は全体にわたって の最大値であり、は単に 次元クリロフ部分空間上の最大値であるため、 が自明に得られます。逆に、そのクリロフ部分空間内の任意の点はの下限値を提供するため、 に対して が小さい点を示すことができる場合、これは に対する厳密な境界を提供します。 ${\displaystyle \theta _{1}}$${\displaystyle r(x)}$${\displaystyle \lambda _{1}}$${\displaystyle r}$${\displaystyle \mathbb {C} ^{n},}$${\displaystyle \theta _{1}}$${\displaystyle m}$${\displaystyle \lambda _{1}\geqslant \theta _{1}}$${\displaystyle x}$${\displaystyle r(x)}$${\displaystyle \theta _{1}}$${\displaystyle \lambda _{1}-r(x)}$${\displaystyle \theta _{1}}$

次元クリロフ部分空間は ${\displaystyle m}$

${\displaystyle \operatorname {span} \left\{v_{1},Av_{1},A^{2}v_{1},\ldots ,A^{m-1}v_{1}\right\},}$

したがって、その任意の要素は、最大次数の多項式について と表すことができます。その多項式の係数は、ベクトル の線形結合の係数に過ぎません。必要な多項式は実係数を持つことになりますが、ここでは複素係数も考慮し、のすべての係数を複素共役にして得られる多項式について と書きます。このクリロフ部分空間のパラメータ化では、 ${\displaystyle p(A)v_{1}}$${\displaystyle p}$${\displaystyle m-1}$${\displaystyle v_{1},Av_{1},A^{2}v_{1},\ldots ,A^{m-1}v_{1}}$${\displaystyle p^{*}}$${\displaystyle p}$

${\displaystyle r(p(A)v_{1})={\frac {(p(A)v_{1})^{*}Ap(A)v_{1}}{(p(A)v_{1})^{*}p(A)v_{1}}}={\frac {v_{1}^{*}p(A)^{*}Ap(A)v_{1}}{v_{1}^{*}p(A)^{*}p(A)v_{1}}}={\frac {v_{1}^{*}p^{*}(A^{*})Ap(A)v_{1}}{v_{1}^{*}p^{*}(A^{*})p(A)v_{1}}}={\frac {v_{1}^{*}p^{*}(A)Ap(A)v_{1}}{v_{1}^{*}p^{*}(A)p(A)v_{1}}}}$

の式を固有ベクトルの線形結合として用いると、次の式が得られる。 ${\displaystyle v_{1}}$

${\displaystyle Av_{1}=A\sum _{k=1}^{n}d_{k}z_{k}=\sum _{k=1}^{n}d_{k}\lambda _{k}z_{k}}$

そしてより一般的には

${\displaystyle q(A)v_{1}=\sum _{k=1}^{n}d_{k}q(\lambda _{k})z_{k}}$

任意の多項式に対して。 ${\displaystyle q}$

したがって

${\displaystyle \lambda _{1}-r(p(A)v_{1})=\lambda _{1}-{\frac {v_{1}^{*}\sum _{k=1}^{n}d_{k}p^{*}(\lambda _{k})\lambda _{k}p(\lambda _{k})z_{k}}{v_{1}^{*}\sum _{k=1}^{n}d_{k}p^{*}(\lambda _{k})p(\lambda _{k})z_{k}}}=\lambda _{1}-{\frac {\sum _{k=1}^{n}|d_{k}|^{2}\lambda _{k}p(\lambda _{k})^{*}p(\lambda _{k})}{\sum _{k=1}^{n}|d_{k}|^{2}p(\lambda _{k})^{*}p(\lambda _{k})}}={\frac {\sum _{k=1}^{n}|d_{k}|^{2}(\lambda _{1}-\lambda _{k})\left|p(\lambda _{k})\right|^{2}}{\sum _{k=1}^{n}|d_{k}|^{2}\left|p(\lambda _{k})\right|^{2}}}.}$

ここでの分子と分母の主な違いは、項が分子では消えるが、分母では消えないことです。したがって、 で大きく、他のすべての固有値で小さくなるように選択できれば、誤差の厳しい境界が得られます。 ${\displaystyle k=1}$${\displaystyle p}$${\displaystyle \lambda _{1}}$${\displaystyle \lambda _{1}-\theta _{1}}$

の固有値は係数よりはるかに多いので、これは難しいように思えるかもしれませんが、これを満たす方法の 1 つはチェビシェフ多項式を使用することです。次数 1 種チェビシェフ多項式 (すべての に対して を満たすもの)について と書くと、既知の区間の範囲内にとどまり、その外側では急速に増加する多項式が得られます。引数をいくらかスケーリングすると、を除くすべての固有値を にマッピングできます。 ${\displaystyle A}$${\displaystyle p}$${\displaystyle c_{k}}$${\displaystyle k}$${\displaystyle c_{k}(\cos x)=\cos(kx)}$${\displaystyle x}$${\displaystyle [-1,1]}$${\displaystyle [-1,1]}$${\displaystyle \lambda _{1}}$${\displaystyle [-1,1]}$

${\displaystyle p(x)=c_{m-1}\left({\frac {2x-\lambda _{2}-\lambda _{n}}{\lambda _{2}-\lambda _{n}}}\right)}$

（ の場合は、 より小さい最大の固有値を使用してください）、 に対するの最大値はであり、 の最小値は であるため、 ${\displaystyle \lambda _{2}=\lambda _{1}}$${\displaystyle \lambda _{1}}$${\displaystyle |p(\lambda _{k})|^{2}}$${\displaystyle k\geqslant 2}$${\displaystyle 1}$${\displaystyle 0}$

${\displaystyle \lambda _{1}-\theta _{1}\leqslant \lambda _{1}-r(p(A)v_{1})={\frac {\sum _{k=2}^{n}|d_{k}|^{2}(\lambda _{1}-\lambda _{k})|p(\lambda _{k})|^{2}}{\sum _{k=1}^{n}|d_{k}|^{2}|p(\lambda _{k})|^{2}}}\leqslant {\frac {\sum _{k=2}^{n}|d_{k}|^{2}(\lambda _{1}-\lambda _{k})}{|d_{1}|^{2}|p(\lambda _{1})|^{2}}}\leqslant {\frac {(\lambda _{1}-\lambda _{n})\sum _{k=2}^{n}|d_{k}|^{2}}{|p(\lambda _{1})|^{2}|d_{1}|^{2}}}.}$

さらに

${\displaystyle p(\lambda _{1})=c_{m-1}\left({\frac {2\lambda _{1}-\lambda _{2}-\lambda _{n}}{\lambda _{2}-\lambda _{n}}}\right)=c_{m-1}\left(2{\frac {\lambda _{1}-\lambda _{2}}{\lambda _{2}-\lambda _{n}}}+1\right);}$

数量

${\displaystyle \rho ={\frac {\lambda _{1}-\lambda _{2}}{\lambda _{2}-\lambda _{n}}}}$

（つまり、最初の固有ギャップとスペクトルの残りの直径の比）は、ここでの収束速度にとって非常に重要である。また、

${\displaystyle R=e^{\operatorname {arcosh} (1+2\rho )}=1+2\rho +2{\sqrt {\rho ^{2}+\rho }},}$

我々は次のように結論づけることができる。

${\displaystyle {\begin{aligned}\lambda _{1}-\theta _{1}&\leqslant {\frac {(\lambda _{1}-\lambda _{n})\left(1-|d_{1}|^{2}\right)}{c_{m-1}(2\rho +1)^{2}|d_{1}|^{2}}}\\[6pt]&={\frac {1-|d_{1}|^{2}}{|d_{1}|^{2}}}(\lambda _{1}-\lambda _{n}){\frac {1}{\cosh ^{2}((m-1)\operatorname {arcosh} (1+2\rho ))}}\\[6pt]&={\frac {1-|d_{1}|^{2}}{|d_{1}|^{2}}}(\lambda _{1}-\lambda _{n}){\frac {4}{\left(R^{m-1}+R^{-(m-1)}\right)^{2}}}\\[6pt]&\leqslant 4{\frac {1-|d_{1}|^{2}}{|d_{1}|^{2}}}(\lambda _{1}-\lambda _{n})R^{-2(m-1)}\end{aligned}}}$

したがって、収束率は主に によって制御されます。これは、この境界が各追加反復ごとに 係数で縮小するためです。${\displaystyle R}$${\displaystyle R^{-2}}$

比較のために、べき乗法の収束率が にどのように依存するかを検討することもできますが、べき乗法は主に固有値の絶対値間の商に敏感であるため、と間の固有ギャップが支配的なものである必要があります。その制約の下では、べき乗法が最も有利なケースは であるため、 を検討します。べき乗法の後半では、反復ベクトル: ${\displaystyle \rho }$${\displaystyle |\lambda _{n}|\leqslant |\lambda _{2}|}$${\displaystyle \lambda _{1}}$${\displaystyle \lambda _{2}}$${\displaystyle \lambda _{n}=-\lambda _{2}}$

${\displaystyle u=(1-t^{2})^{1/2}z_{1}+tz_{2}\approx z_{1}+tz_{2},}$^{[注 1]}

ここで、各新しい反復は、実質的に振幅 を${\displaystyle z_{2}}$${\displaystyle t}$

${\displaystyle {\frac {\lambda _{2}}{\lambda _{1}}}={\frac {\lambda _{2}}{\lambda _{2}+(\lambda _{1}-\lambda _{2})}}={\frac {1}{1+{\frac {\lambda _{1}-\lambda _{2}}{\lambda _{2}}}}}={\frac {1}{1+2\rho }}.}$

最大固有値の推定値は

${\displaystyle u^{*}Au=(1-t^{2})\lambda _{1}+t^{2}\lambda _{2},}$

したがって、ランチョスアルゴリズムの収束率の上限は、

${\displaystyle \lambda _{1}-u^{*}Au=(\lambda _{1}-\lambda _{2})t^{2},}$

これは、各反復で 倍に縮小します。したがって、違いはと の違いに帰着します。領域では、後者は に近くなり、固有ギャップが 2 倍大きいべき乗法と同様のパフォーマンスを発揮します。これは顕著な改善です。ただし、 の場合の方が難しく、 ではがさらに大きな固有ギャップの改善となります。領域では、Lanczos アルゴリズムの収束に関してべき乗法の改善が 最も小さくなります。${\displaystyle (1+2\rho )^{-2}}$${\displaystyle 1+2\rho }$${\displaystyle R=1+2\rho +2{\sqrt {\rho ^{2}+\rho }}}$${\displaystyle \rho \gg 1}$${\displaystyle 1+4\rho }$${\displaystyle \rho \ll 1,}$${\displaystyle R\approx 1+2{\sqrt {\rho }}}$${\displaystyle \rho \gg 1}$

安定性とは、小さな数値誤差が導入されて蓄積された場合に、アルゴリズムがどの程度影響を受けるか (つまり、元の結果に近い近似結果が生成されるかどうか) を意味します。数値安定性は、丸め機能を備えたコンピューターでアルゴリズムを実装することの有用性を判断するための中心的な基準です。

Lanczos アルゴリズムでは、正確な演算により、ベクトルのセットが正規直交基底を構成し、解かれた固有値/ベクトルが元の行列の固有値/ベクトルの良好な近似値になることが証明されています。ただし、実際には (計算は不正確さが避けられない浮動小数点演算で実行されるため)、直交性はすぐに失われ、場合によっては新しいベクトルが既に構築されているセットに線形に依存することさえあります。その結果、結果として得られる三角行列の固有値の一部は、元の行列の近似値ではない可能性があります。したがって、Lanczos アルゴリズムはあまり安定していません。 ${\displaystyle v_{1},v_{2},\cdots ,v_{m+1}}$

このアルゴリズムのユーザーは、これらの「偽の」固有値を見つけて除去できなければなりません。ランチョスアルゴリズムの実際の実装は、この安定性の問題に対処するために3つの方向に進みます。^{[6] [7]}

1. 直交性の喪失を防ぐ、
2. 基底が生成された後、直交性を回復します。
3. 正しい固有値と「誤った」固有値がすべて識別されたら、誤った固有値を削除します。

Lanczos アルゴリズムのバリエーションとして、関係するベクトルがベクトルではなく縦長の狭い行列であり、正規化定数が小さな正方行列であるものがあります。これらは「ブロック」Lanczos アルゴリズムと呼ばれ、レジスタの数が多くメモリ フェッチ時間が長いコンピュータでは、はるかに高速になります。

ランチョスアルゴリズムの多くの実装は、一定回数の反復後に再開します。最も影響力のある再開バリエーションの1つは、暗黙的に再開されたランチョス法です。^{[10]これは}ARPACKに実装されています。 ^[11] これにより、再開されたランチョス二重対角化など、他の多くの再開バリエーションが生まれました。^[12] もう一つの成功した再開バリエーションは、厚い再開ランチョス法です。^[13]これはTRLanと呼ばれるソフトウェアパッケージに実装されています。^[14]

1995年、ピーター・モンゴメリーは、ランチョス法に基づいて、GF(2)上の大規模疎行列の零空間の要素を見つけるアルゴリズムを発表しました。有限体上の大規模疎行列に関心のある人々の集合と大規模固有値問題に関心のある人々の集合はほとんど重複しないため、これは不当な混乱を招くことなく、ブロックランチョス法とも呼ばれます。^[要出典]

Lanczos アルゴリズムは、 による乗算が唯一の大規模な線形演算であるため、非常に魅力的です。加重用語テキスト検索エンジンはこの演算のみを実装するため、Lanczos アルゴリズムはテキスト ドキュメントに効率的に適用できます (潜在的意味インデックス作成を参照)。固有ベクトルは、Jon Kleinbergによって開発されたHITS アルゴリズムや、 Google が使用するPageRankアルゴリズムなどの大規模なランキング手法でも重要です。 ${\displaystyle A\,}$

ランチョスアルゴリズムは、凝縮系物理学において強相関電子系のハミルトニアンを解く方法として使用されているほか、^[15]原子核物理学の殻模型コードにも使用されている。^[16]

NAGライブラリには、ランチョスアルゴリズムを使用する大規模線形システムおよび固有値問題を解くための いくつかのルーチン^{[17]が含まれています。}

MATLABとGNU Octave にはARPACKが組み込まれています。格納された行列と暗黙的な行列の両方をeigs()関数 (Matlab/Octave) で分析できます。

同様に、Pythonでは、SciPyパッケージに scipy.sparse.linalg.eigsh が含まれています。これは、暗黙的に再開された Lanczos 法を使用する ARPACKの SSEUPD および DSEUPD 関数のラッパーでもあります。

LanczosアルゴリズムのMatlab実装（精度の問題に注意）は、Gaussian Belief Propagation Matlabパッケージの一部として利用できます。GraphLab [ ^18] 協調フィルタリングライブラリには、マルチコア用のLanczosアルゴリズム（C++）の大規模な並列実装が組み込まれています。

PRIMME ライブラリは Lanczos のようなアルゴリズムも実装します。

• Golub, Gene H. ; Van Loan, Charles F. (1996)。「Lanczos 法」。行列計算。ボルチモア: Johns Hopkins University Press。pp. 470–507。ISBN 0-8018-5414-8。
• Ng, Andrew Y. ; Zheng, Alice X.; Jordan, Michael I. (2001). 「リンク解析、固有ベクトル、安定性」(PDF) . IJCAI'01 Proceedings of the 17th International Joint Conference on Artificial Intelligence . 2 : 903–910.
• エリック・コッホ (2019)。 「正確な対角化とランチョス法」(PDF)。 E.パヴァリーニでは。 E. コッホ; S. チャン (編)。実際のマテリアルの多体法。ユーリッヒ。ISBN 978-3-95806-400-3。