第6章3-4节矩阵三角分解法-与范数.课件.ppt

1、13 矩阵三角分解法矩阵三角分解法 1 Doolittle分解法 将高斯消去法改写为紧凑形式，可以直接从矩阵 的元素得到计算 元素的递推公式，而不需任何中间步骤，AUL , 一旦实现了矩阵 的 分解，那么求解 的问题就等价于求解两个三角形方程组 ALUbAx 求,bLy ;y 求 ,yUx. x这就是直接三角分解法直接三角分解法. 2 设 为非奇异矩阵，且有分解式 （A的Doolittle分解）A,LUA .111222112112121nnnnnnuuuuuulllA其中 为单位下三角阵， 为上三角阵，即 LU 的元素可以由 步直接计算定出，其中第 步定出 的第 行和 的第 列元素. UL

2、,nrUrLr3；的第1行元素得U),2, 1(11niuaii 设已经定出 的第1行到第 行元素与 的第1列到第 列元素. U1rL1r 的第1列元素.得L), 2(/,11111111niualulaiiii 利用等式两边元素比较及当 时， kr ,0rkl有 nkkirkriula1.11rirkkirkuul故 .111222112112121nnnnnnuuuuuulllA.111222112112121nnnnnnuuuuuulllA4),1,(11nrriulaurkkirkriri nkkrikirula1 用直接三角分解法解 (要求 的所有顺序主子式都不为零)的计算公式. b

3、AxA ), 2(/), 2 , 1(111111niualniauiiii 计算 的第 行和 的第 列元素 UrLr).,3,2(nr );,1,(11nrriulaurkkirkriri.11rrirrkkrikulul.111222112112121nnnnnnuuuuuulllA );, 1(/)(11nriuulalrrrkkrikirir5 );, 1(/ )(11nrnriuulalrrrkkrikirir且 求解 的计算公式： yUxbLy, ,11by,/nnnnuyx );,3 ,2(11niylbyikkikiiiinikkikiiuxuyx/1).1 ,2, 1(nni

4、6 例例5 5.201814513252321321xxx 解解用Doolittle三角分解法解 ,11111 au,11/2/112121ual,122512212222ulau,21212 au,31313 au，31/3/113131ual,432213212323ulau,51/)231(/)(2212313232uulal);,1,(11nrriulaurkkirkriri);, 1(/ )(11nrnriuulalrrrkkrikirir且72400410321153012001A因为 ,)20,18,14(TyL,)72,10,14(TxU.LU.24)4()5(33523321

5、3313333ululau从而,)72,10,14(Ty得求解.)3,2, 1(Tx得;11by（4.4）);,3 ,2(11niylbyikkikii8 当 计算好后 就不用了，故可将 仍存放在 的相应位置. riuriariuria例如 44434241343332312423222114131211aaaaaaaaaaaaaaaaA最后在存放 的数组中得到 的元素. UL ,A 直接分解法大约需要 次乘除法，和高斯消去法计算量基本相同. 3/3n 再考虑存储问题44434241343332312423222114131211ullluulluuuluuuu9 如果已经有了 的 分解，则求

6、解具有相同系数的方程组 是相当方便的，每解一个方程组 仅需要增加 次乘除法运算. ALU)(21mbbbAxjbAx 2n10 若 A的各价顺序主子式不为零，uii不为零.111222112112121nnnnnnuuuuuulllA2. LDR分解111.1.1.11111112111121uuuuuulllAnnnnnnLDR12定理4 设n阶可逆矩阵A有唯一的LDR分解的充分必要条件是A的各价顺序主子式不为零.133. Crout分解 在A的LDR分解中，将LD看成一个矩阵记为L1 A=L1R，为方便也可记为A=LR其中L下三角矩阵，R为单位上三角矩阵.这种分解称为Crout分解.144

7、 平方根法平方根法(Cholesky(Cholesky分解法）分解法） 平方根法是利用对称正定矩阵的三角分解而得到的求解对称正定方程组的一种有效方法. 又因为A为对称矩阵，A=LDR=AT=(LDR)T=RTDLT分解的唯一性，L=RT,LT=R所以A=LDLT设D=diag(d1,dn), 设 A为对称正定矩阵，则 A 的所有顺序主子式均大于零，由定理4知， A可唯一分解为 LDR.15因为A为正定矩阵，di0 (i=1,n)为下三角矩阵。其中表示为为方便计，也可将上式为下三角矩阵。其中令LLLALLLLGLGAdddiagGTTTn1111)(),.,(16 定理定理5 5如果 为 阶对称

8、正定矩阵，则存在一个实的非奇异下三角阵An,L 可以用直接分解方法来确定计算 元素的递推公式. L(对称正定矩阵的三角分解或Cholesky分解),TLLA 使当限定 的对角元素为正时，这种L分解是唯一的. 因为 ,2221211121222111nnnnnnnnllllllllllllA17其中).,2,1(0niliinkjkikijlla1于是得到解对称正定方程组 的平方根法计算公式： bAx 对于 nj,2,1 l. .21112jkjkjjjjlal),(0时当kjljk由矩阵乘法及 按等式两边对应元素相等，得 ,11ijjjjkjkikllll)., 1(/11njilllaljj

9、jkjkikijij 2. 18求解 即求解两个三角形方程组： ,bAx;,1ybLy求）（ 4. ).1 , 1,(/1nnilxlbxiinikkkiii 3. ).,2, 1(/11nilylbyiiikkikii由计算公式1知 ),2, 1(12nilajkjkjj所以 .,)2(TxyxL求19jjjkjjjkalal|,2既 当求出 的第 列元素时， 的第 行元素也算出. LjTLj所以平方根法约需 次乘除法，大约为一般直接分解法计算量的一半. 6/3n 于是不选主元素的平方根法是一个数值稳定的方法. 这个结果说明，分解过程中元素 的数量级不会增长jkl20 由于 为对称阵，因此在

10、计算机实现时只需存储 的下三角部分.AA 下三角部分共需存储 个元素，可按行主序用一维数组存放，2/)1(nn即.,)2/)1(21222111nnnnaaaaaannA矩阵元素 在一维数组中表示为 的元素存放在 的相应位置. ijaL),2/)1(jiiAA 215 追赶法追赶法 实际问题中，通常要求解系数矩阵为对角占优的三对角线方程组 ,12112111122211nnnnnnnnnffffxxxxbacbacbacb简记为 .fAx其中，当 ：，且时,01ijaji 0; )a(11 cb22);1,3,2(0, )b(nicacabiiiii0. )c(nnab 利用矩阵的直接三角分解

11、法推导解三对角线方程组的计算公式. ,LUA 其中 为下三角矩阵， 为单位上三角矩阵. LU 由系数阵 的特点，可以将 分解为两个三角阵的乘积，AA即 23 设 nnnnnbacbacbacb11122211A,11111221nnn其中 为待定系数. iii,24比较两边得,11111cb)1,2(niciii ),2(,1nibaiiiiii,/0 01111111bccbb，由得.101,11111221nnnA|10111iiiiiiiiiiicababab设),1,2,1(0nicii25 );,2(),2(1niabniaiiiiiiiiic01. |11均有界，这说明另外，iii

12、iiiiiiiiiiiababababc 由 此可得下列计算公式).1,3,2(/niciii26确定了 ，就实现了 的 分解. ,iiiA三角求解 等价于求解两个三角形方程组： ,fAx ;,)1(yfLy求.,)2(xyUx求 解三对角线方程组的追赶法公式追赶法公式： iiiiiiiiibacnib1111111/1,.,1.1作对分解27 2. 解 fLy ,/111fy 3. 解 yUx);,3,2(/)(1niyfyiiiii,nnyx称计算系数 及 121nnyyy21 称计算方程组的解 的过程为赶的过程.共需5n-4次乘除法.11xxxnn).1 ,2,2,1(1nnixyxii

13、ii的过程为追的过程.);,3,2(/)(1niyafyaiiiiiii28 定理定理6 6设有三对角线方程组 , fAx其中 满足条件A(a)，(b)，(c)，则 为非奇异矩阵且追赶法计算公式中的A);1, 3 , 2(0niababciiiiii ,ii满足： );1,2, 110nii（.0nnnnnabab 追赶法公式实际上就是把高斯消去法用到求解三对角线方程组上去的结果. 29 计算机实现时只需用三个一维数组分别存储 的三条线元素 ，此外再用两组工作单元保存 或 A,iiicba,iiy.ix 由于 特别简单，因此求解的计算公式也非常简单，计算量也很小. A30将实数4 向量和矩阵的

14、范数向量和矩阵的范数 向量范数概念是三维欧氏空间中向量长度概念的推广，在数值分析中起着重要作用. 定义定义1 1niiiyx1T),(xyyx（或 ）.T21T21),(,),(nnyyyxxxyxnRnC设（或复数 ）niiiyx1H),(xyyx称为向量 的数量积数量积. yx ,312112212),(niixxxx将非负实数 称为向量 的欧氏范数欧氏范数 . x 定理定理7 7 关于内积与欧氏欧氏范数，成立如下定理.),CR,nn或（yx设则 ；时成立当且仅当 ,),( .001xxx32nnnnCCRRyxyxyxyxyxyxyxyxyxyx, ),(),( ; ),(),(, ),

15、(),( ; ),(),( .3数,为为实数,复);,(),( (),(),( .2xyyxxyyx或);,(),(),( .42121yxyxyxx 5.5. (Cauchy-Schwarz不等式) ,),(22yxyx等号当且仅当 与 线性相关时成立； xy 6.6. 三角不等式 .222yyxx33 也可以用其他办法来度量向量的“大小”. 向量的欧式范数可以看成是对 中向量“大小”的一种度量.nR 例如，对于 可以用一个 的函数,R),(2T21xxxx 来度量 的“大小”，而且这种度量“大小”的方法计算起来比欧氏范数方便. iixN2,1max)(xx 一般要求度量向量“大小”的函数

16、满足正定性、齐次性和三角不等式. )( xN34），正定条件当且仅当() 0 0(0 . 1xxx ),C(R , .2或xx），三角不等式( .3yxyx则称 是 (或 )上的一个向量范数(或模). nR)(xNnC 由条件3 定义定义2 2如果向量 (或 )的某nRxnC个实值函数 ，满足条件：xx)(N(向量的范数). yyxyyxx35. .4yxyx. xxyxxyy从而有 几种常用的向量范数. 1. 向量的 -范数(最大范数)： .max1inixx 2. 向量的1-范数： .11niixx36 3. 向量的2-范数： .)(),(1212212niixxxx也称为向量 的欧氏范数

17、. x,)(/11pnipipxx 4. 向量的 -范数： p其中 .),1p 可以证明向量函数 是 上向量的范数,pNxx)(nR且容易说明上述三种范数是 -范数的特殊情况.p37如果 例例6 6计算向量 的各种范数. T)3 ,2, 1 ( x 解解 ,61x 定义定义3 3设 为 中一向量序列， )(kxnR,R*nx.),(*,),(T*2*1T)()(2)(1)(nknkkkxxxxxxxx),2, 1(lim*)(nixxikik则称 收敛于向量 ，)(kx*x.lim*)(xxkk记记为 , 3x.142x38 定理定理8 8( 的连续性)( xN为 上任一向量范数，nR则 是

18、的分量)( xNxnxxx,21xx)(N 设非负函数的连续函数.证明证明:,11niiniiiyxeyexi设),0 ,0 , 1 ,0(ie其中 只需证明当 时 . yx )()(yxNNyxyx)()(NNyx niiiiyx1)(e39niiiiyx1e,1niieyx,( 0)()(）时当yxyxyxcNN.1niice其中 40 定理定理9 9的任意两种范数，设 为 上向量tsxx,nR则存在常数,0,21cc 证明证明 只要就 证明上式成立即可，即证明xxs存在常数 使 ,0,21cc.R ,021xxxx且对一切ntcc考虑泛函 .R,0)(ntfxxx(向量范数的等价性),2

19、1stsccxxx有 nRx使得对一切41 由于 为 上的连续函数，所以 于 上达到最大、最小值，)( xfS)( xfS记 则 是一个有界闭集. ,R, 1nSxxxS即存在 使得S xx ,.)(max)(,)(min)(21cffcfxfSS xxxxx设 且nRx,0 x,Sxx则从而有 ,21cfcxx显然 上式为 ,0,21cc42,21cctxx.R ,21ntccxxxx对一切 定理9不能推广到无穷维空间. 由定理9可得到结论如果在一种范数意义下向量序列收敛时，则在任何一种范数意义下该向量序列均收敛. 43 定理定理1010,0*lim*lim)()(xxxxkkkk 其中为向

20、量的任一种范数. ,0*lim*lim)()(xxxxkkkk证明：, 0,21cc由定理9，存在常数* *)(2)()(1xxxxxxkkkcc.0*lim0*lim)()(xxxxkkkk44 向量范数概念可以推广到矩阵. 定义定义4 4(矩阵的范数)如果矩阵 的某个非负的nn RA实值函数 , AA)(N满足条件 45正定条件);( ) 0 0(0 . 1AAA ( 2齐次条件);为实数ccc,.AA三角不等式);(. 3BABA . 4BAAB.则称 是 上的一个矩阵范数(或模). )( ANnnR 由于在大多数与估计有关的问题中，矩阵和向量会同时参与讨论，所以希望引进一种矩阵的范数，

21、它和向量范数相联系而且和向量范数相容.46 . xAAx 定义定义5 5设 , ，nRxnn RA给出一种向量范数 (如 或)，相应地定义一个矩阵的非负函数vx2,1v即对任何向量 及 都成立nn RAnRx(矩阵的算子范数) . max 0vvxvxAxA可以验证 满足定义4，所以 是 上矩阵的一个范数，称为 的算子范数. vAvAnnRA47 定理定理1010设 是 上一个向量范数，vxnR . vvvxAAx则 定理定理11nRxnn RA的行范数),称为AA( max 1. 11njijnia的列范数),称为AA( max 2. 111niijnja. )( 3. Tmax2范数）的2

22、(称为AAAA . max 0vvxvxAxA48例例, 642,31max1A设 ，计算 的各种范数. 4321AA解解, 743,21maxA.46.522115)(Tmax2AAA49另一种矩阵范数 ,)(211,2,FnjijiaFAA称为A 的Frobenius范数50 定义定义 设 的特征值为 , nn RA), 2 , 1(niiini1max)(A为 的谱半径谱半径. A 定理定理1212设 ,nn RA则 , AA )(即 的谱半径不超过 的任何一种算子范数(对 也对). AAFA称 (特征值上界) 证明证明设 是 的任一特征值， 为相应的特征向量，Ax则 ，xAx由相容性条件 得 xxAx,xA 注意到 , 即得 0 xA . vvvxAAx51 定理定理1313如果 为对称矩阵，nn RA 定理定理1414如果 ，1B则 为非奇异矩阵，BI ,11)(1BBI其中是指矩阵的算子范数. ).(2AA则 且 证明证明若 , 0)det( BI用反证法. 0 xBI)(则有非零解，使 , , 00 xBx100 xBx00 x即存在 又由 ，有 IBIBI1)(1B故 ，000 xBBxx与假设矛盾. 52,)()(11BIBIBI从而 ,)()(11BIBIBI.)(BBI111