一次方程式を解く鍵
情報処理Ｉ: ガウス・ジョルダン 改訂版 松谷茂樹
a11
a12 a13 a14
a22 a23 a24
の形の行列を上三角行列と呼ぶ．
0
0
a23 a34
0
0
0
a24
特に対角成分が aii ̸= 0 を仮定する．
b1
x1
b2
x2
A が上三角行列（aii ̸= 0）のとき b = とにより x =
b3
x3
b4
x4
に関する方程式 Ax = b は
a11 x1 +a12 x2 +a13 x3 +a14 x4 = b1
a12 x2
+a23 x3 +a24 x4 = b2
となる。これは解く
a33 x3
+a34 x4 = b3
a44 x4
= b4
ことが可能である．４次元以上でも上三角行列にすれば一次方程
式は解く事が可能である．
2015.7.8
0
一次方程式とは
与えられた n × n 行列 A と n 次元ベクトル b,
a11 a12 · · · a1n
b1
x1
a21 a22 · · · a2n
b2
x2
A=
..
..
..
..
, b = .. に対し x = ..
.
.
.
.
.
.
an1 an2 · · · ann
bn
xn
に関する方程式
Ax = b
を解くことである．
つまり，n 次連立一次方程式
a11 x1 + a12 x2 + · · · + a1n xn = b1
a21 x1 + a22 x2 + · · · + a2n xn = b2
..
.
an1 x1 + an2 x2 + · · · + ann xn = bn
を満たす xi を決定することである。
A−1 A = E となる A−1 が存在した場合 Ax = b を解くとは A−1 を
両辺に掛け，
x = A−1 b
とすることである。つまり，一次方程式を解くとは，逆行列を決
定することである．
1 0 ··· 0
0 1 · · · 0
但し，E は単位行列である：E = . . .
. . ...
.. ..
0 0 ··· 1
一次方程式 n = 2 の場合
( )
)
(
(
x1
b
a11 a12
と b = 1 に対し，x =
x2
b2
a21 a22
Ax = (
b を解くこと． )
a11 x1 + a12 x2
Ax =
より Ax = b は
a21 x1 + a22 x2
(
) ( )
a11 x1 + a12 x2
b1
=
に一致．
a21 x1 + a22 x2
b2
−1
Ax = b を解くとは(x = A b により
)
1
a22
−a12
A−1 =
を利用して
−a
a11
)
( ) |A| ( 21
1
a22 b1 − a12 b2
x1
=
x2
|A| −a21 b1 + a11 b2
)
に関する方程式
A=
)
( )
(
a22 a33 − a23 a32
−(a12 a33 − a13 a32 )
−(a21 a33 − a23 a31 )
a11 a33 − a13 a31
a21 a32 − a22 a31
−(a11 a32 − a12 a31 )
これにより x = A−1 b は解ける
)
a13
a23
a33
a43
a14
b1
a24
b2
と b = , に対し，拡張行列
a34
b3
a44
b4
a11 a12 a13 a14 b1
a22 a23 a24 b2
a
(A|b) = 21
a31 a32 a33 a34 b3
a41 a42 a43 a44 b4
を「一次方程式の解として等価な」を上三角行列
c11 c12 c13 c14 d1
0 c22 c23 c24 d2
に変形するアルゴリズム。
(C|d) = 0
0
c33 c34 d3
0
0
0
c44 d4
A は正則とし，n × (n + 1) 行列 (C|d) が上三角行列とは n × n 行
列部 C が上三角行列となることである。
a11 a12 · · · a1m
a1,m+1
a1,m+2
···
a1n
b1
0 a22 · · · a2m
a2,m+1
a2,m+2
···
a2n
b2
0
0
· · · a3m
a3,m+1
a3,m+2
···
a3n
b3
..
..
..
..
..
..
..
..
.
.
.
.
.
.
.
.
0
0
·
·
·
a
a
a
·
·
·
a
b
mm
m,m+1
m,m+2
mn
m
0
0
·
·
·
0
a
a
·
·
·
a
b
m+1,m+1
m+1,m+2
m+1,n
m+1
0
0
·
·
·
0
a
a
·
·
·
a
b
m+2,m+1
m+2,m+2
m+2,n
m+2
..
..
..
..
..
..
..
..
.
.
.
.
.
.
.
.
0
0
0
an,m+1
···
bn
···
an,m+1
an,n
を m 次部分上三角行列と呼ぶこととする。但し、成分は aij とも
ai,j とも記している。aij = ai,j 。
ガウスの消去法は m 次部分上三角行列を「一次方程式の解として
等価な」m + 1 次部分上三角行列に変形することを繰り返す方法。
（ガウスの消去法の場合、その後、代入を行う過程があるがフロー
ではそれは略した）
x1
b1
a11 a12 a13 a14
x2
b2
a21 a22 a23 a24
と b = に対し、x = に
A=
x3
b3
a31 a32 a33 a34
x4
b4
a41 a42 a43 a44
関する方程式 Ax = b を解くことである．
４次元以上では，逆行列を解く事は困難である．
a12
a22
a32
a42
a12 a23 − a13 a22
−(a11 a23 − a13 a21 )．
a11 a22 − a12 a21
一次方程式 n = 4 の場合
a11
a21
A=
a31
a41
n × (n + 1) 行列 C =
a11 a12 a13
b1
x1
A = a21 a22 a23 と b = b2 に対し x = x2 に関する方
a31 a32 a33
b3
x3
程式 Ax = b を解くこと．
|A| = a11 a22 a33 +a13 a21 a32 +a12 a23 a31 −a13 a22 a31 −a11 a23 a32 −
a12 a21 a33 より A−1 は以下のように書ける：
1
A−1 = |A|
×
ガウスの消去法 n = 4
ガウスの消去法（直接法）
一次方程式 n = 3 の場合
(
1
ガウス・ジョルダン法（直接法）
しかし，もともと，3 × 4 行列 (A, b) として、左辺からの適当な 3 ×
n × (n + 1) 行列 C =
3 行列の計算を行っているだけなので、次のようにも考えられる。
一次方程式 n = 3 の場合の具体例の続き
1 0 ··· 0
a1,m+1
a1,m+2
···
a1n
b1
0 1 · · · 0
a2,m+1
a2,m+2
···
a2n
b2
0 0 · · · 0
a
a
·
·
·
a
b3
3,m+1
3,m+2
3n
.. .. . .
..
..
..
..
..
. .
. .
.
.
.
.
0 0 · · · 1
am,m+1
am,m+2
···
amn
bm
0 0 · · · 0 am+1,m+1 am+1,m+2 · · · am+1,n bm+1
0 0 · · · 0 am+2,m+1 am+2,m+2 · · · am+2,n bm+2
.. .. . .
.
..
..
..
..
. .
.
. ..
.
.
.
0 0 ··· 0
an,m+1
an,m+1
···
an,n
bm+1
を m 次部分単位行列と呼ぶこととする。(一般的な呼び方ではない）
ガウス・ジョルダン法は m 次部分単位行列を「一次方程式の解とし
て等価な」m + 1 次部分単位行列に変形することを繰り返す方法。
方程式 Ax = b )
を解くとは、
(
2 1 3 13
1 3 2 13 を考え、
3 2 1 10
ステップ１：
(
)
(
1/2 0 0
1 1/2 3/2
0
1 0 を掛けると 1
3
2
左から
0
0 1
3
2
1
(これは 1 行めに 1/2 を掛けたことに相当）
13/2
13
10
)
となる。
ステップ２：
(
)
(
)
1
0 0
1 1/2
3/2
13/2
13/2 とな
左から −1 1 0 を掛けると 0 5/2 1/2
−3 0 1
0 1/2 −7/2 −19/2
る。
(これは”2 行目-1 行目”と”3 行目-3 × 1 行目”に相当）
つまり、このように左辺からの 3 × 3 行列の適当な行列を掛ける
ことにより行列を変形させてゆき、
1 0 0 b′1
0 1 0 b′2 なればよい。
0 0 1 b′3
一次方程式 n = 3 の場合の具体例の続き
(
一次方程式 n = 3 の場合の具体例
(
)
2 1 3
A= 1 3 2 とb=
3 2 1
Ax = b を解く．
(
2
Ax = b つまり、 1
3
1
3
2
( )
13
13
10
3
2
1
(
に対し、x =
)(
x1
x2
x3
x1
x2
x3
)
に関する方程式
=
13
13
10
ステップ４．
)
)
(
(
1 0
7/2
26/5
1 −1/2 0
1/5
13/5
0
1
0 を掛けると 0 1
0 0 −18/5 −54/5
0 −1/2 1
(これは”1 行目-1/2 × 2 行目”と”3 行目-1/2 × 2 行目”に相当）
に対して、
ステップ１： (
)
1/2 0 0
0
1 0 を掛けると、つまり
両辺に左から
0
0 1
(
)(
)( ) (
)( )
1/2 0 0
2 1 3
x1
1/2 0 0
13
0
1 0
1 3 2
x2 =
0
1 0
13 は
0
0 1
3 2 1
x3
0
0 1
10
(
)( ) (
)
1 1/2 3/2
x1
13/2
1
3
2
13
x2 =
となる。
3
2
1
x3
10
ステップ２：
(
ステップ５．
(
)
(
)
1 0
0
1 0 7/2 26/5
0 1
0
を掛けると 0 1 1/5 13/5
0 0 −5/18
0 0
1
3
(これは 3 行めに −5/18 を掛けたことに相当）
ステップ６．
(
)
(
)
1 0 −7/2
1 0 0 1
0 1 −1/5 を掛けると 0 1 0 2
0 0
1
0 0 1 3
(これは”1 行目-7/2 × 3 行目”と”2 行目-1/5 × 3 行目”に相当）
)
1
0 0
この両辺に左から −1 1 0 を掛けると、つまり
−3 0 1
(
)(
)( ) (
)(
)
1
0 0
1 1/2 3/2
1
0 0
x1
13/2
−1 1 0
1
3
2
x2 = −1 1 0
13
は
−3 0 1
x3
3
2
1
−3 0 1
10
(
)( ) (
)
1 1/2
3/2
13/2
x1
0 5/2
1/2
x2 =
13/2
となる。
x3
0 1/2 −7/2
−19/2
つまり、このように左辺から適当な 3 × 3 行列を両辺に掛けるこ
とにより Ax = b を変形させてゆき、
(
)( ) ′
b1
1 0 0
x1
0 1 0
x2 = b′2 なればよい。これにより
x3
0 0 1
b′3
′
′
x1 = b1 , x2 = b2 , x3 = b′3 を得ることになる。
)
1 1/2
3/2
13/2
13/2
に対して
0 5/2 1/2
0 1/2 −7/2 −19/2
ステップ３：
(
)
(
)
1
0
0
1 1/2
3/2
13/2
0 2/5 0 を掛けると 0
1
1/5
13/5
0
0
1
0 1/2 −7/2 −19/2
(これは 2 行めに 2/5 を掛けたことに相当）
( )
)
これらにより
方
こ と(で)
）
( 程 式 Ax
(左)辺 に 適 当 な 行 列 を 掛 け
) (= b )は（
(る )
1 0 0
1
1
x1
x1
0 1 0
x2 = 2 となることを意味し、 x2 = 2
x3
x3
0 0 1
3
3
となる。
2
一次方程式 n = 3 の場合の具体例の続き（行列を使わない説明） 方程式 Ax = b を解くとは、
{
2x1
x1
3x1
+x2
+3x2
+2x2
+3x3
+2x3
+x3
=
=
=
13
13
10
(1)
(2) を考えることである。
(3)
ステップ１．1 式に 1/2 を掛けることで
{
x1 +(1/2)x2 +(3/2)x3 = 13/2
x1
+3x2
+2x3
=
13
3x1
+2x2
+x3
=
10
(1)
(2)
(3)
ステップ２ ”2 式-1 式”と”3 式-3 × 1 式”により
{
x1 +(1/2)x2 +(3/2)x3 =
13/2
(1)
(5/2)x2
+(1/2)x3 =
13/2
(2)
+(1/2)x2 −(7/2)x3 = −19/2
(3)
ステップ３：2 式に 5/2 を掛けることで
{
x1 +(1/2)x2 +(3/2)x3 =
13/2
x2
+(2/5)x3 =
13/5
+(1/2)x2 −(7/2)x3 = −19/2
(1)
(2)
(3)
ステップ４．”1 式-(1/2) × 2 式”と”3 式-(1/2) × 1 式”により
{
x1
x2
(7/2)x3
+(2/5)x3
−(18/5)x3
=
=
=
26/5
13/5
−54/5
(1)
(2)
(3)
ステップ５．3 式に −5/18 を掛けることで
{
x1
(7/2)x3
= 26/5
(1)
x2 +(2/5)x3 = 13/5
(2)
x3
=
3
(3)
ステップ６．”1 式-(7/2) × 3 式”と”2 式-(1/2) × 3 式”により
{
x1
= 1
(1)
= 2
(2) を得る。
x3 = 3
(3)
これは、行列を用いた計算と等価である。
x2
エクセルの行列演算
「行列の和」や「行列の積」
「転置行列」
「逆行列」
「行列式」を計
算する関数がエクセルでは用意されている。
n が数∼数 10 であれば、これらの関数により計算可能である。
但し，現在必要とされる行列のサイズの計算は n = 106 ∼1012 の
計算である．
3
© Copyright 2024 ExpyDoc
