数值分析7-4,5(牛顿法,弦截法).ppt

7.4-7.5 牛顿法及其推广,/*Newton Method*/,一、牛顿迭代法的公式,二、牛顿迭代法的改进与推广,原理：将非线性方程线性化泰勒展开/*Taylors expansion*/,取 x0 x*，将 f(x*)在 x0 做一阶泰勒展开:,在 x0 和 x*之间。,将(x*x0)2看成高阶小量，则有：,一、牛顿迭代法的公式,线性/*linear*/,x0,只要 每一步迭代都有f(xk)0，而且，则 x*就是 f 的根。,牛顿迭代法的基本思想,将非线性方程 f(x)=0 的求根问题归结为计算一系列线性方程的求根问题。,牛顿迭代法的计算步骤,(1)给出初始近似根 x0 及精度；,(3)若，转向(4)，否则，转向(2);,(4)输出满足精度的根 x1，结束。,(2)计算,例,用牛顿迭代法求方程,在 x=0.5 附近的根。取,解,其牛顿迭代公式为,取初值 x0=0.5，迭代结果见下表,易见,故,k 0 1 2 3 xk 0.880000 0.884688 0.884675 0.884675,例 2 计算 的近似值,=10-6 x0=0.88,解：令 x=,问题转化为求f(x)=x2-0.78265=0 的正根,由牛顿迭代公式,xk+1=xk-(xk)/(xk)=xk/2+0.78265/2xk,迭代结果,满足了精度要求,故,0.884675,设 f C2a,b，若 x*为 f(x)在a,b上的根，且 f(x*)0，则存在 x*的邻域,Newtons Method产生的序列 xk 收敛到x*，且满足,使得任取初值,Newtons Method 有，只要 就有 p 2。重根是线性收敛的。,证明：Newtons Method 事实上是一种特殊的不动点迭代，其中,收敛,则,由泰勒展开：,在单根/*simple root*/附近收敛快,注：Newtons Method 收敛性依赖于x0 的选取。,x*,x0,x0,x0,注(1)牛顿法要求初值充分接近根以保证局部收敛性。,(2)牛顿迭代法的主要优点是收敛较快，是平方收敛的缺点是公式中需要求 f(x)的导数。若 f(x)比较复杂，则使用牛顿公式就大为不便。,重根/*multiple root*/加速收敛法：,问题1:若，Newtons Method 是否仍收敛？,设 x*是 f 的 n 重根，则：,因为 Newtons Method 事实上是一种特殊的不动点迭，其中,二、牛顿迭代法的改进与推广/*improvement and generalization*/,且,K1:有局部收敛性，但重数 n 越高，收敛越慢。,则,问题2:如何加速重根的收敛？,K2:将求 f 的重根转化为求另一函数的单根。,?,令,则 f 的重根=的单根。,下山法/*Descent Method*/Newtons Method 局部微调：,原理：若由 xk 得到的 xk+1 不能使|f|减小，则在 xk 和 xk+1 之间找一个更好的点，使得,注：=1 时就是Newtons Method 公式。当=1 代入效果不好时，将 减半计算。,弦截法/*Secant Method*/,Newtons Method 一步要计算 f 和 f，相当于2个函数值，比较费时。现用 f 的值近似 f，可少算一个函数值。,切线/*tangent line*/,割线/*secant line*/,切线斜率 割线斜率,需要 2 个初值 x0 和 x1。,收敛比Newtons Method 慢，且对初值要求同样高。,弦截法与牛顿法相比较,相同之处：都是线性化方法,不同之处：牛顿法在计算xk+1时只用到前一步的值xk，故这种方法称为单点迭代法。,而弦截法在求xk+1时要用到前两步的值xk和xk-1，因此这种方法称为多点迭代法。,有关弦截法的收敛速度,与牛顿法相比，弦截法的收敛速度也是比较快的。可以证明，弦截法具有超线性收敛速度，收敛阶为,即,例,用弦截法求方程,在x=0.5附近的根。取,解,取x0=0.5，x1=0.6作为初始近似根，令,其弦截法迭代公式为,迭代结果见下表,易见,故,取初值 x0=0.5，牛顿迭代结果见下表,抛物线法,本质：将非线性方程转化为一元二次方程的 求解。有两种转化方法！,作业：习题 7，12，13,