第7章 非線性方程求根,7.1 方程求根與二分法 7.2 迭代法及其收斂性 7.3 迭代收斂的加速方法 7.4 牛頓法 7.5 弦截法與拋物線法 7.6 解非線性方程組的牛頓迭代法,7.1 方程求根與二分法,例如代數(shù)方程 x5-x3+24x+1=0, 超越方程 sin(5x2)+e-x=0.,對(duì)于不高于4次的代數(shù)方程已有求根公式，而高于4次的代數(shù)方程則無(wú)精確的求根公式，至于超越方程 就更無(wú)法求出其精確的解，因此，如何求得滿足一定精度要求的方程的近似根也就成為迫切需要解決的問(wèn)題，為此，本章介紹幾種常見(jiàn)的非線性方程的近似求根方法.,7.1.1 引言,本章主要討論單變量非線性方程,f(x)=0 (1.1),的求根問(wèn)題，這里xR, f(x)Ca, b. 在科學(xué)與工程計(jì)算中有大量方程求根問(wèn)題，其中一類特殊的問(wèn)題是多項(xiàng)式方程,其中系數(shù)ai(i=0,1,n)為實(shí)數(shù).,方程f(x)=0的根x*，又稱為函數(shù)f(x)的零點(diǎn)，它使得f(x*)=0，若f(x)可分解為,f(x)=(x-x*)mg(x)，,其中m為正整數(shù)，且g(x*)0. 當(dāng)m=1時(shí)，則稱x*為單根，若m1稱x*為(1.1)的m重根，或x*為函數(shù)f(x)的m重零點(diǎn). 若x*是f(x)的m重零點(diǎn)，且g(x)充分光滑，則,當(dāng)f(x)為代數(shù)多項(xiàng)式(1.2)時(shí)，根據(jù)代數(shù)基本定理可知，n次代數(shù)方程f(x)=0在復(fù)數(shù)域有且只有n個(gè)根(含復(fù)根，m重根為m個(gè)根).,n=1,2時(shí)方程的根是大家熟悉的，n=3,4時(shí)雖有求根公式但比較復(fù)雜，可在數(shù)學(xué)手冊(cè)中查到，但已不適合數(shù)值計(jì)算，而n5時(shí)就不能用公式表示方程的根.因此，通常對(duì)n3的多項(xiàng)式方程求根與一般連續(xù)函數(shù)方程(1.1)一樣都可采用迭代法求根.,迭代法要求給出根x*的一個(gè)近似，若f(x)Ca, b且f(a)f(b)0，根據(jù)連續(xù)函數(shù)性質(zhì)中的介值定理可知方程f(x)=0在(a, b)內(nèi)至少有一個(gè)實(shí)根，這時(shí)稱a, b為方程(1.1)的有根區(qū)間，通?？赏ㄟ^(guò)逐次搜索法求得方程(1.1)的有根區(qū)間.,若 f(x)在a,b內(nèi)連續(xù), 且 f(a) f(b)0, 則 f(x)=0 在a,b內(nèi)必有根; 若f(x)在a,b內(nèi)還嚴(yán)格單調(diào), 則f(x)=0在a,b內(nèi)只有一根, 據(jù)此可得求隔根區(qū)間的兩種方法.,1. (描)做圖法,畫出 y=f(x) 的草圖, 由f(x)與橫軸交點(diǎn)的大概位置來(lái)確定隔根區(qū)間; 或者利用導(dǎo)函數(shù)f(x)的正、負(fù)與函數(shù)f(x)的單調(diào)性的關(guān)系確定根的大概位置.,求隔根區(qū)間的一般方法,若f(x)比較復(fù)雜, 還可將方程f(x)=0化為一個(gè)等價(jià)方程(x)=(x), 則曲線y=(x)與y=(x)之交點(diǎn)A(x*,y*)的橫坐標(biāo) x*即為原方程之根, 據(jù)此也可通過(guò)作圖求得x*的隔根區(qū)間.,例1 判別下列方程有幾個(gè)實(shí)根，并求隔根區(qū)間. (1) f(x)=x3-x-1=0, (2) f(x)=x4-4x3+1=0.,解 (1)將方程變形為 x3=x+1 繪曲線圖 y=x3 及 y=x+1 由圖可知, 方程只有一個(gè)實(shí)根x*(1, 1.5)，所以(1, 1.5) 即為其隔根區(qū)間.,(2) 方程 f(x)=x4-4x3+1=0.,由f(x)= 4x2(x-3)=0 得駐點(diǎn)x1=0, x2=3. 該二點(diǎn)將實(shí)軸分為三個(gè)區(qū)間: (-, 0), (0, 3)，(3, +),f(x)在此三個(gè)區(qū)間上的符號(hào)分別為“-”、“-”、“+”, 又知 f(-)0, f(0)=10, f(3)=-260.,可見(jiàn)f(x)僅有兩個(gè)實(shí)根, 分別位于(0, 3), (3, +), 又f(4)=10, 所以第二根的隔根區(qū)間可縮小為(3, 4).,以上分析可用下表表示,2. 逐步搜索法,從區(qū)間a, b的左端點(diǎn) a 出發(fā), 按選定的步長(zhǎng)h 一步步向右搜索，若,f(a+jh)f(a+(j+1)h)0 (j=0,1,2,),則區(qū)間a+jh, a+(j+1)h內(nèi)必有根. 搜索過(guò)程也可從b開(kāi)始，這時(shí)應(yīng)取步長(zhǎng) h0.,7.1.2 二分法,設(shè)f(x)在區(qū)間a, b上連續(xù), f(a)f(b)0, 則在a, b,內(nèi)有方程的根. 取a, b的中點(diǎn),將區(qū)間一分為二. 若 f (x0)=0, 則x0就是方程的根, 否則判別根 x*在 x0 的左側(cè)還是右側(cè).,若f(a) f(x0)0, 則x*(a, x0), 令 a1= a, b1=x0;,若f(x0) f(b)0, 則x*(x0 , b), 令 a1=x0, b1=b.,不論出現(xiàn)哪種情況, (a1, b1)均為新的有根區(qū)間, 它的長(zhǎng)度只有原有根區(qū)間長(zhǎng)度的一半, 達(dá)到了壓縮有根區(qū)間的目的.,對(duì)壓縮了的有根區(qū)間, 又可實(shí)行同樣的步驟, 再壓縮. 如此反復(fù)進(jìn)行, 即可的一系列有根區(qū)間套,由于每一區(qū)間都是前一區(qū)間的一半，因此區(qū)間an , bn的長(zhǎng)度為,若每次二分時(shí)所取區(qū)間中點(diǎn)都不是根，則上述過(guò)程將無(wú)限進(jìn)行下去. 當(dāng) n 時(shí)，區(qū)間必將最終收縮為一點(diǎn)x* ，顯然x*就是所求的根.,若取區(qū)間an , bn的中點(diǎn),作為x*的近似值，則有下述誤差估計(jì)式,只要 n 足夠大, (即區(qū)間二分次數(shù)足夠多)，誤差就可足夠小.,由于在偶重根附近曲線 y=f(x) 為上凹或下凸, 即 f(a)與f(b)的符號(hào)相同, 因此不能用二分法求偶重根.,例2 用二分法求例1中方程 f(x)=x3-x-1=0的實(shí)根,要求誤差不超過(guò)0.005.,解 由例1可知x*(1, 1.5), 要想滿足題意，即：,則要,|x*-xn|0.005,由此解得 取n=6, 按二分法計(jì)算過(guò)程見(jiàn)下表, x6 = 1.3242 為所求之近似根.,二分法的優(yōu)點(diǎn)是算法簡(jiǎn)單，且總是收斂的，缺點(diǎn)是收斂的太慢，故一般不單獨(dú)將其用于求根，只是用其為根求得一個(gè)較好的近似值.,二分法的計(jì)算步驟:,步驟1 準(zhǔn)備 計(jì)算函數(shù)f(x)在區(qū)間a, b端點(diǎn)處的值f(a), f(b).,若f(a)f(a+b)/2)0, 則以(a+b)/2代替b ，否則以(a+b)/2代替a.,步驟2 二分 計(jì)算函數(shù)f(x)在區(qū)間中點(diǎn)(a+b)/2處的值f(a+b)/2).,步驟3 判斷 若f(a+b)/2)=0，則(a+b)/2即是根，計(jì)算過(guò)程結(jié)束，否則檢驗(yàn).,反復(fù)執(zhí)行步驟2和步驟3，直到區(qū)間a, b長(zhǎng)度小于允許誤差，此時(shí)中點(diǎn)(a+b)/2即為所求近似根.,7.2 迭代法及其收斂性,7.2.1 不動(dòng)點(diǎn)迭代法,將方程f(x)=0改寫為等價(jià)方程形式,x=(x). (2.1),若要求x*滿足f(x*)=0，則x*=(x*)；反之亦然，稱x*為函數(shù)(x)的一個(gè)不動(dòng)點(diǎn). 求f(x)的零點(diǎn)就等于求(x)的不動(dòng)點(diǎn)，選擇一個(gè)初始近似值x0，將它代入(2.1)右端，即可求得,x1=(x0).,可以如此反復(fù)迭代計(jì)算,xk+1=(xk) (k=0,1,2,). (2.2),(x)稱為迭代函數(shù). 如果對(duì)任何x0a, b，由(2.2)得到的序列xk有極限,則稱迭代方程(2.2)收斂. 且x*=(x*)為(x)的不動(dòng)點(diǎn)，故稱(2.2)為不動(dòng)點(diǎn)迭代法.,上述迭代法是一種逐次逼近法，其基本思想是將隱式方程(2.1)歸結(jié)為一組顯式的計(jì)算公式(2.2)，迭代過(guò)程實(shí)質(zhì)上是一個(gè)逐步顯式化過(guò)程.,當(dāng)(x)連續(xù)時(shí)，顯然x*就是方程x=(x)之根(不動(dòng)點(diǎn)). 于是可以從數(shù)列xk中求得滿足精度要求的近似根. 這種求根方法稱為不動(dòng)點(diǎn)迭代法,稱為迭代格式, (x)稱為迭代函數(shù), x0 稱為迭代初值,數(shù)列xk稱為迭代序列. 如果迭代序列收斂, 則稱迭代格式收斂,否則稱為發(fā)散. （幾何意義的解釋見(jiàn)書p265頁(yè)）,分別按以上三種形式建立迭代公式，并取x0=1進(jìn)行迭代計(jì)算，結(jié)果如下：,解 對(duì)方程進(jìn)行如下三種變形：,例3 用迭代法求方程x4+2x2-x-3=0 在區(qū)間1, 1.2內(nèi)的實(shí)根.,準(zhǔn)確根 x* = 1.124123029, 可見(jiàn)迭代公式不同, 收斂情況也不同. 第二種公式比第一種公式收斂快得多, 而第三種公式不收斂.,參見(jiàn)書p266頁(yè)-例3.,例3表明原方程化為(2.1)的形式不同，有的收斂，有的不收斂，有的發(fā)散，只有收斂的的迭代過(guò)程(2.2)才有意義，為此我們首先要研究(x)的不定點(diǎn)的存在性及迭代法(2.2)的收斂性.,7.2.2 不動(dòng)點(diǎn)的存在性與迭代法的收斂性,首先考察(x)在a, b上不動(dòng)點(diǎn)的存在唯一性.,定理1 設(shè)(x)Ca, b滿足以下兩個(gè)條件：,1 對(duì)任意xa, b有a(x)b.,2 存在正數(shù)L1，使對(duì)任意x,ya, b都有,則(x)在a, b上存在唯一的不動(dòng)點(diǎn)x*.,證明 先證不動(dòng)點(diǎn)的存在性. 若(a)=a或(b)=b，顯然(x)在a, b上存在不動(dòng)點(diǎn). 因?yàn)閍(x)b，以下設(shè)(a)a及(b)b定義函數(shù),顯然f(x)Ca, b,且滿足f(a)=(a)-a0, f(b)=(b)-b0, 由連續(xù)函數(shù)性質(zhì)可知存在 x*(a, b) 使 f(x*)=0，即x*=(x*)，x*即為(x)的不動(dòng)點(diǎn).,再證不動(dòng)點(diǎn)的唯一性. 設(shè)x1*, x2*a, b都是(x)的不動(dòng)點(diǎn)，則由(2.4)得,引出矛盾，故(x)的不動(dòng)點(diǎn)只能是唯一的. 證畢.,在(x)的不動(dòng)點(diǎn)存在唯一的情況下，可得到迭代法(2.2)收斂的一個(gè)充分條件.,定理2 設(shè)(x)Ca, b滿足定理1中的兩個(gè)條件，則對(duì)任意x0a, b，由(2.2)得到的迭代序列xk收斂到的不動(dòng)點(diǎn)x*，并有誤差估計(jì)式,證明 設(shè)x*a, b是(x)在a, b上的唯一不動(dòng)點(diǎn),由條件1，可知xka, b，再由(2.4)得,因0L1，故當(dāng)k時(shí)序列xk收斂到x*.,下面證明估計(jì)式(2.5)，由(2.4)有,于是對(duì)任意正整數(shù)p有,上述令p, 注意到limxk+p=x* (p)即得(2.5)式.,又由于對(duì)任意正整數(shù)p有,上述令p, 及l(fā)imxk+p=x* (p)即得(2.6)式. 證畢.,迭代過(guò)程是個(gè)極限過(guò)程. 在用迭代法進(jìn)行時(shí)，必須按精度要求控制迭代次數(shù). 誤差估計(jì)式(2.5)原則上確定迭代次數(shù)，但它由于含有信息L而不便于實(shí)際應(yīng)用. 而誤差估計(jì)式(2.6)是實(shí)用的，只要相鄰兩次計(jì)算結(jié)果的偏差足夠小即可保證近似值xk具有足夠精度.,對(duì)定理1和定理2中的條件2可以改為導(dǎo)數(shù)，即在使用時(shí)如果(x)Ca, b且對(duì)任意xa, b有,則由微分中值定理可知對(duì)任意x, ya, b有,故定理中的條件2是成立的. 見(jiàn)書p269.,例如，在前面例3中采用的三種迭代公式，在隔根區(qū)間(1, 1.2)內(nèi)，有,故前兩個(gè)迭代公式收斂，第三個(gè)迭代公式不收斂.,7.2.3 局部收斂性與收斂階,上面給出了迭代序列xk在區(qū)間a, b上的收斂性,通常稱為全局收斂性. 有時(shí)不易檢驗(yàn)定理的條件，實(shí)際應(yīng)用時(shí)通常只在不動(dòng)點(diǎn)x*的鄰近考察其收斂性，即局部收斂性.,定義1 設(shè)(x)有不動(dòng)點(diǎn)x*，如果存在x*的某個(gè)鄰域R: |x-x*|，對(duì)任意x0R，迭代公式(2.2)產(chǎn)生的序列xkR，且收斂到x*，則稱迭代法(2.2)局部收斂.,定理3 設(shè)x*為(x)的不動(dòng)點(diǎn)， 在x*的某個(gè)鄰域連續(xù)，且 ，則迭代法(2.2)局部收斂.,證明 由連續(xù)函數(shù)的性質(zhì)，存在不動(dòng)點(diǎn)x*的某個(gè)鄰域R: |x-x*|，使對(duì)于任意xR成立,此外，對(duì)于任意xR，總有(x)R，這時(shí)因?yàn)?于是依據(jù)定理2可以斷定迭代過(guò)程xk+1=(xk)對(duì)于任意初值x0R均收斂. 證畢.,例4 用不同迭代法求方程x2-3=0的根 .,解 這里f(x)= x2-3，可以改寫為各種不同的等價(jià)形式x=(x)，其不動(dòng)點(diǎn)為 ，由此構(gòu)造不同的迭代法.,取x0=2, 對(duì)上式4種迭代法, 計(jì)算三步所得結(jié)果入下表.,注意 ，從計(jì)算結(jié)果看到迭代法(1)及(2)均不收斂，且它們均不滿足定理3中的局部收斂條件，迭代法(3)和(4)均滿足局部收斂條件，且迭代法(4)比(3)收斂快，因在迭代法(4)中(x*)=0. 為了衡量迭代法(2.2)收斂速度的快慢可給出以下定義.,定義2 設(shè)迭代過(guò)程xk+1=(xk)收斂于方程x=(x)的根x*，如果迭代誤差ek=xk-x*當(dāng)k時(shí)成立下列漸近關(guān)系式,則稱該迭代法是p階收斂的. 特別地，p=1時(shí)稱線性收斂，p1時(shí)稱超線性收斂，p=2時(shí)稱平方收斂.,定理4 對(duì)于迭代過(guò)程xk+1=(xk)，如果(p)(x)在所求根x*的鄰近連續(xù)，并且,則該迭代過(guò)程在x*的鄰近是p階收斂的.,證明 由于(x*)=0，根據(jù)定理3立即可以斷定迭代過(guò)程xk+1=(xk)具有局部收斂性.,再將(xk)在根x*處做泰勒展開(kāi), 利用條件(2.4), 則有,注意到(xk)=xk+1，(x*)= x*，由上式得,因此對(duì)迭代誤差，令k時(shí)有,這表明迭代過(guò)程xk+1=(xk)確實(shí)為p階收斂. 證畢.,上述定理告訴我們，迭代過(guò)程的收斂速度依賴于迭代函數(shù)(x)的選取. 如果xa, b但(x)0時(shí)，則該迭代過(guò)程只可能是線性收斂.,對(duì)例4的討論見(jiàn)書p272.,的三階方法. 假設(shè) x0 充分靠近 x*, 求,證明 首先由泰勒展式可得,例子 證明迭代公式 xk+1=xk(xk2+3a)/(3xk2+a)是求,而1/4a0，故此迭代公式是三階方法.,7.3 迭代收斂的加速方法,7.3.1 埃特金加速收斂方法,對(duì)于收斂的迭代過(guò)程，只要迭代足夠多次，就可以使結(jié)果達(dá)到任意的精度，但是有時(shí)迭代過(guò)程收斂較慢，從而使計(jì)算量變得很大，因此迭代過(guò)程的加速是個(gè)重要的課題.,設(shè)x0是根x*的某個(gè)近似值, 用迭代公式校正一次得,x1=(x0),而由微分中值定理，有,假設(shè)(x)改變不大, 近似地取某個(gè)近似值L, 則有,由于 x2-x*L(x1-x*).,若將校正值x1=(x0)再校正一次，又得,x2=(x1),將它與(3.1)式聯(lián)立，消去未知的L，有,由此推知,在計(jì)算了x1及x2之后，可用上式右端作為x*的新近似,記作x1，一般情形是由xk計(jì)算xk+1, xk+2，記,它表明序列xk的收斂速度比xk的收斂速度快.,(3.1)式稱為埃特金(Aitken) 2加速方法.,可以證明,也稱為埃特金 ( Aitken ) 外推法. 可以證明:,為線性收斂,則埃特金法為平方收斂；,這個(gè)加速迭代法也可寫成下面格式,若,為 p ( p 1)階收斂，,導(dǎo)數(shù)連續(xù)，則埃特金法為 2p1 階收斂.,的 p 階,若,例題 求方程 x = e x 在 x=0.5 附近的根.,解 取 x0=0.5, 迭代格式,x25=x26=0.5671433,若對(duì)此格式用埃特金法, 則,得,仍取 x0=0.5 , 得,由此可見(jiàn), 埃特金法加速收斂效果是相當(dāng)顯著的.,7.3.2 斯蒂芬森(Steffensen)迭代法,埃特金方法不管原序列xk是怎樣產(chǎn)生的，對(duì)xk進(jìn)行加速計(jì)算，得到序列xk. 如果把埃特金加速技巧與不定點(diǎn)迭代結(jié)合，則可得到如下的迭代法：,稱為斯蒂芬森(Steffensen)迭代法. 它可以這樣理解，我們要求x=(x)的根x*，令誤差(x)=(x)-x，有等式(x*)=(x*)-x*=0，已知x*的近似值xk及yk，其誤差分別為,把誤差(x)“外推到零”，即過(guò)(xk,(xk)及(yk,(yk)兩點(diǎn)做線性插值函數(shù)，它與x軸交點(diǎn)就是(3.3)中的xk+1，即方程,的解,實(shí)際上(3.3)是將不定點(diǎn)迭代法(2.2)計(jì)算兩步合并成一步得到的，可將它寫成另一種不動(dòng)點(diǎn)迭代,其中,對(duì)不動(dòng)點(diǎn)迭代(3.5)有以下局部收斂性定理.,定理5 若x*為(3.5)定義的迭代函數(shù)(x)的不動(dòng)點(diǎn)，則x*為(x)的不定點(diǎn). 反之，若x*為(x)的不動(dòng)點(diǎn)，設(shè)(x)存在，(x)1，則x*是(x)的不動(dòng)點(diǎn)，且斯蒂芬森迭代法(3.3)是2階收斂的.,證明可見(jiàn)2.,例5 見(jiàn)書p274.,例6 見(jiàn)書p275.,7.4 牛 頓 法,7.4.1 牛頓法及其收斂性,對(duì)于方程f(x)=0，如果f(x)是線性函數(shù)，則它的求根是容易的. 牛頓法實(shí)質(zhì)上是一種線性化方法，其基本思想是將非線性方程f(x)=0逐步歸結(jié)為某種線性方程來(lái)求解.,設(shè)已知方程f(x)=0有近似根x0，且在 x0附近f(x)可用一階泰勒多項(xiàng)式近似，表示為,當(dāng)f(x0)0時(shí)，方程f(x)=0可用線性方程(切線) 近似代替，即,f(x0)+f(x0)(x-x0)=0. (4.1),解此線性方程得,得迭代公式,此式稱為牛頓(Newton)迭代公式.,牛頓法有顯然的幾何意義，方程f(x)=0的根x*可解釋為曲線y=f(x)與x軸交點(diǎn)的橫坐標(biāo). 設(shè)xk是根x*的某個(gè)近似值，過(guò)曲線y=f(x)上橫坐標(biāo)為xk的點(diǎn)Pk引切線，并將該切線與x軸交點(diǎn)的橫坐標(biāo)xk+1作為x*的新的近似值. 注意到切線方程為,這樣求得的值xk+1必滿足(4.1), 從而就是牛頓公式(4.2)的計(jì)算結(jié)果. 由于這種幾何背景，所以牛頓迭代法也稱切線法.,y=f(x),xk+1,Pk,Pk+1,xk+2,牛頓迭代法的收斂性,設(shè)x*是f(x)的一個(gè)單根，即f(x*)=0，f(x*)0, 有,牛頓迭代法的迭代函數(shù)為,由定理4的(2.9)式可得 (4.3)式,由此得到，當(dāng)x*為單根時(shí)，牛頓迭代法在根x*的鄰近是二階(平方)收斂的.,關(guān)于x*為重根時(shí)，牛頓迭代法在根x*的鄰近的收斂性在后面討論.,定理(局部收斂性) 設(shè)fC2a, b, 若x*為f(x)在a, b上的根，且f(x*)0，則存在x*的鄰域U, 使得任取初值x0U，牛頓法產(chǎn)生的序列xk收斂到x*，且滿足,即有下面的局部收斂性定理.,解 將原方程化為xex= 0，則,牛頓迭代公式為,取 x0=0.5，迭代得,x1=0.566311, x2=0.5671431, x3=0.5671433.,f(x)=xex， f(x)=1+ex，,例7 用牛頓迭代法求方程x=ex在x=0.5附近的根.,參見(jiàn)書p277的例7.,牛頓法的計(jì)算步驟 見(jiàn)書p278.,7.4.2 牛頓法應(yīng)用舉例,對(duì)于給定的正數(shù)C，應(yīng)用牛頓法解二次方程,我們現(xiàn)在證明，這種迭代公式對(duì)于任意初值x00都是收斂的.,可導(dǎo)出求開(kāi)方值 的計(jì)算程序,事實(shí)上，對(duì)(4.5)式施行配方整理，易知,以上兩式相除得,據(jù)此反復(fù)遞推有,記,整理(4.6)式，得,對(duì)任意初值x00，總有|q|1，故由上式推知，當(dāng)k時(shí) ，即迭代過(guò)程恒收斂.,參見(jiàn)書p279的例8.,7.4.3 簡(jiǎn)化牛頓法與牛頓下山法,牛頓法的優(yōu)點(diǎn)是收斂快，缺點(diǎn)每步迭代要計(jì)算f(xk)及f(xk)，計(jì)算量較大，且有時(shí)f(xk)計(jì)算較困難；初始近似值x0只在根x*附近才能保證收斂，如x0給的不合適可能不收斂. 為克服這兩個(gè)缺點(diǎn)，通?？捎孟率龇椒?,(1) 簡(jiǎn)化牛頓法，也稱平行弦法，其迭代公式為,迭代函數(shù)為 (x)=x-Cf(x).,若|(xk)|=|1-Cf(x)|1，即取0Cf(x)2. 在根x*附近成立，則迭代法(4.7)局部收斂.,在(4.7)中取C=1/f(x0)，則稱為簡(jiǎn)化牛頓法，這類方法計(jì)算量省，但只有線性收斂，其幾何意義是用平行弦與x軸交點(diǎn)作為x*的近似，見(jiàn)下圖.,(2) 牛頓下山法, 牛頓法收斂性依賴初值x0的選取, 如果x0偏離所求根x*較遠(yuǎn), 則牛頓法可能發(fā)散.,注：Newtons Method收斂性依賴于x0的選取.,x*,例如，用牛頓法求解方程 x3-x-1=0. (4.8),此方程在x=1.5附近的一個(gè)根x*.,設(shè)取迭代初值x0=1.5，用牛頓迭代法公式,計(jì)算得 x1=1.34783, x2=1.32520, x3=1.32472.,迭代3次得到的結(jié)果x3有6位有效數(shù)字.,但是，如取x0=0.6，用(4.9)式迭代1次得,計(jì)算得 x1=17.9.,這個(gè)結(jié)果反而比x0=0.6更偏離了所求的根x*=1.32472.,為了防止迭代發(fā)散，我們對(duì)迭代過(guò)程再附加一項(xiàng)要求，即具有單調(diào)性.,滿足這項(xiàng)要求的算法稱為下山法.,我們將牛頓法與下山法結(jié)合起來(lái)使用，即在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度. 為此，我們將牛頓法的結(jié)果,與前一項(xiàng)的近似值xk適當(dāng)加權(quán)平均作為新的改進(jìn)值,其中(01)稱為下山因子，(4.11)即為,稱為牛頓下山法.,選擇下山因子時(shí)從=1開(kāi)始，逐次將減半進(jìn)行試算，直到能使下降條件(4.10)成立為止.,若用此法解方程(4.8)，當(dāng)x0=0.6時(shí)由(4.9)式求得x1=17.9，它不滿足條件(4.10)，通過(guò)逐次減半進(jìn)行試算,當(dāng)=1/32時(shí)可求得x1=1.140625. 有f(x0)=-1.384, f(x1)=-0.656643, 顯然|f(x1)|f(x0)|. 計(jì)算x2,x3,時(shí)，均能使條件(4.10)成立. 得到x4=1.32472即為x*的近似., 下山法 /* Descent Method */ Newtons Method 局部微調(diào)：,原理：若由 xk 得到的 xk+1 不能使 | f | 減小，則在 xk 和 xk+1 之間找一個(gè)更好的點(diǎn) ，使得 。,注： = 1 時(shí)就是Newtons Method 公式。 當(dāng) = 1 代入效果不好時(shí)，將 減半計(jì)算。,一般情況下，只要能使條件選擇(4.10)成立，則可得到極限,從而使數(shù)列xk收斂.,7.4.4 重根情形,當(dāng)x*為f(x)的m(m0)重根時(shí)，則f(x)可表為,f(x)=(x-x*)mg(x).,其中g(shù)(x*)0，此時(shí)用牛頓迭代法(4.2)求x*仍然收斂，只是收斂速度將大大減慢. 事實(shí)上，因?yàn)榈?令ek=xkx*，則,可見(jiàn)用牛頓法求方程的重根時(shí)僅為線性收斂.,從而有,兩種提高求重根的收斂速度的方法：,1) 取如下迭代函數(shù),得到迭代公式,下面介紹一個(gè)求重?cái)?shù)m的方法，令,則,求m重根具有2階收斂. 但要知道x*的重?cái)?shù)m.,由式,得,因此得估計(jì)m的式子為,對(duì)f(x)=(x-x*)mg(x), g(x*)0，令函數(shù),則為求(x)=0的單根x*的問(wèn)題，對(duì)它用牛頓法是二階(平方)收斂的. 其迭代函數(shù)為,2) 將求重根問(wèn)題化為求單根問(wèn)題.,從而構(gòu)造出迭代方法為,例8 用牛頓迭代法求函數(shù) f(x)=(x-1)sin(x-1)+3x-x3+1=0 在0.95附近之根.,解 取x0 = 0.95 用牛頓迭代法求得的xk見(jiàn)右表. 可見(jiàn)xk收斂很慢.,由重根數(shù)m=2, 用(4.13)式加速法，作,求得 x0=0.95, x1=0.9988559, x2=x3=1.,收斂速度大大加快于直接用牛頓迭代公式.,參見(jiàn)書p283的例9.,7.5 弦截法與拋物線法,用牛頓法求方程f(x)=0的根，每步除計(jì)算f(xk)外還要算f(xk)，當(dāng)函數(shù)f(x)比較復(fù)雜時(shí)，計(jì)算f(x)往往比較困難，為此可以利用已求函數(shù)值f(xk),f(xk-1),來(lái)回避導(dǎo)數(shù)值f(xk)的計(jì)算. 這類方法是建立在插值原理基礎(chǔ)上的，下面介紹兩種常用方法.,7.5.1 弦截(割線)法,設(shè)xk,xk-1是f(x)=0的近似根，我們利用f(xk),f(xk-1)構(gòu)造一次插值多項(xiàng)式p1(x)，并用p1(x)=0的根作為方程f(x)=0的新的近似根xk+1，由于,因此有,這樣導(dǎo)出的迭代公式(5.2)可以看做牛頓公式,中的導(dǎo)數(shù) 用差商 取代的結(jié)果.,(5.2)式有明顯的幾何意義：,設(shè)曲線y=f(x)上橫坐標(biāo)為xk-1和xk的點(diǎn)分別為P0和Pk, 則差商 表示弦 的斜率, 弦 的方程為,因此，按(5.2)式求得xk+1實(shí)際上是兩點(diǎn)弦線 與x軸交點(diǎn)的橫坐標(biāo)(令y=0解出x即可).這種算法因此而形象地稱為弦截(割線)法.,參見(jiàn)書p285的例10.,弦截法與切線法(牛頓法)都是線性化分法，但兩者有本質(zhì)的區(qū)別. 切線法在計(jì)算xk+1時(shí)只用到前一步的值xk，而弦截法要用到前面兩步的結(jié)果xk-1,xk，因此使用這種方法必須先給出兩個(gè)開(kāi)始值x0, x1.,定理6 假設(shè)f(x)在根x*的鄰域內(nèi): |x-x*|具有二階連續(xù)導(dǎo)數(shù)，且對(duì)任意x有f(x)0，所取的初值x0, x1，那么當(dāng)鄰域充分小時(shí)，弦截法(5.2)將按階,收斂到x*. 這里p是方程2-1=0的正根.,定理證明可見(jiàn)2.,因?yàn)?5.2)式用到前兩點(diǎn)xk-1和xk的值，故此方法又稱為雙點(diǎn)割線法.,每步只用一個(gè)新點(diǎn)xk的值，此方法稱為單點(diǎn)割線法.,如果把(5.2)式中的xk-1改為x0，即迭代公式為,例題 用牛頓迭代法和割線法求方程 f(x)=x4+2x2x3=0， 在區(qū)間(1, 1.5)內(nèi)之根(誤差為10-9).,解 取x0=1.5，用牛頓法, 可得x6=1.12412303030；,取x0=1.5, x1=1，用雙點(diǎn)割線法，迭代6次得到同樣的結(jié)果，而采用單點(diǎn)割線法，則迭代18次得x18=1.124123029.,例題 用快速弦截法求方程xex-1=0的根. 設(shè)方程的兩個(gè)初始近似根為x0=0.5 , x1=0.6.,與例7(p277)中牛頓法的計(jì)算結(jié)果相比較，可以看出快速弦截法的收斂速度也是相當(dāng)快的，迭代到第4步就得到精度 的結(jié)果.,7.5.2 拋物線法,設(shè)已知方程f(x)=0的三個(gè)近似根xk,xk-1,xk-2，我們以這三點(diǎn)為節(jié)點(diǎn)構(gòu)造二次插值多項(xiàng)式p2(x)，并適當(dāng)選取p2(x)的一個(gè)零點(diǎn)xk+1作為新的近似根，這樣確定的迭代過(guò)程稱為拋物