數(shù)值計(jì)算方法

1、第二章非線性方程數(shù)值解法在科學(xué)計(jì)算中常需要求解非線性方程 (2.1)即求函數(shù)的零點(diǎn)非線性方程求解沒有通用的解析方法，常采用數(shù)值求解算法數(shù)值解法的基本思想是從給定的一個(gè)或幾個(gè)初始近似值出發(fā)，按某種規(guī)律產(chǎn)生一個(gè)收斂的迭代序列，使它逐步逼近于方程(2.1)的某個(gè)解本章介紹非線性方程實(shí)根的數(shù)值求解算法：二分法、簡單迭代法、Newton迭代法及其變形，并討論它們的收斂性、收斂速度等§2.1二分法一、實(shí)根的隔離定義2.1設(shè)非線性方程(2.1)中的是連續(xù)函數(shù)如果有使，則稱為方程(2.1)的根，或稱為函數(shù)的零點(diǎn)；如果有，且在鄰域內(nèi)連續(xù)，為正整數(shù)，則稱為方程(2.1)的重根當(dāng)時(shí)，稱為方程的單根非線性方

2、程根的數(shù)值求解過程包含以下兩步(1) 用某種方法確定有根區(qū)間稱僅存在一個(gè)實(shí)根的有根區(qū)間為非線性方程的隔根區(qū)間，在有根區(qū)間或隔根區(qū)間上任意值為根的初始近似值；(2) 選用某種數(shù)值方法逐步提高根的精度，使之滿足給定的精度要求對(duì)于第(1)步有時(shí)可以從問題的物理背景或其它信息判斷出根的所在位置，特別是對(duì)于連續(xù)函數(shù)，也可以從兩個(gè)端點(diǎn)函數(shù)值符號(hào)確定出有根區(qū)間當(dāng)函數(shù)連續(xù)時(shí)，區(qū)間搜索法是一種有效的確定較小有根區(qū)間的實(shí)用方法，其具體做法如下設(shè)是方程(2.1)的一個(gè)較大有根區(qū)間，選擇合適的步長，由左向右逐個(gè)計(jì)算，如果有，則區(qū)間就是方程的一個(gè)較小的有根區(qū)間一般情況下，只要步長足夠小，就能把方程的更小的有根區(qū)間分離出

3、來；如果有根區(qū)間足夠小，例如區(qū)間長度小于給定的精度要求，則區(qū)間內(nèi)任意一點(diǎn)可視為方程(2.1)的根的一個(gè)近似例2.1確定出方程的一個(gè)有根區(qū)間 解由知為上的單調(diào)遞增函數(shù)，進(jìn)而在內(nèi)最多只有一個(gè)實(shí)根經(jīng)計(jì)算知，所以在區(qū)間內(nèi)有惟一實(shí)根如果希望將有根區(qū)間再縮小，可以取步長，在點(diǎn)，計(jì)算出函數(shù)值的符號(hào)，最后可知區(qū)間內(nèi)有一個(gè)實(shí)根二、二分法 二分法是求非線性方程實(shí)根近似值的最簡單的方法其基本思想是將有根區(qū)間分半，通過判別函數(shù)值的符號(hào)，逐步縮小有根區(qū)間，直到充分逼近方程的根，從而得到滿足一定精度要求的根的近似值設(shè)在區(qū)間上連續(xù)，且方程(2.1)在區(qū)間內(nèi)有惟一實(shí)根記，中點(diǎn)將區(qū)間分為兩個(gè)小區(qū)間和，計(jì)算函數(shù)值，根據(jù)如下3種情

4、況確定新的有根區(qū)間：(1) 如果，則是所要求的根；(2) 如果，取新的有根區(qū)間；(3) 如果，取新的有根區(qū)間新有根區(qū)間的長度為原有根區(qū)間長度的一半對(duì)有根區(qū)間施以同樣的過程，即用中點(diǎn)將區(qū)間再分為兩半，選取新的有根區(qū)間，并記為，其長度為的一半(如圖2.1所示)圖2.1 二分法示意圖重復(fù)上述過程，建立如下嵌套的區(qū)間序列其中每個(gè)區(qū)間的長度都是前一個(gè)區(qū)間長度的一半，因此的長度為由和，得當(dāng)時(shí)，顯然，有總結(jié)得到如下收斂定理：定理2.1設(shè)在隔根區(qū)間上連續(xù)，且，則由二分法產(chǎn)生的序列收斂于方程(2.1)在上的根，并且有誤差估計(jì) (2.2)設(shè)預(yù)先給定根的絕對(duì)誤差限為，要求，只要成立，這樣求得對(duì)分次數(shù) (2.3)取為

5、大于的最小整數(shù)此時(shí)是方程(2.1)的滿足精度要求的根近似值注：由于舍入誤差和截?cái)嗾`差存在，利用浮點(diǎn)運(yùn)算不可能精確計(jì)算函數(shù)值，二分法中的判斷幾乎不可能滿足，取而代之為判斷條件，其中為根近似值的函數(shù)值允許誤差限總結(jié)以上內(nèi)容，給出如下算法算法2.1 (二分法) 輸入端點(diǎn)、根的絕對(duì)誤差限、根近似值的函數(shù)值允許誤差限；輸出近似解或失敗信息；Step 1用公式(2.3)計(jì)算最大迭代次數(shù)；Step 2對(duì)循環(huán)執(zhí)行Step 35；Step 3，計(jì)算；Step 4若，則輸出，end；Step 5若，則，否則例2.2用二分法求在上的根的近似值，要求解由于在區(qū)間上，故在上有惟一實(shí)根確定循環(huán)次數(shù)為，利用二分法計(jì)算結(jié)果見

6、表2.1表2.1二分法計(jì)算結(jié)果有根區(qū)間12345678910111.0,2.01.0,1.51.25,1.51.25,1.3751.3125,1.3751.343725,1.3751.359375,1.3751.359375,1.36718751.3632813,1.36718751.3632813,1.36523441.36425785, 1.36523441.51.251.3751.31251.343751.3593751.36718751.36328131.36523441.364257851.3647461252.3751.7968950.16210940.84838870.35098

7、270.09640880.03235580.03215000.00007200.01604600.0079887二分法具有如下特點(diǎn)(1) 優(yōu)點(diǎn)：計(jì)算簡單，對(duì)函數(shù)的光滑性要求不高，只要它連續(xù)，且在兩端的函數(shù)值異號(hào)，算法收斂就可以保證；(2) 缺點(diǎn)：只能求單實(shí)根和奇數(shù)重實(shí)根，收斂較慢，與為公比的等比級(jí)數(shù)相同當(dāng)函數(shù)連續(xù)時(shí)，方程(2.1)的實(shí)重根可轉(zhuǎn)換為的實(shí)單根一般在求方程根近似值時(shí)不單獨(dú)使用二分法，而常用它為其它數(shù)值方法提供初值§2.2簡單迭代法簡單迭代法是求解非線性方程根的近似值的一類重要數(shù)值方法本節(jié)將介紹簡單迭代法的基本思想、收斂條件、收斂速度以及相應(yīng)的加速算法一、簡單迭代法的基本思想

8、簡單迭代法采用逐步逼近的過程建立非線性方程根的近似值首先給出方程根的初始近似值，然后用所構(gòu)造出的迭代公式反復(fù)校正上一步的近似值，直到滿足預(yù)先給出的精度要求為止在給定的有根區(qū)間上，將方程(2.1)等價(jià)變形為 (2.4)在上選取作為初始近似值，用如下迭代公式() (2.5)建立序列如果有，并且迭代函數(shù)在的鄰域內(nèi)連續(xù)，對(duì)式(2.5)兩邊取極限，得因而是(2.4)的根，從而也是(2.1)的根稱為迭代函數(shù)，所得序列為迭代序列將這種求方程根近似值的方法稱為簡單迭代法，簡稱迭代法 例2.3試用方程的不同形式的變形建立迭代公式，并試求其在附近根的近似值 解利用方程的變形建立如下4種迭代公式 (1) ， (2)

9、 (3) (4) 取初值，迭代計(jì)算，結(jié)果見表2.2表2.2迭代法計(jì)算結(jié)果公式(1)公式(2)公式(3)公式(4)0123456781.51.35721.330861.325881.324931.324761.324721.324711.324711.52.37512.39651904.016.902443.288573.556514.49856inf1.51.290991.332141.323131.325061.324641.324731.324711.324711.51.93754.1053536.148223634.76.601241.438291.4877inf例2.3表明非線性方程的

10、不同等價(jià)形式對(duì)應(yīng)不同的迭代過程，從某一初值出發(fā)，有的迭代收斂快，有的收斂慢，甚至不收斂那么迭代函數(shù)滿足什么條件時(shí)才能保證迭代序列收斂? 迭代序列的誤差如何估計(jì)? 怎樣才能建立收斂速度快的迭代公式?定理2.2若函數(shù)在區(qū)間上具有一階連續(xù)導(dǎo)數(shù)，且滿足條件 對(duì)任意，有； 存在常數(shù)：，使得對(duì)任意有成立則(1) 方程在上有惟一實(shí)根(2) 對(duì)任意，迭代公式(2.5)收斂，且(3) 迭代公式(2.5)有誤差估計(jì)式 (2.6) (2.7)(4) (2.8)證明(1)構(gòu)造函數(shù)，由條件知，因此在上至少存在一個(gè)實(shí)根，又由條件知當(dāng)時(shí)，所以在內(nèi)存在惟一實(shí)根，即在內(nèi)存在惟一實(shí)根，記為(2)由及條件知，并且有，二者作差，并由

11、微分中值定理得 (2.9)其中，介于與之間結(jié)合條件，得 (2.10)反復(fù)遞推，有， 因，故(3)由式(2.10)得從而 (2.11)又由于 (2.12)其中介于和之間綜合式(2.11)及式(2.12)得誤差估計(jì)由式(2.12)反復(fù)遞推，得并代入式(2.6)得誤差估計(jì)(4)由式(2.9)得兩端取極限，并注意到的連續(xù)性和(因?yàn)榻橛谂c之間)，得誤差估計(jì)(2.6)稱為后驗(yàn)誤差估計(jì)，也稱為誤差漸進(jìn)估計(jì)，誤差估計(jì)(2.7)稱為先驗(yàn)誤差估計(jì)定理2.2條件成立時(shí)，對(duì)任意，迭代序列均收斂，故稱定理2.2為全局收斂性定理下面討論鄰近的收斂性，即局部收斂性定理2.3設(shè)存在方程根的閉鄰域以及小于的正數(shù)，使得連續(xù)且則對(duì)

12、任意，迭代收斂證明由在內(nèi)連續(xù)，且有，則對(duì)任意，有由定理2.2知迭代過程對(duì)任意初值均收斂二、迭代法的收斂階為刻畫迭代法收斂速度的快慢，引進(jìn)收斂序列的收斂階概念 定義2.2 設(shè)迭代序列收斂到，記，如果存在常數(shù)和實(shí)數(shù)，使得 (2.13)則稱序列是階收斂的當(dāng)時(shí)，稱為線性收斂的，此時(shí)要求；為超線性收斂越大，序列收斂到越快稱為漸進(jìn)常數(shù)，越小，收斂越快所以迭代法的收斂階是對(duì)迭代法收斂速度的一種度量 顯然，由定理2.2(4)知，當(dāng)時(shí)簡單迭代法線性收斂，漸進(jìn)常數(shù) 算法2.2 (簡單迭代法) 輸入初始值、容許誤差；輸出近似解或失敗信息；Step 1對(duì)循環(huán)執(zhí)行Step 23；Step 2；Step 3若，則輸出，e

13、nd；否則，轉(zhuǎn)向Step2例2.4求方程的最大實(shí)根的近似值，要求絕對(duì)誤差不超過解(1)確定有根區(qū)間方程等價(jià)形式為作函數(shù)和的圖形，如圖2.2所示，知方程的最大實(shí)根在區(qū)間內(nèi)(2)建立迭代公式，判別收斂性將方程等價(jià)變形為迭代函數(shù)，迭代公式由，知在區(qū)間內(nèi)僅有一根又，所以，當(dāng)時(shí)，圖2.2 函數(shù)和的圖形因?yàn)?，所以?duì)于一切有由定理2.2知，迭代法收斂(3) 迭代計(jì)算取，有，因?yàn)?，所以方程的最大根三、迭代法的加速?duì)于收斂的迭代序列，理論上迭代次數(shù)足夠多時(shí)，就可以使計(jì)算結(jié)果滿足任意給定的精度要求但在應(yīng)用中，有的迭代過程收斂極為緩慢，計(jì)算量很大，因此研究迭代格式的加速方法是非常必要的1.線性收斂序列的Aitken

14、加速法設(shè)是一個(gè)線性收斂的序列，極限為即有小于的正數(shù)使得由于它線性收斂，誤差減少的速度較慢，值得采用加速技術(shù)下面介紹Aitken加速法對(duì)充分大的，有由上面兩式得解得利用上式右端的值可定義另一序列，即得Aitken加速公式 (2.14)它仍然收斂到，但收斂速度更快證明請(qǐng)參考文獻(xiàn)19 2.Steffensen迭代法Aitken加速方案是對(duì)任意線性收斂序列構(gòu)建的，并不限定如何獲得將Aitken加速方法用于簡單迭代法產(chǎn)生迭代序列時(shí)，得到著名的Steffensen迭代法，具體迭代公式如下 (2.15)或者直接寫成可以證明Steffensen迭代法在一定的條件下與原簡單迭代法的迭代序列具有相同的極限，但St

15、effensen迭代法收斂速度更快，可以達(dá)到二階收斂證明請(qǐng)參考文獻(xiàn)19例2.5對(duì)例 2.3用Steffensen迭代法求方程根的近似值，要求 解(1) 簡單迭代法 將原方程化成，建立迭代公式易驗(yàn)證該迭代公式在區(qū)間上滿足定理2.2的條件，產(chǎn)生的迭代序列收斂(2) Steffensen迭代法 加速公式為(1) 取初值，簡單迭代法和Steffensen迭代法計(jì)算結(jié)果見表2.3注意：Steffensen迭代法每一迭代步的計(jì)算量大約是原簡單迭代法計(jì)算量的兩倍表2.3簡單迭代法和Steffensen迭代法計(jì)算結(jié)果迭代法Steffensen法0123456789101.51.3483997251.36737

16、63721.3649570151.3652647481.3652255941.3652305751.3652299411.3652300221.3652300121.3652300131.51.92.43.13.94.06.38.11.01.31.51.3652652231.3652300131.3652300131.33.52.5§2.3Newton迭代法 Newton迭代法是求解非線性方程根的近似值的一種重要數(shù)值方法其基本思想是將非線性函數(shù)逐步線性化，從而將非線性方程(2.1)近似地轉(zhuǎn)化為一系列線性方程來求解下面討論其格式的構(gòu)造、收斂性、收斂速度以及有關(guān)變形一、Newton 迭代

17、法的構(gòu)造設(shè)是方程(2.1)的某根的一個(gè)近似值，將函數(shù)在點(diǎn)處作Taylor展開取前兩項(xiàng)近似代替，即用線性方程近似非線性方程(2.1)設(shè)，則用線性方程的根作為非線性方程根的新近似值，即定義 (2.16)上式即是著名的Newton迭代公式它也是一種簡單迭代法，其中迭代函數(shù) Newton迭代法具有明顯的幾何意義(如圖2.3所示)方程的根即為曲線與軸的交點(diǎn)的橫坐標(biāo)設(shè)是的某個(gè)近似值，過曲線上相應(yīng)的點(diǎn)作切線，其方程為它與軸的交點(diǎn)橫坐標(biāo)就是只要初值取得充分靠近根，序列就會(huì)很快收斂到所以Newton迭代法也稱為切線法圖2.3 Newton迭代法的幾何意義二、收斂性定理2.4設(shè)是方程(2.1)的單根，在的鄰域上連

18、續(xù)且則存在，當(dāng)時(shí)，Newton法產(chǎn)生的序列至少二階收斂 證明(1) Newton法迭代函數(shù)的導(dǎo)數(shù)為顯然，在鄰域上連續(xù)又，一定存在的某個(gè)閉鄰域，當(dāng)時(shí)，有從而Newton法產(chǎn)生的序列收斂(2)將在處作一階Taylor展開 (2.17)其中介于與之間又由Newton迭代公式有 (2.18)式(2.17)與式(2.18)相減從而 (2.19)由迭代法收斂階的定義知，Newton迭代法至少具有二階收斂速度上述定理給出了Newton法局部收斂性，它對(duì)初值要求較高，初值必須充分靠近方程根時(shí)才可能收斂，因此在實(shí)際應(yīng)用Newton法時(shí)，常常需要試著尋找合適的初值下面的定理則給出Newton法在有根區(qū)間上全局收斂

19、的一個(gè)充分條件 定理2.5設(shè)是方程(2.1)在區(qū)間上的根且在上存在，如果(1) 對(duì)于任意有，； (2) 選取初值，使則Newton法產(chǎn)生的迭代序列單調(diào)收斂于，并具有二階收斂速度(a) (b)(c) (d)圖2.4定理2.5的幾何解釋 證明滿足定理?xiàng)l件(1)共有4種情形，如圖2.4所示下面僅以圖2.4()情況進(jìn)行證明，此時(shí)滿足對(duì)任意有，初值 首先用數(shù)學(xué)歸納法證明有下界當(dāng)時(shí)，成立假設(shè)時(shí)，不等式成立將在處作一階Taylor展開，得于是又由Newton迭代公式，有 (2.20)式(2.20)右端的第二項(xiàng)大于零，因此由數(shù)學(xué)歸納法知， 其次證明單調(diào)遞減由，知，于是Newton迭代公式(2.16)的第二項(xiàng)大

20、于零，從而故迭代序列單調(diào)減少 序列單調(diào)減少有下界，它必有極限，記為，它滿足，進(jìn)而有對(duì)兩端取極限，并利用，的連續(xù)性，得=0結(jié)合函數(shù)在上的單調(diào)性知 因此，Newton法產(chǎn)生的迭代序列單調(diào)收斂于，利用式(2.20)及式(2.19)知該Newton迭代序列二階收斂算法2.3 (Newton迭代法) 輸入初始近似值、 容許誤差；輸出近似解或失敗信息；Step 1對(duì)循環(huán)執(zhí)行Step 23；Step 2；Step 3若，則輸出，end；否則，轉(zhuǎn)向step2 例2.6利用非線性方程的Newton迭代公式計(jì)算的近似值，使得，并證明對(duì)任意，該迭代法均收斂解(1) 建立計(jì)算公式 其中(2) 判斷收斂性 在區(qū)間內(nèi)，當(dāng)

21、選取初值時(shí)，存在足夠大的，使得由定理2.5知，該迭代公式產(chǎn)生的迭代序列都收斂于當(dāng)選取初值時(shí)， 這樣，從起，以后的都大于 故該迭代公式對(duì)任何初值都收斂 (3) 取初值，迭代計(jì)算，結(jié)果見表2.4表2.4Newton法計(jì)算結(jié)果0123421.751.73214291.73205081.7320508從表2.4可見，迭代4步后已經(jīng)滿足精度要求，精確解三、Newton迭代法的變形Newton迭代格式構(gòu)造容易，迭代收斂速度快，但對(duì)初值的選取比較敏感，要求初值充分接近真解，另外對(duì)重根收斂速度較慢（僅有線性收斂速度），而且當(dāng)函數(shù)復(fù)雜時(shí)，導(dǎo)數(shù)計(jì)算工作量大下面從不同的角度對(duì)Newton法進(jìn)行改進(jìn)1 Newton下

22、山算法Newton迭代法的收斂性依賴于初值的選取，如果偏離較遠(yuǎn)，則Newton迭代法有可能發(fā)散，從而在實(shí)際應(yīng)用中選出較好的初值有一定難度，而Newton下山法則是一種降低對(duì)初值要求的修正Newton迭代法方程(2.1)的根也是的最小值點(diǎn)，若把看成在處的高度，則是山谷的最低點(diǎn)若序列滿足單調(diào)性條件 (2.21)則稱為稱為的下山序列在Newton迭代法中引入下山因子，將Newton迭代公式(2.16)修正為 (2.22)適當(dāng)選取下山因子，使得單調(diào)性條件(2.21)成立，即稱為Newton下山法對(duì)下山因子的選取是逐步探索進(jìn)行的一般地，從開始反復(fù)將因子的值減半進(jìn)行試算，一旦單調(diào)性條件(2.21)成立，則

23、稱“下山成功”；反之，如果在上述過程中找不到使條件(2.21)成立的下山因子，則稱“下山失敗”，這時(shí)可對(duì)進(jìn)行擾動(dòng)或另選初值，重新計(jì)算2 針對(duì)重根情形的加速算法假設(shè)是方程的重根，并且存在函數(shù)，使得有 (2.23)式中在的某鄰域內(nèi)可導(dǎo)，則Newton迭代函數(shù)，其導(dǎo)數(shù)在處的值所以，由定理2.2知Newton迭代法此時(shí)只有線性收斂速度為了加速收斂，可以采用如下兩種方法方法一令，則是方程的單根，將Newton迭代函數(shù)修改為因此有重根加速迭代公式 (2.24)它至少二階收斂方法二將Newton迭代函數(shù)改為這時(shí)，由此得到加速迭代公式 (2.25)3 割線法Newton法每步需要計(jì)算導(dǎo)數(shù)值如果函數(shù)比較復(fù)雜時(shí)，

24、導(dǎo)數(shù)的計(jì)算量比較大，此時(shí)使用Newton法不方便為了避免計(jì)算導(dǎo)數(shù)，可以改用平均變化率替換Newton迭代公式中的導(dǎo)數(shù)，即使用如下公式 (2.26)上式即是割線法的迭代公式割線法也具有明顯的幾何意義，如圖2.5所示，依次用割線方程的零點(diǎn)逐步近似曲線方程的零點(diǎn)割線法的收斂速度比Newton法稍慢一點(diǎn)，可以證明其收斂階約為1.618，證明請(qǐng)參考文獻(xiàn)4此外在每一步計(jì)算時(shí)需要前兩步的信息，即這種迭代法也是兩步法兩步法在計(jì)算前需要提供兩個(gè)初始值與圖2.5割線法的幾何意義例2.7已知方程有一個(gè)二重根，分別用Newton法(2.16)和重根Newton法(2.24)和(2.25)求其近似值，要求解，由Newton法(2.16)得由Newton法(2.24) 得由Newton法(2.25) 得利用上述三種迭代格式，取初值，分別計(jì)算，結(jié)果見表2.5表2.5Newton法和重根Newton法計(jì)算結(jié)果式(2.16)式(2.24)式(2.25)01231014151.41.40714291.41068711.41245251.41419981.41421271.41421311.41.41414141.41