方程组的误差估计学习培训模板课件.ppt

1、第四章方程组的直接解法4.3.2 方程组的误差估计方程组的误差估计4.3.1 矩阵的条件数矩阵的条件数4.3 方程组的性态和误差估计方程组的性态和误差估计第四章方程组的直接解法解解Ly=b得得y=(6,1,-1)T,解解LTx=D-1y得得x=(2,1,-1)T4.3.1 矩阵的条件数矩阵的条件数定义定义4.1 如果方程组如果方程组Ax=b中，矩阵中，矩阵A和和b右端的微小变化，引起解右端的微小变化，引起解向量向量x的很大变化，则称的很大变化，则称A为关于解发才组和矩阵求逆的为关于解发才组和矩阵求逆的病态矩阵病态矩阵，称相应的方程组为称相应的方程组为病态方程组病态方程组。否则，。否则，称称A为

2、为良态矩阵良态矩阵，称相应的，称相应的方程组为方程组为良态方程组良态方程组。0001.4410001.31321xx的准确解是（的准确解是（1，1）T。若。若A及及b作微小的变化，考扰动后的方程组作微小的变化，考扰动后的方程组 其准确解为（其准确解为（-2，10）T 先看一个例子，说明方程组的解对或的扰动的敏感性问题。先看一个例子，说明方程组的解对或的扰动的敏感性问题。例例4.9 方程组方程组 123142.9 9 9 914.0 0 0 2xx 在上例中，在上例中，A和和b的微小变化引起的微小变化引起x很大的变化，很大的变化，x对对A和和b的扰的扰动是敏感的。这种现象的出现完全是有方程组的性

3、态决定的。动是敏感的。这种现象的出现完全是有方程组的性态决定的。第四章方程组的直接解法方程组右端所引起的解向量的相对误差就可能越大。方程组右端所引起的解向量的相对误差就可能越大。bbAAxx 1 AA1 bb/可见，量可见，量是相对误差是相对误差的倍增因子，该量越大，的倍增因子，该量越大，又由于又由于，bAx 1 xAb x=A-1 b，即得即得我们需要一种能刻画矩阵和方程组病态程度的标准。暂且不考虑我们需要一种能刻画矩阵和方程组病态程度的标准。暂且不考虑矩阵矩阵A的扰动，仅须考虑的扰动，仅须考虑b 的扰动对方程组的影响，设方程组的扰动对方程组的影响，设方程组Ax=b的扰的方程组为的扰的方程组

4、为A（x+x）=b+b，则，则AA1 为矩阵为矩阵A的条件数。的条件数。如果矩阵范数取如果矩阵范数取2范数，则记范数，则记定义定义4.2 设设ARnn为可逆矩阵，按算子范数，称为可逆矩阵，按算子范数，称 cond（A）=同样可以定义同样可以定义cond（A）和）和cond1（A）。）。按（。按（4.3.1），），1222cond(A)AA第四章方程组的直接解法 （1）其中）其中cond（A）1，cond（A）=cond（A-1），），cond（A）=cond（A），其中），其中 R，0 （2）若）若U为正交矩阵，即为正交矩阵，即UT U=I则则cond2（U）=1，cond2（A）=cond2

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

6、（H6）=1.4951 107，cond2（H8）=1.525 1010。由此可见，随着。由此可见，随着n的增加，的增加，Hn的病态可能越严重。的病态可能越严重。Hn常常在数据拟合和函数逼近中出现常常在数据拟合和函数逼近中出现。对于实际问题，条件数一般是很难计算的。下列现象可能表示方对于实际问题，条件数一般是很难计算的。下列现象可能表示方程组程组Ax=b是病态的。是病态的。（1）如果矩阵）如果矩阵A的按绝对值最大特征值和最小特征值之比很大，的按绝对值最大特征值和最小特征值之比很大，则则A是病态的。是病态的。（2）如果系数矩阵）如果系数矩阵A的元素间数量级很大，并且无一定规则，则的元素间数量级很

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

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

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

10、两端取范数，则有将上式两端取范数，则有bbxxAA)(证证.将代入扰动方程组将代入扰动方程组，整理后有，整理后有1()()()xAbA xAx第四章方程组的直接解法 xAbAxAA 11)1(经整理后得经整理后得由于由于11 AA)(111xAbAAAx xAb，即得所证。，即得所证。再利用再利用，则有，则有若若)1()(1)(1AAAAcondAAAAAcondxx 0,0bA时，则由（时，则由（4.3.2）有）有xbrAcondxxxbrAcond)()(1 定理定理4.10 设设Ax=b，b0，则对方程组的近似解，则对方程组的近似解有误差估计式有误差估计式第四章方程组的直接解法 该定理说

11、明，当该定理说明，当cond(A)很大时，即使方程组余量很大时，即使方程组余量r 的相对误差已的相对误差已经很小，但近似解的相对误差仍然可能很大。经很小，但近似解的相对误差仍然可能很大。如果用直接解法得到的近似解如果用直接解法得到的近似解 误差很大，我们可以用迭代改善误差很大，我们可以用迭代改善的办法对近似解进行修正。设的办法对近似解进行修正。设r=b-A ，x为修正量，为修正量，为新的近似解。这样为新的近似解。这样，我们可以通过求解，我们可以通过求解 A x=r得到得到 ，显，显然，在准确运算下有然，在准确运算下有xxxxxxxArbxxAxA)(（4.3.3）xxx=A（x-）brAcon

12、dbAArxxx)(111 证证 由由Ax=b有有 r=Ax-A 又由又由x=A-1 b，有，有定理得证。定理得证。其中其中r=b-A 为剩余向量。为剩余向量。1|()|xxrAA rcond Axbb第四章方程组的直接解法 方程组直接解法的稳定性是应当注重的问题。如果通过直接计算每方程组直接解法的稳定性是应当注重的问题。如果通过直接计算每一步设入误差对解的影响来获得近似解的误差界，那将是非常困难的一步设入误差对解的影响来获得近似解的误差界，那将是非常困难的。J.H.Wilkinson等人提出了等人提出了“向后误差分析法向后误差分析法”，其基本思想是把计算过，其基本思想是把计算过程中设入误差对

13、解的影响归结为原始数据对解的影响。下面给出一个定程中设入误差对解的影响归结为原始数据对解的影响。下面给出一个定理来说明这方面的结果。理来说明这方面的结果。然而，再实际计算时，方程组（然而，再实际计算时，方程组（4.3.3）不大可能求解，所以解（）不大可能求解，所以解（4.3.3）只能提供有限的修正。因此，需要反复求解为（只能提供有限的修正。因此，需要反复求解为（4.3.3）的方程组，不断）的方程组，不断对所得的近似解进行改进。这种近似值逐进接近真解的过程称为迭代解对所得的近似解进行改进。这种近似值逐进接近真解的过程称为迭代解法。为了节省计算量，可事先对矩阵法。为了节省计算量，可事先对矩阵A进行

14、进行LU分解，把反复解形为分解，把反复解形为（4.3.3）的方程组改为反复解形为）的方程组改为反复解形为Ly=r，Ux=y 的方程组。为了保证的方程组。为了保证计算精度，计算剩余向量计算精度，计算剩余向量r可采用高精度计算。可采用高精度计算。定理定理4.11 设设ARnn，A为非奇异矩阵，用列主元法或全主元法为非奇异矩阵，用列主元法或全主元法解方程组解方程组x kijkijnjiaAa,/max,1 Ax=b，其计算解，其计算解满足满足。记计算机尾数字长。记计算机尾数字长是消去过程中是消去过程中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）计算解有精度估计：）计算解有精度估计：