トップ > 数理計画用語集 > LU 分解

数理計画用語集

LU 分解

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

正方行列equationを下三角行列equationと上三角行列equationの積,equationに分解すること.equationが正定値対称行列でequationequationequationに限定した場合にはコレスキー分解と呼ばれる.同じ構造の線型方程式を繰り返し解く場合などに用いられる.

equationを LU 分解することで,線型方程式

equation

は2つの線型方程式

equation

に分割される.equationequationは三角行列であるため,これらの線型方程式はそれぞれ前進代入,後退代入だけで解くことができる.そのため,同じequationに対し,equationだけを変えて何度も解く場合には,一回あたりの計算量を抑えることができる.

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

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