數值分析課件第二章_非線性方程求根

1、第二章第二章 非線性方程的求根方法非線性方程的求根方法第二章第二章 非線性方程的求根方法非線性方程的求根方法2.1 引言引言超越方程超越方程 ：中含三角函數、指數函數、或其中含三角函數、指數函數、或其他超越函數。他超越函數。用數值方法求解非線性方程的步驟：用數值方法求解非線性方程的步驟：（1）找出隔根區(qū)間；（只含一個實根的區(qū)間稱隔根）找出隔根區(qū)間；（只含一個實根的區(qū)間稱隔根區(qū)間）區(qū)間）（2）近似根的精確化。從隔根區(qū)間內的一個或多個）近似根的精確化。從隔根區(qū)間內的一個或多個點出發(fā)，逐次逼近，尋求滿足精度的根的近似值。點出發(fā)，逐次逼近，尋求滿足精度的根的近似值。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對函數的性質要求低，只要連續(xù)即可。對函數的性

3、質要求低，只要連續(xù)即可。n收斂速度慢；收斂速度慢；n不能求復根和重根；不能求復根和重根；n調用一次求解一個，調用一次求解一個，a, b間的多個根間的多個根無法求得。無法求得。二分法求解非線性方程的優(yōu)缺點：二分法求解非線性方程的優(yōu)缺點：n二分法的基本原理就是以 0.5的比例逐次縮小有根區(qū)間，事實上，這個比例還可取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此時稱迭代過程此時稱迭代過程發(fā)散發(fā)散。則有則有x1=2.375， x2=12.396，x3=1904,結果越來越大。結果越來越大。仍取初值仍取初值x0=1.5，建迭代公式：建迭代公式：012*xxxxO)(xyxy 0231*xxxxxO)(xyxy 收斂收斂 附近較平緩在*)

5、(xx2013*xxxxxO)(xyxy *012xxxxO)(xyxy 發(fā)散發(fā)散 附近較陡峭在*)(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 )故迭代格式發(fā)散。（故迭代格式發(fā)散。（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 是發(fā)散的?，F(xiàn)用是發(fā)散的?，F(xiàn)用迭代法計算。取迭代法計算。取 (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.程序死循環(huán)程序死循環(huán)-6-4-20246-200-1000100200 xx3-3 x+2y = arctan x對對 f(x) = arctan x存在存在 x0，Newton迭代迭代法陷入死循環(huán)。法陷入死循環(huán)。 (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取初值收斂發(fā)散xk+1xk2.4.4 Newton下山法下山法)()(1kkkkxfxfxx稱稱Newton下山法下山法。)()(1kkkkxfxfxxkkkxxx)1 (11（0 1,下山因下山因子）子）從從 =1開始，逐次減半

13、計算。開始，逐次減半計算。,21,21,21, 132 的選?。旱倪x?。杭窗醇窗?33 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