病态线性方程组.ppt

朱立永 北京航空航天大学数学与系统科学学院 数值分析 Email numerical analysis Password beihang答疑时间 星期三下午2 00 5 00答疑地点 主216 第四讲病态线性方程组求解 第二章线性方程组的解法 InScientificComputing LargeLinearSystemsAx bassub problems asintermediatesteps ConjugateGradientmethodforsymmetricsystems perturbation perturbation It sfunnythatsuchsmallperturbationsinthecoefficientsleadtosobigchangeinthesolution 数值算例 提问 求解Ax b时 A和b的误差对x有何影响 由实际问题建立起来的线性方程组Ax b本身存在模型误差和观测误差 或者是由计算得到的 存在舍入误差等 总之 A b都会有一定扰动 A b 因此实际处理的是A A或b b 我们需要分析A或b的扰动对解的影响 矩阵的条件数与病态线性方程组 提问 求解Ax b时 A和b的误差对x有何影响 1 A非奇异 设精确 b有误差 b 导致解x有多大误差 2 设b精确 A有误差 A 导致解x有多大误差 设A非奇异 A A 1 1 3 设b A分别有误差 b和 A 导致解x有多大误差 设A非奇异 A A 1 1 解的相对误差 A的相对误差 b的相对误差 矩阵的条件数 Conditionnumber 定义 对非奇异矩阵A 称乘积 A A 1 为矩阵A的条件数 记为cond A A A 1 A A 1 是我们遇到的第二个放大因子 cond A 的具体大小与 有关 但相对大小一致 cond A 的大小本质取决于A 与解题的方法无关 cond A 如果A是奇异的 常用的矩阵条件数 例 Hilbert阵 注 现在用Matlab数学软件可以很方便求矩阵的条件数 矩阵条件数的一些性质 cond A 1 A非奇异 k 0 则cond kA cond A A非奇异对称矩阵 则cond A 2 1 n A是正交矩阵 则cond A 2 1 A可逆 R正交 则cond RA 2 cond AR 2 cond A 2 病态 良态线性方程组 定义 对线性方程组Ax b 若cond A 相对很大 则称Ax b是病态的线性方程组 若cond A 相对很小 则称Ax b是良态的线性方程组 一个病态线性方程组的例子 见书上 对于严重的病态线性方程组 即使原始数据A和b都没有误差 但如果在求解过程中有舍入误差 所得到的解也会有很大的相对误差 什么样的线性方程组可能是病态的 注 一般判断矩阵是否病态 并不计算A 1 而由经验得出 行列式很大或很小 如某些行 列近似相关 元素间相差大数量级 且无规则 主元消去过程中出现小主元 特征值相差大数量级 缓和甚至解决线性方程组病态的手段 采用高精度的算法 不是总有效 通过行或列的平衡来降低矩阵的条件数 平衡法 残差校正法 通过矩阵的预条件处理来降低矩阵的条件数 残差校正法步骤 求解Ax b 得到x的近似解x1 校正x1 令r1 b Ax1 解A x1 r1 x2 x1 x1 令r2 b Ax2 解A x2 r2 x3 x2 x2 令rk b Axk 解A xk rk Xk 1 xk xk 预条件技术 80年代提出 纯代数观点M近似A 求解 左预条件 My c易解相当于化学反应中寻找高效 廉价的催化剂 能极大地提高迭代方法的速度 预条件技术 续 代数预条件技术ILU SPAI SOR 多项式几何预条件技术某方向压缩粗化 网格均匀化 区域规则化近似分析预条件技术变系数常数化 Green函数稀疏近似 强化