第7章 非線性方程的數(shù)值求法

第七章非線性方程與方程組的數(shù)值解法1.二分法2.迭代法及其收斂性3.埃特金（Aitken）加速法4.牛頓迭代法(切線法)5.弦截法2023/2/11

引言在科學(xué)研究和工程設(shè)計(jì)中,經(jīng)常會(huì)遇到的一大類問題是非線性方程

f(x)=0(7.1)

的求根問題，其中f(x)為非線性函數(shù)。方程f(x)=0的根,亦稱為函數(shù)f(x)的零點(diǎn)

如果f(x)可以分解成,其中m為正整數(shù)且,則稱x*是f(x)的m重零點(diǎn),或稱方程f(x)=0的m重根。當(dāng)m=1時(shí)稱x*為單根。若f(x)存在m階導(dǎo)數(shù),則是方程f(x)=0的m重根(m>1)當(dāng)且僅當(dāng)2023/2/12記筆記

當(dāng)f(x)不是x的線性函數(shù)時(shí)，稱對(duì)應(yīng)的函數(shù)方程為非線性方程。如果f(x)是多項(xiàng)式函數(shù)，則稱為代數(shù)方程，否則稱為超越方程（三角方程，指數(shù)、對(duì)數(shù)方程等）。一般稱n次多項(xiàng)式構(gòu)成的方程為n次代數(shù)方程,當(dāng)n＞1時(shí),方程顯然是非線性的一般稍微復(fù)雜的3次以上的代數(shù)方程或超越方程,很難甚至無法求得精確解。本章將介紹常用的求解非線性方程的近似根的幾種數(shù)值解法2023/2/13記筆記

通常方程根的數(shù)值解法大致分為三個(gè)步驟進(jìn)行①

判定根的存在性。即方程有沒有根？如果有根，有幾個(gè)根？②確定根的分布范圍。即將每一個(gè)根用區(qū)間隔離開來，這個(gè)過程實(shí)際上是獲得方程各根的初始近似值。③根的精確化。將根的初始近似值按某種方法逐步精確化，直到滿足預(yù)先要求的精度為止2023/2/147.1二分法

二分法又稱二分區(qū)間法,是求解方程(7.1)的近似根的一種常用的簡單方法。設(shè)函數(shù)f(x)在閉區(qū)間[a,b]上連續(xù),且f(a)f(b)<0,根據(jù)連續(xù)函數(shù)的性質(zhì)可知,f(x)=0在(a,b)內(nèi)必有實(shí)根,稱區(qū)間[a,b]為有根區(qū)間。為明確起見,假定方程f(x)=0在區(qū)間[a,b]內(nèi)有惟一實(shí)根x*。二分法基本思想:首先確定有根區(qū)間,將區(qū)間二等分,判斷f(x)的符號(hào),逐步將有根區(qū)間縮小,直至有根區(qū)間足夠地小,便可求出滿足精度要求的近似根。2023/2/157.1.1確定有根區(qū)間的方法為了確定根的初值，首先必須圈定根所在的范圍，稱為圈定根或根的隔離。在上述基礎(chǔ)上，采取適當(dāng)?shù)臄?shù)值方法確定具有一定精度要求的初值。對(duì)于代數(shù)方程，其根的個(gè)數(shù)（實(shí)或復(fù)的）與其次數(shù)相同。至于超越方程，其根可能是一個(gè)、幾個(gè)或無解，并沒有什么固定的圈根方法求方程根的問題，就幾何上講,是求曲線

y=f(x)與

x軸交點(diǎn)的橫坐標(biāo)。2023/2/16

由高等數(shù)學(xué)知識(shí)知,設(shè)f(x)在區(qū)間[a,b]上連續(xù),如果f(a)·f

(b)<0,則在[a,b]中至少有一個(gè)實(shí)根。如果f(x)在[a,b]上還是單調(diào)的，則僅有一個(gè)實(shí)根。記筆記由此可大體確定根所在子區(qū)間，方法有：(1)畫圖法(2)逐步搜索法y=f(x)abyx2023/2/17(1)畫圖法畫出y=f(x)的略圖，從而看出曲線與x軸交點(diǎn)的大致位置。也可將f(x)=0分解為1(x)=2(x)的形式，1(x)

與2(x)兩曲線交點(diǎn)的橫坐標(biāo)所在的子區(qū)間即為含根區(qū)間。 例如xlnx-1=0

可以改寫為lnx=1/x

畫出對(duì)數(shù)曲線y=lnx,與雙曲線y=1/x,它們交點(diǎn)的橫坐標(biāo)位于區(qū)間[2,3]內(nèi)2023/2/18(1)畫圖法023yx2023/2/19對(duì)于某些看不清根的函數(shù)，可以擴(kuò)大一下曲線y0xy=f(x)y=kf(x)(1)畫圖法記筆記2023/2/110y0xABa1b1a2b2(2)逐步搜索法(2)搜索法

對(duì)于給定的f(x),設(shè)有根區(qū)間為[A,B],從x0=A出發(fā),以步長h=(B-A)/n(n是正整數(shù)),在[A,B]內(nèi)取定節(jié)點(diǎn):xi=x0＋ih(i=0,1,2,…,n),從左至右檢查f(xi)的符號(hào),如發(fā)現(xiàn)xi與端點(diǎn)x0的函數(shù)值異號(hào),則得到一個(gè)縮小的有根子區(qū)間［xi-1,xi］。2023/2/111例1方程f(x)=x3-x-1=0

確定其有根區(qū)間解：用試湊的方法，不難發(fā)現(xiàn)

f(0)<0f(2)>0

在區(qū)間（0，2）內(nèi)至少有一個(gè)實(shí)根設(shè)從x=0出發(fā),取h=0.5為步長向右進(jìn)行根的搜索,列表如下xf(x)00.51.01.52

–––++可以看出，在[1.0,1.5]內(nèi)必有一根2023/2/112用逐步搜索法進(jìn)行實(shí)根隔離的關(guān)鍵是選取步長h

要選擇適當(dāng)h，使之既能把根隔離開來，工作量又不太大。

為獲取指定精度要求的初值,可在以上隔離根的基礎(chǔ)上采用對(duì)分法繼續(xù)縮小該含根子區(qū)間

二分法可以看作是搜索法的一種改進(jìn)。2023/2/113①取有根區(qū)間[a,b]之中點(diǎn),將它分為兩半,分點(diǎn),這樣就可縮小有根區(qū)間7.1.2

二分法求根過程

設(shè)方程f(x)=0在區(qū)間[a,b]內(nèi)有根,二分法就是逐步收縮有根區(qū)間，最后得出所求的根。具體過程如下

2023/2/114②對(duì)壓縮了的有根區(qū)間施行同樣的手法,即取中點(diǎn),將區(qū)間再分為兩半,然后再確定有根區(qū)間,其長度是的二分之一③如此反復(fù)下去,若不出現(xiàn),即可得出一系列有根區(qū)間序列：上述每個(gè)區(qū)間都是前一個(gè)區(qū)間的一半,因此的長度

當(dāng)k→∞時(shí)趨于零,這些區(qū)間最終收斂于一點(diǎn)x*即為所求的根。2023/2/115

每次二分后,取有根區(qū)間的中點(diǎn)作為根的近似值，得到一個(gè)近似根的序列該序列以根x*為極限只要二分足夠多次(即k足夠大),便有這里ε為給定精度,由于,則2023/2/116當(dāng)給定精度ε＞0后,要想成立,只要取k滿足即可，亦即當(dāng):

時(shí),做到第k+1次二分,計(jì)算得到的就是滿足精度要求的近似根。在程序中通常用相鄰的與的差的絕對(duì)值或與的差的絕對(duì)值是否小于ε來決定二分區(qū)間的次數(shù)。

2023/2/117

二分法算法實(shí)現(xiàn)2023/2/118例２求方程f(x)=x3-x-1=0

在區(qū)間[1.0,1.5]內(nèi)的一個(gè)實(shí)根,使誤差不超過0.5×10-2。P215例３證明方程在區(qū)間[2,3]內(nèi)有一個(gè)根,使用二分法求誤差不超過0.5×10-3的根要二分多少次？證明令且f(x)在[2,3]上連續(xù),故方程f(x)=0在[2,3]內(nèi)至少有一個(gè)根。又當(dāng)時(shí)時(shí)，,故f(x)在[2,3]上是單調(diào)遞增函數(shù),從而f(x)在[2,3]上有且僅有一根。

給定誤差限＝0.5×10-3,使用二分法時(shí)2023/2/119誤差限為只要取k滿足

即可，亦即二分法的優(yōu)點(diǎn)是不管有根區(qū)間多大,總能求出滿足精度要求的根,且對(duì)函數(shù)f(x)的要求不高,只要連續(xù)即可,計(jì)算亦簡單;它的局限性是只能用于求函數(shù)的實(shí)根,不能用于求復(fù)根及偶重根,它的收斂速度與比值為的等比級(jí)數(shù)相同。所以需二分10次便可達(dá)到要求。2023/2/1207.2不動(dòng)點(diǎn)迭代法及其收斂性

一般的非線性方程,沒有通常所說的求根公式求其精確解,需要設(shè)計(jì)近似求解方法.迭代法---是一種逐次逼近的方法,用某個(gè)固定公式反復(fù)校正根的近似值,使之逐步精確化，最后得到滿足精度要求的結(jié)果。為求解非線性方程f(x)=0的根，先將其寫成便于迭代的等價(jià)方程7.2.1迭代法的基本思想2023/2/1212023/2/122再將代入式的右端,得到,依此類推,得到一個(gè)數(shù)列…，其一般表示式(5.4)稱為求解非線性方程的迭代公式。

(5.4)2023/2/123如果由迭代格式產(chǎn)生的序列收斂,即

則

實(shí)際計(jì)算中當(dāng)然不可能也沒必要無窮多步地做下去,對(duì)預(yù)先給定的精度要求ε，只要某個(gè)k滿足即可結(jié)束計(jì)算并取2023/2/124例4用迭代法求方程在x=1.5附近的一個(gè)根。相應(yīng)地可得到兩個(gè)迭代公式如果取初始值，用上述兩個(gè)迭代公式分別迭代，計(jì)算結(jié)果將方程改寫成如下兩種等價(jià)形式

注意：迭代函數(shù)的構(gòu)造方法是多種多樣的。2023/2/125kxk012345671.51.357211.330861.325881.324941.324761.324731.32472迭代公式是否收斂是選擇迭代公式的關(guān)鍵！2023/2/126(a)(b)7.2.2迭代法的幾何意義

通常將方程f(x)=0化為與它同解的方程的方法不止一種,有的收斂,有的不收斂,這取決于的性態(tài),方程的求根問題在幾何上就是確定曲線y=與直線y=x的交點(diǎn)P*的橫坐標(biāo)(圖7-2所示)

2023/2/127圖7-2迭代法的幾何意義

2023/2/128對(duì)方程f(x)=0可以構(gòu)造不同的迭代公式,但迭代公式并非總是收斂。那么,當(dāng)?shù)瘮?shù)滿足什么條件時(shí)，相應(yīng)的迭代公式才收斂呢？即使迭代收斂時(shí)，我們也不可能迭代無窮多次，而是迭代有限次后就停止，這就需要估計(jì)迭代值的誤差，以便適時(shí)終止迭代.

7.2.3迭代法收斂的條件2023/2/129定理1設(shè)函數(shù)在[a,b]上具有連續(xù)的一階導(dǎo)數(shù),且滿足

（1）對(duì)所有的x∈[a,b]有

（2）則方程在[a,b]上的解存在且唯一，且對(duì)任意的∈[a,b]，迭代過程均收斂于。并有誤差估計(jì)式：

①

②

2023/2/130證:構(gòu)造函數(shù),由條件(1)對(duì)任意的x∈[a,b]

[a,b]由零點(diǎn)定理知,假設(shè)有兩個(gè)解由微分中值定理有由條件(2)存在唯一2023/2/131按迭代過程,有

由于L<1,所以有,可見L越小,收斂越快，且與無關(guān)。2023/2/132即

①

得證。

即

②

得證。

證(2)

再證誤差估計(jì)式2023/2/133定理1

對(duì)任意的∈[a,b]，迭代過程均收斂于。且有①

②

通過①式控制近似值的誤差

2023/2/1347.2.4迭代法的算法框圖2023/2/135例5

對(duì)方程,構(gòu)造收斂的迭代格式,求其最小正根,計(jì)算過程保留4位小數(shù)。解容易判斷[1,2]是方程的有根區(qū)間,且在此區(qū)間內(nèi)僅有一根。將原方程改寫成以下兩種等價(jià)形式:①迭代公式不滿足迭代收斂條件!2023/2/136例5

對(duì)方程,構(gòu)造收斂的迭代格式,求其最小正根,計(jì)算過程保留4位小數(shù)。此時(shí)迭代公式滿足迭代收斂條件。

②2023/2/137例5

對(duì)方程,構(gòu)造收斂的迭代格式,求其最小正根,計(jì)算過程保留4位小數(shù)。解將原方程改寫成以下形式。

2023/2/138例6設(shè),要使迭代過程局部收斂到,求的取值范圍。解：由在根鄰域具有局部收斂性的時(shí)條件

2023/2/139例7已知方程在內(nèi)有根,且在上滿足,利用構(gòu)造一個(gè)迭代函數(shù),使局部收斂于。故迭代公式局部收斂解：2023/2/1407.2.6迭代法的收斂速度

一種迭代法具有實(shí)用價(jià)值，首先要求它是①收斂的，其次還要求它②收斂較快。

則稱序列是p階收斂的,c

稱漸近誤差常數(shù)。特別地,p=1時(shí)稱為線性收斂,p=2時(shí)稱為平方收斂。1<p<2時(shí)稱為超線性收斂。

定義2.2設(shè)迭代過程收斂于的根,記迭代誤差若存在常數(shù)p（p≥1）和c(c>0)，使

2023/2/141

數(shù)

p

的大小反映了迭代法收斂的速度的快慢，p越大，則收斂的速度越快，故迭代法的收斂階是對(duì)迭代法收斂速度的一種度量。

定義2.2設(shè)迭代過程收斂于的根,記迭代誤差若存在常數(shù)p（p≥1）和c(c>0)，使p——收斂階2023/2/142定理4設(shè)迭代過程，若在所求根的鄰域連續(xù)且則迭代過程在的鄰域p

階收斂。證:由迭代公式及根據(jù)已知條件得2023/2/143例8已知迭代公式收斂于證明該迭代公式平方收斂。根據(jù)定理7.3可知，迭代公式平方收斂。將代入，為了使迭代過程收斂或提高收斂的速度,可設(shè)法①提高初值的精度以減少迭代的次數(shù)②提高收斂的階數(shù)p證:迭代公式相應(yīng)的迭代函數(shù)為2023/2/144（1）加權(quán)法其中

可見,是比更好的近似根7.3迭代過程的加速*

又根據(jù)中值定理有設(shè)是根的某個(gè)近似值,用迭代公式校正一次得2023/2/145在龍貝格(Romberg)算法中我們已使用過此技術(shù)

根據(jù)積分區(qū)間分成n等份和2n等份時(shí)的梯形公式誤差估計(jì)式(4.8)可得

如果用對(duì)進(jìn)行修正，將更接近積分真值,因此可得到具有更好效果的近似公式。2023/2/146作為中間值并記為：化簡并寫成：修正為：迭代一次，計(jì)算一次在上述迭代公式中，要事先估計(jì)L的值。2023/2/147例9用加權(quán)法加速技術(shù)求方程在0.5附近的一個(gè)根。仍取,逐次計(jì)算得=0.56658…=0.56714。迭代4次便可得到精度的結(jié)果,而不用加速技術(shù)需迭代18次,效果顯著。取L=-0.6，建立如下迭代公式解：因?yàn)樵诟浇?023/2/148（2）埃特金（Aitken）方法

在加權(quán)法中,估計(jì)L的值有時(shí)不太方便。假設(shè)在求得以后,先求出由于求根區(qū)間變化不大,用某個(gè)定值L近似2023/2/149將迭代值再迭代一次,得新的迭代值將上述兩個(gè)方程聯(lián)立消去常數(shù)L化簡可得同理記2023/2/150這樣得到公式稱為埃特金（Aitken）加速公式計(jì)算一次迭代加速迭代兩次2023/2/151例10用埃特金方法求方程在初值附近的一個(gè)根,精度要求，

取迭代格式所以迭代格式收斂。2023/2/152例10用埃特金方法求方程在初值附近的一個(gè)根,精度要求，

取迭代格式解埃特金方法迭代格式為只迭代二次就得到滿足精度要求的解。2023/2/153控制遞推公式中誤差的傳播

對(duì)于一個(gè)數(shù)學(xué)問題的求解往往有多種數(shù)值方法在選擇數(shù)值方法時(shí)，要注意:所用的數(shù)值方法不應(yīng)將計(jì)算過程中難以避免的誤差放大的較快，造成計(jì)算結(jié)果完全失真。例

計(jì)算積分并估計(jì)誤差解容易得到遞推公式2023/2/154則遞推公式前進(jìn)式2023/2/155于是

計(jì)算時(shí)的誤差被擴(kuò)大了倍,顯然算法不穩(wěn)定。

若有誤差且與精確值的誤差為，則誤差的遞推規(guī)律為

2023/2/156準(zhǔn)確的理論遞推式實(shí)際運(yùn)算的遞推式如果將遞推公式變換一種形式從而有后退式2023/2/157即于是有則這個(gè)算法的誤差傳遞規(guī)律為

即每計(jì)算一步的誤差的絕對(duì)值是上一步的十分之一，誤差的傳播逐步縮小，得到很好的控制，這個(gè)算法是數(shù)值穩(wěn)定的2023/2/158用迭代法可逐步精確方程根的近似值，但必須要找到的等價(jià)方程,如果選得不合適,不僅影響收斂速度,而且有可能造成迭代格式發(fā)散。能否通過一定的程序找到一個(gè)迭代函數(shù),使之滿足結(jié)構(gòu)簡單,收斂速度快,又不存在發(fā)散的問題。這就是本節(jié)要介紹的牛頓迭代法。7.4

牛頓迭代法

2023/2/159牛頓迭代法是一種重要和常用的迭代法,它的基本思想是將非線性函數(shù)f(x)逐步線性化,從而將非線性方程f(x)=0近似地轉(zhuǎn)化為線性方程求解。7.4.1牛頓迭代法的基本思想

2023/2/1607.4.2牛頓迭代法的幾何解釋

方程f(x)=0的根x*是曲線y=f(x)與x軸交點(diǎn)的橫坐標(biāo),設(shè)xk是根x*的某個(gè)近似值,過曲線y=f(x)的橫坐標(biāo)為xk的點(diǎn)Pk=(xk,f(xk))引切線交x軸于xk+1,并將其作為x*新的近似值,重復(fù)上述過程,一次次用切線方程的根近似方程f(x)=0的根,所以亦稱為牛頓切線法。2023/2/161忽略高次項(xiàng),用其線性部分作為函數(shù)f(x)的近似，

對(duì)于方程f(x)=0，設(shè)其近似根為xk，函數(shù)f(x)可在xk的附近作泰勒展開2023/2/162將右端取為,即是比更接近于的近似值

這就是著名的牛頓迭代公式2023/2/1637.4.3

牛頓迭代法的收斂性證:牛頓迭代公式對(duì)應(yīng)的迭代函數(shù)為從而定理2.4設(shè)x*是方程f(x)=0的單根，且

f(x)在x*的某個(gè)鄰域內(nèi)有連續(xù)的二階導(dǎo)數(shù),則牛頓法在x*附近局部收斂,且至少二階收斂?！?/p>

x*是方程f(x)=0的單根，所以,牛頓迭代法在

x*附近局部收斂。2023/2/164證至少二階收斂,方法12023/2/165則稱序列是p階收斂的,c

稱漸近誤差常數(shù)。特別地,p=1時(shí)稱為線性收斂,p=2時(shí)稱為平方收斂。1<p<2時(shí)稱為超線性收斂。

定義2.2設(shè)迭代過程收斂于的根,記迭代誤差若存在常數(shù)p（p≥1）和c(c>0)，使

證法2：用泰勒公式2023/2/166證法2：用泰勒公式2023/2/167所以證畢2023/2/168解：牛頓迭代公式2023/2/169證收斂：證法2：2023/2/170解：證畢2023/2/171切線法(Newton)的使用條件2023/2/172yx0B=x0f′′(x)>0xn+1X*ayx0Bf′′(x)>0a=x0yx0B=x0f′′(x)<0ayx0Bf′′(x)<0a=x02023/2/173yx10x0X*0x0X*x2不滿足迭代條件時(shí)，可能導(dǎo)致迭代值遠(yuǎn)離根的情況而找不到根或死循環(huán)的情況2023/2/1747.4.4牛頓迭代法的算法實(shí)現(xiàn)2023/2/175例11用牛頓迭代法求方程的根,ε=10-4.

取x0=0.5,逐次計(jì)算得

x1=0.57102,x2=0.56716，

x3=0.56714解：因建立迭代公式2023/2/1767.4.5牛頓下山法

將牛頓迭代法與下山法結(jié)合起來使用,即在下山法保證函數(shù)值下降的前提下,用牛頓迭代法加快收斂速度。把這一算法稱為牛頓下山法。即滿足這項(xiàng)要求的算法稱下山法。其中λ(0<λ<1)為下山因子通常,牛頓迭代法的收斂性依賴于初始值x0的選取,如果x0偏離所求的根x*比較遠(yuǎn),則牛頓法可能發(fā)散。為了防止迭代發(fā)散,我們對(duì)牛頓迭代法的迭代過程再附加一項(xiàng)要求,即具有單調(diào)性2023/2/177

下山因子的選擇是個(gè)逐步探索的過程，設(shè)從λ=1開始反復(fù)將λ減半進(jìn)行試算,即逐次取λ為從中挑選下山因子，直至找到其中某個(gè)λ使單調(diào)性條件成立，則稱“下山成功”，否則“下山失敗”，這時(shí)需另選初值重算。2023/2/178牛頓法可用于求方程重根2023/2/179迭代格式收斂且為線性收斂2023/2/180可將迭代公式改為：2023/2/181得(4.14)式平方收斂。2023/2/1822023/2/183kxk(1)(2)(3)0123x0x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.414213562(2),(3)都是二階方法的精度均達(dá)到(1)是一階方法精度要達(dá)到需迭代30次。2023/2/184§7.5弦截法牛頓迭代法雖然具有收斂速度快的優(yōu)點(diǎn)，但每迭代一次都要計(jì)算導(dǎo)數(shù),當(dāng)f(x)比較復(fù)雜時(shí),不僅每次計(jì)算導(dǎo)數(shù)帶來很多不便，而且還可能十分麻煩，如果用不計(jì)算導(dǎo)數(shù)的迭代方法，往往只有線性收斂的速度。本節(jié)介紹的弦截法便是一種不需求導(dǎo)的求根方法。弦截法在迭代過程中不僅用到前一步處的函數(shù)值，而且還使用處的函數(shù)值來構(gòu)造迭代函數(shù)，稱為多點(diǎn)迭代法，能夠提高迭代的收斂速度。2023/2/185

7.5.1弦截法的基本思想

為避免計(jì)算函數(shù)的導(dǎo)數(shù)，使用差商

替代牛頓公式中的導(dǎo)數(shù),便得到迭代公式

稱為弦截迭代公式，相應(yīng)的迭代法稱為弦截法。2023/2/186弦截法也稱割線法,其幾何意義是用過曲線上兩點(diǎn)、的割線來代替曲線,用割線與x軸交點(diǎn)的橫座標(biāo)作為方程的近似根再過P1點(diǎn)和點(diǎn)作割線求出,再過P2點(diǎn)和點(diǎn)作割線求出,余此類推，當(dāng)收斂時(shí)可求出滿足精度要求的7.5.2弦截法幾何意義2023/2/187可以證明，弦截法具有超線性收斂，收斂的階約為1.618，它與前面介紹的一