Subsections
ここの説明は,文献 [
1]を参考にしました.これは,線形代数を
実際にどのように使うか述べられた教科書で,詳しく書かれている.線形代数を実際に使
う場合,一読することを進める.初めて私が線形代数の講義を受けたとき,あまりにも抽
象的で,さっぱりわからなかった.その後,この教科書を読むことにより,なるほど便利
なものであるとやっとわかったのである.
さて,いままで学習した直接法はしつこく計算すれば,必ず解が求まる.しかし,大きな
連立方程式を計算するには不向きである.なぜならば,ガウス・ジョルダン法の計算回数
は,方程式の元nの
![$ n^3$](img22.png)
に比例するため,大きな行列ではとたんに計算時間が必要になる
からである.
実用的なプログラムでは,非常に大きな連立方程式を計算しなくてはならない.たとえば,
私の研究室での計算でも10万元くらいは計算している.これを,ガウス・ジョルダン法で
計算するの時間的にほとんど不可能である.そこで,これよりは格段に計算の速い反復法
を用いている.ここでは,反復法を簡単に説明する.
当然ここでも,連立方程式
を満たす
![$ \boldsymbol{x}$](img3.png)
を数値計算により,求めることになる.ここで,真の解
![$ \boldsymbol{x}$](img3.png)
とする.
ここで,ある計算によりn回目で求められたものを
とする.そして,計算回数を増やして,
![$\displaystyle \lim_{n\rightarrow\infty}\boldsymbol{x}_n=\boldsymbol{x}$](img25.png) |
(12) |
になったとする.この様に計算回数を増やして,真の解に近づける方法を反復法という.
この様な方法は,行列
を
と分解するだけで,容易に作ることが
できる.たとえば,
とすればよい.ここで,
![$ \boldsymbol{x}_k$](img28.png)
が
![$ \boldsymbol{\alpha}$](img29.png)
に収束するとする.すると,式
(
13)と式(
11)を比べれば,
![$ \boldsymbol{\alpha}$](img29.png)
と
![$ \boldsymbol{x}$](img3.png)
は等しいことがわかる.すなわち,式(
13)で元の方程式
(
11)を表した場合,
![$ \boldsymbol{x}_k$](img28.png)
が収束すれば,必ず真の解
![$ \boldsymbol{x}$](img3.png)
に収束するのである.別の解に収束することはなく,真の解に収束するか,発散
するかのいずれかである.振動することはないのか?.それはよい質問である.興味があ
る人が調べてみてほしい.
先の説明で,式(
13)を使った反復法の場合,
![$ \boldsymbol{x}_k$](img28.png)
の収束が重要
であることがわかった.ここでは,これが収束する条件を示す.
真の解の場合,式(13)は
となる.この式(
14)から式(
13)を引くと,
となる.
![$\displaystyle \boldsymbol{S}(\boldsymbol{x}-\boldsymbol{x}_{k+1})=\boldsymbol{T}(\boldsymbol{x}-\boldsymbol{x}_k)$](img31.png) |
(15) |
となる.ここで,
![$ \boldsymbol{x}-\boldsymbol{x}_{k+1}$](img32.png)
や
![$ \boldsymbol{x}-\boldsymbol{x}_k$](img33.png)
は,真の解からの差,すな
わち,誤差を示している.k回目の計算の誤差を
![$ \boldsymbol{e}_k$](img34.png)
とすると,
![$\displaystyle \boldsymbol{e}_{k+1}=\boldsymbol{S}^{-1}\boldsymbol{T}\boldsymbol{e}_k$](img35.png) |
(16) |
と表すことができる.この誤差ベクトル
![$ \boldsymbol{e}_k$](img34.png)
がゼロに収束すれば,ハッピーなのだ.
ハッピーになるための条件を探すために,計算の最初の誤差を
とする.すると,
となる.この式の右辺に行列のk乗の計算がある.このとき,
2.3
節で得た結果を利用する.行列
![$ \boldsymbol{S}^{-1}\boldsymbol{T}$](img43.png)
の固有値と固有ベクトルで作る行列
を,
![$ \Lambda$](img20.png)
と
![$ \boldsymbol{X}$](img8.png)
とすると,式(
17)は
![$\displaystyle \boldsymbol{e}_{k+1}=\boldsymbol{X}\Lambda^k\boldsymbol{X}^{-1}\boldsymbol{e}_0$](img44.png) |
(18) |
となる.明らかに,計算回数kを増やしていくと,誤差のベクトルは
![$ \Lambda^k$](img45.png)
に依存す
る.これは,
![$\displaystyle \Lambda^k=\left[ \begin{array}{@{ }ccccc@{ }} \lambda_1^k & & &...
...ash{\Huge$0$}}\quad} & & \ddots & \ & & & & \lambda_n^k \ \end{array} \right]$](img46.png) |
(19) |
なので,
![$ k\rightarrow\infty$](img47.png)
の場合,誤差
![$ \boldsymbol{e}_k$](img34.png)
がゼロに収束するためには,固有
値すべてが
![$ \vert\lambda_i\vert<1$](img48.png)
でなくてはならない.そして,収束の速度は,最大の固有値
![$ \max\vert\lambda_i\vert$](img49.png)
に依存する.この絶対値が最大の固有値をスペクトル半径と言う.
ここで言いたいのは,連立方程式を式(13)の反復法で計算する場合,
結果が真の値に収束するためには,行列
の最大固有値の絶対値が1以
下でなくてはならないと言うことである.
最大固有値が1以下になる行列の条件を探すことは難しい.また,予め行列
の最大固有値を計算することも考えられるが,それもかなりの計算
量が必要で,反復法を使って計算時間を短縮するメリットが無くなってしまう.このよう
なことから,反復法はとりあえず試してみて,発散するようであれば他の方法に切り替え
るのが良いだろう.後で述べるSOR法の加速緩和係数
を1以下にするという方法も
ある.
ホームページ:
Yamamoto's laboratory著者:
山本昌志
Yamamoto Masashi
2005-12-09