ランチョス法

ランチョス法（ランチョスほう、）とは、対象となる対称行列を三重対角化する手法。
コルネリウス・ランチョスによって開発された反復計算法である。クリロフ部分空間法の一つ。
概要.
行列 formula_1 を formula_2 の対称行列とする。
これが直交行列 formula_3 によって三重対角行列 formula_4 に直交変換されたとする。
ここで、formula_1 が対称であるから formula_4 も対称である。
そこで、三重対角化された行列 formula_4 の成分を次のようにおくことにする。
formula_9
一方、直交行列 formula_3 の第 formula_11 列のベクトルを formula_12 とすると、formula_3 の直交性から
が成立する。
また上記の直交変換はつぎのように書くことができる。
ランチョス法とは、この関係から直接変換行列 formula_3 すなわちベクトル formula_12 を定めながら、それと同時に三重対角化を行っていく方法である。
上の等式で formula_18 とおき、
行列 formula_4 の成分を代入して両辺の各列を比較すると、次式が得られる。
第 formula_11 行目の式に左から formula_22 を乗じると、直交性より以下のように formula_23 が求められる。
また、formula_25 がすでに求められているとすると、formula_26 はつぎのように計算することができる。
まず formula_27 を
によって求める。つぎに formula_26 の正規化条件 formula_30 を満足させるために formula_31 を
と定める。そして、
とすればよい。
このようにして、formula_34 なる任意の初期ベクトル formula_35 からはじめて順次 formula_36 を計算することにより三重対角行列 formula_4 を求めることができる。
特徴.
もとの行列 formula_1 は変形を受けず、formula_1 とベクトルの積だけで計算が行われるのがランチョス法の長所である。
このため、行列要素にゼロの割合が多い疎行列の対角化法として有力なものである。
また、直交性から、3項のみから成る漸化関係によって逐次求める量が得られていくのがこの方法の大きな特徴である。
しかし計算を進めていくうちに丸め誤差の累積によって formula_12 の直交性がくずれてしまう可能性も持っている。