计算方法 第二章解线性方程组的直接法 §24直接三角分解法
第二章 解线性方程组的直接法 §2.4 直接三角分解法
§24直接三角分解法 、基本的三角分解法( Doolittle法) 若m阶方阵A=(an)的顺序主子式D≠0,k=1,2,…,n 则由上节可知,A的LU分解A=LU存在且唯 k A kk =LU
§2.4 直接三角分解法 一、基本的三角分解法(Doolittle法) = ( ) ¹ 0, ij n´n Dk 若n阶方阵A a 的顺序主子式 k = 1,2,L, n 则由上节可知 , A的LU分解A = LU存在且唯一 ,即 ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ = n nk nn k kk kn k n a a a a a a a a a A L L M M O M L L M O M M L L 1 1 11 1 1 ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ = 1 1 1 1 1 L L M M O L M O n nk k m m m ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ × ( ) ( ) ( ) (1) 1 (1) 1 (1) 11 n nn k kn k kk k n a a a a a a O M L O M M L L = LU
上式可记为 11 1 A 1 根据矩阵的乘法原理,A的第一行元素a1为 =1,2,…,n A的第r行元素主对角线以右元素an(j=r…,n)为 ∑1v k=1 r=1,2
÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ = 1 1 1 1 1 L L M M O L M O n nr r l l l ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ × nn rr rn r n u u u u u u O M L O M M 11 L 1 L 1 ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ = n nr nn r rr rn r n a a a a a a a a a A L L M M O M L L M O M M L L 1 1 11 1 1 上式可记为 根据矩阵的乘法原理 , A的第一行元素 a1 j为 a1 j = u1 j j = 1,2,L, n A的第r行元素主对角线以右元 素arj ( j = r,L,n)为 å= = r k rj rk kj a l u 1 r = 1,2,L,n j = r,L,n
同样,由 11 Ir A=ar1 r+1,1 可知A的第r列元素主对角线以下元素an(=r+1…,m)为 ∑ i=r+1, k=1 =12,…,n-1 显然,厂=1时,an=lnln1i=2,3,…,n
÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ = + 1 1 1 1 1,1 L L M M O L M O n nr r l l l ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ × nn rr rn r n u u u u u u O M L O M M 11 L 1 L 1 ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ = n nr nn r rr rn r n a a a a a a a a a A L L M M O M L L M O M M L L 1 1 11 1 1 同样,由 可知A的第r列元素主对角线以下元素 air (i = r + 1,L,n)为 å= = r k ir ik kr a l u 1 r = 1,2,L, n - 1 i = r + 1,L, n 1 1 11 显然, r = 1时 , ai = l i u i = 2,3,L,n
综合以上分析,有 1,2 1 111 r+1, r=1,2…,n 1,2 H-1 an=21b+1 L4.+l.4 k=1 因此可以推导出 j=1,2,…,n U的第一行 il 2,3,…,n L的第一列--(2
综合以上分析,有 a1 j = u1 j j = 1,2,L, n å= = r k rj rk kj a l u 1 r = 1,2,L, n j = r,L,n å= = r k ir ik kr a l u 1 r = 1,2,L,n - 1 i = r + 1,L, n 1 1u11 a l i = i i = 2,3,L,n 因此可以推导出 u1 j = a1 j j = 1,2,L, n U的第一行 11 1 1 u a l i i = i = 2,3,L,n L的第一列 rj r k rj rk kj a = ål u + ×u - = 1 1 1 ir rr r k ir ik kr a = ål u + l u - = 1 1 ------(1) ------(2)
∑ r=12…,nU的第行 k=1 ∑ur=1,2,…,mn-1 k=1 L的第r列-( i=r+1,…, 称上述(1)~(4)式所表示的分解过程为 Doolittle分解 A的 Doolittle分解A=LU中L为单位下三角阵U 思考 为上三角阵,如果将A=LU中的L表示为下三 盛 角阵,U表示为单位上三角阵,则称之为 Crout分 解,请找出类似于(1)~(4)式的表达式
å - = = - 1 1 r k rj rj rk kj u a l u r = 1,2,L,n j = r,L,n U的第r行 rr r k ir ik kr ir u a l u l å - = - = 1 1 r = 1,2,L, n - 1 i = r + 1,L, n L的第r列 ------(3) ------(4) 称上述(1) ~ (4)式所表示的分解过程为Doolittle分解 , (1) ~ (4) . , , 解 请找出类似于 式的表达式 角阵 表示为单位上三角阵 则称之为 分 为上三角阵，如果将 中的 表示为下三 的 分解 中 为单位下三角阵 U Crout A LU L A Doolittle A LU L U = = 思考
对于线性方程组 Ax=b 系数矩阵非奇异经过Doot分解后A=LU 线性方程组可化为下面两个三角形方程组 Ly=b Ux=y y为中间未知量向量 L=l21l21 -1,n-1 u 1 2
对于线性方程组 Ax = b 系数矩阵非奇异,经过Doolittle分解后 A = LU 线性方程组可化为下面两个三角形方程组 Ly = b Ux = y y为中间未知量向量 ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ = 1 1 1 1 1 2 3 31 32 21 L M M M O n n n l l l l l l L ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ = - - - nn n n n n n n u u u u u u u u u u U 1, 1 1, 22 23 2, 11 12 13 1, O M L L
由第一节三角形方程组的知识不难得到Ly=b的解: L. 1 21y L b-∑ r=23,…,n :1 1 因此再由Ux=y的解便得到Ax=b的解 u.X r+1 r=n-1,n-2…,2,1
由第一节三角形方程组的知识,不难得到Ly = b的解: 1 1 y = b å - = = - 1 1 r j r r rj j y b l y r = 2,3,L, n 2 2 21 1 y = b - l y 因此再由Ux = y的解便得到Ax = b的解 nn n n u y x = rr n j r r rj j r u y u x x å= + - = 1 r = n - 1,n - 2,L,2,1 ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ = 1 1 1 1 1 2 3 31 32 21 L M M M O n n n l l l l l l L ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ - - - nn n n n n n n u u u u u u u u u u 1, 1 1, 22 23 2, 11 12 13 1, O M L L
上述解线性方程组的方法称为 直接三角分解法的 Doolittle法 例1.用 Doolittle法解方程组 2100 3 10 3-4-1213 2 5 123 4 4149-13 解:由 Doolittle解 11 12 13l1 )=(2100-3) 14 1 21 =(1-1.5052
u1 j = a1 j 11 1 1 u a l i i = 上述解线性方程组的方法称为 直接三角分解法的 Doolittle法 例1. 用Doolittle法解方程组 ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ - - - - - - 4 14 9 13 1 2 3 4 3 4 12 13 2 10 0 3 ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ 4 3 2 1 x x x x ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ - = 7 2 5 10 解: 由Doolittle分解 ( ) u11 u12 u13 u14 = (2 10 0 - 3) ( ) T l l l 1 21 31 41 ( ) T = 1 - 1.5 0.5 2
0 22 3 4 11-128.5 an-∑lu k=1 32 2)=(01-3/11-6/1)s 0 )=(00-3/11-2/11) 00113=(001-9) 000a4)=(000-4) =y∑ 解Ly=b,得 )=(1020-17/11-16)
( ) 0 u22 u23 u24 = (0 11 - 12 8.5) ( ) T l l 0 1 32 42 ( ) T = 0 1 - 3/11 -6/11 ( ) 0 0 u33 u34 = (0 0 - 3/11 - 2 /11) ( ) T l 0 0 1 43 ( ) T = 0 0 1 -9 ( ) 0 0 0 u44 = (0 0 0 - 4) 解Ly = b,得 ( ) T y y y y 1 2 3 4 ( ) T = 10 20 - 17/11 - 16 å - = = - 1 1 r k rj rj rk kj u a l u rr r k ir ik kr ir u a l u l å - = - = 1 1