第2章非線性方程求根

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

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

為方程的根，或稱為函數的零點。3如：①當f(x)為代數方程時，理論上已經證明，大于五次的多項式一般沒有代數解法。②當f(x)為超越方程時，一般不能用代數方法求其根。

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

在[1,1.5]內的實根，要求

解即可推出所需的迭代次數滿足

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

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

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

用迭代法求方程根的基本步驟如下：第一步：化為同解方程14第二步：產生迭代序列先建立適當的迭代格式：利用上述格式可產生一列數：第三步：取極限一定收斂嗎？15在直角坐標系中同時作和兩條曲線，如圖所示，則這兩條曲線的交點的橫坐標就是方程的根，也就是的根。迭代格式由求，相當于過曲線上作水平線與直線相交，過交點作x軸的垂線，此時垂足至原點距離等于，故垂足橫坐標為。

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

實際用迭代法計算時，先用二分法求得較好的初值，然后再進行迭代。28性質

1.若方程x=(x)在處有根，則當|'()|<1且'(x)在x=的某鄰域內連續(xù)時，簡單迭代法必在x=的某鄰域內收斂；

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

設迭代過程收斂于的根.如果迭代誤差滿足下列關系則稱該迭代序列是p

階收斂的(時要求)。

迭代法收斂的階當p=1時，稱為線性收斂；當p>1時，稱為超線性收斂；當p=2時，稱為平方收斂或二次收斂。顯然，迭代序列的收斂階越高，它的收斂速度就越快。31因為，由得32

在實際使用中收斂的階有時很難直接確定，常常采用一些其它的方法來確定收斂的階。使用Taylor展開式是一種常用的方法。如果在根處充分光滑(各階導數存在)，則可對在處進行Taylor展開，得33上式說明迭代法為p階收斂的。34補充35例2.2.6建立的迭代法至少是平方收斂的。證明根據上述定理，只需證明因為故該迭代法至少是平方收斂的。Newton迭代法36

迭代法的加速37令新的迭代函數為構造加速迭代序列即38

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

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

其中迭代函數42

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

基本思想非線性問題的最簡單解法是線性近似！44

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

原來是以直線代替曲線的近似方法啊!47

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

優(yōu)點與缺點

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

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

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

全局收斂性定理2.3.2

保證了根的存在性

函數單調，根唯一函數圖形的凸向不變56例2.3.2解57

Newton迭代法的計算步驟58

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

迭代格式61

幾何意義62此格式稱為推廣的簡化Newton迭代。迭代格式為

進一步簡化由簡單迭代的局部收斂條件

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

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

幾何意義切線

割線

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

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

72

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