迭代法的收敛条件.ppt

* 解线性方程组的迭代法 3.5.3　误差估计 定理3.7　设有迭代格式 若 收敛于 则有误差估计式 证明: 因为 故 于是 存在, 方程组 (即 有惟一解 ) 且 从而有 p35 * 解线性方程组的迭代法 取范数得 * 解线性方程组的迭代法 又因为 于是 取范数得 移项得 又 * 解线性方程组的迭代法 将(3-28)代入(3-27)得 有了误差估计(3-26), 根据事先给定的精度 可以估算出迭代的次数k p32 * 解线性方程组的迭代法 例如对迭代格式 其中 取 有 代入式(3-29)得 * 解线性方程组的迭代法 所以需要迭代13次才能保证各分量误差绝对值 不超过 实际计算时, 常常采用事后估计误差的方法, 即利用相邻两次迭代值之差是否达到精度作为停 机准则. 因而下面的结论比定理3.7 更实用. * 解线性方程组的迭代法 定理3.8　在定理3.7的条件下,有 证明: 因为 所以 * 解线性方程组的迭代法 由定理3.8,为使 只要 即可.实际计算时, 当 不太接近1时,可用 作为停机准则, 即为满足精度 之近似解. 拉格朗日(Lagrange )插值 牛顿(Newton)插值 分段线性插值 第5章 插值法 样条插值 埃尔米特(Hermite)插值 快速傅里叶变换(FFT) 应用实例 1 生产实践中常常出现这样的问题： 给出一批离散样点, 要求作出一条通过这些点的光滑曲线，以便满足设计要求或进行加工. 反映在数学上，既已知函数在一些点上得 值，寻求它的分析表达式. 因为由函数的表格形式不能 直接得出表中未列点处的函数值，也不便于研究函数的 的性质. 此外，有些函数虽然有表达式，但因式子复杂， 不易计算其值和进行理论分析，也需要构造一个简单 函数来近似它. 解决这种问题的方法有两种： 插值法 2 一类是给出函数 的一些点值，选定一个便于计算 的函数形式，如多项式，分式线性函数和三角多项式 等，要求它通过已知样点，由此确定函数 作为 的近似.这就是插值法。 另一类方法在选定近似函数形式后,不要求近似 函数过已知样点,只要求在某种意义下它在这些点上的 总偏差最小. 拟合法. 本章主要讨论构造插值多项式的几种常用方法及 其误差. 这类方法称为曲线(数据) 插值法 3 设函数 在区间 上有定义,它在该区间上 n+1个互异点 处的函数值为已知,记为 若存在一个简单函数 使得 成立, 就称 为 的插值函数,点 称为插值节点, 区间 称为插值区间,求插值函数 的方法称为插值法. 4 * 解线性方程组的迭代法 3.5 迭代法的收敛条件 3.5.1 矩阵的谱半径 迭代法的收敛性与迭代矩阵的特征值有关。 定义3.3 设A为n阶方阵， 为 A的特征值， 称特征值模的最大值为矩阵A 的谱半径， 记为 称为矩阵 A 的谱. * 解线性方程组的迭代法 由特征值的定义容易得出，矩阵 矩阵的谱半径与范数有以下关系。 的谱是 因而 * 解线性方程组的迭代法 定理3.3 设 A为任意n阶方阵， 为任意由向量 范数诱导出的矩阵范数，则 [证明] 对 的任一特征值 及相应的特征向量 都有 因为 为非零向量，于是有 由 的任意性即得 * 解线性方程组的迭代法 定理3.4 设A为n阶方阵， 则对任意正数 存在一 种矩阵范数 使得 证明参看［１］ . 对任意n 阶方阵 A, 一般不存在矩阵范数 使得 但若 A为对称矩阵，则 下面的结论对建立迭代法的收敛性条件非常重要。 * 解线性方程组的迭代法 定理3.5 设 A 为n阶方阵， 则 ［证明］必要性. 若 而 于是由极限存在准则，有 由定义3.2得 的充要条件为 所以 * 解线性方程组的迭代法 充分性. 若 取 由定理3.4存在一种存在一种 使得 所以 而 于是 * 解线性方程组的迭代法 3.5.2　迭代法的收敛条件 定理３.６ 对任意初始向量 和右端项 由迭代格式 产生的向量序列 收敛的充要条件是 ［证明］ 设存在n 维向量 使得 则 满足 p9 * 解线性方程组的迭代法 由迭代公式(3-24),有 于是有 因为 为任意n维向量, 因此上式成立必须 由定理3.5 * 解线性方程组的迭代法 反之，若 则 不是M 的特征值， 因而有 于是对任意n维向量 g, 方程组 有唯一解，记为 即 并且 又因为 所以，对任意初始向量 都有 即由迭代公式(3-24)产生的向量序列 收敛. p7 * 解线性方程组的迭代法 由定理3.4即得 推论１在定理3.6的条件下,若 则 收敛. 推论２　松弛法收敛的必要条件是 ［证明］　设松弛法的迭代矩阵 有特征值　 因为 由定理3.6，松弛法收敛必有 p19 * 解线性方程组的迭代法 又因为 于是有 所以 * 解线性方程组的迭代法 定理3.6表明， 迭代法