数值分析-误差分析和解的精度改进课件.ppt

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

2、的方方程程组组是是近近似似方方程程组组将将对对解解的的精精度度产产生生影影响响。2（）计计算算过过程程中中，舍舍入入误误差差的的传传播播和和积积累累将将影影响响解解的的精精度度。12解解的的稳稳定定性性：“小小的的误误差差会会不不会会引引起起解解的的很很大大变变化化”有有两两种种解解的的稳稳定定性性概概念念：（）数数值值方方法法的的稳稳定定性性：与与数数值值方方法法有有关关。（）数数学学稳稳定定性性：是是由由数数学学问问题题本本身身故故有有属属性性所所决决定定的的，与与数数值值方方法法无无关关。即即通通常常所所说说的的“病病态态问问题题”和和“良良态态问问题题”。数学稳定性数学稳定性:对数学问

3、题而言，如果输入数据有对数学问题而言，如果输入数据有微小扰动，引起输出数据（即数学问题的解）有很微小扰动，引起输出数据（即数学问题的解）有很大扰动，则称数学问题是大扰动，则称数学问题是病态问题病态问题，否则称为，否则称为良态良态问题问题。数值方法的稳定性数值方法的稳定性:一个算法如果输入数据有扰一个算法如果输入数据有扰动（即有误差），而计算过程中舍入误差不增长，动（即有误差），而计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称此算法为不稳定则称此算法是数值稳定的，否则称此算法为不稳定的。的。151210.31032105(1)(0,0.333),(1.0,1.667)(2)(0.033

4、3,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,1.0)(0.217,0.254)2TTTTxxxAxxAx 顺顺序序消消元元列列主主元元消消元元例例120.78010.56290.2170.91300.65910.254(3)(0.2528,0.0352)(0.217

5、,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.2170.9130.6590.254(1)(1.0,1.0)(0.217,0.254)(2)(1.0,1.0)(0.217,0.254)2TTTTxxxAxxAx 顺顺序序消消元元列列主主元元消消元元例例|1.|xxxxxxrbAxbbx 解解的的相相对对误误差差

6、不不知知道道是是否否可可改改用用相相对对剩剩余余量量来来估估计计误误差差两两种种误误差差估估用用计计即即代代替替二二、方方程程组组的的状状态态和和条条件件数数由由前前面面例例子子说说明明是是不不可可以以的的。为为什什么么？下下面面我我们们来来证证明明事事后后误误差差估估计计。11*rArAebAbxA 将将上上两两式式合合并并就就推推出出*,()exxrbAxAxAxA xxAe 事事后后误误差差估估记记计计1rbAxAeeA r 由由和和可可得得到到,1rAeAr *1*1,bAxb xA bxAbA由由得得，1*erA Abx 得得到到事事后后误误差差估估计计1,.A A 当当很很大大时时

7、 不不能能用用相相对对剩剩余余量量来来估估计计解解的的相相对对误误差差|bAx 又又1,0bbA 先先验验误误差差估估计计：（）只只有有 有有扰扰动动bAxbxAbbxxAbAx 1)(相减得相减得|1bAx 11|AbxbAAbxbA 解解的的相相对对误误差差估估计计式式111|1|1|,|20AAbAAAAAxAxAA 当当时时，解解的的相相对对误误差差（）只只有有扰扰动动估估计计式式为为有有1|130,0AAAb 当当时时，解解的的相相对对（）误误差差估估计计式式为为1*1()1AbA AxAbxAA .,1,1max0是非奇异的是非奇异的时时当当因此因此与所设矛盾与所设矛盾由范数定义由

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

9、):AxbAAxxbbAAxbAx 两两式式相相减减得得证证明明111,().AAIAA 设设由由引引理理知知非非奇奇异异11111)()(,)(AAAIAAAAIAAA 有有也非奇异也非奇异于是于是111*()()xIAAAbxA111*1*1()()()1xIAAAbxAAbxAxAA 由由引引理理的的估估计计式式得得到到bAxxAb *1,即即由由AAbbAAAAxx 11*1)(得得到到这就是由这就是由A A和和b b的原始数据小的扰动引起解的相对误差界的原始数据小的扰动引起解的相对误差界:(),.Acond AAAxb 若若线线性性代代数数方方程程组组的的系系数数矩矩阵阵 的的条条件

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

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

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

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

14、axminmax2 IIQQQQQcondTT 21.,()1.Qcond Q 正正交交阵阵的的谱谱条条件件数数等等于于即即若若 是是正正交交阵阵 则则22|n nARAAAQA QA Q AQ AA 同同样样，对对有有，则则，且且正正交交变变换换后后，误误差差也也没没有有增增加加。22,|()()()()|TTTQ xQxQ xx Q Qxxxx 其其中中是是的的误误差差 且且即即正正交交变变换换后后，没没有有增增加加误误差差。在正交变换下，误差不增长在正交变换下，误差不增长,nn nxRxxxxQRQxQxQ x 对对有有误误差差，用用正正交交阵阵作作变变换换，2.(1)(2)(3)Axb

15、 解解的的精精度度改改进进双双在在良良态态下下，用用稳稳定定的的数数值值方方法法求求解解，也也总总是是会会有有误误差差的的，可可用用以以下下方方法法改改进进计计算算解解的的精精度度。用用双双精精度度计计算算，有有效效数数字字增增加加了了，舍舍入入误误差差自自然然会会减减少少。精精度度改改善善：（行行）比比例例增增减减改改善善迭迭代代改改善善三三、数数值值稳稳定定性性及及解解的的精精度度改改进进1.Axb 结结论论：直直接接法法解解，用用顺顺序序消消元元是是不不稳稳定定，而而用用选选主主元元（列列主主元元）是是数数值值稳稳定定性性稳稳定定的的。前面介绍的列主元法解决了前面介绍的列主元法解决了Ga

16、ussGauss消元法由于小主元的出消元法由于小主元的出现所导致的舍入误差的积累，从而出现的失真的问题。但列主现所导致的舍入误差的积累，从而出现的失真的问题。但列主元法也有缺点，当方程中出现比例因子时，列主元法就无能为元法也有缺点，当方程中出现比例因子时，列主元法就无能为力了。力了。41212121011,02xxGaussxxxx 法法求求解解，失失真真列主元法求解列主元法求解x1 1=x2 2=1=13771212121010101,02xxxxxx 列列主主元元法法求求解解，失失真真 按行比例按行比例消元法消元法 :将每个方程乘上一个适当的比例因子，使将每个方程乘上一个适当的比例因子，使

17、方程组的最大系数的绝对值不超过方程组的最大系数的绝对值不超过1 1，然后再做列主元消元。，然后再做列主元消元。（2）（行）比例增减改善）（行）比例增减改善例例4 4 应用按比例消元法求解应用按比例消元法求解 方程组方程组 3321221132110410234332ExxxExxExxx2,51,43,21,110,4,2331221111321 rsasasaksss对对解解：2 2、在第、在第k k步消元前，选主元指标步消元前，选主元指标r r使使iiknikrrksasa max3 3、对换、对换 E Ek k E Er r ,s,sk k s sr r 4 4、消元、消元 具体步骤如下

18、：具体步骤如下：1 1、在第一步消元前，计算、在第一步消元前，计算niasijnji,2,1max1 得得：2323332222,315113022,3123/22ssEErsasak 10211141178432234322321084322434312333232121333222321121 xxxExExxExxsExxsExxsExx解解得得：消消元元，得得12121211221231232123323312334334322323210410224834,2,10EEssxxExxExxxExxExxxExxEsss 对对换换，得得：消消元元，得得算法算法:按行比例列主元高斯消元法

19、解线性方程组按行比例列主元高斯消元法解线性方程组Ax=b停停机机。信信息息输输出出失失败败则则认认为为如如果果使使确确定定、选选列列主主元元步步。循循环环执执行行到到第第对对、,0det ,0,max 2 51,2,1 ,1,max,1det 1 1 kikiiiknikikikijnjikkkkaaSaSainkniaS kkkikikjikjkSSbbnkkjaaki detdet,),1,(,4 ,3否否则则交交换换行行步步转转出出执执行行第第、如如果果。、输输出出解解向向量量、否否则则停停机机。输输出出失失败败信信息息则则认认为为如如果果、回回代代求求解解、FTnnniinijjiji

20、innnnnnnnkkAAbbbxanniababbabbaaadet,),(8detdet7)1,2,2,1(/)(/,0,6detdet 5211 (3),1(2)/(1),2,14kikiikjikijijkkikikikbabbnkjaaaaaamankki 、消消元元计计算算,(3)Axbxxxxxxxx 求求解解，迭迭代代改改善善计计算算解解 有有误误差差则则精精确确解解,()()xAxbAxA xxbA xbA xbA xxbAx 以上未知，但由以上未知，但由可得到可得到A xbbAxrxxxx 解方程组解出解方程组解出就得到改进解就得到改进解这个过程可以用迭代方法重复进行，这就

21、是这个过程可以用迭代方法重复进行，这就是计算解的迭代改善法（余量校正法）。计算解的迭代改善法（余量校正法）。rbAxA xrxxx 迭迭代代改改善善法法：迭代改善的计算格式：迭代改善的计算格式：(1)()()()(1)()()0Pr(1,2,.)kkkkkkxbAxLYUxYxxxk (k k)取取r r(1)1x 问问题题：可可否否取取det(),1.1AA如如数数量量级级差差别别大大，分分布布零零乱乱，特特病病态态问问题题的的识识别别：有有以以下下几几种种方方法法（）由由 的的直直观观信信息息，判判断断病病态态的的可可能能征征值值分分布布分分散散，的的大大小小 但但都都只只是是性性。可可能

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

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

24、异的大小可作为度量矩阵的大小可作为度量矩阵最小的奇异值最小的奇异值分解分解的的nnTTnAAAAAconddiagVUASVDA 1minmax221)()()(),.,(,)1(S SS S,1,(1,2,.,)TTiiiAUVEu vin 若若定定义义秩秩为为 的的矩矩阵阵1212(,.,),(,.,),nnUu uuVv vv奇异值分解的应用奇异值分解的应用11221211221110,.nnTnnnnFnAEEEAUVEEEAAAA 则则有有再再令令显显然然 是是奇奇异异矩矩阵阵 则则有有结结论论因因此此可可以以作作为为度度量量矩矩阵阵 接接近近奇奇异异的的程程度度1121121(2)

25、1111,(,.,)0,111(,.,0)()TTnnnTnAU VAVdiagUAxbxVdiagU b SS 用用奇奇异异值值分分解解求求病病态态方方程程组组的的欧欧氏氏范范数数最最小小的的解解对对小小扰扰动动很很敏敏感感，存存在在不不止止一一个个解解欧欧氏氏范范数数最最小小的的解解 要想成为一名计算机算法语言的要想成为一名计算机算法语言的明智的使用者，那么掌握归纳、递推明智的使用者，那么掌握归纳、递推等基本概念，理解算法的精确性、经等基本概念，理解算法的精确性、经济性和稳定性的属性则是非常重要的。济性和稳定性的属性则是非常重要的。培养培养“数觉数觉”：当计算机接替了大量计算，对机器当计算机接替了大量计算，对机器的使用者来说，聪明地设计正确算的使用者来说，聪明地设计正确算法和解释结果是很重要的。设计计法和解释结果是很重要的。设计计算需要充分理解运算的意义，解释算需要充分理解运算的意义，解释结果需要会判断机器输出的某个结结果需要会判断机器输出的某个结果正确与否，如果有错，错误是来果正确与否，如果有错，错误是来自数据输入、运算的选择或是机器自数据输入、运算的选择或是机器的运行。的运行。二版习题二版习题 P116-24,26,28三版习题三版习题 P138-14,16,18