《計算方法》課件1第3章

第三章非線性方程求根3.1二分法3.2迭代法3.3加速迭代收斂的方法3.4牛頓迭代法3.5弦割法與拋物線法3.6非線性方程組零點的迭代方法習(xí)題33.1二分法

單變量函數(shù)方程:

f(x)=0(3.1)

其中，f(x)在閉區(qū)間［a，b］上連續(xù)、單調(diào)，且f(a)f(b)<0，則由函數(shù)的介值定理可知，方程(3.1)在(a,b)內(nèi)有且只有一個根x*。下面用二分法通過函數(shù)在區(qū)間端點的符號來確

定x*所在區(qū)間，將有根區(qū)間縮小到充分小，從而求出滿足給定精度的根x*的近似值。記a1=a，b1=b，對分區(qū)間［a1，b1］，計算中點x1=

(a1+b1)及f(x1)，如果f(x1)=0，則x*=x1，否則有f(a1)f(x1)<0或f(x1)f(b1)<0。不妨設(shè)f(a1)f(x1)<0，并記a2=a1，b2=x1,則根x*∈(a2,b2)，這樣就得到長度縮小一半的有根區(qū)間［a2,b2］，即f(a2)f(b2)<0，此時b2－a2=

(b1－a1)。對有根區(qū)間［a2,b2］重復(fù)上述步驟，即分半求中點，判斷中點處函數(shù)符號，則可得到長度又縮小一半的有根區(qū)間［a3,b3］，如圖3-1所示。圖3-1重復(fù)上述過程，第n步就得到根x*的近似值序列{xn}及包含x*的區(qū)間套，有如下形式：

(1)

(2)

(3)

(4)

(3.2)，且（n=1,2…..）由(3.2)式顯然有，且xn以等比數(shù)列的收斂速度收斂于x*，因此，用二分法求f(x)=0的實根x*可以達(dá)到任意指定精度。事實上，對任意給定的精度要求ε>0，要求

|xn－x*|≤

(b－a)<ε，可得，即得到區(qū)間對分次數(shù)n。

例3.1已知方程f(x)=x3+4x2－10=0在區(qū)間［1,2］上有一個實根x*，用二分法求該實根，要求|xn－x*|≤

×10－2。

解

f(x)=x3+4x2－10,

f′(x)=3x2+8x>0

(x∈［1,2］)

f(1)=-5<0,

f(2)=14>0所以f(x)=0在［1,2］內(nèi)有唯一實根，令

解出n>6，即至少對分7次。取x1=

=1.5開始計算，列表如表3.1所示，因此有

二分法的優(yōu)點是方法及相應(yīng)的程序都簡單，且對函數(shù)f(x)的性質(zhì)要求不高，只要連續(xù)單調(diào)即可，但二分法不能用于求復(fù)根和重根。

3.2迭代法

迭代法是一種逐步逼近的方法，它是解代數(shù)方程、超越方程、線性方程組、非線性函數(shù)方程組、微分方程等的一種基本而重要的數(shù)值方法。3.2.1不動點迭代法

用不動點迭代方法求方程根的基本思想是將方程(3.1)轉(zhuǎn)化為等價的形式：

x=φ(x)

(3.3)

若x*滿足f(x*)=0，則x*滿足x*=φ(x*)，反之亦然，我們稱x*是f(x)=0的根，是x=φ(x)的不動點，從而求f(x)=0根的問題轉(zhuǎn)化為求x=φ(x)的不動點問題。一般來說，不可能從x=φ(x)中直接得到不動點x*，需要先給出不動點x*的一個猜測值x0(稱為初始值)，然后代入(3.3)式右端，按下述公式進(jìn)行計算：

xk+1=φ(xk)

(k=0,1,2,…)

(3.4)

稱(3.4)式為不動點迭代法(也稱簡單迭代法或逐步逼近法),φ為迭代函數(shù)。若(3.4)式產(chǎn)生的序列{xk}收斂到x*，則x*就是x=φ(x)的不動點，即方程f(x)=0的根。

我們可以通過不同的途徑將方程(3.1)化成等價的(3.3)式的形式，現(xiàn)舉例如下。

例3.2已知方程x3+4x2－10=0在區(qū)間［1,2］上有一個根，可以用不同的迭代格式求其不動點，在收斂情況下求其不動點精確到10－8。

方法一： 即

方法二： 即

方法三： 即方法四： 即

方法五： 即

取x0=1.5。用以上五種方法進(jìn)行迭代計算，結(jié)果見表3.2。由表3.2可以看出：方法一不收斂；方法三出現(xiàn)負(fù)數(shù)開平方，不能繼續(xù)作實數(shù)運算；方法二算出x29=1.365230013，與方法四中的x11及方法五中的x4相同。它們在字長范圍內(nèi)完全達(dá)到精度要求，因此可見，迭代函數(shù)φ(x)選取不同，相應(yīng)地，{xk}的收斂情況也不同。

由迭代公式(3.4)求方程f(x)=0的近似根時，應(yīng)該選擇什么樣的迭代函數(shù)φ(x)，使由迭代公式xk+1=φ(xk)產(chǎn)生的序列{xk}收斂呢？如果有多種迭代公式，哪一種迭代公式產(chǎn)生的序列收斂得更快呢？現(xiàn)在討論一般的收斂理論。3.2.2不動點迭代的一般理論

定理3.1設(shè)與方程f(x)=0等價的形式為x=φ(x)，其中φ(x)在區(qū)間［a,b］上具有連續(xù)的一階導(dǎo)數(shù)，且

(1)當(dāng)x∈［a,b］時總有φ(x)∈［a,b］；

(2)存在常數(shù)L，0≤L<1，使得對任意x∈(a,b),都有|φ′(x)|≤L，則有：

(1)x=φ(x)在［a,b］內(nèi)有唯一不動點x*；

(2)對任意初始值x0∈［a,b］，由迭代公式xk+1=φ(xk)

(k=0，1，2，…)產(chǎn)生的序列{xk}均收斂于x*；

(3)

(3.5)

(3.6)

證明

(1)先證方程x=φ(x)在區(qū)間［a,b］內(nèi)有唯一不動點。

令f(x)=x－φ(x)，則f(x)在［a,b］上連續(xù)，由條件(1)可知，

f(a)=a－φ(a)≤0,

f(b)=b－φ(b)≥0

從而必有(至少有)x*∈(a,b)，使f(x*)=0，即x*=φ(x*)(零點定理)。

若在區(qū)間［a,b］內(nèi)還有一點，使，則

若，則φ′(ζ)=1，與假設(shè)條件|φ′(x)|≤L<1矛盾，因此有=x*，即不動點x*是唯一的，如圖3-2所示。（(ξ介于x*與之間)圖3-2

(2)由假設(shè)條件(1)、(2)可知：對任意正整數(shù)k，都有xk+1=φ(xk)∈［a,b］，因此,

|xk+1－x*|=|φ(xk)－φ(x*)|

=|φ′(ξ)||xk－x*|≤L|xk－x*|≤L2|xk-1－x*|≤…≤Lk|x0－x*|，

從而，即迭代序列{xk}收斂于不動點x*。

(3)因為

所以又由于

因此

定理3.1的幾何意義是明顯的，它表明在不動點x*附近，y=φ(x)的切線不能太陡，不動點x*實際就是直線y=x與曲線y=φ(x)的交點。圖3-3和圖3-4分別給出了發(fā)散與收

斂的幾何說明。圖3-3圖3-4對于不等式(3.6)，由于|x1－x0|與k無關(guān)，是定值,而若L≈1，則xk收斂于x*時很緩慢；若L<<1，則xk收斂于x*時就很快，因此，L的值可以表示出xk收斂于x*的快慢情況。此外，給定x0(從而x1也給定)及誤差要求ε,從(3.6)式中可估計出需要迭代的次數(shù)，顯然，迭代次數(shù)與L有關(guān)。下面，利用定理3.1來分析例3.2的幾種方法。

對于函數(shù)φ1(x)：φ1′

(x)=1－3x2－8x，x*=1.365230013，找不到包含x*的區(qū)間［a,b］，使得|φ

1′

(x)|<1，故不能用定理3.1保證其收斂性。對于函數(shù)φ2(x)：φ

2′

(x)=

,若?。踑,b］=［1,1.5］，則有|φ

2′

(x)|≤|φ

2′

(1.5)|≈

0.66，而φ2(x)是x的減函數(shù)。1.28≈φ(1.5)≤φ(x)≤φ2(1)

=1.5，在［1,1.5］上φ2(x)滿足定理3.1條件。因此，若取x0∈［1,1.5］，則迭代格式產(chǎn)生的迭代序列收斂。對于函數(shù)φ3(x)：φ3(x)=，設(shè)［a,b］=［1，2］不能保證a≤x≤b時，a≤φ3(x)≤b，同時，也沒有區(qū)間

［a,b］，使|φ

3′

(x)|<1成立，故不能用定理3.1來保證其收斂性。

對φ4(x)、φ5(x)可作類似分析，可估計得|φ

4′

(x)|

<0.15(1≤x≤2)，φ4(x)對應(yīng)的L值比φ2(x)對應(yīng)的L值要小，故由x=φ4(x)產(chǎn)生的迭代序列比由x=φ5(x)產(chǎn)生的迭代序列

收斂得快些。從以上分析可以看出，利用定理3.1分析區(qū)間［a,b］上迭代過程的收斂性是比較困難的。定理3.1給出的是區(qū)間

［a,b］上的收斂性，稱為全局收斂，下面我們討論局部收斂性的概念。

定義3.1對于x*=φ(x*)，若存在x*的一個閉鄰域

U(x*,δ)=［x*－δ,x*+δ］(δ>0),使得對任意

x0∈U(x*,δ)，由迭代格式xk+1=φ(xk)(k=0,1,2,…)產(chǎn)生的迭代序列{xk}都收斂到x*，則稱迭代過程xk+1=φ(xk)在x*的閉鄰域U(x*，δ)內(nèi)是局部收斂的。

定理3.2設(shè)φ(x)在x=φ(x)的不動點x*的某鄰域內(nèi)有一階連續(xù)導(dǎo)數(shù)，且|φ′(x*)|≤L<1，則迭代格式xk+1=φ(xk)

(k=0,1,2,…)具有局部收斂性。

證明因為|φ′(x*)|<1，又φ′(x)在x*的某個鄰域內(nèi)連續(xù)，故存在x*的某個鄰域U(x*,δ)，使得在此領(lǐng)域內(nèi)恒有|φ′(x*)|≤L<1，且對任意x∈U(x*,δ)有

|φ(x)－x*|=|φ(x)－φ(x*)|=|φ′(ξ)||x－x*|

≤L|x－x*|<|x－x*|<δ

從而也有φ(x)∈U(x*,δ)，根據(jù)定理3.1可知迭代格式xk+1=φ(xk)對任意x0∈U(x*,δ)均收斂，即具有局部收斂性。

例3.3用迭代法求方程x3－x2－1=0在區(qū)間［1.4,1.5］內(nèi)的根，要求精確到小數(shù)點后第4位。

解

(1)構(gòu)造迭代格式。方程x3－x2－1=0的等價形式為

迭代格式為

(2)由定理3.2可知在(1.4，1.5)內(nèi)有|φ′(x)|≤0.5<1，因此迭代序列收斂。

(3)計算結(jié)果見表3.3。最后，給出迭代格式的階的概念，它是衡量一種迭代法收斂快慢的標(biāo)志。

定義3.2設(shè)序列{xk}收斂到x*，記誤差ek=xk－x*，若存在實數(shù)P≥1及非零常數(shù)C>0,使得

則稱序列{xk}是P階收斂的，且C稱為漸近誤差常數(shù)。當(dāng)P=1且0<C<1時，稱{xk}為線性收斂；當(dāng)P>1時稱{xk}為超線性收斂；當(dāng)P=2時稱{xk}為平方收斂或二次收斂。

一般地，若由迭代格式xk+1=φ(xk)產(chǎn)生的序列{xk}是P階收斂的，我們就稱迭代格式xk+1=φ(xk)為P階收斂。

3.3加速迭代收斂的方法

3.3.1兩個迭代值組合的加速方法

將(3.3)式兩邊同時減去θx，得

(1－θ)x=φ(x)－θ(x)

當(dāng)θ≠0且θ≠1時，可將這個方程變形為

(3.7)相應(yīng)的迭代格式為

(3.8)

迭代格式(3.8)式也可寫成

(3.9)

對(3.9)式中的θ取不同的值或表達(dá)式，就可得到不同的迭代方法。選取特殊的θ，有可能使迭代加速。(k=0，1，2，…)(k=0，1，2，…)取θ=－1，則(3.8)式變成

(3.10)

下面的例子說明這種迭代格式的確能加速收斂。(k=0，1，2，…)

例3.4用(3.9)式及例3.2中的φ2(x)，求方程

x3+4x2－10=0在［1,2］上的根x*。

解對仍取x0=1.5,

則利用(3.10)式計算的結(jié)果如表3.4所示。與例3.2對比,可看出(3.10)式的確能加速收斂。需要指出的是，若{xk}單調(diào)趨于x*時，(3.10)式不能加速收斂，只有當(dāng)0≥φ′≥－L>－1且L較大時，加速效果才會明顯。

由(3.8)式有：再令，則上式變?yōu)?/p>

xk+1=(1－ω)xk+ωφ(xk)

ω稱為松馳因子，上述方法稱為松馳迭代法。用松馳迭代法計算時要確定松馳因子ω，從理論上可以證明，取

最有效，但在實際應(yīng)用上不太方便，因為每迭代一次,松馳因子都要改變。實際應(yīng)用時用φ′(x0)來近似代替φ′(xk)，也能達(dá)到較好的效果。

例3.5求方程x=e－x在x=0.5附近的一個不動點，要求精度達(dá)到10－8。

解方法一：一般迭代法。取

φ(x)=e－x

(x∈［0.5,0.6］)

令

f(x)=x－e－x

容易驗證f(x)=0在［0.5,0.6］內(nèi)有唯一根x*。又|φ′(x)|=e－x,當(dāng)x∈［0.5,0.6］時,|φ′(x)|≈0.607<1，故迭代格式

所產(chǎn)生的迭代序列必收斂。取x0=0.5時的計算結(jié)果見表3.5。方法二：應(yīng)用加速迭代公式。取θ=－0.566≈φ′(0.5)，

則加速迭代公式為

取=0.5時的計算結(jié)果見表3.6。由表3.6可知，只要迭代5次便可得到結(jié)果,因此方法二與方法一相比,加速效果更加明顯。3.3.2三個迭代組合的加速方法

在由兩個迭代值組合的加速方法中，需要計算φ′(x)≈θ，而在實際計算中，導(dǎo)數(shù)的求值比較麻煩，因而想把θ去掉。

下面,我們從幾何意義上尋求一種解決途徑。由初值x0出發(fā),計算出,后，便可在曲線y=φ(x)上找到兩個點和,見圖3-5。用直線連接P0和P1兩點，將它與直線y=x的交點設(shè)為P3，則P3點的坐標(biāo)(x1，y1)應(yīng)滿足：圖3-5由此式解出x1，得

將x1視為新的初值,重復(fù)上述步驟可得其中，，?？梢?，其一般形式由xk，，組合而成。

或?qū)懗?/p>

(3.11)這個方法稱為艾特肯(Aitken)加速收斂法。

若記yk=φ(xk)，zk=φ(yk)(k=0,1,2,…)，則(3.11)式可以寫成如下所謂的斯蒂芬森(Steffensen)迭代法：

(k=0，1，2，…)

(3.12)

例3.6用斯蒂芬森迭代法求方程x3－x2－1=0在區(qū)間［1.4,1.5］內(nèi)的根，要求精確到小數(shù)點后第四位。

解由斯蒂芬森迭代格式((3.12)式)，得計算結(jié)果如表3.7所示。由表3.7可知，第二次迭代結(jié)果已經(jīng)滿足精度要求，故取x*≈1.4656。

3.4牛頓迭代法

牛頓迭代法適用求方程f(x)=0的單根、重根等情形，下面進(jìn)行討論。

1.單根情形的牛頓迭代法

我們假設(shè)方程f(x)=0在其根x*的某個領(lǐng)域U(x*，δ)內(nèi)有一階連續(xù)導(dǎo)數(shù)，且f′(x*)≠0。

要求f(x)=0的根x*，關(guān)鍵問題是要把f(x)=0轉(zhuǎn)化為等價形式x=φ(x)，并使φ(x)滿足3.3節(jié)中定理3.1或定理3.2的條件。一個較為自然的選擇是取φ(x)=x+Cf(x)，(其中,C為非零常數(shù))。顯然f(x*)=0當(dāng)且僅當(dāng)x*=φ(x*)。為了加速不動點迭代過程的收斂速度，應(yīng)盡量使迭代函數(shù)φ(x)在x=x*處有更高階導(dǎo)數(shù)為零，而φ′(x)=1+Cf′(x)，要使φ′(x*)=0，就有

C=－1/f′(x*)，但是x*未知，因而C值不確定。若令φ(x)=x+h(x)f(x)，可由φ′(x*)=0來確定h(x)的結(jié)構(gòu)，根據(jù)

φ′(x*)=1+h′(x*)f(x*)+h(x*)f′(x*)=1+h(x*)f′(x*)=0

可得由于假定f′(x*)≠0，且f′(x)連續(xù)，因此當(dāng)h(x)=－1/f′(x)時，就能保證φ′(x*)=0，即令

，從而有迭代格式:

(k=0，1，2，…)

(3.13)

此迭代方法稱為牛頓—拉夫森(NewtonRaphson)方法，簡稱牛頓法。在牛頓法中，每次都要計算f′(xk),比較麻煩，因為在x*的領(lǐng)域U(x*,δ)內(nèi)取x0，以至于x1,x2,…都在此鄰域內(nèi)，從而當(dāng)δ較小時，用f′(x0)近似代替f′(xk)，就有迭代格式:

(3.14)

此迭代方法簡稱為簡化牛頓法。

2.牛頓法的幾何意義

方程f(x)=0的根x*就是曲線y=f(x)與x軸交點的橫坐標(biāo)，x*的某個近似值過曲線y=f(x)上相應(yīng)點Pk(xk,f(xk))的切線方程為

Y=f(xk)+f′(xk)(X－xk)

此切線與x軸交點的橫坐標(biāo)記為xk+1，它作為x*的一個新的近似值，即有

因此，牛頓法也稱切線圖法，其基本思想是將非線性方程f(x)=0的求解轉(zhuǎn)化為一次次用切線方程來求解。牛頓法和簡化牛頓法的幾何意義如圖3-6和圖3-7所示。圖3-6

圖3-7

3.牛頓迭代法的收斂性定理

定理3.3設(shè)x*是方程f(x)=0的根，在x*的某個開區(qū)間內(nèi)f″(x)連續(xù)且f′(x)≠0，則存在δ>0，當(dāng)x0∈［x*－δ,x*+δ］時，由牛頓迭代法(3.13)式產(chǎn)生的序列{xk}是以不低于二階的收斂速度收斂到x*。證明略。

定理3.4對于方程f(x)=0，設(shè)f(x)在［a,b］上有二階連續(xù)導(dǎo)數(shù)且滿足下述條件：

(1)f(a)f(b)<0;

(2)f′(x)≠0,f″(x)≠0,對任意x∈［a,b］;

(3)存在x0∈［a,b］,使f(x0)f″(x0)>0,

則由牛頓迭代法(3.14)式產(chǎn)生的迭代序列{xk}收斂到f(x)=0的根x*，且

證明

f(x)在［a,b］上連續(xù)，由條件(1)、(2)可知f(x)=0在［a,b］內(nèi)有唯一根x*。

由條件(1)和f″(x)≠0可知，有如下四種情形：

(1)f(a)<0，f(b)>0,當(dāng)x∈［a,b］時f″(x)>0；

(2)f(a)<0,f(b)>0，當(dāng)x∈［a,b］時f″(x)<0;

(3)f(a)>0,f(b)<0,當(dāng)x∈［a,b］時f″(x)>0;

(4)f(a)>0,f(b)<0,當(dāng)x∈［a,b］時f″(x)<0。下面我們給出情形(1)的證明。

由中值定理知，存在ζ∈(a,b)使得,

由于在［a,b］上f′(x)≠0，故在［a,b］上恒大于零，從而f(x)在［a,b］上單調(diào)增加。

由x0∈［a,b］且f(x0)f″(x)>0知f(x0)>0，而f(x*)=0，從而x0>x*，由牛頓迭代法知。又由泰勒展開式得

(ζ0介于x與x0之間)把x=x*代入上式，并由f(x*)=0得

其中,介于x0與x*之間，也就有由于已假設(shè)當(dāng)x∈［a,b］時，有f″(x)>0，f′(x)>0,

以及前面已證明x1<x0，因此有x*<x1<x0。

一般地假設(shè)x*<xk<xk－1，下面證明也有x*<xk+1<xk。

由假設(shè)x*<xk知f(xk)>f(x*)=0，且由牛頓迭代法有

，再由泰勒展開式有:

(ζk介于xk與x之間)把x=x*代入上式，并由f(x*)=0得

(介于xk與x*之間)

也有:

(3.15)由歸納法可知，數(shù)列{xk}單調(diào)下降且有下界x*，由單調(diào)有界原理可知{xk}必有極限l，對迭代公式

兩邊取k→∞的極限。由f(x)、f′(x)的連續(xù)性及f′(x)>0知f(l)=0，由根的唯一性知l=x*。由(3.15)式有:

再由f′(x)、f″(x)的連續(xù)性及f′(x)≠0可得

由定理3.4及其證明可看出牛頓迭代法對其初值x0的選取帶有挑選性。

定理3.5對方程f(x)=0，若f(x)在［a,b］上有連續(xù)的二階導(dǎo)數(shù)且滿足下述條件：

(1)f(a)f(b)<0;

(2)對任何x∈［a,b］,有f′(x)≠0、f″(x)≠0;

(3)，

則對任何x0∈［a,b］，牛頓迭代法產(chǎn)生的序列{xk}都收斂于f(x)=0的根x*。

定理3.5的幾何意義見圖3-8。圖3-8條件(3)保證了從x*兩側(cè)任取x0，如x0=a或b所得到的迭代序列{xk}均在［a,b］內(nèi)。

例3.7設(shè)a>0，試建立求二次方程x2－a=0的根的收斂牛頓迭代格式，并對a=3給出計算結(jié)果。

解令f(x)=x2－a(x>0)

則f′(x)=2x>0，由牛頓迭代格式得

(3.16)

此公式可以理解為xk是的近似值，也是的近似值，它們兩個的算術(shù)平均值將是更好的近似值。(k=0，1，2，…)下面證明迭代格式(3.16)式對于任意初始值x0>0都是平方收斂的。

由于

從而得

(3.17)

(3.18)兩式相除得

依次遞推可得(k=0,1，2，…)令，則，得

，顯然對任意x0>0，都有|q|<1，故

。令，則由(3.17)式可得

(k→∞)

從而迭代格式(3.16)式為平方收斂的。當(dāng)a=3時，(3.16)式變?yōu)?/p>

取x0=1,得

x1=2.000000000,

x2=1.750000000

x3=1.732142857,

x4=1.732050810

x5=1.732050808,

x6=1.732050808

x5與精確解取10位有效數(shù)字時完全相同。(k=0，1，2，…)

例3.8用牛頓法建立計算(c>0)近似值的迭代公式。

解令x=，則可將以上問題化為求解方程

f(x)=x2－c=0正根的問題。

牛頓迭代格式為

因為x>0，f′(x)>0,f″(x)=2>0,所以任取x0>作為初始值，迭代序列必收斂于，故迭代公式是收斂的。

3.5弦割法與拋物線法

3.5.1弦割法

牛頓法是二階方法，每步都要計算f(xk)和f′(xk)，但f′(xk)的計算比較困難，而牛頓法的一種修正是用xk-1、xk兩點處的割線斜率代替xk處的切線斜率f′(xk)，即得到：

(3.19)

這就是弦割法的迭代公式，其幾何意義如圖3-9所示。圖3-9弦割法不是用f(x)的切線方程與x軸交點的橫坐標(biāo)近似代替f(x)零點，而是用通過兩點(xk－1,f(xk－1))和(xk,f(xk))的弦所在直線(簡稱弦線)與x軸交點的橫坐標(biāo)近似代替f(xk)的零點。過(xk-1,f(xk-1))和(xk,f(xk))的弦線方程為

其零點為

把X用xk+1表示即得到迭代格式(3.19)式，它又稱為雙點弦割法，需要兩個初值。為了給出弦割法的收斂性條件，先證明引理3.1。

引理3.1設(shè)f(x)在其零點x*的某個領(lǐng)域U(x*,δ)=

［x*－δ,x*+δ］內(nèi)具有二階連續(xù)導(dǎo)數(shù)，且f′(x)≠0，又設(shè)xk-1和xk∈U(x*,δ),且xk-1、xk、x*互異，記ek=xk－x*，則

其中,xk+1由弦割法(3.19)式產(chǎn)生,ηk和ξk介于min［xk-1,xk,x*］和max［xk-1,xk,x*］之間。

證明記過(xk-1,f(xk-1))和(xk,f(xk))的直線方程為L(x)，則

其中,η介于xk-1與xk之間。由于f(x*)=0，故其中,ηk介于xk-1與xk之間。另一方面，由于xk+1是L(x)=0的根，因此

其中,ξk介于xk-1與xk之間。聯(lián)立上述兩式得

其中,ηk和ξk均在xk-1,xk,x*所界定的范圍內(nèi)，當(dāng)xk-1,xk∈U(x*,δ)時，ηk和ξk∈U(x*,δ)。對弦割法,有局部收斂定理3.6。

定理3.6設(shè)f(x)在其零點x*的鄰域U(x*,δ)=［x*－δ,x*+δ］(δ>0)內(nèi)有二階連續(xù)導(dǎo)數(shù)，f′(x*)≠0，則當(dāng)x0∈U(x*,δ)時，由弦割法(3.19)式產(chǎn)生的序列{xk}收斂于x*，且收斂的階為1.618。

證明分三步進(jìn)行證明。

(1)證明存在x*的鄰域U(x*,δ)=［x*－δ,x*+δ］，當(dāng)

x0,x1∈U(x*,δ)時，由(3.19)式產(chǎn)生的xk(k≥2)均在U(x*,δ)內(nèi)。由于f′(x)，f″(x)在U(x*,δ)內(nèi)連續(xù)，且f′(x*)≠0，

故存在ε>0,當(dāng)x∈U(x*,ε)=［x*－ε,x*+ε］時，有f′(x)≠0。令則對一切x0,x1∈U(x*,δ)，由引理3.1知|e2|≤Mε|e0||e1|。

取δ>0，且δ<ε，δMδ<1,則當(dāng)x0,x1∈U(x*,ε)時，有|e0|<δ,|e1|<δ。再由引理3.1知|e2|≤Mδ·δ·δ=δMδδ<δ，]即x2∈U(x*,ε)。一般地，若xk-1,xk∈U(x*,ε)，由引理3.1可知

|ek+1|≤Mδ|ek-1||ek|≤Mδδ·δ<δ

即得xk+1∈U(x*,δ)。

(2)證明序列{xk}收斂。由引理3.1及遞推關(guān)系知，當(dāng)k≥1時，有

|ek|≤Mδ|ek-2||ek-1|≤Mδδ|ek-1|≤(δMδ)2|ek-2|

≤…≤(δMδ)k|e0|

因δMδ<1，所以k→∞時,ek→0，即{xk}收斂于x*。

(3)收斂階分析。令，顯然有M*≤Mδ，因為{xk}收斂，所以當(dāng)k充分大時，引理3.1的結(jié)論可寫成

|ek+1|≈M*|ek-1||ek|

(3.20)

令dk=M*|ek|，d=Mδ·δ，顯然有dk≤d<1，對(3.20)式兩邊同乘以M*可得

dk+1≈dkdk-1

(3.21)設(shè)

(k=0，1，2，…)，則{mk}滿足差分方程:

mk+1=mk+mk-1

(k=0,1,2,…)

(3.22)

式中，初始條件m0，m1由迭代初值決定。由d0≤d，d1≤d知，差分方程(3.22)式的初始條件m0≥1,m1≥1，其特征方程為λ2－λ－1=0，特征根為因而mk可以表示為

mk=α1λk1+α2λk2

(3.23)

其中，α1,α2由m0≥1，m1≥1來確定，從而得到因為|λ1|>|λ2|，且α1≠0，故當(dāng)k充分大時有mk≈α1λk1，因此所以有

這表明弦割法的收斂階p=1.618。

弦割法不必計算f′(xk)，但其收斂階要比牛頓法低。

定理3.7設(shè)f″(x)在區(qū)間［a,b］上連續(xù)，且滿足下述三點:

(1)f(a)f(b)<0;

(2)對任何x∈［a,b］,有f′(x)≠0,f″(x)≠0;

(3)

則對任意初始值x0,x1∈［a,b］，弦割法產(chǎn)生的迭代序列{xk}收斂于f(x)=0的唯一根x*。弦割法與斯蒂芬森迭代法有著密切關(guān)系。

設(shè)f(x)=0的等價方程為

x=φ(x),

yk=φ(yk),

zk=φ(yk)=φ(φ(xk))

對g(x)=x－φ(x)=0在(xk,g(xk))，(yk,g(yk))兩點處使用弦割法，得到的割線方程為此割線與x軸交點的橫坐標(biāo)為xk+1，則有：

(3.24)

這就是斯蒂芬森迭代格式。此迭代格式稱為斯蒂芬森方法，它是牛頓法和弦割法的一種修正。這個迭代公式不需要計算f′(xk)，也不需要兩個初值，是一種單點迭代法，在一定條件下可以證明它還是二階收斂的。

在弦割法中若固定x0，讓xk變動，即xk+1，…，得到簡化弦割法迭代法：

也稱單點弦割法。單點弦割法是線性收斂的，其迭代函數(shù)為

例3.9用弦割法和斯蒂芬森迭代式求方程x3+4x2－10

=0在［1,2］上的根，要求|xk+1－xk|<10－9。

解

(1)用弦割法求解。

設(shè)f(x)=x3+4x2－10，則f(1)=－5，f(2)=14，取x0=1，x1=2，用(3.19)式計算，結(jié)果如表3.8所示。

(2)用斯蒂芬森方法求解。

取x0=1.5，利用(3.24)式計算，結(jié)果如表3.9所示。3.5.2拋物線法

弦割法以過兩點(xk-1,f(xk-1))和(xk,f(xk))的直線與x軸交點的橫坐標(biāo)作為xk+1，我們想用過三點(xk-2,f(xk-2))，(xk-1,f(xk-1))，

(xk,f(xk))的拋物線:

(3.25)

與x軸交點的橫坐標(biāo)作為xk+1，是否會比用直線得到更好的近似點？用這種方法得到的迭代法稱為拋物線法，也稱Mliiller方法。一條拋物線有兩個實零點時，我們?nèi)∨cxk較近的那個零點作為xk+1。另外，關(guān)于拋物線法有計算其零點xk+1的規(guī)范計算公式。令

(3.26)則過三點(xk-2，f(xk-2))，(xk-1，f(xk-1))，(xk，f(xk))的拋物線(3.25)式可表示成λ的二次函數(shù):

(3.27)

其中,

(3.28)(3.27)式的兩個零點為

(3.29)

從λ的表達(dá)式可知，取模較小的λ得到的xk+1與xk較為接近，故取(3.29)式中分母較大的零點作為λ4，即

(3.30)由λ的表達(dá)式知，x*的近似值為

xk+1=xk+λ4(xk－xk－1)

(3.31)

總之，拋物線法的規(guī)范計算步驟為

(1)由(3.26)式計算λ3，δ；

(2)由(3.28)式計算a，b，c；

(3)由(3.30)式計算λ4；

(4)由(3.31)式計算xk+1；

(5)由xk-1，xk，xk+1分別代替xk-2，xk-1，xk；用

f(xk-1)，f(xk)，f(xk+1)分別代替f(xk-2)，f(xk-1)，f(xk)作下一步迭代。

拋物線法的幾何意義如圖3-10所示。圖3-10關(guān)于拋物線法有收斂性定理3.8。

定理3.8設(shè)f(x)在其零點x*的某個鄰域內(nèi)有三階連續(xù)導(dǎo)數(shù)且f′(x*)≠0，則存在x*的一個鄰域U(x*,δ)=［x*－δ,x*+δ］(δ>0)，當(dāng)x0，x1，x2∈U(x*,δ)時，由拋物線法產(chǎn)生的序列{xk}收斂到x*，且

拋物線法對初值的選取范圍較牛頓法和弦割法寬，用弦割法求f(x)=0的根不收斂時，用拋物線法求根仍可能收斂，但收斂速度較慢，拋物線法的缺點是每一步迭代所需的計算量大。

例3.10用拋物線法求方程x3+4x2－10=0在［1,2］上的根，要求|xk+1－xk|<10－9。

解取初始值x0=1.0，x1=1.5，x2=2.0，按計算步驟，計算結(jié)果如表3.10所示。與例3.9相比，拋物線法比弦割法收斂快，但比牛頓法收斂慢。

3.6非線性方程組零點的迭代方法

在科學(xué)研究或工程計算中經(jīng)常會遇到求解多個變量的非線性方程組的根問題，如在微分方程穩(wěn)定性理論中要研究解的大范圍性質(zhì)，首先要求微分方程所定義的向量場的平衡點，即要求非線性方程組的根。非線性方程組是指n個變量n個方程的方程組：

(3.32)

其中，fi(x1,…，xn)(i=1，2，…，n)是定義在

中的n個自變量x1，…，xn的實值函數(shù)，且fi(x1，…，xn)中至少有一個是非線性的。若fi(x1，…，xn)全為線性函數(shù)，則稱為線性方程組。對于n=1，則為前面已經(jīng)討論的單個方程求根問題。下面討論中假設(shè)n≥2?？梢园亚髥蝹€非線性方程根的方法推廣到求非線性方程組的根上來。由于非線性方程組具有比單個方程更復(fù)雜的性質(zhì)，且有比單個方程求解方法更多的新方法，因此有必要給出求解非線性方程組根的基本數(shù)值方法。為了方便討論，引進(jìn)向量記法。令

x=(x1,x2,…，xn),

F(x)=(f1(x),f2(x),…，fn(x))T

則方程組(3.32)可以寫成向量形式

F(x)=0

(3.33)

其中,

，即F是定義在區(qū)域上且取值于Rn的n維實值向量函數(shù)。若存在x*∈D使得F(x*)=0，則稱x*是方程組(3.33)的根。3.6.1實值向量函數(shù)的基本概念與性質(zhì)

設(shè)F:D

Rn→Rn，即

當(dāng)m=1時，F(xiàn)(x)=f(x1,x2,…，xn)就是多元函數(shù)。因此，關(guān)于F(x)的連續(xù)與可導(dǎo)等概念是多元函數(shù)f(x1，x2，…，xn)連續(xù)與可導(dǎo)的概念的推廣。

定義3.3對于F(x)，若對任給ε>0，存在δ>0，使得當(dāng)x∈U(x0,δ)={‖x－x0‖<δ}D

時，有

‖F(xiàn)(x)－F(x0)‖<ε

則稱F(x)在點x0∈int(D)連續(xù)。若F(x)在D內(nèi)每一點都連續(xù)，則稱F(x)在區(qū)域D內(nèi)連續(xù)。如果任給ε>0，存在δ=δ(ε)>0，使得對任何x,y∈

Ω

D，只要‖x－y‖<δ，就有

‖F(xiàn)(x)－F(y)‖<ε

則稱F(x)在Ω上一致連續(xù)。

顯然，若F(x)在Ω上一致連續(xù)，則F(x)在Ω上一定連續(xù)，反之不一定成立，但是若F(x)在有界閉區(qū)域上連續(xù)，則它也是一致連續(xù)的。

定義3.4設(shè)F(x)為定義在有界閉區(qū)域上的函數(shù)，若存在常數(shù)L>0，使得對任何x,y∈都有:

‖F(xiàn)(x)－F(y)‖≤L‖x－y‖p

成立，其中0<p<1，則稱F(x)在區(qū)域上是赫爾德(Holder)連續(xù)的。如果p=1，則稱F(x)在區(qū)域上是李譜希茲(Lipschitz)連續(xù)的。

顯然李譜希茲連續(xù)可以推出赫爾德連續(xù)，赫爾德連續(xù)可以推出一致連續(xù)。

定義3.5設(shè)F(x)定義在D上，對x∈int(D)及任意h∈Rn，若存在A(x)∈Rm×n，使得

(3.34)

則稱F(x)在x處可微，稱A(x)為F(x)在點x處的導(dǎo)數(shù)，記為F′(x)=A(x)。上述定義的導(dǎo)數(shù)稱為弗雷歇(Frechet)導(dǎo)數(shù)，并稱為F-導(dǎo)數(shù)。如果F(x)在D內(nèi)每點都可導(dǎo)，則稱F(x)在D內(nèi)可導(dǎo)。由向量范數(shù)的等價性，(3.34)式中可任取一種向量范數(shù)。

對m=1情形，即F(x)=f(x1,x2,…，xn)，有如下結(jié)論。

定理3.9設(shè)f:D

Rn→R，在點x∈int(D)可導(dǎo)，則f在點x處的偏導(dǎo)數(shù)(i=1，2，…，n)存在，且

證明記αT(x)=(α1(x),α2(x),…，αn(x))，由F-導(dǎo)數(shù)可知依次取h=hjej，由上式可得

(j=1，2，…，n)

則有

(i=1，2，…，n)從而得

即f(x)的導(dǎo)數(shù)就是f(x)的梯度f(x)=gradf(x)。

對于F：D

Rn→Rm，如果F(x)在點x處可導(dǎo)，對每個分量fi(x)應(yīng)用定理3.9的結(jié)論，可知從而可得F(x)在點x處的導(dǎo)數(shù)就是F(x)的雅可比矩陣，即關(guān)于實值向量函數(shù)有如下導(dǎo)數(shù)性質(zhì)和中值定理。

定理3.10對F：D

Rn→Rm,x∈D：

(1)若F(x)在點x處可導(dǎo)，則F(x)在點x處連續(xù)；

(2)若F(x)在D內(nèi)可導(dǎo)，D為凸區(qū)域，則存在ξi∈(0，1)

(i=1，2，…，m)，使得

(3)對任意x,y,z∈D,有

證明略。

定理3.11設(shè)F:D

Rn→Rm,D為開的凸區(qū)域，F(xiàn)(x)在D內(nèi)可導(dǎo)，若對任意x,y∈D，存在常數(shù)α>0，使得

‖F(xiàn)′(y)－F′(x)‖≤α‖y－x‖

(3.35)

則對任何x,y∈D,有

(3.36)

證明定義函數(shù)f:［0,1］R→Rm

為

f(t)=F(x+t(y－x))

(t∈［0,1］)

令h(t)=(t′－t)(y－x)，其中x,y固定。當(dāng)t′→t時，由F(x)可導(dǎo)得

f′(t)=F′(x+t(y－x))(y－x)

(t∈［0,1］)

于是對t∈［0,1］,由(3.35)式有

‖f′(t)－f′(0)‖≤‖F(xiàn)′(x+t(y－x))－F′(x)‖‖y－x‖

≤αt‖y－x‖2從而得

則(3.36)式成立。

定義3.6若F:D

Rn→Rm的各個分量fi(x)(i=1,2,…，m)的二階偏導(dǎo)數(shù)在x∈int(D)處連續(xù)，則稱F(x)在x處二次連續(xù)可微。

定義3.7向量序列{xk}收斂于向量x*，ek=xk－x*≠0

(k=0,1,2,…)，若存在常數(shù)p≥1和常數(shù)C>0，使極限存在，或者當(dāng)k≥K(K是某個正整數(shù))時，有

‖ek+1‖≤C‖ek‖p

成立，則稱序列{xk}是p階收斂。其中，C為收斂因子。當(dāng)p=1時，稱序列{xk}是線性收斂的，此時必有0<C<1；當(dāng)p>1時，稱序列{xk}是超線性收斂的；當(dāng)p=2時，稱序列{xk}

是平方或二次收斂的。

前面的討論對m=n也成立。在非線性方程組的數(shù)值解法研究中，主要應(yīng)用m=n的結(jié)論。3.6.2壓縮映射原理與不動點迭代法

把非線性方程組F(x)=0改寫成與之等價的形式

x=φ(x)

(3.37)

其中,φ:D

Rn→Rn。若x*∈D滿足x*=φ(x*)，則稱x*為函數(shù)φ(x)的不動點。因此，求方程F(x)=0的根就轉(zhuǎn)化為求φ(x)的不動點。

定義3.8選取x(0)∈D作為初始向量，由(3.37)式構(gòu)造迭代格式：

xk+1=φ(x(k))

(k=0，1，2，…)

(3.38)

則(3.38)式稱為求方程組(3.37)的不動點迭代法或簡單迭代法，φ(x)稱為迭代函數(shù)。

定義3.9設(shè)φ:D

Rn→Rn，若存在常數(shù)L∈(0,1)，使得對任意x,y∈D0

D，都有

‖φ(x)－φ(y)‖≤L‖x－y‖(3.39)

則稱φ(x)在D0上是壓縮映射的，L為壓縮系數(shù)。

從定義可知，若φ(x)在D0是壓縮映射的，則φ(x)在D0上為連續(xù)函數(shù)。其次，壓縮與所取的范數(shù)有關(guān)，即φ(x)對某一種范數(shù)是壓縮的而對另一種范數(shù)可能不是壓縮的。

定理3.12(壓縮映射原理)設(shè)φ：D

Rn→Rn在閉區(qū)域

D0

D上滿足：

(1)φ把D0映入它自身，即φ(D0)

D0；

(2)φ在D0上是壓縮映射，壓縮因子是L，

則下列結(jié)論成立：

(1)φ在D0上存在唯一不動點x*；

(2)對任意初始值x(0)∈D0，不動點迭代法(3.38)式產(chǎn)生的序列{x(k)}

D0，且收斂于x*；

(3)有如下誤差估計式：

證明由x(0)∈D0及條件(1)知，迭代格式產(chǎn)生的序列{x(k)}D0。又由條件(2)得到

‖x(k+1)－x(k)‖=‖φ(x(k))－φ(x(k－1))‖

≤L‖x(k)－x(k－1)‖≤…≤Lk‖x(1)－x(0)‖

從而對正整數(shù)m≥1，有

(3.40)因為L∈(0，1)，由柯西(Cauchy)收斂原理知，序列{x(k)}收斂。又由于D0是閉區(qū)域，因此存在x*∈D0使得。由φ(x)的壓縮性、連續(xù)性，有

故x*是φ(x)的不動點。

若x*，是φ(x)的兩個不動點，則由于φ(x)在D0內(nèi)為壓縮映射，于是有

從而必有

，即φ(x)的不動點唯一。在(3.40)式兩邊令m→∞，即有

又當(dāng)m≥1時,有:再令m→∞,有

在定理條件下，容易得到不動點迭代格式(3.38)式產(chǎn)生的序列{x(k)}滿足:

‖x(k+1)－x*‖=‖φ(x(k))－φ(x*)‖≤L‖x(k)－x*‖

其中,L∈(0,1)，因而序列{x(k)}是線性收斂的。實際應(yīng)用時，由于定理3.12中φ(x)為壓縮映射這一條件難以驗證，因而通常情況下，應(yīng)用一個更強(qiáng)的條件“φ在D0上連續(xù)可微，且對任何x∈D0都有‖φ′(x)‖≤L<1”來代替。

其中，矩陣范數(shù)‖φ′(x)‖是向量范數(shù)的從屬范數(shù)。

對不動點迭代格式(3.38)式，當(dāng)x(0)在不動點x*附近時，有下面局部收斂定理。

定理3.13若映射φ(x)在不動點x*的δ鄰域

U(x*,δ)={x|‖x－x*‖≤δ}D0

內(nèi)滿足條件：對任何x∈U(x*,δ),都有:

‖φ(x)－φ(x*)‖≤L‖x－x*‖

(0<L<1)

則對任意x(0)∈U(x*,δ)，由不動點迭代格式(3.38)式產(chǎn)生的序列{x(k)}收斂到x*，且有估計式:

‖x(k)－x*‖≤Lk‖x(0)－x*‖

(k=0,1，2，…)

定理3.14設(shè)φ(x)在不動點x*處可微，且φ′(x*)的譜半徑ρ(φ′(x*))<1，則存在開球：B0={x|‖x－x*‖<δ,δ>0}

D，使得對任意x(0)∈B0，由迭代格式(3.38)式產(chǎn)生的序列{x(k)}B0，且收斂到x*。

定理3.13及定理3.14的證明略去，有興趣的讀者可參考相關(guān)文獻(xiàn)。

例3.11用不動點迭代格式(3.38)式求解下列非線性方程組：

解將方程組改寫成等價形式x=φ(x)，其中,設(shè)B0={(x1,x2)|0≤x1,x2≤0.5}，容易驗證:

0≤φ1(x)<0.5,

0≤φ2(x)<0.5

故有φ(B0)B0，對任意x,y∈B0,有于是有

故φ(x)滿足壓縮條件。根據(jù)壓縮映射原理，φ(x)在B0內(nèi)存在唯一不動點x*。取x(0)=(0,0)T，由x(k+1)=φ(x(k))(k=0,1,2,…)迭代，當(dāng)‖x(k+1)－x(k)‖1<10－9

時結(jié)果為由于

因此

故

ρ(φ′(x*))≤0.25<1

表明定理3.14條件成立。不動點迭代格式類似于解線性代數(shù)方程組的雅可比算法。同樣，可以給出求解非線性方程組時完全類似于線性代數(shù)方程組迭代格式中的GS-迭代法、SOR-迭代法和SSOR-迭代法等公式，只不過在非線性方程組求解迭代格式的迭代過程中，由于非線性的困難，有些公式的形式比較復(fù)雜，難以得到收斂性和收斂階的判定條件。SOR-迭代法和牛頓法聯(lián)合使用，可以得到Newton-SOR法、非線性SOR-Newton法等，有興趣的讀者可參考相關(guān)文獻(xiàn)。3.6.3牛頓迭代法

在非線性方程f(x)=0求根時，用泰勒展開法將非線性方程近似地化為線性方程得到過