ランチョス法

ランチョス法（ランチョスほう、英: 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年）。

関連項目

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

表 話 編 歴 線型代数学・行列解析
連立一次方程式	ガウスの消去法 クラメルの公式 ガウス＝ザイデル法 ヤコビ法
ベクトル	線型独立 線型結合 基底 双対基底
ベクトル空間	双対空間 核空間 固有空間 広義固有空間 線型包 行空間 列空間 次元
計量ベクトル空間	ドット積 コーシー＝シュワルツの不等式 直交 正規直交系 正規直交基底 グラム・シュミットの正規直交化法 直交補空間
行列・線型写像	演算・操作 乗法 転置 逆行列 サラスの方法 基本変形 対角化 分解 LU QR コレスキー シューア 特異値 固有値 不変量 行列式 跡 階数 固有値と固有ベクトル 固有多項式 最小多項式 単因子 階数標準形 スミス標準形 ジョルダン標準形 有理標準形 小行列式 クラス 正則 基本 対称 エルミート 正規 直交 回転 ユニタリ 冪零 射影 正定値 ユニモジュラー 置換 区分
行列式	余因子展開 余因子行列 ヴァンデルモンドの行列式 終結式 コーシー・ビネの公式
多重線型代数	外積 外積代数 対称代数 テンソル代数
数値線形代数	基本的な概念 浮動小数点 数値的安定性 疎行列 Z-行列 M行列 条件数 ゲルシュゴリンの定理 クリロフ部分空間 ソフトウェア MATLAB 数値解析ソフトの比較/一覧 ライブラリ Armadillo Basic Linear Algebra Subprograms (BLAS) INTLAB Intel oneAPI Math Kernel Library LAPACK NumPy OpenBLAS 線型代数学ライブラリの比較 反復法・技法 SOR法 共役勾配法 GMRES法 固有値問題の数値解法 ランチョス法 QR法 べき乗法 逆べき乗法 ヤコビ法 (固有値問題) シュトラッセンのアルゴリズム ハウスホルダー変換 ギブンス回転 人物 ジェームズ・H・ウィルキンソン クリーブ・モラー ニコラス・ハイアム ジーン・ゴラブ リチャード・バルガ
行列値関数	行列指数関数 行列の対数 行列の平方根
その他	スカラー ケイリー・ハミルトンの定理 ペロン＝フロベニウスの定理 シューア補行列 シルヴェスターの慣性法則
カテゴリ