LU 分解による連立一次方程式の解法
前回は,ガウスの消去法について,簡単に説明した.今回は,LU 分解について説明する.
LU 分解
行列 は正則行列(逆行列を持つもの)であるとする.このとき,行列 を部分ピボット選択をする(この行列を とする)ことにより,
のように LU 分解できる.ここで,L,U はそれぞれ,
である.ここから, を解くことを考える.まず, を解く.すなわち,
を解くことになる.ここで, は,部分ピボット選択により,入れ替えたものを表す.入れ替えが行われなかった場合は, である. この方程式は,前進代入で解くことが出来る.つまり,
で求められる.次に, を解く.すなわち,
を解く.これは,ガウスの消去法のときと同様に,後退代入で解くことが出来る.つまり,
で求められる.
アルゴリズム
これを,C 言語で書き下すと以下のようになる.
参考文献
ガウスの消去法,LU 分解 http://www.ms.u-tokyo.ac.jp/~narutaka/lec/lud.pdf
LU 分解法 http://www.kata-lab.itc.u-tokyo.ac.jp/OpenLecture/SP20121218.pdf