LU Decomposition
LU分解は行列 A を下三角行列 L と上三角行列 U の積 A=LU に分解する。繰り返しの線形方程式求解を高速化する。
目的
一度分解すれば、複数の右辺を持つ連立一次方程式を効率的に解けるようになる。
メカニズム
ガウス消去の行列形式であり、消去の過程から L（乗数）と U（消去結果）が得られる。Ax=b の求解は Ly=b（前進代入）と Ux=y（後退代入）になる。分解は O(n^3)、求解ごとに O(n^2) である。
ユースケース
- 連立一次方程式（linear system）を解く
- 行列の逆行列の計算（matrix inversion）
- 数値線形代数（numerical linear algebra）への応用