数值分析课件第二章_非线性方程求根

1、第二章第二章 非线性方程的求根方法非线性方程的求根方法第二章第二章 非线性方程的求根方法非线性方程的求根方法2.1 引言引言超越方程超越方程 ：中含三角函数、指数函数、或其中含三角函数、指数函数、或其他超越函数。他超越函数。用数值方法求解非线性方程的步骤：用数值方法求解非线性方程的步骤：（1）找出隔根区间；（只含一个实根的区间称隔根）找出隔根区间；（只含一个实根的区间称隔根区间）区间）（2）近似根的精确化。从隔根区间内的一个或多个）近似根的精确化。从隔根区间内的一个或多个点出发，逐次逼近，寻求满足精度的根的近似值。点出发，逐次逼近，寻求满足精度的根的近似值。2.2 方程求根的二分法方程求根的二

2、分法1()2kkkbabauf(an)f(bn)0;ubn an= (b a)/ 2n-1an, bn 的的中点中点xn满足不等式满足不等式*22nnnnbabaxx*2nnbaxx证明：证明：n方法一（事后估计法）方法一（事后估计法） （）/2n方法二（事前估计法）方法二（事前估计法） 二分法精度控制的两种方法：二分法精度控制的两种方法：*22nnnnbabaxx：ln()lnln 2bak这样就可以由给定的精度要求这样就可以由给定的精度要求 , 事先计算出计事先计算出计算次数算次数 k。n计算过程简单，收敛性可保证；计算过程简单，收敛性可保证；n对函数的性质要求低，只要连续即可。对函数的性

3、质要求低，只要连续即可。n收敛速度慢；收敛速度慢；n不能求复根和重根；不能求复根和重根；n调用一次求解一个，调用一次求解一个，a, b间的多个根间的多个根无法求得。无法求得。二分法求解非线性方程的优缺点：二分法求解非线性方程的优缺点：n二分法的基本原理就是以 0.5的比例逐次缩小有根区间，事实上，这个比例还可取0到1之间的任何值，即令 n若取c=0.618，即令，即令得到著名的黄金分割法。二分法的一种改进：二分法的一种改进：2.3 迭代法及其收敛性迭代法及其收敛性迭代法的基本思想：迭代法的基本思想：31xx35721. 115 . 113301xx33086. 1135721. 113312x

4、x32588. 1133086. 113323xx311kkxx2.3.1 不动点迭代法不动点迭代法)(1kkxx*limxxkk)(xx)(xyxyx2 x1 x0y = x)(xyn但迭代法并不总令人满意，如将前述方程但迭代法并不总令人满意，如将前述方程改写为另一等价形式：改写为另一等价形式：13 xx131kkxx此时称迭代过程此时称迭代过程发散发散。则有则有x1=2.375， x2=12.396，x3=1904,结果越来越大。结果越来越大。仍取初值仍取初值x0=1.5，建迭代公式：建迭代公式：012*xxxxO)(xyxy 0231*xxxxxO)(xyxy 收敛收敛 附近较平缓在*)

5、(xx2013*xxxxxO)(xyxy *012xxxxO)(xyxy 发散发散 附近较陡峭在*)(xx2.3.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性证：证： 若若aa )(bb )(或或显然显然 有不动点；有不动点；否则，设否则，设aa )(bb )(则有则有aa )(bb )(记记xxx)()(则有则有0)()(ba故存在故存在x*使得使得0*)(x即即*)(xxx*即为不动点。即为不动点。设有设有 x1* x2*, 使得使得*1*1)(xx*2*2)(xx则则|)(| )()(|*2*1*2*1*2*1xxxxxx其中，其中，介于介于 x1* 和和 x2* 之

6、间。之间。由定理条件由定理条件1| )(|Lx可得可得|*2*1*2*1xxxx矛盾！矛盾！故故 x1* = x2*，不动点唯一存在。，不动点唯一存在。x0 xn+1xn xn |11|1*nnnxxLxx011*xxLLxxnn)()(*1xxxxnn|)(| )()(|*1*1*xxxxxxnnn|*1*xxLxxnn|*0*xxLxxnn0|lim|lim*0*xxLxxnnnn( 0L1 )故迭代格式收敛。故迭代格式收敛。*limxxnn所以所以|*1*11*11*xxLxxxxxxxxxxxxnnnnnnnnnn| )1(1*nnnxxxxL|11|1*nnnxxLxx011*xxL

7、Lxxnnx0 xk+1xk xk xk+1xk x0 x0 *0lim |lim|nnnnxxLxx(L1 )故迭代格式发散。（故迭代格式发散。（L=1？）？）limnnx 所以所以关于不动点迭代法的几点说明：关于不动点迭代法的几点说明：10*1nnLxxxxL*111| |1nnnnnxxxxxxL321kkkxxxkkxx31211(3)5kkkxxx)3(211kkkxxx032xx0=2，对上述四种方法，计算三步所得结果如下：，对上述四种方法，计算三步所得结果如下：k xk (1) (2)(3) (4)0 x0 2 2221 x1 3 1.51.81.752 x2 9 21.7521

8、.7321433 x3 87 1.51.738099 1.732051注：注：x*=1.7320508xkekxk 1li mkpkkecexkxx x x xn+1xn pnnpnnnxxpxxxxxxxx)(!1)(! 21)()()(*)(2* 0*)(, 0*)(*)(*)()()1( xxxxpp)(!|*|*)()(|*|)(1nppnnnpxxxxxx|*)(|!1| )(|!1lim|*|*|lim)()(1xppxxxxpnpnpnnn由由Taylor公式公式xk+1=g(xk) 2.3.3 迭代收敛的加速方法迭代收敛的加速方法解解：由前知，迭代格式：由前知，迭代格式 xk+

9、1=xk3-1 是发散的。现用是发散的。现用迭代法计算。取迭代法计算。取 (x )=x3-1，结果如下：，结果如下：x0230 xxe23xex2ln32lnln3( )xxxx12lnln3kkxx2( )xxx 2max |( )|13x2.4 Newton迭代法迭代法2.4.1 Newton迭代法及其收敛性迭代法及其收敛性)()(1kkkkxfxfxxxyx*xk+1xkPky=f(x)()(kkkxxxfxfy)()()(xfxfxx222)()()()()()()(1)(xfxfxfxfxfxfxfx 解解： f (x)=ex+xex，故，故Newton迭代公式为迭代公式为kkkxk

10、xxkkkexeexxx11kxkkkxexxxk11k xk 00.51 0.5710220.5671630.56714迭代迭代3次即可得到精度为次即可得到精度为10-5的近似解的近似解0.56714。若。若用不动点迭代，达到同一用不动点迭代，达到同一精度需精度需17次。次。Newton迭代法的缺陷：迭代法的缺陷：1.被零除错误被零除错误2.程序死循环程序死循环-6-4-20246-200-1000100200 xx3-3 x+2y = arctan x对对 f(x) = arctan x存在存在 x0，Newton迭代迭代法陷入死循环。法陷入死循环。 (x)|=|1-cf (x)|1，即取

11、，即取0cf (x)2在在x*附近成附近成立，则收敛。立，则收敛。u若取若取c=1/f (x0)，则称，则称简化简化Newton法法，避免了每次，避免了每次迭代中导数值的运算，收敛阶下降为一阶。迭代中导数值的运算，收敛阶下降为一阶。2.4.2 简化简化Newton法（平行弦法）法（平行弦法）)(1kkkxcfxx)()(xcfxx2.4.3 弦截法（割线法）弦截法（割线法）11)()()(kkkkkxxxfxfxf)()()()(111kkkkkkkxxxfxfxfxxx0 ，x1 ，)()()()(11kkkkkkxxxxxfxfxfyxyx*xk+1xk-1Pk-1y=f(x)xkPk)(

12、)()()(111kkkkkkkxxxfxfxfxx100()()()()kkkkkf xxxxxf xf x313)()()()(21123111kkkkkkkkkkkkkkxxxxxxxxxxfxfxfxx)()(01xfxfxxkkk3313203xxxxkkk0)arctan()(xxf0 x精确解为)1(arctan21kkkkxxxx10 x取初值20 x取初值收敛发散xk+1xk2.4.4 Newton下山法下山法)()(1kkkkxfxfxx称称Newton下山法下山法。)()(1kkkkxfxfxxkkkxxx)1 (11（0 1,下山因下山因子）子）从从 =1开始，逐次减半

13、计算。开始，逐次减半计算。,21,21,21, 132 的选取：的选取：即按即按033 xx)()(1kkkkxfxfxx)1(3323kkkkxxxx)1(332003001xxxxx505829.32)()(1kkkkxfxfxxm g(x) ,m 2，m为整数，为整数，g(x*) 0,则则x*为为方程方程f(x)=0的的m重根。此时有重根。此时有 f(x*)=f (x*)= (m-1) (x*)=0, (m) (x*) 02.4.5 重根情形重根情形)()()(xfxfmxx)()(1kkkkxfxfmxx方法一方法一只要只要f (xk ) 0，仍可用，仍可用Newton法计算，此法计算

14、，此时时)()()(xfxfx)(*)()()(*)()(xgxxxmgxgxxx)()()()()()()(21kkkkkkkkkkxfxfxfxfxfxxxxx 关于精度控制问题关于精度控制问题()kf x精度控制方法一精度控制方法一是一种比较简单的精度控制方法，特别是求复数根的是一种比较简单的精度控制方法，特别是求复数根的时候，但其与真正误差的偏差为时候，但其与真正误差的偏差为*()()()()()kkkkf xf xf xfxx当当()1,kf则则*()()kkkf xxxe这时这时 是很好的停机准则是很好的停机准则()kf x但若但若 很大或很小，则与实际误差偏差较大。很大或很小，则与实际误差偏差较大。()kf关于精度控制问题关于精度控制问题1kkxx精度控制方法二精度控制方法二是一种最常用的停机准则，对于不动点（简单）迭代是一种最常用的停机准则，对于不动点（简单）迭代法法L难估计且难估计且L越大误差越大，故越大误差越大，故这时取这时取 ，可以得到更好的停机准则，可以得到更好的停机准则0()()kggx*111| |1kkkkkxxxxxxL*11*()()()1()kkkkk