资源预览内容
第1页 / 共22页
第2页 / 共22页
第3页 / 共22页
第4页 / 共22页
第5页 / 共22页
第6页 / 共22页
第7页 / 共22页
第8页 / 共22页
第9页 / 共22页
第10页 / 共22页
亲,该文档总共22页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
7.4 -7.5 牛顿法及其推广/* Newton Method */一、牛顿迭代法的公式二、牛顿迭代法的改进与推广原理:将非线性方程线性化泰勒展开 /* Taylors expansion */取 x0 x* ,将 f(x*) 在 x0 做一阶泰勒展开: 在 x0 和 x*之间。将 (x* x0)2看成高阶小量,则有:一、牛顿迭代法的公式线性 /* linear */xyx* 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.5 0.57102 0.56716 0.56714k 0 1 2 3xk 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 */ 附近收敛快只要 f (x*) 0,则令 可得结论。注:注: Newtons Method 收敛性依赖于x0 的 选取。x*x0x0x0注 (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 之间找一个更好的点 ,使得 xkxk+1注:注: = 1 时就是Newtons Method 公式。当 = 1 代入效果不好时,将 减半计算。 。 弦截法 /* Secant Method */ Newtons Method 一步要计算 f 和 f ,相 当于2个函数值,比较费时。现用 f 的值近 似 f ,可少算一个函数值。x0x1切线 /* 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作为初始近似 根,令其弦截法迭代公式为迭代结果见下表k 0 1 2 3 4 xk 0.5 0.6 0.56754 0.56715 0.56714易见 故取初值 x0=0.5 ,牛顿迭代结果见下表k 0 1 2 3 xk 0.5 0.57102 0.56716 0.56714抛物线法本质:将非线性方程转化为一元二次方程的求解。有两种转化方法!作业:习题 7,12,13
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号