講義・実習メモ

2014 年度・後期・数理解析・計算機数学３・第１２回
1
● 講義資料
▼ 講義予定
• 連立一次方程式の数値解法
▼ 消去法
★ はき出し法
• 以下, A ∈ Mn (R), b, x ∈ Rn として, 連立一次方程式 Ax = b を数値的に解くことを考える.
（A が正則でない場合には, 「正則でない」ことが判定できればよいことにする.）
• 連立一次方程式を数値的に解く方法としては, 大きく分けて, 消去法と反復法がある. はじめ
に, 消去法の中でももっとも基本的な「掃出し法」（「Gauss-Jordan の消去法」）を考える.
• 掃出し法とは, 「行基本変形」を繰り返して, 行列 A を単位行列に変形する方法である. こ
こで, 「行基本変形」は, 以下の３種類の変形である.
1. i 行目を λ 倍する.
これは, 方程式の両辺に左から Di (λ) をかけることに他ならない.
2. i 行目と j 行目を入れ替える.
これは, 方程式の両辺に左から Tij をかけることに他ならない.
3. i 行目に j 行目の λ 倍を加える. （ただし, j < i を仮定する）
これは, 方程式の両辺に左から Eij (λ) をかけることに他ならない.
ただし, 行列 Di (λ), Tij , Eij (λ) は,
<
i

1
0

0

.
.
.
Di (λ) = 

0

.
 ..

.
.
.
0
..
Dec. 17, 2014, Version: 1.0
........
.
..
...
.
λ
...
..
.
..
........
0
.

0
.. 
.

.. 

.

0
< i
.. 
.



0
1
[email protected]
2014 年度・後期・数理解析・計算機数学３・第１２回
i
j
<
<
2


0
.. 
.


· · · 0 < i

.. 
.


· · · 0 < j
.
..

. .. 
1
.........
. .
..
 ..
.......


0 · · · 0 · · · 1
Tij = 
 ..
..
.
.


0 · · · 1 · · · 0
.
.
.
.......
0
.........

1
.
 ..


0
Eij (λ) = 
 ..
.


0
.
.
.
0
j
i
<
<
1

0
.. 
.......
.


1 · · · 0 · · · 0 < j

.. 
..
.
.


λ · · · 1 · · · 0 < i
.
..

. .. 
.......
.........
..
.
···
···
.........
1
である.
• 掃出し法のアルゴリズムは以下の通りである. ただし, 「枢軸選択」を行っていないので, 正
則であっても, アルゴリズムが最後まで到達できないときがある.
– i = 1, . . . , n に対して, 以下を繰り返す.
1. 対角成分 aii が 1 となるように, i 行目を定数倍する.
すなわち, 「Di (a−1
ii ) を左からかける」または, 「aij := aij /aii (j = 1, . . . , n) と
する」
2. j = 1, . . . , i − 1, i + 1, . . . , n に対して, 非対角成分 aji を 0 となるように, j 列目か
ら i 列目の定数倍を引く.
すなわち, 「Eji (−aji ) を左からかける」または, 「ajk := ajk −aji aik (k = 1, . . . , n)
とする」
– もし, 1 のステップで aii = 0 であるときには, プログラムを停止する.
★ Gauss の消去法
• 連立一次方程式を与える行列 A が上三角行列 U である場合には, U y = b は以下のようにし
て O(n2 ) の計算量で解くことができる. いま, U y = b を explicit に書くと,
a11 y1 + · · · + a1n yn = b1 ,
..
.
an−1n−1 yn−1 + an−1n yn = bn−1 ,
ann yn = bn
Dec. 17, 2014, Version: 1.0
[email protected]
2014 年度・後期・数理解析・計算機数学３・第１２回
3
であるので, すべての i に対して, 対角成分 aii が non-zero と仮定すると（この仮定は U が
正則であることと同値である）
yn =
yn−1 =
1
ann
bn ,
1
(bn−1 − an−1n yn ),
an−1n−1
..
.
y1 =
1
(b1 − a1n yn − · · · − a12 y2 )
a11
として, yn , yn−1 , . . . , y1 の順序で陽的に解くことができる. これを後退代入と呼ぶ.
• したがって, 連立一次方程式 Ax = b を解くためには, A に行基本変形を施して U x = b′ の
形にすればよい. 実際, これは以下のように実行できる. これを Gauss の消去法と呼ぶ.
i = 1, . . . , n に対して, 以下を繰り返す.
1. aji (j ≥ i) の中で絶対値最大の要素を探し, それを含む行と i 行目を交換し, その後 aii
が 1 となるように i 行目を定数倍する.
2. j = i + 1, . . . , n に対して, 非対角成分 aji を 0 となるように, j 列目から i 列目の定数
倍を引く.
このアルゴリズムは, A が正則ならば必ず終了する. 実際, これが終了しない可能性があるの
は, ステップ１において, {aji }n
j=i がすべて 0 となっている場合である. この場合には, i 列
目は i − 1 列以前の列の一次結合で書けることとなり, A が正則であるという仮定と矛盾す
る. よって, Gauss の消去法は A が正則であれば, 必ず終了する.
• Gauss の消去法の計算量は O(n3 ) であるが, ステップ２のループ回数が掃出し法と比較して
半分となっているので, 掃出し法のほぼ半分の計算量となる.
● 実習内容
1. （★★★）4 × 4 行列の積を計算するプログラムを書きなさい.
2. （★★★）4 × 4 行列の転置行列を計算するプログラムを書きなさい.
3. （★★★）連立一次方程式

3 x + 12y + 9z = 3



2 x + 5 y + 4z = 4



−x + 3 y + 2z = 5
を Gauss-Jordan の消去法（掃出し法）で解くプログラムを書きなさい. また, この方程式を
Gauss の消去法で解くプログラムを書きなさい.
4. （★★）整数係数の 4 × 4 行列に対して, それが正則か否かを判定し, もし正則であるときに
は, 逆行列を有理数係数で求め, 正則でないときには, ランク, 核の基底, 像の基底を求めるプ
ログラムを書きなさい,
Dec. 17, 2014, Version: 1.0
[email protected]

Download Report