前へ / 戻る / 次へ

ガウスの消去法と LU 分解法の実行時間比較

　加減乗除の四則演算の実行時間は、乗算と除算が同程度、加法・減法の実行時間はそれに比べると大したことはありません ( 今日の６ページ目参照 ) 。 従って、加減乗除で構成されているプログラムの実行時間は、その中の乗算・除算の回数で見積ることができます。 サイズ $n$ のガウスの消去法と LU 分解法で用いられる乗算・除算の回数は凡そ次の通りです。

	Step 1	Step 2	Step 3	合　計
ガウスの消去法	$\dps{\frac{1}{3}n^3}$ 回	$\dps{\frac{1}{2}n^2}$ 回	な　し	$\dps{\frac{1}{3}n^3+\frac{1}{2}n^2}$ 回
LU 分解法	$\dps{\frac{1}{3}n^3}$ 回	$\dps{\frac{1}{2}n^2}$ 回	$\dps{\frac{1}{2}n^2}$ 回	$\dps{\frac{1}{3}n^3+n^2}$ 回

これだけをみるとわざわざ LU 分解する理由がわかりませんが、

LU 分解法の利点

こんな状況を考えてください：

• $A$ は固定されていて
• たくさんの $\bbb$ について $A\xxx=\bbb$ を解きたい

このとき、ガウスの消去法では $\bbb$ が変わるごとに拡大係数行列 $(A\ \bbb)$ も変わってしまいますので Step 1-2 を実行しなければなりません。 これに対し、LU 分解法の Step 1 は $\bbb$ を使いませんので、2 つ目以降の $\bbb$ については Step 2-3 のみ実行すればよく、 乗算・除算の回数は凡そ $n^2$ となります。 すなわち、2 つ目以降の $\bbb$ についての実行時間は、ガウスの消去法の方が $\dps{\frac{(\frac{1}{3}n^3+\frac{1}{2}n^2)}{n^2}}$ ≒ $\dps{\frac{1}{3}n}$ 倍も掛かってしまいます。巨大な行列、たとえば $n=10000$ になるとその比は $3333$ 倍、1 秒と1時間位の差になります。

前へ / 戻る / 次へ