ランチョス法
ランチョス法（英: 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] の直交性がくずれてしまう可能性も持っている。
参考文献
- 森正武 『数値解析』 共立出版、2002年2月。ISBN 4-320-01701-3。
- 夏目雄平、小川建吾、鈴木敏彦 『計算物理３』 朝倉書店、2002年11月。ISBN 978-4-254-13715-6。