Subsections
実用的なプログラムでは,非常に大きな連立方程式を計算しなくてはならない.数百万元
に及ぶことも珍しくない.これを,ガウス・ジョルダン法で
計算するの時間的にほとんど不可能である.そこで,これよりは格段に計算の速い方法が
用いられる.ここでは,その一つとして反復法を簡単に説明する.
当然ここでも,連立方程式
を満たす
![$ \boldsymbol{x}$](img5.png)
を数値計算により,求めることになる.ここで,真の解
![$ \boldsymbol{x}$](img5.png)
とする.
ここで,ある計算によりn回目で求められたものを
とする.そして,計算回数を増やして,
![$\displaystyle \lim_{n\rightarrow\infty}\boldsymbol{x}_n=\boldsymbol{x}$](img7.png) |
(2) |
になったとする.この様に計算回数を増やして,真の解に近づける方法を反復法という.
この様な方法は,行列
を
と分解するだけで,容易に作ることが
できる.たとえば,
とすればよい.ここで,
![$ \boldsymbol{x}_k$](img11.png)
が
![$ \boldsymbol{\alpha}$](img12.png)
に収束するとする.すると,式
(
3)と式(
1)を比べれば,
![$ \boldsymbol{\alpha}$](img12.png)
と
![$ \boldsymbol{x}$](img5.png)
は等しいことがわかる.すなわち,式(
3)で元の方程式
(
1)を表した場合,
![$ \boldsymbol{x}_k$](img11.png)
が収束すれば,必ず真の解
![$ \boldsymbol{x}$](img5.png)
に収束するのである.別の解に収束することはなく,真の解に収束するか,発散
するかのいずれかである.
係数行列
![$ \boldsymbol{A}$](img8.png)
の対角行列を反復計算の行列
![$ \boldsymbol{S}$](img13.png)
としたものがヤコビ(Jacobi)法で
ある.係数行列を
![$\displaystyle \left[ \begin{array}{@{\,}ccccc@{\,}} a_{11} & a_{12} & a_{13} & ...
... & \ddots & \vdots \\ a_{n1} & a_{n2} & a_{n3} & \ldots & 0 \end{array} \right]$](img14.png) |
(4) |
と分解し,右辺第1項が行列
![$ \boldsymbol{S}$](img13.png)
で第2項が
![$ -\boldsymbol{T}$](img15.png)
となる.
![$ \boldsymbol{x}_{k+1}$](img16.png)
の解の
計算に必要な
![$ \boldsymbol{S}$](img13.png)
の逆行列は,それが対角行列なので,
![$\displaystyle \boldsymbol{S}^{-1}= \left[ \begin{array}{@{\,}ccccc@{\,}} a_{11}...
...vdots & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & a_{nn}^{-1} \end{array} \right]$](img17.png) |
(5) |
と簡単に求めることができる.
![$ k+1$](img18.png)
番目の近似解は
![$ \boldsymbol{x}_{k+1}=\boldsymbol{S}^{-1}\left(\boldsymbol{b}+\boldsymbol{T}\boldsymbol{x}_k\right)$](img19.png)
となるなので,容易に
求めることができる.実際,
![$ k$](img20.png)
番目の解を
とすると,k+1番目の解は
![\begin{align*}\begin{aligned}&x_1^{(k+1)}=a_{11}^{-1}\left\{b_1-\left( a_{12}x_2...
...^{(k)}+ \cdots+a_{nn-1}x_{n-1}^{(k)}\right)\right\} \\ \end{aligned}\end{align*}](img22.png) |
(6) |
と計算できる.これを繰り返して連立方程式の解を求める方法が,ヤコビ法である.
ヤコビ法の特徴では,
![$ \boldsymbol{x}^{(k+1)}$](img23.png)
の近似値は,すべてその前の値
![$ \boldsymbol{x}^{(k)}$](img24.png)
を
使うことにある.大きな行列を扱う場合,全ての
![$ \boldsymbol{x}^{(k+1)}$](img23.png)
と
![$ \boldsymbol{x}^{(k)}$](img24.png)
を記
憶する必要があり,大きなメモリーが必要となり問題が生じる.今では,個人で大きなメ
モリーを使い計算することは許されるが,ちょっと前まではできるだけメモリーを節約し
たプログラムを書かなくてはならなかった.
そこで,
の各成分の計算が終わると,それを直ちに使うことが考えば,
メモリーは半分で済む.即ち,
を計算するときに,
とするのである.実際の計算では,
![$ k+1$](img18.png)
番目の解は
と計算できる.これを繰り返して連立方程式の解を求める方法が,ガウス・ザイデル法である.
ガウス・ザイデル法をもっと改善する方法がある.ガウス・ザイデル法の解の修正は,
![$ x_{k+1}-x_k$](img30.png)
であったが,これをもっと大きなステップにしようというのである.通常
の場合,ガウス・ザイデル法では近似解はいつも同じ側にあり,単調に収束する.そのた
め,修正を適当にすれば,もっと早く解に近づく.修正幅を,加速緩和乗数
![$ \omega$](img31.png)
を用
いて,
![$ \omega(x_{k+1}-x_k)$](img32.png)
とする事が考えられた.これが,逐次加速緩和法(SOR法:
Successive Over-Relaxation)である.
具体的な計算手順は,次のようにする.ここでは,ガウス・ザイデル法の式
(8)を用いて,得られた近似解を
としている.
これを繰り返して連立方程式の解を求める方法が,SOR法である.
ここで,問題なのが加速緩和係数
の値の選び方である.明らかに,それが1の場
合,ガウス・ザイデル法となりメリットは無い.また,1以下だと,ガウス・ザイデル法
よりも収束が遅い.ただし,ガウス・ザイデル法で収束しないような問題には使える.
従って,1以上の値にしたいわけであるが,余り大きくすると,発散するのは目に見えて
いる.これについては,2を越えると発散することが分かっている.最適値となると,だ
いたい1.9くらいが選ばれることが多い.
ホームページ:
Yamamoto's laboratory著者:
山本昌志
Yamamoto Masashi
2006-02-08