数值分析第7章非线性方程的数值解法46;ppt课件

1、 在科学研究的数学问题中更多的是非线性问题，在科学研究的数学问题中更多的是非线性问题，它们又常常归结为非线性方程或非线性方程组的它们又常常归结为非线性方程或非线性方程组的求解问题。求解问题。第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法/ /* * Numerical Solutions of Numerical Solutions of Nonlinear EquationsNonlinear Equations* */ /7.1 7.1 方程求根与二分法方程求根与二分法 7.2 7.2 不动点迭代法及其收敛性不动点迭代法及其收敛性 7.3 7.3 迭代收敛的加速方

2、法迭代收敛的加速方法 7.4 7.4 牛顿法牛顿法 7.5 7.5 弦截法与抛物线法弦截法与抛物线法 7.6 7.6 求根问题的敏感性与多项式的零点求根问题的敏感性与多项式的零点7.7 7.7 非线性方程组的数值解法非线性方程组的数值解法7.1 方程求根与二分法方程求根与二分法 7.1.1 引言引言0)( xf（1.1）单变量非线性方程的一般形式单变量非线性方程的一般形式 其中其中 也可以是无穷区间也可以是无穷区间. . ,)(,RbabaCxfxf(x)是高次多项式函数或超越函数是高次多项式函数或超越函数),0()(01110 aaxaxaxaxfnnnn（1.2） 如果函数如果函数 是多项

3、式函数，即是多项式函数，即)(xf其中其中 为实数，则称方程为实数，则称方程(1.1)(1.1)为为 次代数方程次代数方程. . ), 1 ,0(,00niaain超越函数超越函数 不能表示为多项式的函数不能表示为多项式的函数如如 (x)=3x5-2x4+8x2-7x+1 (x)=e2x+1-xln(sinx)-2高次代数方程高次代数方程超越方程超越方程 假设假设 是是 的的 重零点，且重零点，且 充分光滑，那么充分光滑，那么*x)(xfm)(xg, 0*)(*)(*)()1( xfxfxfm. 0*)()( xfm 次方程在复数域有且只有次方程在复数域有且只有 个根含重根，个根含重根， 重根

4、为重根为 个根）个根）. . mmnn超越方程超越方程,010sine10/xx它在整个它在整个 轴上有无穷多个解，假设轴上有无穷多个解，假设 取值范围不同，解也取值范围不同，解也不同，因此讨论非线性方程不同，因此讨论非线性方程(1.1)(1.1)的求解必须强调的求解必须强调 的定的定义域，即义域，即 的求解区间的求解区间xxxx.,ba 如果实数如果实数 满足满足 ，则称，则称 是方程是方程(1.1)(1.1)的的根，或称根，或称 是是 的零点的零点. .*x)(xf0*)(xf*x*x假设假设 可分解为可分解为 )(xf),(*)()(xgxxxfm其中其中 为正整数，且为正整数，且 则称

5、则称 为方程为方程(1.1)(1.1)的的 重根，或重根，或 为为 的的 重零点，重零点， 时为单根时为单根. .m.0*)(xg1m*xm*x)(xfm结论结论通常方程根的数值解法大致分为三个步骤进行：通常方程根的数值解法大致分为三个步骤进行：非线性问题一般不存在直接的求解公式，要使用迭代法非线性问题一般不存在直接的求解公式，要使用迭代法. .本章将介绍常用的求解非线性方程的近似根的几种数值解法本章将介绍常用的求解非线性方程的近似根的几种数值解法 如何求方程如何求方程 的有根区间？的有根区间？0)( xf 设设 f(x)Ca, b, 且且 f(a) f(b)0, 存在存在(a,b) ，使，使

6、 f()=0. 根的存在性定理根的存在性定理闭区间上连续函数的介值定理闭区间上连续函数的介值定理有根区间有根区间如果如果f(x)在在a,b上还是单调递增或递减的，则上还是单调递增或递减的，则f(x)=0仅有一仅有一个实根。个实根。(1)(1)描图法描图法 画出画出y=f(x)y=f(x)的略图，从而看出曲线与的略图，从而看出曲线与x x轴交点的大致位置轴交点的大致位置。也可将。也可将f(x)=0f(x)=0等价变形为等价变形为g1(x)=g2(x)g1(x)=g2(x)的形式，的形式，y=g1(x)y=g1(x)与与y=g2(x)y=g2(x)两曲线交点的横坐标所在的子区间即为含根区间。两曲线

7、交点的横坐标所在的子区间即为含根区间。例例1 1 求方程求方程3x-1-cosx=03x-1-cosx=0的有根区间。的有根区间。方程等价变形为方程等价变形为3x-1=cosx，y=3x-1与与y=cosx的图像只有一个交点位于的图像只有一个交点位于0.5，1内。内。对对 的根进行搜索计算，的根进行搜索计算，0)(xf 例例2 2 求方程求方程 的有根的有根区间区间. .077.418 .381 .11)(23xxxxf的符号计算结果表)(6543210 1-7xfx由此可知方程的有根区间为由此可知方程的有根区间为 .6,5,4,3,2,1(2)逐步搜索法逐步搜索法 先确定方程先确定方程f(x

8、)=0的所有实根所在的区间为的所有实根所在的区间为a,b,从从x0=a 动身动身,以步长以步长 h=(b-a)/n 其中其中n是正整数，在是正整数，在a,b内取定节点：内取定节点： xi=x0ih (i=0,1,2，n) 计算计算f(xi)的值的值,依据函数值异号及实根的个数确定有根区依据函数值异号及实根的个数确定有根区间间,通过调整步长，总可找到所有有根区间。通过调整步长，总可找到所有有根区间。 解解 7.1.2 二分法二分法求解方程求解方程f(x)= 0的近似根的一种常用的简单方法。的近似根的一种常用的简单方法。 原理原理基本思想基本思想设函数设函数f(x)在闭区间在闭区间a,b上连续上连

9、续,且且f(a)f(b)0,那么那么 f(x)= 0在在(a,b)内必有实根区间。内必有实根区间。逐步将区间二等分逐步将区间二等分, 通过判断区间端点通过判断区间端点f(x)的符号的符号, 逐步将逐步将有根区间缩小有根区间缩小, 直至有根区间足够地小直至有根区间足够地小, 便可求出满足精便可求出满足精度要求的近似根。度要求的近似根。具体做法具体做法)(xfy aboxy x 20bax 1b 1112xba 2a 3a 1a2222xba 2b3b11,a b22,a b33,a b以此类推以此类推由二分法的过程知由二分法的过程知,2211 kkbabababa, 0)().(*kkkkbax

10、bfaf (1)kkkkkababab2211 (2)(3)2kkkbax 作为根的近似作为根的近似可得一个近似根的序列可得一个近似根的序列 ,210kxxxx2/ )(*kkkabxx（1.3）,2/ )(1kab且且(4)只要二分足够多次即只要二分足够多次即 充分大），便有充分大），便有 k,*kxx这里这里 为预定的精度为预定的精度. .12lnln)ln( abk,*kxx要使要使解：解：211 510 ,.;ab，21 5 11012ln( .)lnln 4.64例例3 用二分法求方程用二分法求方程 在区间在区间 上的根，误差上的根，误差限为限为 ，问至少需对分多少次？，问至少需对分

11、多少次？310 xx 1 1 5 , . 210 12lnln)ln( abk5 k二分法的算法二分法的算法 步骤步骤1 1 准备准备 计算计算 在有根区间在有根区间 端点处的值端点处的值 )(xf).(),(bfaf,ba 步骤步骤2 2 二分二分 计算计算 在区间中点在区间中点 处的值处的值 )(xf2ba ).2(baf 步骤步骤3 3 判断判断 假设假设 ，那么，那么 即是即是根，根，计算过程结束，否则检验计算过程结束，否则检验. . 0)2( baf2ba 假设假设 ，则以，则以 替代替代 ，否则以，否则以0)()2(afbaf2ba b替代替代 . . 2ba a此时中点此时中点

12、即为所求近似根即为所求近似根. . 2ba 误差误差 ， 反复执行步骤反复执行步骤2 2和步骤和步骤3 3，直到区间，直到区间 长度小于允许长度小于允许,ba y n 开 始 输 入 a , b, (a+b)/2 x f(a) f(x )0 ? xb x a |b-a|0 输 出 x 结 束 y n 例例4 求方程求方程 01)(3xxxf在区间在区间 内的一个实根，要求准确到小数点后第内的一个实根，要求准确到小数点后第2 2位位. .5.1 ,0.1欲使欲使5.1,0.1ba0)(,0)(bfaf25. 10 x只需只需 ，即只要二分，即只要二分6 6次，便能达到预定的精度次，便能达到预定的

13、精度. . 6k2/ )(*kkkabxx12/ )(kab,005.021211k 解解 0)(0 xf5 .1,25.1101bbxa.,11ba得到新的有根区间得到新的有根区间 3242. 13203. 063203. 13281. 153281. 13438. 143438. 13125. 133125. 1375. 12375. 125. 1125. 15 . 10 . 10)(符符号号kkkkxfxbak二分法对多个零点的情况，只能算出其中一个零点。二分法对多个零点的情况，只能算出其中一个零点。即便即便 f(x)在在a, b上有零点，也未必有上有零点，也未必有 f(a) f(b)0

14、。 不管有根区间多大不管有根区间多大,总能求出满足精度要求的根总能求出满足精度要求的根,且对函数且对函数f(x)的要求不高的要求不高,只要连续即可只要连续即可,计算亦简单。计算亦简单。优点优点缺点缺点7.2 不动点迭代法及其收敛性不动点迭代法及其收敛性 7.2.1 不动点与不动点迭代法不动点与不动点迭代法/*Fixed-Point Iteration*/ ).(xx （2.1）假设假设 满足满足 ，那么，那么 ；反之亦然，称；反之亦然，称为函数为函数 的一个不动点的一个不动点. . *x0*)(xf*)(*xx*x)(x 求求 的零点就等价于求的零点就等价于求 的不动点的不动点. .)(xf)

15、(x0)( xf基本思想基本思想)., 1 ,0()(1kxxkk（2.2） 称为迭代函数称为迭代函数. .)(x.*limxxkk得到的序列得到的序列 有极限有极限 kx,0bax 如果对任何如果对任何 ，由迭代，由迭代)., 1 , 0()(1 kxxkk 不动点迭代法不动点迭代法则称迭代法收敛，且则称迭代法收敛，且 为为 的不动点，的不动点，*)(*xx)(x不动点迭代是一种逐次逼近的方法不动点迭代是一种逐次逼近的方法, ,用某个固定公式反复校用某个固定公式反复校正根的近似值正根的近似值, ,使之逐步精确化，最后得到满足精度要求的使之逐步精确化，最后得到满足精度要求的结果。结果。对预先给

16、定的精度要求对预先给定的精度要求，只要某个，只要某个k满足满足 1kkxx即可结束计算并取即可结束计算并取 kxx *迭代终止的判定迭代终止的判定几何意义几何意义 交点的横坐标交点的横坐标 *x )()(xyxyxx y=x2x0 x1x)(xy xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1 例例5 求方程求方程 01)(3xxxf（2.3）在在 附近的根附近的根 5.10 x.*x设将方程改写成设将方程改写成. 13xx建立迭代公式建立迭代公

17、式 解解32494.1432472.1832588.1332472.1733086.1232473.1635721.1132476.155.1037kkxkxk表)., 2 , 1 , 0(131 kxxkk各步迭代的结果如下表各步迭代的结果如下表 即为所求的根即为所求的根. .7x如果仅取如果仅取6 6位数字，位数字，结果结果 与与 完全相同，完全相同，7x8x. 131kkxx.39.12,375. 221xx发散发散说明：说明：迭代函数不唯一，迭代函数不唯一，迭代点列可能收敛，也可迭代点列可能收敛，也可能发散，迭代收敛与否不仅与迭代函数有关，还与初能发散，迭代收敛与否不仅与迭代函数有关，

18、还与初始点有关。始点有关。 7.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性 不动点的存在唯一性定理不动点的存在唯一性定理 定理定理1 设设 满足以下两个条件：满足以下两个条件：,)(baCx 1. 1. 对任意对任意 有有 ,bax bxa)( 2. 2. 存在正常数存在正常数 ，使对任意，使对任意 都有都有 1L,bayx.)()(yxLyx（2.4）那么那么 在在 上存在唯一的不动点上存在唯一的不动点 )( x,ba.*x证明证明存在性存在性 假设假设 或或 ，则不动点为，则不动点为 或或 ，aa)(bb)(ab 因因 ，bxa)(以下设以下设 及及 ，aa)(b

19、b)(定义函数定义函数.)()(xxxf显然显然 ，,)(baCxf,0)()(aaaf且且,0)()(bbbf由零点定理知存在由零点定理知存在 , , ),(*bax*),(*xx使使 , ,0*)(xf即即唯一性唯一性 设设 都是都是 的不动点，的不动点，,21baxx)( x)()(2121xxxx故故 的不动点是唯一的的不动点是唯一的. . )( x则由则由.2121xxxxL.)()(yxLyx即为即为 的不动点的不动点. .)( x*x得得矛盾矛盾. .1*01xxLLxxkk （2.5） 定理定理2 设设 满足定理满足定理1中的两个条件，那么中的两个条件，那么对任意对任意 ，由，

20、由,)(baCx ,0baxkx)( x*x得到的迭代得到的迭代)., 1 , 0()(1 kxxkk 序列序列 收敛到收敛到 的不动点的不动点 ，并有误差估计，并有误差估计 L L 越越 收敛越快收敛越快小小事前估计：选取事前估计：选取k k，预先估计迭代次数。，预先估计迭代次数。证明证明 设设 是是 在在 上的唯一不动点，上的唯一不动点，,ba,*bax)( x,baxk由条件，可知由条件，可知*)()(*1xxxxkk因因 ，故当，故当 时序列时序列 收敛到收敛到 . .10 Lkkx*x*1xxLk.*0 xxLk .)()(yxLyx又由又由误差估计误差估计收敛性收敛性由由.)()(

21、yxLyx)()(11kkkkxxxx（2.6）.1kkxxL得得反复递推得反复递推得 1*1* kkkkkxxxxLxxLxx)(1* kkkxxxxL1*)1( kkkxxLxxL1*1 kkkxxLLxx.1*01xxLLxxkk 迭代过程的控制迭代过程的控制只要相邻两次计算结果的偏差只要相邻两次计算结果的偏差 足够小，即可保证足够小，即可保证 1 kkxx近似值近似值 具有足够精度具有足够精度. .kx011*xxLLxxkk 事后估计事后估计事前估计：选取事前估计：选取k k，预先估计迭代次数。，预先估计迭代次数。1*1 kkkxxLLxx注：注： 定理定理1 1、2 2的条件的条件

22、(2)(2)可替换为可替换为,1)(Lx（2.7）假如假如 且对任意且对任意 有有 ,bax ,)(1baCx 则由中值定理可知对则由中值定理可知对 有有 ,bayx)()()(yxyx).,(,bayxL例例5 53/2)1(31)(xx14131)(3/1 x又因又因 ，23)(2133x 而当而当 时，时， ，在区间，在区间 中中 不满足定理条件不满足定理条件. .1)(3 xx23)(xx2, 11)( x31)(xx当当 时，时，2, 1在区间在区间 中，中，所以迭代法是收敛的所以迭代法是收敛的. . 7.2.3 局部收敛性与收敛阶局部收敛性与收敛阶 迭代序列迭代序列 在区间在区间

23、上的收敛性，上的收敛性，kx,ba全局收敛性全局收敛性 定义定义1 设设 有不动点有不动点 ,如果存在如果存在 的某个邻域的某个邻域 对任意对任意 ，迭代，迭代 产生的序列产生的序列 且收敛到且收敛到 ，则称迭代法局部收敛，则称迭代法局部收敛.)( x*x,*: xxRRx 0,Rxk*x*x)., 1 , 0()(1 kxxkk 定理定理3 设设 为为 的不动点，的不动点， 在在 的某个邻的某个邻域连续，且域连续，且 ，则迭代法，则迭代法 局部收敛局部收敛.*x)(x)( x*x1*)( x)., 1 , 0()(1 kxxkk 局部收敛性局部收敛性证明证明 由连续函数的性质，存在由连续函数

24、的性质，存在 的某个邻域的某个邻域 *x,*: xxR.1)(LxRx 使对于任意使对于任意 成立成立*)()(*)(xxxx所以，所以，对于任意对于任意 ，Rx 总有总有 。Rx )(因为因为 *xxL.*xx 迭代序列的收敛速度迭代序列的收敛速度 例例6 用不同方法求方程用不同方法求方程 的根的根 032x.3* x 解解 ,3)1(21kkkxxx,12)(xx.1132)3(*)(x,3)(2xxx,3)2(1kkxx,3)(xx ,3)(2xx.1*)( x),3(41)3(21kkkxxx),3(41)(2xxx构造不同的迭代法构造不同的迭代法,211)(xx.1134.0231*

25、)( x),3(21)4(1kkkxxx),3(21)(xxx),31(21)(2xx.0)3(*)(x03)(2 xxf),(xx 取取 ，对上述，对上述4 4种迭代法，计算三步所得的结果如下表种迭代法，计算三步所得的结果如下表. . 20 x732051.1732361.15.1873732143.173475.129275.175.15.13122220473210 xxxxxkk(4)(3)(2)(1)迭迭代代法法迭迭代代法法迭迭代代法法迭迭代代法法表表计算结果 从计算结果看到迭代法从计算结果看到迭代法1 1及及2 2均不收敛，且它均不收敛，且它们均不满足定理们均不满足定理3 3中的局

26、部收敛条件中的局部收敛条件. . 注意注意 . .7320508.13 0*)( x 迭代法迭代法3 3和和4 4均满足局部收敛条件，且迭代法均满足局部收敛条件，且迭代法4 4比比3 3收敛快，因在迭代法收敛快，因在迭代法4 4中中 . . 求方程求方程xex-1=0在在0.5附近的根附近的根,精度要求精度要求=10-3。可以验证方程可以验证方程xex-1=0在区间在区间0.5,0.61内仅有一个根。内仅有一个根。例例7 改写方程为改写方程为x=e-x ,建立迭代格式建立迭代格式, 2 , 1 , 0,1 kexkxk 由于由于 (x)=e-x ,在在0.5,0.61上有上有|(x)| e-0

27、.5 0.6 1，且且 (x) 0.5,0.61，所以迭代法收敛。，所以迭代法收敛。取取x0=0.5,得得kxk|xk-xk-1|kxk|xk-xk-1|0123450.50.606530.545240.579700.560060.571170.106530.061290.034460.019640.011116789100.564860.568440.566410.567560.566910.006310.003580.002030.001150.00065 解解 所以所以,取近似根取近似根x10=0.56691满足精度要求。满足精度要求。 如果精度要求为如果精度要求为=10-5, 则由则由

28、LxxLkln)1(ln01 95.196 . 0ln10653. 0104 . 0ln5可知可知,需要迭代需要迭代20次。次。 实际上实际上,方程在区间方程在区间0.55,0.6上有唯一根，而在区间上有唯一根，而在区间0.55,0.6上有上有|(x)|e-0.550.581)阶收敛的方法，改用阶收敛的方法，改用Stefensen迭代方法优点不多。迭代方法优点不多。7.4 牛顿法牛顿法 7.4.1 牛顿法及其收敛性牛顿法及其收敛性 设已知方程设已知方程 有近似根有近似根 （假定（假定 ) )，kx0)(xf0)(kxf将函数将函数 在点在点 展开，有展开，有 )(xfkx),)()()(kkk

29、xxxfxfxf于是方程于是方程 可近似地表示为可近似地表示为 0)(xf.0)()(kkkxxxfxf（4.1）这是个线性方程，记其根为这是个线性方程，记其根为 ，1kx那么那么 的计算公式为的计算公式为 1kx),1 ,0()()(1kxfxfxxkkkk（4.2）牛顿法牛顿法几何意义几何意义切线法切线法收敛性收敛性),1 ,0()()(1kxfxfxxkkkk（4.2）)*)()(*)(0000 xxxfxfxf )()(*000 xfxfxx xyx*x0)()(1kkkkxfxfxx 只要只要 f C1，每一步迭代都有，每一步迭代都有f ( xk ) 0， 而而 ，那么那么 x*就是

30、就是 f 的根。的根。*limxxkk ,)()()(xfxfxx 2)()()()(xfxfxfx 迭代函数迭代函数假定假定 是是 的一个单根，即的一个单根，即 ，则由上式知则由上式知)( xf*x0*)(,0*)(xfxf0*)( x*)(*)(*)(xfxfx 局部平方收敛局部平方收敛.*)(2*)(*)(*lim21xfxfxxxxkkk （4.3）x*x0 x0 x06.1.4 牛顿迭代法牛顿迭代法例例10 用牛顿法解方程用牛顿法解方程 .01e xx（4.4）解解,1e1kxkkkxxxxk取迭代初值取迭代初值 ，迭代结果列于表，迭代结果列于表7-77-7中中. . 5.00 x

31、所给方程所给方程4.44.4实际上是方程实际上是方程 的等价形式的等价形式. . xx e牛顿公式为牛顿公式为 56714.0356716.0257102.015.00计算结果77kxk表若用不动点迭代到同一精度若用不动点迭代到同一精度 要迭代要迭代1717次次. .可见牛顿法的收敛速度是很快的可见牛顿法的收敛速度是很快的. .牛顿法的计算步骤：牛顿法的计算步骤： 步骤步骤1 1 准备准备 选定初始近似值选定初始近似值 ，计算，计算 0 x).(00 xff),(00 xff步骤步骤2 2 迭代迭代 按公式按公式 0001/ ffxx迭代一次，迭代一次，得新的近似值得新的近似值 ，1x).()

32、,(1111xffxff计算计算 1x步骤步骤3 3 控制控制 假如假如 满足满足 或或 ，则终止迭代，则终止迭代，以以 作为所求的根；否则转步骤作为所求的根；否则转步骤4. 4. 1x121f 此处此处 是允许误差，而是允许误差，而 21, ，当当；当当时时CxxxxCxxx1101101 其中其中 是取绝对误差或相对误差的控制常数，是取绝对误差或相对误差的控制常数，C1C一般可取一般可取 步骤步骤4 4 修改修改 如果迭代次数达到预先指定的次数如果迭代次数达到预先指定的次数 ，N或者或者 ，则方法失败；，则方法失败；01f 否则以否则以 替代替代 转步骤转步骤2 2继续迭代继续迭代. .)

33、,(111ffx),(000ffx 7.4.2 牛顿法应用举例牛顿法应用举例 对于给定的正数对于给定的正数 ，应用牛顿法解二次方程，应用牛顿法解二次方程 C,02 Cx可导出求开方值可导出求开方值 的计算程序的计算程序 C).(211kkkxCxx（4.5）这个迭代公式对于任意初值这个迭代公式对于任意初值 都是收敛的都是收敛的. . 00 x配方配方;)(2121CxxCxkkk .)(2121CxxCxkkk 两式相除两式相除211 CxCxCxCxkkkk反复递推反复递推.200kCxCxCxCxkk （4.6）CxCxq 001 qkkqqCCxk2212 Cxkk lim723805.

34、104723805.103723837.102750000.101100计算结果87kxk表取初值取初值 ，对，对 按按(4.5)(4.5)式迭代式迭代3 3次便得次便得到精度为到精度为 的结果见表的结果见表7-8).7-8).100 x115C610 例例11 求求 . 115解解).(211kkkxCxx 由于公式由于公式4.54.5对任意初值对任意初值 均收敛，并且收敛的均收敛，并且收敛的速度很快，因此可取确定的初值如速度很快，因此可取确定的初值如 编成通用程序编成通用程序. . 00 x10 x 7.4.3 简化牛顿法与牛顿下山法简化牛顿法与牛顿下山法 牛顿法的改进牛顿法的改进每步迭代

35、要计算每步迭代要计算 及及 . .)(kxf)(kxf 牛顿法的变形牛顿法的变形 (1) (1) 简化牛顿法简化牛顿法- -平行弦法平行弦法.,1 ,00)(1kCxCfxxkkk（4.7）迭代函数迭代函数 ).()(xCfxx初始近似初始近似 只在根只在根 附近才能保证收敛附近才能保证收敛. .0 x*x优点优点缺点缺点收敛快收敛快 若在根若在根 附近成立附近成立 ，*x1)(1)(xfCx, 2)(0 xfC该迭代法局部收敛该迭代法局部收敛. .取取)(10 xfC)()(01xfxfxxkkk-简化牛顿法简化牛顿法用平行弦与用平行弦与 轴交点作为轴交点作为 的近似的近似. . x*x图图

36、7-57-5oxyy=(x)xx0 x1x2x3几何意义几何意义(2) (2) 牛顿下山法牛顿下山法牛顿法求方程牛顿法求方程 .013 xx在在 附近的一个根附近的一个根 . . 5.1x*x 设取迭代初值设取迭代初值 ，用牛顿法公式，用牛顿法公式 5.10 x131231kkkkkxxxxx（4.9）计算计算.32472.1,32520.1,34783.1321xxx迭代迭代3 3次得到的结果次得到的结果 有有6 6位有效数字位有效数字. . 3x6.00 x.9.171x这个结果反而比这个结果反而比 更偏离了所求的根更偏离了所求的根 . . 6.00 x32472.1* x附加要求附加要求

37、.)()(1kkxfxf（4.10）满足这项要求的算法称下山法满足这项要求的算法称下山法. . 保证函数值稳定下降保证函数值稳定下降131231kkkkkxxxxx牛顿法的计算结果牛顿法的计算结果 )()(1kkkkxfxfxx前一步的近似值前一步的近似值kx,)1(11kkkxxx（4.11）其中其中 称为下山因子，称为下山因子，)10( ),1 ,0()()(1kxfxfxxkkkk（4.12）牛顿下山法牛顿下山法xkxk+1,)1(1kkxx 1, 0 从从 开场，逐次将开场，逐次将 减半进行试算，减半进行试算，1直到能使下降条件直到能使下降条件 成立为止成立为止. . .)()(1kk

38、xfxf下山因子的选取下山因子的选取.013 xx131231kkkkkxxxxx当当 时求得时求得6.00 x ，9.171x 通过通过 逐次取半进行试算，当逐次取半进行试算，当 时可求得时可求得32/1,140625. 11x此时有此时有 ，656643.0)(1xf384.1)(0 xf而而. )()(01xfxf 不满足条件不满足条件显然显然 . .)()(01xfxf 由由 计算计算 时时 , , 均能使下山条件均能使下山条件成立成立. . 1x,32xx1),1 ,0()()(1kxfxfxxkkkk（4.12）计算结果：计算结果： 即为即为 的近似的近似. .4x*x;1866.

39、0)(,36181.122xfx;00667.0)(,32628.133xfx.0000086.0)(,32472.144xfx下山条件成立，可得到下山条件成立，可得到 ，从而使，从而使 收敛收敛. . 0)(limkkxfkx 7.4.4 重根情形重根情形 设设 ，整数，整数 ，那么那么 为方程为方程 的的 重根，此时有重根，此时有 )(*)()(xgxxxfm 0*)(,2xgm*x0)(xfm . 0*)(, 0*)(*)(*)()1( xfxfxfxfmm设设0)(kxf)(*)()()(*)()()()(xgxxxmgxgxxxxfxfxx 导数导数011*)( mx 且且 ，1*)

40、( x),1 ,0()()(1kxfxfxxkkkk,)()()(xfxfmxx那么那么 . . 0*)( x牛顿法的改进牛顿法的改进 迭代法迭代法 ), 1 , 0()()(1 kxfxfmxxkkkk（4.13）局部线性收敛局部线性收敛牛顿法牛顿法迭代函数迭代函数 求求 重根，至少有重根，至少有2 2阶收敛，阶收敛，mm*x晓得晓得 的重数的重数 令令)(/)()(xfxfx假设假设 是是 的的 重根，那么重根，那么 *x0)(xfm,)(*)()()(*)()(xgxxxmgxgxxx )()()(xxxx迭代法迭代法 ), 1 , 0()()()()()(21 kxfxfxfxfxfx

41、xkkkkkkk（4.14）至少至少2 2阶收敛阶收敛. . 故故 是是 的单根的单根. . *x0)(x牛顿法牛顿法.)()()()()(2xfxfxfxfxfx 改进改进求重根迭代法的改进求重根迭代法的改进mx1)(* 迭代函数为迭代函数为 例例12 方程方程 的根的根 是二重根，是二重根，用上述三种方法求根用上述三种方法求根.04424xx2* x解解 （1 1） 牛顿法牛顿法 .42844423241kkkkkkkkkxxxxxxxxx （2 2） 用用4.134.13式式 .22,221kkkkxxxxm （3 3） 用用4.144.14式式 .2)2(221kkkkkxxxxx取初

42、值取初值 ，计算结果如表，计算结果如表7-9. 7-9. 5.10 x,44)(24xxxf),1 ,0()()(1kxfxfmxxkkkk（4.13）),1 ,0()()()()()(21 kxfxfxfxfxfxxkkkkkkk（4.14） 从结果看出，经过三步计算，方法从结果看出，经过三步计算，方法2 2及及3 3均达到均达到1010位有效数字，而由于牛顿法只有线性收敛，所以要达到同位有效数字，而由于牛顿法只有线性收敛，所以要达到同样精度需迭代样精度需迭代3030次次. . 414213562.1414213562.14254976191414215686.14

43、36607143.12411764706.1416666667.1458333333.11)3()2()1(9321xxxxkk方法方法方法三种方法数值结果表77.5 弦截法与抛物线法弦截法与抛物线法 计算计算 较困难较困难)(xf 每步迭代要计算每步迭代要计算 及及 . .)(kxf)(kxf 缺点缺点7.5.1 弦截法弦截法 设设 是是 的近似根，的近似根，1,kkxx0)(xf利用利用 )(),(1kkxfxf构造一次插值多项式构造一次插值多项式 ，并用，并用 的根作为新的的根作为新的近似根近似根 . . )(1xp0)(1xp1kx).()()()(111kkkkkkxxxxxfxfx

44、fxp（5.1）由由有有 ).()()()(111kkkkkkkxxxfxfxfxx（5.2）牛顿公式牛顿公式 )()(1kkkkxfxfxx中的导数中的导数 用差商用差商 取代的结果取代的结果. .)(kxf 11)(kkkkxxxfxf几何意义几何意义 曲线曲线 上横坐标为上横坐标为 的点分别记为的点分别记为 ，)( xfy 1,kkxx1,kkPP则弦线则弦线 的斜率等于差商值的斜率等于差商值 , , 1kkPP11)(kkkkxxxfxf).()()(11kkkkkkxxxxxfxfxfy其方程为其方程为按按5.2)5.2)式求得的式求得的 实际上是弦线实际上是弦线 与与 轴交点的轴交

45、点的横坐标横坐标. . 1kx1kkPPx这种算法因此而称为弦截法这种算法因此而称为弦截法. . 表表7-67-6 而弦截法而弦截法5.25.2），在求），在求 时要用到前面两步的结时要用到前面两步的结果果 ，1kx1,kkxx弦截法与切线法的区别弦截法与切线法的区别 切线法在计算切线法在计算 时只用到前一步的值时只用到前一步的值 . .kx1kx因此使用这种方法必须先给出两个开始值因此使用这种方法必须先给出两个开始值 . .01, xx 例例12 用弦截法解方程用弦截法解方程 .01e)(xxxf56714.0456709.0356532.026.015.00计算结果107kxk表 设取设取

46、 作为作为开始值，用弦截法求得的结果见表开始值，用弦截法求得的结果见表7-107-10，6.0,5.010 xx解解弦截法的收敛速度也是相当快的弦截法的收敛速度也是相当快的这里这里 是方程是方程 的正根的正根. . 618.1251p012 定理定理6 6 假设假设 在根在根 的邻域的邻域 内内具有二阶连续导数，且对任意具有二阶连续导数，且对任意 有有 ，又初值，又初值 那么当邻域那么当邻域充分小时，弦截法充分小时，弦截法5.25.2将按将按 阶收敛到根阶收敛到根 . . )(xf*x*:xxx0)( xf,10 xx*xp).()()()(111kkkkkkkxxxfxfxfxx（5.2）

47、设已知方程设已知方程 的三个近似根的三个近似根 ，21,kkkxxx0)(xf 几何上，这种方法的基本思想几何上，这种方法的基本思想是用抛物线与是用抛物线与 轴的交点轴的交点 作为作为所求根所求根 的近似位置图的近似位置图7-7). 7-7). 1kxx*x图图7-77-7以这三点为节点构造二次插值多项式以这三点为节点构造二次插值多项式 ，)(2xp 的一个零点的一个零点 作为新的近似根，作为新的近似根，)(2xp1kx并适当选取并适当选取密勒密勒MllerMller法法 7.5.2 抛物线法抛物线法 插值多项式插值多项式 ).)(,)(,)()(12112kkkkkkkkkxxxxxxxfx

48、xxxfxfxp).)(,)(,)()(12112kkkkkkkkkxxxxxxxfxxxxfxfxp有两个零点：有两个零点： ,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）式中式中 ).(,1211kkkkkkkxxxxxfxxf 问题是该如何确定问题是该如何确定 . .1kx 假定在假定在 三个近似根中，三个近似根中， 更接近所求的更接近所求的根根 . .21,kkkxxxkx*x 为了保证精度，选为了保证精度，选5.35.3中较接近中较接近 的一个值作为的一个值作为新的近似根新的近似根 . . kx1kx 为此，只要取根式前的符号与为此，只要取根式前的符号与 的符号相

49、同的符号相同. . 例例13 13 用抛物线法求解方程用抛物线法求解方程 .01e)(xxxf设用表设用表7-107-10的前三个值的前三个值 56532.0,6.0,5.0210 xxx作为开始值，计算得作为开始值，计算得 ,093271.0)(,175639.0)(10 xfxf,005031.0)(2xf,68910.2,01xxf56714.0456709.0356532.026.015.00计算结果107表kxk解解故故 .75694.2)(,1201212xxxxxfxxf,83373.2,12xxf.21418.2,012xxxf代入代入5.35.3式求得式求得 .56714.0,)(4)(201222223xxxfxfxfxx 以上计算表明，抛物线法比弦截法收敛得更快以上计算表明，抛物线法比弦截法收敛得更快. . 在一定条件下可以证明，对于抛物线法，迭代误差有在一定条件下可以证明，对于抛物线法，迭代误差有下列渐近关系式下列渐近关系式 .*)(6*)(42.01840.1xfxfeekk 从从5.35.3看到，即便看到，即便 均为实数，均为实数， 也也可以是复数，所以抛物线法适用于求多项式的实根和复根可以是复数，所以抛物线法适用于求多项式的实根和复根. . 21,kkkxxx1kx可