ランチョス法のソースを表示

{{pathnav|数学|数値解析|数値線形代数|クリロフ部分空間}}
'''ランチョス法'''（ランチョスほう、{{lang-en-short|Lanczos algorithm}}）とは、対象となる[[対称行列]]を[[三重対角化]]する手法。

[[コルネリウス・ランチョス]]によって開発された[[反復計算]]法である。[[クリロフ部分空間]]法の一つ。

== 概要 ==
行列 <math>A</math> を <math>n\times n</math> の対称行列とする。
これが直交行列 <math>P</math> によって三重対角行列 <math>B</math> に直交変換されたとする。

:<math> B = P^{\rm T}AP </math>

ここで、<math>A</math> が対称であるから <math>B</math> も対称である。
そこで、[[三重対角化]]された行列 <math>B</math> の成分を次のようにおくことにする。

<math>
B=
\left(
\begin{array}{ccccccc}
\alpha_{1}&\beta_{1}&      &      &      & &\\
\beta_{1}&\alpha_{2}&\beta_{2}&      &      &0&\\
      &\beta_{2}&\alpha_{3}&\beta_{3}&      & &\\
      &      &\ddots&\ddots&\ddots& &\\
      & 0    &      &      &\ddots&\alpha_{n-1}&\beta_{n-1}\\
      &      &      &      &      &\beta_{n-1}&\alpha_{n}\\

\end{array}
\right)
</math>

一方、[[直交行列]] <math>P</math> の第 <math>k</math> 列のベクトルを <math>\boldsymbol u_{k}</math> とすると、<math>P</math> の直交性から

:<math>
\boldsymbol u_{i}{}^{\rm T} \boldsymbol u_{j} = 
\left\{
\begin{array}{ll}
0 & (i\neq j), \\
1 & (i=j)
\end{array}
\right.
</math>

が成立する。
また上記の直交変換はつぎのように書くことができる。

:<math> AP = PB </math>

'''ランチョス法'''とは、この関係から直接変換行列 <math>P</math> すなわちベクトル <math>\boldsymbol u_{k}</math> を定めながら、それと同時に三重対角化を行っていく方法である。

上の等式で <math>P=[\boldsymbol u_{1}, \boldsymbol u_{2}, \dots, \boldsymbol u_{k}, \dots, \boldsymbol u_{n} ]</math> とおき、
行列 <math>B</math> の成分を代入して両辺の各列を比較すると、次式が得られる。

:<math>
\left\{
\begin{array}{l}
A \boldsymbol u_{1}=\alpha_{1}\boldsymbol u_{1}+\beta_{1}\boldsymbol u_{2}\\
A \boldsymbol u_{2}=\beta_{1}\boldsymbol u_{1}+\alpha_{2}\boldsymbol u_{2}+\beta_{2}\boldsymbol u_{3}\\
\cdots\\
A \boldsymbol u_{k}=\beta_{k-1}\boldsymbol u_{k-1}+\alpha_{k}\boldsymbol u_{k}+\beta_{k}\boldsymbol u_{k+1}\\
\cdots\\
A \boldsymbol u_{n}=\beta_{n-1}\boldsymbol u_{n-1}+\alpha_{n}\boldsymbol u_{n}
\end{array}
\right.
</math>

第 <math>k</math> 行目の式に左から <math>\boldsymbol u_{k}{}^{\rm T}</math> を乗じると、直交性より以下のように <math>\alpha_{k}</math> が求められる。

:<math> \alpha_{k}=\boldsymbol u_{k}{}^{\rm T} A \boldsymbol u_{k} </math>

また、<math>\boldsymbol u_{k-1}, \boldsymbol u_{k}{}</math> がすでに求められているとすると、<math>\boldsymbol u_{k+1}</math> はつぎのように計算することができる。
まず <math>\boldsymbol v_{k+1} = \beta_k \boldsymbol u_{k+1}</math> を

:<math> \boldsymbol v_{k+1} = A \boldsymbol u_{k} - \beta_{k-1}\boldsymbol u_{k-1} - \alpha_{k} \boldsymbol u_{k} </math>

によって求める。つぎに <math>\boldsymbol u_{k+1}</math> の[[正規化]]条件 <math>\boldsymbol u_{k+1}{}^{\rm T}\boldsymbol u_{k+1}=1</math> を満足させるために <math>\beta_{k}</math> を

:<math> \beta_{k} = ||\boldsymbol v_{k+1}||_{2} </math>

と定める。そして、

:<math> \boldsymbol u_{k+1} = \dfrac{1}{\beta_k}\boldsymbol v_{k+1} </math>

とすればよい。

このようにして、<math>||\boldsymbol u_{1}||_{2}=1</math> なる任意の初期ベクトル <math>\boldsymbol u_{1}</math> からはじめて順次 <math>\alpha_{k}, \beta_{k}</math> を計算することにより三重対角行列 <math>B</math> を求めることができる。

== 特徴 ==
もとの行列 <math>A</math> は変形を受けず、<math>A</math> とベクトルの積だけで計算が行われるのがランチョス法の長所である。
このため、行列要素にゼロの割合が多い疎行列の対角化法として有力なものである。
また、直交性から、3項のみから成る漸化関係によって逐次求める量が得られていくのがこの方法の大きな特徴である。

しかし計算を進めていくうちに丸め誤差の累積によって <math>\boldsymbol u_{k}</math> の直交性がくずれてしまう可能性も持っている。

== 参考文献 ==
{{参照方法|date=2023年9月}}
* {{Cite book|和書|author=森正武|authorlink=森正武|year=2002|month=2|title=数値解析|publisher=共立出版|isbn=4-320-01701-3}}
* {{Cite book|和書|author=夏目雄平、小川建吾、鈴木敏彦|authorlink=夏目雄平、小川建吾、鈴木敏彦|year=2002|month=11|title=計算物理３|publisher=朝倉書店|isbn=978-4-254-13715-6}}
* Louis Komzsik: "The Lanczos Method: Evolution and Application", SIAM, ISBN 978-0-898715-37-8 (2003).
* Ge'rard Meurant: "The Lanczos and Conjugate Gradient Algorithms: From Theory to Finite Precision Computations", SIAM, ISBN 978-0-898716-16-0（2006年）。

== 関連項目 ==
* [[数値解析]]
* [[数値線形代数]]
* [[三重対角化]]
* [[対称行列]]
* [[固有値問題]]
* [[クリロフ部分空間]]
{{linear algebra}}
{{デフォルトソート:らんちょすほう}}
[[Category:数値線形代数]]
[[Category:数学に関する記事]]
[[Category:行列]]
[[Category:エポニム]]