3.2 Lanczos (ランチョス) 法

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

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

$$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)$ とおくと、

$$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)$$

となるから

$$A u_1 = \alpha_1 u_1 + \beta_1 u_2$$

$$A u_2 = \beta_1 u_1 + \alpha_2 u_2 + \beta_2 u_3$$

$$\cdots$$

$$A u_i = \beta_{i-1}u_{i-1} + \alpha_i u_i + \beta_i u_{i+1}$$

$$\cdots$$

$$A u_N = \beta_{N-1}u_{N-1} + \alpha_N u_N$$

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

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

また

$$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.$$ (2)

とおくと、 $v_{k+1}=\beta_k u_{k+1}$ , $\Vert u_{k+1}\Vert=1$ であるから、

$$\beta_k = \pm\Vert v_{k+1}\Vert$$ (3)

$$u_{k+1} = \frac{v_{k+1}}{\beta_k}.$$ (4)

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