ランチョスアルゴリズム

Numerical eigenvalue calculation

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

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

これらの著者らは、原著論文において、開始ベクトルの選択方法（すなわち、開始ベクトルの各要素を乱数発生器を用いて選択する）と、ベクトルの減少数を決定するための経験的に決定された方法（すなわち、望ましい正確な固有値の数の約1.5倍になるように選択する）も提案した。その後まもなく、ペイジが彼らの研究に続き、誤差分析も行った。^{[3] [4]} 1988年、オジャルボはこのアルゴリズムのより詳細な歴史と効率的な固有値誤差検定を発表した。^[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^{*}}$

警告：ランチョス反復法は数値不安定性を起こしやすい。非正確な計算で実行する場合は、結果の妥当性を確保するために、後述の追加の対策を講じる必要がある。

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}-\beta _{j}v_{j-1}}$
   4. させて。 ${\displaystyle \alpha _{j}=w_{j}'^{*}v_{j}}$
   5. させて。 ${\displaystyle w_{j}=w_{j}'-\alpha _{j}v_{j}}$
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}=\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}$

行列とベクトルの乗算を除くと、各反復では算術演算が行われます。行列とベクトルの乗算は、行内の非ゼロ要素の平均数である算術演算で実行できます。したがって、全体の計算量は、またはの場合、ランチョス法は非常に高速です。数値安定性を向上させる手法は、通常、この高い性能に基づいて評価されます。 ${\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. が非常に大きい場合、 を扱いやすいサイズに縮小しても、 のより極端な固有値と固有ベクトルを見つけることができます。 の領域では、Lanczos アルゴリズムは、極端な固有値の保存に重点を置いたエルミート行列の非可逆圧縮方式として考えることができます。 ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle T}$ ${\displaystyle A}$ ${\displaystyle m\ll n}$

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

三重対角化への応用

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

2 つのアルゴリズムの異なる点は次のとおりです。

• Lanczos は疎行列であることを活用しますが、Householder は疎行列ではないため、 fill-in を生成します。 ${\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}}$

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

行列はエルミート行列である。これは、 も下ヘッセンベルク行列であることを意味し、したがって、実際には三重対角行列でなければならない。エルミート行列であるため、その主対角成分は実数であり、また、その第一下対角成分は構成上実数であるため、第一上対角成分も同様である。したがって、は実対称行列であり、これはランチョス法の仕様における行列である。 ${\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}$

また、この固有基底に関する初期 Lanczos ベクトルの係数の表記を固定するのも便利です。つまり、すべて について とし、 となるようにします。開始ベクトルからいくつかの固有成分が失われると、対応する固有値への収束が遅れます。これは誤差範囲の定数因子として出てくるだけですが、それでもこの減少は望ましくありません。これに常に悩まされるのを避ける一般的な手法の 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}}$

の固有値は係数よりもはるかに多いので、これは難しい要求のように思えるかもしれないが、これを実現する一つの方法はチェビシェフ多項式を使うことだ。第一種次チェビシェフ多項式（すべての に対してを満たすもの）について と書くと、既知の区間内では の範囲内に留まり、その外側では急激に増加する多項式が得られる。引数をある程度スケーリングすることで、 を除くすべての固有値を に写像することができる。 ${\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倍大きいべき乗法と同等の性能を発揮します。これは顕著な改善です。しかし、より難しいのは における の場合で、これは固有ギャップに対してさらに大きな改善をもたらします。領域では、ランチョス法の収束性に関してべき乗法に対する改善が最も小さくなります。 ${\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}$

数値安定性

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

ランチョス法では、正確な演算によりベクトル集合が直交基底を構成し、解かれた固有値／ベクトルが元の行列の固有値／ベクトルの良い近似値になることが証明されています。しかし、実際には（計算は不正確さが避けられない浮動小数点演算で行われるため）、直交性はすぐに失われ、場合によっては新しいベクトルが既に構築された集合に線形従属することさえあります。その結果、結果として得られる三角行列の固有値の一部は、元の行列の近似値にならない可能性があります。したがって、ランチョス法はあまり安定していません。 ${\displaystyle v_{1},v_{2},\cdots ,v_{m+1}}$

このアルゴリズムを使用するには、これらの「偽の」固有値を見つけて除去する必要があります。ランチョスアルゴリズムの実用的な実装では、この安定性の問題に対処するために3つの方向性が取られています。^{[6] [7]}

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

バリエーション

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

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

有限体上の零空間

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

アプリケーション

ランチョスアルゴリズムは、乗算が唯一の大規模線形演算であるため、非常に魅力的です。重み付き単語テキスト検索エンジンはこの演算のみを実装しているため、ランチョスアルゴリズムはテキスト文書に効率的に適用できます（潜在的意味インデックスを参照）。固有ベクトルは、ジョン・クラインバーグが開発したHITSアルゴリズムやGoogleが使用するPageRankアルゴリズムなどの大規模ランキング手法でも重要です。 ${\displaystyle A\,}$

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

実装

NAGライブラリには、Lanczosアルゴリズムを使用する大規模線形システムおよび固有値問題を解くためのいくつかのルーチン^{[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 のようなアルゴリズムも実装しています。

注記

1. 係数は両方とも実数である必要はありませんが、位相はそれほど重要ではありません。他の固有ベクトルの成分が完全に消滅している必要もありませんが、少なくとも の成分の減少速度と同じ速さで減少するため、 は最悪のケースを表します。 ${\displaystyle z_{2}}$ ${\displaystyle u\approx z_{1}+tz_{2}}$

参考文献

1. Lanczos, C. (1950). 「線形微分・積分演算子の固有値問題の解法のための反復法」(PDF) .米国国立標準技術研究所研究ジャーナル. 45 (4): 255– 282. doi : 10.6028/jres.045.026 .
2. Ojalvo, IU; Newman, M. (1970). 「自動マトリックス縮約法による大規模構造物の振動モード」. AIAAジャーナル. 8 (7): 1234– 1239. Bibcode :1970AIAAJ...8.1234N. doi :10.2514/3.5878.
3. Paige, CC (1971).非常に大きな疎行列の固有値と固有ベクトルの計算(博士論文). ロンドン大学. OCLC  654214109.
4. Paige, CC (1972). 「固有値問題に対するランチョス法の計算的変種」. J. Inst. Maths Applics . 10 (3): 373– 381. doi :10.1093/imamat/10.3.373.
5. Ojalvo, IU (1988). 「大規模動的システムにおけるランチョスベクトルの起源と利点」.第6回モーダル解析会議 (IMAC) 講演論文集, フロリダ州キシミー. pp.  489– 494.
6. Cullum; Willoughby (1985).大規模対称固有値計算のためのランチョスアルゴリズム. 第1巻. Birkhäuser. ISBN 0-8176-3058-9。
7. Yousef Saad (1992-06-22). 大規模固有値問題のための数値解析法. Wiley. ISBN 0-470-21820-7。
8. Coakley, Ed S.; Rokhlin, Vladimir (2013). 「実対称三対角行列のスペクトルを計算するための高速分割統治アルゴリズム」.応用および計算調和解析. 34 (3): 379– 414. doi :10.1016/j.acha.2012.06.003.
9. Golub, Gene H.; Van Loan, Charles F. (1996). Matrix computes (第3版). Baltimore: Johns Hopkins Univ. Press. ISBN 0-8018-5413-X。
10. D. Calvetti、L. Reichel、DC Sorensen (1994). 「大規模対称固有値問題に対する暗黙的にリスタートされたLanczos法」. Electronic Transactions on Numerical Analysis . 2 : 1– 21.
11. RB Lehoucq; DC Sorensen; C. Yang (1998). ARPACKユーザーズガイド：暗黙的にリスタートされたアーノルディ法による大規模固有値問題の解法. SIAM. doi :10.1137/1.9780898719628. ISBN 978-0-89871-407-4。
12. E. Kokiopoulou; C. Bekas; E. Gallopoulos (2004). 「暗黙的に再開されたLanczos二重対角化による最小特異三重項の計算」(PDF) . Appl. Numer. Math . 49 : 39– 61. doi :10.1016/j.apnum.2003.11.011.
13. Kesheng Wu; Horst Simon (2000). 「大規模対称固有値問題のためのThick-Restart Lanczos法」. SIAM Journal on Matrix Analysis and Applications . 22 (2). SIAM: 602– 616. doi :10.1137/S0895479898334605.
14. Kesheng Wu; Horst Simon (2001). 「TRLanソフトウェアパッケージ」。2007年7月1日時点のオリジナルよりアーカイブ。2007年6月30日閲覧。
15. Chen, HY; Atkinson, WA; Wortis, R. (2011年7月). 「アンダーソン・ハバード模型における無秩序誘起ゼロバイアス異常：数値計算と解析計算」. Physical Review B. 84 ( 4) 045113. arXiv : 1012.1031 . Bibcode :2011PhRvB..84d5113C. doi :10.1103/PhysRevB.84.045113. S2CID  118722138.
16. 清水 則孝 (2013年10月21日). 「大規模並列計算のための核殻モデルコード「KSHELL」」". arXiv : 1310.5431 [nucl-th].
17. 数値アルゴリズムグループ. 「キーワード索引: Lanczos」. NAGライブラリマニュアル, Mark 23. 2012年2月9日閲覧。
18. GraphLab 2011年3月14日アーカイブ（Wayback Machine）

さらに読む

• ゴルブ, ジーン・H. ;ヴァン・ローン, チャールズ・F. (1996). 「ランチョス法」.行列計算. ボルチモア: ジョンズ・ホプキンス大学出版局. 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。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Lanczos_algorithm&oldid=1319514969"