next up previous contents
Next: 3.3 実験プログラムたたき台 Up: 3 三重対角化の手法 Previous: 3.1.0.2 Householder 行列による三重対角化

3.2 Lanczos (ランチョス) 法

(この話題については、 『固有値問題ノートの補足』 http://nalab.mind.meiji.ac.jp/~mk/labo/text/eigenvalues-add.pdfに説明を書いた。そのうちこちらとマージする。)

実対称行列 $ A$ が直交行列 $ P$ で三重対角化されたとする:

$\displaystyle B=P^T A P =
\left(
\begin{array}{ccccc}
\alpha_1 & \beta_1 & 0...
... \beta_{N-1}\\
\bigzerol& & 0 & \beta_{N-1} & \alpha_N
\end{array} \right).
$

これから $ A P=P B$ であるが、 $ P=(u_1 u_2 \cdots u_N)$ とおくと、

$\displaystyle A (u_1 u_2 \cdots u_N) = (u_1 u_2 \cdots u_N)
\left(
\begin{arr...
...& \beta_{N-1}\\
\bigzerol& & 0 & \beta_{N-1} & \alpha_N
\end{array} \right)
$

となるから
  $\displaystyle A u_1$ $\displaystyle =$ $\displaystyle \alpha_1 u_1 + \beta_1 u_2$
  $\displaystyle A u_2$ $\displaystyle =$ $\displaystyle \beta_1 u_1 + \alpha_2 u_2 + \beta_2 u_3$
  $\displaystyle \cdots$    
  $\displaystyle A u_i$ $\displaystyle =$ $\displaystyle \beta_{i-1}u_{i-1} + \alpha_i u_i + \beta_i u_{i+1}$
  $\displaystyle \cdots$    
  $\displaystyle A u_N$ $\displaystyle =$ $\displaystyle \beta_{N-1}u_{N-1} + \alpha_N u_N$

$ k$ 行と $ u_k$ の内積を作ると

(1) $\displaystyle \alpha_k = {u_k}^T A u_k.$

また

(2) $\displaystyle v_{k+1}:= \left\{ \begin{array}{ll} A u_1 - \alpha_1 u_1 & \mbox{...
...- (\beta_k u_{k-1}+\alpha_k u_k) & \mbox{($1\le k\le N-1$)} \end{array} \right.$

とおくと、 $ v_{k+1}=\beta_k u_{k+1}$ , $ \Vert u_{k+1}\Vert=1$ であるから、
(3) $\displaystyle \beta_k$ $\displaystyle =$ $\displaystyle \pm\Vert v_{k+1}\Vert$
(4) $\displaystyle u_{k+1}$ $\displaystyle =$ $\displaystyle \frac{v_{k+1}}{\beta_k}.$

これから、最初に適当に $ \Vert u_1\Vert=1$ となる $ u_1$ を選び、 以下 $ \beta_k\ne 0$ である限り、計算を進めることができる。


next up previous contents
Next: 3.3 実験プログラムたたき台 Up: 3 三重対角化の手法 Previous: 3.1.0.2 Householder 行列による三重対角化
桂田 祐史
2015-12-22