ランチョス法

ランチョス法（ランチョスほう、英: Lanczos algorithm）とは、対象となる対称行列を三重対角化する手法。

数学 > 数値解析 > 数値線形代数 > クリロフ部分空間 > ランチョス法

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

概要

行列 ${\displaystyle A}$ を ${\displaystyle n\times n}$ の対称行列とする。 これが直交行列 ${\displaystyle P}$ によって三重対角行列 ${\displaystyle B}$ に直交変換されたとする。

${\displaystyle B=P^{\rm {T}}AP}$

ここで、${\displaystyle A}$ が対称であるから ${\displaystyle B}$ も対称である。 そこで、三重対角化された行列 ${\displaystyle B}$ の成分を次のようにおくことにする。

${\displaystyle 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)}$

一方、直交行列 ${\displaystyle P}$ の第 ${\displaystyle k}$ 列のベクトルを ${\displaystyle {\boldsymbol {u}}_{k}}$ とすると、${\displaystyle P}$ の直交性から

${\displaystyle {\boldsymbol {u}}_{i}{}^{\rm {T}}{\boldsymbol {u}}_{j}=\left\{{\begin{array}{ll}0&(i\neq j),\\1&(i=j)\end{array}}\right.}$

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

${\displaystyle AP=PB}$

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

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

${\displaystyle \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.}$

第 ${\displaystyle k}$ 行目の式に左から ${\displaystyle {\boldsymbol {u}}_{k}{}^{\rm {T}}}$ を乗じると、直交性より以下のように ${\displaystyle \alpha _{k}}$ が求められる。

${\displaystyle \alpha _{k}={\boldsymbol {u}}_{k}{}^{\rm {T}}A{\boldsymbol {u}}_{k}}$

また、${\displaystyle {\boldsymbol {u}}_{k-1},{\boldsymbol {u}}_{k}{}}$ がすでに求められているとすると、${\displaystyle {\boldsymbol {u}}_{k+1}}$ はつぎのように計算することができる。 まず ${\displaystyle {\boldsymbol {v}}_{k+1}=\beta _{k}{\boldsymbol {u}}_{k+1}}$ を

${\displaystyle {\boldsymbol {v}}_{k+1}=A{\boldsymbol {u}}_{k}-\beta _{k-1}{\boldsymbol {u}}_{k-1}-\alpha _{k}{\boldsymbol {u}}_{k}}$

によって求める。つぎに ${\displaystyle {\boldsymbol {u}}_{k+1}}$ の正規化条件 ${\displaystyle {\boldsymbol {u}}_{k+1}{}^{\rm {T}}{\boldsymbol {u}}_{k+1}=1}$ を満足させるために ${\displaystyle \beta _{k}}$ を

${\displaystyle \beta _{k}=||{\boldsymbol {v}}_{k+1}||_{2}}$

と定める。そして、

${\displaystyle {\boldsymbol {u}}_{k+1}={\dfrac {1}{\beta _{k}}}{\boldsymbol {v}}_{k+1}}$

とすればよい。

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

特徴

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

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

参考文献

• 森正武『数値解析』共立出版、2002年2月。ISBN 4-320-01701-3。
• 夏目雄平、小川建吾、鈴木敏彦『計算物理３』朝倉書店、2002年11月。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年）。

関連項目

• 数値解析
• 数値線形代数
• 三重対角化
• 対称行列
• 固有値問題
• クリロフ部分空間