方程组的性态和误差估计

第四章方程组的直接解法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为良态矩阵，称相应的方程组为良态方程组。0001.4410001.31321xx的准确解是（1，1）T。若A及b作微小的变化，考扰动后的方程组其准确解为（-2，10）T先看一个例子，说明方程组的解对或的扰动的敏感性问题。例4.9方程组123142.999914.0002xx在上例中，A和b的微小变化引起x很大的变化，x对A和b的扰动是敏感的。这种现象的出现完全是有方程组的性态决定的。第四章方程组的直接解法方程组右端所引起的解向量的相对误差就可能越大。bbAAxx1AA1bb/可见，量是相对误差的倍增因子，该量越大，又由于，bAx1xAbx=A-1b，即得我们需要一种能刻画矩阵和方程组病态程度的标准。暂且不考虑矩阵A的扰动，仅须考虑b的扰动对方程组的影响，设方程组Ax=b的扰的方程组为A（x+x）=b+b，则AA1为矩阵A的条件数。如果矩阵范数取2范数，则记定义4.2设A∈Rn×n为可逆矩阵，按算子范数，称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为正交矩阵，即UTU=I则cond2（U）=1，cond2（A）=cond2（AU）=cond2（UA）。（3）设与为A按绝对值最的和最小的特征值，则1nn1n/1若A对称，则cond2（A）=cond（A）≧设A-1存在，条件数有如下一些性质：)12/(1)1/(1/1)1/(13/12/1/12/11nnnnnHn例4.10下列Hilbert矩阵是一族著名的病态矩阵：第四章方程组的直接解法它是一个n×n的对称矩阵，可以证明是正定的。计算条件数有cond2（H4）=1.5514×104，cond2（H6）=1.4951×107，cond2（H8）=1.525×1010。由此可见，随着n的增加，Hn的病态可能越严重。Hn常常在数据拟合和函数逼近中出现。对于实际问题，条件数一般是很难计算的。下列现象可能表示方程组Ax=b是病态的。（1）如果矩阵A的按绝对值最大特征值和最小特征值之比很大，则A是病态的。（2）如果系数矩阵A的元素间数量级很大，并且无一定规则，则A可能病态。（3）如果系数矩阵A的莫些行或列是近似相关的，或系数矩阵的行列式值相对说很小，则A可能病态。（4）如果在A的三角化过程中出现小指元或采用选用选主远技术，主元素数量级相差悬除时，则A可能病态。对于病态方程组，数值求解必须小心进行，否则达不到所要求的准确度。有时可以用高精度（如双精度或扩充精度）的运算，以改善或减轻方程组的病态程度，有时也可以对圆方程组作预处理，以降低第四章方程组的直接解法系数矩阵的条件数，即选择非奇异矩阵P和Q，一般选着为对角阵或三角矩阵，使cond（PAQ）cond(A)然后，求解等价方程组PAQy=Py，y=Q-1x。.111011011,111015515AA.11110101055APAB例如，对矩阵有cond∞≈105。若进行预处理则cond∞（B）=4，条件数的改善。第四章方程组的直接解法4.3.2方程组的误差估计定理4.9设Ax=b，A为非奇异矩阵，b为非零向量，A和b分别有扰动，A和b,。若1,则有误差估计式bbxxAA))((AA1由于舍入误差，我们解方程组往往得到的是近似解。下面利用条件数给出近似解的事前误差估计，即计算之前和计算之后的误差估计。)(1)(1bbAAAAAcondxxxAxAbAx1将上式两端取范数，则有bbxxAA))((证.将代入扰动方程组，整理后有1()()()xAbAxAx第四章方程组的直接解法xAbAxAA11)1(经整理后得由于11AA)(111xAbAAAxxAb，即得所证。再利用，则有若)1()(1)(1AAAAcondAAAAAcondxx0,0bA时，则由（4.3.2）有x~brAcondxxxbrAcond)(~)(1定理4.10设Ax=b，b≠0，则对方程组的近似解有误差估计式第四章方程组的直接解法该定理说明，当cond(A)很大时，即使方程组余量r的相对误差已经很小，但近似解的相对误差仍然可能很大。如果用直接解法得到的近似解误差很大，我们可以用迭代改善的办法对近似解进行修正。设r=b-A，△x为修正量，为新的近似解。这样，我们可以通过求解A△x=r得到，显然，在准确运算下有xxx~x~xx~xArbxxAxA)~(（4.3.3）x~x~x~=A（x-）brAcondbAArxxx)(11~1证由Ax=b有r=Ax-A又由x=A-1b，有定理得证。其中r=b-A为剩余向量。1||||()||||xxrAArcondAxbb第四章方程组的直接解法方程组直接解法的稳定性是应当注重的问题。如果通过直接计算每一步设入误差对解的影响来获得近似解的误差界，那将是非常困难的。J.H.Wilkinson等人提出了“向后误差分析法”，其基本思想是把计算过程中设入误差对解的影响归结为原始数据对解的影响。下面给出一个定理来说明这方面的结果。然而，再实际计算时，方程组（4.3.3）不大可能求解，所以解（4.3.3）只能提供有限的修正。因此，需要反复求解为（4.3.3）的方程组，不断对所得的近似解进行改进。这种近似值逐进接近真解的过程称为迭代解法。为了节省计算量，可事先对矩阵A进行LU分解，把反复解形为（4.3.3）的方程组改为反复解形为Ly=r，U△x=y的方程组。为了保证计算精度，计算剩余向量r可采用高精度计算。定理4.11设A∈Rn×n，A为非奇异矩阵，用列主元法或全主元法解方程组x~kijkijnjiaAa,/max,1Ax=b，其计算解满足。记计算机尾数字长是消去过程中A(k)中的元为t，且n2-t≦0.01。素，则有~AAxb第四章方程组的直接解法该定理说明，矩阵A的阶数越高条件数越大矩阵元素的增长因子越大和计算机字长越短，则舍入误差对解的影响越严重。因此计算精度取决于矩阵的规模、方程组的性态、所选取的算法和计算机字长。UL~,~tAnEEAUL2,~~2（1）若A的LU分解计算结果为,则有（2）tAnnA2301.123tnnAAAcondxxx2301.11)(~231（3）计算解有精度估计：