next up previous contents
Next: 6.5 都合が「よくない」場合の Lanczos 法 Up: 6 Lanczos アルゴリズム Previous: 6.3 Lanczos 原理

6.4 都合が「よい」状況下での Lanczos 法

$ A$ $ n$ 次の実対称行列で、$ x\in\R^n$ に対して、 「都合よく」

$\displaystyle {\cal K}_n(A,x)=\R^n
$

が成り立つと仮定する。前節の定理から、

$\displaystyle U^T A U=
\left(
\begin{array}{ccccccc}
\alpha_1&\beta_1 & & & ...
...1}&\beta_{n-1}\\
\bigzerol& & & & &\beta_{n-1}&\alpha_n
\end{array} \right)
$

をみたす実直交行列 $ U=(\Vector{u}_1 \Vector{u}_2 \cdots\
\Vector{u}_n)$ が存在する。 これから

      $\displaystyle A \Vector{u}_1=\alpha_1 \Vector{u}_1+\beta_1 \Vector{u}_2,$
      $\displaystyle A\Vector{u}_2=\beta_1\Vector{u}_1+\alpha_2\Vector{u}_2+\beta_2\Vector{u}_3,$
      $\displaystyle \quad \vdots$
(5)   $\displaystyle A\Vector{u}_i=\beta_{i-1}\Vector{u}_{i-1}+\alpha_i\Vector{u}_i+\beta_i \Vector{u}_{i+1},$
      $\displaystyle \quad \vdots$
      $\displaystyle A\Vector{u}_{n-1}=\beta_{n-2}\Vector{u}_{n-2}+\alpha_{n-1}\Vector{u}_{n-1}+ \beta_{n-1}\Vector{u}_{n},$
      $\displaystyle A \Vector{u}_{n}=\beta_{n-1} \Vector{u}_{n-1}+\alpha_{n} \Vector{u}_{n}$

という条件が導かれる。 また

(6) $\displaystyle \Vector{u}_1=\pm\dfrac{1}{\Vert x\Vert}x$

である。 実は $ \{\alpha_i\}$ , $ \{\beta_i\}$ , $ \{\Vector{u}_j\}$ は この条件 (5), (6) だけで定めることができる。

最初の式と $ \Vector{u}_1$ との内積を取ると

$\displaystyle \alpha_1=\Vector{u}_1^T A \Vector{u}_1.
$

$ \Vector{v}_2:= A\Vector{u}_1-\alpha_1\Vector{u}_1$ とおくと、 $ \beta_1\Vector{u}_2=\Vector{v}_2$ であるから、

$\displaystyle \vert\beta_1\vert=\Vert\Vector{v}_2\Vert.
$

ゆえに

$\displaystyle \beta_1=\pm\Vert\Vector{v}_2\Vert,\quad
\Vector{u}_2:=\frac{1}{\beta_1}\Vector{v}_2=\pm\frac{1}{\Vert\Vector{v}_2\Vert}
\Vector{v}_2$   (複号同順)$\displaystyle .$

(5) の第2式と $ \Vector{u}_2$ との内積を取ると、

$\displaystyle \alpha_2=\Vector{u}_2^T A \Vector{u}_2.
$

$ \Vector{v}_3:= A\Vector{u}_2-\beta_1\Vector{u}_1-
\alpha_2\Vector{u}_2$ とおくと、 $ \beta_2\Vector{u}_3=\Vector{v}_3$ であるから、

$\displaystyle \vert\beta_2\vert=\Vert\Vector{v}_3\Vert.
$

ゆえに

$\displaystyle \beta_2=\pm\Vert\Vector{v}_3\Vert,\quad
\Vector{u}_3:=\frac{1}{\beta_2}\Vector{v}_3=\pm\frac{1}{\Vert\Vector{v}_3\Vert}
\Vector{v}_3$   (複号同順)$\displaystyle .$

以下同様にして...


next up previous contents
Next: 6.5 都合が「よくない」場合の Lanczos 法 Up: 6 Lanczos アルゴリズム Previous: 6.3 Lanczos 原理
桂田 祐史
2015-12-22