プログラム演習 (3)Gauss の消去法
Gauss の消去法は一元連立方程式を数値的に解く方法である。
例として、以下の連立方程式を解くことを考えよう。
 a1,1 x + a1,2 ya2,1 x + a2,2 y a x + a y3,13,2+ a1,3 z= d1 ,+ a2,3 z= d2 ,+ a3,3 z=(1)d3Gauss の消去法では、これを以下のように変形することを目指す。

x= d˜1 ,y= d˜2 ,z = d˜(2)3

このように変形することで、元の方程式の解が得られていることが分かるであろう。
まずは、式 (1) の２つ目、３つ目の式から x の項を消去することを考える。この場合、式 (1) の１つ目の式の両辺をa1,1 で割ると便利である。この操作を行うと以下の式が得られる。
a1,3d1a1,2

y +z =,+ x
a1,1a1,1a1,1(3)a2,1 x + a2,2 y + a2,3 z = d2 , a3,1 x + a3,2 y + a3,3 z =d3
そして、２つ目、３つ目の式から x の項を消去するため、２つ目の式からは１つ目の式の両辺に a2,1 を乗じたものを、３つ目の式からは１つ目の式の両辺に a3,1 を乗じたものをそれぞれ引く。







xa2,1 x − a2,1 x a3,1 x − a3,1 xa1,2ya1,1a1,2+ a2,2 y −a2,1 ya1,1a1,2+ a3,2 y −a3,1 ya1,1+a1,3z
a1,1a1,3+ a2,3 z −a2,1 z
a1,1a1,3+ a3,3 z −a3,1 za1,1+d1,a1,1d1= d2 −
a2,1 ,
a1,1d1= d3 −
a3,1a1,1=(4)

ここで、= a2,2 −(5)

a′2,3=(6)d′2=a′3,2=a′3,3=d′3=とおくと、式 (4) は以下のように書き直せる。
 x +


a1,2a2,1 ,a1,1a1,3
a2,3 −
a2,1 ,a1,1d1a2,1 ,d2 −a1,1a1,2a3,2 −
a3,1 ,
a1,1a1,3a3,3 −
a3,1 ,
a1,1d1a3,1d3 −a1,1a′2,2(7)
(8)
(9)
(10)

a1,2ya1,1+

a1,3z
a1,1=d1,
a1,1a′2,2 y+a′2,3 z=

d′2 ,a′3,2 y+a′3,3 z

=d′3

1(11)

次は、２つ目の式に着目する。ここでは、上記の操作を行うことによって３つ目の式から y の項を消去することが目標となる。この場合、はじめに２つ目の式の両辺を a′2,2 で割る操作を行う。
a1,2a1,3d1

x +y +z =,a1,1a1,1a1,1

a′2,3d′2y+z =,′
a2,2a′2,2
a′3,2 y + a′3,3 z =d′3(12)ここで分かるように、この操作は、i 番目の式を対象とした場合、(i, i) の位置にある係数を 1 にする操作と言い換えることができる。
そして、３つ目の式から２つ目の式の両辺に a′3,2 を乗じたものを引く。
a1,3a1,2
y+z=x +
a1,1a1,1

a′2,3z=y+a′2,2


a′2,3


a′3,2 y − a′3,2 y + a′3,3 z − ′ a′3,2 z =a2,2d1,a1,1d′2,a′2,2d′d′3 − ′ 2 a′3,2a2,2(13)ここで、

a′2,3 ′
a ,a′2,2 3,2(14)d′2 ′aa′2,2 3,2(15)a′′3,3= a′3,3 −d′′3= d′3 −とおくと、式 (13) は以下のように書き直せる。
a1,2


x +y

a

1,1
y





a1,3z
a1,1a′2,3z
a′2,2++==a′′3,3 z=

d1,a1,1d′2,a′2,2(16)d′′3

さらに、３つ目の式の両辺を a′′3,3 で割ると、以下のように書き直せる。
a1,2a1,3d1
x +y +z =,a1,1a1,1a1,1′
a2,3d′2z =,y+′a2,2a′2,2

d′′3z=a′′3,3(17)ここまでの過程を前進消去と呼ぶ。
さて、次に、残った（右上に位置する）項を消去していくこととしよう。まず、１つ目、２つ目の式から z の項を消去することを考える。そのために、２つ目の式からは３つ目の式の両辺に a′2,3 /a′2,2 を乗じたものを、１つ目の式からは３つ目の式の両辺に a1,3 /a1,1 を乗じたものを、それぞれ引けばよい。
a1,3a1,3a1,2
y +z−z =x +
a1,1a1,1a1,1

a′2,3a′2,3y+z−z =a′2,2a′2,2z=
この式を整理すると、以下のように書ける。
x
+d1
a1,3 d′′3−,
a1,1
a1,1 a′′3,3
a′2,3 d′′3
d′2−
a′2,2a′2,2 a′′3,3d′′3
a′′3,3

a1,2
y
a1,1

=d′′1 ,y=d′′2 ,d′′3a′′3,3z

2

=(18)

(19)

ここで、

d′′1

=

d1
a1,3 d′′3−,
a1,1
a1,1 a′′3,3

(20)

d′′2

=a′2,3 d′′3
d′2−
a′2,2a′2,2 a′′3,3(21)である。
最後に、x の解を得るために、１つ目の式から２つ目の式の両辺に a1,2 /a1,1 を乗じたものを引く操作を行う。その結果、以下の式が得られる。


 x


= d′′1 − d′′2y

d′′2 ,d′′3a′′3,3=
za1,2,a1,1=(22)

ここまでの過程を後退代入と呼ぶ。
以上の前進消去、後退代入の操作を行うことにより、x、y 、z 全ての解が得られることになる。これが Gauss の消去法の原理である。
式 (1) は行列形式で以下のように書ける。
a1,1
 a2,1a1,2a2,2a3,2a3,1a1,3xd1 a2,3   y  =  d2 a3,3zd3(23)

これまでに述べた Gauss の消去法の手続きはこのような行列形式でも記述することができるが、便宜的に以下のような特殊な表記で示すのが分かりやすい。

a1,1
 a2,1a3,1a1,2a1,3a2,2a3,2a2,3a3,3d1d2 d3(24)

それでは、まず前進消去について、この表記で説明しよう。1 行目を対象とした規格化操作により、式 (24) は以下のように変形される。

1
 a 2,1a3,1a1,2a1,1a2,2a1,3a1,1a2,3


d1a1,1 d2 

a3,2a3,3d3

また、２つ目、３つ目の式から x の項を消去する操作を行うことにより、式 (25) は以下のように変形される。
d1a1,2 a1,31

a1,1 a1,1 a1,1  0 a′a′2,3d′2 
2,20 a′3,2 a′3,3d′3
次に、同様の操作を 2 行目について行うことにより、式 (26) は以下のように書ける。

a1,2 a1,3d11

a1,1 a1,1 a1,1 


a′2,3
d′2 
 0
1

a′2,2 a′2,2 
d′′3 001a′′3,3(25)

(26)

(27)

ここまででが前進消去の過程であり、ここまでの操作により、行列の左部分において、対角成分が 1 で対角成分よりも左下の要素が全てゼロになる。
後退代入については説明は省略するが、最終的には以下のように変形されることになる。
a1,2 1 0 0 d′′1 − d′′2a1,1  0 1 0d′′2

d′′30 0 1a′′3,33(28)縦の線で区切られた左側の行列が単位行列になるまで変形を繰り返していったときの右側のベクトル（行列）が求める
Tべき解 x(= (x, y, z) ) となる。

Gauss の消去法は、逆行列を数値的に求めるために用いることも出来る。
例えば、n × n 行列 A の逆行列を求めるときにはAX = I(29)を満たす X が逆行列になることを利用する（I は単位行列である）。この場合、に対して Gauss の消去法を行う。結果として

(A|I)

(30)

()
I|A−1(31)が得られる。


問題：Ax = b を Gauss の消去法で解き x を求めよ。ここで作成するプログラムは、任意の大きさの行列に対応できるものとする（従って、配列を用いることが必須となる）。なお、
 
1 2 15 
A =  4 5 6 ,b= 4 

189(32)3とする。また、A の逆行列を Gauss の消去法で求めるとともに、行列 A に乗じて単位行列となることを確かめよ。

具体的なプログラミングであるが、行列 A とベクトル b を定義する配列を用意し、Gauss の消去法の手続きに従い、その内容を逐次更新していく、という流れとなるであろう。
まずは前進消去によって、式 (27) のような形に変形を行うことを目指し、その後、後退代入によって式 (28) のような形に変形することを目指す。
前進消去は第 1 行から順次行うことになるので、ループを組むことになるだろう。また、前進消去における各行での操作は、（対角成分を 1 とするような）規格化と、着目行よりも下に位置する行の簡易化の２つの段階に分けられる。後退代入は、逆に一番下の行から順次行う。ここでも前進消去と同様にループを組むことになるだろう。

4