第2章非線性方程求根2.1引言2.2二分法2.3迭代法2.4牛頓迭代法與弦割法 2.1引言

科學(xué)研究及生產(chǎn)實踐中的許多問題常歸結(jié)為求解非線性方程f(x)=0根的問題，對求解非線性方程的方法進行研究具有重要的實用價值。根據(jù)數(shù)學(xué)相關(guān)理論可知,方程通常分為代數(shù)方程和超越方程。代數(shù)方程即為多項式方程，如x3+4x2－10=0，而超越方程不僅要對未知數(shù)和一些常數(shù)施行有限次代數(shù)運算，而且還要施行有限次指數(shù)、對數(shù)、三角函數(shù)等運算，如e－x－sinx=0。對于代數(shù)方程的求解，理論上已經(jīng)證明,當次數(shù)大于等于5時無精確的求根公式，而對于一般的超越方程更沒有求根公式可以利用。在實際問題中，求方程的根時，不一定要得到根的準確值，而只需求得滿足一定精度的近似值即可，因此本章將介紹求解非線性方程的近似根的方法，并只討論近似根為實根的情況。求解方程的近似根包括兩個步驟：第一步是求根的隔離區(qū)間，第二步是根的精確化。求根的隔離區(qū)間，即確定根所在的區(qū)間，使方程在這個小區(qū)間內(nèi)有且只有一個根，這一過程稱為根的隔離，而且所求根的隔離區(qū)間越小越好。根的精確化是在已知一個根的近似值后，用某種方法把此近似值精確化，使其滿足給定的精度要求。下面介紹求根的隔離區(qū)間的描圖法與逐步搜索法，而根的精確化將在以后各節(jié)中進行介紹。

(1)描圖法獲得根的隔離區(qū)間。根據(jù)方程f(x)=0，畫出曲線y=f(x)的簡圖，觀察曲線y=f(x)與x軸的交點的大致位置，從而確定根的隔離區(qū)間；或?qū)⒎匠痰葍r變換為y1(x)=y2(x)，畫出曲線y1(x)和y2(x)的簡圖，從兩條曲線交點橫坐標位置確定根的隔離區(qū)間。

例2－1用描圖法求方程3x－1－cosx=0的根的隔離區(qū)間。

解將方程等價變換為3x－1=cosx

令y1(x)=3x－1，y2(x)=cosx，作出該兩條曲線的圖形如圖2.1所示。從圖中可以看出,y1(x)和y2(x)曲線交點的橫坐標在［1/3，1］內(nèi)，［1/3,1］即為所求方程根的隔離區(qū)間。圖2.1

y1(x)=3x-1和y2(x)=cosx的圖形(2)逐步搜索法獲得根的隔離區(qū)間。根據(jù)連續(xù)函數(shù)的界值定理，設(shè)f(x)在區(qū)間［a，b］內(nèi)連續(xù)，若f(a)和f(b)異號，則方程f(x)=0在［a，b］內(nèi)至少有一個根。據(jù)此，先確定方程f(x)=0的所有實根所在的大致區(qū)間，設(shè)為［a，b］，再按照選定的步長h=(b-a)/n(n為正整數(shù))，取點xk=a+kh(k=0，1，…，n)，逐次計算函數(shù)值f(xk)，依據(jù)函數(shù)值的異號及實根的個數(shù)即可確定根的隔離區(qū)間。

例2－2利用逐步搜索法確定方程x3－x－1=0的一個根的隔離區(qū)間。

解根據(jù)已知方程，令f(x)=x3－x－1則可得f(0)<0，f(2)>0，因此,在區(qū)間［0，2］之間至少有一個實根。取步長h=(2-0)/4=0.5，即n=4，則取點xk=a+kh(k=0，1，2，3，4)，逐次計算函數(shù)值f(xk)便可得其符號，見表2.1。表2.1例2－2的計算結(jié)果

根據(jù)表2.1的計算結(jié)果可知,方程在區(qū)間［1.0，1.5］內(nèi)必有一實根，且在該區(qū)間內(nèi)，f′(x)>0，表明方程x3－x－1=0在區(qū)間［1.0，1.5］內(nèi)有唯一實根，所以可取［1.0，1.5］為方程的一個根的隔離區(qū)間。需要說明的是,利用逐步搜索法得到的方程根的隔離區(qū)間長度與步長h有關(guān)，且隨著步長的減小，根的隔離區(qū)間長度也減小。這意味著步長h如果取的足夠小，則可得到任意精度的近似根，即可獲得方程的根。然而，單用逐步搜索法計算方程的根不是一個好的方法，因為當要求計算精度很高時，步長較小，搜索的步數(shù)增多，計算量增大；可以將逐步搜索法與其他方法，如二分法等聯(lián)合使用來計算方程的根。 2.2二分法

二分法的基本思想是取隔離區(qū)間的中點作為方程的近似根，通過計算區(qū)間的中點、中點函數(shù)值及區(qū)間端點函數(shù)值，判斷它們的符號，逐步對半縮小有根區(qū)間，直至將有根區(qū)間縮小到滿足根的精度要求，從而得到方程的近似根。下面介紹二分法的具體計算過程。它們的關(guān)系為并且，其中每一個區(qū)間都是前一個區(qū)間長度的一半，從而［an，bn］的長度為(2.1)當n→∞，這些區(qū)間將收斂于一點，該點即為所求方程的根。在實際應(yīng)用中，無法也沒必要去完成無窮的運算，只要能夠獲得滿足預(yù)定精度的近似值即可。若令區(qū)間［ak，bk］的中點xk=(ak+bk)/2為方程的根x*的近似值，則根據(jù)二分法的計算過程可以得到一個序列：x0，x1，x2，…，xk，由此可得(2.2)此即為以xk作為方程的近似根時的誤差。如果預(yù)定精度為ε，則只要(2.3)xk即可作為方程的近似根。據(jù)此給出二分法的具體步驟如下：(1)計算f(x)在區(qū)間［a，b］端點的函數(shù)值f(a)，f(b);表2.2例2－3的計算結(jié)果

從表2.2可以看出，當計算到k=7時，得到方程的近似根x7=1.364，其誤差為0.004,小于要求的誤差0.005，此即為滿足要求的方程的近似根。

根據(jù)二分法的計算過程可知，每一步計算得到區(qū)間的中點都需要判斷其誤差是否滿足要求，如果滿足要求則停止計算，否則繼續(xù)。這種情況下不知道需要計算的具體步數(shù),那么是否能夠事先計算出需要的步數(shù)，然后直接計算到具體的步數(shù)從而得到滿足誤差的根呢？回答是肯定的，推導(dǎo)二分法計算步數(shù)公式的過程如下：設(shè)第k步計算得到的方程的根x*的近似值為xk，可知其絕對誤差 ，若要求的誤差為ε，則有另外，根據(jù)式(2.1)有所以有，即對上式兩邊取對數(shù)可得，即(2.4)

例2－4根據(jù)例2－3的方程及其要求的精度，計算二分法的計算步數(shù)。

解根據(jù)題意知a=1，b=2，ε=0.5×10－2，將其代入式(2.4)得則k取7，即二分法對分的次數(shù)為7時即可滿足精度要求，這也與例2－3的計算結(jié)果相同。二分法計算過程簡單，程序容易實現(xiàn)，可在大范圍內(nèi)求根，但該方法收斂較慢(僅與一個以1/2為比值的等比級數(shù)相同)，且不能求重根和復(fù)根，一般用于求根的初始近似值。

2.3迭代法

2.3.1迭代法的概念及其過程

迭代法是一種逐步求精的方法，是解代數(shù)方程、超越方程、方程組、微分方程等的一種基本而重要的方法。迭代法采用的是逐次逼近的方法，首先給定一個粗糙的初始值，然后用一個迭代公式反復(fù)校正這個初始值，直到滿足預(yù)先給定的精度要求為止。下面介紹迭代法的具體計算過程。(2.5)由此得(2.6)式(2.6)即為迭代公式，也稱迭代格式。其中,函數(shù)φ(x)稱為迭代函數(shù)。 將初始值x0代入迭代公式(2.6)可得逐步代入式(2.6)迭代可得

例2－5用迭代法求方程2x3－x－1=0在0附近的根。

解

(1)根據(jù)方程將其等價變換為x=2x3－1，得迭代公式：xk+1=2x3k－1,取x0=0，代入迭代公式進行計算，其迭代過程如下：…

(2)根據(jù)方程將其等價變換為，得迭代公式： ,取x0=0，代入迭代公式進行計算，其迭代過程如下：

從計算結(jié)果可以看出，根據(jù)該迭代公式得到的數(shù)列{xn}]收斂到1.0000，則方程的根為1.0000。

在例2－5中，同樣的方程，不同的迭代公式，得到了不同的結(jié)果。也就是說,迭代函數(shù)φ(x)不同，相應(yīng)的數(shù)列{xn}收斂情況不同，可能收斂也可能不收斂，若收斂則稱迭代公式收斂(迭代收斂)，否則稱迭代公式發(fā)散(迭代發(fā)散)。而對于方程f(x)=0，如何選擇迭代函數(shù)，使由其得到的迭代公式是收斂的呢？下面討論迭代法的收斂性。2.3.2迭代法的收斂性定理

定理2.1設(shè)方程f(x)=0的等價形式為x=φ(x)，其中φ(x)在區(qū)間［a，b］上具有連續(xù)的一階導(dǎo)數(shù)，假設(shè)迭代函數(shù)滿足下列兩項條件：

條件1:對任意x∈［a，b］總有φ(x)∈［a，b］；

條件2:存在正常數(shù)L<1，使對任意x∈［a，b］有φ′(x)≤L。則有

結(jié)論1:方程f(x)=0在區(qū)間［a，b］內(nèi)有唯一根x*；

結(jié)論2:迭代公式xk+1=φ(xk)(k=0，1，2,…)對于任意的初始值x0∈［a，b］均收斂于方程的根x*；

結(jié)論3:

(2)證明結(jié)論2。根據(jù)迭代公式xk+1=φ(xk)(k=0，1，2,…)有根據(jù)拉格朗日中值定理有其中ξk為(xk－1，x*)內(nèi)的一點,所以有則利用條件2有即(k=1，2，3,…)遞推可得即由于L<1，故對上式兩端取極限可得即

也就是說迭代數(shù)列收斂，且迭代公式xk+1=φ(xk)收斂于方程的根。

(3)證明結(jié)論3。因為而根據(jù)結(jié)論2的證明有所以由此可得而根據(jù)條件2可得所以結(jié)論3得證。定理的結(jié)論3給出了誤差的估計方式，只要前后兩次迭代值的偏差|xk－xk－1|足夠小，就可以保證迭代誤差|x*－xk|有足夠的精度，因此常常通過|xk－xk－1|來判斷是否滿足迭代精度，即若預(yù)先要求的誤差限為ε，只要|xk－xk－1|≤ε就停止迭代,得到滿足誤差要求的近似根xk。

此外 ，滿足定理2.1的條件2。所以迭代公式收斂。

例2－7用迭代法求方程ex+10x－2=0在區(qū)間(0，0.2)上的近似解，要求精確到小數(shù)點后6位。

解根據(jù)題目，迭代函數(shù)有如下兩種構(gòu)造形式：計算其一階導(dǎo)數(shù)得則根據(jù)定理2.1可知,采用能夠獲得方程的根，即迭代公式為取初始值x0=0，代入迭代公式計算可得而，不滿足精度要求，繼續(xù)迭代，計算結(jié)果如表2.3所示。表2.3例2－7的計算結(jié)果+代入已知條件可得由此得兩邊取極限有則根據(jù)定義2.2可知,迭代公式φ(x)為p階收斂的。 2.4牛頓迭代法與弦割法

2.4.1牛頓迭代法

1.牛頓迭代公式

設(shè)xk是方程f(x)=0的一個近似根，把f(x)在xk處進行泰勒展開可得取前兩項，即其線性部分作為f(x)的近似:(2.8)設(shè)f′(xk)≠0，則由式(2.8)可得令其左端的x為xk+1，則有(k=0，1，…)式(2.9)即為牛頓迭代公式。由該式可得到相應(yīng)的迭代函數(shù)為(2.9)(2.10)

例2－8用牛頓迭代法求方程x=e－x在x=0.5附近的根。

解將方程變換為xex－1=0，即f(x)=xex－1，則根據(jù)牛頓迭代公式有整理后得取初始值x0=0.5，并代入以上迭代公式進行計算，結(jié)果如表2.4所示。從表2.4中可以看出，應(yīng)用牛頓迭代法迭代3次，可得到較高的精度0.2×10－4。表2.4例2－8的計算結(jié)果

2.牛頓迭代法的幾何意義

設(shè)方程f(x)=0，取x的一個初始值x0，則可得曲線y=f(x)上的一個點(x0，f(x0))，曲線上過該點的切線方程為令y=0，則得到該切線與x軸交點的橫坐標此值即為根據(jù)牛頓迭代公式及初始值x0得到的值x1。圖2.2牛頓迭代法的幾何意義

3.牛頓迭代法的收斂性

對牛頓迭代法中的迭代函數(shù)求導(dǎo)數(shù)有(2.11)(2.12)設(shè)x*是方程f(x)=0的單根，則有f(x)=(x－x*)g(x)，且g(x*)≠0。則有則于是有(2.13)(2.14)通常情況下，φ″(x*)≠0，則根據(jù)定理2.3可知,牛頓迭代法至少是二階局部收斂的，且根據(jù)定理2.3的證明有(2.15)2.4.2近似牛頓迭代法與弦割法

1.近似牛頓迭代法

牛頓迭代公式需要計算每個迭代點的導(dǎo)數(shù)f′(xk)，如果用x0的導(dǎo)數(shù)近似代替f′(xk)，則牛頓迭代公式變成(2.16)此即為近似牛頓迭代公式，也稱為簡化的牛頓迭代法。近似牛頓迭代公式只需要計算一次導(dǎo)數(shù)，減少了計算量，但精度比牛頓迭代法稍低。

2.弦割法

用數(shù)值導(dǎo)數(shù)代替牛頓迭代公式中迭代點的導(dǎo)數(shù)f′(xk)的計算，即將其代入牛頓迭代公式可得(k=1,2,…)(2.17)此即為弦割法的迭代公式。從該公式可以看出,弦割法需要兩個初始值才能進行迭代計算。圖2.3弦割法的幾何意義

圖2.3中的曲線y=f(x)由方程f(x)=0得到，該