LU 分解#

読み: えるゆーぶんかい
英名: LU Factorization

正方行列 \(A\) を下三角行列 \(L\) と上三角行列 \(U\) の積，\(A=LU\) に分解すること．\(A\) が正定値対称行列で \(L\) と \(U\) を \(U=L^\top\) に限定した場合にはコレスキー分解と呼ばれる．同じ構造の線型方程式を繰り返し解く場合などに用いられる．

\(A\) を LU 分解することで，線型方程式

(20)#\[Ax=b\]

は 2 つの線型方程式

(21)#\[\begin{split}\begin{array}{l} Ly=b \\ Ux=y \end{array}\end{split}\]

に分割される．\(L\) と \(U\) は三角行列であるため，これらの線型方程式はそれぞれ前進代入，後退代入だけで解くことができる．そのため，同じ \(A\) に対し，\(b\) だけを変えて何度も解く場合には，1 回あたりの計算量を抑えることができる．

通常，LU 分解のアルゴリズムにはガウスの消去法と等価な手法が用いられ，ガウスの消去法と同様にピボットの選択アルゴリズムには自由度が残されている．ピボットの選択アルゴリズムは，数値的安定性や選択に伴う計算量のほか，\(A\) が疎行列である場合には，分解後の行列の疎性等も考慮して設計される．

また，行列 \(A\) の LU 分解から，\(A\) に修正を加えた行列 \(A^\prime\) の LU 分解を高速に計算できる場合がある．特に，単体法の基底行列の LU 分解を更新する手続きは LU update と呼ばれ，高速化の重要な技術として知られている．