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(λ)は,
Di(λ) =
i
<
1 0 . . . 0
0 . .. ...
... . .. ...
0 . . . λ . . . 0
... . .. ...
... . .. 0
0 . . . 0 1
< i
Dec. 17, 2014, Version: 1.0 [email protected]
2014年度・後期・数理解析・計算機数学３・第１２回 2
Tij=
i
<
j
<
1 . . . 0
... . .. . . ... 0 · · · 0 · · · 1 · · · 0
... . .. ...
0 · · · 1 · · · 0 · · · 0 ... . . .. ...
0 . . . 1
< i
< j
Eij(λ) =
j
<
i
<
1 . . . 0
... . .. . . ... 0 · · · 1 · · · 0 · · · 0
... . .. ...
0 · · · λ · · · 1 · · · 0 ... . . .. ...
0 . . . 1
< j
< i
である.
• 掃出し法のアルゴリズムは以下の通りである. ただし,「枢軸選択」を行っていないので,正 則であっても,アルゴリズムが最後まで到達できないときがある.
– i= 1, . . . , nに対して,以下を繰り返す.
1. 対角成分aii が 1となるように,i 行目を定数倍する.
すなわち,「Di(a−ii1)を左からかける」または,「aij :=aij/aii (j = 1, . . . , n) と する」
2. j= 1, . . . , i−1, i+ 1, . . . , nに対して,非対角成分aji を0となるように,j 列目か らi列目の定数倍を引く.
すなわち,「Eji(−aji)を左からかける」または,「ajk:=ajk−ajiaik (k= 1, . . . , n) とする」
– もし, 1のステップでaii= 0 であるときには,プログラムを停止する.
★ Gaussの消去法
• 連立一次方程式を与える行列Aが上三角行列U である場合には,U y=bは以下のようにし てO(n2)の計算量で解くことができる. いま,U y=b をexplicitに書くと,
a11y1+· · ·+a1nyn=b1, ...
an−1n−1yn−1+an−1nyn=bn−1, annyn=bn
Dec. 17, 2014, Version: 1.0 [email protected]
2014年度・後期・数理解析・計算機数学３・第１２回 3
であるので,すべてのiに対して,対角成分aii がnon-zeroと仮定すると（この仮定はU が 正則であることと同値である）
yn = 1 ann
bn, yn−1= 1
an−1n−1
(bn−1−an−1nyn), ...
y1= 1
a11(b1−a1nyn− · · · −a12y2)
として,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}nj=i がすべて0となっている場合である. この場合には,i 列 目はi−1列以前の列の一次結合で書けることとなり, Aが正則であるという仮定と矛盾す る. よって, Gaussの消去法はA が正則であれば,必ず終了する.
• Gaussの消去法の計算量はO(n3)であるが,ステップ２のループ回数が掃出し法と比較して
半分となっているので,掃出し法のほぼ半分の計算量となる.
● 実習内容
1. （★★★）4×4 行列の積を計算するプログラムを書きなさい.
2. （★★★）4×4 行列の転置行列を計算するプログラムを書きなさい.
3. （★★★）連立一次方程式
3x+ 12y+ 9z= 3 2x+ 5 y+ 4z= 4
−x+ 3 y+ 2z= 5
をGauss-Jordanの消去法（掃出し法）で解くプログラムを書きなさい. また,この方程式を
Gaussの消去法で解くプログラムを書きなさい.
4. （★★）整数係数の4×4行列に対して,それが正則か否かを判定し,もし正則であるときに は,逆行列を有理数係数で求め,正則でないときには, ランク,核の基底,像の基底を求めるプ ログラムを書きなさい,
Dec. 17, 2014, Version: 1.0 [email protected]
