2.09级7.3-1简单迭代法.pptVIP

* §3 简单迭代法 (不动点迭代法或 Picard迭代法) 3.1 简单迭代法公式 问题 f (x)实函数，求f (x)=0的近似解.设x*是其精确解. 例1 求解方程 x3-x-1=0在x=1.5附近的一个根. 解 将所给方程 x3-x-1=0 改写成 的形式，当x*是原方程的根时， 即有 假若初值x0 =1.5是其根, 代入后, 得 再将 x1=1.35721代入，求得 再将 x2=1.33086代入，求得 迭代结果如表3-1所示. 1. 迭代公式 迭代结果如表3-1所示. 1.5 1.35721 1.33086 1.32588 1.32494 1.32476 1.32473 1.32472 1.32472 0 1 2 3 4 5 6 7 8 表 3-1 仅取6位数字， x7 与x8 相同，认为 x7 是方程的根，即 问题 f(x)连续函数,求f(x)=0 (1)先将f(x)=0化为等价方程 初始近似 k+1次近似 (迭代公式) 若{xk}收敛于x*, 且g(x)连续, 则x*是 f (x)=0的根. 说明 由f(x)=0化成等价方程x =g(x)的化法有很多种. (1)如何选取迭代函数g(x)？ (3.3)式称为简单迭代法或单点迭代法或单步迭代法. g(x)称为迭 迭代法基本思想 出发,作序列 (2) 从某 讨论的问题 (2) g(x)满足什么条件，迭代序列收敛？收敛速度如何？ (3) 如何加速迭代序列的收敛速度？ 代函数. 连续函数 的近似解.设x*是其精确解. 首先考虑 由g(xk)求xk+1 , xk是否是g(x)定义域上的值? ？ 结论 考虑问题 由g(xk)求xk+1 , xk是否是g(x)定义域上的值? 定义4 简单迭代法(3.3)称为适定的； 法(3.3)称为收敛的. 当迭代(3.3)收敛时,极限点 又是g(x)的连续点,则 的解x*也称 的不动点. g(x)把定义域的每个x 映成了g(x)， 因此 保持有界, 若迭代序列 且全在g(x)定义域内,则 若进一步有 则简单迭代 迭代公式 注 适定是收敛必要条件，即不适定一定不收敛. 结论 说明两点 分别就下列四种情况说明几何意义 (1) 中 的产生. （2） 何时收敛,何时发散. 2. 几何意义 求x =g(x)的根 求 的根 迭代法收敛 可能不收敛 从点 的直线交y =x于点 出发,作平行于x轴 作平行于y 轴的直线交y =g(x)于点 过该点 即 依次进行下去得到 且 1. 压缩不动点定理 定理3 (压缩不动点定理或压缩映象定理) 若迭代函数g(x)满足 则 收敛程度 收敛速度 分析 结论10中x=g(x)有唯一根,因此用根的存在性定理, (3.5)实际是Lip.z.连续条件. 验后误差估计式 验前误差估计式 3.2 迭代法收敛性 证明 若等号成立, 则表示a是根或者b是根, [a,b]上已有根存在 , 对于 一般情况 , 由根的存在定理，h(x)=0在(a,b)上至少存在一个根 x*, 即x = g (x)在 [a,b]上至少存在一个根 x*, 从而 从而 下证唯一性， 设y*为x=g(x)在[a,b]上另一根,则 及条件(1)知 迭代适定，另外 （导数的定义） ＃ 注 (1) 从定理结论30知,L越小收敛越快, L叫做渐进收敛因子. 从验后误差估计式知只要相邻两次xk-1 与xk迭代值的偏差充分小 ， 就能保证迭代值xk足够准确,因而可用| xk –xk-1 |来控制迭代过程的 结束 . 取xk作为根x*的近似值 . 但当 时，该方法不可靠. (3.5)式的条件较难验证，常采用导数来代替. 即有推论 推论1 定理1 中(3.5)可用下式替代 证明 只证 因 ＃ 思考 不成立时结论是否成立 ？ 不一定 该推论是充分条件但不是必要条件. 若(3.5)不成立时,需要 判断(3.5)或缩小含根区间进行讨论 . 注 (2) 该定理是充分条件但不是必要条件. 注 定理4 （局部收敛定理） 有 则 由 产生的序列 收敛于 且有误差估计 证明 2.局部收敛定理 ＃ 说明 定理中的条件是充分但非必要条件.见定理1的注(2). 例如 上不满足推论1的条件，但是实际上 x=0是解， 只要x0取在0附近, 即 把（－1，1）缩小可使 成立，从而该迭代收敛. 优点 算法的逻辑结构简单 . 推论2 若 在不动点 处可微，而且 则存在 当 时，由 产生的序列 收敛于 且 证明 任取 由 知存在 ，成立 即 由定理2得证. ＃ (3.7)式的条件较难验证,常采用导数来代替.即有推论 例2 求方程 x3-2x