迭代法及其收敛性ppt课件.ppt

数值计算方法 1 对于一般的非线性方程 没有通常所说的求根公式求其精确解 需要设计近似求解方法 即迭代法 它是一种逐次逼近的方法 用某个固定公式反复校正根的近似值 使之逐步精确化 最后得到满足精度要求的结果 10 2迭代法及其收敛性 2 10 2 1不动点迭代法的基本概念和迭代格式的构造 将方程 1 1 改写成等价的形式 2 1 若要求满足 则 反之亦然 称为函数的一个不动点 求的零点就等价于求的不动点 选择一个初始近似值 将它代入 2 1 右端 即可求得 如此反复迭代计算 2 2 3 称为迭代函数 如果对任何 由 2 2 得到的迭代序列有极限 则称迭代方程 2 2 收敛 且为的不动点 故称 2 2 为不动点迭代法 上述迭代法是一种逐次逼近法 其基本思想是将隐式方程 2 1 归结为一组显式的计算公式 2 2 就是说 迭代过程实质上是一个逐步显示化的过程 方程的求根问题在平面上就是要确定曲线与直线的交点 对于的某个近似值 在曲线上可确定一点 它以为横坐标 而纵坐标则等于 4 过引平行轴的直线 设此直线交直线于点 然后过再作平行于轴的直线 它与曲线的交点记作 则点的横坐标为 纵坐标则等于 图1 2 5 例1求方程 2 3 在附近的根 解设将方程 2 3 改写成下列形式 按图1 2中箭头所示的路径继续做下去 在曲线上得到点列 其横坐标分别为依公式求得的迭代值 据此建立迭代公式 如果点列趋向于点 则相应的迭代值收敛得到所求的根 6 各步迭代的结果见表 如果仅取6位数字 那么结果与完全相同 这时可以认为实际上已满足方程 2 3 即为所求的根 7 但若采用方程 2 3 的另一种等价形式 建立迭代公式 仍取迭代初值 则有 结果会越来越大 不可能趋于某个极限 这种不收敛的迭代过程称作是发散的 一个发散的迭代过程 纵使进行了千百次迭代 其结果也是毫无价值的 8 x2 9 10 2 2不动点的存在性与迭代法的收敛性 首先考察在上不动点的存在唯一性 定理1设满足以下两个条件 1 映内性对任意有 2 压缩性存在正常数 使对都有 2 4 10 证明先证不动点存在性 若或 显然在上存在不动点 因 以下设及 定 义函数 显然 且满足 由连续函数性质可知存在使 即即为的不动点 11 再证唯一性 设都是的不动点 则由 2 4 得 引出矛盾 故的不动点只能是唯一的 证毕 12 定理 2设满足定理1中的两个条件 则对任意 由 2 2 得到的迭代序列收敛到的不动点 并有误差估计 2 5 证明设是在上的唯一不动点 由条件1 可知 再由 2 4 得 因 故当时序列收敛到 再证明估计式 2 5 由李普希兹条件有 2 6 13 反复递推得 于是对任意正整数有 在上式令 注意到即得式 2 5 证毕 迭代过程是个极限过程 在用迭代法实际计算时 必须按精度要求控制迭代次数 14 误差估计式 2 5 原则上可用于确定迭代次数 但它由于含有信息而不便于实际应用 根据式 2 6 对任意正整数有 在上式中令知 由此可见 只要相邻两次计算结果的偏差足够小即可保证近似值具有足够精度 对上述定理中的压缩性 在使用时如果且对任意有 15 2 7 则由中值定理可知对有 表明定理中的压缩性条件可用 2 7 代替 例7 2 3中 当时 在区间中 故 2 7 成立 又因 故定理1中条件1 也成立 所以迭代法是收敛的 而当时 在区间中不满足定理条件 16 10 3局部收敛性与收敛阶 上面给出了迭代序列在区间上的收敛性 通常称为全局收敛性 定理的条件有时不易检验 实际应用时通常只在不动点的邻近考察其收敛性 即局部收敛性 定义7 2 1设有不动点 如果存在的某个邻域 对任意 迭代 2 2 产生的序列 且收敛到 则称迭代法 2 2 局部收敛 17 定理7 2 3设为的不动点 在的某个邻域连续 且 则迭代法 2 2 局部收敛 证明由连续函数的性质 存在的某个邻域 使对于任意成立 此外 对于任意 总有 这是因为 于是依据定理7 2 2可以断定迭代过程对于任意初值均收敛 证毕 18 解这里 可改写为各种不同的等价形式 其不动点为由此构造不同的迭代法 19 取 对上述4种迭代法 计算三步所得的结果如下表 20 注意 从计算结果看到迭代法 1 及 2 均不收敛 且它们均不满足定理3中的局部收敛条件 迭代法 3 和 4 均满足局部收敛条件 且迭代法 4 比 3 收敛快 因在迭代法 4 中 21 定义7 2 2设迭代过程收敛于方程的根 如果迭代误差当时成立下列渐近关系式 则称该迭代过程是阶收敛的 C为渐进误差常数 特别地 时称线性收敛 时称超线性收敛 时称平方收敛 22 23 24 证明先证充分性由于 据定理7 2 3立即可以断定迭代过程具有局部收敛性 再将在根处做泰勒展开 利用条件 2 8 则有 注意到 由上式得 因此对迭代误差 当时有 2 9 这表明迭代过程确实为阶收敛 证毕 25 26 上述定理说明 迭代过程的收敛速度依赖于迭代函数的选取 如果当时