数値解析（塩田）2020年度

数値解析第12回 (3)　ガウス・ザイデル法

ガウス・ザイデル法のアイデア

　ヤコビ法のアルゴリズム 2° をよく見てみましょう：

for $i=1$ to $n$
$\require{color}$ $\dps{ x^{(k+1)}_i = \left.\left\{ b_i-\dps{\sum_{j=1}^{i-1}a_{ij} \, \textcolor{red}{x^{(k)}_j}} -\dps{\sum_{j=i+1}^na_{ij} \, x^{(k)}_j} \right\}\right/a_{ii} }$

$x^{(k+1)}_i$ を求める時点では既に新しい $x^{(k+1)}_1$, $x^{(k+1)}_2$, $\cdots$ $x^{(k+1)}_{i-1}$ が求まっているのですが、古い $x^{(k)}_1$, $x^{(k)}_2$, $\cdots$ $x^{(k)}_{i-1}$ を使っています ( 赤い部分 )。 $\{\,\xxx^{(k)}\,\}$ が解に収束するのであれば新しいデータの方が良い近似値であると考えられるので、折角なので新しい方を使おう、というのがガウス・ザイデル法です。

ガウス・ザイデル法のアルゴリズム

Algorithm 3 ( ガウス・ザイデル法 )　

$\xxx^{(0)} = $ 適当なベクトル, $k=0$
for $i=1$ to $n$
$x^{(k+1)}_i = \left.\left\{ b_i-\dps{\sum_{j=1}^{i-1}a_{ij}\,\textcolor{red}{x^{(k+1)}_j}} -\dps{\sum_{j=i+1}^na_{ij}\,x^{(k)}_j} \right\}\right/a_{ii}$,
$k=k+1$
if ( 終了条件 ) $\xxx^{(k)}$ を出力して終了 else 2° へ戻れ

赤い部分がヤコビ法との違いで、終了条件はヤコビ法と同様に設定します。

実行例

　さっきと同じ

Ex.1　 $ \dps{ \left\{ \begin{array}{l} 3x-2y = 1\\ \phantom{3}x+3y = 4\\ \end{array} \right. } $

で実行してみましょう。今度は $\dps{ \left\{ \begin{array}{l} \mbox{新} x = \dps{\frac{1}{3}} \left(1+2\times\mbox{旧}y\right) \\ \mbox{新} y = \dps{\frac{1}{3}} \left(4-\textcolor{red}{\mbox{新}x}\right) \\ \end{array} \right. }$ となり、初期値 $(x,y)=(0,0)$ で実行すると

k =  0 : (x,y) = (0.0000000000, 0.0000000000)
k =  1 : (x,y) = (0.3333333333, 1.2222222222)
k =  2 : (x,y) = (1.1481481481, 0.9506172840)
k =  3 : (x,y) = (0.9670781893, 1.0109739369)
k =  4 : (x,y) = (1.0073159579, 0.9975613474)
k =  5 : (x,y) = (0.9983742316, 1.0005419228)
k =  6 : (x,y) = (1.0003612819, 0.9998795727)
k =  7 : (x,y) = (0.9999197151, 1.0000267616)
k =  8 : (x,y) = (1.0000178411, 0.9999940530)
k =  9 : (x,y) = (0.9999960353, 1.0000013216)
k = 10 : (x,y) = (1.0000008810, 0.9999997063)
k = 11 : (x,y) = (0.9999998042, 1.0000000653)
k = 12 : (x,y) = (1.0000000435, 0.9999999855)
k = 13 : (x,y) = (0.9999999903, 1.0000000032)
k = 14 : (x,y) = (1.0000000021, 0.9999999993)
k = 15 : (x,y) = (0.9999999995, 1.0000000002)
k = 16 : (x,y) = (1.0000000001, 1.0000000000)
k = 17 : (x,y) = (1.0000000000, 1.0000000000)

ヤコビ法の半分ほどのループ回数で厳密解 $(x,y)=(1,1)$ に収束しました。

前へ / 戻る / 次へ