Linear Algebra Chap2.6
Elimination = Factorization: A=LU
今回は自分が発表する範囲でLU分解法についてだった.
工夫点
反省点
- iPad・Apple Pencilの利用及び事前にスライドの用意
- PowerPointアプリにバグがあった
- PowerPointアプリの仕様を十分に把握できずに書きづらかった
- 今回の発表では
The Cost of Elimination
の範囲を省いてしまったが,重要度が高く,より詳しく調べておくべきだった.
考察
The Cost of Elimination まとめ
教科書には
Elimination on A requires about multiplications
と書いており,で普通にガウス消去法を行うときと変わらず,
AがFull matrix
であるとき,あまりLU分解法の利点が掴めない.
LU分解法はBand matrix
のとき,band widthが小さいときに特に計算量が小さくなり,
計算量がになるという利点がある.
これは,教科書にも記載されているが,ゼミ中に永原教授にも指摘していただいた.
AがFull matrix
であっても当てはまる利点として複数の方程式を解く際に,Ax=bのうちAは変化せず,bのみが変化するような場合,LUはAのみに依存するため,一度分解してしまえば,その後の計算量は分解したLUを用いてで済む.
以下のサイトに明示的に書いてあるのをゼミ後に見つけたので記載しておく.
Challenge Problems
No.24
The square upper left submatrices of A
という記載があり,これについて調べてみると首座小行列という言葉があることが分かった.
ほとんどは行列式として使うことが多いようで,以下のように定義が書いてあった.
- 主小行列式(principal minor) 主小行列(principal submatrix)
- Aの(主)対角線上にある小行列式→同じ番号の行列を選択/排除
- 番号は連番でなくてもよい
- 首座小行列式(leading principal minor)
- 主小行列式の内から始まる
- までを選択する
参考にしたサイトも一緒に載せておく.
また,永原教授の書籍を物色させていただいたので,ページ数などをまとめておく.
斎藤正彦(1966-1990)『線型代数入門』p156 東京大学出版会.
佐武一郎(1958-1993)『線型代数学』 p163 裳華房.
が正則である必要があるということはブロック行列を用いると簡単に証明できることを教えてもらった.
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
とは以下のように書き下せることだと教えていただいたため,記述しておく.
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.]]
がwonderful
な表記をラボメンの徳重君に教えてもらったため,記述しておく.
感想
教科書にLc=bとUx=cの計算量がになることが記載されていたが,Aが変化しない複数の方程式を解く
という考えがなく,
AがFull matrix
のときの利点を自分だけではあまり理解できなかったため,The Cost of Elimination
を省く結果となってしまった.
発表の荒が出てしまったところを反省材料として次の発表に活かしたい.
『数学は完全に合っていないといけない』