第七講：非線性方程與方程組的數(shù)值解法

第7章非線性方程與方程組的數(shù)值解法7.1方程求根與二分法7.2不動點迭代法及其收斂性7.3迭代收斂的加速方法7.4牛頓法7.5弦截法與拋物線法7.6非線性方程組的數(shù)值解法

例如代數(shù)方程

x5-x3+24x+1=0,

超越方程

sin(5x2)+e-x=0.

對于不高于4次的代數(shù)方程已有求根公式，而高于4次的代數(shù)方程則無精確的求根公式，至于超越方程就更無法求出其精確的解，因此，如何求得滿足一定精度要求的方程的近似根也就成為迫切需要解決的問題，為此，本章介紹幾種常見的非線性方程的近似求根方法.引言主要討論單變量非線性方程

f(x)=0

(1.1)的求根問題，這里x∈R,f(x)∈C[a,b].在科學與工程計算中有大量方程求根問題，其中一類特殊的問題是多項式方程其中系數(shù)ai(i=0,1,,n)為實數(shù).方程f(x)=0的根x*，又稱為函數(shù)f(x)的零點，它使得f(x*)=0，若f(x)可分解為f(x)=(x-x*)mg(x)，其中m為正整數(shù)，且g(x*)≠0.當m=1時，則稱x*為單根，若m>1稱x*為(1.1)的m重根，或x*為函數(shù)f(x)的m重零點.若x*是f(x)的m重零點，且g(x)充分光滑，則當f(x)為代數(shù)多項式(1.2)時，根據(jù)代數(shù)基本定理可知，n次代數(shù)方程f(x)=0在復(fù)數(shù)域有且只有n個根(含復(fù)根，m重根為m個根).

n=1,2時方程的根是大家熟悉的，n=3,4時雖有求根公式但比較復(fù)雜，可在數(shù)學手冊中查到，但已不適合數(shù)值計算，而n≥5時就不能用公式表示方程的根.因此，通常對n≥3的多項式方程求根與一般連續(xù)函數(shù)方程(1.1)一樣都可采用迭代法求根.迭代法要求給出根x*的一個近似，若f(x)∈C[a,b]且f(a)f(b)<0，根據(jù)連續(xù)函數(shù)性質(zhì)中的介值定理可知方程f(x)=0在(a,b)內(nèi)至少有一個實根，這時稱[a,b]為方程(1.1)的有根區(qū)間.

例1

判斷方程

f(x)=x3-x-1=0的有根區(qū)間.x00.511.52f(x)---++

設(shè)f(x)在區(qū)間[a,b]上連續(xù),f(a)·f(b)<0,則在[a,b]

內(nèi)有方程的根.取[a,b]的中點

將區(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ū)間,它的長度只有原有根區(qū)間長度的一半,達到了壓縮有根區(qū)間的目的.7.1方程求根與二分法

對壓縮了的有根區(qū)間,又可實行同樣的步驟,再壓縮.如此反復(fù)進行,即可的一系列有根區(qū)間套

由于每一區(qū)間都是前一區(qū)間的一半，因此區(qū)間[an,bn]的長度為若每次二分時所取區(qū)間中點都不是根，則上述過程將無限進行下去.當

n→∞

時，區(qū)間必將最終收縮為一點x*

，顯然x*就是所求的根.abx0x2abWhentostop?或不能保證

x

的精度x*2xx*

若取區(qū)間[an,bn]的中點作為x*的近似值，則有下述誤差估計式只要

n

足夠大,(即區(qū)間二分次數(shù)足夠多)，誤差就可足夠小.

由于在偶重根附近曲線y=f(x)

為上凹或下凸,即f(a)與f(b)的符號相同,因此不能用二分法求偶重根.

例2

用二分法求例1中方程

f(x)=x3-x-1=0的實根,要求誤差不超過0.005.

解由例1可知x*∈(1,1.5),要想滿足題意，即：則要|x*-xn|≤0.005由此解得取n=6,按二分法計算過程見下表,x6=1.3242

為所求之近似根.nanbnxnf(xn)說明01234561.01.251.251.31251.31251.31251.32031.51.51.3751.3751.34381.32811.32811.251.3751.31251.34381.32811.32031.3242-+-++--(1)f(a)<0,

f(b)>0(2)根據(jù)精度要求，取到小數(shù)點后四位即可.

二分法的優(yōu)點是算法簡單，且總是收斂的，缺點是收斂的太慢，故一般不單獨將其用于求根，只是用其為根求得一個較好的近似值.逐步搜索法

從區(qū)間[a,b]的左端點a

出發(fā),按選定的步長h

一步步向右搜索，若f(a+jh)·f(a+(j+1)h)<0

(j=0,1,2,)則區(qū)間[a+jh,a+(j+1)h]內(nèi)必有根.搜索過程也可從b開始，這時應(yīng)取步長h<0.7.2不動點迭代法及其收斂性7.2.1不動點迭代法

將方程f(x)=0改寫為等價方程形式

x=(x).(2.1)若要求x*滿足f(x*)=0，則x*=(x*)；反之亦然，稱x*為函數(shù)(x)的一個不動點.求f(x)的零點就等于求(x)的不動點，選擇一個初始近似值x0，將它代入(2.1)右端，即可求得

x1=(x0).可以如此反復(fù)迭代計算xk+1=(xk)

(k=0,1,2,).(2.2)

(x)稱為迭代函數(shù).如果對任何x0∈[a,b]，由(2.2)得到的序列{xk}有極限則稱迭代方程(2.2)收斂.且x*=(x*)為(x)的不動點，故稱(2.2)為不動點迭代法.

當(x)連續(xù)時，顯然x*就是方程x=(x)之根(不動點).于是可以從數(shù)列{xk}中求得滿足精度要求的近似根.這種求根方法稱為不動點迭代法,稱為迭代格式,(x)稱為迭代函數(shù),x0

稱為迭代初值,數(shù)列{xk}稱為迭代序列.如果迭代序列收斂,則稱迭代格式收斂,否則稱為發(fā)散.（幾何意義的解釋見下頁）xyy=xxyy=xxyy=xxyy=xx*x*x*x*x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1分別按以上三種形式建立迭代公式，并取x0=1進行迭代計算，結(jié)果如下：

解對方程進行如下三種變形：

例1

用迭代法求方程x4+2x2-x-3=0

在區(qū)間[1,1.2]內(nèi)的實根.準確根x*

=1.124123029,可見迭代公式不同,收斂情況也不同.第二種公式比第一種公式收斂快得多,而第三種公式不收斂.當方程有多個解時，同一個迭代法的不同初值也可能收斂到不同的根.

例1表明原方程化為x=(x)的形式不同，有的收斂，有的不收斂，有的發(fā)散.

例2表明同一個迭代法的不同初值可能收斂到不同的根.只有收斂的的迭代過程才有意義，為此我們首先要研究(x)的不定點的存在性及迭代法的收斂性.7.2.2不動點的存在性與迭代法的收斂性

首先考察(x)在[a,b]上不動點的存在唯一性.定理1

設(shè)(x)∈C[a,b]滿足以下兩個條件：

1o對任意x∈[a,b]有a≤(x)≤b.

2o存在正數(shù)L<1，使對任意x,y∈[a,b]都有則(x)在[a,b]上存在唯一的不動點x*.

證明先證不動點的存在性.若(a)=a或(b)=b，顯然(x)在[a,b]上存在不動點.因為a≤(x)≤b，以下設(shè)(a)>a及(b)<b定義函數(shù)顯然f(x)∈C[a,b],且滿足f(a)=(a)-a>0,f(b)=(b)-b<0,由連續(xù)函數(shù)性質(zhì)可知存在x*∈(a,b)使f(x*)=0，即x*=(x*)，x*即為(x)的不動點.

再證不動點的唯一性.設(shè)x1*,x2*∈[a,b]都是(x)的不動點，則由(2.4)得引出矛盾，故(x)的不動點只能是唯一的.

證畢.

在(x)的不動點存在唯一的情況下，可得到迭代法(2.2)收斂的一個充分條件.

定理2

設(shè)(x)∈C[a,b]滿足定理1中的兩個條件，則對任意x0∈[a,b]，由(2.2)得到的迭代序列{xk}收斂到的不動點x*，并有誤差估計式

證明設(shè)x*∈[a,b]是(x)在[a,b]上的唯一不動點,由條件1o，可知{xk}∈[a,b]，再由(2.4)得因0<L<1，故當k→∞時序列{xk}收斂到x*.下面證明估計式(2.5)，由(2.4)有于是對任意正整數(shù)p有上述令p→∞,注意到limxk+p=x*(p→∞)即得(2.5)式.又由于對任意正整數(shù)p有上述令p→∞,及l(fā)imxk+p=x*(p→∞)即得(2.6)式.證畢.

迭代過程是個極限過程.在用迭代法進行時，必須按精度要求控制迭代次數(shù).誤差估計式(2.5)原則上確定迭代次數(shù)，但它由于含有信息L而不便于實際應(yīng)用.而誤差估計式(2.6)是實用的，只要相鄰兩次計算結(jié)果的偏差足夠小即可保證近似值xk具有足夠精度.

對定理1和定理2中的條件2o可以改為導(dǎo)數(shù)，即在使用時如果(x)∈C[a,b]且對任意x∈[a,b]有則由微分中值定理可知對任意x,y∈[a,b]有故定理中的條件2o是成立的.

例如，在前面例3中采用的三種迭代公式，在隔根區(qū)間(1,1.2)內(nèi)，有故前兩個迭代公式收斂，第三個迭代公式不收斂.7.2.3局部收斂性與收斂階

上面給出了迭代序列{xk}在區(qū)間[a,b]上的收斂性,通常稱為全局收斂性.有時不易檢驗定理的條件，實際應(yīng)用時通常只在不動點x*的鄰近考察其收斂性，即局部收斂性.

定義1

設(shè)(x)有不動點x*，如果存在x*的某個鄰域R:|x-x*|≤δ，對任意x0∈R，迭代公式(2.2)產(chǎn)生的序列{xk}∈R，且收斂到x*，則稱迭代法(2.2)局部收斂.

定理3

設(shè)x*為(x)的不動點，在x*的某個鄰域連續(xù)，且，則迭代法(2.2)局部收斂.

證明由連續(xù)函數(shù)的性質(zhì)，存在不動點x*的某個鄰域R:|x-x*|≤δ，使對于任意x∈R成立此外，對于任意x∈R，總有(x)∈R，這時因為于是依據(jù)定理2可以斷定迭代過程xk+1=(xk)對于任意初值x0∈R均收斂.證畢.

例4

用不同迭代法求方程x2-3=0的根.

解這里f(x)=

x2-3，可以改寫為各種不同的等價形式x=(x)，其不動點為，由此構(gòu)造不同的迭代法.取x0=2,對上式4種迭代法,計算三步所得結(jié)果入下表.kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4)0123┆

x0x1x2x3┆23987┆21.521.5┆21.751.734751.732361┆21.751.7321431.732051┆

注意，從計算結(jié)果看到迭代法(1)及(2)均不收斂，且它們均不滿足定理3中的局部收斂條件，迭代法(3)和(4)均滿足局部收斂條件，且迭代法(4)比(3)收斂快，因在迭代法(4)中(x*)=0.為了衡量迭代法(2.2)收斂速度的快慢可給出以下定義.

定義2

設(shè)迭代過程xk+1=(xk)收斂于方程x=(x)的根x*，如果迭代誤差ek=xk-x*當k→∞時成立下列漸近關(guān)系式則稱該迭代法是p階收斂的.特別地，p=1時稱線性收斂，p>1時稱超線性收斂，p=2時稱平方收斂.

定理4

對于迭代過程xk+1=(xk)，如果(p)(x)在所求根x*的鄰近連續(xù)，并且則該迭代過程在x*的鄰近是p階收斂的.

證明由于(x*)=0，根據(jù)定理3立即可以斷定迭代過程xk+1=(xk)具有局部收斂性.

再將(xk)在根x*處做泰勒展開,利用條件(2.8),則有注意到(xk)=xk+1，(x*)=x*，由上式得因此對迭代誤差，令k→∞時有這表明迭代過程xk+1=(xk)確實為p階收斂.證畢.

上述定理告訴我們，迭代過程的收斂速度依賴于迭代函數(shù)(x)的選取.如果x∈[a,b]但(x)≠0時，則該迭代過程只可能是線性收斂.7.3迭代收斂的加速方法7.3.1埃特金加速收斂方法

對于收斂的迭代過程，只要迭代足夠多次，就可以使結(jié)果達到任意的精度，但是有時迭代過程收斂較慢，從而使計算量變得很大，因此迭代過程的加速是個重要的課題.設(shè)x0是根x*的某個近似值,用迭代公式校正一次得

x1=(x0)而由微分中值定理，有假設(shè)(x)改變不大,近似地取某個近似值L,則有由于

x2-x*≈L(x1-x*).若將校正值x1=(x0)再校正一次，又得

x2=(x1)將它與(3.1)式聯(lián)立，消去未知的L，有由此推知

Aitken加速：xyy=xy=

φ(x)x*x0P(x0,x1)x1x2P(x1,x2)一般地有：比收斂得略快。在計算了x1及x2之后，可用上式右端作為x*的新近似,記作?x1，一般情形是由xk計算xk+1,xk+2，記它表明序列{?xk}的收斂速度比{xk}的收斂速度快.(3.2)式稱為埃特金(Aitken)△2加速方法.

可以證明也稱為埃特金(Aitken)外推法.可以證明:為線性收斂,則埃特金法為平方收斂；

這個加速迭代法也可寫成下面格式若為p(p>1)階收斂，導(dǎo)數(shù)連續(xù)，則埃特金法為2p–1

階收斂.的

p

階若例題求方程x=e–x

在x=0.5

附近的根.

解取x0=0.5,迭代格式x25=x26=0.5671433

若對此格式用埃特金法,則

得仍取x0=0.5,得由此可見,埃特金法加速收斂效果是相當顯著的.7.3.2斯蒂芬森(Steffensen)迭代法

埃特金方法不管原序列{xk}是怎樣產(chǎn)生的，對{xk}進行加速計算，得到序列{?xk}.如果把埃特金加速技巧與不動點迭代結(jié)合，則可得到如下的迭代法：稱為斯蒂芬森(Steffensen)迭代法.

實際上(3.3)是將不定點迭代法計算兩步合并成一步得到的，可將它寫成另一種不動點迭代其中

對不動點迭代(3.5)有以下局部收斂性定理.

定理5

若x*為(3.5)定義的迭代函數(shù)Ψ(x)的不動點，則x*為(x)的不定點.反之，若x*為(x)的不動點，設(shè)(x)存在，(x)≠1，則x*是Ψ(x)的不動點，且斯蒂芬森迭代法(3.3)是2階收斂的.7.4牛頓法7.4.1牛頓法及其收斂性

對于方程f(x)=0，如果f(x)是線性函數(shù)，則它的求根是容易的.牛頓法實質(zhì)上是一種線性化方法，其基本思想是將非線性方程f(x)=0逐步歸結(jié)為某種線性方程來求解.

設(shè)已知方程f(x)=0有近似根x0，且在x0附近f(x)可用一階泰勒多項式近似，表示為當f(x0)≠0時，方程f(x)=0可用線性方程(切線)近似代替，即f(x0)+f(x0)(x-x0)=0.

(4.1)解此線性方程得得迭代公式此式稱為牛頓(Newton)迭代公式.牛頓法有顯然的幾何意義，方程f(x)=0的根x*可解釋為曲線y=f(x)與x軸交點的橫坐標.設(shè)xk是根x*的某個近似值，過曲線y=f(x)上橫坐標為xk的點Pk引切線，并將該切線與x軸交點的橫坐標xk+1作為x*的新的近似值.注意到切線方程為這樣求得的值xk+1必滿足(4.1),從而就是牛頓公式(4.2)的計算結(jié)果.由于這種幾何背景，所以牛頓迭代法也稱切線法.xyx*xky=f(x)xk+1PkPk+1xk+2牛頓迭代法的收斂性設(shè)x*是f(x)的一個單根，即f(x*)=0，f(x*)≠0,有牛頓迭代法的迭代函數(shù)為由定理4的(2.9)式可得由此得到，當x*為單根時，牛頓迭代法在根x*的鄰近是二階(平方)收斂的.關(guān)于x*為重根時，牛頓迭代法在根x*的鄰近的收斂性在后面討論.

定理(局部收斂性)

設(shè)fC2[a,b],若x*為f(x)在[a,b]上的根，且f(x*)0，則存在x*的鄰域U,使得任取初值x0U，牛頓法產(chǎn)生的序列{xk}收斂到x*，且滿足即有下面的局部收斂性定理.

解將原方程化為x–e–x=0，則牛頓迭代公式為取x0=0.5，迭代得x1=0.566311,x2=0.5671431,x3=0.5671433.

f(x)=x–e–x，f(x)=1+e–x，例7

用牛頓迭代法求方程x=e–x在x=0.5附近的根.7.4.2牛頓法應(yīng)用舉例對于給定的正數(shù)C，應(yīng)用牛頓法解二次方程我們現(xiàn)在證明，這種迭代公式對于任意初值x0>0都是收斂的.可導(dǎo)出求開方值的計算程序事實上，對(4.5)式施行配方整理，易知以上兩式相除得據(jù)此反復(fù)遞推有記整理(4.6)式，得對任意初值x0>0，總有|q|<1，故由上式推知，當k→∞時，即迭代過程恒收斂.注：Newton’sMethod收斂性依賴于初值x0

的選取。x*x0x0x07.4.3簡化牛頓法牛頓法的優(yōu)點是收斂快，缺點①每步迭代要計算f(xk)及f(xk)，計算量較大，且有時f(xk)計算較困難；②初始近似值x0只在根x*附近才能保證收斂，如x0給的不合適可能不收斂.為克服這兩個缺點，通?？捎孟率龇椒?

簡化牛頓法，也稱平行弦法，其迭代公式為迭代函數(shù)為(x)=x-Cf(x).若|(xk)|=|1-Cf(x)|<1，即取0<Cf(x)<2.在根x*附近成立，則迭代法(4.7)局部收斂.在(4.7)中取C=1/f(x0)，則稱為簡化牛頓法，這類方法計算量省，但只有線性收斂，其幾何意義是用平行弦與x軸交點作為x*的近似，見下圖.y=f(x)x0x1x2x*7.4.4重根情形當x*為f(x)的m(m>0)重根時，則f(x)可表為f(x)=(x-x*)mg(x).其中g(shù)(x*)≠0，此時用牛頓迭代法(4.2)求x*仍然收斂，只是收斂速度將大大減慢.事實上，因為迭代公式令ek=xk–x*，則可見用牛頓法求方程的重根時僅為線性收斂.從而有兩種提高求重根的收斂速度的方法：

1)

取如下迭代函數(shù)得到迭代公式求m重根具有2階收斂.但要知道x*的重數(shù)m.對f(x)=(x-x*)mg(x),g(x*)≠0，令函數(shù)則為求μ(x)=0的單根x*的問題，對它用牛頓法是二階(平方)收斂的.其迭代函數(shù)為

2)

將求重根問題化為求單根問題（去重數(shù)）.從而構(gòu)造出迭代方法為例8

用牛頓迭代法求函數(shù)

f(x)=(x-1)[sin(x-1)+3x]-x3+1=0

在0.95附近之根.

解取x0=0.95

用牛頓迭代法求得的xk見右表.可見xk收斂很慢.kxk01234560.950.97442790.98705830.99348780.99673280.99835760.9991901由重根數(shù)m=2,用(4.13)式加速法，作求得

x0=0.95,x1=0.9988559,x2=x3=1.收斂速度大大加快于直接用牛頓迭代公式.7.5弦截法與拋物線法用牛頓法求方程f(x)=0的根，每步除計算f(xk)外還要算f(xk)，當函數(shù)f(x)比較復(fù)雜時，計算f(x)往往比較困難，為此可以利用已求函數(shù)值f(xk),f(xk-1),來回避導(dǎo)數(shù)值f(xk)的計算.這類方法是建立在插值原理基礎(chǔ)上的，下面介紹兩種常用方法.7.5.1割線(弦截)法設(shè)xk,xk-1是f(x)=0的近似根，我們利用f(xk),f(xk-1)構(gòu)造一次插值多項式p1(x)，并用p1(x)=0的根作為方程f(x)=0的新的近似根xk+1，由于因此有這樣導(dǎo)出的迭代公式(5.2)可以看做牛頓公式中的導(dǎo)數(shù)用差商取代的結(jié)果.

(5.2)式有明顯的幾何意義：

設(shè)曲線y=f(x)上橫坐標為xk-1和xk的點分別為Pk-1和Pk,則差商表示弦的斜率,弦的方程為Ox*xk+1xkPkxk-1yxPk-1因此，按(5.2)式求得xk+1實際上是兩點弦線與x軸交點的橫坐標(令y=0解出x即可).這種算法因此而形象地稱為割線(弦截)法.割線法與牛頓法(切線法)都是線性化分法，但兩者有本質(zhì)的區(qū)別.牛頓法在計算xk+1時只用到前一步的值xk，而割線法要用到前面兩步的結(jié)果xk-1,xk，因此使用這種方法必須先給出兩個開始值x0,x1.

定理6

假設(shè)f(x)在根x*的鄰域內(nèi)△:|x-x*|≤δ具有二階連續(xù)導(dǎo)數(shù)，且對任意x△有f(x)≠0，所取的初值x0,x1△，那么當鄰域△充分小時，弦截法(5.2)將按階收斂到x*.這里p是方程λ2-λ-1=0的正根.因為(5.2)式用到前兩點xk-1和xk的值，故此方法又稱為雙點割線法.每步只用一個新點xk的值，此方法稱為單點割線法.如果把(5.2)式中的xk-1改為x0，即迭代公式為

例題用牛頓迭代法和割線法求方程

f(x)=x4+2x2–x–3=0，在區(qū)間(1,1.5)內(nèi)之根(誤差為10-9).

解取x0=1.5，用牛頓法,可得x6=1.12412303030取x0=1.5,x1=1，用雙點割線法，迭代6次得到同樣的結(jié)果，而采用單點割線法，則迭代18次得

x18=1.124123029.7.5.2拋物線法設(shè)已知方程f(x)=0的三個近似根xk,xk-1,xk-2，我們以這三點為節(jié)點構(gòu)造二次插值多項式p2(x)，并適當選取p2(x)的一個零點xk+1作為新的近似根，這樣確定的迭代過程稱為拋物線法，亦稱為密勒(Müller)法.在幾何圖形上,這種方法的基本思想是用拋物線y=p2(x)與x軸的交點xk+1作為所求根x*的近似位置.Ox*xk+1xky