非線性方程的求根第二章1例

解：根據(jù)阿基米德定律，排出的水質(zhì)量應(yīng)等于球體自身的質(zhì)量：2現(xiàn)代科學(xué)技術(shù)或工程技術(shù)領(lǐng)域的許多實(shí)際問(wèn)題，常常可以歸結(jié)為求解函數(shù)方程：如果函數(shù)能寫成如下形式如果有使得，則稱

為方程的根，或稱為函數(shù)的零點(diǎn)。3如：①當(dāng)f(x)為代數(shù)方程時(shí)，理論上已經(jīng)證明，大于五次的多項(xiàng)式一般沒(méi)有代數(shù)解法。②當(dāng)f(x)為超越方程時(shí)，一般不能用代數(shù)方法求其根。

所以，超越方程(含有指數(shù)和對(duì)數(shù)等)代數(shù)方程（多項(xiàng)式）對(duì)于一般的非線性方程，只能用數(shù)值方法求解。4方程求根的問(wèn)題分成兩步：第二步：根的隔離確定根所在的區(qū)間，使方程在這個(gè)小區(qū)間內(nèi)僅有一個(gè)根，該區(qū)間叫隔根區(qū)間。第三步：根的精確化已知根的一個(gè)近似值后，用某種方法對(duì)其進(jìn)行加工，使之滿足給定的精度要求。第一步：根的存在性5求隔根區(qū)間的一般方法理論依據(jù)：6本章主要介紹二分法與迭代法（包括Newton迭代法及其變型、弦割法等）§1.二分法二分法是方程求根最常用而且也是最保險(xiǎn)的方法之一。一、算法的基本思想將區(qū)間對(duì)分，保留有根的區(qū)間，舍去無(wú)根的區(qū)間。如此往復(fù)，以逐步逼近方程的根?；緱l件：7二、算法的步驟8ax0ba1b1三、算法的收斂性此時(shí)有誤差估計(jì)：常用來(lái)估計(jì)k的值9四、算法的優(yōu)點(diǎn)與缺點(diǎn)缺點(diǎn)：不能求偶數(shù)重根及復(fù)根；收斂速度非常緩慢，與以1/2為公比的等比級(jí)數(shù)相同；沒(méi)有充分利用函數(shù)值。因此一般不單獨(dú)使用，但往往可以為其它快速方法提供初值。優(yōu)點(diǎn)：計(jì)算簡(jiǎn)單且必收斂，是一種可靠的算法；對(duì)函數(shù)性質(zhì)要求低，只要求函數(shù)f(x)連續(xù)就可以了。用二分法求方程

在[1,1.5]內(nèi)的實(shí)根，要求

解即可推出所需的迭代次數(shù)滿足

在區(qū)間[1,1.5]上至少存在一個(gè)根。其具體過(guò)程如下：

例2.1.1由于因而由誤差估計(jì)式1011例2.1.2解即可推出所需的迭代次數(shù)滿足因而函數(shù)在區(qū)間[1,2]上存在惟一的零點(diǎn)。

由于以及由誤差估計(jì)式12二分法的一種修正是試位法。在二分法中，原來(lái)區(qū)間的中點(diǎn)為新的區(qū)間的一個(gè)端點(diǎn)。因此，每迭代一步，區(qū)間的長(zhǎng)度均減半。在試位法中，不用中點(diǎn)，而用過(guò)點(diǎn)與的直線的零點(diǎn)作為新區(qū)間的一個(gè)端點(diǎn)。在實(shí)際計(jì)算中，試位法比二分法往往收斂得要快。在試位法的每一步計(jì)算中，有13§2.非線性方程求解的迭代法等價(jià)變換迭代法是一種逐步逼近的方法:首先給出一個(gè)粗糙的初值，反復(fù)利用同一個(gè)迭代公式，逐步逼近精確解。

用迭代法求方程根的基本步驟如下：第一步：化為同解方程14第二步：產(chǎn)生迭代序列先建立適當(dāng)?shù)牡袷剑豪蒙鲜龈袷娇僧a(chǎn)生一列數(shù)：第三步：取極限一定收斂嗎？15在直角坐標(biāo)系中同時(shí)作和兩條曲線，如圖所示，則這兩條曲線的交點(diǎn)的橫坐標(biāo)就是方程的根，也就是的根。迭代格式由求，相當(dāng)于過(guò)曲線上作水平線與直線相交，過(guò)交點(diǎn)作x軸的垂線，此時(shí)垂足至原點(diǎn)距離等于，故垂足橫坐標(biāo)為。

迭代法的幾何解釋：16由上圖可見(jiàn)，曲線斜率時(shí)迭代序列收斂，且越小收斂越快；反之，若，則迭代序列發(fā)散。xyy=xxyy=xx0p0x1p1x0p0x1p117例2.2.1解18下面給出簡(jiǎn)單迭代法的一個(gè)收斂性定理。Lipschitz條件保證迭代不中斷，連續(xù)時(shí)保證有解壓縮映像19①存在唯一性證明做輔助函數(shù)，則有所以，存在點(diǎn)若又有，則有所以②收斂性任取初值則所以，任意的初值都收斂。20③誤差估計(jì)證畢21222324例2.2.3解也可化為等價(jià)方程.但此時(shí)定理?xiàng)l件不成立，迭代序列不能保證收斂。25例2.2.4解26由于定理中條件(1)一般難于驗(yàn)證，而且在大區(qū)間上，這些條件也不一定都成立。所以實(shí)際使用迭代法總是在根的鄰近進(jìn)行。表明收斂性與初值的選擇有關(guān)！27

實(shí)際用迭代法計(jì)算時(shí)，先用二分法求得較好的初值，然后再進(jìn)行迭代。28性質(zhì)

1.若方程x=(x)在處有根，則當(dāng)|'()|<1且'(x)在x=的某鄰域內(nèi)連續(xù)時(shí)，簡(jiǎn)單迭代法必在x=的某鄰域內(nèi)收斂；

2.若'(x)在某閉區(qū)間上連續(xù)且|'(x)|1，則方程x=(x)用相應(yīng)的簡(jiǎn)單迭代法所得點(diǎn)列必定發(fā)散。29證明：只需證2.用反證法：若簡(jiǎn)單迭代法所得點(diǎn)列{xn}收斂到，易知x=為方程x=(x)的根。但由于這說(shuō)明隨著n的增加，點(diǎn)列xn越來(lái)越遠(yuǎn)離，故{xn}不可能收斂到，矛盾！前面定理所涉及的收斂性，即在根鄰域的收斂性稱為局部收斂性，具有局部收斂性質(zhì)的迭代法通常對(duì)初值的要求較高，使用起來(lái)不太方便。因而，人們通常希望迭代算法對(duì)相對(duì)大的范圍的初始點(diǎn)具有收斂性，這種收斂性稱為全局收斂性。構(gòu)造迭代法，人們自然希望迭代算法不僅收斂，而且收斂快，即所謂收斂的速度。30定義2.2.1

設(shè)迭代過(guò)程收斂于的根.如果迭代誤差滿足下列關(guān)系則稱該迭代序列是p

階收斂的(時(shí)要求)。

迭代法收斂的階當(dāng)p=1時(shí)，稱為線性收斂；當(dāng)p>1時(shí)，稱為超線性收斂；當(dāng)p=2時(shí)，稱為平方收斂或二次收斂。顯然，迭代序列的收斂階越高，它的收斂速度就越快。31因?yàn)?，由?2

在實(shí)際使用中收斂的階有時(shí)很難直接確定，常常采用一些其它的方法來(lái)確定收斂的階。使用Taylor展開式是一種常用的方法。如果在根處充分光滑(各階導(dǎo)數(shù)存在)，則可對(duì)在處進(jìn)行Taylor展開，得33上式說(shuō)明迭代法為p階收斂的。34補(bǔ)充35例2.2.6建立的迭代法至少是平方收斂的。證明根據(jù)上述定理，只需證明因?yàn)楣试摰ㄖ辽偈瞧椒绞諗康摹ewton迭代法36

迭代法的加速37令新的迭代函數(shù)為構(gòu)造加速迭代序列即38

迭代法的埃特金加速法3940則41(1).

k=0，1，2，…埃特金迭代格式可改寫成：(2).

其中迭代函數(shù)42

小結(jié)43§3.Newton迭代法及其簡(jiǎn)單變形用迭代法解非線性方程時(shí)，如何構(gòu)造迭代函數(shù)是非常重要的，那么怎樣構(gòu)造的迭代函數(shù)才能保證迭代法收斂呢？一、Newton迭代法將非線性方程線性化，以線性方程的解逐步逼近非線性方程的解。

基本思想非線性問(wèn)題的最簡(jiǎn)單解法是線性近似！44

迭代格式45上述格式稱為Newton迭代格式。這樣一直下去，可以得到一列迭代序列，其迭代格式為：類似地，同樣可以得到46幾何意義xyNewton迭代法又稱為切線法切線

原來(lái)是以直線代替曲線的近似方法啊!47

局部收斂性484950改進(jìn)：則至少是二階收斂的。51缺點(diǎn)：對(duì)初值要求較高，計(jì)算量較大。優(yōu)點(diǎn)：收斂速度快，精度高，格式簡(jiǎn)單，應(yīng)用廣泛。

優(yōu)點(diǎn)與缺點(diǎn)

52下圖表明Newton法收斂性依賴于初值x0

的選取。x0x0x0總之，Newton法具有收斂快，穩(wěn)定性好，精度高等優(yōu)點(diǎn)，是求解非線性方程的有效方法之一。但它每次迭代均需計(jì)算函數(shù)值與導(dǎo)數(shù)值，故計(jì)算量較大。而且當(dāng)導(dǎo)數(shù)值提供有困難時(shí)，Newton法無(wú)法進(jìn)行。此外，由于它是局部收斂的，因而對(duì)初值要求較高，只有初值選得充分靠近根時(shí)，才能保證序列收斂。53注1：使用牛頓迭代法存在從一個(gè)根跳到另一個(gè)根的情況。注2：如果f(x)=0沒(méi)有實(shí)根，則牛頓迭代序列不收斂。54例2.3.1

用Newton法解方程f(x)=x(x+1)2-1=0在0.4附近的根。解將函數(shù)f(x)求導(dǎo)，得到k0123xk0.40.470130.465390.46537所以，取根為0.4654.55

全局收斂性定理2.3.2

保證了根的存在性

函數(shù)單調(diào)，根唯一函數(shù)圖形的凸向不變56例2.3.2解57

Newton迭代法的計(jì)算步驟58

程序框圖終止準(zhǔn)則：59例2.3.3解根據(jù)全局收斂性定理，對(duì)任何滿足上述Newton迭代產(chǎn)生的迭代序列均收斂于60二、簡(jiǎn)化Newton法此格式稱為簡(jiǎn)化Newton迭代。迭代函數(shù)為

迭代格式61

幾何意義62此格式稱為推廣的簡(jiǎn)化Newton迭代。迭代格式為

進(jìn)一步簡(jiǎn)化由簡(jiǎn)單迭代的局部收斂條件

收斂性與收斂速度63得64推廣的簡(jiǎn)化Newton法收斂時(shí)，因?yàn)樗?，推廣的簡(jiǎn)化Newton法只有線性收斂速度。65三、下山Newton迭代在Newton迭代法中，若函數(shù)較復(fù)雜，初值的選取較困難時(shí)，為防止迭代發(fā)散，可改用如下的迭代式，以擴(kuò)大初值的選取范圍：成立，上述迭代方法稱為下山Newton法。66終止準(zhǔn)則：67例2.3.5解68四、弦割法

迭代格式由上式定義的迭代算法稱為弦割法，也稱為割線法。為什么稱為弦割法？是從它的幾何意義而言。69

幾何意義切線

割線

還是以直線代替曲線的近似方法啊!70

收斂性與收斂速度71例2.3.6解兩步方法

72

弦割法的計(jì)算步驟73例2.3.7解取x0=1,x1=2,代入公式，計(jì)算結(jié)果如下表所示。kxkf(xk)01-112521.166666667-0.5787036931.253112023-0.2853630241.3372064440.05388057951.323850096-0.003698116861.324707936-4.273521*10E-571.3247179653.79*10E-87