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{X}$ とすると，式(17)は

$$\boldsymbol{e}_{k+1}=\boldsymbol{X}\Lambda^k\boldsymbol{X}^{-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以 下でなくてはならないと言うことである．

最大固有値が1以下になる行列の条件を探すことは難しい．また，予め行列 $\boldsymbol{S}^{-1}\boldsymbol{T}$ の最大固有値を計算することも考えられるが，それもかなりの計算 量が必要で，反復法を使って計算時間を短縮するメリットが無くなってしまう．このよう なことから，反復法はとりあえず試してみて，発散するようであれば他の方法に切り替え るのが良いだろう．後で述べるSOR法の加速緩和係数$\omega$ を1以下にするという方法も ある．

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