ランチョス法

行列 ${\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}$ を求めることができる。