《现代数值分析课件第4章解非线性方程2章节》由会员分享，可在线阅读，更多相关《现代数值分析课件第4章解非线性方程2章节（34页珍藏版）》请在金锄头文库上搜索。
1、4.4 非线性方程的牛顿法 (Newton Method of Nonlinear Equations ),内容提纲（Outline),牛顿法及其几何意义 收敛性及其收敛速度 计算实例及其程序演示,取x0作为初始近似值，将 f (x)在x0做Taylor展开:,重复上述过程 ,作为第一次近似值,一、牛顿法及其几何意义,Newton 迭代公式,基本思路：将非线性方程 f (x)=0 线性化,牛顿法的几何意义,牛顿法也称为切线法, 迭代函数,（局部收敛性定理） 设 f (x)C2a, b，若 x* 为 f (x) 在a, b上的根,且 f (x*) 0，则存在 x* 的邻域 使得任取初始值 ，Ne
2、wton 法产生的序列 xk 收敛到 x*，且满足,至少平方收敛,二、牛顿法的收敛性与收敛速度,定理4.4.1,在x*的附近收敛,由Taylor 展开：,令k ，由 f (x*) 0，即可得结论。,证明：Newton法实际上是一种特殊的迭代法,迭代函数为：,设 x* 是 f 的 m 重根，则令： 且,Answer1: 有局部收敛性,Answer2: 线性收敛,结论：Newton法的收敛性依赖于x0 的选取。 局部收敛定理对初始值 x0 要求较高。,有根,根唯一,(全局收敛性定理): 设 f (x)C2a, b, 若 f (a) f (b) 0； 则由Newton法产生的序列 xk 单调地收敛到
3、 f (x)=0 在 a, b 的唯一根x*,且收敛速度至少是二阶的,保证Newton迭代函数将a , b映射于自身,定理4.4.2,将f (x* )在 xk 处作Taylor展开,对迭代公式两边取极限，得,说明数列 xk 有下界,故xk单调递减, 从而xk收敛.令,？,定理4.4.3,(全局收敛性定理): 设 f (x)C2a, b, 若,(1) f (a) f (b) 0； (2) 在整个a, b上 f (x) 0, f (x) 0 ； (3),则对任何 , Newton 迭代格式产生的序列 都收敛于f (x)=0 的根 x* .,注:定理的条件(3) 保证了从 x*两侧任取 x0 , 所
4、得到的数列 xk 均在a , b内.,三、计算实例及其程序演示,辅助工具: VC程序设计语言 Matlab数学软件,(1) 选定初值x0 ,计算f (x0) , f (x0),计算步骤,(2) 按公式 迭代 得新的近似值xk+1,(3) 对于给定的允许精度，如果 则终止迭代，取 ;否则k=k+1，再转 步骤(2)计算,允许精度,最大迭代次数,迭代信息,例1：用Newton法求方程 的根, 要求,迭代格式一：,迭代格式二：,取初值 x00.0,计算如下：,对迭代格式一: the iterative number is 27, the numerical solution is 0.4428527
5、06 对迭代格式二: the iterative number is 3, the numerical solution is 0.442854401,解：,例题2,求函数 的正实根 精度要求：,从图形中我们可以看出： 在x = 7和 x = 8 之间有一单根； 在x =1和x = 2 之间有一重根。,用Matlab画图，查看根的分布情形,初值x08.0 时,计算的是单根, The iterative number is 28,The numerical solution is 7.600001481 初值x01.0 ,计算的是重根, The iterative number is 1356,
6、The numerical solution is 1.198631981,小 结,(1) 当f (x)充分光滑且 x* 是f (x) =0的单根时，牛顿法在 x*的附近至少是平方收敛的。 (2) 当f (x)充分光滑且 x* 是f (x) =0的重根时，牛顿法在 x*的附近是线性收敛的。 (3) Newton法在区间a , b上的收敛性依赖于初值x0 的选取。 (4) Newton法的突出优点：收敛速度快 缺点：需计算函数的导数。,四 重根情形的Newton迭代法,重根情形的Newton迭代法是线性收敛的, 且有,由此易知若迭代函数为：,则Newton迭代格式 为平方收敛.,但 m 通常未知
7、,故常用修改方法：,令,若x*为f (x)的m重根, 则x*为u (x) = 0的单根,取,则得:,此格式二阶收敛,但要计算二阶导数.,4.5 弦截法与抛物线法,一、 单点弦截法,固定一点 P0( x0 , f (x0), 用差商 代替Newton公式中的 , 则得离散化的公式:,称为单点弦截法, 是一种简单迭代法.,几何意义: 依次用弦线代替曲线, 用线性函数的零点作为f (x)零点的近似值.,定理4.5.1,设 f (x)在a , b上满足：,(1) f (a) f (b) 0; (2) 在a , b上连续且不变号; (3) 选取初始值 , 使得 , 选 定a , b中的一个, 另一个为
8、.,则由迭代格式,所产生的序列 xk 单调地收敛于f (x)=0在a , b上的唯一根 x*, 且收敛速度是线性的.,二、 双点弦截法,若 用差商 代替Newton公式中的 , 则得公式:,称为双点弦截法.,注：双点弦截法与前面介绍的迭代法有明显区别, 前面所讲述 迭代法计算 xk+1时只用到 xk , 故称为单步迭代; 而双点弦截法 计算 xk+1时, 却同时用到前面两步的结果 xk-1和 xk , 故称为多步 迭代.,说明：单点弦截是双点弦截的特殊情况.,几何解释：,为 的斜率,直线方程为：,(1) f (x)在根 x*的某个领域内有连续的二阶导数, 且 (2) 任取 属于该领域; 则由双
9、点弦截公式所得序列 收敛于根 x*, 且收敛速度,(1) f (a) f (b) 0； (2) 在整个a, b上 f (x) 0, f (x) 0 ； (3),则 由双点弦截公式所得序列 收敛于 f (x)=0 的唯一根 x*.,例1：用单点弦截和双点弦截求方程 在2,3内的特殊情况.,解: (1) 单点弦截法,取 ， 单点弦截公式为：,(2) 双点弦截法,取 ， 双点弦截公式为：,三、弦截法与Aitken迭代法的联系,设,对于 在 和 两点处使用弦截法, 则得,即为Aitken迭代公式,四、抛物线法,若用过三点 和 的抛物线,与x 轴交点的横坐标作为 xk+1 , 则得抛物线法或Mlller
10、方法. 一条抛物线有两个实零点时, 取与 xk 较近的那个零点作为xk+1 .,4.5 非线性方程组的迭代算法,一、不动点迭代格式(简单迭代格式),取初值 代入计算即可.,二、Newton迭代格式,将非线性方程组线性化：,设 为 的第k 次近似解, 由Taylor公式得,用线性方程组,即,近似代替 , 用(*)的解作为 的第k+1次近似解, 则得Newton迭代格式：,这里,例：用牛顿法解方程组,取初始值(1,1,1), 计算如下,N x y z 0 1.0000000 1.0000000 1.00000000 2.1893260 1.5984751 1.3939006 1.8505896 1
11、.4442514 1.2782240 1.7801611 1.4244359 1.2392924 1.7776747 1.4239609 1.2374738 1.7776719 1.4239605 1.2374711 1.7776719 1.4239605 1.2374711,练习：,3. Newton 迭代法是如何推出的? 它若在单根附近收敛,是几阶收敛?在重根附近是几阶收敛？求方程重根时,能达到2阶收敛的改进 Newton 迭代公式是什么,用牛顿法求方程 在区间 1，2 内 的一个实根，要求,2. 导出求立方根 的迭代公式，并讨论其收敛性。,首先导出求根方程 ，再对 使用牛顿法 得迭代公式 ,用全局收敛性定理或局部收 敛性定理讨论其收敛性。,
