連立方程式の解法１ 掃き出し法

連立方程式の解法１　掃き出し法

 

次の連立３元方程式を例に、数値計算で用いられる、連立方程式を解くための掃き出し法――中学で習う連立方程式の解法の一つである、加減法とほとんど同じもの――について説明する。

　　

まず、係数だけを取り出し、次のような表（行列）を作る。

　　

①に1/2を掛けて、xの係数を1にする。

　　

次に、②、③のxの係数を0にするために、②−5×①’、③−３×①’を計算する。

　　

②の係数を１にするために、②’に−2/11を掛ける。

　　

①’と③’のyの係数を０にするために、

①’−3/2×②’’、③’−1/2×②’’を計算する。

　　

③’’のzの係数を１にするために、
③’’×11/94を計算する。

　　

①’’と②’’のzの係数を０にするために、

①’’−7/11×③’’’、②’’+1/11×③’’’を計算する。

　　

①’’’、②’’’、③’’’を連立方程式の形に書き換えると、

　　

だから、この連立方程式の解は(x,y,z)=(1,1,0)である。

 

要するに、連立方程式

　　

の係数行列を

　　

を単位行列

　　

に変形することによって連立方程式の解(x,y,z)を求める方法を掃き出し法という。

 

連立３元方程式だと書くのが大変なので、次の連立２元方程式を掃き出し法で、もう一度、解くことにする。

　　

係数だけを取り出すと次のようになる。

　　

①×1/2

　　

②−３×①’

　　

(-2/25)×②’

　　

①’−7/2×②’’

　　

よって求める解は

　　

 

この作業をコンピュータにさせるためにプログラムを書くことは大変そうだけど、実は、簡単に書けてしまう。

Fortranによるサンプルプログラムを以下に示す。

 

! 掃き出し法で連立方程式を解く

real a(50,51)

 

! sample data

a(1,1)=2; a(1,2)=3; a(1,3)=1; a(1,4)=4

a(2,1)=4; a(2,2)=1; a(2,3)=-3; a(2,4)=-2

a(3,1)=-1; a(3,2)=2; a(3,3)=2; a(3,4)=2

 

n=3 ! ３元連立方程式だからn=3

 

call hakidashi(a,n) ! 掃き出し法を呼び出す

 

do i=1, n

  write(6,100) 'x(',i,')=', a(i,n+1)

end do

100 format(a,i2, a,f10.6)

end

 

! 掃き出し法

subroutine hakidashi(a,n)

real a(50,51)

 

do k =1, n

   p= a(k,k)

   do j=k+1, n+1

     a(k,j)= a(k,j)/p

   end do

   do i=1, n

      if (i.ne.k) then

        do j=k+1, n+1

          a(i,j)=a(i,j)-a(i,k)*a(k,j)

        end do

      end if

    end do

end do

 

end

 

解いているのは、次の連立方程式。

　　

上のプログラムは、より一般の

　　

すなわち、

　　

も解けるようになっている。

 

プログラム使用上の注意は、をに格納し、サブルーティンhakidashiを呼び出し後には、解がに格納されていること。

これは、連立方程式（１）を

　　

という行列に置き換え、この行列の操作によって連立方程式の解を求めているためで、この行列のn+1列目を

　　

としているためである。

 

上のプログラムを見るとわかると思うけれど、n元連立１次方程式を解くための反復計算の回数は、３重（do）ループになっているので、およそ、n³/2回。

したがって、nが１０倍になると、反復回数は10³、すなわち１０００倍になり、この計算に要する時間もおよそ１０００倍になる。

nが１００倍になると、なんと、１００³=１００万倍！！

このため、単純計算を超高速で行えるコンピュータといえども、多元連立１次方程式を解くということは大変な手間のかかる作業なのであった。