数值分析(10) 误差分析和解的精度改进

1、数值分析数值分析数值分析数值分析 第四节第四节 误差分析和解的精度改进误差分析和解的精度改进一、解的误差分析基本问题一、解的误差分析基本问题解的稳定性解的稳定性二二、方方程程组组的的状状态态和和条条件件数数三、数值稳定性及解的精度改进三、数值稳定性及解的精度改进四四、病病态态方方程程组组的的处处理理数值分析数值分析数值分析数值分析一、解的误差分析基本问题一、解的误差分析基本问题解的稳定性解的稳定性,Axb 用用直直接接法法求求解解，得得到到的的是是带带有有误误差差的的计计算算解解（数数值值解解）误误差差产产生生的的原原因因主主要要有有两两个个：1,()(),A bAbAA xxbbAb （ ）

2、一一般般原原始始数数据据都都带带有有误误差差，因因此此实实际际解解的的方方程程组组是是近近似似方方程程组组将将对对解解的的精精度度产产生生影影响响。2（ ）计计算算过过程程中中，舍舍入入误误差差的的传传播播和和积积累累将将影影响响解解的的精精度度。数值分析数值分析数值分析数值分析12解解的的稳稳定定性性：“小小的的误误差差会会不不会会引引起起解解的的很很大大变变化化”有有两两种种解解的的稳稳定定性性概概念念：（）数数值值方方法法的的稳稳定定性性：与与数数值值方方法法有有关关。（）数数学学稳稳定定性性：是是由由数数学学问问题题本本身身故故有有属属性性所所决决定定的的，与与数数值值方方法法无无关关

3、。即即通通常常所所说说的的“病病态态问问题题”和和“良良态态问问题题”。数值分析数值分析数值分析数值分析 数学稳定性数学稳定性: :对数学问题而言，如果输入数据有对数学问题而言，如果输入数据有微小扰动，引起输出数据（即数学问题的解）有很微小扰动，引起输出数据（即数学问题的解）有很大扰动，则称数学问题是大扰动，则称数学问题是病态问题病态问题，否则称为，否则称为良态良态问题问题。 数值方法的稳定性数值方法的稳定性: :一个算法如果输入数据有扰一个算法如果输入数据有扰动（即有误差），而计算过程中舍入误差不增长，动（即有误差），而计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称此算法为不稳定则

4、称此算法是数值稳定的，否则称此算法为不稳定的。的。数值分析数值分析数值分析数值分析151210.31032105(1)(0,0.333) ,(1.0,1.667)(2)(0.0333,0.333) ,(1.0,2. )10TTTTxxxAxxAx 顺顺序序消消元元列列主主元元消消元元例例151210.3102.999210.0014.999(3)(0.0333,0.334) ,(1.0,2.0)TTxxxAx 列列主主元元消消元元数值分析数值分析数值分析数值分析120.7800.5630.2170.9130.6590.254(1)(1.0, 1.0)(0.217,0.254)(2)(1.0,

5、1.0)(0.217,0.254)2TTTTxxxAxxAx 顺顺序序消消元元列列主主元元消消元元例例120.78010.56290.2170.91300.65910.254(3)(0.2528,0.0352)(0.217,0.254)(4)(0.341, 0.08)(0.217,0.254)TTTTxxxAxxAx 列列主主元元消消元元列列主主元元消消元元数值分析数值分析数值分析数值分析120.7800.5630.21720.9130.6590.2541(5)(176.500, 105.60)(0.2171,0.2547)TTxxxAx 列列主主元元消消元元120.7800.5630.217

6、0.9130.6590.254(1)(1.0, 1.0)(0.217,0.254)(2)(1.0, 1.0)(0.217,0.254)2TTTTxxxAxxAx 顺顺序序消消元元列列主主元元消消元元例例数值分析数值分析数值分析数值分析|1.|xxxxxxrbAxbbx 解解的的相相对对误误差差不不知知道道是是否否可可改改用用相相对对剩剩余余量量来来估估计计误误差差两两种种误误差差估估用用计计即即代代替替二二、方方程程组组的的状状态态和和条条件件数数由由前前面面例例子子说说明明是是不不可可以以的的。为为什什么么？下下面面我我们们来来证证明明事事后后误误差差估估计计。数值分析数值分析数值分析数值分

7、析11*rArAebAbxA 将将上上两两式式合合并并就就推推出出*,()exxrbAxAxAxA xxAe事事后后误误差差估估记记计计1rbAxAeeA r 由由和和可可得得到到,1rAeAr *1*1,bAxb xA bxAbA由由得得，数值分析数值分析数值分析数值分析1*erA Abx 得得到到事事后后误误差差估估计计1,.A A 当当很很大大时时 不不能能用用相相对对剩剩余余量量来来估估计计解解的的相相对对误误差差数值分析数值分析数值分析数值分析 | | |bAx 又又1,0bbA 先先验验误误差差估估计计：（ ）只只有有 有有扰扰动动bAxbxAbbxxAbAx 1)( 相减得相减得

8、|1bAx 11| | |AbxbAAbxbA 解解的的相相对对误误差差估估计计式式数值分析数值分析数值分析数值分析111| | 1| |1 |,|20AAbAAAAAxAxAA 当当时时，解解的的相相对对误误差差（ ）只只有有扰扰动动估估计计式式为为有有1| | 130,0AAAb 当当时时，解解的的相相对对（ ）误误差差估估计计式式为为1*1()1AbA AxAbxAA 数值分析数值分析数值分析数值分析.,1, 1max0是非奇异的是非奇异的时时当当因此因此与所设矛盾与所设矛盾由范数定义由范数定义AIAxAxAx 1,1,11()11n nARAIAIAAA 若若则则是是非非奇奇异异阵阵

9、且且有有引引理理000(1),()0,0:,.IAIA xxAxx 假假设设是是奇奇异异阵阵 则则有有非非零零解解 即即证证明明 用用反反法法存存在在证证使使100 xAx于是于是数值分析数值分析数值分析数值分析AAI 11)(1即即)()()()(1,)()()2(111AIAIAIAIIAIAII 有有两边取范数两边取范数又由又由1)(11 AIA得到得到1111()()()()IAIIAAIAIIAA再再利利用用有有证毕证毕数值分析数值分析数值分析数值分析1*1()1AbA AxAbxAA 下下面面证证明明相相对对误误差差估估计计式式*, ()()(): AxbAAxxbbAAxbAx

10、两两式式相相减减得得证证明明111,().AAIAA设设由由引引理理知知非非奇奇异异11111)()(,)( AAAIAAAAIAAA 有有也非奇异也非奇异于是于是111*()()xIAAAbAx数值分析数值分析数值分析数值分析111*1*1()()()1由引理的估计式得到xIAAAbAxAbxAxAA bAxxAb *1, 即即由由AAbbAAAAxx 11*1)( 得得到到数值分析数值分析数值分析数值分析:(),.Acond AAAxb 若若线线性性代代数数方方程程组组的的系系数数矩矩阵阵 的的条条件件数数相相对对很很大大 称称 对对求求解解线线性性代代数数方方程程组组是是病病态态的的矩矩

11、阵阵 方方程程组组称称为为病病态态方方程程组组反反之之则则定定称称其其为为良良态态的的义义11:2,).(nAA AAcond AA A 对对非非奇奇异异 阶阶方方阵阵称称量量为为矩矩阵阵 的的条条件件数数记记为为矩矩阵阵的的条条件件数数定定义义11:.,.,.A AA A 大大致致是是实实际际误误差差对对原原始始误误差差的的放放大大倍倍数数于于是是这这个个数数学学量量定定量量的的刻刻画画了了方方程程组组对对原原始始误误差差的的敏敏感感程程度度即即 病病态态 程程度度由由此此 定定义义矩矩由由先先验验估估计计式式说说明明阵阵的的条条件件数数数值分析数值分析数值分析数值分析1.( )1,2.(

12、),Cond AAAxbCond AAAxb 当当是是病病态态矩矩阵阵是是病病态态方方程程几几点点注注意意：组组。当当较较小小时时是是良良态态矩矩阵阵是是良良态态方方程程组组。3.( )4.( )Cond AACond A与与矩矩阵阵 本本身身的的结结构构有有关关，与与其其他他任任何何外外部部因因素素无无关关。条条件件数数的的大大小小没没有有绝绝对对的的标标准准，与与方方阵阵的的阶阶数数有有关关。数值分析数值分析数值分析数值分析11111()()cond AAAcond AAA 通通常常使使用用的的条条件件数数有有1max1222min()()()TTnA Acond AAAA A 谱谱条条件

13、件数数22maxmin,()()():.TAA AAcond AAA 当当 为为非非奇奇异异的的实实对对称称阵阵时时 因因注注意意 谱谱条条件件数数在在理理论论上上有有重重要要意意义义111maxmax2minmin()()111()()TTTTnAAAAAAAA A 证证：数值分析数值分析数值分析数值分析111( )1,1Acond AIAAIAAA A 对对任任何何条条件件数数的的性性质质非非奇奇异异阵阵 都都有有222maxmax22,.,()()()()()TTTAQcond QAcond AQcond AQAA Q QAA AA 对对非非奇奇异异阵阵 作作正正交交变变换换后后 谱谱条

14、条件件数数不不变变即即若若正正交交阵阵 则则为为 11,0,()( )ppppkcond kAkAkAAAcond A 矩矩阵阵乘乘非非零零的的常常数数后后条条件件数数不不变变1,( )1,1,2,pIcond Ip单单位位阵阵 的的条条件件数数为为数值分析数值分析数值分析数值分析1,2以以上上说说明明，正正交交变变换换在在数数值值计计算算中中有有很很好好的的数数值值稳稳定定性性。（ ）对对矩矩阵阵的的正正交交变变换换不不改改变变矩矩阵阵的的谱谱条条件件数数 正正交交矩矩阵阵的的条条件件数数达达到到最最小小。（ ）对对有有误误差差的的向向量量（矩矩阵阵），正正交交变变化化后后按按谱谱范范数数不

15、不会会增增加加误误差差。1)()()()()(minmaxminmax2 IIQQQQQcondTT 21.,( )1.Qcond Q 正正交交阵阵的的谱谱条条件件数数等等于于即即若若 是是正正交交阵阵 则则数值分析数值分析数值分析数值分析22|n nARAAAQA QA Q AQ AA 同同样样，对对有有，则则，且且正正交交变变换换后后，误误差差也也没没有有增增加加。22,|()()() () |TTTQ xQxQ xxQ Qxxxx 其其中中是是的的误误差差 且且即即正正交交变变换换后后，没没有有增增加加误误差差。在正交变换下，误差不增长在正交变换下，误差不增长,nn nxRxxxxQRQ

16、xQxQ x 对对有有误误差差，用用正正交交阵阵作作变变换换，数值分析数值分析数值分析数值分析2.(1)(2)(3)Axb 解解的的精精度度改改进进双双在在良良态态下下，用用稳稳定定的的数数值值方方法法求求解解，也也总总是是会会有有误误差差的的，可可用用以以下下方方法法改改进进计计算算解解的的精精度度。用用双双精精度度计计算算，有有效效数数字字增增加加了了，舍舍入入误误差差自自然然会会减减少少。精精度度改改善善：（行行）比比例例增增减减改改善善迭迭代代改改善善三、数值稳定性及解的精度改进三、数值稳定性及解的精度改进1.Axb 结结论论：直直接接法法解解，用用顺顺序序消消元元是是不不稳稳定定，而

17、而用用选选主主元元（列列主主元元）是是数数值值稳稳定定性性稳稳定定的的。数值分析数值分析数值分析数值分析 前面介绍的列主元法解决了前面介绍的列主元法解决了GaussGauss消元法由于小主元的出消元法由于小主元的出现所导致的舍入误差的积累，从而出现的失真的问题。但列主现所导致的舍入误差的积累，从而出现的失真的问题。但列主元法也有缺点，当方程中出现比例因子时，列主元法就无能为元法也有缺点，当方程中出现比例因子时，列主元法就无能为力了。力了。41212121011,02xxGaussxxxx 法法求求解解，失失真真列主元法求解列主元法求解x1 1= =x2 2=1=1377121212101010

18、1,02xxxxxx 列列主主元元法法求求解解，失失真真 按行比例按行比例消元法消元法 : :将每个方程乘上一个适当的比例因子，使将每个方程乘上一个适当的比例因子，使方程组的最大系数的绝对值不超过方程组的最大系数的绝对值不超过1 1，然后再做列主元消元。，然后再做列主元消元。（2）（行）比例增减改善）（行）比例增减改善数值分析数值分析数值分析数值分析例例4 4 应用按比例消元法求解应用按比例消元法求解 方程组方程组 3321221132110410234332ExxxExxExxx2,51,43,21, 110, 4, 2331221111321 rsasasaksss对对解解：2 2、在第、

19、在第k k步消元前，选最小的步消元前，选最小的r r，使，使iiknikrrksasa max3 3、对换、对换 E Ek k E Er r , s, sk k s sr r 4 4、消元、消元 具体步骤如下：具体步骤如下：1 1、在第一步消元前，计算、在第一步消元前，计算niasijnji,2,1max1 数值分析数值分析数值分析数值分析得得：2323332222, 315113022,3123/22ssEErsasak 10211141178432234322321084322434312333232121333222321121 xxxExExxExxsExxsExxsExx解解得得：消

20、消元元，得得12121211221231232123323312334334322323210410224834,2,10EEssxxExxExxxExxExxxExxEsss 对对换换，得得：消消元元，得得数值分析数值分析数值分析数值分析算法算法 按行比例列主元高斯消元法解线性方程组按行比例列主元高斯消元法解线性方程组 Ax = bAx = b停停机机。信信息息输输出出失失败败则则认认为为如如果果使使确确定定、选选列列主主元元步步。循循环环执执行行到到第第对对、, , 0det , 0 ,max 2 51, 2 , 1 , 1,max, 1det 1 1 kikiiiknikikikijnj

21、ikkkkaaSaSainkniaS kkkikikjikjkSSbbnkkjaaki detdet , ), 1,( , 4 , 3否否则则交交换换行行步步转转出出执执行行第第、如如果果数值分析数值分析数值分析数值分析。、输输出出解解向向量量、否否则则停停机机。输输出出失失败败信信息息则则认认为为如如果果、回回代代求求解解、FTnnniinijjijiinnnnnnnnkkAAbbbxanniababbabbaaadet, ,),( 8detdet7)1 , 2 , 2, 1( / )( / , 0,6detdet 5211 (3) ), 1( (2) /(1) , 2, 14kikiikj

22、ikijijkkikikikbabbnkjaaaaaamankki 、消消元元计计算算数值分析数值分析数值分析数值分析,(3)Axbxxxxxxxx 求求解解，迭迭代代改改善善计计算算解解 有有误误差差则则精精确确解解,()()xAxbAxA xxbA xbA xbA xxbAx 以上未知，但由以上未知，但由可得到可得到A xbbAxrxxxx 解方程组解出解方程组解出就得到改进解就得到改进解这个过程可以用迭代方法重复进行，这就是这个过程可以用迭代方法重复进行，这就是计算解的迭代改善法（余量校正法）。计算解的迭代改善法（余量校正法）。数值分析数值分析数值分析数值分析rbAxA xrxxx 迭迭

23、代代改改善善法法：迭代改善的计算格式：迭代改善的计算格式：(1)()()()(1)()()0Pr(1, 2,.)kkkkkkxbAxLYUxYxxxk ( (k k) )取取r r(1)1x 问问题题： 可可否否取取数值分析数值分析数值分析数值分析det( ),1.1AA如如数数量量级级差差别别大大，分分布布零零乱乱，特特病病态态问问题题的的识识别别：有有以以下下几几种种方方法法（）由由 的的直直观观信信息息，判判断断病病态态的的可可能能征征值值分分布布分分散散，的的大大小小 但但都都只只是是性性。可可能能性性。 12(,)det( ),( ),( ),.,( ),1,2,.,m nn nni

24、ARARAr AAcond Air 这这是是关关于于数数学学稳稳定定性性的的问问题题刻刻画画矩矩阵阵固固有有属属性性的的量量有有：奇奇异异值值这这些些量量从从不不同同角角四四、病病态态方方程程组组度度考考察察矩矩的的处处理理阵阵的的好好坏坏。数值分析数值分析数值分析数值分析10 10111011001det( )1( )5120ARACond A 如：如：100 10010012121det( )( )12ARACond A 数值分析数值分析数值分析数值分析(2)( )Cond A 有有一一些些近近似似方方法法，带带有有经经验验性性，但但不不增增估估计计加加计计算算量量。(3)()AxbAA

25、xbxx 比比较较所所得得结结果果， 与与 相相差差大大，试试算算和和则则病病态态。111111,()| | | |AxbAAAAxbAxbxA bA AxAAA xxAAxxxAAxxxAAx 对对有有小小扰扰动动由由1| |( )|,( ),|xxAAACond AAxxxACond AAx 得得到到若若大大 则则大大 因因为为小小。数值分析数值分析数值分析数值分析病态严重：病态严重：1:1:正交分解正交分解2:2:A A的奇异值分解。的奇异值分解。轻度病态：轻度病态：1:1:双精度改善双精度改善2:2:比例增减改善比例增减改善3:3:迭代改善。迭代改善。2.解的精度改进解的精度改进数值分析数值分析数值分析数值分析证明证明：病态的程度。病态的程度。接近奇异接近奇异的大小可作为度量矩阵的大小可作为度量矩阵最小的奇异值最小的奇异值分解分解的的nnTTnAAAAAconddiagVUASVDA 1minmax221)()()(),.,(,)