n個の変数を含む以下のn元連立一次方程式の解法を考える。
これを行列表示すると、
A=
a11 a12 a13 ! ! ! ! a1n a21 a22 a23 ! ! ! ! a2n
! ! ! ! !
! ! ! ! !
an1 an2 an3 ! ! ! ! ann
"
#
$$
$$
$$
$
%
&
'' ''
''
'
⋅
= ⋅
xn
x x x
2 1
⋅
⋅
=
bn
b b b
2 1
Ax=b
1. クラメールの公式
Aが正則(detA ≠0)でA-1が存在する)の時 x = A-1b
A
xj = Aj (j = 1, 2, ..., n)
|Aj|: Aでその第j列とbとを交換して得られる行列Ajの行列式
解法例:以下の二元連立一次方程式をクラメールの公式を使って解く。
8 5 2
10 4
3
2 1
2 1
= +
= +
x x
x x
= 5 2
4 A 3
=
2 1
x
x x
= 8
b 10
=
5 8
4 10
A1
=
8 2
10 3 A2
x1 = |A1|/|A| = 18/7 = 2.5714 x2 = |A2|/|A|= 4/7 = 0.5714
問題点:数学的には完璧でも、Aの次数が大きくなるにつれ必要な乗除算の数が
非常に多くなっていく。
a11x1+a12x2+a13x3+!!!+a1nxn=b1 a21x1+a22x2+a23x3+!!!+a2nxn=b2
!
!
an1x1+an2x2+an3x3+!!!+annxn=bn
2. 数値計算の工夫
直接法:一定の手順を一回行うだけで解を求める。元の数が小さい時に適す。
例:ガウスの消去法(掃き出し法、LU分解)
反復法:ある初期値から出発して繰り返し演算を行い、ある精度に達した値を 近似解とする。
元の数が大きく(10000≦)かつ係数行列が疎行列の時、特に有効。
例:ヤコビ法、ガウス・ザイデル法
【ガウスの消去法】
行を交換しても、また、ある行に他の行の定数倍を加えても、連立方程式としては
変わらないことに基づき、係数行列Aと、定数ベクトルbを変形していき解を求
める。
解法例:以下の二元連立一次方程式をガウスの消去法を使って解く。
1 2 3
5 4
2 1
2 1
= +
= +
x x
x x
= 2 3
1 A 4
=
2 1
x
x x
= 1
b 5
=
1 2 3
5 1 ) 4
,
(Ab
②
①
拡大係数行列 (A, b) のAの部分が単位行列になるまで、変形を繰り返す。
Step 1.
④ ③
③
②
4
①
× −
−
÷
75 . 2 25 . 1 0
25 . 1 25 . 0 1 3 Step 2.
⑤ ⑥
④
⑤
③
÷ −
×
−
2 . 2 1 0
8 . 1 0 1 25
. 1
25 . 0
ここで、解が求まり、x1 = 1.8 x2 = -2.2 となる。
【ヤコビ法】
係数行列Aを対角成分のみからなる行列Dと、それ以外の成分からなる行列G
とに分解する。
A = D + G
=
ann
a a a D
0 0 0
0 0
0
0 0
0
0 0
0
33 22 11
=
0 0
0 0
3 2 1
3 32
31
2 23
21
1 13
12
n n n
n n n
a a a
a a
a
a a
a
a a
a G
(D + G)x = b Dx = b – Gx
左からD-1をかけると D-1Dx = x = D-1(b – Gx)
これを漸化式と考え、x(k+1) = D-1(b – Gx(k)) があるベクトルαに収束する場合を 近似解ベクトルとする。
成分で表すと
)
1 ( ( )
1 1
1 ) ( )
1
( k
j n
i j
ij i
j k j ij i
ii k
i b a x a x
x a
∑ ∑
+
=
−
=
+ = − − (1)
例: 二元連立一次方程式 (n = 2の場合)
2 2 22 1 21
1 2 12 1 11
b x a x a
b x a x a
= +
=
+
解の漸化式は
) 1 (
) 1 (
) ( 1 21 2 22 ) 1 ( 2
) ( 2 12 1 11 ) 1 ( 1
k k
k k
x a a b
x
x a a b
x
−
=
−
=
+ +
*これらは与えられた方程式をx1とx2について解いた形
三元連立一次方程式 (n = 3の場合)
3 3 33 2 32 1 31
2 3 23 2 22 1 21
1 3 13 2 12 1 11
b x a x a x a
b x a x a x a
b x a x a x a
= +
+
= +
+
= +
+
解の漸化式は
)) (
1 (
)) (
1 (
)) (
1 (
) ( 2 32 ) ( 1 31 3 33 ) 1 ( 3
) ( 3 23 ) ( 1 21 2 22 ) 1 ( 2
) ( 3 13 ) ( 2 12 1 11 ) 1 ( 1
k k
k
k k
k
k k
k
x a x a a b
x
x a x a a b
x
x a x a a b
x
+
−
=
+
−
=
+
−
=
+ + +
【ガウス・ザイデル法】
ヤコビ法でのGを更にE(下三角行列)とF(上三角行列)とに分解すると
Ax = b (D + E + F)x = b Dx + (E + F)x = b Dx = b – (E + F)x
左からD -1をかけると x = D -1 (b –Ex - Fx)
そして、漸化式はx(k+1) = D-1(b – Ex(k+1) – Fx(k))とする。
この成分表示は式(2)で表される。つまり、式(1)で波線の項は、xj(j=1 to i-1)に関 する項で xiより先に求められているはずなので、前回の値(k番目)ではなく、
最新の値(k+1番目)を使う。
)
1 ( ( )
1 1
1
) 1 ( )
1
( k
j n
i j
ij i
j
k j ij i
ii k
i b a x a x
x a
∑ ∑
+
=
−
= +
+ = − − (2)
このため、ガウス・ザイデル法の方がヤコビ法より収束が速い。
例: 二元連立一次方程式 (n = 2の場合)
解の漸化式は
) 1 (
) 1 (
) 1 ( 1 21 2 22 ) 1 ( 2
) ( 2 12 1 11 ) 1 ( 1
+ +
+
−
=
−
=
k k
k k
x a a b
x
x a a b
x
三元連立一次方程式 (n = 3の場合)、解の漸化式は
)) (
1 (
)) (
1 (
)) (
1 (
) 1 ( 2 32 ) 1 ( 1 31 3 33 ) 1 ( 3
) ( 3 23 ) 1 ( 1 21 2 22 ) 1 ( 2
) ( 3 13 ) ( 2 12 1 11 ) 1 ( 1
+ +
+
+ +
+
+
−
=
+
−
=
+
−
=
k k
k
k k
k
k k
k
x a x
a a b
x
x a x
a a b
x
x a x a a b
x
◎ ヤコビ法およびガウス・ザイデル法の収束のための十分条件
唯一の近似解に収束する。
ii n
i j j
ij a
a <
∑
≠=1( )
(i=1, 2, …, n) 狭い意味での対角優位行列
例
3 1 1 i=1 3 > 1 + 1 = 2
0 2 0 2 2 > 0 + 0 = 0
1 0 5 3 5 > 1 + 0 = 1
【例題】
以下に示す二元連立一次方程式を①ヤコビ法および②ガウス・ザイデル法で解け。
但し、初期値はx1 = x2 = 0、精度ε= 0.005とせよ。
5 2
4 2
2 1
2 1
= +
= +
x x
x x
二つの方法での近似解の漸化式は以下の様になる。
① ヤコビ法
) ( 1 )
( 1 )
1 ( 2
) ( 2 )
( 2 )
1 ( 1
5 . 0 5 . 2 2 / ) 5 (
5 . 0 2 2 / ) 4 (
k k
k
k k
k
x x
x
x x
x
−
=
−
=
−
=
−
=
+ +
②ガウス・ザイデル法
) 1 ( 1 )
1 ( 1 )
1 ( 2
) ( 2 )
( 2 )
1 ( 1
5 . 0 5 . 2 2 / ) 5
(
5 . 0 2 2 / ) 4 (
+ +
+ +
−
=
−
=
−
=
−
=
k k
k
k k
k
x x
x
x x
x
また、収束の条件は次式となる。(この例題の場合はn = 2)
Nk= x(k)j !x(k!1)j "!
j=1 n
#
計算結果①
k x1 x2 Nk
0 0 0
1 2 2.5 4.5
2 0.75 1.5 2.25
3 1.25 2.125 1.125
4 0.9375 1.875 0.5625
5 1.0625 2.03125 0.28125
6 0.984375 1.96875 0.140625 7 1.015625 2.0078125 0.0703125 8 0.99609375 1.9921875 0.03515625 9 1.00390625 2.001953125 0.017578125 10 0.999023438 1.998046875 0.008789063 ◎11 1.000976563 2.000488281 0.004394531 12 0.999755859 1.999511719 0.002197266 計算結果②
k x1 x2 Nk
0 0 0
1 2 1.5 3.5
2 1.25 1.875 1.125
3 1.0625 1.96875 0.28125
4 1.015625 1.9921875 0.0703125 5 1.00390625 1.998046875 0.017578125 ◎6 1.000976563 1.999511719 0.004394531 7 1.000244141 1.99987793 0.001098633 この例題で、2つの式の順序を変えてみる。
4 2
5 2
2 1
2 1
= +
= +
x x
x
x
すると、ガウス・ザイデル法での漸化式は以下となる。
) 1 ( 1 )
1 ( 2
) ( 2 )
1 ( 1
2 4
2 5
+ +
+
−
=
−
=
k k
k k
x x
x
x
そして、反復計算の結果は以下となり、収束しない。
k x1 x2 Nk
0 0 0
1 5 -6 11
2 17 -30 36
3 65 -126 144
4 257 -510 576
5 1025 -2046 2304
6 4097 -8190 9216
よって、収束させるためには対角要素の絶対値が大きくなる様に方程式を並べる。
参考文献
○ だれにでもわかる数値解析入門 理論とCプログラム 新濃・船田著 近代科学社
!