第4章-2(非線性方程迭代解法)

第4章-2(非線性方程迭代解法)第一頁，共51頁。4.2非線性方程的迭代解法第二頁，共51頁。

工程實(shí)際與科學(xué)計(jì)算中都遇到大量求解非線性若數(shù)

(4-17)，，為方程（4-17）的零點(diǎn)。

的根，

使則稱或稱函數(shù)常見的非線性方程有代數(shù)方程（二次、三次等）、超越方程（三角方程，指數(shù)、對數(shù)方程等）。方程的問題。對于非線性方程第三頁，共51頁。

困難即使是最基本的代數(shù)方程，當(dāng)次數(shù)超過4時(shí)，在一般情況下沒有根式解公式，即難以用解析法求出方程的根，對于超越方程就更難了。

因此，研究用數(shù)值方法計(jì)算非線性方程的根就顯得非常必要。在求根時(shí)通常假設(shè)非線性方程中的函數(shù)是關(guān)于的連續(xù)函數(shù)。若令則它在平面直角坐標(biāo)系

下的圖像為連續(xù)曲線，

第四頁，共51頁?？梢?求的根，如果在區(qū)間

上僅有一個(gè)根，則稱

為方程的單根區(qū)間；為方程的多根區(qū)間。

上有多個(gè)根，則稱

若方程在與

軸的交點(diǎn)

就是求yxo第五頁，共51頁。

方程的單根區(qū)間和多根區(qū)間統(tǒng)稱為方程的有根區(qū)間。

為了研究方便，我們主要研究方程在單根區(qū)間上的求解方法。

第六頁，共51頁。（4-18）

4.2.1簡單迭代法

首先將方程化為一個(gè)與它同解的方程

為

其中的連續(xù)函數(shù)。即如果數(shù)使反之，，。則也有，則也有，若第七頁，共51頁。稱迭代法或迭代過程或迭代格式，通常稱（4-19）為求解非線性方程的簡單迭代法，代入（4-18）的右端，得到，再將代入（4-18）右端得，繼為之，得到一個(gè)數(shù)列，（4-19）稱為迭代函數(shù)，稱第步的迭代值或簡稱迭代值。其一般表示形式為

也，任取一個(gè)初始值第八頁，共51頁。則稱迭代法收斂，如果由迭代格式產(chǎn)生的數(shù)列收斂，即否則稱迭代法發(fā)散。若迭代法收斂于則所以。即第九頁，共51頁。幾何直觀：在曲線上得到點(diǎn)列，其橫坐標(biāo)分別為由公式所確定的迭代值，若迭代法收斂，則點(diǎn)列將越來越逼近所求的交點(diǎn)。p1p2p*yxop0y=x第十頁，共51頁。（1）化方程為等價(jià)方程則迭代值為取初始值用迭代法求的根。，，，，…顯然,當(dāng)時(shí)，,即迭代法收斂于1.就是方程的根。例1解則迭代格式為,所以第十一頁，共51頁。（2）

為等價(jià)方程化，同樣取初始值，其迭代格式為，，，顯然,當(dāng),故迭代法發(fā)散。

上述例子表明，迭代法的收斂與發(fā)散，依賴于迭代函數(shù)的構(gòu)造，迭代函數(shù)構(gòu)造的方法很多。

第十二頁，共51頁。

對于同一個(gè)方程，由于構(gòu)造出來的迭代函數(shù)不同，有的迭代函數(shù)所構(gòu)成的迭代法收斂，有的迭代函數(shù)所構(gòu)成的迭代法卻發(fā)散。迭代函數(shù)滿足什么條件時(shí)，迭代法收斂？第十三頁，共51頁。從而,迭代函數(shù)滿足條件：時(shí),迭代法收斂。第十四頁，共51頁。從而,當(dāng)或時(shí),迭代法發(fā)散。第十五頁，共51頁。定理4.5

設(shè)迭代函數(shù)滿足（1）

（2）

，存在正數(shù)對任意均有則在內(nèi)存在唯一根,且對任意初始值,迭代法收斂于,且1．2．（4-20）（4-21）當(dāng)時(shí)，第十六頁，共51頁。滿足條件（1）、（2）時(shí)，

易證方程在[a,b]內(nèi)存在唯一根。因?yàn)?，且，根?jù)微分中值定理可得其中。由條件（2）得（4-22）證第十七頁，共51頁。又因?yàn)閷⑸鲜揭祈?xiàng)整理后，得從而即（4-20）成立。再反復(fù)使用（4-22）的第2式，得

將上式代入（4-20）即得（4-21）成立。

又因?yàn)長＜1，所以根據(jù)（4-21）得故迭代法收斂。第十八頁，共51頁。當(dāng)?shù)瘮?shù)滿足定理4.5的條件且較小時(shí)，根據(jù)（4-20）式可知，只要相鄰兩次計(jì)算值的偏差達(dá)到事先給定的精度要求（即）時(shí)，過程就可以終止，迭代就可作為的近似值。因此，（4-20）式也是判斷迭代是否可終止的依據(jù)。如果對的大小可作出估計(jì)時(shí)，由（4-21）式就可以大概估計(jì)第十九頁，共51頁。出迭代過程所需要的迭代次數(shù)，即時(shí)，的大小范圍。由于定理4.5的條件一般難于驗(yàn)證，而且在大區(qū)間上，這些條件也不一定都成立，所以在使用迭代法時(shí)往往在根的附近進(jìn)行。只要假定在的附近連續(xù)，且滿足則根據(jù)連續(xù)函數(shù)的性質(zhì)，一定存在的某個(gè)鄰域，在S上滿足定理4.5的條件。第二十頁，共51頁。故在S中任取初始值,迭代格式收斂于方程的根,即,稱這種收斂為局部收斂。求方程在附近的一個(gè)根，要求精度。解由于,故當(dāng)時(shí)，<1因此，迭代格式,對于初始值=0.5是收斂的。例2第二十一頁，共51頁。

迭代的數(shù)值結(jié)果表第二十二頁，共51頁。從定理4.5的（4-21）式可以看出，當(dāng)L或在上的值越小，迭代過程的收斂速度就越快。但當(dāng)且接近于1時(shí)，迭代法雖然收斂,但是收斂速度很慢。為了使收斂速度有定量的判斷，概念，作為判斷迭代法收斂速度的重要標(biāo)準(zhǔn)。設(shè)迭代格式，當(dāng)時(shí)，，并記。特介紹收斂速度的階的第二十三頁，共51頁。定義4.2

若存在實(shí)數(shù)和滿足（4-23）則稱迭代法是階收斂。當(dāng)時(shí)，稱線性收斂，當(dāng)時(shí)稱超線性收斂，當(dāng)時(shí)稱平方收斂。越大迭代法的收斂速度也越快。但是在實(shí)際使用中很難直接確定，常常采用一些其他的方法來確定收斂的階。使用Taylor展開式是一種常用的方法。第二十四頁，共51頁。如果在根處充分光滑（各階導(dǎo)數(shù)存在），則可對在處進(jìn)行Taylor展開，得如果，但是，則即第二十五頁，共51頁。從而上式說明迭代法具有階收斂。定理4.6

如果在根中的迭代函數(shù)附近滿足滿足：（1）存在階連續(xù)導(dǎo)數(shù)；（2）則迭代法是階收斂。，第二十六頁，共51頁。要使迭代法收斂到例取迭代函數(shù)解：令且其收斂階是多少？此時(shí)為線性收斂，p=1。即有當(dāng)時(shí)，此時(shí)為平方收斂，p=2。當(dāng)時(shí)，則

應(yīng)取何值？第二十七頁，共51頁。4.2.2Newton迭代法及其變形

用迭代法解非線性方程時(shí)，如何構(gòu)造迭代函數(shù)是非常重要的，那么怎樣構(gòu)造的迭代函數(shù)才能保證迭代法收斂呢？不管非線性方程的形式如何，總可以構(gòu)造（4-25）作為方程（4-17）求解的迭代函數(shù)。因?yàn)槎以诟浇叫?，其局部收斂速度越快，第二十八頁，?1頁。故可令若（不是重根），則故可取代入（4-25）式，得第二十九頁，共51頁。例3證明由（4-24）建立的迭代格式至少是平方收斂。證根據(jù)定理4.6，只需證明。因?yàn)楣试摰ㄖ辽偈瞧椒绞諗?。由?-24）式建立的迭代法就是有名的Newton法。設(shè)且第三十頁，共51頁。定理4.7

設(shè)方程f（x）=0的根為,且則Newton迭代法（4-26）至少是平方收斂。第三十一頁，共51頁。Newton迭代法的幾何意義---切線法第三十二頁，共51頁。Newton迭代法由于Newton迭代法帶有的導(dǎo)數(shù),使用起來不太方便。為了不求導(dǎo)數(shù)，可用導(dǎo)數(shù)的近似式替代：將它代入（4-26）代替,得第三十三頁，共51頁。則（4-27）（4-27）就是弦截法。由于弦截法采用了導(dǎo)數(shù)的近似值，故在Newton法和弦截法都收斂的情況下，弦截法的收斂階為,低于Newton法，為超線性收斂。第三十四頁，共51頁。

弦截法的幾何意義第三十五頁，共51頁。例4用Newton法和弦截法分別計(jì)算方程在附近的根。解（1）使用Newton法，并?。?-28）第三十六頁，共51頁。迭代3次就得到具有6位有效數(shù)字的結(jié)果。第三十七頁，共51頁。（2）使用弦截法，并取第三十八頁，共51頁。（3）取,使用Newton法計(jì)算方程的根。使用公式（4-28）進(jìn)行迭代計(jì)算后得這個(gè)結(jié)果不但偏離所求的根，而且還看不出它的收斂從中可知，初始值的選取對Newton法是否收斂的性。重要性。第三十九頁，共51頁。4.2.3多根區(qū)間上的逐次逼近法方程在多根區(qū)間上，根的情況主要有兩種：其一，均為單根；其二，有重根。討論如下：一、

是

僅有單根的多根區(qū)間

1）求單根區(qū)間設(shè)在上有個(gè)根。將分成個(gè)小區(qū)間：，（其中）現(xiàn)在分別第四十頁，共51頁。然后計(jì)算的值，由圖3-1可知，當(dāng)時(shí)，在上至少有一個(gè)根。如果有根區(qū)間的個(gè)數(shù)卻為，則所得到的有根區(qū)間就都是單根區(qū)間。如果有根區(qū)間的個(gè)數(shù)小于時(shí)，再將有些小區(qū)間對分，設(shè)對分點(diǎn)為，然后計(jì)算再搜索有根區(qū)間，直到有根區(qū)間的個(gè)數(shù)是為止。第四十一頁，共51頁。2）在單根區(qū)間

上求根

單根區(qū)間上求根的方法在前面已作介紹。在此介紹一種根的搜索法，它可用于求迭代法的初始值，也可用于求的近似根。將區(qū)間對分，設(shè)對分點(diǎn)（即區(qū)間中點(diǎn)）為，計(jì)算，如果與同號，說明方程的根在的右側(cè)，此時(shí)令否則令。不管是那種情況，新的有根區(qū)間為，其長度為原來區(qū)間的一半。第四十二頁，共51頁?？蓪⒑鶇^(qū)間的長度再壓縮一半。如此繼續(xù)可使有根區(qū)間為，其長度為只要足夠大，有根區(qū)間的長度就足夠小，當(dāng)達(dá)到根的精度要求時(shí)，取就可作為根的近似值。這種搜索根的方法稱二分法。用同樣方法下去，第四十三頁，共51頁。第四十四頁，共51頁。如果發(fā)現(xiàn)用二分法求根的過程中，有根區(qū)間趨于零的速度較慢，此時(shí)，可以從某個(gè)區(qū)間開始使用其他迭代法求解，將或作為迭代法的初始值。例6求在[0，8]中的三個(gè)根。解首先將有根區(qū)間[0，3]三等分，得[0,2.7][2.7,5.4][5.4,8]第四十五頁，共51頁。搜索單根區(qū)間：故的三個(gè)根分別在區(qū)間中。用計(jì)算單根的方法，可分別求出三個(gè)區(qū)間上的計(jì)算根。第四十六頁，共51頁。二、

在

上有重根

設(shè)則有此時(shí)在這種情況下，如果，雖然使用Newton法也可以繼續(xù)算下去，但是由于Newton法在定理4.7中的條件不滿足，它的收斂速度可能較慢。事實(shí)上,由是的重根，其中m≥2整數(shù)，第四十七頁，共51頁。則從而得到在這種條件下的Newton法如果收斂，它必是線性收斂的。為了提高收斂的階，可?。?-31）第四十八頁，共51頁。此時(shí)（4-30）變成，從而，故迭代法（3-31）至少是平方收斂的。當(dāng)不知道時(shí)，可采用試探法或其他變形