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

1、第二章第二章 非線性方程的求根方法非線性方程的求根方法第二章第二章 非線性方程的求根方法非線性方程的求根方法2.1 引言引言超越方程超越方程 ：中含三角函數(shù)、指數(shù)函數(shù)、或其中含三角函數(shù)、指數(shù)函數(shù)、或其他超越函數(shù)。他超越函數(shù)。用數(shù)值方法求解非線性方程的步驟：用數(shù)值方法求解非線性方程的步驟：（1）找出隔根區(qū)間；（只含一個實根的區(qū)間稱隔根）找出隔根區(qū)間；（只含一個實根的區(qū)間稱隔根區(qū)間）區(qū)間）（2）近似根的精確化。從隔根區(qū)間內(nèi)的一個或多個）近似根的精確化。從隔根區(qū)間內(nèi)的一個或多個點出發(fā)，逐次逼近，尋求滿足精度的根的近似值。點出發(fā)，逐次逼近，尋求滿足精度的根的近似值。2.2 方程求根的二分法方程求根的二

2、分法1()2kkkbaba*22nnnnbabaxx*2nnbaxx證明：證明：二分法精度控制的兩種方法：二分法精度控制的兩種方法：*22nnnnbabaxx：ln()lnln 2bak這樣就可以由給定的精度要求這樣就可以由給定的精度要求 , 事先計算出計事先計算出計算次數(shù)算次數(shù) k。二分法求解非線性方程的優(yōu)缺點：二分法求解非線性方程的優(yōu)缺點：二分法的一種改進：二分法的一種改進：2.3 迭代法及其收斂性迭代法及其收斂性迭代法的基本思想：迭代法的基本思想：31xx35721. 115 . 113301xx33086. 1135721. 113312xx32588. 1133086. 113323

3、xx311kkxx2.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 收斂收斂 附近較平緩在*)(xx2013*xxxxxO)(xyxy *0

4、12xxxxO)(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* 之間。之間。由定理條件由定理條件1| )(|Lx

5、可得可得|*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*xxLLxxnnx0 x0 *0lim |lim|n

6、nnnxxLxx(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.7321433 x3 87 1.51.738099 1.732051注：注：x*=1

7、.7320508xkekxk 1li mkpkkecexkpnnpnnnxxpxxxxxxxx)(!1)(! 21)()()(*)(2* 0*)(, 0*)(*)(*)()()1( xxxxpp)(!|*|*)()(|*|)(1nppnnnpxxxxxx|*)(|!1| )(|!1lim|*|*|lim)()(1xppxxxxpnpnpnnn由由Taylor公式公式xk+1=g(xk) 2.3.3 迭代收斂的加速方法迭代收斂的加速方法x0230 xxe23xex2ln32lnln3( )xxxx12lnln3kkxx2( )xxx 2max |( )|13x2.4 Newton迭代法迭代法2.

8、4.1 Newton迭代法及其收斂性迭代法及其收斂性)()(1kkkkxfxfxxxyx*xk+1xkPky=f(x)()(kkkxxxfxfy)()()(xfxfxx222)()()()()()()(1)(xfxfxfxfxfxfxfx kkkxkxxkkkexeexxx11kxkkkxexxxk11k xk 00.51 0.5710220.5671630.56714迭代迭代3次即可得到精度為次即可得到精度為10-5的近似解的近似解0.56714。若。若用不動點迭代，達到同一用不動點迭代，達到同一精度需精度需17次。次。Newton迭代法的缺陷：迭代法的缺陷：1.被零除錯誤被零除錯誤2.程序

9、死循環(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)。2.4.2 簡化簡化Newton法（平行弦法）法（平行弦法）)(1kkkxcfxx)()(xcfxx2.4.3 弦截法（割線法）弦截法（割線法）11)()()(kkkkkxxxfxfxf)()()()(111kkkkkkkxxxfxfxfxxx0 ，x1 ，)()()()(11kkkkkkxxxxxfxfxfyxyx*xk+1xk-1Pk-1y=f(x)xkPk)()()()(111kk

10、kkkkkxxxfxfxfxx100()()()()kkkkkf xxxxxf xf x313)()()()(21123111kkkkkkkkkkkkkkxxxxxxxxxxfxfxfxx)()(01xfxfxxkkk3313203xxxxkkk0)arctan()(xxf0 x精確解為)1(arctan21kkkkxxxx10 x取初值20 x取初值收斂發(fā)散2.4.4 Newton下山法下山法)()(1kkkkxfxfxx稱稱Newton下山法下山法。)()(1kkkkxfxfxxkkkxxx)1 (11（0 1,下山因下山因子）子）,21,21,21, 132 的選?。旱倪x?。杭窗醇窗?3

11、3 xx)()(1kkkkxfxfxx)1(3323kkkkxxxx)1(332003001xxxxx505829.32)()(1kkkkxfxfxx2.4.5 重根情形重根情形)()()(xfxfmxx)()(1kkkkxfxfmxx方法一方法一只要只要f (xk ) 0，仍可用，仍可用Newton法計算，此法計算，此時時)()()(xfxfx)(*)()()(*)()(xgxxxmgxgxxx)()()()()()()(21kkkkkkkkkkxfxfxfxfxfxxxxx 關于精度控制問題關于精度控制問題()kf x精度控制方法一精度控制方法一是一種比較簡單的精度控制方法，特別是求復數(shù)根

12、的是一種比較簡單的精度控制方法，特別是求復數(shù)根的時候，但其與真正誤差的偏差為時候，但其與真正誤差的偏差為*()()()()()kkkkf xf xf xfxx當當()1,kf則則*()()kkkf xxxe這時這時 是很好的停機準則是很好的停機準則()kf x但若但若 很大或很小，則與實際誤差偏差較大。很大或很小，則與實際誤差偏差較大。()kf關于精度控制問題關于精度控制問題1kkxx精度控制方法二精度控制方法二是一種最常用的停機準則，對于不動點（簡單）迭代是一種最常用的停機準則，對于不動點（簡單）迭代法法L難估計且難估計且L越大誤差越大，故越大誤差越大，故這時取這時取 ，可以得到更好的停機準則，可以得到更好的停機準則0()()kggx*111| |1kkkkkxxxxxxL*11*()()()1()kkkkkkkkkkkxxxxxxxxg xg xxxgxxgxx1011()kkx