LU分解アルゴリズムのおさらい
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行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分解のアルゴリズムの説明を終わります。