2.5 LU decomposition (2) L と U の性質

今回も LU 分解の続きである．線形代数に興味のない方は残念ですが，飛ばすとよいでしょう．

前回は Elimination matrix のかけ算の結果 $L$ はもとの Elimination matrixの要素それぞれの符号反転であることを見た．それがどうした，というかもしれないが，行列の掛け算の答えが，掛け算せずにわかるというのは便利なものだ．

まずは一つ最初に注意しておこう．前回のL = (E_{32} E_{31} E_{21})^{-1}では，各要素の数が符号の反転だけで保存されていた．しかし，これは (E_{32}E_{31} E_{21}) では保存されない．Lという逆行列の時に保存されることに注意すること．実際に，

であって，E_{31}は保存されていない．(この例ではE_{31}だけ符号が反転しているだけに見えるが，Gilbert Srang の本の 103 の問題 8 を解けばそれだけではないことがわかる．)

これは直感的には左から作用する行列の row に関する性質による．2 x 2 の行列で説明してみよう．2 x 2 の Elimination 行列(E_{21})は下三角では式7のようになる．これは式8 に示すような列に対する操作として考えるとわかりやすい．連立一次方程式を解く時に第1行にl_{21}を掛けて第2 行に加えるということと同じである．この逆行列が式9となることは 2x2 の行列の逆行列の公式からもわかるが，考えてみれば，第1 行にl_{21}をかけたもの(l_{21}a_{r_1})を引けば，l_{21} a_{r_1} + a_{r_2} - l_{21} a_{r_1} = a_{r_2}のように元に戻ることはわかると思う．2 x 2 の場合には，逆行列の公式が使えるから，こんな他の解釈は別にいらないという考えもあるだろう．学校での試験では直接一般の2 x2 の逆行列が求まる公式は使えるが，このrow に関する操作という考えは，行列の大きさによらないところが優れている．つまり，この考えは Elimination 行列でしか使えないのではあるが，3 x 3, 4 x 4, そして n x n でも成立するところが優れている．そして一般の問題は n x n である．

L,U は Elimination の性質から，必ず 0 になる部分が以下のようになる．

L は下半分(Lower)に 0 でない要素が，U は上半分(Upper)に 0 でない要素が並ぶが，L の下半分にたまたま 0がある場合，U の上半分にたまたま 0がある場合には以下の性質がある．(Gilbert Strangの本のp. 96を参照)

1. 行列 A の行が 0 からはじまる場合，L も同様である
2. 行列 A の列が 0 からはじまる場合，U も同様である

まず 1. は既に Elimination が終わっているから0になる．なぜならElimination は 0 でない要素を消去する方法であったので，要素が 0 になっていたらもう Elimination をする必要がない．だからその要素は 0 になる．次に2. は，Elimination が行の上の方から作用することに関係している．たとえば，U の 3 行は A の 3 行から 1 行と2行の linear combination を引くことでelimination される．すると，行列の上の方に 0 があれば，その linearcombination も 0 であるから( l_{31} t0 + l_{32} 0 + 0 = 0)，2. が成立する．

さて，結局やっていることは Elimination である．なぜ Eliminationそのものを実行して終わりではなく，LU 分解という形に変形するのであろうか? 私が理解する限りでは，2つの理由がある．次の回ではようやくその理由，なぜ消去法で答えがわかるのにもっとややこしい LU 分解などというものをするのか，について話をしたいと思う．

レストランの三人の客 in German

私の好きなクイズがドイツ語になりました(Isabelleさんの協力に感謝します．)

Drei Gäste im Restaurant


Wir (ich, Isabelle, und mein Freund) waren in einem Restaurant. Wir nahmen ein Menue. Es kostete 300 Euro. Der Kellner kassierte das Geld von uns und ging in die Kueche zurück, dann sagte der Chef: ,,Heute ist der Jahrestag des Restaurants, also kostet das Menu nur 250 Euro''. Der Kellner kam an den Tisch zurück, aber er dachte: ,,Man kann 50 Euro nicht durch drei Personen teilen''. Dann sagte er: ,,Heute ist unser Jubilaeums Tag, also bekommen Sie 30 Euro zurück''. Jeder bekam 10 Euro. Wir dankten dem Kellner und gingen nach Hause. Der Kellner fühlte sich ein bisschen schuldig, aber er entscheied es zu vergessen. Aber, er bemerkte etwas seltsam. ''Jeder bezahlt 90 Euro, also ist die Summe 270. Ich habe 20 Euro von ihnen. Die Summe ist 270 plus 20 gleich 290. Aber zuerst bekam ich 300 Euro.'' Der Kellner schrieb:

Jeder bezahlt 90 x drei = 270
+ Ich habe 20
-----------------------------------------
Summe 290

Wo sind denn die 10 Euro?

なぜ LU 分解というものを考えるのか (1)

Gilbert Strang's Introduction to Linear Algebra 2.5

LU 分解という手法がある．日曜研究家の常として，まずは基本的な質問からはじめることにしよう．

- LU 分解とは何か?
- なぜそんなものを考えるの?

LU 分解とは表現が違うだけで Elimination (消去法) そのものである．なぜEliminationを行うのか．それは方程式を解きたいからである．問題が何かがわかることはとても重要であるが，答えが出てこないのではちょっと残念である．答えも欲しい．Elimination は線型方程式で答えを求める方法の一つである．Eliminationは式から式の定数倍を足したり引いたりして，特定の項を消していく．日本の中学校では，連立一次方程式の消去法という名前でこれを習う．まずは次の行列A を例題に使って Elimination が何かを示そう．

A の a_{21}, a_{31}を次の Elimination 行列 E_{21}, E_{31}を用いて消去する．たとえば，E_{21}は a_{21} を消去するために，第1行を第2行から引くので，E_{21} の 21 成分が -1になっており，残りの要素は単位行列である．E_{32} はこの時点ではまだわからない．

Note: Ameba では画像が切れてしまうので画像をクリックして画像全体を御覧下さい．

a_{21}, a_{31} を消去した結果，E_{21} E_{31} Aは次のようになる．

ここでやっとa_{32}の 2 を消去すれば三角行列になることがわかるので，E_{32}がどんなものかわかった．E_{32}を用いてa_{32}を消去すると結果は以下のようになる．

これが，LU 分解の L, U である．

ところで，L = (E_{32} E_{31} E_{21})^{-1} の要素を眺めると，それが符号が反転された値になっていることに気がつくだろう．対応する(符号の反転した)要素を同じ色で表現してみた．

この色の対応には私はちょっと驚いた．実際に行列のかけ算を計算しなくても結果がわかってしまう．なんと便利なことであろうか．次回はどうしてこの色の対応があるのかを考えてみたい．