第二章非线性方程求解

1、School of mathematics & physics华北电力大学数理学院华北电力大学数理学院第二章第二章 非线性方程求根非线性方程求根*:( )0fCCf xxC ，问题：设求使 的解理论： （1）解的存在性.即有解还是无解； （2）解的邻域性态。即解的个数、孤立解、解的重数。*( )f xDCx，假设在一个邻域内有唯一解*x如何求得这个 ?任务是:School of mathematics & physics华北电力大学数理学院华北电力大学数理学院 2.1 2.1 二分法二分法f(x)a,bf(a) f(b)0,f(x)a,b 设在区间上连续，且则在区间内有解。不妨

2、假设有唯一解，则有function x,n=erff(f_name,a,b,epsl)%二分法函数求根，f(a)*f(b)epsl if abs(f)=0,break,end; if f*feval(f_name,a)0 a=x; else b=x; end x=(a+b)/2; n=n+1; f=feval(f_name,x); endSchool of mathematics & physics华北电力大学数理学院华北电力大学数理学院注注1： 二分法只能求奇数重实根奇数重实根。只能求实根是显见的！* m)(x)*( )m( )()()0*( )0,( ) *,(,)( )(xx,n

3、nnnmxf xf xxxxxxxxxnabxxmf xab在 设 为的 重根，则 ），。由的连续性，当时，不变号。于是，当 充分大时，有。 当 为偶数时函数上不变号了！关于奇数重有:School of mathematics & physics华北电力大学数理学院华北电力大学数理学院 注注2：二分法的收敛性 总而言之，二分法最大用处是划分有解区间。*11()()22nnnnxxbaba *12nnxxSchool of mathematics & physics华北电力大学数理学院华北电力大学数理学院例：用二分法求方程 在（-1,0）内的一个实根。 310f xxx 1.00

4、0000000000000 -0.500000000000000 0.500000000000000 2.000000000000000 -0.750000000000000 0.250000000000000 3.000000000000000 -0.625000000000000 0.125000000000000 4.000000000000000 -0.687500000000000 0.062500000000000 5.000000000000000 -0.656250000000000 0.031250000000000 6.000000000000000 -0.67187500

5、0000000 0.015625000000000 7.000000000000000 -0.679687500000000 0.007812500000000 8.000000000000000 -0.683593750000000 0.003906250000000 9.000000000000000 -0.681640625000000 0.001953125000000 10.000000000000000 -0.682617187500000 0.000976562500000 11.000000000000000 -0.682128906250000 0.0004882812500

6、00 12.000000000000000 -0.682373046875000 0.000244140625000 13.000000000000000 -0.682250976562500 0.000122070312500 14.000000000000000 -0.682312011718750 0.000061035156250 15.000000000000000 -0.682342529296875 0.000030517578125 16.000000000000000 -0.682327270507813 0.000015258789063 17.00000000000000

7、0 -0.682334899902344 0.000007629394531 18.000000000000000 -0.682331085205078 0.000003814697266 19.000000000000000 -0.682329177856445 0.000001907348633 20.000000000000000 -0.682328224182129 0.000000953674316 21.000000000000000 -0.682327747344971 0.000000476837158 22.000000000000000 -0.682327985763550

8、 0.000000238418579 23.000000000000000 -0.682327866554260 0.000000119209290 24.000000000000000 -0.682327806949615 0.000000059604645 25.000000000000000 -0.682327777147293 0.000000029802322 26.000000000000000 -0.682327792048454 0.000000014901161 27.000000000000000 -0.682327799499035 0.000000007450581nn

9、xnnbxSchool of mathematics & physics华北电力大学数理学院华北电力大学数理学院2.2 2.2 迭代法迭代法( )0( )xxfx ( )x把方程求解问题方程求解问题转化为不动点问题不动点问题。 称为迭代函数。0n 1n*xN (x )x(x )n0,1,2, 算法：function x,n=diedf(f_name, dief_name,x0,epsl)%一般迭代法求方程的根。n=0;while 1 f=feval(f_name,x0); if abs(f)=0,break,end; x= feval(dief_name,x0); if abs(x-x

10、0)=epsl,break,end; x0=x; n=n+1;end*limnnxx ?School of mathematics & physics华北电力大学数理学院华北电力大学数理学院0 ( ) , ( ) , * 101 1* 1 11nxa bxxa bxnLLxxxxnLxxxxnnnL 定理1: 如果在上是一阶导数连续的自映射，且，则，由迭代算法产生的数列收敛，且和 2.2 2.2 迭代法迭代法这称为全局收敛定理！School of mathematics & physics华北电力大学数理学院华北电力大学数理学院定理1的条件太强，不便应用!0n *(x)xx*(

11、x )L1xN (x )xnL* xxxxn101L1*xxxxnnn 11L 有连续一阶导数且定理2：设有不动点，满足在，则存在0，对于，迭代算法产生的序列收敛，且和2.2 2.2 迭代法迭代法这称为局部收敛定理！School of mathematics & physics华北电力大学数理学院华北电力大学数理学院一般迭代法在实际应用中，会遇到迭代函数构造的困难！一般迭代法在实际应用中，会遇到迭代函数构造的困难！2.2 2.2 迭代法迭代法 310f xxx 例：用迭代法求方程 的一个实根。可以转换为如下几个不动点方程：232321111131xxxxxxxxxxxx 等等！Scho

12、ol of mathematics & physics华北电力大学数理学院华北电力大学数理学院可以验证， 在（-1,0）内满足定理1的条件； 满足定理2的条件。取 ，迭代结果见下表。 1211xxx 322131xxxxxx00.5x 31.000000000000000 -0.682327581635735 0.000000571911748 32.000000000000000 -0.682327944996648 0.000000363360913 33.000000000000000 -0.682327714137326 0.000000230859322 34.0000000

13、00000000 -0.682327860812500 0.000000146675174 35.000000000000000 -0.682327767623250 0.000000093189250 36.000000000000000 -0.682327826830517 0.000000059207267 37.000000000000000 -0.682327789213512 0.000000037617005 38.000000000000000 -0.682327813113265 0.000000023899753 39.000000000000000 -0.68232779

14、7928691 0.000000015184574 40.000000000000000 -0.682327807576125 0.000000009647434nnx1nnxx 1xxSchool of mathematics & physics华北电力大学数理学院华北电力大学数理学院 1.000000000000000 -0.500000000000000 0 2.000000000000000 -0.714285714285714 0.214285714285714 3.000000000000000 -0.683179723502304 0.031105990783410 4.

15、000000000000000 -0.682328423304578 0.000851300197726 5.000000000000000 -0.682327803828347 0.000000619476231 6.000000000000000 -0.682327803828019 0.000000000000328nnx1nnxx 2xx21xxx 1.0000 -0.5000 0 2.0000 -2.0000 1.5000 3.0000 0.2500 2.2500 4.0000 -20.0000 20.2500 5.0000 0.0475 20.0475 6.0000 -464.26

16、59 464.3134nnx1nnxxSchool of mathematics & physics华北电力大学数理学院华北电力大学数理学院 上述说明，迭代法的迭代函数决定了迭代的收敛性。2.2 2.2 迭代法迭代法School of mathematics & physics华北电力大学数理学院华北电力大学数理学院2.3 2.3 牛顿迭代法牛顿迭代法*0*0000( )()()()()()（ ） 如果在其零点 有一阶的连续导数，且，那么对充分靠近 的点 ，有f xxxxff xf xfxxxxxx 0 *000()()()()0f xfxxxf x即0*010() ()f x

17、xxxfx得到：School of mathematics & physics华北电力大学数理学院华北电力大学数理学院0 x1x111()()()yf xfxxx2x*2 xx更靠近！*1110()()()(-)f xf xfxxx同理1*121( )-( )f xxxxfx得到School of mathematics & physics华北电力大学数理学院华北电力大学数理学院1(0,1,2,)-,()nnnnf xxxfxn称之为牛顿迭代法。类推，2.3 2.3 牛顿迭代法牛顿迭代法School of mathematics & physics华北电力大学数理学院华

18、北电力大学数理学院*0*( ) 0()(0nf xxxNxxxfx【定理】如果在其零点 有直到二阶的连续导数，且，则，对于，牛顿迭代产生的数列 至方收敛于平少。( )( )( )f xxxfx证明：令*2( )( )( )()0( )fxxf xxfx牛顿迭代收敛。School of mathematics & physics华北电力大学数理学院华北电力大学数理学院* 21*12*( )()()() ;2( )max( ) 22nnnnnxxxxxxxxxcxx 又 至少二阶收敛。School of mathematics & physics华北电力大学数理学院华北电力大学数理

19、学院4（ ）能求复数根吗？0 x1（ ）牛顿迭代法是局部收敛的。因此初始迭代点 的，选择较困难。另外，牛顿迭代法有下列问题：*2f (x )0（ ）说明，牛顿迭代法求单根有效且平方收敛。能求重根吗？n3) f (x )（导数一般来说计算困难！2.3 2.3 牛顿迭代法牛顿迭代法School of mathematics & physics华北电力大学数理学院华北电力大学数理学院*1*( )m1), ( )()( ) ( )()( )()0()0mmxf xmf xxxg xfxm xxh xg xh x 如果是的 重零点（那么其中， 关于重根关于重根 关于初值关于初值 实际问题的初值往

20、往是明确的！一般来说，初值的选择通常采用试探法。2.3 2.3 牛顿迭代法牛顿迭代法School of mathematics & physics华北电力大学数理学院华北电力大学数理学院*( )( )1( ) ()( )( )1()1L1*f xg xxxxx- xfxmh xxm1nmm牛顿迭代求重根时以速度 （1-） 收敛，且随重数 的增加收敛性越来越差。2.3 2.3 牛顿迭代法牛顿迭代法School of mathematics & physics华北电力大学数理学院华北电力大学数理学院nn 1nnf(x1m xxmf (x ) （ ）重数 已知时，迭代 至少平）方收敛

21、。nn 1nnf(x2m(x),f (x) (x )xx(x )）（ ）重数 未知时，令则迭代 至少平方收敛。求重根时可做如下改进，以提高其收敛速度！求重根时可做如下改进，以提高其收敛速度！2.3 2.3 牛顿迭代法牛顿迭代法School of mathematics & physics华北电力大学数理学院华北电力大学数理学院关于导数，可做如下改进：关于导数，可做如下改进：11(), 0,1, ;() ()1 =;(1 ), ,nnnkknnnf xxxnkfxfxxxf xnk（ ）0100111() () 2 () 12,()() nnnnnnnf xxxfxxxxxf xnf x

22、f x（ ）割，线法2.3 2.3 牛顿迭代法牛顿迭代法School of mathematics & physics华北电力大学数理学院华北电力大学数理学院能求复根能求复根20f (x)(x1)(x1)0 xix1.5i.例1 求方程的复根。初值n,x=newtonfa(ff14,1.5i,0.0001);n = 5x = -0.0000 + 1.0000i ii12.3 2.3 牛顿迭代法牛顿迭代法School of mathematics & physics华北电力大学数理学院华北电力大学数理学院2*( )(1)(1)0 1,xxxx例：分别用牛顿迭代法、改进牛顿迭代法以

23、及它们的离散型，求方程f的二重根并比较快慢。nn 1n 1nnnn 1nn 1n 1nnnn 1nn 1n 1nnnn 1nn 1nnnn 1xxxxf(x )f(x )f xxx1xxmf(x )f(x )f(xxx2xx(x )(x )(xxx (x )f(x )f(x )f(x)离散： 离散 ： 离散 ：，2.3 2.3 牛顿迭代法牛顿迭代法nn 1nnnn 1nnnn 1nnf(x ): xxf (x )f(x )1xxmf (x )(x )f(x)2xx, (x)(x )f (x)牛顿法 改进 ： 改进 ：School of mathematics & physics华北电力

24、大学数理学院华北电力大学数理学院方法牛顿改进1改进2离散离散1离散2迭代次数2655362031 epsl=1e-8, x0=1.5, m=2实验结果：2.3 2.3 牛顿迭代法牛顿迭代法School of mathematics & physics华北电力大学数理学院华北电力大学数理学院由此产生算法！称之为斯蒂芬森算法。2.4 2.4 迭代迭代加速收敛技术加速收敛技术222121*22121 () 22nnnnnnnnnnnnxxxxxxxxxxxxx解出1() 问题：迭代法收敛，但收敛较慢！怎么办？nnxx*21*1 这时，对充分大的 应有nnnnnxxxxxxxxSchool o

25、f mathematics & physics华北电力大学数理学院华北电力大学数理学院nnnn2nnn 1nnnnSteffensen z(x ) y(z )(yz ) xyy2zx算法： 预估：预估：校正： *n*(x )(x)x ,(x)x,Steffensenx1定理：如果有不动点在处连续，则算法生成的序列至少局部平方收敛。 School of mathematics & physics华北电力大学数理学院华北电力大学数理学院2*steffensenx ( (x)(x) (x)( (x)2 (x)x(x )=x 证明：迭代函数为显然， 与 有共同的不动点。令。* 22*1

26、(x)(x )(x )(xx )( )(xx )2 =xa(xx )( xx) School of mathematics & physics华北电力大学数理学院华北电力大学数理学院2*2*22*2*(x)(x )2ax (xx ) a (xx )( xx) * 212*2*( (x)( (x ) ( (x ) (xx )1 ( ( () (xx )2 xa (xx )( xx) 2*2*( xx)(x)x(a1)( xx )School of mathematics & physics华北电力大学数理学院华北电力大学数理学院*nn 122*nn2*n222*nna1n(x )xxx xxxx( xx)1c (a1)(a1)( xx )xx 当时，*n 1n(x )1x(x ) 即，当时迭代平方收敛。School of mathematics & phy