LU分解を使って連立一次方程式を解く方法

LU分解は係数行列Aを、A=LUと、上三角行列Lと下三角行列Uに分解して解くものでした。

例えば係数行列Aのサイズが3×3の場合は

と分解できます。

これを使って連立一次方程式

……式02

を解くには、

……式03

となるベクトルcをおいて、式02に代入し、

……式04

より、ベクトルcの値を求めます。この処理を前進代入といいます。

得られたベクトルcの値を式03に代入すると変数ベクトルxの値が求まります。この処理を後進代入といいます。

LU分解の方法

LU分解の方法はいくつかあります。 今回は片桐さんの資料でも並列化に向くと紹介されている、外積形式ガウス法を用いて計算を行います。

外積形式ガウス法は英語ではDoolittle algorithmと呼ばれています。 そのアルゴリズムは、ガウスの消去法と同様の操作でLU分解を行うというものです。以下でそのアルゴリズムを説明します。

n行n列の係数行列A、変数ベクトルx、定数項bを与えられ、これを解いていきます。

ガウスの消去法の前進消去は（n-1）個の変数を、1度の処理で1つずつAから削除していきます。 この削除の処理を何度行ったかわかりやすくするため、 削除処理を行った回数をAの上につけて表します。 初期状態では次のように定義されます。

……式05

次にA^(k-1)のとき、k行ｋ列の変数を削除する処理を考えます。

……式06

この削除処理は対角線上の係数a_kkを用いて列方向に行います。 この消去を列方向のインデックスi(i=k+1, k+2, …, n)を用いて表すと式07になります。

……式07

ここからは式07の処理を、行列で表していきます。

行列Lを式08と定義すると、A^(k)に対する消去は式09のように表せます。

……式08

……式09

この式09より、式07を行列式で表せました。

次に係数行列Aをガウスの消去法で削除していく全過程を式09を使って表します。つまり初期状態の A^(0) から A^(n-1) までの消去の式を式09を用いて表すと、次の式10となります。

……式10

この式10が終了する――つまりガウスの消去法の前進消去が終了すると、 上三角行列Uが得られます。 つまりは、

……式11

となり、上三角行列Uは求まります。

下三角行列Lは、逆行列L^(-1)の要素の符号を変転させたものなので、 容易にもとまります。

以上で、LU分解のアルゴリズムの説明を終わります。