線形計算の基礎（密行列）

線形計算の基礎（密行列）
1E11M103 本山義史
行列演算の基礎について
・行列の四則演算
・ピボット選択
・三角分解（LU分解）
連立一次方程式について
・ガウスの消去法
・部分ピボット選択付きガウスの消去法
・逆行列の計算
・LU分解を用いる方法
行列の四則演算について。
（１）n次元ベクトルの加算
 c1 
 a1 
 b1 
c 
a 
b 
 2   2   2
  
  
  






c
a
b
 n
 n
 n
プログラミングに利用できる書式にすると、
𝑐𝑖 = 𝑎𝑖 + 𝑏𝑖 となる。
（２）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 
（３）n次元ベクトルの減算
 c1 
 a1 
 b1 
c 
a 
b 
 2   2   2
  
  
  






c
a
b
 n
 n
 n
プログラミングに利用できる書式にすると、
𝑐𝑖 = 𝑎𝑖 − 𝑏𝑖 となる。
（４）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 
（５）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 
（６）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

正方行列𝐴の行を入れ替えるときは置換行列を左からかけ、列を入れ替え
たい時には置換行列を右からかける。
（例題）
次の行列𝐴の第１行と第２行を入れ替える置換行列𝑃を示せ。
また、置換行列を左からかけることによって、行列𝐴の第１行と
第２行が入れ替わることを示せ。
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, … , 𝑛)
とする。
𝑙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
下三角行列の対角成分の値を１と考えると、𝑙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−𝑙31𝑢13 −𝑙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 
（Step１）
まず、左辺の係数行列の第𝑘列の対角成分𝑎𝑘𝑘 初期値は𝑘 = 1
に注目する。第𝑘列の対角成分から下の行をすべて０にするために
以下の式を用いる。
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 
前進消去が終わった段階で得られた式について、対角成分は必ずしも
１であるとは限らない！！
（Step２）
前進消去によって得られた式（前ページ）をもとにして、式を下から
順に以下のように後退代入を行うことにより、解𝑥𝑛 から𝑥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

２行目 − １行目 × ２ → ２行目、
３行目 − １行目 × ３ → ６行目
を行う。
最後に３行目−２行目×２→３行目を行うと、
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が得られる。
部分ピボット選択付きガウスの消去法について。
ピボット選択をガウスの消去法に適用する方法がある。
（Step１）
前進消去の際にピボット選択を行う。𝑘列の𝑘行目以降で最も絶対値の
大きな要素を探す。もし絶対値の最大値が𝑙行目の要素だった場合には、
方程式の両辺について𝑘行目と𝑙行目の要素をすべて入れかれる。
（Step２）
第𝑘列初期値は𝑘 = 1 の対角成分より下の要素がすべて０になるように
計算を行う。
𝑎
𝛼 = 𝑎 𝑖𝑘
𝑘𝑘
(𝑖 = 𝑘 + 1, ⋯ , 𝑛)
𝑎𝑖𝑗 = 𝑎𝑖𝑗 − 𝛼𝑎𝑘𝑗
𝑏𝑖 = 𝑏𝑖 − 𝛼𝑏𝑘
𝑗 = 𝑘 + 1, ⋯ , 𝑛
(𝑖 = 𝑗 + 1, ⋯ , 𝑛)
Step１とStep２の計算を第𝑛 − 1列まで繰り返す。第𝑛 − 1列までの
計算が終了すると、左辺の係数行列は上三角行列になっている。
（Step３）
以下、後退代入処理となる。この部分についても基本アルゴリズムと
同じである。前進消去によって得られた式を下から順に、以下の式を用いて
処理を行うことにより、解𝑥𝑛 から𝑥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 
ピボット選択により、１行目と３行目の入れ替えを行う。１行目と３行目の
入れ替えを行うための置換行列𝑃は以下のようになる。
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
入れ替えたあとで、２行目−１行目 × 18 →２行目、３行目−１行目 × 18 →
３行目とする。この変換行列を𝐺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 は次のようになる。
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
入れ替えたあとで、３行目−２行目× 2 →３行目を行う。
この変換行列を𝐺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
１行目× 2 →１行目としたあとで、２行目
−１行目×２→２行目、３行目−１行目→３行目
という演算を行う。


1
1 2 3 2 0 0
 0 0 2  1 1 0 


1
0 1 2 
0 1
2


２行目と３行目を入れ替える。


1
0

0


2
1
0
1
3 2
1
2
2
2 1
0
0
1

0

1

0


１行目−２行目×２→１行目


1
 0

0


0
1
0
3
1 2
1
2 
2
2 1
0
0
1

 2

1 

0 


1
３行目× 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 は次のようになる。
0
P1  0
1
0
1
0
1
0
0
12
6
行を入れ替えたあとで、２行目−１行目× 18 →２行目、３行目−１行目× 18 →
３行目とする。この変換行列を𝐺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 は、
1 0 0
P2  0 0 1
0 1 0
1
行を入れ替えたあとで、３行目−２行目× 2 →３行目を行う。
この変換行列を𝐺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分解」アルゴリズムの置換行列𝑃𝑖 をすべて単位行列𝐼として、
前進代入および後退代入を行えばよい。

Download Report