Web教材一覧数値解析
(BOK大区分:1 基礎理論、中区分:2 アルゴリズムとプログラミング、中区分:2 アルゴリズム)

連立一次方程式

キーワード

数値解析、連立一次方程式、ガウスの消去法


連立一次方程式
   a111+a122+・・・+a1n1=b1
   a211+a222+・・・+a2nn=b2
     :   :       :  :
   an11+an22+・・・+annn=bn

を解く代表的な方法に、ガウスの消去法があります。

数値例:連立一次方程式の解法の復習

次の連立一次方程式を例にしましょう。
   2x+4y   =10  ・・・A
   3x+ y+5z=20  ・・・B
      3y+2z=12  ・・・C
●ステップ1
Aを、xの係数2で割る。
    x+2y   = 5  ・・・A(1)
Bから、A(1)にxの係数3をかけたものを引く。
   3x+ y+5z=20
 -)3x+6y   =15
     -5y+5z= 5
Cから、A(1)にxの係数0をかけたものを引く(実際にはCのまま)。
      3y+2z=12
ここまでで、A、B、Cは次のようになりました。
    x+2y   = 5  ・・・A(1)
     -5y+5z= 5  ・・・B(1)
      3y+2z=12  ・・・C(1)
●ステップ2
Bを、yの係数(-5)で割る。
       y- z=-1  ・・・B(2)
Aから、B(2)にyの係数2をかけたものを引く。
    x   +2z= 7)
Cから、B(2)にyの係数3をかけたものを引く。
         5z= 5
ここまでで、A、B、Cは次のようになりました。
    x   +2z= 7  ・・・A(2)
       y- z=-1  ・・・B(2)
         5z=15  ・・・C(2)
●ステップ3
Cを、zの係数5で割る。
          z= 3  ・・・C(3)
Aから、C(2)にzの係数2をかけたものを引く。
    x      = 1
Bから、C(2)にzの係数(-1)をかけたものを引く。
    x      = 1
       y   = 2
この結果、次の解が得られました。
    x      = 1  ・・・A(3)
       y   = 2  ・・・B(3)
          z= 3  ・・・C(3)

xをx1、yをx2、zを3とし、Aを式1、Bを式2、Cを式3と番号をつければ、ステップiで、変数i、式iが特別な処理になっていることに注意してください。

計算表による整理

上の計算は、次の表にまとめることができます。

     ─────────────
      1  2  3   4
      x  y  z   b
ステップ0─────────────
  1   2  4  0  10
  2   3  1  5  20
  3   0  3  2  12
ステップ1─────────────
  1   1  2  0   5
  2   0 -5  5   5
  3   0  3  2  12
ステップ2─────────────
  1   1  0  2   7
  2   0  1 -1  -1
  3   0  0  5  15
ステップ3─────────────
  1   1  0  0   1
  2   0  1  0   2
  3   0  0  1   3
     ─────────────

アルゴリズム

例えば、ステップ1の表は、次の式で計算できます。
ステップ1の値   ステップ0の値
(1,1)の 1:(1,1)/(1,1)=2/2=1
(1,2)の 2:(1,2)/(1,1)=4/2=2
(1,3)の 0:(1,3)/(1,1)=0/2=0
(1,4)の10:(1,4)/(1,1)=10/2=5
(2,1)の 0:(2,1)-(2,1)*(1,1)/(1,1)= 3-3×2/2= 0
(2,2)の-5:(2,2)-(2,1)*(1,2)/(1,1)= 1-3×4/2=-5
(2,3)の 5:(2,3)-(2,1)*(1,3)/(1,1)= 5-3×0/2= 5
(2,4)の 5:(2,4)-(2,1)*(1,4)/(1,1)=20-3×10/2= 5
(3,1)の 0:(3,1)-(3,1)*(1,1)/(1,1)= 0-0×2/2= 0
(3,2)の 0:(3,2)-(3,1)*(1,2)/(1,1)= 3-0×4/2= 3
(3,3)の 5:(3,3)-(3,1)*(1,3)/(1,1)= 2-0×0/2= 2
(3,4)の12:(3,4)-(3,1)*(1,4)/(1,1)=12-0×10/2=12

ステップ3の値は、ステップ2の値を用いて同様に計算できます。

この関係を一般化すれば、ステップkからステップk+1への変化は、
   aij=aij/akk       (i=kのとき)
     =aij-aik×akj/akk (i≠kのとき)

と表現できます。
 なお、この akkピボットといいます。

上記のアルゴリズムは、次の問題では、ピボット(対角線の要素)が0になり計算できません。
      3y+2z=12
   2x+4y   =10
   3x+ y+5z=20
ピボットが0でなくても、
   εx+3y+2z=12   ε=0.000001
   2x+4y   =10
   3x+ y+5z=20

のような場合には、誤差が生じてしまいます。

それを避けるために、ステップのたびに、ピボットになる変数の絶対値が最大になるように、式の順序を入れ替えることが必要になります。


計算プログラム

変数(式)の個数n=
定数項12345

数値解析へ