数值分析课件：5.5方程组的性态与误差估计.ppt

1、第四章方程组的直接解法5.5.2 方程组的误差估计方程组的误差估计5.5.1 矩阵的条件数矩阵的条件数5.5 方程组的性态和误差估计方程组的性态和误差估计第四章方程组的直接解法5.5.1 矩阵的条件数矩阵的条件数定义定义5.5.1 如果方程组如果方程组Ax= b中，矩阵中，矩阵A和右端常数项和右端常数项b的微小变化，的微小变化，引起解向量引起解向量x的很大变化，则称的很大变化，则称A为为病态矩阵病态矩阵(相对于方程组而言相对于方程组而言) ，称相应的方程组为称相应的方程组为病态方程组病态方程组。否则，。否则， 称称A为为良态矩阵良态矩阵，称相应的，称相应的方程组为方程组为良态方程组良态方程组。

2、 0001. 4410001. 31321xx 若若A及及b作微小的变化，扰动后的方程组作微小的变化，扰动后的方程组 其准确解为（其准确解为（-2，10）T 先看一个例子，说明方程组先看一个例子，说明方程组Ax=b的解对的解对A(或或b)的扰动的敏感性问题的扰动的敏感性问题. 123142 .9 9 9 914 .0 0 0 2xx 在上例中，在上例中， A和和b的微小变化引起的微小变化引起x很大的变化，很大的变化， x对对A和和b的扰的扰动是敏感的。这种现象的出现完全是由方程组的性态决定的。动是敏感的。这种现象的出现完全是由方程组的性态决定的。例例5.7 方程组方程组的准确解是的准确解是(1

3、,1) T.第四章方程组的直接解法1.先考察常数项先考察常数项b的微小误差对解的影响。的微小误差对解的影响。设设A是精确的，且为非奇异矩阵，是精确的，且为非奇异矩阵，b有误差（或扰动）有误差（或扰动）b。x为为Ax=b 的精确解。的精确解。 方程组方程组 的解与的解与 x 的差记为：的差记为： bbxA从而从而 |x| | | *|b| 1A即即 bAx1又又 Ax=b0 则则 |b|A| * |x| xxx即：即： A(x+x) =b+ b， 即：即： A(x)=b.（假设（假设Ax=b0)我们需要一种能刻画矩阵和方程组病态程度的标准。我们需要一种能刻画矩阵和方程组病态程度的标准。第四章方程

4、组的直接解法 式说明：当式说明：当b有一定相对误差时，引起解有一定相对误差时，引起解Ax=b解的变化的相对解的变化的相对误差上界由误差上界由给出。解的相对误差是常数项相对误差的给出。解的相对误差是常数项相对误差的 倍。倍。|1AA由由得下面结论得下面结论:定理定理 (b扰动对解的影响扰动对解的影响)设：设： 1） 设设Ax=b0 ，x 为精确解，为精确解，detA 0 ； 2）且设）且设 A(x+x)=b+b 则有则有:|1bbAAxx第四章方程组的直接解法AA1 如果矩阵范数取如果矩阵范数取2范数，则记范数，则记定义定义5.5.2 设设ARnn为可逆矩阵，按算子范数，称为可逆矩阵，按算子范数

5、，称 cond（A）=同样可以定义同样可以定义cond（A）和）和cond1（A）。）。 。按（。按（ 5.5.1），），1222cond (A)AA为矩阵为矩阵A的条件数。的条件数。)()(|)cond( |)cond( |)cond( minmax212211111AAAAAAAAAAAAATT常用的条件数有(5.5.1)第四章方程组的直接解法.,|)cond( n112特征值的绝对值最大和最小的为其中为对称矩阵时当AAAn第四章方程组的直接解法 （1）cond（A）1， cond（A）= cond（A-1），）， cond（ A）= cond (A), 其中其中 R， 0n /1若若A对

6、称，则对称，则cond2（A） =设设A-1存在，条件数有如下一些性质：存在，条件数有如下一些性质：1nn 1cond（A） （3）设）设 与与 为为A按绝对值最大和最小的特征值，则按绝对值最大和最小的特征值，则（2）若）若U为正交矩阵，即为正交矩阵，即UT U=I , 则则cond2（U）=1， cond2（A）= cond2（AU）= cond2（UA）。）。第四章方程组的直接解法 ) 12/(1) 1/(1/1) 1/(13/12/1/12/11nnnnnHn例例5.10 下列下列Hilbert矩阵是一族著名的病态矩阵：矩阵是一族著名的病态矩阵：它是一个它是一个nn的对称矩阵，可以证明是

7、正定的。的对称矩阵，可以证明是正定的。计算条件数有计算条件数有cond2（H4）= 1.5514 104 ， cond2（ H6）=1.4951 107，cond2（ H8）= 1.525 1010。由此可见，随着。由此可见，随着n的增加，的增加， Hn的病的病态可能越严重。态可能越严重。 Hn常常在数据拟合和函数逼近中出现常常在数据拟合和函数逼近中出现 。第四章方程组的直接解法练习：已知练习：已知Hilbert矩阵：矩阵：1112111231111121nnHnnnn计算H3的条件数。解：5/14/13/14/13/12/13/12/113H13936303619218030180180H

8、下面计算H3的条件数1333()|11/ 6 |408Cond HHH，由，同样可计算 ，一般Hn矩阵当n越大时，病态越严重。1333()| |11/6 408=748Cond HHH66109 . 2)(HCond则：第四章方程组的直接解法对于实际问题，条件数一般是很难计算的。下列现象可能表示方对于实际问题，条件数一般是很难计算的。下列现象可能表示方程组程组Ax=b是病态的。是病态的。 （1）如果矩阵）如果矩阵A的按绝对值最大特征值和最小特征值之比很大，的按绝对值最大特征值和最小特征值之比很大，则则A是病态的。是病态的。 （2）如果系数矩阵）如果系数矩阵A的元素间数量级很大，并且无一定规则，

9、则的元素间数量级很大，并且无一定规则，则A可能病态。可能病态。（3）如果系数矩阵）如果系数矩阵A的某些行或列是近似相关的，或系数矩阵的的某些行或列是近似相关的，或系数矩阵的行列式值相对说很小，则行列式值相对说很小，则A可能病态。可能病态。 （4）如果在）如果在A的三角化过程中出现小主元或采用选主元技术，主的三角化过程中出现小主元或采用选主元技术，主元素数量级相差悬殊时，则元素数量级相差悬殊时，则A可能病态。可能病态。对于病态方程组，数值求解必须小心进行，否则达不到所要求的对于病态方程组，数值求解必须小心进行，否则达不到所要求的准确度。有时可以用高精度（如双精度或扩充精度）的运算，以改善准确度。

10、有时可以用高精度（如双精度或扩充精度）的运算，以改善或减轻方程组的病态程度，有时也可以对原方程组作预处理，以降低或减轻方程组的病态程度，有时也可以对原方程组作预处理，以降低第四章方程组的直接解法系数矩阵的条件数，即选择非奇异矩阵系数矩阵的条件数，即选择非奇异矩阵P和和Q，一般选，一般选P和和Q为对角阵或三为对角阵或三角矩阵，使角矩阵，使 cond（ PAQ ） cond(A)然后，求解等价方程组然后，求解等价方程组PAQ y=Pb ， y =Q-1x。55151 101101,.1 101111AA.11110101055 APAB例如，对矩阵例如，对矩阵有有cond 105。若进行预处理。若

11、进行预处理则则cond （B）=4，条件数有改善。，条件数有改善。第四章方程组的直接解法5.5.2 方程组的误差估计方程组的误差估计定理定理5.9 设设Ax=b，A为非奇异矩阵，为非奇异矩阵， b为非零向量，为非零向量， A和和b分别有分别有扰动，扰动， A和和 b, 。若。若 1,则有则有误差估计式误差估计式bbxxAA )(AA 1 由于舍入误差，我们解方程组往往得到的是近似解。下面利用由于舍入误差，我们解方程组往往得到的是近似解。下面利用条件数给出近似解的事前误差估计，即计算之前和计算之后的误差估条件数给出近似解的事前误差估计，即计算之前和计算之后的误差估计。计。1( )()1xAbco

12、nd AxAbAAxAxAbAx1将上式两端取范数，则有将上式两端取范数，则有bbxxAA)(证证. 将将Ax=b代入扰动方程代入扰动方程组组，整理后有，整理后有1()()()xAbA xAx(5.5.2)第四章方程组的直接解法 xAbAxAA 11)1(经整理后得经整理后得由于由于11 AA )(111xAbAAAx xAb ，即得所证即得所证。再利用再利用，则有，则有若若)1()(1)(1AAAAcondAAAAAcondxx 0, 0bA时，则由（时，则由（5.5.2）有）有第四章方程组的直接解法 例：P139第四章方程组的直接解法 该定理说明，当该定理说明，当cond(A)很大时，即使

13、方程组余量很大时，即使方程组余量r 的相对误差已的相对误差已经很小，但近似解的相对误差仍然可能很大。经很小，但近似解的相对误差仍然可能很大。xxx=A（x- ）brAcondbAArxxx)(111 证证 由由Ax=b有有 r=Ax- A 又由又由x= A-1 b ，有，有定理得证。定理得证。其中其中r=b- A 为剩余向量。为剩余向量。1|( )|xxrAA rcond AxbbxbrAcondxxxbrAcond)()(1 定理定理5.10 设设Ax=b ， b0，则对方程组的近似解，则对方程组的近似解有误差估计式有误差估计式第四章方程组的直接解法如果用直接解法得到的近似解如果用直接解法得

14、到的近似解 误差很大，我们可以用迭代改善误差很大，我们可以用迭代改善的办法对近似解进行修正。设的办法对近似解进行修正。设r=b- A ，x为修正量，为修正量，为新的近似解。这样为新的近似解。这样 ，我们可以通过求解，我们可以通过求解 A x = r得到得到 ，显，显然，在准确运算下有然，在准确运算下有xxxxxxxArbxxAxA)(（5.5.3）x然而，再实际计算时，方程组（然而，再实际计算时，方程组（5.5.3）不大可能求解，所以解（）不大可能求解，所以解（5.5.3）只能提供有限的修正。因此，需要反复求解为（只能提供有限的修正。因此，需要反复求解为（5.5.3）的方程组，不断）的方程组，

15、不断对所得的近似解进行改进。这种近似值逐进接近真解的过程称为迭代解对所得的近似解进行改进。这种近似值逐进接近真解的过程称为迭代解法。为了节省计算量，可事先对矩阵法。为了节省计算量，可事先对矩阵A进行进行LU分解，把反复解形为分解，把反复解形为（5.5.3）的方程组改为反复解形为）的方程组改为反复解形为Ly=r，Ux=y 的方程组。为了保证的方程组。为了保证计算精度，计算剩余向量计算精度，计算剩余向量r可采用高精度计算。可采用高精度计算。第四章方程组的直接解法 方程组直接解法的稳定性是应当注重的问题。如果通过直接计算每方程组直接解法的稳定性是应当注重的问题。如果通过直接计算每一步设入误差对解的影

16、响来获得近似解的误差界，那将是非常困难的一步设入误差对解的影响来获得近似解的误差界，那将是非常困难的 。J.H.Wilkinson等人提出了等人提出了“向后误差分析法向后误差分析法”，其基本思想是把计算过，其基本思想是把计算过程中设入误差对解的影响归结为原始数据对解的影响。下面给出一个定程中设入误差对解的影响归结为原始数据对解的影响。下面给出一个定理来说明这方面的结果。理来说明这方面的结果。 定理定理5.11 设设ARnn ，A为非奇异矩阵，用列主元法或全主元法为非奇异矩阵，用列主元法或全主元法解方程组解方程组x kijkijnjiaAa,/max,1 Ax=b ，其计算解，其计算解满足满足。

17、记计算机尾数字长。记计算机尾数字长是消去过程中是消去过程中A(k)中的元中的元为为t，且，且n2-t 0.01 。素，则有素，则有AA xb第四章方程组的直接解法 该定理说明，矩阵该定理说明，矩阵A的阶数越高条件数越大矩阵元素的增长因子的阶数越高条件数越大矩阵元素的增长因子 越大和计算机字长越短，则舍入误差对解的影响越严重。因此计算精度越大和计算机字长越短，则舍入误差对解的影响越严重。因此计算精度取决于矩阵的规模、方程组的性态、所选取的算法和计算机字长。取决于矩阵的规模、方程组的性态、所选取的算法和计算机字长。UL,tAnEEAUL 2,2 （1）若）若A的的LU分解计算结果为分解计算结果为,则有则有（2） tAnnA 2301.123 tnnAAAcondxxx 2301.11)(231 （3）计算解有精度估计：）计算解有精度估计：