22第I部分数值分析 其中，L为下三角阵，0为单位上三角阵 证明：（留作习题）. 关于计算矩阵A的LDR分解和Crout分解有下列的计算公式. 算法2.3矩阵A的LDR分解 考虑分解 A=LDR 即 a1 a12 … a1,n-1 ain 「1 0 … … 0 a21 a22 d2.n-1 w 1 an-1,满-1am-1n 1 0 …a-1 … In.n-1 1 d10…… 01「1 0 d o 1 .d- 0 0 0 0 1 、 可以通过比较上式两边的系数，得到矩阵L,D,R中元素的计算公式：对k=1,2,…, n,计算： (d=a一 i7=(a-2ld,ri)/d,G=k+1,…,n）y 2=(a4-dr/d,i=+1…,m, 算法2.4矩阵的Crout分解 勿 A=IU a12 azi a22 Q2,n-1 42m am-1.小 am-12 an-1.n-1 an-1.n an a,w-1
22 分析 其中，互为下三角阵 U为单位上三角阵. 证明: (留作习题). 关于计算短阵 A的 R分解和 o u t分解有下列的计算公式. 算法 3矩阵 R分解 考虑分解 A=LDR all a l2 ••• l. 1 O ••• ••• O 1 • • a2] a 22 ••• a 2,n-l a Zn • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • a n-lo1 ••• a n- 1•n- 1 an-t ,n • • • • 1 O anl a n2 .., an ，n ann Ll n1 ••• ••• ln , n• l 1 d1 O ... •• • O 1 Tl2 ••• ••• TIn O d2 • • O 1 • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • ' • • • • • • • • dn- l O • • • • • • • • • • 1 γn , n O ••• ••• O d O ••• ••• O 1 可以通过比较上式两边的系数，得到矩阵 R中元素的计算公式:对 1， ，…， d k= aU - 2: lk,d ,T,k , rhJ=(GhJ-21Jhsdzrd)/ (j = k+1 , '" ，的， lik = (a 址 1， .. ，时， 算法 4矩阵的 o u t分解 A=LU all a l 2 ••• al ，n a l n a 21 a 22 '" a z • • • • • • • • • • • • • • • a n- 1. 1 a n-l• Z ••• an l，n-1 an- ],n anI a n2 ••• n•
第二章解线性代数方程组的直接法23 0 01 0 1 : Ln-1.n-1 0 1 Ua-l.m a … 气 0 1] 可以通过比较上式两边的系数得到矩阵L,0中元素的计算公式：对k=1,2,…,, 计算： =a-2, （G=k+1,…,n), ,=a2第2)九，g=k+1m ◆ 当矩阵A为对称正定时，我们还有下面更好的计算方法. 算法2.5给定对称正定矩阵A,用Cholesky分解求解线代数方程组Ax=b的 平方根法. l)先考虑Cholesky分解： rl110…07i11121…11m A= 0i2…i2n :.0:.. =1T 2n11n2…1nm」L0…01nn」 第一步对i=1,…,n,用L的第i行乘LT的第1列，再比较两边，得 a11=l1,l11 a=il（i=2,…,n). 从而 1,=√a1, 1a=aa/几1(i=2,…,n) 第二步对i=2,…,n,用L的第i行乘LT的第2列，再比较两边，得 a2=2十li2 a2=1al2,+ial2(i=3,…,n) 从而
第二章 解线性代数方程组的直接法 23 U 1n • • • • • • U n- I. n ••• ... U 1 1Z O ... ... O • • • 1 • • • • • • • • • O 1 • • • • • • • • • •••••• • • • • • • O O 1 O ... ... in I，n ln.n-I • • • • • • • • • ... ... 可以通过比较上式两边的系数得到矩阵 U中元素的计算公式:对 1， 2，… 计算: (j=k+ l， k-I JJK=GJh-Zllp·ι • -Aai=(ahep-211 (j=k ,k + 1，…，川， 当矩阵 A为对称E定时，我们还有下面更好的计算方法. 算法 5给定对称正定矩阵 e s y分解求解线代数方程组 Ax b的 平方根法. 1)先考虑 分解 =llT. 1nn , " A''tvA''t ... ... O ... O 2212 O • • • • • • "[II lZI A= • • • • • • • • O • • • • inl ... inn O ... O 第一步 l，… L的第 行乘 较两 all = l 1l 111 , ll Ci = 2 ,… , n ) • 从而 /11 =,;;;;;, /n=an// (i=2 ,…,n ) . lI 第二步 较两边 G22=IL 十1:2 α;Z =lnlzl +l;2 122 (i=3 从而
24第I部分数值分析 12z=√a22-ii, 12=(a2-1ai1)/l2(i=3,…,n). 依次下去，…，一直进行到第(n一1)步. 第n步对i=n用L的第n行乘L的第n列，再比较两边，得 a=1%+1+…+i-1十i2, 从而 1..-22 上述的n步计算格式可以写成如下的计算公式，对i=1,2,…,n,计算： 2.a-2 2.=(a4-2.2.)/1,(k=i+1,i+2,…,m. 2)回代过程：令 (Ly=b, LTx=y. 逐次回代计算方程组的解 y1=6/几1， =(a.-22y,)/2,k=2,3,…,m. xn=yn/几nm, x=（A1,)/i,(=n-1,,2,1), 由于解对称正定方程组的平方根法在进行Cholesky分解时需要将对角元作开 方运算，为了避免开方运算，可采用对称正定矩阵的分解式： A=LDLT」 下面我们给出求解对称正定方程组的改进平方根法 算法2.6给定对称正定矩阵A,用改进平方根法求解线代数方程组Ax=b. 1)先考虑LDLT分解： A=LDLT
24 数值分析 122=dtz1' 2 Ci . i2 = (a i 2 - 2a 221)/222 依次下去，……，一直进行到第 n步对 n用 L的第 n行乘 L的第 n列，再比较两边，得 ann=1:l 月2+ …+lin 从而 Gnn-21: 上述的 n步计算格式可以写成如下的计算公式，对 ，… ，计算: (k=i+I ,i+2 ,… ,n) . Gu-21: lhz=(α 2: 2i, ·lA, )/2ii , 2) 过程 Ly=b , LTX=y. 逐次回代计算方程组的解: (k= ，3 Y1 =b1 /211 ' Yk= (bk - 2: 2j" y ,)/2u ' X n= Yn/1ml , • XA= (Yk- 2: [j" X，)/ (k=n-I ,… , 2 , 1). 由于解对称正定方程组的平方根法在进行 e s y分解时需要将对角元作开 方运算，为了避免开方运算，可采用对称正定矩阵的分解式: A=LDLT • 下面我们给出求解对称正定方程组的改进平方根法. 算法 6给定对称正定矩阵 A，用改进平方根法求解线代数方程组 1)先考虑 A=LDLT
第二章解线性代数方程组的直接法25 a11 a12 Q1,n-1 0 0 a21 a22 … a2,-1 an-1.1 am-1,2 … an-1n-1 an-1.n 1 0 ann-1 ann 1 [d 0 … … 0]1 T12 :0 1 di-1 0 1 In-l.n 0 0 d 。。。 0 通过比较上式两边的系数得到矩阵L,D元素的计算公式：对k=1,2,…,n,计算： d (d=a一 k (l=(a与-∑lwd,la)/d,(i=k+1,…,n), 2)回代过程：令 (Ly=b, LTx=D-y, 逐次回代计算方程组的解： y=6-2w,-1,2…m x=y/d-lx,(k=n-1,…,2,1). 对一般的非奇异矩阵的三角分解，只要在每个分解步中考虑行交换就可以了.下 面我们仅对一般的非奇异阵给出Doolittle分解结果，至于Crout分解和LDR分解 也可进行相应的讨论。 定理2.4如果矩阵A∈Rx“非奇，则存在n阶置换阵P=P其中，k≤
第二章 解线性代数方程组的直接法 25 all a12 ••• a1n l O ••• ••• O • • • • • • • • • 1 O • • • • • • • • • 1 • • • a2n • • aZ • •• • • • • α22 • • α2] • • • an J. an- I •n a ••• an-l,l n - 1 • 2 a ,ll an2 ••• ann • ••• • • In. n-] 1 r 1n • • • • • r • •• ••• 1 1Z d 1 O ••• • •• O • • • 1 n • • • • • • • • • O 1 • • • • • • O d2 • • • •••••• • • • • • • O • • • • • • • • • •••••• O ••• • • • O dn O •• • ••• O 1 通过比较上式两边的系数得到矩阵 D元素的计算公式:对 1， ，…， η，计算: Ci ，…，川， dk=a 'i 崎=(GhJ-Zllhdstu)/ 2) 代过程 Ly=b , L T x=D- 1 y , 逐次回代计算方程组的解: Yk=bk- 'i lksY ,' (走= ，2 Xk=Yk/dk- 'i , (k= 1， 1) s=k+l 对一般的非奇异矩阵的三角分解，只要在每个分解步中考虑行交换就可以了.下 面我们仅对一般的非奇异阵给出 tt e分解结果，至于 t分解和 R分解 也可进行相应的讨论. 定理 如果矩阵 RnXn 存在 1T
26第I部分数值分析 ◇ … 1 0 1 第k行 1 P= 1 1 0 第行 … 1) 为初等置换阵(=时为恒等阵)，成立 PA=LU, 这里，L为单位下三角阵，U为上三角阵， 证由算法2.1及矩阵的Doolittle分解可以得到 L-P-1.L2 P2L PA=U, (2-8) 其中，P=P(k≤i4)为初等置换，U为上三角阵， 1 L m+1,k 1 mn,k 由P.的定义及式(2-8)，得 L-1P-1…L2P2LP1=L1·(P-1L2P-i)…(P-1…PL2Pg…Pn-） ·(Pm-1…P2L1P2…Pn-1)(P.-1…P2P1) =L-iL-2…LP 这里
26 部分 值分 l • • • 1 O 1 Pkik= 1 为初等置换阵 .时为恒等阵) ，成立 • • • 1 I O 1 • • • 1 ih PA=LU, 这里， L为单位下三角阵 U为上三角阵. 证由算法 及矩 的Doolittle 解可 …LzPzL PjA=U , 其中 ki i k 置换 为上三 (2-8) L k = 由凡的定义及式 • • • 1 η1 j ,k 1 • • • • • • 1 , Ln-jPn- j…L ZP 2L j P j =Ln_ 1 0 (P Lz n- j) . . . P3...pn一j ) ·(Pn-1...pzLIP2...pn一j)(Pn- I" ，P2P j) =Ln- jLn- 2…LIP 这里