Gauss-Jordanの消去法

連立1次方程式の数値解
例
4 x1  2 x2  16

2 x1  8 x2  22
4 x1  2 x2  16

2 x1  8 x2  22
2 x1  x2  8

　x2  2
2 x1  x2  8

2 x1  8 x2  22
2 x1  2  8

　x2  2
2 x1  x2  8

　7 x2  14
　x1  3

　x2  2
nｘn 連立1次方程式
a11x1  a12 x2  a13 x3      a1n xn  b1
a x  a x  a x      a x  b
23 3
2n n
2
 21 1 22 2
a31x1  a32 x2  a33 x3      a3n xn  b3






an1 x1  an 2 x2  an 3 x3      ann xn  bn
n
a x
j 1
ij
j
 bi
i  1,2,3,  , n
a11x1  a12 x2  a13 x3      a1n xn  b1
行列とベクトル記号で表す 
a21x1  a22 x2  a23 x3      a2 n xn  b2

連立1次方程式 
a31x1  a32 x2  a33 x3      a3n xn  b3






an1 x1  an 2 x2  an 3 x3      ann xn  bn
AX  b
 a11 a12

a21 a22
A   a31 a32


 
a
 n1 an 2
a13    a1n 

a23    a2 n 
a33    a3n 

   
an3    ann 
 x1 
 
 x2 
X   x3 
 

 xn 
 b1 
 
b2 
b  b3 
 

bn 
A：係数行列； X：未知数ベクトル；ｂ：定数ベクトル
連立1次方程式
AX  b
 a11 a12

a21 a22
A   a31 a32


 
a
 n1 an 2
a13    a1n 

a23    a2 n 
a33    a3n 

   
an3    ann 
1
XA b
 x1 
 
 x2 
X   x3 
 

 xn 
 b1 
 
b2 
b  b3 
 

bn 
A：係数行列； X：未知数ベクトル；ｂ：定数ベクトル
連立1次方程式
AX  b
1
XA b
A-1：係数行列Aの逆行列
1
A AI
1

0
I  0


0

0 0    0

1 0    0
0 1    0

   
0 0    1
連立1次方程式
１．直接法
•
Gauss-Jordanの消去法
•
LU分解法
2．反復法
•
ヤコビ（Jacobi）法
•
ガウス―ザイデル（Guass-Seidel) 法
•
SOR法（逐次緩和法）
•
収束条件・終了判定
Gauss-Jordanの消去法
4 x1  2 x2  16

2 x1  8 x2  22
1

 x1  x2  4
2

2 x1  8 x2  22

1

 x1  x2  4
2

　7 x2  14

1

 x1  x2  4
2

　x2  2

1

 x1  4   2
2

　x2  2

　x1  3

　x2  2
Gauss-Jordanの消去法
4 x1  2 x2  16

2 x1  8 x2  22
1

 x1  x2  4
2

2 x1  8 x2  22

1

 x1  x2  4
2

　7 x2  14

連立方程式の性質：
1. 方程式の両辺に０でない数を
掛けたり、割ったりしても
2. ある方程式を他の方程式に加
えたり、引いたりしても
その連立方程式の解が変わらない。
消去法はこれらの性質を利用して、
連立方程式の係数を次々に消
去して、解の求めやすい形に
する。
Gauss-Jordanの消去法の手順
AX  b
１．Aの拡大行列を作る
 a11 a12

 a21 a22
ˆ  a
A
a32
31

 


 an1 an 2
ain1  bi
a13    a1n
a23    a2 n
a33    a3n

an3
 
   ann
a1n 1 

a2 n 1 
a3n 1 

 

ann1 
i  1,2,3,  , n
２．行列を変形する
正規化
 1 a12 a11 a13 a11

a22
a23
 a21
ˆ  a
A
a32
a33
 31
 



an 2
an3
 an1
①
1

0

ˆ
A  0


0

(1)
a12
(1)
a13
   a1(1n)
(1)
a22
(1)
a32
(1)
a23
(1)
a33


an(12)
an(13)

a2(1n)
a3(1n)

 
(1)
   ann
   a1n a11 a1n 1 a11 


a2n
a2n 1 

a3n
a3n 1 







ann
ann1 
a1(1n)1 
a2(1n)1 
(1) 
a3n 1 
 
(1) 
ann
1 
(1)
1j
a
 a1 j a11
aij(1)  aij  ai1  a1(1j)
i  2,3,  , n
j  1,2,  , n  1
②
1

0

ˆ
A  0


0

( 2)
2j
a
( 2)
ij
a
a
(1)
2j
( 2)
0 a13
   a1(n2)
( 2)
1 a23
   a2( 2n)
0



 
( 2)
( 2)
0 an3    ann
( 2)
a33
( 2)
a3n
(1)
22
a
 a a a
(1)
ij
(1)
i2
( 2)
2j
a1(n2) 1 
a2( 2n)1 
( 2) 
a3n 1 
 
( 2) 
ann1 
i  1,3,  , n
j  1,2,3,  , n  1
i2
３．単位行列を作って、解を求める
1

0

ˆ
A  0


0

ｎ
(k )
kj
a
(k )
ij
a
a1(nn) 1 
   0 a2( nn)1 
(n) 
   0 a3n 1 
 
 
(n) 
   1 ann
1 
0 0  0
方程式の解
1 0
xi  a
0 1
 
0 0
( k 1)
kj
( k 1)
kk
a
( k 1)
ij
a
a
i  1,2,, n
k  1,2,3,, n
a
( k 1)
ik
(n)
in1
i  1,2,3,, n　(i  k )
a
(k )
kj
j  k , k  1, k  2,, n  1
実用的な消去法
1

0

ˆ
A  0


0

(1)
a12
(1)
a22
(1)
a32
(1)
a13
(1)
a23
(1)
a33


an(12)
an(13)
1

0

ˆ
A  0


0

(1)
a12

1
(1)
a13
( 2)
a23
0

0
1

0





a1(1n)
a2(1n)
a3(1n)

 
(1)
   ann

a1(1n)1 
a2(1n)1 
(1) 
a3n 1 


(1) 
ann1 

a1(1n)
a2( 2n)
a3(3n)
a1(1n)1 
a2( 2n)1 
(3) 
a3n 1 

1



( n) 
ann1 
上三角行列にする
 1 a (1)
12

0 1

ˆ
A  0 0



0 0

(k )
kj
a
(1)
a13
   a1(1n)
( 2)
   a2( 2n)
a23
( 2)
   a3( 2n)
a33
 

( 2)
an( 23)    ann
( k 1)
kj
a
a1(1n)1 
a2( 2n)1 
( 2) 
a3n 1 
 
( 2) 
ann
1 
( k 1)
kk
a
aij( k )  aij( k 1)  aik( k 1)  akj( k )
k  1,2,3,, n
i  k  1, k  2,, n
j  k , k  1, k  2,, n  1
 1 a (1)
12

0 1

ˆ
A  0 0



0 0

(1)
a13
   a1(1n)
( 2)
a23
   a2( 2n)
   a3(3n)
 
 1
1

0
a1(1n)1 
a2( 2n)1 
(3) 
a3n 1 
 
( n) 
ann1 
方程式の解
n
(i )
xi  ain1 

(i )
aij x j
j i 1
i  n, n  1, n  2,,3,2,1
応用例：逆行列の計算
 a11 a12 a13

ˆ
A   a21 a22 a23
a
 31 a32 a33
1 0 0

0 1 0
0 0 1
消
去
法
1 0 0

ˆ  0 1 0
A
0 0 1

b11 b12 b13 

b21 b22 b23 
b31 b32 b33 
 a11 a12 a13 


A   a21 a22 a23 
a

a
a
 31 32 33 
 b11 b12 b13 

1 
A   b21 b22 b23 
b

b
b
 31 32 33 
AA 1  I
1 0 0


I   0 1 0
0 0 1


消去法の注意点
演算の途中でakk
が０になったとき、
適当な行または列
同士の入れ換えを
行って、０でない
要素をピボットに
選んで、掃出すこ
とが必要である。
akk ：ピボット（対
角線上の要素）
 1 a (1)
12

0 1

ˆ
A  0 0



0 0

(k )
kj
a
(k )
ij
a
(1)
a13
   a1(1n)
( 2)
a23
   a2( 2n)
1

0
   a3(3n)
 
 1
( k 1)
kj
a
( k 1)
ij
a
a1(1n)1 
a2( 2n)1 
(3) 
a3n 1 
 
( n) 
ann
1 
( k 1)
kk
a
( k 1)
ik
a
a
(k )
kj
k  1,2,3,, n
i  k  1, k  2,, n
j  k , k  1, k  2,, n  1
ガウス消去法の利点
1. 必ず収束で、繰り返し回数≦方程式の元数ｎ。
2. 手順が簡単、計算量が少ない。
3. 多少性質が悪い係数行列にも適用可能。
ガウス消去法の欠点
1. 正規化によって丸め誤差が生じる。
2. 消去の途中の減算によって桁落ちが生じる。
3. 乗算回数が多くなって誤差の累積する可能性がある。
4. 元の係数行列が破壊してしまう。
LU分解法
AX  b
下三角行列
0
0
 1

0
 21 1
L   31  32 1



 

 n1  n 2  n3
A  LU
LUX  b
上三角行列
   0
 11 12


   0
 0  22
   0 U   0
0


 

 
 0
   1
0

13    1n 
 23     2 n 
 33     3n 

0

  
    nn 
0
0
 1

0
 21 1
L   31  32 1



 

 n1  n 2  n3
LUX  b
UX  Y
   0
 11 12


   0
 0  22
   0 U   0
0


 

 
 0
   1
0

13    1n 
 23     2 n 
 33     3n 

0

  
    nn 
n


1 

xi 
yi 
 ij x j 

 ii 

j

i

1


i  n, n  1, n  2,,3,2,1

i 1
LY  b
yi  bi 

j 1
i  1,2,3,, n
ij y j
AのLU分解
0
0
 1

0
 21 1
L   31  32 1



 

 n1  n 2  n3
   0

   0
   0

 
   1

0
ij  aij 

  
    nn 

ik  kj
k 1
n

13    1n 
 23     2 n 
 33     3n 
i 1
A  LU
 ik  kj  aij
 11 12

 0  22
U 0
0


 
 0
0

(i , j 1, 2,n )
k 1
方程式の数：ｎｘｎ
未知数の数：ｎｘｎ
j 1


1 

 ij 
a



ij
ik kj 
 jj 

k

1


j  1,2,3,, n
i  j  1, j  2,, n

LUの保存
0
0
 1

0
 21 1
L   31  32
1



 

 n1  n 2  n3
 11 12

 0  22
U 0
0


 
 0
0

   0

   0
   0

 
   1
 11

 21
 31

 

 n1
i  j  1, j  2,, n
12 13    1n 
 22  23     2 n 
 32  33     3n 


 n 2  n3

  
    nn 
13    1n 
 23     2 n 
 33     3n 

0

  
    nn 
連立1次方程式・反復法
a11x1  a12 x2  a13 x3      a1n xn  b1
a x  a x  a x      a x  b
23 3
2n n
2
 21 1 22 2
a31x1  a32 x2  a33 x3      a3n xn  b3






an1 x1  an 2 x2  an 3 x3      ann xn  bn
n
a x
j 1
ij
j
 bi
i  1,2,3,  , n
ヤコビ法（Jacobi)
a11x1  a12 x2  a13 x3      a1n xn  b1
a x  a x  a x      a x  b
23 3
2n n
2
 21 1 22 2
a31x1  a32 x2  a33 x3      a3n xn  b3






an1 x1  an 2 x2  an 3 x3      ann xn  bn
1
 ( k 1)
x

(b1  a12 x2( k )    a1n xn( k ) )
 1
a11

 ( k 1)
1
x

(b2  a21x1( k )    a2n xn( k ) )
 2
a22






1
 ( k 1)
(k )
(k )
x

(
b

a
x



a
x
n
n
n
1
nn

1

1
n 1 )
ann

Jacobiの反復計算式
( k 1)
i
x
i 1
n
1
(k )
(k )
 (bi   aij x j   aij x j )
aii
j 1
j i 1
i  1,2,3,, n
ガウス・ザイデル法（ Gauss・Seidel)
a11x1  a12 x2  a13 x3      a1n xn  b1
a x  a x  a x      a x  b
23 3
2n n
2
 21 1 22 2
a31x1  a32 x2  a33 x3      a3n xn  b3






an1 x1  an 2 x2  an 3 x3      ann xn  bn
1
 ( k 1)
x

(b1  a12 x2( k )    a1n xn( k ) )
 1
a11

 ( k 1)
1
x

(b2  a21x1( k 1)    a2 n xn( k ) )
 2
a22






1
 ( k 1)
( k 1)
(k )
x

(
b

a
x



a
x
n
n
n
1
nn

1

1
n 1 )
ann

Gauss・Seidelの反復計算式
xi( k 1)
1

(bi 
aii
i  1,2,3,, n
i 1

j 1
aij x(jk 1) 
n

aij x(jk ) )
j i 1
SOR法（逐次緩和法)
 ( k 1)

 xˆ1

 ( k 1)

 xˆ2



  ( k 1)

 xn

a11x1  a12 x2  a13 x3      a1n xn  b1
a x  a x  a x      a x  b
23 3
2n n
2
 21 1 22 2
a31x1  a32 x2  a33 x3      a3n xn  b3






an1 x1  an 2 x2  an 3 x3      ann xn  bn
1
(b1  a12 x2( k )    a1n xn( k ) )
a11
1
(b2  a21x1( k 1)    a2n xn( k ) )
a22



1
(bn  an1x1( k 1)    ann1xn( k)1 )
ann
SORの反復計算式
xˆi( k 1) 
1
(bi 
aii
i 1

j 1

 x 　aij x(jk 1) 

xi(k 1)  xi(k )  SOR * xˆi(k 1)
n
aij x(jk ) )
i  1,2,3,, n
j i 1
(k )
i
SOR  0.5 ~ 1.5
小行列によるSOR法
小行列
a11x1  a12 x2  a13x3  a14 x4      a1n xn  b1

a22 x2  a23x312
 a24 x4      a2n xn  b2
a21x1 11
a31x1  a32 x2  a33x3  a34 x4      a3n xn  b3

a42 x2  a43x3 12
a44 x4      a4n xn  b4
a41x1 21






an1x1  an 2 x2  an3 x3  an 4 x4      ann xn  bn
D
U
L
D
 a11 a12

a21 a22
A   a31 a32


 
a
 n1 an 2
a13    a1n 

a23    a2 n 
a33    a3n 

   
an3    ann 
Lij Dij U ij
k k
k k
k k
n  km
 D11 U12

 L 21 D22
A   L31 L32


 
L
 m1 L m 2
U13    U1m 

U 23    U 2 m 
D33    U3m 



 
L m3    Dmm 
A  LDU
 D11 U12

 L 21 D22
A   L31 L32


 
L
 m1 L m 2
D11 0

 0 D22
D 0
0


 
 0
0

U13    U1m 

U 23    U 2 m 
D33    U3m 



 
L m3    Dmm 
0 
0 
D33   

0






 
   Dmm 
0
0
0
0
 0

0
 L 21
L   L31 L32


 
L
 m1 L m 2
0
0
0

L m3
0 U12 U13

0 0 U 23
U  0 0
0




0 0
0

   0

   0
   0

 
   0
   U1m 

   U 2m 
   U 3m 


 

0 
小行列によるSOR法の計算式
 D11 U12

 L 21 D22
A   L31 L32


 
L
 m1 L m 2
U13    U1m 

U 23    U 2 m 
D33    U3m 



 
L m3    Dmm 
 x1 
 
 x2 
X   x3 
  
 
x m 
AX  b
 b1 
 
 b2 
b   b3 
  
 
b m 
SORの反復計算式
xˆ i( k 1)


 Dii1 bi 




Lij x(jk 1) 
Uij x(jk ) 

j 1
j i 1

i 1
m




i  1,2,3,, m
xi(k 1)  xi(k )  SOR * xˆ i(k 1)  xi(k ) SOR  0.5 ~ 1.5
SOR法（逐次緩和法)の計算式
要素によるSORの反復計算式
xˆi( k 1)
1

(bi 
aii
i 1


 x 　aij x(jk 1) 
j 1

xi(k 1)  xi(k )  SOR * xˆi(k 1)
n
aij x(jk ) )
i  1,2,3,, n
j i 1
(k )
i
SOR  0.5 ~ 1.5
小行列によるSORの反復計算式
xˆ i( k 1)


 Dii1 bi 




Lij x(jk 1) 
Uij x(jk ) 

j 1
j i 1

i 1
m




i  1,2,3,, m
xi(k 1)  xi(k )  SOR * xˆ i(k 1)  xi(k ) SOR  0.5 ~ 1.5
反復法の収束条件
n
aii 
a
ij
i  1,2,, n
j 1
j i
反復法の終了判定

① max xi( k 1)  xi( k )
②
1
n
n

i 1
xi( k 1)

xi( k )


i  1,2,, n  
1
③
n
n

i 1
xi( k 1)  xi( k )
xi( k )

反復法の利点
1. 大次元の連立方程式を解くときによく利用される。
2. 要素に０を含んだ係数行列をもつ連立方程式では演
算回数が減る。
反復法の欠点
1. 収束条件を満たす行列のみで、適用範囲が限定され
ている。
2. 反復演算による誤差が生じやすい。
演習問題
１．次の連立1次方程式をガウス・ジョルダン
（Gauss-Jordan）の消去法で解け。
2 x1  x2  x3  2
2 x1  3x2  x3  4
x1  x2  3x3  1
２．上の連立1次方程式をSOR反復法で解け。ただし
SOR=1.3
収束判定：
1
n
n

i 1
xi( k 1)  xi( k ) 0.001

Download Report