3 反復法の基礎

ここの説明は、文献 [1]を参考にしました。これは、線形代数を 実際にどのように使うか述べられた教科書で、詳しく書かれている。線形代数を実際に使 う場合、一読することを進める。初めて私が線形代数の講義を受けたとき、あまりにも抽 象的で、さっぱりわからなかった。その後、この教科書を読むことにより、なるほど便利 なものであるとやっとわかったのである。

3.1 反復法とは

さて、いままで学習した直接法はしつこく計算すれば、必ず解が求まる。しかし、大きな 連立方程式を計算するには不向きである。なぜならば、ガウス・ジョルダン法の計算回数 は、方程式の元nの$n^3$に比例するため、大きな行列ではとたんに計算時間が必要になる からである。

実用的なプログラムでは、非常に大きな連立方程式を計算しなくてはならない。たとえば、 私の研究室での計算でも10万元くらいは計算している。これを、ガウス・ジョルダン法で 計算するの時間的にほとんど不可能である。そこで、これよりは格段に計算の速い反復法 を用いている。ここでは、反復法を簡単に説明する。

当然ここでも、連立方程式

$$\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}$$ (11)

を満たす $\boldsymbol{x}$を数値計算により、求めることになる。ここで、真の解 $\boldsymbol{x}$とする。

ここで、ある計算によりn回目で求められたものを $\boldsymbol{x}_n$とする。そして、計算回数を増やして、

$$\lim_{n\rightarrow\infty}\boldsymbol{x}_n=\boldsymbol{x}$$ (12)

になったとする。この様に計算回数を増やして、真の解に近づける方法を反復法という。

この様な方法は、行列 $\boldsymbol{A}$を $\boldsymbol{S}-\boldsymbol{T}$と分解するだけで、容易に作ることが できる。たとえば、

$$\boldsymbol{S}\boldsymbol{x}_{k+1}=\boldsymbol{T}\boldsymbol{x}_{k}+\boldsymbol{b}$$ (13)

とすればよい。ここで、 $\boldsymbol{x}_k$が $\boldsymbol{\alpha}$に収束するとする。すると、式 (13)と式(11)を比べれば、 $\boldsymbol{\alpha}$と $\boldsymbol{x}$は等しいことがわかる。すなわち、式(13)で元の方程式 (11)を表した場合、 $\boldsymbol{x}_k$が収束すれば、必ず真の解 $\boldsymbol{x}$に収束するのである。別の解に収束することはなく、真の解に収束するか、発散 するかのいずれかである。振動することはないのか?。それはよい質問である。興味があ る人が調べてみてほしい。

3.2 解の収束の条件

先の説明で、式(13)を使った反復法の場合、 $\boldsymbol{x}_k$の収束が重要 であることがわかった。ここでは、これが収束する条件を示す。

真の解の場合、式(13)は

$$\boldsymbol{S}\boldsymbol{x}=\boldsymbol{T}\boldsymbol{x}+\boldsymbol{b}$$ (14)

となる。この式(14)から式(13)を引くと、 となる。

$$\boldsymbol{S}(\boldsymbol{x}-\boldsymbol{x}_{k+1})=\boldsymbol{T}(\boldsymbol{x}-\boldsymbol{x}_k)$$ (15)

となる。ここで、 $\boldsymbol{x}-\boldsymbol{x}_{k+1}$や $\boldsymbol{x}-\boldsymbol{x}_k$は、真の解からの差、すな わち、誤差を示している。k回目の計算の誤差を $\boldsymbol{e}_k$とすると、

$$\boldsymbol{e}_{k+1}=\boldsymbol{S}^{-1}\boldsymbol{T}\boldsymbol{e}_k$$ (16)

と表すことができる。この誤差ベクトル $\boldsymbol{e}_k$がゼロに収束すれば、ハッピーなのだ。

ハッピーになるための条件を探すために、計算の最初の誤差を $\boldsymbol{e}_0$とする。すると、

$$\boldsymbol{e}_{k+1} =\boldsymbol{S}^{-1}\boldsymbol{T}\boldsymbol{e}_k$$

$$=\boldsymbol{S}^{-1}\boldsymbol{T}\boldsymbol{S}^{-1}\boldsymbol{T}\boldsymbol{e}_{k-1}$$

$$=\boldsymbol{S}^{-1}\boldsymbol{T}\boldsymbol{S}^{-1}\boldsymbol{T}\boldsymbol{S}^{-1}\boldsymbol{T}\boldsymbol{e}_{k-2}$$

$$=\boldsymbol{S}^{-1}\boldsymbol{T}\boldsymbol{S}^{-1}\boldsymbol{... ...l{S}^{-1}\boldsymbol{T}\cdots \boldsymbol{S}^{-1}\boldsymbol{T}\boldsymbol{e}_0$$

$$=\left(\boldsymbol{S}^{-1}\boldsymbol{T}\right)^k\boldsymbol{e}_0$$ (17)

となる。この式の右辺に行列のk乗の計算がある。このとき、2.3 節で得た結果を利用する。行列 $\boldsymbol{S}^{-1}\boldsymbol{T}$の固有値と固有ベクトルで作る行列 を、$\Lambda$と $\boldsymbol{S}^\prime$とすると、式(17)は

$$\boldsymbol{e}_{k+1}=\boldsymbol{S}^\prime\Lambda^k\boldsymbol{S}^{\prime-1}\boldsymbol{e}_0$$ (18)

となる。明らかに、計算回数kを増やしていくと、誤差のベクトルは$\Lambda^k$に依存す る。これは、

$$\Lambda^k=\left[ \begin{array}{@{\,}ccccc@{\,}} \lambda_1^k & & &... ...ash{\Huge$0$}}\quad} & & \ddots & \\ & & & & \lambda_n^k \\ \end{array} \right]$$ (19)

なので、 $k\rightarrow\infty$の場合、誤差 $\boldsymbol{e}_k$がゼロに収束するためには、固有 値すべてが $\vert\lambda_i\vert<1$でなくてはならない。そして、収束の速度は、最大の固有値 $\max\vert\lambda_i\vert$に依存する。この絶対値が最大の固有値をスペクトル半径と言う。

ここで言いたいのは、連立方程式を式(13)の反復法で計算する場合、 結果が真の値に収束するためには、行列 $\boldsymbol{S}^{-1}\boldsymbol{T}$の最大固有値の絶対値が1以 下でなくてはならないと言うことである。

ホームページ: Yamamoto's laboratory
著者: 山本昌志