Gakuyu
４．3 連立１次方程式の反復解法
反復法は，未知数に適当な初期値を仮定し，必要な精度に到達するまで同じ手
順を繰り返して，解を求める方法である。
方程式の元数が非常に多く（数千元以上），係数行列がスパース行列（要素の大部分
が０の行列）の場合は，直接法(ガウスの消去法など）よりは，反復法が有利である。
しかし，反復法の公式の多くは，無条件に収束しない（反復回数の増加とともに近似
解が真の解から離れていく）から，適用に際しては収束条件に注意しなければならな
い。
4.3.1 ヤコビ法
［Ａ］ヤコビ法の考え方
まず，ヤコビ法の考え方を，次の例題によって，説明しよう。解こうと する連立１次方程式は次式とする。
4ｘ＋ ｙ＝8 ①
ｘ＋2ｙ＝5.5
これを解くには次のようにする。まず，第１式をｘについて解き，第２式をｙ について解くと，次のようになる。
ｘ＝2.0－0.25ｙ ②
ｙ＝2.75－0.5ｘ
ここで，ｘとｙに適当な値を仮定して，この２つの式の右辺に代入する。適当 な値は何でもよいが，例えば，ｘ＝ｙ＝0 として右辺に代入すると，次のように なる。
ｘ＝2.0-0.25･0=2.0 ③
ｙ＝2.75-0.5･0=2.75
この値をまた，式②の右辺に代入すると，次のようになる。
ｘ＝2.0-0.25×2.75=1.3125 ④
ｙ＝2.75-0.5×2.0=1.75
このように，つぎつぎと代入を繰り返していくと，ｘとｙは, 次のように，真 の解に近づいていく。
表4.1 ヤコビ法による連立１次方程式①の解を求める途中の過程|
|
|
|
この反復法がヤコビ法（Jacob）である。
以上の手順を，次のｎ元連立１次方程式の場合について一般化しよう。
|
ａ１１ｘ１＋ａ１２ｘ２＋
･････＋ａ１ｎｘｎ＝ｂ１ ａ２１ｘ１＋ａ２２ｘ２＋ ･････＋ａ２ｎｘｎ＝ｂ２ ･･････････････････････ ａｉ１ｘ１＋ａｉ２ｘ２＋ ･････＋ａｉｎｘｎ＝ｂｉ ･･････････････････････ ａｎ１ｘ１＋ａｎ２ｘ２＋ ･････＋ａｎｎｘｎ＝ｂｎ |
(4.51) |
いま，対角要素ａ１１，ａ２２，･･･，ａｎｎ は０でないとして，ｘ１，ｘ２，･･･，ｘｎ を求めると，次のようになる。
|
ｘ１＝（ｂ１－ａ１２ｘ２－
ａ１３ｘ３･････－ａ１ｎｘｎ
）／ａ１１ ｘ２＝（ｂ２－ａ２１ｘ１－ ａ２３ｘ３･････－ａ２ｎｘｎ ）／ａ２２ ･･･････････････････････ ｘｉ＝（ｂｉ－ａｉ１ｘ１･･･ －ａｉｉ－１ｘｉ－１－ａｉ＋１ｘ ｉ＋１･･･－ａｉｎｘｎ）／ａｉｉ ･･･････････････････････ ｘｎ＝（ｂｎ－ａｎ１ｘ１－ ａｎ２ｘ２－･････－ａｎｎ－１ｘ ｎ－１）／ａｎｎ |
(4.52) |
上式を用いて，まず，１番目の式の未知数ｘ２，････，ｘｎ
に近似値を代入してｘ１を求め，２番目の式からｘ２
以外の未知数に近似値を代入してｘ２を求める。このように，
右辺の未知数に近似値を代入し，それによって左辺の未知数のより良い近似解を計
算する。これを何回も繰り返してやれば，解の精度が高くなってくる。
いま，ｋ回繰り返して，ｘ１，ｘ２，･･･，ｘｎ
の「第ｋ近似解」を，ｘの右肩に（ｋ）をつけて，
ｘ１（ｋ），ｘ２（ｋ） ，････，ｘｎ（ｋ）
のように表すとする。これをもとに第（ｋ＋１）近似解求める反復公式は次の ようになる。
|
ｘ１（ｋ＋１）＝（ｂ１－ａ１２
ｘ２（ｋ）－ａ１３ｘ３
（ｋ）･････－ａ１ｎｘｎ（ｋ）
）／ａ１１ ｘ２（ｋ＋１）＝（ｂ２－ａ２１ ｘ１（ｋ）－ａ２３ｘ３ （ｋ）･････－ａ２ｎｘｎ（ｋ） ）／ａ２２ ･･･････････････････････ ｘｉ（ｋ＋１）＝（ｂｉ－ａｉ１ ｘ１（ｋ）･･･－ａｉｉ－１ｘ ｉ－１（ｋ）－ａｉ＋１ｘｉ＋１ （ｋ）･･･－ａｉｎｘｎ（ｋ） ）／ａｉｉ ･･･････････････････････ ｘｎ（ｋ＋１）＝（ｂｎ－ａｎ１ ｘ１（ｋ）－ａｎ２ｘ２ （ｋ）－･････－ａｎｎ－１ｘｎ－１ （ｋ））／ａｎｎ |
(4.53) |
上式をまとめて書くと，次のようになる。
|
(4.54) |
これがヤコビ法の公式である。
［Ｂ］ヤコビ法の手順とフローチャート
ヤコビ法の公式(4.54)を用いて，次の手順で連立１次方程式の解を求める。
|
（０）ｋ＝０として，ヤコビの公式(4.54)の右辺のｘ１
（０），ｘ２（０），･･･，ｘｎ
（０）に任意の値を与え、公式(4.54)より， （１）次に，ｋ＝１として，いま求めたｘ１（１）
，ｘ２（１），･･･，ｘｎ（１）
を式(4.54)の右辺に代入し， （２）次に，ｋ＝２として，いま求めたｘ１（２）
，ｘ２（２），･･･，ｘｎ（２）
を式(4.54)の右辺に代入し， ･･････････････ （ｋ）この反復を繰り返して，あるｋに対して求めた解， |
以上の手順をフローチャートに示した結果を図4.37に示す。
図中に用いた収束判定条件は次式を用いた。
ｄｘ／｜ｘｎｅｗ｜＜ε (4.55)
ここで，ｄｘ＝｜ｘｎｅｗ－ｘｏ(i)｜
ｘｎｅｗ ：いま，求めた近似解
ｘｏ(i) ：前回に求めた近似解
ε ：許容相対誤差
収束判定条件がすべてのｘｉに対して成り立っていることが，反復 終了のためには必要である。反復は，式(4.55)が成り立つまで続けられる。
4.3.2 ガウス・ザイデル法
［Ａ］ガウス・ザイデル法の考え方
ヤコビ法の公式(4.54)の右辺を見ると，総和が２つある。第１の総和は， ｊ＝１からｉ－１であり，第２の総和は，ｊ＝ｉ＋１からｎまでである。 第１の 総和のｘｊ（ｋ）をすでに計算されたｘｊ （ｋ＋１）で置き換えると，最新のｘｊの値を使っている ことになり，収束が早くなることが予想される。すなわち，次のガウス・ザイデル 法（Gauss-Seidel）の公式が得られる。
|
|
|
|
| |
|
［解］第１式をｘについて，第２式をｙについて，解くと次のようになる。
|
［Ｂ］ガウス・ザイデル法のフロー・チャート
ガウス・ザイデル法の公式(4.56)にしたがって，ガウス・ザイデル法の フロー・チャートを図4.38に示した。このガウス・ザイデル法は，つねに最新の ｘｊを使うので，古いｘｊ（ｋ）と新しい ｘｊ（ｋ＋１）の両方を記憶しておく必要がない。した がって，ヤコビ法（図4.37）のように，ｘｏ(j)が必要ないし，ｘ(j)をｘｏ(j)に 入れ換える操作も不要になり，フロー・チャートは簡単になる。
これらの手法はどの場合でも収束するわけではなく、収束するための十分条件
は次の条件を満足することである。すなわち、
係数マトリックスの各行とも、対角要素の絶対値｜ａｉｉ｜が非対
角要素の絶対値の和より大きいことである。
|
(4.57) |
