牛顿法抛物线法ppt课件.ppt
1第七章非线性方程(组)的数值解法计算方法 Newton 法法 弦截法、抛物线法弦截法、抛物线法2本讲内容本讲内容n Newton 法及其收敛性法及其收敛性n 牛顿下山法牛顿下山法n 弦截法与抛物线法弦截法与抛物线法3Newton 法法q 基本思想基本思想将非线性方程将非线性方程线性化线性化2( )( )()()()()2!kkkkff xf xfxxxxx l 设设 xk 是是 f (x)=0 的近似根，将的近似根，将 f(x) 在在 xk 处处 Taylor 展开展开令：令：( )0P x 1()()kkkkf xxxfx ( )P x()()()kkkf xfxxx 条件：条件： f(x) 04Newton 法法xyx*xkxk+15Newton 法法算法算法 ：( Newton 法法 )(1) 任取迭代初始值任取迭代初始值 x0(2) 对对 k = 1, 2, . , maxit，计算，计算判断收敛性，若收敛，则停止计算，输出近似解判断收敛性，若收敛，则停止计算，输出近似解1()()kkkkf xxxfx 6收敛性收敛性1()()kkkkf xxxfx k = 0, 1, 2, . . . l 迭代函数迭代函数( )( )( )f xxxfx ( *)( *)0,( *)2( *)fxxxfx牛顿法至少二阶牛顿法至少二阶局部收敛局部收敛12*( *)( *)lim(*)2!2( *)kkkxxxfxxxfx 7举例举例例：例：用用 Newton 法求法求 f(x) = xex 1=0 的解的解ex75.m8举例举例例：例：用用 Newton 法求法求 f(x) = x2 C=0 的正根的正根112kkkCxxx 解：解： 2112kkkxCxCx 2112kkkxCxCx 211kkkkxCxCxCxC 2200kkkkxCxCqxCxC 2221kkkqxCCq 对任意对任意 x00，总有总有 |q|1，即牛顿法收敛即牛顿法收敛9牛顿牛顿法法q 牛顿牛顿的的优点优点牛顿牛顿法是目前求解非线性方程法是目前求解非线性方程 (组组) 的主要方法的主要方法至少二阶局部收敛，收敛速度较快，特别是当迭代点至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解时。充分靠近精确解时。q 牛顿牛顿的缺点的缺点l 对重根收敛速度较慢（线性收敛）对重根收敛速度较慢（线性收敛）l 对初值的选取很敏感，要求初值相当接近真解对初值的选取很敏感，要求初值相当接近真解先用其它算法获取一个近似解，然后使用牛顿法先用其它算法获取一个近似解，然后使用牛顿法l 需要求导数！需要求导数！10简化的简化的Newton法法10()()kkkfxf xxx 线性收敛线性收敛简化的简化的 Newton 法法l 基本思想：基本思想：用用 f(x0) 替代所有的替代所有的 f(xk)11Newton下山法下山法1()()kkkkf xxxfx l 下山因子的取法：下山因子的取法： 从从 =1 开始，逐次减半，直到满足下降条件开始，逐次减半，直到满足下降条件l 基本思想：基本思想：要求每一步迭代满足下降条件要求每一步迭代满足下降条件 1kkfxfx l 具体做法：具体做法：加加下山因子下山因子 Newton下山法下山法保证全局收敛保证全局收敛12重根情形重根情形( )(*)( )mf xxxg x ( *)0g x 且且l 解法一解法一：直接使用：直接使用 Newton 法法( )( )( )f xxxfx 1( *)1xm 线性收敛线性收敛l 解法二解法二：改进的：改进的 Newton 法法( )( )( )f xxxmfx ( *)0 x 二阶收敛二阶收敛缺点：缺点：需要知道需要知道 m 的值的值重根情形重根情形13重根情形重根情形( )( )( )f xxfx 令令x* 是是 (x)=0 的的单重根单重根l 解法三解法三：用：用 Newton 法解法解 (x) = 02( )( ) ( )( )( ) ( )( ) ( )xf x fxxxxxfxf x fx 12() () ()() ()kkkkkkkf xfxxxfxf xfx 迭代格式：迭代格式：14举例举例例：例：求求 x4 - 4x2 4=0 的二重根的二重根 *2x 212( )4xxxx (1) 普通普通 Newton 法法ex76.m(2) 改进的改进的 Newton 法法(3) 用用 Newton 法解法解 (x) = 0222( )2xxxx 232(2)( )2x xxxx 15弦截法与抛物线法弦截法与抛物线法弦截法与抛物线法弦截法与抛物线法l 目的目的：避免计算：避免计算 Newton 法中的导数，且具有较法中的导数，且具有较高的收敛性（超线性收敛）高的收敛性（超线性收敛）l 弦截法（割线法）：弦截法（割线法）：用差商代替微商用差商代替微商l 抛物线法：抛物线法：用二次多项式近似用二次多项式近似 f(x)16弦截法弦截法l 弦截法迭代格式：弦截法迭代格式：111()()(),kkkkkkkf xf xfxf xxxx 111()()()kkkkkkkxxxxf xf xf x k = 1, 2, 3, . . .l 注：弦截法需要提供注：弦截法需要提供两个迭代初始值两个迭代初始值17收敛性收敛性定理：定理：设设 x* 是是 f(x) 的零点的零点， f(x) 在在 x* 的某邻域的某邻域 U(x, ) 内有二阶连续导数，且内有二阶连续导数，且 f(x) 0，若初值，若初值 x0，x1 U(x, )，则当则当 U(x, ) 充分小时，弦截法具有充分小时，弦截法具有 p 阶收敛性，其中阶收敛性，其中152p 2(10)pp18弦截法几何含义弦截法几何含义xyx*xk-1xkxk+119抛物线法抛物线法l 基本思想：基本思想： 用二次曲线与用二次曲线与 x 轴的交点作为轴的交点作为 x* 的近似值的近似值 抛物线法抛物线法20抛物线法抛物线法yxk-2xk-1xkxk+121抛物线法抛物线法l 计算过程计算过程二次曲线方程二次曲线方程 (三点三点 Newton 插值多项式插值多项式)21( )(),()kkkkpxf xf xxxx 121,()()kkkkkf xxxxxxxl 问题：问题：p2(x) 与与 x 轴有轴有两个交点两个交点，取哪个点？，取哪个点？解决方法：解决方法：取靠近取靠近 xk 的那个点的那个点!22抛物线法抛物线法21( )(),()kkkkpxf xf xxxx 121,()()kkkkkf xxxxxxx12122 ()4 () ,kkkkkkkf xxxf xf xxx 1121,()kkkkkkkf xxf xxxxx 取靠近取靠近 xk 的那个点的那个点23收敛性收敛性在一定条件下可以证明：抛物线法的收敛阶为在一定条件下可以证明：抛物线法的收敛阶为 1.840p 32(10)ppp24作业作业l 教材教材 238 页，习题页，习题 7l 教材教材 239 页，习题页，习题 9、15
