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_ie_j^T

Aの第j行にαをかけて第i行に加える操作:

P_ij(α)A = A + αe_ie_j^TA

P_ij(α) について次の性質がある:

• P_ij^-1(α) = P_ij(-α) = I - αe_ie_j^T
• P_i'j(α')P_ij(α) = I + (αe_i + α'e_i')e_j^T

実際にLU分解を行うときには、行列P_ij(α)をAにかけるような計算は計算が遅いためしない。代わりに、行どうしの消去の計算を行う。

一般に行列の次元がnのとき、方程式 Ly=b の解 y=(y₁…,y_n)^T は、i=1,2,…,nについて y_i=(b_i-∑_j=1^i-1l_ijy_j)

また、方程式 Ux=y の解x=(x₁…,x_n)^Tは、i=n,n-1,…,1について x_i=(y_i- ∑_j=i+1ⁿu_ijx_j)×1/u_ij 参考文献: ​http://www.math.meiji.ac.jp/~mk/lecture/suurikaisekitokuron/gauss-elimination.pdf