2017-06-03

Linear Algebra Chap2.6

LinearAlgebra

Elimination = Factorization: A=LU

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

工夫点

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

反省点

iPad・Apple 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を省く結果となってしまった．

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

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

2017-06-01

今日の気づいたこと

Keywords

今日思いついたことについてキーワードを残しておく．

Bonjour Zeroconf nmap mDNS(Multicast DNS) ICMP APNs

2017-05-19

パターン認識と機械学習 05/19/2017

Seminar PRML

2.3 ガウス分布

今回は自分の発表だった．

ガウス分布は多くの場面で出てくるため，しっかりと基本的な内容を伝えられるように努めた．

自分がこの範囲で興味を持ったところは共分散行列の性質で，対称行列としての性質や，対角行列になる際は対角の分散のみが残り，共分散が0であるため，相関がなくなることなどがとても納得できた．

対称行列の逆行列が対称行列になるか

という証明をラボメンの長野君がしてくれたため，記述しておく．

2017-05-17

Linear Algebra Chap2.5

LinearAlgebra Seminar

Challenge Problems

No.44

How does the identity $({\bf I}+{\bf AB})^{-1}{\bf A} = {\bf A}({\bf I}+{\bf BA})^{-1}$ connect the inverses of ${\bf I}+{\bf BA}$ and ${\bf I}+{\bf AB}$ ?