LU分解
連立1次方程式
A x = b {\displaystyle A{\boldsymbol {x}}={\boldsymbol {b}}}
の解き方に、行列 A を LU分解する方法がある。L , U は下三角行列、上三角行列であるため、逆行列を求めることなく計算することが可能である。このため、同じA に対しb だけを変えていくつも連立方程式を解く場合、LU分解は有用である。
与えられた方程式
A x = L U x = b {\displaystyle A{\boldsymbol {x}}=LU{\boldsymbol {x}}={\boldsymbol {b}}}
に対し、変数y を
U x = y {\displaystyle U{\boldsymbol {x}}={\boldsymbol {y}}}
とおき、これを上式に代入する。
L y = b {\displaystyle L{\boldsymbol {y}}={\boldsymbol {b}}}
から変数y を求める。求めた解y をUx = y の右辺に代入し、解 x を求めることができる。
Ly = bはガウスの消去法の前進消去、Ux = yは後退代入に対応する。
以下、n 次正方行列の場合で説明する。基本的にはA = LU の各成分について書き下した n 個の式を解くことにより、行列 L , U を求めるのだが、このままでは未知の係数の個数(n (n + 1) 個)が式の個数(n個)より多いので解けない。これを解くための解法には ドゥーリトル法 と クラウト法 の2つがある。
ドゥーリトル法では、行列 L の対角成分の全てを 1 とおき、(1, 1) 成分 , (2, 1) 成分 , (3, 1) 成分 , ... , (1, 2) 成分, (2, 2) 成分, ... の順に n 個の式を解く。
クラウト法では、行列 U の対角成分の全てを 1 とおき、(1, 1) 成分 , (1, 2) 成分 , (1, 3) 成分 , ... , (2, 1) 成分, (2, 2) 成分, ... の順に n 個の式を解く。