Krylov部分空間の基本

とても久しぶりの更新となりました．ブログ欲が出てきたので、復活したいと思います． 以前までの記事の書き方と変えて，単にまとめるだけでなく紹介する形の文体を取っていきたいと思います．

線形連立方程式の数値計算法は数値シミュレーションを代表として工学上非常に重要な研究対象となっています．係数行列が正定値対称となる場合の線形連立方程式の数値計算法として、一般に共役勾配法と呼ばれる反復法が非常に有効であることが知られています．

共役勾配法はKrylov部分空間法の一種で、Krylov部分空間と呼ばれる線形部分空間をベースに解を探索します．今回はKrylov部分空間の基本的な性質をまとめます．

定義

行列\( A \in \mathbb{R}^{n\times n} \)とベクトル\( b \in \mathbb{R}^n \)に対し，

\( \mathcal{K}_{r}(A;b) = \mathrm{span} ( b, Ab, A^{2} b, \ldots , A^{r-1} b ) \)

をKrylov部分空間と呼ぶ．

Krylov部分空間法は，\( r \)ステップにおける近似解を\( \mathcal{K}_{r}(A;b) \)の中から探すアルゴリズムとなっています．この近似解を\( \mathcal{K}_{r}(A;b) \)の基底を用いてどのように構成するのかによってさまざまなバリエーションがあります．

Krylov部分空間の基本的な性質を説明します．

補題

\( r\in \mathbb{N} \)に対し，

\( \mathcal{K}_{r}(A;b) \subseteq \mathcal{K}_{r+1}(A;b) \)

をみたす．

証明

Krylov部分空間の定義より明らか．（証明終）

定理

正則な行列\( A \in \mathbb{R}^{n\times n} \)とベクトル\( b \in \mathbb{R}^n \)を考える．\(\mathcal{K}_{r}(A;b) = \mathcal{K}_{r+1}(A;b) \)をみたす最小の\(r \in \mathbb{N}\)に対し，\( Ax = b \)をみたす\(x \in \mathbb{R}^n \)は\(\mathcal{K}_{r}(A;b)\)に含まれる．

証明

\(\mathcal{K}_{r}(A;b) = \mathcal{K}_{r+1}(A;b) \)であることから，

\( A^{r}b = c_{0}b + c_{1}Ab + \cdots + c_{r-1}A^{r-1}b \)

をみたす\(c_{0}, c_{1}, \ldots, c_{r-1} \)が存在する．ここで，\(c_{0} = 0\)とすると一次独立性から\(r \)が最小であることと矛盾するため，\(c_{0} \neq 0\)である．このとき，

\( A\left(\frac{1}{c_{0}}A^{r-1}b - \frac{c_{r-1}}{c_{0}}A^{r-2}b - \cdots - \frac{c_{1}}{c_{0}}b \right) = b \)

と変形できる．したがって，\(Ax = b\)をみたす\(x \)は，

\( x = \frac{1}{c_{0}}A^{r-1}b - \frac{c_{r-1}}{c_{0}}A^{r-2}b - \cdots - \frac{c_{1}}{c_{0}}b \)

となり，\( x \in \mathcal{K}_{r}(A; b) \)である．（証明終）

上記の定理はKrylov部分空間法に基づいて計算を行った場合における解の存在性を示しています． しかも，係数行列が\(n\)次の正方行列であれば，Krylov部分空間は\( \mathcal{K}_{n} \)以上に拡大することはないため，理論上反復計算を最大\( n\)ステップで終了させることができます．

しかしながら，実際には丸めなどの数値的な誤差の影響で必ず\( n \)ステップで収束するとは限りません．このあたりの話はまた別の機会に．