Linear Algebra Chap2.6

Elimination = Factorization: A=LU

今回は自分が発表する範囲でLU分解法についてだった.

工夫点

  • iPadApple Pencilを使い,発表の流れを簡単に載せたスライドを事前に作成し,その後さらに書き込む形式を取り入れてみた.
    • ホワイトボードと異なり,書いているときに体で隠れない
    • ホワイトボードと比べて事前資料の上に書き込むため,筆記量が少なくて済む

反省点

  • iPadApple Pencilの利用及び事前にスライドの用意
    • PowerPointアプリにバグがあった
    • PowerPointアプリの仕様を十分に把握できずに書きづらかった
  • 今回の発表ではThe Cost of Eliminationの範囲を省いてしまったが,重要度が高く,より詳しく調べておくべきだった.

考察

The Cost of Elimination まとめ

教科書には

Elimination on A requires about \frac{1}{3} n^3 multiplications

と書いており,O(n^3)で普通にガウス消去法を行うときと変わらず,
AがFull matrixであるとき,あまりLU分解法の利点が掴めない.

LU分解法はBand matrixのとき,band widthが小さいときに特に計算量が小さくなり,
計算量がO(n)になるという利点がある.

これは,教科書にも記載されているが,ゼミ中に永原教授にも指摘していただいた.

AがFull matrixであっても当てはまる利点として複数の方程式を解く際に,Ax=bのうちAは変化せず,bのみが変化するような場合,LUはAのみに依存するため,一度分解してしまえば,その後の計算量は分解したLUを用いてO(n^2)で済む.

以下のサイトに明示的に書いてあるのをゼミ後に見つけたので記載しておく.


d.hatena.ne.jp

Challenge Problems

No.24

The square upper left submatrices  A_k of A

という記載があり,これについて調べてみると首座小行列という言葉があることが分かった.

ほとんどは行列式として使うことが多いようで,以下のように定義が書いてあった.

  • 主小行列式(principal minor) 主小行列(principal submatrix)
    • Aの(主)対角線上にある小行列式→同じ番号の行列を選択/排除
    • 番号は連番でなくてもよい
  • 首座小行列式(leading principal minor)
    • 主小行列式の内a_{11}から始まる
    • a_{kk}までを選択する

参考にしたサイトも一緒に載せておく.

主小行列式の定義 [数学についてのwebノート]

また,永原教授の書籍を物色させていただいたので,ページ数などをまとめておく.

斎藤正彦(1966-1990)『線型代数入門』p156 東京大学出版会

佐武一郎(1958-1993)『線型代数学』 p163 裳華房

A_kが正則である必要があるということはブロック行列を用いると簡単に証明できることを教えてもらった.


A = LU: 
\left[
\begin{array}{c:c}
A_k & ? \\ \hdashline
? & ?
\end{array}
\right]
 =
\left[
\begin{array}{c:c}
L_k & 0 \\ \hdashline
? & ?
\end{array}
\right]
\left[
\begin{array}{c:c}
U_k & ? \\ \hdashline
0 & ?
\end{array}
\right]
 = 
\left[
\begin{array}{c:c}
L_kU_k & ? \\ \hdashline
? & ?
\end{array}
\right]

No.25

教科書ではMATLABのようなソフトで解くとあったため,
自分はpythonを用いて解くことにした.

import numpy as np
import scipy.linalg as sl

K = sl.toeplitz([ 2,-1, 0, 0, 0, 0])

T = sl.lu(K)
L = T[1]
print(sl.inv(L))

結果は以下のようになった.

K =
[[ 2 -1  0  0  0  0]
 [-1  2 -1  0  0  0]
 [ 0 -1  2 -1  0  0]
 [ 0  0 -1  2 -1  0]
 [ 0  0  0 -1  2 -1]
 [ 0  0  0  0 -1  2]]
L =
[[ 1.     0.     0.     0.     0.     0.   ]
 [-0.5    1.     0.     0.     0.     0.   ]
 [ 0.    -0.667  1.     0.     0.     0.   ]
 [ 0.     0.    -0.75   1.     0.     0.   ]
 [ 0.     0.     0.    -0.8    1.     0.   ]
 [ 0.     0.     0.     0.    -0.833  1.   ]]
U =
[[ 2.    -1.     0.     0.     0.     0.   ]
 [ 0.     1.5   -1.     0.     0.     0.   ]
 [ 0.     0.     1.333 -1.     0.     0.   ]
 [ 0.     0.     0.     1.25  -1.     0.   ]
 [ 0.     0.     0.     0.     1.2   -1.   ]
 [ 0.     0.     0.     0.     0.     1.167]]
inv(L) =
[[ 1.     0.     0.     0.    -0.    -0.   ]
 [ 0.5    1.     0.     0.    -0.    -0.   ]
 [ 0.333  0.667  1.     0.    -0.    -0.   ]
 [ 0.25   0.5    0.75   1.    -0.    -0.   ]
 [ 0.2    0.4    0.6    0.8    1.    -0.   ]
 [ 0.167  0.333  0.5    0.667  0.833  1.   ]]

永原教授からはnice patternとは以下のように書き下せることだと教えていただいたため,記述しておく.


\hat{l_{ij}} =
\left\{
\begin{array}{cc}
i/j, & (i\geq j) \\
0, & others
\end{array}
\right.

No.26

この問題もpythonで解いた.

print(7*sl.inv(K))
print(np.matmul(K,  7*sl.inv(K)))

結果は以下のようになった.

K =
[[ 2 -1  0  0  0  0]
 [-1  2 -1  0  0  0]
 [ 0 -1  2 -1  0  0]
 [ 0  0 -1  2 -1  0]
 [ 0  0  0 -1  2 -1]
 [ 0  0  0  0 -1  2]]
7*inv(K) =
[[  6.   5.   4.   3.   2.   1.]
 [  5.  10.   8.   6.   4.   2.]
 [  4.   8.  12.   9.   6.   3.]
 [  3.   6.   9.  12.   8.   4.]
 [  2.   4.   6.   8.  10.   5.]
 [  1.   2.   3.   4.   5.   6.]]
K * 7*inv(K) =
[[ 7.  0.  0.  0.  0.  0.]
 [-0.  7. -0.  0.  0.  0.]
 [ 0.  0.  7.  0. -0. -0.]
 [-0. -0.  0.  7.  0.  0.]
 [ 0.  0.  0.  0.  7.  0.]
 [ 0.  0.  0.  0.  0.  7.]]

7K^{-1}wonderfulな表記をラボメンの徳重君に教えてもらったため,記述しておく.


7K^{-1} =
\left\{
\begin{array}{cc}
i(7-i), & (i\geq j) \\
j(7-i), & others
\end{array}
\right.

感想

教科書にLc=bとUx=cの計算量がO(n^2)になることが記載されていたが,Aが変化しない複数の方程式を解くという考えがなく,
AがFull matrixのときの利点を自分だけではあまり理解できなかったため,The Cost of Eliminationを省く結果となってしまった.

発表の荒が出てしまったところを反省材料として次の発表に活かしたい.

『数学は完全に合っていないといけない』