第二章 解线性代数方程组的直接法17 1) a 综合上述n一1步，我们得到 A=Aw=L1A2=…=L1L21…L,Aw (2-7) 由L:的定义和简单计算知 m: -m21 L1L21…L21= ma-1.1 mn-1,2 记 L=L1L22…L,U=Am 对照式(2-？)，矩阵A可以分解成单位下三角阵L和上三角阵U的乘积.这种分解过 程称为矩阵的Doolittle分解. 上述消元过程也可以通过下列直接的紧凑格式分解完成， 算法2.2矩阵A∈Rx"的Doolittle分解. 考虑分解 1 0 07 12 1 0 u22 A=: =:LU 0 … 1」L0 0
第二章 解线性代数方程组的直接法 17 1 α( ，， ".η-1 m..1I, n - 1 __, =一. (n- 1) 12 , 1 • • • L ,, _ J = mn,n-l 1 综合上述刀一1步，我们得到 A=AtDzLflAtD=…=LJILJ1…L二 (2-7) 1 • • • 1 ;l • • • • • • mn,; 1 1 m 21 1 1 • • • • • • • • • • • L~1 L;1 • ηt m ,,- I.l ，， 1， m n 1 ,n- l m '" m"l n ,l L=L~IL;2 ..·L , U=A( 对照式 成单 和上三 解过 程称为短阵的 l i tl 上述消元过程也可以通过下列直接的紧凑格式分解完成. 算法 li tl 考虑分解 U 1 " • • ... O U ll U 12 1 O ... • • • O • • • • • • I ZI 1 • • • =:LU U 22 • • • • • • • • • • • • • • • Un" • • • ... O • • • O O 1 • • • ln. ,, _ I ... •••••• A=
18第I部分数值分析 第1步用L的第1行乘U的第j(1≤≤n)列，再比较两边，得 ay=41,（j=1,2,…,n) 用L的第i(2≤i≤n)行乘U的第1列，再比较两边，得 aa=laun 于是 l知=aa/411,(i=2,3,…,n) 第2步用L的第2行乘U的第j(2≤j≤n)列，再比较两边，得 a2y=l21a1;十42j 于是 4,=a2-214j’（0=2,3,…,n) 用L的第i(3≤≤n)行乘U的第2列，再比较两边，得 a2=la412十l2u22， 于是 Lz=(a2-La21）/u22,(i=3,…,n) 依次下去，…，一直进行到第一1步，即已求出U的前k一1行和L的前k一1 列，那么 第k步用L的第k行乘U的第j(≤j≤n)列，再比较两边，得 a二L知1，十…十乙，m-1u-1,十4材 于是 6=a为-(L14十+l-14-1)，（G=k,k+1,,n） 用L的第i(k+1≤≤n)行乘L的第k列，再比较两边，得 a=La4十…十L:,k-1uk-1,十l认 于是 l=（a一la1k一…-L.k-1s-1k）/u,(i=k+1,…,n). 第n步用L的第n行乘U的第n列，再比较两边，得
18 值分析 1步用 L的第 l行乘 U的第 (l a1j=ul j , (j=1, 2 ,… ,n ) . L的第 (2~i~n) 两边 ail = Lil U ll ' 于是 Lil = ail / Un , (i= 2 ,3 ,… ,n ) 2步用 L的第 2行乘 U的第 )列，再比较两边，得 a2j =L21alj 十U j· U2j = a2j -L21Ul j , (j= ，3 L的第 (3 )行乘 U的第 2列，再比较两边，得 a i2= Lil 十L U2 2 , Li2= (a i2-(I U21)/U22' (i=3 ,…… ,n) 依次下去，……，一直进行到第 1步，即已求出 U的前 1行和 L的前 h一 列，那么 h步用 L的第 h行乘 U的第 (k~j~ζn) 较两 akj = LkI t n Ukj Ukj =a u lj +…+ Lk,k- l Uk- l ,) ' (j=k ,k + l, …,n) L的第 -:s )行乘 L的第 h列，再比较两边，得 a il< = LiI Ujk 十 … Li ，是 于是 il Ujk Uk jk (i= ••• n步用 L的第 n行乘
第二章解线性代数方程组的直接法19 am=乙a141n十十l,w-1uw-1,m十um 于是 un=am一ln41n十…十la-1-1 上述n步计算过程可以综合改写成如下的计算公式，对k=1,2,…n计算： 4=a,2 (j=k,k十1，…，n) a=（aa一含l。ua)/,(i=k+1,…,n) 在上式和本书的以后各处，都规定s从1到0求和（即）为零。 下面的结果给出了算法2.2可以分解到底的条件. 定理2.2如果非奇异矩阵A满足下列三个条件之一： 1)各阶顺序主子式 a1a1… 4,=::0+0,06=1,2…,0 a划a2…a lail>2ay 2) laal≥2lagl,，(i=2,…ni 3)对称正定， 则矩阵A可以进行Doolittle分解： A=LU, 并且这种分解是唯一的，其中，L为单位下三角阵，U为上三角阵. 证1)首先证明Doolittle分解的存在性，从算法2.1和算法2.2知，当a, a2,…,a均不为零时，Doolittle分解的计算过程可以进行到底，于是，我们仅需证 明如果条件1)，2)和3)之一成立，就有牛0(k=1,2,…,n)即可
第二章解线性代数方程组的直接法 aWl = i nl 十ln ，n-l U n- 1 Rn 于是 -inl U 1n + … l. 上述 η步计算过程可以综合改写成如下的计算公式，对 1， 2，… η计算: n 'R , J u-A ''iu -as u -• a (ail< - L i"u /uu , Ci= k+1,… ,n ) 在上式和本书的以后各处，都规定 5从 1到 O求和(即2:)为零。 下面的结果给出了算法 条件 定理 2如果非奇异矩阵 A满足下列三个条件之一: 1)各阶顺序主子式 • α11 a 12 ...αlk D.k = a ZI a ZZ …aZk • • • • • • • • • (k= 1，2 a k1 akZ …au 2) |α11l I, |α ii lazJ| , (i = 2, … ,n ) ; 3) 则矩阵 A可以进行 l i tl e分解: A=LU, 井且这种分解是唯一的，其中 L为单位下三角阵 U为上三角阵. 证1)首先证明 tt e分解的存在性，从算法 法2. aZ) Doolittle 分解 算 过程可 进行 我们 明如果条件1)， )和 )之一成立，就有 ，2
20第1部分数值分析 a aj2 … a) a a … a a a … a 0 a … A= a a … a 0 … a a出 … a 0 a … … … ai ai 0 … a =a州a…aw 因此，当△车0(k=1,2,…,n)时，有a牛0(k=1,2,…,n). 2》由假定条件知1=1ai1>名a,1≥0，即1牛0，经过一步消元过程 后，得到的矩阵形式为 an a] 0A2 由简单计算知A2中元素为 a8=a+mg=4,2au 并且，对角线元满足下列关系 盒l1a,+会a） ≤a+|a+e-a <2lal+lanl- 于是有a经牛0，同理可以证明a牛0，(k=3,…,n). 3)假如存在某个顺序主子式△.=0，则存在[名，…，之4]T士0满足
20 I部分 数值分析 a~~) II α0)12 ... (]) afl} II a <l ) 12 ••• G<I } 1* i::. k G <1 > 21 • • • (I) ak l ===…=== (I 22 • • • G{l > k2 G{]> 11 O • • • • • • O '" • • • '" (I) a l2 (2) 22 • • • •• • α(]) 2 是 • • • (]) αu ... .., • • • • • • ... O • • • O (I) al. k- I G <2) 2 ,k- l • • • (k-]) 1， O a(2) 22 • • • a <2 ) k2 1* G <2) 2k • • • (k-]) ak • J,k 〈的 αu • •• • • • ... G <2} 2k • • • G(2> kk (J) (2) (是} 二三 ll a22 …au 因此，当乌等 )时，有 i; 1 ,2 , … , n ) . 2) all| 经 过 一 步 元过 后，得到的矩阵形式为 由简单计算知 all O T a l A2 (2)__ (1 ) 1___ _(])__ ail 71 Gljzau-TG1J' ""11 并且，对角线元满足下列关系: 22|α ij ail GGIJ II 422|au l+ ail all ,2 2<la lj l +|GIg |-|GIg |> ail ail 一一 1; all ζlaul an --aJi "'11 ζI a~2) I 于是有 ，同理可以证明 3) 子式 '…，引了美
第二章 解线性代数方程组的直接法21 a1[z17 a22…a2 =0 Lak ak2 …a」L之 于是，有 a11 alk a1,k+1 a1w1[1 … an … a a,k+1 am ≥0， 0 Qx+l.1 … a,k+1 … a+1 40 L0」 a,k+1 这与A为正定阵矛盾.因此，A的各阶顺序主子式非零，由1)知，a￥0，(k=1,2, …,n). 现在证明Doolittle分解的唯一性.假定A有两个Doolittle分解 A=L:U=L:U 其中，L,和L2为单位下三角阵，U1与U2为上三角阵，由于A非奇，则U1亦非奇， 于是 LL=UU, 上式右边为上三角阵，左边为单位下三角阵，所以 L21L,=U2U'=I, L1=L2,U1=U2 唯一性得证。 矩阵的三角分解除了Doolittle分解之外，还有其他一些变形情况. 定理2.3如果非奇异矩阵A满足定理2.2中的三个条件之一，则 1)A有唯一的三角分解： A=LDR, 其中，L为单位下三角阵，D为对角阵，R为单位上三角阵 2)A有唯一的Crout分解： A=LU
第二章解线性代数方程组的直接法 于是，有 T α11 ••• alk a J. k+ 1 .., a ZI 1n I ZI • • • • • • • • ... • • ... • • • • • • • • Zk akl ... au a ，k ... I Zk =0 , O I ... a k+ l, k 1 ... a k+ lIn O • ' • • • • • • • • • • • • • • • • • • • • • • O anI • • • a nk a 11 ,k+l .., ami O 这与 A为正定阵矛盾.因此 A的各阶顺序主子式非零，由1)知， 1， 2 …,n) . 现在证明 tt e分解的唯一性.假定 A有两个 tt e分解: A=L1U1=L2U2 其中 单位下三 非 奇 于是 L;l L 1 =U2U;] , 上式右边为上三角阵，左边为单位下三角阵，所以 L;I L] =U2U;1 =1 , NP L1=L2 , U1=U2 唯一性得证 • 矩阵的三角分解除了 oo t tl e分解之外，还有其他一些变形情况. 定理 3如果非奇异矩阵 A满足定理 2中的三个条件之一，则、 l) 有唯 A=LDR , 其中 L为单位下三角阵， D为对角阵 R为单位上三角阵. 2) 有 唯 ro u A=LU