方程求根的迭代法

§4.1引言緒論中講到方程求根得二分法，但二分法收斂速度慢，有必要掌握新的方法?！?.迭代法是一種逐次逼近法，使用某個(gè)固定公式〔迭代公式〕反復(fù)校正，逐步精確，直到滿足精度。迭代法求根分兩步：猜想初值2〕迭代如求解初值問題用梯形公式〔1〕看作關(guān)于的函數(shù)方程，按歐拉公式提供猜想值，代入〔1〕得假設(shè)仍不滿足要求，那么將它代入〔1〕式，繼續(xù)得到校正值，寫成迭代公式〔2〕一般地，為了求一元非線性方程的根，可以先將其轉(zhuǎn)換為如下的等價(jià)形式〔3〕式〔3〕中連續(xù)函數(shù)稱為迭代函數(shù)，其右端含未知數(shù)，不能直接求解。先用根的某個(gè)猜想值代入〔3〕，構(gòu)造迭代公式：。如果迭代值有極限，那么稱迭代收斂，極限值就是方程〔3〕的根。幾何意義P127圖4-1為使迭代法有效，必須保證它的收斂行，滿足什么條件，才能保證收斂？以最簡單的線性迭代，可以看出收斂的充分必要條件。幾何意義P127圖4-2,3,4,5?！?.設(shè)是方程的根，那么由微分中值定理，如果存在，使得有，那么迭代誤差，由于，故，即迭代收斂。需注意，上述過程中需保證一切迭代值全落在，為此要求對(duì)任意，總有。綜上，壓縮映像原理：定理1設(shè)在上具有連續(xù)的一階導(dǎo)數(shù)，滿足條件：〔1〕對(duì)任意，總有。映內(nèi)性〔2〕存在，使得對(duì)于任意成立。壓縮性那么迭代過程對(duì)于任意初值均收斂于方程的根，且有以下誤差估計(jì)式：證明：由有從而有，〔7〕式得證，結(jié)合〔7〕式得由〔7〕式知只要的偏差足夠小，就能保證迭代值足夠準(zhǔn)確，可用來控制迭代過程是否結(jié)束。流程圖見P128圖4－6。例1P130P142題3，5，6，7注意迭代函數(shù)的選擇，同一方程，可以采用不同的迭代函數(shù)，但迭代函數(shù)可能不收斂，或收斂緩慢，迭代函數(shù)的選擇非常重要。§4.在方程求根的迭代法中，迭代函數(shù)確實(shí)定，至關(guān)重要，它直接影響著迭代法的收斂性。但在實(shí)際應(yīng)用中，同一個(gè)方程可以等價(jià)導(dǎo)出不同的迭代函數(shù)，而且要嚴(yán)格地利用定理1的條件判斷迭代公式在整個(gè)區(qū)間內(nèi)收斂〔全局收斂〕也非常困難，因此常常判斷迭代公式的局部收斂性。通常在根的鄰近考察。如果存在鄰域，使得迭代過程對(duì)于任意初值均收斂，這種收斂性稱為局部收斂性。定理2設(shè)在的根鄰近有一階導(dǎo)數(shù)，且成立，那么迭代過程在鄰近具有局部收斂性。證：存在充分小鄰域，使，L為某個(gè)定數(shù)，根據(jù)微分中值定理：，注意到，又當(dāng)時(shí)，故有，即由定理1知對(duì)于任意均收斂。例2P131§4.迭代誤差，當(dāng)時(shí)，稱迭代過程為P階收斂的，P＝1稱線性收斂，P＝2稱為平方收斂。對(duì)于在根鄰近收斂的迭代公式，由于，式中介于和之間，故有，假設(shè)，那么為線性收斂。假設(shè)，將在處進(jìn)行泰勒展開有：，又，，由上式知，說明當(dāng)，時(shí)平方收斂。故有下述論斷：定理3設(shè)在在根的鄰近有連續(xù)的二階導(dǎo)數(shù)，且，那么時(shí)線性收斂；當(dāng)，時(shí)平方收斂。例P146題3§4.2迭代過程的加速§4.迭代過程收斂緩慢，計(jì)算量將很大，需要進(jìn)行加速。設(shè)是根的某個(gè)近似值，用迭代公式校正一次得，假設(shè)在所考察得范圍內(nèi)變化不大，其估計(jì)值為L，那么有：有迭代公式，是比更好的近似根。這樣加工后的計(jì)算過程為：迭代改良合并的例3P133§4.上述加速方法含有導(dǎo)數(shù)，不便于計(jì)算。設(shè)將迭代值再迭代一次，又得，由于又，消去L得計(jì)算過程如下：迭代迭代改良§4.3牛頓法§4.對(duì)于方程，設(shè)它的近似根，函數(shù)在處可用一階泰勒展開來近似，取的根作為的新的近似根，記作，那么：，這就是牛頓公式，相應(yīng)的迭代函數(shù)是牛頓法是一種逐步線性化方法，將非線性方程的求根問題歸結(jié)為計(jì)算一系列的根。牛頓法幾何意義是：(牛頓法亦稱切線法，直線經(jīng)過、)，流程圖P136圖4－9例5：P137牛頓法收斂很快。其迭代公式假定是的單根，即，，那么由上式知。故牛頓法至少平方收斂定理4牛頓法在的單根附近為平方收斂。(局部收斂)證：1〕由知，故其局部收斂。2〕代入得由上式得，故單根時(shí)平方收斂。但當(dāng)是的重根時(shí)，牛頓法線性收斂。因，其中有二階導(dǎo)數(shù)，且故，當(dāng)m>1時(shí)，且有，故線性收斂?！?.3.給定正數(shù)c，用牛頓法解二次方程的計(jì)算公式，設(shè)是近似根，那么也是近似根，它們的算術(shù)平均將是更好的近似值。定理5開方公式對(duì)于任意給定初值均為平方收斂。證明：〔15〕兩式相除得令，那么由上式得對(duì)任意，總有，故有，收斂性得證。由〔15〕，迭代誤差，有，迭代過程為平方收斂?！?.例7P138為防止迭代發(fā)散，通常對(duì)迭代過程附加一項(xiàng)要求，即保證函數(shù)單調(diào)下降：，稱為下山法。將牛頓法與下山法結(jié)合，在下山法保證函數(shù)值穩(wěn)定下降得前提下，用牛頓法加快收斂速度。由牛頓法有，與前一步的近似值適當(dāng)加權(quán)平均作為新值：其中，稱為下山因子，選取適當(dāng)?shù)南律揭蜃邮箚握{(diào)條件成立。下山因子的選擇，可從開始反復(fù)折半，一旦單調(diào)性條件成立，稱下山成功。如果單調(diào)性條件始終不成立，那么下山失敗，需要重新選擇初值進(jìn)行計(jì)算。牛頓法的收斂性強(qiáng)烈依賴于初值的選擇，實(shí)際計(jì)算中，可先采用二分法，求得足夠精確的近似值，再用牛頓法?！?.4弦截法牛頓法的收斂速度快，但需要提供導(dǎo)數(shù)值，如果比擬復(fù)雜，導(dǎo)數(shù)的計(jì)算困難，為防止求導(dǎo)數(shù)，改用差商替換牛