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