1、LU分解的代数理论 记P(j为单位矩阵第行与第/行交换后的矩阵 a(k+1,k) a(kk) a(n, k) a(k, k) kk(k)=k+kk-1,其中kk为qkk]=max(abs(a(k:n,k)) 1
1: 1. ( ) 1, [ , ] max( ( ( : , ))). . 1 ( , ) ( , ) 1 ( , ) ( 1, ) 1 1 P(i, j) i = − = + − = − + = − k n k k k k k k k k q k k abs a k n k a k k a n k a k k a k k L j k 其中 为 记 为单位矩阵第 行与第 行交换后的矩阵， 1、LU分解的代数理论
于是: 2 13 LPA an, L2rLPA 33 n 3 12 13 2223…·a2n Lm_P-Ln-pn-2.L2P2LPA U 其中,P=P(k,k(k
( , ( )). , 3 3 3 2 2 2 3 2 1 1 1 2 1 3 1 1 1 2 2 2 2 1 1 3 3 3 3 2 2 2 3 2 1 1 1 2 1 3 1 2 2 1 1 2 3 2 3 2 2 2 1 1 1 2 1 1 1 P P k k k k U a a a a a a a a a a L P L P L P L P A a a a a a a a a a a a L P L P A a a a a a a a a a L P A k n n n n n n n n n n n n n n n n n n n n n = = = = = − − − − 其中， 于是：
Ln-Pn-lln-aPn-2.L2PLPA=U (Ln-1)(Pn=1Ln-2Bn-1)(Pn=1P2=2Ln=3n=2P21) (Pn-1…Bk+2Bk+1Lkfk+1Rk+2…B-1) (Pn-1…P2L1P2…Pn (Pn-1P2…B)A=U n n-1 2 n-1 k=Pn-1…Bk+2B+1LkP2k+1k+2…P21, 1=Pn1…P2L1P2…P
. . ~ , , ~ , , ~ , ~ ( ) ; ( ) ( ) ( )( )( ) 1 2 1 1 1 2 1 2 1 1 2 1 1 2 1 1 1 2 1 2 1 1 2 1 1 2 1 2 1 1 2 1 1 2 1 1 1 2 1 1 2 3 2 1 1 1 2 2 2 2 1 1 P P P P L P P L P P L P P P L P P P L L L P L P P P P A U P P L P P P P P L P P P L P L P P P L P P L P L P L P L P A U n n n k n k k k k k n n n n n n n n n n n n k k k k k n n n n n n n n n n n n n n − − − − + + + + − − − − − − − − − − − − + + + + − − − − − − − − − − − − − − = = = = = = = 令：
2…L1PA=U →PA=LU,其中L=L1…Ln2Ln1 可以证明L为单位下三角矩阵 现在我们只要将列主元高斯消去法稍加改造即是LU分解 的算法 列主元高斯消去法的矩阵表示: "+1y+5y…)一手1r 即妹上三思一平(+:I)h 趣用即距妹下三电n KH()一1B=b(Y() "-b-3b-5…bb=
. ~ ~ ~ , . ~ ~ ~ 1 1 1 2 1 1 1 2 1 可以证明 为单位下三角矩阵。 其中 L PA LU L L L L L L L PA U n n n n − − − − − − − = = = 现在我们只要将列主元高斯消去法稍加改造即是LU分解 的算法。 列主元高斯消去法的矩阵表示： , , , ) . ( 1: , ) U ( ) ( , ( )) . ' 1, 2, 1 1 2 2 2 2 1 1 k k k k n k k k n n n n a a a L A A k n k A k k k P P k k k k L P L P L P L P A U （ 唯一确定了 输出的矩阵 的下三角的每一 部分，即 输出的矩阵 的上三角为 ； 唯一确定了 ； + + − − − − + = =
2、LU分解算法 function kk, a= gAuss(a) [m, n]=size(a) for k=l: n [9, m]=max(abs(a(k: n, k)) kk(k)=k+m-1 ta=a(k, k:n) a(k, k: n)=a(kk(k),k: n) a(kk(k),: n)=to fori=k+l:n a(i,k=a(i, k)/a(k, k) 运算量和高斯消去法一样 forj=k+l:n ali,j=a(i,j-a(i, k)a( k nd end
2 、LU分解算法 end end end a i j a i j a i k a k j for j k :n a i k a i k a k k fori k n a k k k k n t a a k k n a k k k k n t a a(k,k:n) ; k k k k m q m abs a k n k for k n m n size a function k k a LGauss a ( , ) ( , ) ( , ) ( , ); 1 ( , ) ( , )/ ( , ); 1: ( ( ), : ) ; ( , : ) ( ( ), : ); ( ) 1; [ , ] max( ( ( : , ))); 1: 1 [ , ] ( ); [ , ] ( ) = − = + = = + = = = = + − = = − = = 运算量和高斯消去法一样