FEM0

Report
線形計算の基礎(密行列)
1E11M103 本山 義史
行列演算の基礎について
・行列の四則演算
・ピボット選択
・三角分解(LU分解)
連立一次方程式について
・ガウスの消去法
・部分ピボット選択付きガウスの消去法
・逆行列の計算
・LU分解を用いる方法
行列の四則演算について。
(1)n次元ベクトルの加算
 c1 
 a1 
 b1 
c 
a 
b 
 2   2   2
  
  
  






c
a
b
 n
 n
 n
プログラミングに利用できる書式にすると、
 =  +  となる。
(2)n×n型(正方)行列の加算
 c11 c12
c c
 21 22
 

cn1 cn 2
 c1n   a11 a12
 c2 n  a21 a22

  

 
 cnn  an1 an 2
 a1n  b11 b12
 a2 n  b21 b22

    
 
 ann  bn1 bn 2
プログラミングに利用できる書式にすると、
 =  +  となる。
 b1n 
 b2 n 
 

 bnn 
(3)n次元ベクトルの減算
 c1 
 a1 
 b1 
c 
a 
b 
 2   2   2
  
  
  






c
a
b
 n
 n
 n
プログラミングに利用できる書式にすると、
 =  −  となる。
(4)n×n型(正方)行列の減算
 c11 c12
c c
 21 22
 

cn1 cn 2
 c1n   a11 a12
 c2 n  a21 a22

  

 
 cnn  an1 an 2
 a1n  b11 b12
 a2 n  b21 b22

    
 
 ann  bn1 bn 2
プログラミングに利用できる書式にすると、
 =  −  となる。
 b1n 
 b2 n 
 

 bnn 
(5)n次元ベクトルの乗算
c  a1
a2

an 
 b1 
b 
 2
 
 
bn 
プログラミングに利用できる書式にすると、

=
  となる。
=1
また、
 c11
c
 21
 

cn1
c12
c22

cn 2
c1n   a1 
 c2 n  a2 
b1

   
  
 cnn  an 

b2
プログラミングに利用できる書式にすると、
 =   となる。
 bn 
(6)n×n型行列の乗算
 c1   a11
c   a
 2    21
  
  
cn  an1
a12  a1n   b1 
a22  a2 n  b2 
   
 
an 2  ann  bn 
プログラミングに利用できる書式にすると、

 =
  となる。
=1
また、
 c11 c12
c
 21 c 22



cn1 cn 2
 c1n   a11
 c2 n  a21

    
 
 cnn  an1
a12  a1n  b11 b12
a22  a2 n  b21 b22
    


an 2  ann  bn1 bn 2
プログラミングに利用できる書式にすると、

 =
  となる。
=1
 b1n 
 b2 n 
  

 bnn 
ピボット選択について
連立一次方程式や逆行列の計算の際に、係数行列の第k列の第k行目以降の
要素の中で絶対値が最も大きいものを探し、それが第l行にあれば第k行と第l行
全体を入れ替えるという操作のこと。
 a11
a
 21
 

an1
a12  a1n 
 b1 
b 
a22  a2 n 
x   2

   

 
an 2  ann 
bn 
左辺の係数行列  =  についてピボット選択を行う際に、右辺の同じ行
についても入れ替えを行えば、の未知数の順番は変化しない。
→このような式の両辺に対してピボット選択を行うことは、行列を展開した
時の式の順序を入れ替えることに相当しており、結果には影響を与えない。
ピボット選択を行列表現で行うときには、次に示す置換行列を用いる。
正方行列の第行と第行(あるいは第列と第列)を入れ替える時、置換
行列は単位正方行列の第行と第行を入れ替えたものになっている。
また、置換行列は = −1 という性質がある。
1


0

P  
0


0








0

0

1

0







0

1

0

0







0


0 ←第行


0 ←第行


1

正方行列の行を入れ替えるときは置換行列を左からかけ、列を入れ替え
たい時には置換行列を右からかける。
(例題)
次の行列の第1行と第2行を入れ替える置換行列を示せ。
また、置換行列を左からかけることによって、行列の第1行と
第2行が入れ替わることを示せ。
6 5 4
A  18 21 17 
12 13 10
(解答)
置換行列は次のようになる。
0 1 0 
P  1 0 0
0 0 1
この置換行列を行列の左からかけると次のような結果になる。
0 1 0  6 5 4  18 21 17 
1 0 0 18 21 17    6 5 4 


 

0 0 1 12 13 10 12 13 10
三角分解(LU分解)について
行列が与えられたとき、その行列を下三角行列と上三角行列の積の形に
分解することを三角分解(LU分解)という。
LU分解にはいくつかの方法が考えられているが、一般的によく知られている
クラウト法について説明する。
今、行列 =  を下三角行列 =  と上三角行列 =  に分解すること
を考える。
 a11
a
 21
 

an1
a12  a1n  l11 0
a22  a2 n  l21 l22

    

 
an 2  ann  ln1 ln 2
0  u11 u12
 0   0 u22
   


 lnn   0
0

 u1n 
 u2 n 
  

 unn 
下三角行列の対角成分を1にする方法と上三角行列の対角成分を1にする
方法の2種類あるが、ここでは下三角行列の対角成分を = 1 ( = 1, … , )
とする。
11 = 1
1 =   = 1,2, … , 
1 = 0  = 2,3, … , 
1 =
1
 = 2,3, … , 
11
1 = 0 ( = 2,3, … , )
行列の要素の値については、まず(= 2,3, … , )の値に注目して次のように
下三角行列、上三角行列の行列(対角要素)を計算する。
11 = 1

 =
 
=1
下三角行列および上三角行列の行列成分および行列成分については、
それぞれ以下の式を用いて計算を行う。
 =
 −

=1  

 = 0
 = 0

 =  −
 
=1
行列の成分まで計算が終わると、元の行列が三角分解されている。
クラウド法はわかりやすい方法ではあるが、ピボット選択を行うことが
できない。LU分解は連立一次方程式の解法に利用されることが多いので、
ピボット演算を適用した方が望ましい。
ピボット選択を含んだLU分解法としては、部分ピボット付きガウスの
消去法に基づいた方法が知られている。
(例題)
次の行列をクラウト法を用いてLU分解せよ。
6 5 4
A  12 13 10
18 21 17 
(解答)
行列を下三角行列と上三角行列で表現すると次のようになる。
 6 5 4  l11 0 0  u11 u12 u13 
12 13 10  l
0 u

l
0
u
22
23 

  21 22

18 21 17  l31 l32 l33   0
0 u33 
l11u12
l11u13
l11u11


 l21u11 l21u12  l22u22
l21u13  l22u23

l31u11 l31u12  l32u22 l31u13  l32u23  l33u33 
両辺の各要素を対応させると次のような等式が得られる。
11 11 = 6, 11 12 = 5, 11 13 = 4
下三角行列の対角成分の値を1と考えると、11 = 1 より次の値が決まる。
11 = 6, 12 = 5, 13 = 4
この値をもとにして、他の要素の値を計算する。
12
21 =  = 2
11
18
31 =  = 3
11
13−21 12
13−2×5
22 =
=
=3
22
1
10−21 13
10−2×4
23 =
=
=2
22
1
21−31
21−3×5
32 =  12 = 3 = 2
22
17−3113 −32
17−3×4−2×2
23
33 =
=

1
33
=1
三角分解した結果は次のようになる。
 6 5 4  1 0 0  6 5 4 
12 13 10  2 1 0 0 3 2

 


18 21 17  3 2 1 0 0 1 
ガウスの消去法について。
直接法の中でよく知られている連立一次方程式の解法として、ガウスの
消去法がある。この方法は前進消去(前進差分)といわれる処理と後進代入
といわれる処理に別けて行われる。
いま、次の連立一次方程式について考える。
a11 x1  a12 x2    a1n xn  b1
a21 x1  a22 x2    a2 n xn  b2

an1 x1  an 2 x2    ann xn  bn
この式を
a '11 x1  a '12 x2    a '1n xn  b'1
a '22 x2    a '2 n xn  b'2

 a 'nn xn  b'n
上記のような形式の連立一次方程式に変換する処理のことを前進消去と
呼ぶ。また、前進消去によって得られた式を下から順に  = , … , 1 に
ついて解く処理を後退代入という。
説明のため、前のページの式を次のように行列表現する。
 a11
a
 21
 

an1
a12  a1n   x1   b1 





a22  a2 n   x2  b2 

     
   
an 2  ann   xn  bn 
(Step1)
まず、左辺の係数行列の第列の対角成分 初期値は = 1
に注目する。第列の対角成分から下の行をすべて0にするために
以下の式を用いる。
aik

akk
(i  k  1, , n)
aij  aij  akj
bi  bi  bk
( j  k  1, , n)
(i  j  1, , n)
上記の計算を第 − 1列まで行うと左辺の係数行列は上三角行列と
なり、次のような式に変換されている。
a '11
 0

 

 0
a '12  a '1n   x1   b'1 
a '22  a '2 n   x2  b'2 

      
   
0  a 'nn   xn  b'n 
前進消去が終わった段階で得られた式について、対角成分は必ずしも
1であるとは限らない!!
(Step2)
前進消去によって得られた式(前ページ)をもとにして、式を下から
順に以下のように後退代入を行うことにより、解 から1 が順次求まる。
b'n
xn 
a 'nn
n
xk 
b'k   a 'kj x j
j  k 1
a 'kk
(k  n  1, ,1)
(例題)
ガウスの消去法の基本アルゴリズムを用いて、次の連立方程式の
解を求めよ。
6 x1  5 x2  4 x3  8
12 x1  13 x2  10 x3  16
18 x1  21x2  17 x3  27
(解答)
6

12

18
⇒
5
13
21
6

0

0
4 8 

10 16 
17 27 

5
3
6
4 8

2 0
5 3

2行目 − 1行目 × 2 → 2行目、
3行目 − 1行目 × 3 → 6行目
を行う。
最後に3行目−2行目×2→3行目を行うと、
6

0

0
5
3
0
4
2
1
8

0
3
前進消去によって得られた式をもとに、後退代入を行う。
3 = 3
0−2×3
2 =
= −2
3
8−5× −2 −4×3
6
1 =
=1
このようにして解1 = 1, 2 = −2, 3 = 3が得られる。
部分ピボット選択付きガウスの消去法について。
ピボット選択をガウスの消去法に適用する方法がある。
(Step1)
前進消去の際にピボット選択を行う。列の行目以降で最も絶対値の
大きな要素を探す。もし絶対値の最大値が行目の要素だった場合には、
方程式の両辺について行目と行目の要素をすべて入れかれる。
(Step2)
第列 初期値は = 1 の対角成分より下の要素がすべて0になるように
計算を行う。

 =  

( =  + 1, ⋯ , )
 =  − 
 =  − 
 =  + 1, ⋯ , 
( =  + 1, ⋯ , )
Step1とStep2の計算を第 − 1列まで繰り返す。第 − 1列までの
計算が終了すると、左辺の係数行列は上三角行列になっている。
(Step3)
以下、後退代入処理となる。この部分についても基本アルゴリズムと
同じである。前進消去によって得られた式を下から順に、以下の式を用いて
処理を行うことにより、解 から1 まで求まる。
xn 
b'n
a 'nn
b'k 
xk 
n
 a'
j  k 1
a 'kk
kj
xj
( k  n  1, ,1)
(例題)
部分ピボット選択付きガウスの消去法を用いて次の連立方程式を解け。
6 x1  5 x2  4 x3  8
12 x1  13 x2  10 x3  16
18 x1  21x2  17 x3  27
(解答)
 6 5 4 x1 


12 13 10 x2 
18 21 17 x3 
ピボット選択により、1行目と3行目の入れ替えを行う。1行目と3行目の
入れ替えを行うための置換行列は以下のようになる。
0 0 1 
P1  0 1 0
1 0 0
1 を左から両辺にかけると、
 6 5 4   x1 
8
P1 12 13 10  x2   P1 16 
18 21 17   x3 
27 
12
6
入れ替えたあとで、2行目−1行目 × 18 →2行目、3行目−1行目 × 18 →
3行目とする。この変換行列を1 とすると、次のように表すことができる。

 1
 12
G1   
 18
 6

 18
0
1
0

0

0

1


これを用いて次のように表現できる。
 6 5 4   x1 
8
G1 P1 12 13 10  x2   G1 P1 16 
18 21 17   x3 
27 
ここまでを計算した結果は次のようになる。
18
0
0
21
17
4 1
27
−1 −
3 2 = −2
5 3
−1
−2 −
3
次にピボット選択により、2行目と3行目の入れ替えを行う。
2行目と3行目の入れ替えを行うための置換行列2 は次のようになる。
1 0 0
P2  0 0 1
0 1 0
置換行列を用いて入れ替えを表現すると次のようになる。
18
2
0
0
21
17
4 1
27
−1 −
3 2 = 2 −2
5 3
−1
−2 −
3
1
入れ替えたあとで、3行目−2行目× 2 →3行目を行う。
この変換行列を2 とすると、次のように表すことができる。
1
0
0
1
2 =
1
0 −
2
0
0
1
これを用いて次のように表現することができる。
18
2 2
0
0
21
17
27
4 1
−1 −
−1
3 2 =
3
1 3
−
−2 −
2
2
前進消去によって得られた式をもとに、後退代入を行う。
3
−2
3 =
=3
1
−2
5
−1 + × 3
3
2 =
= −2
−2
27 − 21 × −2 − 17 × 3
1 =
=1
18
このようにして、1 = 1, 2 = −2, 3 = 3が得られる。
逆行列の計算について
ガウスの消去法の前進消去を応用して、前進消去終了後の左辺の係数行列
が単位行列になるように変換することもできる。
この場合には、後退代入を行うことなしに連立方程式の解を求めることが
できる。この手法を掃き出し法(ガウス・ジョルダンの消去法)という。
掃き出し法を用いて、逆行列を求めることができる。
 a11
a
 21
 

an1
a12  a1n 
1
0
a22  a2 n 
X 

   


an 2  ann 
0
0  0
1  0
  

0  1
この行列と右辺行列に対して基本演算とピボット選択を行っても
行列の要素はまったく変化しない。
基本演算とピボット演算だけを利用して次のような式に変換したとき、
右辺に作られた行列 =  は、行列 =  の逆行列となる。
1
0



0
0  0
b11 b12
b
b
1  0
21
22
X 


  


0  1
bn1 bn 2
b11 b12
b
b22
21
1

A 



bn1 bn 2
 b1n 
 b2 n 
  

 bnn 
 b1n 
 b2 n 
  

 bnn 
ここで、左辺の係数行列を単位行列に変換する際には各列に対して次式
を用いる。今、第行の対角成分 に着目する。行列の初期値は単位行列と
する。

 = 1, ⋯ , ,  ≠ 

 =  −   =  + 1, ⋯ , 
=
 =  − 
 = 1, ⋯ , 
 = 1 ( = 1, ⋯ , )
次式において、左辺と右辺は中央の分離線によって分けられている。
 a11

a21
 

an1
a12  a1n 1
a22  a2 n 0
   
an 2  ann 0
0  0

1  0
  

0  1
最終的な目標として、次のように単位行列が左半分に移ることである。
1

0


0
0  0 b11
1  0 b21
   
0  1 bn1
b12  b1n 

b22  b2 n 
   

bn 2  bnn 
(例題)
次の行列の逆行列を求めよ。
 2 4 6
A  2 4 8
1 3 5
(解答)
 2 4 6 1 0 0


 2 4 8 0 1 0
1 3 5 0 0 1
1
1行目× 2 →1行目としたあとで、2行目
−1行目×2→2行目、3行目−1行目→3行目
という演算を行う。


1
1 2 3 2 0 0
 0 0 2  1 1 0 


1
0 1 2 
0 1
2


2行目と3行目を入れ替える。


1
0

0


2
1
0
1
3 2
1
2
2
2 1
0
0
1

0

1

0


1行目−2行目×2→1行目


1
 0

0


0
1
0
3
1 2
1
2 
2
2 1
0
0
1

 2

1 

0 


1
3行目× 2 →3行目としたあとで、1行目+3行目→1行目、2行目−
3行目×2→2行目という演算を行う。


1
0

0


0
1
0
1
0
1
0
2
1 1

2
1
2
1
1
2

 2

1 


0 

逆行列は次のようになる。

1
1

 2 4 6

2 4 8   1


 2
1 3 5
 1
 2

 2

1 1 

1
0

2
1
2
LU分解を用いる方法について
置換行列  = 1, ⋯ ,  − 1 と変換行列 ( = 1, ⋯ ,  − 1)を用いると、
ガウスの消去法の前進消去の過程は次のように表すことができる。
−1 −1 ⋯ 1 1  = −1 −1 ⋯ 1 1 
Pi Pi 1 ( I )を Pi 1の左から挿入して漸化 式で表現すると、
−1  = −1 −2 となる。
ただし、
0 = 
 =   −1
0 = 
1
−1 =  −1 −2 Pi
−1
=
−
=1
左辺の係数行列−1 を計算した結果は上三角行列となり、次式の
ようになる。
 = −1 −2 
これより、次式を得る。
(−1 −2 )−1  = 
−1 (−1 −2 ) −1  = 
上式の(−1 −2 )−1 は下三角行列となる。
もとの連立方程式 = と対応させると、分解が行われていることが
分かる。
 = −1  = 
ここまででLU分解は終了し、次にLU分解の結果を利用して連立一次方程式
を解くことを考える。
前ページの最後の式は次のように変形できる。
 = 
→  = −1 
ここで = とおくと、次のようになる。
 = 
下三角行列の要素を =  , 上三角行列の要素を =  とするとき、
この連立方程式の解は、前進代入を用いて解くことができる。

1 =  1
11
1 =
 − =1  

( = 2, ⋯ , )
次に連立一次方程式
 = 
を解くことによって、与えられた連立一次方程式の解を得ることができる。
この場合の後退代入は次のようになる。

 = 

 =
 − 
=+1  

( =  − 1, ⋯ , 1)
(例題)
次の連立方程式を行列表現し、部分ピボット選択付きガウスの消去法
に基づきLU分解せよ。また、LU分解した結果をもとに連立一次方程式の
解を求めよ。
6 x1  5 x2  4 x3  8
12 x1  13 x2  10 x3  16
18 x1  21x2  17 x3  27
(解答)
 6 5 4   x1   8 
12 13 10  x   16 

  2  
18 21 17   x3  27 
上式は次のように表すことができる。
 = 
ピボット選択によって1行目と3行目の入れ替えを行う。1行目と3行目の
入れ替えを行うための置換行列1 は次のようになる。
0
P1  0
1
0
1
0
1
0
0
12
6
行を入れ替えたあとで、2行目−1行目× 18 →2行目、3行目−1行目× 18 →
3行目とする。この変換行列を1 とすると、次のようになる。

 1
 12
G1   
 18
 6

 18
0
1
0

0

0

1


ここまでの演算は1 と1 を用いて表現できる。
1 1  = 1 1 
また、上式の1 = 1 1 を計算した結果は次のようになる。


18 21 17   x 
8
1


4  
 
 0  1    x2   G1 P1 16 
3

 
27 
 0  2  5   x3 

3 
次にピボット選択により、2行目と3行目の入れ替えを行う。2行目と3行目
の入れ替えを行うための置換行列2 は、
1 0 0
P2  0 0 1
0 1 0
1
行を入れ替えたあとで、3行目−2行目× 2 →3行目を行う。
この変換行列を2 とすると、


1
0
0


G2  0 1 0


1
1
0 
2


これを用いて、


18 21 17   x 
8
1

5  
G2 P2  0  1    x2   G2 P2G1 P1 16  3

x 
27 
 0  2  1  3

2 
と表すことができる。
2 = 2 2 1 を計算した結果は、
L  (G2 P2G1 P21 ) 1

1
1

3
2
 3
0
1
1
2

0

0

1

上式左辺の係数行列2 は上三角行列になっている。次に、
G2 P2G1 P1  (G2 P2G1 P21 ) 1 P2 P1  L1 P
より、下三角行列を求める。

1
1
1 1
L  (G2 P2G1 P2 )  
3
2
 3

0 0

1 0

1
1

2
置換行列の積 = 2 1 は次のようになる。
0 0 1 
P  P2 P1  1 0 0
0 1 0
まず、 = とおいて、を求める。 = より、は前進代入を
用いて、次のように計算できる。
y1  27
1
y2  8   27  1
3
2
1
3
y3  16   27   (1)  
3
2
2
最後に = より、後退代入式を用いて解を求める。
3

2 3
x3 
1

2
5
1  3
3
x2 
 2
2
27  21 ( 2)  17  3
x3 
1
18
このようにして解1 = 1, 2 = −2, 3 = 3が得られる。
連立一次方程式を一回解くだけなら、ガウスの消去法を利用した方がよい
場合が多いが、解くべき問題によっては同じ係数行列で定数項の値だけを変え
て連立一次方程式を繰り返して計算しなければならない場合がある。
その時は、LU分解法を用いるのが一般的になっている。
クラウト法による解法について。
次の連立一次方程式を考える。
 = 
係数行列を下三角行列および上三角行列を用いて三角分解すると、
連立一次方程式は次のようになる。
 =  = 
LU分解した結果は、(基本)ガウスの消去法に基づくLU分解の場合と
全く同じ式になる。クラウト法の場合も「ピボット選択付きガウスの消去
法に基づくLU分解」アルゴリズムの置換行列 をすべて単位行列として、
前進代入および後退代入を行えばよい。

similar documents