ランチョス法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ランチョス法: Lanczos algorithm)とは、対象となる対称行列三重対角化する手法。

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

概要[編集]

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

 B = P^{-1}AP

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


w=
\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)

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


\boldsymbol u_{i}{}^{\rm T} \boldsymbol u_{j} = 
\left\{
\begin{array}{ll}
0;&i\neq j\\
1;&i=j
\end{array}
\right.

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

 AP = PB

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

行列 B に値を入れ、各列を比較すると次式が得られる。


\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.

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

 \alpha_{k}=\boldsymbol u_{k}{}^{\rm T} A \boldsymbol u_{k}

また、\boldsymbol u_{k}{}^{\rm T}, u_{k+1}{}^{\rm T} がすでに求められているとすると、\boldsymbol u_{k+1}{}^{\rm T} はつぎのように計算することができる。 まず \boldsymbol v_{k+1} = \beta_k \boldsymbol u_{k+1}

 \boldsymbol v_{k+1} = A \boldsymbol u_{k} - \beta_{k-1}\boldsymbol u_{k-1} - \alpha_{k} \boldsymbol u_{k}

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

 \beta_{k} = ||\boldsymbol v_{k+1}||_{2}

と定める。そして、

 \boldsymbol u_{k+1} = \dfrac{1}{\beta_k}\boldsymbol v_{k+1}

とすればよい。

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

特徴[編集]

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

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

参考文献[編集]

関連項目[編集]