第二节矩阵的三角分解 LU分解法 用n=3的情况分析Ga顺序消去法的消元 过程,从而导出一些很有用的结论。 b a21 a22=[A b] 3132a 33 2 b2)=40|b0) (1)|h(1) 32 33 第一步中,设a1≠0,小小=(=2,3) 将第二行和第三行分别减去第一行的l21倍和 l31倍。事实上第一步得到的结果,可以表述为 个初等矩阵与[Ab的乘积。 2 0a20a20-1×=M14b )么2小房) (1
42 第二节 矩阵的三角分解 一、LU 分解法 用 n = 3 的情况分析 Gauss 顺序消去法的消元 过程，从而导出一些很有用的结论。 11 12 13 1 21 22 23 2 31 32 33 3 [ | ] a a a b a a a b A a a a b = b 11 12 13 1 1 (1) (1) (1) (1) (1) 22 23 2 (1) (1) (1) 32 33 3 0 [ | ] 0 a a a b a a b A a a b → = b 第一步中，设 0 11 a ，令 1 1 11 i i a l a = ， ( 2,3) i = 将第二行和第三行分别减去第一行的 21 l 倍和 31 l 倍。事实上第一步得到的结果，可以表述为一 个初等矩阵与 [A | b] 的乘积。 11 12 13 1 (1) (1) (1) (1) 22 23 2 21 (1) (1) (1) 31 32 33 3 1 0 1 [ | ] 0 0 1 a a a b a a b l A M A a a b l = − = − b b
将第一步的结果再进行第二步消元: 12 3|b 令 (1) 22 23 r3-1 43b3 12a13b 00 (2)h1(2) 2 13 a1a42a13|b )。()n() (1)h(l) 22 23 (2)bh(2)0 ()(①)h(1) M (2)(1)p(1 由此可见,消元过程相当于下述矩阵乘法运算 M2MOJAb1=JUly 由分块矩阵乘法可得 2M①A=UM2M0b= 令 L=(M2M0)=(M)(M(2) 直接计算知
43 将第一步的结果再进行第二步消元： (1) 22 (1) (1) 32 32 22 3 32 2 11 12 13 1 0 (1) (1) (1) 22 23 2 (1) (1) (1) 32 33 3 0 0 a l a a r l r a a a b a a b a a b = − ⎯⎯⎯⎯⎯⎯→ 令 11 12 13 1 (1) (1) (1) 22 23 2 (2) (2) 33 3 0 0 0 a a a b a a b a b = U y 11 12 13 1 11 12 13 1 (1) (1) (1) (1) (1) (1) 22 23 2 22 23 2 (2) (2) (1) (1) (1) 32 33 3 32 33 3 (2) (1) (1) 1 0 0 1 0 0 0 0 0 1 | a a a b a a a b a a b a a b a b a a b l M A = − = b 由此可见，消元过程相当于下述矩阵乘法运算 (2) (1) M M A U | | b y = 由分块矩阵乘法可得 (2) (1) (2) (1) M M A =U M M b = y 令 (2) (1) 1 (1) 1 (2) 1 ( ) ( ) ( ) − − − L = M M = M M 直接计算知
12 13 L=l,11 22 令 21 23 则:A=LU y=6 我们称之为矩阵A的LU分解或三角状分解 其中L是单位下三角矩阵,U是上三角矩阵。这种 解方程组的方法称为LU分解法或三角状分解法。 ( Doolittle分解方法) 因此,只要消元过程能进行到底,就有如下等 价关系 Ax=b<4=1Lx=b<令 Lv=b 消元过程即是将A分解成单位下三角阵L与上三角 阵U的乘积,解方程组Ly=b;回代过程即是解方 程 Ux=yo 以此类推可得n阶矩阵A的LU分解,其中
44 令 = 1 1 1 31 32 21 l l L l ， = (2) 33 (1) 23 (1) 22 11 12 13 0 0 0 a a a a a a U 则： A LU = Ly = b 我们称之为矩阵 A 的 LU 分解或三角状分解。 其中 L 是单位下三角矩阵， U 是上三角矩阵。这种 解方程组的方法称为 LU 分解法或三角状分解法。 （Doolittle 分解方法） 因此，只要消元过程能进行到底，就有如下等 价关系 = = = ⎯= ⎯→ = ⎯= ⎯→ U x y Ly b Ax b LUx b A LU 令y U x 消元过程即是将 A 分解成单位下三角阵 L 与上三角 阵 U 的乘积，解方程组 Ly = b ；回代过程即是解方 程 Ux = y 。 以此类推可得 n 阶矩阵 A 的 LU 分解，其中
下面给出关于矩阵A的LU分解的存在唯一性条件 的两个定理。 定理2若矩阵A非奇异,则A能分解为LU的充 分必要条件是A的顺序主子行列式不为0,即 △1=a1≠0 ≠0 detA)≠ 定理3若非奇异矩阵A有LU分解,则此分解 是唯一的。 为简化LU分解,下面通过比较元素法导出 个直接求L与U的元素的公式。 令 A=LU/
45 = 1 1 1 1 2 21 n n l l l L = ( −1) (1) 2 (1) 22 11 12 1 n nn n n a a a a a a U 下面给出关于矩阵 A 的 LU 分解的存在唯一性条件 的两个定理。 定理 2 若矩阵 A 非奇异，则 A 能分解为 LU 的充 分必要条件是 A 的顺序主子行列式不为 0，即 0 0 det( ) 0 1 1 1 1 2 1 2 2 1 1 1 2 1 = 1 1 2 = = = A a a a a a a a a a n n n n n 定理 3 若非奇异矩阵 A 有 LU 分解，则此分解 是唯一的。 为简化 LU 分解，下面通过比较元素法导出一 个直接求 L 与 U 的元素的公式。 令 A = LU 。 即
n 21 22 21 u. n-1 比较第一框得: 假设前k-1框元素已求出,则由 ∑ka u: +u (j=k,k+1,…,n) u tlu k(i=k+1,k+2,…,n) 得 ∑ j=k,k+1 1=1a1k kk =k+1,k+2,…,n., a
46 = − n n n n n n n n n n n n n u u u u u u l l l a a a a a a a a a 1 0 1 1 0 2 2 2 1 1 1 2 1 1 1 2 1 1 2 2 1 2 2 2 1 1 1 2 1 比较第一框得： = = = = / , 2,3, , . , 1,2, , , 1 1 11 1 1 l a u i n u a j n i i j j 假设前 k −1 框元素已求出，则由 − = − = = + = + + = + = + 1 1 1 1 ( 1, 2, , ) ( , 1, , ) k s i k i s s k i k kk kj k s kj ks s j a l u l u i k k n a l u u j k k n 得 = − = + + = − = + − = − = [ ]/ , 1, 2, , . , , 1, , , 1 1 1 1 l a l u u i k k n u a l u j k k n kk k s i k i k i s s k k s kj kj ks s j ， （a）
计算的规律性:计算时,除用到ak外, 仅用到前k-1框中与它位于同一行的k与同一列 的ly的乘积之和;而计算k时,规律与“一样, 只不过最后还要用4k除一下。因此可以按下图所 示逐框求出矩阵A的LU分解,这种计算方法称紧 凑格式。 例求A的LU分解,其中 214 A=441 6512 解:用紧凑格式法 l12=a12=1 l13=a13=4 22=a l21·u1 2 11 2 33=43-l31l13-132:l23 7
47 计算的规律性：计算 ukj 时，除用到 akj 外， 仅用到前 k −1 框中与它位于同一行的 ks l 与同一列 的 sj u 的乘积之和；而计算 ik l 时，规律与 kj u 一样， 只不过最后还要用 kk u 除一下。因此可以按下图所 示逐框求出矩阵 A 的 LU 分解，这种计算方法称紧 凑格式。 例 求 A 的 L U 分解，其中 = 6 5 12 4 4 1 2 1 4 A . 解： 用紧凑格式法 u11 = a11 = 2 u12 = a12 =1 u13 = a13 = 4 2 7 2 22 22 21 12 23 23 21 13 11 21 21 = − = − = = − = = u a l u u a l u a a l 7 1 3 33 33 31 13 32 23 22 32 31 12 32 11 31 21 = = − − = − = = = u a l u l u u a l u l a a l
214 A=LU=2 1 将矩阵A进行LU分解后,解线性方程组Ax=b 转化为依次解下三角方程组L=b与上三角方程组 Ux=y, by nn-I 得同解方程组 21y+ 2 b2 解得从k=bk∑kys(k=1,2,…m) 解Ux=y
48 − = = 7 2 7 2 1 4 3 1 1 2 1 1 A LU 将矩阵 A 进行 LU 分解后，解线性方程组 Ax = b 转化为依次解下三角方程组 Ly = b 与上三角方程组 Ux = y ， 1 1 21 2 2 1 1 1 0 1 1 n nn n n y b l y b Ly l l y b − = = 得同解方程组： 1 1 21 1 2 2 n n n n 1 1 2 2 y b l y y b l y l y y b = + = + + + = 解得 1 1 ( 1,2, , ) k k k ks s s y b l y k n − = = − = 解 Ux = y
2 nx2y2 得同解方程组: 11x1+v12x2+…+1nxn=y l22+…+l2nxn=y2 nn n xk=(k-∑ usx 1.n k+1 -∑ (k=1,2,…,n) S=1 xk=(yk-∑ukx,)(k=n,n-1,…1) S=k+1 优点: 1、当要解多个系数矩阵为A的线性方程组时,只 要对系数矩阵做一次LU分解,以后只要解三角
49 11 12 1 1 1 22 2 2 2 0 n n nn n n u u u x y u u x y u x y = 得同解方程组： 11 1 12 2 1 1 22 2 2 2 n n n n nn n n u x u x u x y u x u x y u x y + + + = + + = = 1 ( ) ( , 1, ,1) n k k ks s s k x y u x k n n = + = − = − = − = − = − = = + − = ( ) ( , 1, ,1) ( 1,2, , ) 1 1 1 x y u x k n n y b l y k n n s k k k ks s k s k k ks s 优 点： 1、当要解多个系数矩阵为 A 的线性方程组时，只 要对系数矩阵做一次 LU 分解，以后只要解三角
形方程组即可; 2、可以根据系数矩阵的形状来设计算法 缺点 、lk不能为0; 2、uk的绝对值很小时误差会很大,数值不稳定。 原因:LU分解法的实质是高斯消去法。 例:用LU分解法解方程组 1648 45-4 8-422八(x 10 解:用紧凑格式 16 4 164 2 4-2=-6 4-2-3 32 NW2-4_9=9 矩阵A的LU分解式为:
50 形方程组即可； 2、可以根据系数矩阵的形状来设计算法。 缺 点： 1、 kk u 不能为 0； 2、 ukk 的绝对值很小时误差会很大，数值不稳定。 原因： LU 分解法的实质是高斯消去法。 例：用 LU 分解法解方程组 − − 8 4 22 4 5 4 16 4 8 3 2 1 x x x = − 10 3 4 解：用紧凑格式 11 12 13 21 22 23 31 32 33 16 4 8 4 1 5 1 4 4 2 6 16 4 8 1 4 2 3 22 4 9 9 16 2 4 2 u u u l u u l l u = = = = = = − = = − − = − − − − = = = = = − − = 矩阵 A 的 LU 分解式为：
1648 1/41 1/2-3/2 4 3→ 4 由 1/2-3/2 18 1648x1 4 9/4 4→ 再由 18 xxx 课堂练习: 对矩阵A作LU分解,A87210 4836 1261120 4215 结果,21
51 − − 9 4 6 16 4 8 1/ 2 3/ 2 1 1/ 4 1 1 。 由 − = − = − 18 4 4 10 3 4 1/ 2 3/ 2 1 1/ 4 1 1 3 2 1 3 2 1 y y y y y y ， 再由 − = − = − 2 4 9 / 4 18 4 4 9 4 6 16 4 8 3 2 1 3 2 1 x x x x x x 。 课堂练习： 对矩阵 A 作 LU 分解， 4 2 1 5 8 7 2 10 4 8 3 6 12 6 11 20 A = 。 结果： 1 4 2 1 5 2 1 3 0 0 1 2 1 2 1 3 0 4 1 1 A =