西华师范大学：《算法与程序设计》课程教学资源_第二章 解线性代数方程组的直接方法（2.3）直接三角分解法

§23直接三角分解法 Gaussi消去法消元过程的矩阵描述 n A,b(1)= n1 n2 nn n 第一次消元相当于用初等矩阵 左乘(4(①),b(1) ),其中 i=2.3

一、Gauss消去法消元过程的矩阵描述 ( , ) (1) (1) A b             = (1) (1) (1) 2 (1) 1 (1) 2 (1) 2 (1) 2 2 (1) 2 1 (1) 1 (1) 1 (1) 1 2 (1) 1 1 n n n n n n n a a a b a a a b a a a b        第一次消元相当于用初等矩阵               − − = 1 1 1 1 21 1 n l l L   ( , ) (1) (1) 左乘 A b ，其中 i n a a l i i 2,3, , (1) 11 (1) 1 1 = =  §2-3 直接三角分解法

第k次消元相当于用矩阵 k+1,k nk (k) 左乘(6),b),其中k=i=k+1,3…,n lk 因此 1 L2·L1(4),b()=(40,b0 从而Ln1…L2·L1·A=A

第k次消元相当于用矩阵                     − − = + 1 1 1 1 , 1, n k k k k l l L    ( , ) (k ) (k ) 左乘 A b ，其中 i k n a a l k k k i k i k 1,3, , ( ) 1 ( ) = = +  ( , ) (1) (1) 1   L  A b  L2  Ln−1 ( , ) (n) (n) 因此 = A b 从而 Ln−1  L1  A (n)  L2  = A

故A=L1L2…Ln L=1,L2…L, 1,1 1,21n-1,2 n,1 n.2 n.n-1 为单位下三角矩阵 12 U=A(n)-= 27为上三角矩阵

1 ( ) 1 1 2 1 1 n L L L n A − − − − 故 A =  = LU   = = − − − − −− − − 1 1 1 1 1 . . . ,1 ,2 ,3 , 1 1,1 1,2 1,2 3 1 3 2 2 1 11 12 11 n n n n n n n n n l l l l l l l l l l L L L L       即 为单位下三角矩阵   = ( ) (2) 2 (2) 2 2 ( 1 ) 1 ( 1 ) 1 2 ( 1 ) 1 1 n n nnn a a a a a a    ( n ) U = A 为上三角矩阵

、矩阵的三角分解 定义1设A为n阶方阵,若存在下三角方阵L和上三角 方阵U,使得A=LU,则称方阵A有三角分解或LU分解。特 别,若L为单位下三角方阵,则称它为杜利特尔 Doolittle) 分解;若U为单位上三角方阵,则称它为克劳特( Crout)分 解 定理1若n阶方阵4=(an)m的顺序主子式D≠0, k=1,2,…,n则存在n阶单位下三角方阵L和上三角方阵U, 使得A=LU,即A有杜利特尔分解. 且detA=detU=∏a

二、矩阵的三角分解 定义1 设A为n阶方阵，若存在下三角方阵L和上三角 方阵U，使得A=LU，则称方阵A有三角分解或LU分解。特 别，若L为单位下三角方阵，则称它为杜利特尔(Doolittle) 分解；若U为单位上三角方阵，则称它为克劳特(Crout)分 解. 定理1 则存在n阶单位下三角方阵L和上三角方阵U， 使得A=LU，即A有杜利特尔分解. = ( )  0, 若n阶方阵A ai j nn 的顺序主子式Dk 且 det A = detU = = n i i aii 1 ( ) k = 1,2,  ,n

11 因此A=a 1 1 根据矩阵的乘法原理,A的第一行元素a1,为 j=1 A的第r行元素主对角线以右元素an(j=r…,n)为 n ∑ 丿∫

根据矩阵的乘法原理, A的第一行元素a1 j 为 a1 j = u1 j j = 1,2,  ,n A的第r行元素主对角线以右元素ar j ( j = r,  ,n)为 = = r k rj rkukj a l 1 r = 1,2,  ,n j = r,  ,n                 = 1 1 1 1 1         n nr r l l l                  nn r r r n r n u u u u u u       11  1  1                 = n nr nn r r r r n r n a a a a a a a a a A               1 1 11 1 1 因此

同样由A=|a1…a rn 11 1,1 可知A的第r列元素主对角线以下元素an(=r+1灬… r+1 ∑ 4 1 显然r=1时,an1=lnn1i=2,3,…,n

                = + 1 1 1 1 1,1         n n r r l l l                  nn r r r n r n u u u u u u       11  1  1                 = n nr nn r r r r n r n a a a a a a a a a A               1 1 11 1 1 同样,由 可知A的第r列元素主对角线以下元素 ai r (i = r + 1,  ,n)为 = = r k i r ikukr a l 1 r = 1,2,  ,n −1 i = r + 1,  ,n 1 1 11 显然, r = 1时 , ai = l i u i = 2,3,  ,n

因此可以推导出 l1=a1;j=12,…,n i11 i=23,…·,n ∑ k=1 ∑ ik kr k=1 i=r+1,…,n

u1 j 因此可以推导出 = a1 j j = 1,2,  , n 11 1 1 u a l i i = i = 2,3,  ,n  − = = − 1 1 r k rj rj rkukj u a l r = 1,2,  ,n j = r,  ,n r r r k i r i k kr i r u a l u l  − = − = 1 1 r = 1,2,  ,n −1 i = r + 1,  ,n

、直接三角分解法 对于线性方程组 Ax=6 系数矩阵非奇异,经过 Doolittle分解后A=L 线性方程组可化为下面两个三角形方程组 Lv=b 由 h b 22b2 Ly=L31 I32 1 y3 得到 V1 ∑l

三、直接三角分解法 对于线性方程组 Ax = b 系数矩阵非奇异,经过Doolittle分解后 A = LU 线性方程组可化为下面两个三角形方程组 Ly = b Ux = y 由                 =                                 = n n n n bn b b b y y y y l l l l l l Ly        3 2 1 3 2 1 1 2 3 3 1 3 2 2 1 1 1 1 1 1 b1 y =  − = = − 1 1 r j r r rj j y b l y r = 2,3,  ,n 得到

再由 l1 unix(yi Ux V3 解的方程组的解: nn y =r+1 r=n-ln

                =                                 = − − − n n n n n n n n n n y y y y x x x x u u u u u u u u u u Ux       3 2 1 3 2 1 1, 1 1, 2 2 2 3 2, 1 1 1 2 1 3 1, 再由 nn n n u y x = r r n j r r rj j r u y u x x = + − = 1 r = n −1,n − 2,  ,2,1 解的方程组的解：

直接三角分解的 Doolittle法可以用以下过程表示 2 15 11 12 13 14 21 23 24 2 35 31 33 34 42 45 41 42 43 44 1 12 13 u 14 r=1 22 24 34 3 42 44

              = 4 3 2 1 4 1 4 2 4 3 4 4 3 1 3 2 3 3 3 4 2 1 2 2 2 3 2 4 1 1 1 2 1 3 1 4 b b b b a a a a a a a a a a a a a a a a             4 5 3 5 2 5 1 5 4 1 4 2 4 3 4 4 3 1 3 2 3 3 3 4 2 1 2 2 2 3 2 4 1 1 1 2 1 3 1 4 a a a a a a a a a a a a a a a a a a a a               − → = 4 3 2 1 4 1 4 2 4 3 4 4 3 1 3 2 3 3 3 4 2 1 2 2 2 3 2 4 1 1 1 2 1 3 1 4 1 b b b y l a a a l a a a l a a a u u u u r 直接三角分解的Doolittle法可以用以下过程表示: