数値計算法

数値計算及び実習
第11回応用プログラミング(3)
応用プログラミング(3)
1. 連立方程式の解法
・ガウス-ジョルダン法
ガウス-ジョルダン法
• 連立一次方程式の解法の１つ
a11X1+a12X2+ … a1nXn=b1
a21X1+a22X2+ … a2nXn=b2
………………………...
an1X1+an2X2+ … annXn=bn
 a 11
a
A   21
 ...

a n1
a 12
a 22
...
a n2
... a 1n 
... a 2 n 
... ... 

... a nn 
AX=B
 b1 
b 
B   1

 
b n 
 X1 
X 
2

X
  
 
X n 
解法
• BをAのn+1行列目に書き足して得られる
拡大行列Ae
• Aeが右のような行列になるような操作を行
い、そのときのb1’,b2’…,bn’が解となる
 a11 a12
a
a 22
21

Ae 
 ... ...

 a n1 a n 2
... a1n b1 

... a 2 n b 2 
... ... ... 

... a nn b n 
1
0

...

0
0
1
...
0
...
...
...
...
0 b1' 
0 b 2' 
... ... 

1 bn' 
計算の手順(1)
第1ステップ
2X+3Y+ 4Z= 6 ①
3X+5Y+ 2Z= 5 ②
4X+3Y+30Z=32 ③
2 3 4 6 
3 5 2 5 


 4 3 30 32 
①×0.5 →①’
②－①’×3 →②’
③－①’×4 →③’
X+1.5Y+ 2Z= 3 ①’
0.5Y－4Z=－5 ②’
－3Y+22Z= 20 ③’
3 
 1 1.5 2
 0 0.5  4  5 


 0  3 22 20 
計算の手順(2)
第2ステップ
X+1.5Y+ 2Z= 3 ①’
0.5Y－4Z=－4 ②’
－3Y+22Z= 20 ③’
3 
 1 1 .5 2
 0 0 .5  4  4 


 0  3 22 20 
②’×2 →②”
①’－②”×1.5 →①”
③－②” ×(－3) →③”
X
+14Z= 15 ①”
Y－8Z=－8 ②”
－2Z=－4 ③”
 1 0 14 15 
 0 1 8 8 


 0 0  2  4 
計算の手順(3)
第3ステップ
X
+14Z= 15 ①”
Y－8Z=－8 ②”
－2Z=－4 ③”
 1 0 14 15 
 0 1 8 8 


 0 0  2  4 
③”×(－0.5) →③”’
①” －③”’×14 →① ”’
②” －③”’×(－8) →②”’
X
Y
=－13 ①”’
= 8 ②”’
Z= 2 ③”’
 1 0 0  13 
0 1 0 8 


 0 0 1 2 
解法のまとめ
a
a
(k)
ij
(k)
ij

a
a
a
(k 1)
kj
(k 1)
kk
(k 1)
ij
(i=k)

a
(k 1) (k 1)
ik
kj
(k 1)
kk
a
a
 a ij(k 1)  a ik(k 1) a (k)
kj
Xi  a
(n)
i n 1
 a11 a12
a
a 22
21

Ae 
 ... ...

 a n1 a n 2
... a1n b1 
... a 2 n b 2 
... ... ... 

... a nn b n 
i=1,2,…,n
j=k,k+1,…,n+1
(i=k)
k : 第kステップ
解法における注意事項
• 拡大行列Aeに含まれる要素を、その行に
含まれる対角要素で割るとき、その除数と
なる要素をピボットという
• 解法から明らかなように、ピボットがゼロに
なると、以後の操作ができなくなる
• 操作の過程で、行と行あるいは列と列を交
換してなるべく大きなピボットを採用するよ
うにする → ピボット選択
ピボット選択の例
以下の連立1次方程式について、以下の2つの解法
により得られる解の比較を行う
1)ピボットの選択をしない
2)行交換を行う
4 x1 
2 x2  x3  11
3x1  1.500001x2  2 x3  12.000002
5 x1 
x2  3x3  16
1)ピボットの交換を行わない場合
2
1
11
4

 3 1.500001 2 12.000002


 5

1
3
16
0.5
0.25
2.75 
1
 0 0.000001 1.25 3.750002


 0
 1.5
1.75
2.25 
 1 0  6.2499975105

6
0
1
1
.
25

10

 0 0 1.8750018106

 1.874998310 
6 
3.75000210 
5.6250053106 
 1 0 0 0.888 
 0 1 1 2.125 


 0 0 0 2.99999
6
2)行交換を行った場合
2
1
11
4

 3 1.500001 2 12.000002


 5

1
3
16
入れ替え
1
3
16
5

 3 1.500001 2 12.000002


 4

2
1
11
0.2
0.6
3.2 
1
 0 0.900001 0.2 2.400002


 0
1.2
 1.4
 1.8 
入れ替え
0.2
0.6
3.2 
1
0

1
.
2

1
.
4

1
.
8


 0 0.900001 0.2 2.400002
3.5
 1 0 0.8333333

 0 1  1.166666

 1.5 

 0 0 1.2500012 3.7500035
 1 0 0 1.0000001
 0 1 0 2.0000000


 0 0 1 2.9999999
※解は x1＝1,
x2=2,
x3=3

Download Report