● 前回の講義のまとめ

(1)

２００６年度・数理解析・計算機数学２・第１１回

1

● 前回の講義のまとめ

【

Gauss-Jordan

の消去法】

1. Gauss-Jordan

の消去法とは,いわゆる「掃き出し法」であり,連立一次方程式

Ax = b

を解く

ために, 基本変形行列の積となる行列を利用して

MAN (N

⁻¹

)x = Mb, MAN =



 

 

1 0 · · · 0 0 · · · 0 0 1 · · · 0 0 · · · 0

. . . .. . . . . 0 0 · · · 1 0 · · · 0 0 0 · · · 0 0 · · · 0 . . . . . .. ...

0 0 · · · 0 0 · · · 0



 

 

とするアルゴリズムである.

2. A

が正方行列で正則な場合, Gauss-Jordanの消去法のアルゴリズムは以下のようなものとなる.

以下で

R

_j は,その時点での各行列の第

j

行目をあらわす. また,

n

は行列のサイズをあらわす.

(a) k = 1, M = I

とする.

(b) (部分枢軸選択) {a

k

}

ⁿ_=k たちの中から,その絶対値が最も大きいものを

a

k0 としたとき,

A , b , M

に対して,

R

k と

R

0 を交換する.

(c) (A

の対角成分

a

kk を

1

にする.)

A, b, M

に対して,

R

k

← (a

kk

)

⁻¹

R

k とする.

(d) (A

の対角成分以外を

0

にする)

A, b, M

に対して,

= 1

から

m

まで,

= k

を除いて,

R

← R

− a

k

L

k を行う.

(e) k += 1

とし,

k = n

ならば終了. そうでなければ, Step bに戻る.

これが終了した時点で,

b

は解

x

を与え,

M

はもとの

A

の逆行列を与える.

3.

浮動小数点演算による誤差を最小限に止めるために「枢軸選択」は必ず必要な手順である.

4.

正則でない場合には, Step 2において,「0でない要素（実際には,誤差を含んで

0

と等しくない要素）が見つからない」という形でアルゴリズムが実行できなくなる.

5. A

が正方行列で正則でない場合も含んだ

Gauss-Jordan

の消去法のアルゴリズムは以下のようなものとなる. 以下で

C

j は, その時点での各行列の第

j

列目をあらわす. また,

n

は行列のサイズをあらわす.

(a) k = 1

とする.

(b) (完全枢軸選択) {a

j

}

ⁿ_=k,j=k の中に

0

でない要素を以下のようにして探す.

i.

はじめに,

= k

とし,

j = k

から

j = n

の範囲で探す. ここで見つからなければ,

+= 1

とし, 再び

j = k

から

j = n

の範囲で探す. 以下,これを

= m , j = n

まで繰り返す.

もし,全てが

0

であれば,アルゴリズムを終了する. 0でない要素が

k

0 列目に見つかれば,

A, N

に対して,

C

_k と

C

_k₀ を交換する.

ii. {a

k

}

ⁿ_=k の中に

0

でない要素があれば,その中から絶対値が最も大きいものを

a

0k としたとき,

A, b, M

に対して,

R

_k と

R

₀ を交換する.

(c) ( A

の対角成分

a

kk を

1

にする)

A , b , M

に対して,

R

k

← ( a

kk

)

⁻¹

R

k とする.

ex11.tex,v 1.6 2006-06-28 08:05:43+09 naito Exp

(2)

2

２００６年度・数理解析・計算機数学２・第１１回

(d) (A

の対角成分以外を

0

にする)

A, b, M

に対して,

= 1

から

m

まで,

= k

を除いて,

R

← R

− a

k

R

k を行う.

(e) k += 1

とし,

k

が

n

に等しいならばステップ

f

へ,そうでなければ, ステップ

b

に戻る.

(f)

この時点での

k

₀

= k, k = 1

とおき,

k = 1

から

k

₀ まで,次の操作を繰り返す.

a

k

= 0 (k < ≤ n)

でない

が存在したら,

A, N

に対して,

C

→ C

− a

k

C

k を行う.

(g) A

の対角成分の

1

の個数を

r

と置き,

r < n

ならば,

b

の第

r + 1

列目（

b

に相当する部分）を

˜ b

とおく.

r < n

かつ, ˜

b

の

r + 1

列目以後に

0

でない成分があれば, 方程式は解を持たない.

そうでなければ,

b = N ˜ b

と置く.

r = n

ならば

x

が求めるただひとつの解.

r < n

ならば,

x

が求める解のうちの一つで,他の解は

N

の

r + 1

列目以後のベクトルで張られる部分空間を

x

に加えたものとなる.

6.

これらの

Gauss-Jordan

の消去法のアルゴリズムは,行に関する演算については左から,列に関

する演算については右から,

A

に基本変形行列を掛けて変形していることに他ならない.

7. Gauss-Jordan

の消去法で, 正則な

n × n

行列を単位行列まで変形するためには,

n

²

(n − 1)

回の乗算と

n(n − 1)

回の加算が必要となる. 特に

O(n

³

)

回の乗算が必要である.

● 実習内容

• Gauss

の消去法を用いて,以下の連立方程式を解くプログラムを書きなさい.

 

 

 



3x+12y+9z=3, 2x+ 5y+4z=4,

−x+ 3y+2z=5.

 

 

 



2x+2y+ z=3, x+ y+2z=4, y+ z=5.

•

次の行列を

LU

分解するプログラムを書きなさい. また,その結果を使って上の連立一次方程式を解くプログラムを書きなさい.



 

3 12 9

2 5 4

−1 3 2



  ,



 

2 2 1 1 1 2 0 0 1



  ,

•

電子メールで「今日の講義の感想や意見」を送ってください.

★ 実習内容の解答

0 @ −7.000000

−22.000000 +32.000000

1 A ,

0 @ −2.666667 +3.333333 +1.666667

1 A

L =

0 @ +1.000000 +0.000000 +0.000000

−0.333333 +1.000000 +0.000000 +0.666667 −0.428571 +1.000000

1 A U =

0 @ +3.000000 +12.00000 +9.000000 +0.000000 +7.000000 +5.000000 +0.000000 +0.000000 +0.142857

1 A

L =

0 @ +1.000000 +0.000000 +0.000000 +0.000000 +1.000000 +0.000000 +0.500000 +0.000000 +1.000000

1 A U =

0 @ +2.000000 +2.000000 +1.000000 +0.000000 +1.000000 +1.000000 +0.000000 +0.000000 +1.500000

1 A

ex11.tex,v 1.6 2006-06-28 08:05:43+09 naito Exp