計(jì)算方法非線性方程數(shù)值解法

1、計(jì)算方法講稿第二章 非線性方程數(shù)值解法第二章非線性方程數(shù)值解法本章將討論非線性方程(2.1)的數(shù)值解法，我們最為熟悉的非線性方程是一元二次方程也是最簡(jiǎn)單的非線性方程，其解為：但是對(duì)于(2.1)式中一般形式的非線性函數(shù)，很難甚至不可能找到解析形式的解，通常只能用數(shù)值的方法求其近似數(shù)值解。2.1基本概念定義2.1如果滿足，則稱為方程(2.1)的解或根，也稱為函數(shù)的零點(diǎn)或根。用數(shù)值方法求解非線性方程的解，通常需要我們對(duì)其解有一個(gè)初步的估計(jì)，或知道其解的一個(gè)限定區(qū)間，因此確定包含解的區(qū)間將是我們首先需要解決的問題。定義2.2若連續(xù)函數(shù)在內(nèi)至少有一個(gè)根，則稱為有根區(qū)間，若在內(nèi)恰有一個(gè)根，則稱為隔根區(qū)間。

2、定理2.1 如果函數(shù)在上連續(xù)且，則在內(nèi)至少有一個(gè)根，如果函數(shù)另外滿足在上單調(diào)連續(xù)，則在內(nèi)恰有一個(gè)根。尋找隔根區(qū)間的通常方法有：圖形法, 試探法。例2.1 求的有根區(qū)間。解：作出函數(shù)的曲線圖形圖2.1 例2.1曲線示意圖觀察圖中的曲線與X軸的交點(diǎn)，可判斷在區(qū)間之間方程有一個(gè)根。例2.2 求的有根區(qū)間。解：計(jì)算出在一些點(diǎn)的值。-3-2-10123-12-10-3-4324從表中可以看出是一個(gè)根，區(qū)間是一個(gè)有根區(qū)間。如果在-2,-1之間把間隔再縮小到0.25我們可以得到下列表格-2-1.75-1.5-1.25-1-1-0.0470.3750.3950在這個(gè)表格里我們又發(fā)現(xiàn)一個(gè)有根區(qū)間。從此例中我們可

3、以體會(huì)到試探法有可能漏掉某些有根區(qū)間，具有一定的局限性。2.2二分法二分法也稱為對(duì)分法，是我們求解很多問題的有效方法，求解非線性方程也有稱之為“二分法”的數(shù)值方法。二分法的算法思想非常簡(jiǎn)單、直觀，收斂性也易于理解，以下我們給出求解非線性方程二分法的算法過程。設(shè)在區(qū)間上連續(xù)且，由高等數(shù)學(xué)的知識(shí)可知在區(qū)間內(nèi)至少有的一個(gè)根，令，取此區(qū)間的中點(diǎn)，則1) 如果，區(qū)間內(nèi)至少有的一個(gè)根，令；2) 如果，區(qū)間內(nèi)至少有的一個(gè)根，令如此我們將得到一個(gè)新的區(qū)間，可以斷定在此區(qū)間內(nèi)至少有一個(gè)根且新區(qū)間的長(zhǎng)度縮小到原長(zhǎng)度的一半，反復(fù)執(zhí)行這一過程，我們將得到一個(gè)包含根的區(qū)間序列，這個(gè)有根區(qū)間序列的每個(gè)區(qū)間有3個(gè)的特點(diǎn)1)

4、 均是有根區(qū)間，；2) 區(qū)間包含，；3) 區(qū)間長(zhǎng)度減半，。二分法算法的收斂性證明正是基于這3個(gè)特點(diǎn)，證明如下：按照以上算法過程，我們可以得到一有根區(qū)間序列，在每個(gè)區(qū)間內(nèi)取其中點(diǎn)構(gòu)造近似解序列(2.2)則有(2.3)從而說明所構(gòu)造的算法是收斂的。誤差估計(jì)：按照(2.3)式，我們可以得到以作為的近似解，其誤差為(2.4)即近似解的誤差不超過原區(qū)間的倍。終止準(zhǔn)則：如果要求近似解的誤差達(dá)到指定的精度，即要求，根據(jù)(2.3)式只要當(dāng)前有根區(qū)間滿足下式即可： (2.5)迭代次數(shù)：在給定精度后就可以確定迭代次數(shù)k，也就是說只要迭代k次，其近似解就可以達(dá)到所要求的精度，根據(jù)終止準(zhǔn)則(2.5)式，有：對(duì)上述后邊

5、的式子兩邊取對(duì)數(shù)就可以算出滿足精度所需要的迭代次數(shù)。算法2.1 (求解非線性方程的二分法)0) 初始化 取初始有根區(qū)間，計(jì)算，置迭代精度1) 如果，則得近似解，算法結(jié)束2) 取3) 如果則，否則4) 轉(zhuǎn)1)繼續(xù)迭代。5) 算法結(jié)束實(shí)際計(jì)算時(shí)，在已經(jīng)確定函數(shù)值時(shí)，僅需要計(jì)算其中一個(gè)函數(shù)值，在每個(gè)迭代過程中，只需要計(jì)算并不需要再次計(jì)算，以節(jié)約計(jì)算量。例2.3 求方程在區(qū)間內(nèi)的一個(gè)實(shí)根，要求準(zhǔn)確到小數(shù)點(diǎn)后兩位(即至少有三位有效數(shù))。解：首先用有效數(shù)字與絕對(duì)誤差關(guān)系公式確定精度再計(jì)算需要迭代的次數(shù)兩邊取對(duì)數(shù)則有，實(shí)際計(jì)算過程的結(jié)果如下：迭代次數(shù)abb-axf(x)11.000001.500000.50

6、0001.25000-0.2968821.250001.500000.250001.375000.2246131.250001.375000.125001.31250-0.0515141.312501.375000.062501.343750.0826151.312501.343750.031251.328130.0145861.312501.328130.015631.32031-0.01871最后近似解為：，精確解為：，估計(jì)誤差為：0.005，實(shí)際誤差為：二分法的優(yōu)點(diǎn)是算法簡(jiǎn)單，無需任何參考資料就可以編程實(shí)現(xiàn)；缺點(diǎn)是收斂速度慢。2.3迭代法迭代法也稱為簡(jiǎn)單迭代法、不動(dòng)點(diǎn)迭代法，是一種對(duì)方程

7、根的逐步逼近、逐步精確直到滿足給定精度要求的迭代算法。1 迭代法的計(jì)算過程首先把非線性方程變換為等價(jià)的形式，稱其為迭代函數(shù)，然后取一個(gè)初始近似解，按如下迭代格式計(jì)算近似解序列：(2.6)如果且連續(xù)，則由于與是等價(jià)的方程，所以滿足，即也是的解。注意到將代入其函數(shù)值仍為，所以也稱為的不動(dòng)點(diǎn)，而迭代法也稱為不動(dòng)點(diǎn)迭代法。例2.4 對(duì)于方程，取，比較以下4種迭代格式的計(jì)算結(jié)果。迭代次數(shù)11.50001.5000e+0001.50001.5000e+00021.35722.3750e+0001.29101.9375e+00031.33091.2396e+0011.33214.1053e+00041.32

8、591.9040e+0031.32313.6148e+00151.32496.9024e+0091.32512.3635e+00461.32483.2886e+0291.32466.6012e+01271.32473.5565e+0881.32471.4383e+038從這4個(gè)迭代函數(shù)建立的迭代法的計(jì)算結(jié)果可以看出，有兩個(gè)收斂?jī)蓚€(gè)發(fā)散，也就意味著并不是所有的迭代函數(shù)都是收斂的，以下我們考察迭代法收斂的條件，為此先看一下迭代法的幾何解釋。2 迭代法的幾何解釋對(duì)于迭代函數(shù)緩慢單調(diào)增情況，如圖2.2取初始點(diǎn)，計(jì)算對(duì)應(yīng)于曲線上的點(diǎn)，從作為自變量的計(jì)算出的，對(duì)應(yīng)于曲線上的點(diǎn)，如此繼續(xù)可以得到，可以看出其

9、趨勢(shì)將是沿左側(cè)逐步逼近其解。圖2.2 緩慢的單調(diào)增圖2.3 緩慢的單調(diào)減對(duì)于迭代函數(shù)緩慢單調(diào)減情況，如圖2.3取可得曲線上點(diǎn)，再?gòu)膶?duì)應(yīng)的計(jì)算得到曲線上的點(diǎn)，同樣可以得到，其趨勢(shì)將是從兩側(cè)逐步逼近其解?？傊?，當(dāng)緩慢變化時(shí)，無論是緩慢增還是緩慢減，迭代法均是收斂到方程的根。再看迭代函數(shù)急速單調(diào)增情況，如圖2.4取可得曲線上點(diǎn)，再?gòu)膶?duì)應(yīng)的計(jì)算得到曲線上的點(diǎn)，同樣可以得到，其趨勢(shì)將向一側(cè)遠(yuǎn)離其解。圖2.4 急速的單調(diào)增圖2.5 急速的單調(diào)減當(dāng)?shù)瘮?shù)急速單調(diào)減時(shí)，如圖2.5取可得曲線上點(diǎn)，再?gòu)膶?duì)應(yīng)的計(jì)算得到曲線上的點(diǎn)，同樣可以得到，但趨勢(shì)將向兩側(cè)遠(yuǎn)離。3 迭代法的收斂性從幾何解釋可以看出，迭代法是否收

10、斂與迭代函數(shù)在其解附近的變化率有關(guān)，亦即是與迭代函數(shù)的導(dǎo)數(shù)絕對(duì)值的大小有關(guān)，事實(shí)確是如此，請(qǐng)看如下定理：定理2.2 (迭代法收斂的充分條件)如果函數(shù)在區(qū)間上可微，時(shí)滿足條件:1) ，即點(diǎn)列恒成立；2) ，即迭代函數(shù)變化緩慢。則以區(qū)間上的任意點(diǎn)為初始點(diǎn)，迭代格式產(chǎn)生的序列都收斂到方程的唯一根。證明：首先證明根的存在性，考慮輔助函數(shù)可驗(yàn)證，則存在使，即。再證迭代格式的收斂性，注意到其中是介于與之間的一點(diǎn)。反復(fù)利用該式，則有：因此有。關(guān)于唯一性，可以任取兩個(gè)解，則有因?yàn)椋灾荒苁浅闪?。定?.3 (誤差估計(jì))在定理2.2的條件下，有如下誤差估計(jì)式：(2.7)證明：事實(shí)上，第k次迭代之后再經(jīng)過p次迭

11、代，應(yīng)該有對(duì)此式兩邊取極限，因?yàn)橛兴砸簿陀?2.7)式成立，證畢。例2.5 求方程在中的根，要求誤差不超 (分析所使用迭代格式的斂散性)。解：容易驗(yàn)證所給區(qū)間是方程的隔根區(qū)間，取迭代函數(shù)為，迭代格式為驗(yàn)證定理2.1中條件1)，任取，迭代函數(shù)的導(dǎo)數(shù)，則g(x)單調(diào)減，所以再驗(yàn)證條件2)，從而所取迭代格式是收斂的。按要求誤差必須達(dá)到，只要即可，因此取終止精度，初始點(diǎn)，迭代過程結(jié)果如下：1234560.6065310.5452390.5797030.5600650.5711720.5648637891011120.5684380.5664090.5675600.5669070.5672770.56

12、70671314151617180.5671860.5671190.5671570.5671350.5671480.567141精確解為，近似解。實(shí)際誤差顯然我們不可能按照例2.5的方法作為迭代終止的準(zhǔn)則，以下我們討論適合編程的迭代算法的終止準(zhǔn)則。(1) 一個(gè)明顯的規(guī)則是對(duì)于給定精度，當(dāng)時(shí)算法終止，遺憾的是在迭代過程中是不可知的，注意到(2.7)式表示的是近似解與精確解之差和相鄰近似解之差的關(guān)系，我們也可以用來作為迭代收斂的判別準(zhǔn)則，即對(duì)于給定的精度，當(dāng)時(shí)算法停止。當(dāng)然此時(shí)的精度不再是近似解于精確解的誤差限，而是一個(gè)算法判斷收斂的精度要求。這一終止準(zhǔn)則不僅用于求解非線性方程的迭代法，幾乎所有的

13、迭代算法都是用這一準(zhǔn)則來判斷迭代算法收斂的。(2) 另一個(gè)需要關(guān)注的問題是，迭代算法有不收斂的可能，不能夠讓算法無休止的迭代下去，所以算法需要規(guī)定迭代超過多少次還沒有收斂時(shí)，判定迭代失敗，即要規(guī)定最大的迭代次數(shù)，這一原則也適用于其他迭代算法。至此我們有了算法的迭代過程以及算法的終止準(zhǔn)則，下面給出簡(jiǎn)單迭代法的算法。算法2.2 (求解非線性方程的簡(jiǎn)單迭代法)0) 初始化 取初始點(diǎn)，最大迭代次數(shù)N和精度，置；1) 當(dāng)時(shí)循環(huán)執(zhí)行下列步驟1.1) 計(jì)算；1.2) 如果，則停止計(jì)算，可作為方程的近似解；1.3) 令，繼續(xù)執(zhí)行下一次循環(huán)。2) 算法結(jié)束前述的定理2.2給出的迭代法收斂的充分條件不便于驗(yàn)證，使

14、用起來有一定的局限性，現(xiàn)在再給出一個(gè)局部收斂條件，較之于定理2.2 更易使用。定義2.3設(shè)是方程的根，如果存在和的一個(gè)鄰域，當(dāng)取時(shí)，迭代格式收斂于方程的根，則稱迭代函數(shù)在方程的根處有局部收斂性。定理2.4 (局部收斂條件) 設(shè)迭代函數(shù)在方程的根附近的一個(gè)鄰域有連續(xù)的一階導(dǎo)數(shù)且，則迭代格式在附近具有局部收斂性。證明留做習(xí)題。4 迭代加速一般的迭代法收斂速度太慢，我們考慮如何提高其收斂速度的方法。取方程的初始近似解，令，在迭代格式收斂的情況下， 一般是比更好的近似解。設(shè)是方程的精確解，由中值定理有記，則有從該式解得以此作為近似解得根據(jù)這一思想我們得到一般迭代格式的加速公式：(2.8)考慮用此加速迭

15、代公式計(jì)算例2.5中的方程，取初始點(diǎn)，計(jì)算結(jié)果為：012340.5000000.5663110.5671230.5671430.567143迭代3次即超過一般迭代法18次的迭代精度。斯蒂芬森(Steffensen)加速對(duì)于上述加速的方法，最大的問題是要估計(jì)的導(dǎo)數(shù)，這是很困難的甚至是不可能做到的，以下我們考慮用兩次迭代的信息估計(jì)出的值。取初始點(diǎn)，計(jì)算，仍記，則有解此聯(lián)立方程，消去L得最后得新的近似解為此公式就是著名的斯蒂芬森加速公式，并由此得到斯蒂芬森加速迭代格式：(2.9)Steffensen迭代法一個(gè)更為重要的優(yōu)點(diǎn)是只要算法就是收斂的，用此加速迭代公式求解例2.5的結(jié)果為：01230.500

16、0000.5676240.5671430.567143兩次已經(jīng)得到很好的近似解，遠(yuǎn)優(yōu)于簡(jiǎn)單迭代法的18次迭代。算法2.3 (求解非線性方程的斯蒂芬森(Steffensen)加速算法)0) 初始化 取初始點(diǎn)，最大迭代次數(shù)N，給定精度，置；1) 當(dāng)時(shí)循環(huán)執(zhí)行下列步驟1.1) 按(2.9)式計(jì)算；1.2) 若，則停止計(jì)算，為方程的近似解。1.3) 令，繼續(xù)執(zhí)行下一次循環(huán)2) 算法結(jié)束我們用迭代格式(2.9)重新計(jì)算例2.4的，取同樣的初始點(diǎn)，計(jì)算結(jié)果為：迭代次數(shù)01.5000001.5000001.5000001.50000011.3248991.4162931.3253721.38938321.3

17、247181.3556501.3247181.33541131.3247181.3289491.3247181.32504441.3248041.32471851.3247181.32471861.3247185 收斂速度在此之前講述的幾個(gè)算法，我們看到不同的迭代公式收斂速度差別很大，為了度量算法的收斂速度，我們引入收斂“階”的概念。所謂一個(gè)算法的收斂速度，其本質(zhì)是迭代過程中的近似解與精確解的誤差收斂于0的速度，而算法的收斂階越高收斂速度越快。定義2.4設(shè)，如果存在常數(shù)，使得(2.10)則稱序列為p階收斂或稱收斂的階是p。顯然階越高收斂越快！p=1時(shí)稱為線性收斂，一般迭代法是線性收斂；p=2時(shí)

18、稱為平方收斂， Steffensen加速法是平方收斂；p=1且c=0稱為超線性收斂。定理2.5(判斷收斂階定理) 設(shè)在非線性方程的根處有連續(xù)的p階導(dǎo)數(shù)而且滿足則迭代格式是p階收斂。證明：因?yàn)?，由定?.3可知，迭代格式在附近局部收斂，將在處Taylor展開，則有其中介于和之間，此式可改寫成：根據(jù)此式可得到從而證得迭代格式是p階收斂的?？梢则?yàn)證，對(duì)于例2.5中的迭代格式，由于，因而是線性收斂的；而對(duì)于Steffensen加速公式，可以驗(yàn)證是二階收斂。2.4牛頓(Newton)法求解非線性方程的Newton法也是一種迭代法，而且是最著名的一種迭代法，也被認(rèn)為是最為有效的迭代法之一，其收斂階可達(dá)二階

19、，而算法的推導(dǎo)過程也非常簡(jiǎn)單。1. Newton法迭代公式及收斂性考慮已得到非線性方程的解的一個(gè)近似值，將函數(shù)在處Taylor展開并忽略二階以上的高階項(xiàng)得到一個(gè)近似的線性方程：以此線性方程的解作為原方程新的近似解有理由認(rèn)為將是比更好的近似解，反復(fù)執(zhí)行此過程可得如下迭代格式：(2.11)稱(2.11)式為Newton迭代格式。如果把，則Newton法也是迭代法的一種形式，其導(dǎo)數(shù)為如果是的一個(gè)單根，則有，進(jìn)而，也就存在的鄰域，使根據(jù)定理2.4和定理2.5可知Newton法有局部收斂性且至少是二階收斂，因此有如下結(jié)論。定理2.6 (Newton法收斂性) 如果是的一個(gè)單根，則Newton法有局部收斂

20、性且至少是二階收斂的。算法2.4 (求解非線性方程的Newton法)0) 初始化 取初始點(diǎn)，最大迭代次數(shù)N和精度，置；1) 當(dāng)時(shí)循環(huán)執(zhí)行以下各步驟1.1) 計(jì)算；1.2) 若，則停止計(jì)算，為方程的近似解；1.3) 令，繼續(xù)執(zhí)行下一次循環(huán)2) 算法結(jié)束例2.6 試用Newton法求解方程，取初始點(diǎn)。解：先計(jì)算導(dǎo)數(shù)，迭代函數(shù)，得迭代格式迭代結(jié)果為012341.5000001.3478261.3252001.3247181.3247182 Newton法的幾何意義如圖所示的是Newton法迭代的收斂過程。圖2.6 Newton法的幾何意義Newton法在求解非線性方程的迭代過程中，首先取近似解可得到

21、曲線上的點(diǎn)，過此點(diǎn)作曲線的切線，而切線與X軸有一個(gè)交點(diǎn)，同樣對(duì)應(yīng)曲線上的一個(gè)新點(diǎn)，過此點(diǎn)再作曲線的切線，此切線與X軸又有一個(gè)交點(diǎn)，。如圖，如此反復(fù)執(zhí)行此過程，迭代點(diǎn)列將收斂到方程的解。3 Newton下山法關(guān)于Newton法的收斂性我們僅證明了局部收斂性，當(dāng)初試點(diǎn)選擇不好時(shí)，迭代有可能存在不收斂的危險(xiǎn)，事實(shí)也確是如此。對(duì)例2.6的方程用Newton法，取初始點(diǎn)迭代3次，迭代點(diǎn)列為：01230.580000151.111304100.74235567.163809為了解決Newton法的此類問題，通常采用所謂的Newton下山法，策略就是在Newton迭代公式中增加一個(gè)參數(shù)，稱為Newton下山

22、迭代公式：(2.12)參數(shù)稱為下山因子，其目的是保證使(2.13)成立，之所以稱為下山因子，是因?yàn)楫?dāng)?shù)c(diǎn)處的函數(shù)值太大(上山)時(shí)，使用此因子能夠使其值減小(下山)。一般是先取，如果不滿足(2.13)式則參數(shù)減半，反復(fù)檢查直到滿足(2.13)式，如果參數(shù)已經(jīng)很小仍然不滿足(2.13)式，則必須換一個(gè)新的初始點(diǎn)。使用Newton下山法重新計(jì)算，迭代結(jié)果為：0123450.5800001.1680131.3537841.3254751.3247181.3247184重根情況的Newton法在前述的有關(guān)Newton法收斂性與收斂階的證明分析中，前提是假設(shè)是的一個(gè)單根，對(duì)于重根情況容易證明Newton

23、法僅是線性收斂的，可以用如下方法提高Newton法的收斂速度。設(shè)是方程的m重根，定義迭代函數(shù)：(2.14)可以證明(2.14)式定義的迭代格式將是二階收斂的，遺憾的是求解非線性方程時(shí)往往事先并不知道其根是否為重根，因此迭代格式(2.14)基本無實(shí)用價(jià)值。另一方面我們知道Steffensen加速公式是二階收斂的，對(duì)于重根情況還可以考慮用Steffensen加速公式對(duì)Newton法進(jìn)行加速能夠提高收斂速度，試看下述例子。例2.7取初始點(diǎn)，用Newton法、(2.14)式、Steffensen加速公式求解解：(1) 用Newton法：迭代17次，結(jié)果如下：0123451.500001.272731.144081.074381.037851.01910678910111.009591.004811.002411.001201.000601.000301213141516171.000151.000081.000041.000021.000011.00000(2) 利用(2.14)式迭代3次，結(jié)果如下：01231.500001.045451.000501.00000(3) 利用Steffensen加速公式迭代2次，結(jié)果如下：0121.500000.995571.00000例2.8導(dǎo)出計(jì)