数值分析第二章2.ppt

定理：设 x* 是 f(x) 的零点， f(x) 在 x* 的某邻域 U(x,?) 内有二阶连续导数，且 f’(x)?0，若初值 x0，x1 ?U(x,?)，则当 U(x,?) 充分小时，弦截法具有 p 阶收敛性，其中 注：弦截法具有超线性收敛性。 弦截法几何含义 x y x* xk-1 xk xk+1 * * * * * * * * 例 只用四则运算不用开方求方程x2-3=0的根 解 k xk 迭代法(1) 迭代法(2) 迭代法(3) 迭代法(4) 0 1 2 3 ? x0 x1 x2 x3 ? 2 3 9 87 ? 2 1.5 2 1.5 ? 2 1.75 1.73475 1.732631 ? 2 1.75 1.732143 1.732051 ? (1)和(2)发散， (3)和(4)收敛. 例 设 试讨论a的取值范围 使迭代公式(2.2)局部收敛到 解 因为 所以 由定理2可知只需 即 所以当 时,迭代公式收敛. 5 迭代收敛的阶 则称该迭代为p 阶收敛. (C为常数) (1) 当p =1时称为线性收敛，此时0C 1； (2) 当p =2 时称为二次收敛，或平方收敛； (3) 当p 1和p =1且C=0时称为超线性收敛. 定义 设迭代 收敛到 的不动点x*. 记ek = xk ? x*，若 例: (1) 二分法线性收敛; (2)不动点迭代中，若 则线性收敛 解: (2) 不动点迭代中第k+1步的误差为： 则 定理3 设迭代 若 在x*的某 邻域内连续并满足 即该迭代法是p阶收敛的。 证明： 根据泰勒展开有 6 迭代加速 若 则迭代公式(2.2)只是线性收敛。 迭代加速方法可对线性收敛的简单迭代法起到加速作用。 取初始点x0,令 那么 由此得加速迭代公式 此加速法的优点： 迭代速度快； 此加速法的缺点： 迭代公式中有待定的L, 使用不方便。 令 得到 Steffensen迭代加速法 由此得Steffensen加速法 Steffensen加速法是平方收敛的. 注：果第k步发生zk-2yk+xk=0, 就终止计算, 取x*?xk 。 分别用简单迭代法和Steffensen加速算法 例 求方程 在 附近的根。 解： 简单迭代法迭代公式 Steffensen迭代公式： k 简单迭代法 k Steffensen迭代法 xk |xk-xk-1| xk |xk-xk-1| 0 1 2 3 4 1.57080 1.6 1.57109 1.59971 1.57138 0.0292 0.02891 0.02862 0.02833 0 1 2 1.5707963 11 00取x0= ? /2, 计算结果如下: Newton迭代法是求方程根的重要方法之一,其最大优点是在方程的单根附近具有平方收敛,而且Newton迭代法还可用来求方程的重根、复根及非线性方程组。 三、 Newton法 1 Newton法基本思想 设xk是f (x)=0的近似根,将f (x)在xk一阶Taylor 展开: (?在xk和x之间) 当 f ′ (x) ? 0时, ,于是 即为Newton迭代公式. x y x* xk xk+1 Newton法的几何意义 Newton法的本质就是不断用切线来近似曲线，因此Newton法也成为切线法. 2 Newton法的算法 (1) 取初始点x0,最大迭代次数N和精度要求ε 置k=0; (2) 计算 (3) 若 则停止计算; (4) 若k=N则停止计算;否则置k=k+1,转(2). Newton 法可以看作下面的不动点迭代： 其中 ?’(x*) = 0 (若f(x*)=0,f′(x*)≠0，即x*是单根） Newton 法至少二阶局部收敛 3 Newton法收敛性 定理4 设f(x)在其零点x*的某个邻域内二阶连续可导且f(x) ? 0，则存在x*的某个? 邻域N(x*) =[x*-? , x* +? ], 使得对? x0? N(x*)，Newton法产生的序列以不低于二阶的收敛速度收