LU分解法-解法

こんばんは。

よっしんです。

昨日のLU分解について。

◇LU分解は何のためにある？

連立方程式を少ない計算量で解くためにあります。

(連立方程式は以下の形となります。)

基本的には以下のように行列Aを上三角と下三角の行列に分割することで、ほかの方法のような収束性の課題を抱えずに、連立方程式を解けるようになるということにメリットがあります。

◇計算のアルゴリズムについて

1. LとUの要素のうち、Lの0部、Uの対角成分と下三角の0部を定義する

2. LとUの非0の要素を1の条件を使って、ひとつずつ求めていく。

※パット見、非0の要素を綺麗に求めることは難しいように見えますが、実は可能です。その理由は、求める際に使う各項が1より1か0であることが保証されているから。

3. 連立方程式を以下のように書き換えます。

最終ほしいのは連立方程式の解xなんですが、その前にyを導入してしまいます。

その理由は4以降で分かります。

4. yを求める

Ly=bを解きます。

Lの形を見てください。上から△です。

つまり・・・

y1はl11×y1=b1で求まります。

y2はl21×y1+l22×y2=b2で求まるのですが。y1が上で分かっているので、実際にはy2も単なる1次連立方程式を解けば良いことになります。

これをyベクトル、すべての要素で繰り返します。

→yが全部わかります。

5. xを求める

Ux=yを解きます。

4と同じことが言えます。

上から求めていくと、単純な1次方程式を解き続ければ解までたどり着きます。

◇効果

計算量が圧倒的に少ないです。

他のガウス法がO(3)なのに対し、LU分解法はO(2)です。

連立方程式のサイズが大きければ大きいほど、効果は大きくなります。