ここの説明は、文献 [
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{S}^\prime$](img44.png)
とすると、式(
17)は
![$\displaystyle \boldsymbol{e}_{k+1}=\boldsymbol{S}^\prime\Lambda^k\boldsymbol{S}^{\prime-1}\boldsymbol{e}_0$](img45.png) |
(18) |
となる。明らかに、計算回数kを増やしていくと、誤差のベクトルは
![$ \Lambda^k$](img46.png)
に依存す
る。これは、
![$\displaystyle \Lambda^k=\left[ \begin{array}{@{\,}ccccc@{\,}} \lambda_1^k & & &...
...ash{\Huge$0$}}\quad} & & \ddots & \\ & & & & \lambda_n^k \\ \end{array} \right]$](img47.png) |
(19) |
なので、
![$ k\rightarrow\infty$](img48.png)
の場合、誤差
![$ \boldsymbol{e}_k$](img34.png)
がゼロに収束するためには、固有
値すべてが
![$ \vert\lambda_i\vert<1$](img49.png)
でなくてはならない。そして、収束の速度は、最大の固有値
![$ \max\vert\lambda_i\vert$](img50.png)
に依存する。この絶対値が最大の固有値をスペクトル半径と言う。
ここで言いたいのは、連立方程式を式(13)の反復法で計算する場合、
結果が真の値に収束するためには、行列
の最大固有値の絶対値が1以
下でなくてはならないと言うことである。
ホームページ:
Yamamoto's laboratory著者:
山本昌志
Yamamoto Masashi
平成16年12月14日