数值3.2.迭代加速、牛顿法及弦截法精讲.ppt

例3 用牛顿迭代法求函数 f(x)=(x-1)[sin(x-1)+3x]-x3+1=0 在0.95附近之根. 解 取x0 = 0.95 用牛顿迭代法求得的xk见右表. 可见xk收敛很慢. k xk ?k m 0 1 2 3 4 5 6 0.95 0.9744279 0.9870583 0.9934878 0.9967328 0.9983576 0.9991901 0.5090 0.5047 0.5007 0.5125 2.0369 2.0190 2.0028 2.0511 由重根数m=2, 用(4.13)式加速法，作 求得 x0=0.95, x1=0.9988559, x2=x3=1. 收敛速度大大加快于直接用牛顿迭代公式. 3.5 弦截法与抛物线法 　　用牛顿法求方程 f(x)=0的根，每步除计算 f(xk)外还要算 f?(xk)，当函数 f(x) 比较复杂时，计算 f?(x)往往比较困难，为此可以利用已求函数值 f(xk),f(xk-1),?来回避导数值 f?(xk)的计算. 这类方法是建立在插值原理基础上的，下面介绍弦截法与抛物线法. 3.5.1 弦截(割线)法 　　设 xk, xk-1是 f(x)=0的近似根，我们利用 f(xk), f(xk-1)构造一次插值多项式 p1(x)，并用 p1(x)=0 的根作为方程f(x)=0 的新的近似根 xk+1，由于 因此有 这样导出的迭代公式(5.2)可以看做牛顿公式 中的导数　　 用差商 取代的结果. 　　(5.2)式有明显的几何意义： 设曲线y=f(x)上横坐标为xk-1和xk的点分别为Pk-1和Pk, 则差商 表示弦 的斜率, 弦 的方程为 O x* xk+1 xk Pk xk-1 y x Pk-1 因此，按(5.2)式求得xk+1实际上是两点弦线 与x轴交点的横坐标(令y=0解出x即可).这种算法因此而形象地称为弦截(割线)法. 注：弦截法与切线法(牛顿法)都是线性化分法，但两者有本质的区别. 切线法在计算 xk+1 时只用到前一步的值 xk，而弦截法要用到前面两步的结果 xk-1, xk，因此使用这种方法必须先给出两个开始值 x0, x1. 　　定理6 假设f(x)在根x*的邻域内△: |x-x*|≤δ具有二阶连续导数，且对任意x?△有f?(x)≠0，所取的初值x0, x1?△，那么当邻域△充分小时，弦截法(5.2)将按阶 收敛到x*. 这里p是方程λ2-λ-1=0的正根. 　　定理证明可见P116. 　　因为(5.2)式用到前两点xk-1和xk的值，故此方法又称为双点割线法. 每步只用一个新点xk的值，此方法称为单点割线法. 　　如果把(5.2)式中的xk-1改为x0，即迭代公式为 　　例4 用牛顿迭代法和割线法求方程 f(x)=x4+2x2–x–3=0， 在区间(1, 1.5)内之根(误差为10-9). 解 取x0=1.5，用牛顿法, 可得x6=1.12412303030； 取x0=1.5, x1=1，用双点割线法，迭代6次得到同样的结果，而采用单点割线法，则迭代18次得x18=1.124123029. *3.5.2 抛物线法 　　设已知方程 f(x)=0的三个近似根 xk, xk-1, xk-2，我们以这三点为节点构造二次插值多项式 p2(x)，并适当选取 p2(x) 的一个零点 xk+1 作为新的近似根，这样确定的迭代过程称为抛物线法，亦称为密勒(Müller)法. 在几何图形上, 这种方法的基本思想是用抛物线y=p2(x)与 x 轴的交点 xk+1 作为所求根 x* 的近似位置. O x* xk+1 xk y=P2(x) xk-2 y x y=f(x) xk-1 　　抛物线法的几何意义见下面图形. 　　现在推导抛物线法的计算公式. 插值多项式 有两个零点 式中 　　因子在(5.3)式定出一个值xk+1，我们需要讨论根式前正负号的取舍问题. 　　在xk, xk-1, xk-2三个近似值中，自然假定xk更接近所求的根x*，这时，为了保证精度，我们选(5.3)式中接近xk的一个值作为新的近似根xk+1. 为此，只要取根式前的符号与ω的符号相同. 例5 用抛物线法求解方程f(x)=xex-1=0. 解 取x0=0.5, x1=0.6, x2=0.56532开始，计算得 f(x0)=-0.