第6章 - 非線性方程求根方法

第六章非線性方程數(shù)值解法基礎(chǔ)知識(shí)非線性方程的二分法解x=g(x)的簡單迭代法解f(x)=0的Newton迭代法1§1基礎(chǔ)知識(shí)一、非線性方程、非線性方程組非線性方程組包括：

高次方程(組),即代數(shù)方程(組)超越方程(組)二、非線性方程(組)求解的特點(diǎn)產(chǎn)生的背景:許多科學(xué)理論與工程技術(shù)都可化為非線性方程(組)求解的特點(diǎn)：無求解公式，無直接解法，難求得精確解。例:

超越方程ex+cosx

=1沒有一定的解法。又例如對(duì)于大于等于五次的代數(shù)方程，無解析根表達(dá)公式，只能使用數(shù)值方法對(duì)于實(shí)際問題進(jìn)行求解。2原理由連續(xù)函數(shù)介值定理,則至少存在某個(gè)x*(a,b)，使得f(x*)=0,即[a,b]內(nèi)至少有方程的一個(gè)根,稱[a,b]為f(x)的一個(gè)含根區(qū)間，且考慮非線性方程：

f(x)=0如果3從一個(gè)初始近似值出發(fā),重復(fù)某種計(jì)算過程來不斷改進(jìn)近似解，有限次改進(jìn)后,計(jì)算出一個(gè)滿足誤差要求的近似解，這種求解方法稱為迭代法。求解的方法：間接法，也即迭代法。求解的要求：

收斂計(jì)算效率(快慢)

數(shù)值穩(wěn)定性(考慮計(jì)算機(jī)的舍入誤差)初始值好迭代公式合適(好的)定義：間接法(迭代法):4根的存在性：方程是否有根？如果有根，有幾個(gè)根？根的隔離：確定根所在的區(qū)間，使方程在這個(gè)小區(qū)間內(nèi)有且僅有一個(gè)根，這一過程稱為根的隔離，完成根的隔離，就可得到方程的各個(gè)根的近似值。根的精確化：已知一個(gè)根的粗略近似值后，將近似解逐步精確化，直到滿足給定精度為止。

關(guān)于根的存在性是純數(shù)學(xué)問題，不詳細(xì)介紹，可查閱有關(guān)代數(shù)學(xué)內(nèi)容。求方程根的近似解，一般有下列幾個(gè)問題：從區(qū)間[a,b]的左端點(diǎn)a出發(fā)，按選定的步長h一步步向右搜索，若:則區(qū)間[a+jh,a+(j+1)h]內(nèi)必有根。搜索過程也可以從

b開始，這時(shí)應(yīng)取步長h<0。

逐步搜索：介值定理5定義序列的收斂性三、基本定義則稱點(diǎn)列收斂于點(diǎn)X*記為或當(dāng)6一、原理把含根區(qū)間不斷縮短，使含根區(qū)間之間含有一個(gè)滿足誤差要求的近似解?！?二分法7找中點(diǎn)：令計(jì)算：f0=f(x0)(即中點(diǎn)函數(shù)值)生成含根區(qū)間二、具體過程(方法)令若f(x0)=0,則x*=x0,若f(x0)·f(a0)>0,取a1=x0,b1=b0,若f(x0)·f(a0)<0,取a1=a0,b1=x08生成含根區(qū)間[a1,b1]滿足:以[a1,b1]取代[a0,b0],重復(fù)以上過程，得[a2,b2]…一般的,設(shè)已得含根區(qū)間[ai,bi]，i=0,1,…,k,滿足：(2)9對(duì)區(qū)間[ak,bk]，找中點(diǎn)：令計(jì)算：fk=f(xk)(中點(diǎn)函數(shù)值)生成含根區(qū)間:若f(xk)=0,則x*=xk,如圖若f(xk)·f(ak)>0,取ak+1=xk,bk+1=bk,如圖若f(xk)·f(ak)<0,取ak+1=ak,bk+1=xk，如圖生成含根區(qū)間[ak+1,bk+1],滿足(2)式{ak}單增，有上界x*,{bk}單減，有下界x*10所以，近似解序列其極限為即序列收斂于f(x)=0的一個(gè)根x*即且f(x*)=0說明:只要就有此時(shí)可計(jì)算或估計(jì)二分法執(zhí)行的次數(shù)k.事實(shí)上,由兩邊取對(duì)數(shù)對(duì)于給定的誤差界可取11收斂速度不快,僅與公比為1/2的等比級(jí)數(shù)的收斂速度相同。即是線性收斂的。不能用于求偶重根、復(fù)根；不能推廣到多元方程組求解；不能求出所有根(即有可能漏根)。對(duì)函數(shù)要求低(只要連續(xù),在兩個(gè)端點(diǎn)異號(hào))。二分法是收斂的。優(yōu)點(diǎn):例如圖該點(diǎn)可求出,但漏掉了四個(gè)點(diǎn)缺點(diǎn):

12試用二分法求方程：f(x)=x3+10x-20=0的唯一實(shí)根，要求誤差不超過Nanbnxnf(xn)0121.5-1.62511.521.752.85937521.51.751.6250.5410156331.51.6251.5625-0.5603027341.56251.6251.59375-0.0143127451.593751.6251.6093750.2621727061.593751.60937501.60156250.1236367271.593751.60156251.59765620.0545888581.593751.59765621.59570310.0201197991.593751.59570311.59472660.00289896101.593751.59472661.5942383-0.00570803111.59423831.59472661.5944824-0.00140482121.59448241.59472661.59460450.00074700131.59448241.59460451.5945435-0.00032893141.59454361.59460461.5945741

例13§3解x=g(x)的簡單迭代法一、簡單迭代法(1)先將f(x)=0化為等價(jià)方程(3.2)式稱為簡單迭代法或單點(diǎn)迭代法或逐次逼近法。g(x)稱為迭代函數(shù)。思想：(2)從某初始值x0出發(fā),作序列{xk}若{xk}收斂于x*且g(x)連續(xù)，則x*是f(x)=0的根。14說明:由f(x)=0化成等價(jià)方程x=g(x)的方法有很多種。如何選取迭代函數(shù)g(x)？

g(x)滿足什么條件，迭代序列收斂？收斂速度是多少？如何加速迭代序列的收斂速度？問題:15解改寫原方程為等價(jià)方程求方程x3-2x-3=0在[1,2]內(nèi)的根.例

建立迭代格式如果取初值x0=1.9,計(jì)算得kxkkxk0123451.91.894536471.893521141.893332331.893297221.89329069678910…1.893289471.893289251.893289211.893289201.89328920……16問題:定義4若迭代序列{xk}保持有界,且全在g(x)定義域內(nèi)，則簡單迭代法則簡單迭代法(3.2)稱為收斂的。由xk+1=g(xk)，求xk+1，但xk

是否位于定義域上？稱為適定的；若進(jìn)一步有17當(dāng)?shù)?3.2)收斂時(shí),極限點(diǎn)x*又是g(x)的連續(xù)點(diǎn),則g(x)把定義域的每個(gè)x

映成了g(x)，因此，(3.2)的解也稱為g(x)的不動(dòng)點(diǎn)。換言之，g(x)是映射，若x*滿足注:

適定是收斂必要條件，即不適定則一定不收斂。即x*是(3.2)的解。稱x*是g(x)的不動(dòng)點(diǎn)。18說明：幾何意義x=g(x)從初始點(diǎn)x0出發(fā)，沿直線x=x0走到曲線y=g

(x)，得點(diǎn)(x0,

g(x0))，再沿直線y=g(x0)走到直線y=x，交點(diǎn)為(x1,g(x1))，如此繼續(xù)下去，越來越接近點(diǎn)(x*,x*)。19xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p120二、收斂定理定理3(壓縮不動(dòng)點(diǎn)定理或壓縮映象定理)若迭代函數(shù)g(x)滿足使有則有以下結(jié)論：

x=g(x)在[a,b]上有唯一解x*;對(duì)有誤差估計(jì)214.若存在，則證明：由介值定理，h(x)在[a,b]上至少存在一個(gè)根x*令唯一性從而設(shè)y*是在[a,b]上另一根，則1.解的唯一存在性22由條件(1)知{xk}適定，那么2.序列收斂性3.誤差估計(jì)23＃4.導(dǎo)數(shù)利用導(dǎo)數(shù)的定義(3.4)式的條件較難驗(yàn)證，常采用導(dǎo)數(shù)來代替。即有推論1：推論1定理3中(3.4)可用下式替代24在[-1,1]上不滿足定理3的條件2，實(shí)際上x=0是解，只要x0取在0的附近，把(-1,1)縮小使得3.定理?xiàng)l件非必要條件，可將[a,b]縮小，定義局部收斂性：若在x*

的某領(lǐng)域B

={x||xx*|}，有g(shù)C1[a,b]且|g’(x*)|<1，則由x0B

開始的迭代收斂。即調(diào)整初值可得到收斂的結(jié)果。例如注：從結(jié)論3可知，L越小收斂越快，L叫做漸進(jìn)收斂因子。從誤差估計(jì)式可見,對(duì)任一>0,要使|xk-x*|<,只要

25定理4（局部收斂定理）有且有誤差估計(jì)：實(shí)際計(jì)算中往往只在根x*鄰近討論，有局部收斂定理4：若g(x)在不動(dòng)點(diǎn)x*的δ鄰域滿足則

x0

[x*-δ,x*+δ]

，由xk+1=g(xk)產(chǎn)生的序列{xk}收斂于x*。26說明：定理中的條件是充分但非必要條件。見定理3注。證明：＃27推論2(3.6)式的條件較難驗(yàn)證,常采用導(dǎo)數(shù)來代替。即有推論2：若g(x)在不動(dòng)點(diǎn)x*處可微，且|g’(x*)|<1,則存在δ>0,則

x0

[x*-δ,x*+δ]

，由xk+1=g(xk)產(chǎn)生的序列{xk}收斂于x*。且28證明：任取由知存在，成立即由定理4得證。＃29求方程xex-1=0在0.5附近的根,精度要求=10-3.解可以驗(yàn)證方程xex-1=0在區(qū)間[0.5,0.6]內(nèi)僅有一個(gè)根.例30改寫方程為x=e-x

,建立迭代格式由于(x)=e-x

,在[0.5,0.6]上有|(x)|e-0.50.6<1。所以迭代法收斂.取初值x0=0.5,計(jì)算得數(shù)表kxk|xk-xk-1|kxk|xk-xk-1|0123450.50.606530.545240.579700.560060.571170.106530.061290.034460.019640.011116789100.564860.568440.566410.567560.566910.006310.003580.002030.001150.0006531所以,取近似根x10=0.56691滿足精度要求.如果精度要求為=10-5,則由可知,需要迭代20次.32例用簡單迭代法求的近似值。解：設(shè)則近似值計(jì)算轉(zhuǎn)化為求方程x(x+2)=1的正根，

取作為的近似值，得：等價(jià)方程：以x0=0為初始值近似得到迭代序列：33取區(qū)間為在上滿足定理3。故迭代法收斂。即1.4142157就是近似值。下證序列收斂于只要證滿足定理3，又34若收斂于X*，若存在常數(shù)C，使得三、簡單迭代法的收斂階定義收斂階p=1時(shí),稱為線性收斂;收斂階p>1時(shí),稱為超收斂;收斂階p=2

時(shí),稱為平方收斂序列的收斂階數(shù)越高,收斂速度越快特別:35一般的，簡單迭代是線性收斂，但在一定條件下，迭代是高階收斂的。有定理5：定理5（高階收斂定理）則簡單迭代法局部收斂，且收斂階為m。分析：已知條件有各階導(dǎo)數(shù)均為0,因此用泰勒公式展開。若g(x)在不動(dòng)點(diǎn)x*

鄰近有m階的連續(xù)導(dǎo)數(shù)，且滿足36＃證明：由推論2，簡單迭代法是局部收斂的。即37四、迭代函數(shù)g(x)的選取方法選取的g(x)必須滿足:兩方程同解；迭代序列收斂于其根。兩種選g(x)的方法:使得設(shè)λ為正常數(shù)，試用g(x)≡x-λf(x)作為迭代函數(shù)，選擇λ，使得成立.，且存在常數(shù)m，M對(duì)于f(x)=0的迭代格式1.假設(shè)在含根區(qū)間[a,b]上存在(*)38作為迭代函數(shù).則簡單迭代法收斂于f(x)=0的根x*。特別,使得(牛頓迭代法的變形)則(*)式成立。故可用392.若求得原方程的根x*。則前述方法不能使用。此時(shí)，若g(x)的反函數(shù)x=t(x)容易求出，可用t(x)作為迭代函數(shù)。因?yàn)閤=g(x)與x=t(x)同根。于是，可用迭代格式40例

求在上的根.解:在上有根.方程與等價(jià).但故不能用作為迭代函數(shù).的反函數(shù)的導(dǎo)數(shù)在[1,2]上滿足所以可用t(x)作迭代函數(shù)進(jìn)行求根。41五、迭代的加速方法(Aitken加速)原理對(duì)于線性收斂數(shù)列,有于是整理化簡得加速收斂序列42結(jié)合不動(dòng)點(diǎn)迭代格式，有xyy=xy=g(x)x*x0P(x0,x1)x1x2P(x1,x2)43六、迭代結(jié)束條件1)根據(jù)實(shí)際問題需要定出解的誤差界由定出迭代次數(shù)2)用相鄰兩次近似值有多少位有效數(shù)字相同,判斷是否停機(jī).注:編程序時(shí),要注意結(jié)束條件.定出的k往往不準(zhǔn)確,因?yàn)橛?jì)算中有舍入誤差，故使迭代次數(shù)比計(jì)算的大。44§4解f(x)=0的Newton迭代法原理:

非線性方程局部線性化(Taylor展開)單根附近具有較高的收斂速度(平方收斂)一、Newton迭代公式1公式:設(shè)f(x)二次連續(xù)可導(dǎo)，xk

是方程的第k次近似解則f(x)在點(diǎn)xk的Taylor展開式：其中ξ(x,xk)。忽略高階小量，取前端的線性部分(線性主部)，用其近似f(x)，有45Newton迭代公式:說明:推導(dǎo)過程中是用f(x)的泰勒展開式的線性部分作為f(x)的近似值,因此說Newton法是一個(gè)逐次線性化方法。把作為第k+1次近似解，即得(4.1)462幾何意義y=f(x)圖象如圖，xk是f(x)=0的k次近似，曲線上對(duì)應(yīng)的點(diǎn)為(xk,f(xk))，過該點(diǎn)做y=f(x)的切線Lk，交x軸于點(diǎn)xk+1，Lk方程：用以近似曲線y=f(x)，則Lk與x軸的交點(diǎn)xk+1作為f(x)=0的第k+1次近似解。即由(4.2)式令y=0得此即Newton法的迭代公式，因此Newton法也稱為切線法。xyox0y=(x)x1x247定理10（Newton法局部二階收斂性）如果f(x)在解x*鄰近二次連續(xù)可導(dǎo),且則存在δ>0，只要Newton序列二階收斂于x*,即二、Newton法收斂性1收斂定理(4.3)48證明：于是有49定理11（Newton法非局部收斂定理）且滿足:在上不變號(hào)；在上不取零。則對(duì)滿足Newton序列單調(diào)二階收斂于f(x)=0在[a,b]上的唯一解x*.50例用Newton法求解解:首先可以判斷解在(0,1)內(nèi).(恒正)(不變號(hào))則Newton迭代序列單調(diào)二階收斂到方程在(0,1)內(nèi)的唯一根，取初始值x0=1,計(jì)算結(jié)果如表：kxkf(xk)f’(xk)010.4596976941.84147098410.7503638670.0189230731.68190495220.739112890.0000464541.67363254430.7390851330又f(x)=x–cos

x在(0,1)有51從適當(dāng)?shù)膞0,x1生成迭代序列的方法稱為正割法。1正割法(割線法)三、Newton法的推廣與改進(jìn)采用迭代格式割線法也可看作以(xn-1，f(xn-1))，(xn，f(xn))作線性插值，而以此插值多項(xiàng)式近似f(x)，以其零點(diǎn)近似f(x)的零點(diǎn)。52即，用f(x)關(guān)于xk-1,xk的線性插值函數(shù)來近似函數(shù)f(x)。取L(x)=0的根作為f(x)=0的新近似根,即x*的k+1次近似oxyy=(x)x0x1x2x3幾何意義來近似原曲線并用割線與x軸的交點(diǎn)xk+1

，近似方程的根x*。用連接(xk-1,f(xk-1)),(xk,f(xk))兩點(diǎn)的直線53注：若(x)在根x*附近二次連續(xù)可微,且f’(x*)≠0,可以證明割線法是收斂的,且有割線法收斂的階為(超線性收斂)xk,xk-1可以在x*的同側(cè)，也可以在x*的兩側(cè)，割線與x軸的交點(diǎn)xk+1比xk，xk-1都更接近真解。542計(jì)算重根的Newton迭代法事實(shí)上，設(shè)x*是f(x)=0的m(m>1)重根,即由于的單根.稱之為帶參數(shù)m的Newton迭代法,它是求方程(x)=0m重根的具有平方收斂的迭代法.可見,x*恰是方程應(yīng)用Newton迭代法可得:55再看函數(shù):可見,x*恰是方程u(x)=0的單根,應(yīng)用Newton迭代法有即為求方程(x)=0重根的具有平方收斂的迭代法,而且不需知道根的重?cái)?shù).u(x)=0的單根即為f(x)=0的重根.且該迭代是二階收斂的.(定理10)(4.5)56例

利用Newton迭代法求方程oxy246810y=f(x)解：y=(x)的圖形為可見,方程在x=4附近有一個(gè)重根,在x=7附近有一單根.的正實(shí)根利用Newton迭代法57求方程的單根,取初值x0=7,精度

=10-6,計(jì)算可得:

x4=7.34846923,x5=7.348469229,|x5-x4|=0.000000001可見,迭代5次就得到滿足精度的解x5=7.348469229利用求重根的Newton迭代法(4.5)求重根,取x0=4,計(jì)算可得x3=4.300000,x4=4.300000,|x4-x3|=0.000000006然而若用一般的Newton迭代法(4.5)求重根,取x0=4,雖然也收斂,卻需要迭代19次才能得到滿足精度要求的解.可見,迭代4次就得到滿足精度的解x4=4.300000.利用帶參數(shù)m=2的Newton迭代法,取x0=4可得x2=4.2999898.58四、Newton下山法(修正的Newton法)牛頓法收斂速度快，但對(duì)初值要求苛刻。在實(shí)際應(yīng)用中不容易確定，有時(shí)往往由于初值選取不當(dāng)而使迭代不收斂.Newton下山法是