大二下课程数值分析课件numerical lec

1、方程求根方程求根Solution of Equations 牛顿法 收敛速度 弦截法与抛物法2Newton 法法l 基本思想基本思想将非线性方程将非线性方程线性化线性化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) 000,xfx11,xfx yfxNewton法的几何意义法的几何意义()()()kkkyf xfxxx)( )(1kk

2、kkxfxfxx只要初值取得合适, 点列 xk 就会很快收敛于 x*。 Newton法切线法4Newton 法法算法算法 ：( Newton 法法 )(1) 任取迭代初始值任取迭代初始值 x0(2) 计算计算(3) 判断收敛性：如果判断收敛性：如果 或者或者 ， 则算法收敛，停止计算，输出近似解则算法收敛，停止计算，输出近似解 x1 0100()()f xxxfx(4) 令令 ， 返回第二步返回第二步01xx10 xx 1fx 5收敛性收敛性 （单根）（单根）1()()kkkkf xxxfx k = 0, 1, 2, . . . l 迭代函数迭代函数( )( )( )f xxxfx ( *)(

3、 *)0,( *)( *)fxxxfx牛顿法至少二阶牛顿法至少二阶局部收敛局部收敛12*( *)( *)lim(*)2!2( *)kkkxxxfxxxfx 举例举例例：例：用 Newton 法求解方程10 xxe 。 这里Newton迭代公式为11kxkkkkxexxxex75.m7举例举例例：例：用用 Newton 法求法求 f(x) = x2 C=0 的正根的正根112kkkCxxx 解：解： 2112kkkxCxCx 2112kkkxCxCx 211kkkkxCxCxCxC 2200kkkkxCxCqxCxC 2221kkkqxCCq 对任意对任意 x00，总有总有 |q|1，即牛顿法收

4、敛即牛顿法收敛8牛顿牛顿法法l 牛顿牛顿的的优点优点牛顿牛顿法是目前求解非线性方程法是目前求解非线性方程 (组组) 的主要方法的主要方法至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解时。时。l 牛顿牛顿的缺点的缺点l 对重根收敛速度较慢（线性收敛）对重根收敛速度较慢（线性收敛）l 对初值的选取很敏感，要求初值相当接近真解对初值的选取很敏感，要求初值相当接近真解先用其它算法获取一个近似解，然后使用牛顿法先用其它算法获取一个近似解，然后使用牛顿法l 需要求导数！需要求导数！下山法下山法例：求方程310 xx 在1.5x 附近

5、的一个根*x。 312131kkkkkxxxxx01.5x 1231.347831.325201.32472xxx00.6x 117.9x 更加偏离所求的根 Newton下山法下山法111 01kkkxxx 下山因子下山因子挑选下山因子，使单调条件成立！挑选下山因子，使单调条件成立！方法：逐步搜索1 单调条件成立单调条件成立单调条件不成立单调条件不成立:2 不变弦截法弦截法)()()()(111kkkkkkkxxxfxfxfxx注：牛顿法在计算1kx时只用到前一步的值kx，而弦截法要用到前面两步的结果1,kkxx，因此必须先给出两个初始值01,x x。 弦截法的几何意义弦截法的几何意义弦截法是

6、用弦1PPkk与 x 轴交点的横坐标 xk+1代替曲线 y = f (x)与 x 轴交点的横坐标 x*的近似值。 1kP13收敛性收敛性定理：定理：设设 x* 是是 f(x) 的零点的零点， f(x) 在在 x* 的某邻域的某邻域 U(x*, ) 内有二阶连续导数，且内有二阶连续导数，且 f(x) 0，若初值，若初值 x0，x1 U(x*, )，则当则当 充分小时，弦截法具有充分小时，弦截法具有 p 阶收敛性，其中阶收敛性，其中152p 2(10)pp弦截法例题弦截法例题例：例：用弦截法求解方程10 xxe 。 Newton 法：15抛物线法抛物线法l 基本思想：基本思想： 用二次曲线与用二次

7、曲线与 x 轴的交点作为轴的交点作为 x* 的近似值的近似值 抛物线法抛物线法16抛物线法抛物线法yxk-2xk-1xkxk+117抛物线法抛物线法l 计算过程计算过程二次曲线方程二次曲线方程 (三点三点 Newton 插值多项式插值多项式)21( )(),()kkkkpxf xf xxxx 121,()()kkkkkf xxxxxxxl 问题：问题：p2(x) 与与 x 轴有轴有两个交点两个交点，取哪个点？，取哪个点？解决方法：解决方法：取靠近取靠近 xk 的那个点的那个点!18抛物线法抛物线法21( )(),()kkkkpxf xf xxxx 121,()()kkkkkf xxxxxxx12122 ()4 () ,kkkkkkkf xxxf xf x