LU分解 - gggggraziegrazie

正方行列 $A$ を、下三角行列(Lower triangular matrix) $L$ と上三角行列(Upper triangular matrix) $U$ の積に分解する操作を指します。連立方程式の厳密解を求める際に使われます。また
$\begin{align} A_1 \vec{x} \ &= \ \vec{b_1} \\ A_2 \vec{x} \ &= \ \vec{b_2} \\ A_3 \vec{x} \ &= \ \vec{b_3} \\ \end{align}$
の様に左辺が変化する場合は、計算を各方程式毎に行う必要があるため、計算量が $O(n^3/3)$ となります（ガウスの消去法を使用）。一方
$\begin{align} A \vec{x} \ &= \ \vec{b_1} \\ A \vec{x} \ &= \ \vec{b_2} \\ A \vec{x} \ &= \ \vec{b_3} \\ \end{align}$
の様に左辺が一定の場合は、計算量を $O(n^2)$ 削減することができます。

参考文献

mathwords.net
LU分解 - [物理のかぎしっぽ]
http://ocw.nagoya-u.jp/files/58/05.pdf