LU分解 行列A,L,U * Lは対角要素が全て1、対角要素より上の要素が全て0の下三角行列 * Uは対角要素は1とは限らない、対角要素より下の要素が全て0の上三角行列 A = LU Ax=b という方程式があれば、 LUx=b すなわちL(Ux)=b Ux=yとおくと、Ly=b LU分解は消去法を用いて行う。 P,,ij,,(α) = I + αe,,i,,e,,j,,^T^ Aの第j行にαをかけて第i行に加える操作: P,,ij,,(α)A = A + αe,,i,,e,,j,,^T^A P,,ij,,(α) について次の性質がある: * P,,ij,,^-1^(α) = P,,ij,,(-α) = I - αe,,i,,e,,j,,^T^ * P,,i'j,,(α')P,,ij,,(α) = I + (αe,,i,, + α'e,,i',,)e,,j,,^T^ 実際にLU分解を行うときには、行列P,,ij,,(α)をAにかけるような計算は計算が遅いためしない。代わりに、行どうしの消去の計算を行う。 一般に行列の次元がnのとき、方程式 Ly=b の解 y=(y,,1,,...,y,,n,,)^T^ は、i=1,2,...,nについて y,,i,,=(b,,i,,-∑,,j=1,,^i-1^l,,ij,,y,,j,,) また、方程式 Ux=y の解x=(x,,1,,...,x,,n,,)^T^は、i=n,n-1,...,1について x,,i,,=(y,,i,,- ∑,,j=i+1,,^n^u,,ij,,x,,j,,)×1/u,,ij,, 参考文献: http://www.math.meiji.ac.jp/~mk/lecture/suurikaisekitokuron/gauss-elimination.pdf