wiki:GB12301/2013-06-11

LU分解

行列A,L,U

  • Lは対角要素が全て1、対角要素より上の要素が全て0の下三角行列
  • Uは対角要素は1とは限らない、対角要素より下の要素が全て0の上三角行列

A = LU

Ax=b という方程式があれば、 LUx=b

すなわちL(Ux)=b

Ux=yとおくと、Ly=b

LU分解は消去法を用いて行う。

Pij(α) = I + αeiejT

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

Pij(α)A = A + αeiejTA

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

  • Pij-1(α) = Pij(-α) = I - αeiejT
  • Pi'j(α')Pij(α) = I + (αei + α'ei')ejT

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

一般に行列の次元がnのとき、方程式 Ly=b の解 y=(y1…,yn)T は、i=1,2,…,nについて yi=(bi-∑j=1i-1lijyj)

また、方程式 Ux=y の解x=(x1…,xn)Tは、i=n,n-1,…,1について xi=(yi- ∑j=i+1nuijxj)×1/uij 参考文献: http://www.math.meiji.ac.jp/~mk/lecture/suurikaisekitokuron/gauss-elimination.pdf

Last modified 6 years ago Last modified on 06/11/2013 09:55:04 AM