第8章 非線性方程求解

第八章非線性方程的數(shù)值解法§1二分法

§2迭代法

2.1迭代格式

2.2收斂性條件

2.3迭代法的收斂階

§3牛頓迭代法

3.1迭代格式

3.2迭代法的收斂階§4弦割法

xyoab*x*這種方程往往無法求得其精確解，只能通過數(shù)值方法求其近似解。這里我們將介紹兩種數(shù)值方法：非線性方程求根是我們經(jīng)常碰到的問題，例如：(1).二分法;(2).迭代法：一般迭代法、牛頓迭代法、弦截法.則x*稱為f(x)的m重零點（根）?！?二分法對于

f(x)=0

（8.1）

設(shè)

f(x)∈C[a,b]

，且

f(a)f(b)<0

，則知（8.1）在(a,b)

內(nèi)至少有一實根x*

。如果在(a,b)內(nèi)有(8.1)的唯一實根x*

：則可以用二分法進行求解，求解的步驟如下：xyoab*x*Step1

計算f(a)、f(b)

及

若令a1=a,若則x*∈[a1,b1]則若b1=b,令則x*∈[a1,b1]x*abx*ababx*a1b1a1b1a=a0,b=b0stepk：計算f(ak-1)、f(bk-1)

及

若則

令ak=ak-1,若則x*∈[ak,bk]若bk=bk-1,令則x*∈[ak,bk]最后可取x*akbk誤差

運算次數(shù)的控制,可以用下面兩種方式處理：1）令

2）令b0=ba=a0a1b1a2b2

例8.1求方程x3-x-1=0

在區(qū)間[1,1.5]內(nèi)的實根，要求誤差不超過0.005.解：令f(x)=x3-x-1則有

f(1)=-1,f(1.5)=0.875且由

f

’

(x)=3x2-1>0,x∈[1.0,1.5]可知f(x)=0

在[1,1.5]

內(nèi)有唯一實根x*

。這時f(1)f(1.5)<0x*Ox1.01.5y我們采用二分法進行計算，每一次的計算結(jié)果由下表給出k

ak

bk

xk=(ak+bk)/2

f(xk)0

1.0

1.5

1

2

3

456f(x)=x3-x-1,f(1)=-1<0,f(1.5)=0.875>01.25-0.29691.251.51.3750.22461.251.3751.3125-0.05151.31251.3751.34380.08281.31251.34381.32810.01451.31251.32811.3203-0.01881.32031.32811.3242-0.0018這時|x6-x5|=0.0039<0.005,可得近似解

x*≈x6=1.3242這里的a=1.0,b=1.5

,

取ε=0.005，代入上面的不等式即

2k+1

>102取k=6,也就是計算6次就可以達到滿足精度要求的近似解.另外，我們也可以提前確定計算次數(shù)，這時利用關(guān)系式

—>

(k+1)lg

2

>2二分法優(yōu)點：算法簡單；f(x)連續(xù)即可，常用來定根的范圍；缺點：只能求單實根；收斂速度慢?！?、一般迭代解法一、迭代格式的構(gòu)造對于f(x)=0(8.1)將其改寫為x=g(x)(8.2)取適當(dāng)?shù)某踔?/p>

x0

得迭代格式:并稱其為求解(8.1)

的迭代法，g(x)

稱為迭代函數(shù)。xk+1=g(xk

),k=0,1,2,…(8.3)設(shè)x*

為

(8.1)

精確解，如果，則稱迭代解{xk

}

收斂，否則稱為發(fā)散。簡單迭代法迭代函數(shù)g(x)的不動點簡單迭代法也稱為單點迭代法或不動點迭代法例8.2

用簡單迭代法求x3-2x-3=0

在[1,2]內(nèi)的根。解：容易驗證方程[1,2]在

內(nèi)只有單根。(1)若改寫原方程為得迭代格式取初始值x0=1.9

，由上面的迭代格式求得近似解如下：這里……………由于x8、x9相當(dāng)接近，故可取x*≈x8=1.89328920。(2)如果將原方程x3-2x-3=0改為

仍取初值x0=1.9

，得迭代格式如下：x1=1.8945647x2=1.89352114x8=1.89328920x9=1.89328920得到的近似解是不收斂的，越來越發(fā)散。

由此可見:迭代函數(shù)

g(x)

選取的適當(dāng)，近似解將會收斂；選取的不適當(dāng)，近似解將會發(fā)散。

求得近似解為：x0=1.900x1=1.930x2=2.095x3=3.098x4=13.37那么，思考如下問題：(1)如何選取合適的迭代函數(shù)g(x)

？(2)迭代函數(shù)g(x)應(yīng)滿足什么條件，序列{xk}才會收斂(即迭代格式xk+1=g(xk)才會收斂)呢？下面我們將討論這一問題。

二、收斂性條件定理8.1

設(shè)迭代函數(shù)g(x)

滿足條件由方程f(x)=0

產(chǎn)生的迭代格式:xk+1=g(xk

),k=0,1,2,…(8.3)具有如下的收斂性條件.

1）g(x)∈C[a,b]

;3）g’(x)存在，且存在0<L<1，使得對一切x∈[a,b]

，

|g’(x)|≤L<1

2）當(dāng)x∈[a,b]

時,g(x)∈[a,b]

;則有以下結(jié)論：全局收斂定理連續(xù)性映內(nèi)性壓縮性1）方程f(x)=0

或者x=g(x)

在[a,b]

上有唯一解x*.3）x*有誤差估計式

2）對于任意的x0∈[a,b]

迭代格式xk+1=g(xk)，k=0,1,2…收斂,而且：或4）解存在惟一性收斂性事先誤差估計事后誤差估計與收斂速度有關(guān)無窮小之比

收斂性只與迭代函數(shù)g(x)有關(guān)；收斂速度主要取決于L，越小收斂越快；終止條件可用事先或事后誤差確定。例8.3

確定xex–1=0

在[0.5，0.65]

內(nèi)是否存在唯一實根，如果存在，試構(gòu)造一收斂的迭代格式，并求出近似解，精度要求為ε=10-5

。解:將原方程改寫成如下的形式x=e-x,則g(x)=e-x檢查定理的條件：1).g(x)∈C[0.5,0.65]

;2).g(x)=e-x在[0.5,0.65]在內(nèi)遞減,而且g(0.5)=0.6065,g(0.65)=0.5220，

故有

g(x)∈[0.5,0.65]

。3).由g’(x)=-e-x

可得|g’(x)|=|-e-x|≤0.6065.由此可知x

=e-x

可在[0.5,0.65]上有唯一解,而且迭代格式xk+1=e-xk

,k=0,1,2,…收斂.下面確定滿足精度要求ε=10-5

需要迭代的次數(shù)：任取一個初始解x0=0.5,則由迭代格式xk+1=e–xk

求得

故最少需迭代22次,計算結(jié)果為按照誤差估計式于是兩邊取對數(shù)得到：klg

0.61<-5+lg3.66查表計算得到：-0.21k<-4.43解得k>4.43/0.21=21.12.x1=e–x0

=e–0.5=0.60653ixiixi00.50000000110.5672772010.60653066120.5670673520.54523921130.5671863630.57970310140.5671188640.56006463150.5671571450.57117215160.5671354360.56486295170.5671477470.56843805180.5671407680.56640945190.5671447290.56755963200.56714248100.56690721210.56714375x22=0.56714303,|x21

-x22|=0.00000072<0.000001=10-6關(guān)于解的唯一性的判別，還可以借助于根的存在性定理。我們用另一種方法完成上面的例子。再由xex

–1=0

得x=e-x,x∈[0.5,0.65],其中g(shù)(x)=e-x.說明f(x)=0在[0.5,0.65]上至少有一個實根，又由于解法二:令f(x)=xex-1,有f(0.5)=-0.176,f(0.65)=0.5220

f(0.5)f(0.65)<0

說明f(x)在[0.5,0.65]上嚴(yán)格遞增，所以在[0.5,0.65]

只有一個實根x*。f’(x)=(x+1)ex>0,x∈[0.5,1]

其它步驟與前面的相同，可以完成問題的解決。當(dāng)含根區(qū)間較大時，全局收斂定理條件不易滿足，可在根的鄰域考慮在根附近收斂，遠處發(fā)散在實際應(yīng)用中，通常已經(jīng)知道方程f(x)=0

根的x*在在某點x0

附近存在，希望采用迭代法求出足夠精確的近似解。這時，在使用迭代法時，總是在根x*的鄰域內(nèi)考慮。上面定理中的第二個條件|g’(x)|≤L<1

在較大的區(qū)間內(nèi)有可能不成立，但在根的附近是成立的。由此給出下面局部收斂性定理

定理8.2(迭代法局部收斂性定理)：如果方程x=g(x)

滿足條件：1).g(x)在方程的解x*的鄰域內(nèi)連續(xù)可微；

2).|g’(x*)|<1(由于g(x)在x*的鄰域內(nèi)連續(xù)可微，故一定存在L使得|g’(x*)|≤L<1

，且在x*附近|g’

(x*)|≤L

)；則定理8.1的結(jié)論成立。

三、迭代法的收斂階迭代法收斂速度的快慢可以通過收斂階來衡量，下面給出這一概念。定義：由迭代法xk+1=g(xk)產(chǎn)生的誤差ek=xk-x*，如果當(dāng)k

∞時則稱迭代法是p

階收斂的，當(dāng)p=1

且0<c<1時稱為線性收斂，當(dāng)p=2

時稱為平方收斂或二階收斂。p=1,c=1/2與二分法差不多例如，對于迭代解xk+1=g(xk)與精確解x*=g(x*)兩式相減，得到如果則迭代格式xk+1=g(xk)

線性收斂（收斂時至少線性）。且線性收斂二階收斂例8.4

如果g(x)在方程x=g(x)

根x*的附近具p階連續(xù)導(dǎo)函數(shù),且g’(x*)=g”(x*)=…=g(p-1)(x*)=0,但g(p)(x*)≠0，試證明迭代格式xk+1=g(xk)，k=0,1,2,…具有p階收斂速度。證明：利用Taylor展式得到ek+1=xk+1-x*=g(xk)-g(x*)其中ξ位于

xk與x*之間，這時由于

|g’(x*)|=0<1,所以迭代格式xk+1=g(xk)，k=0,1,2,…收斂，且具有p階收斂速度。上面討論的迭代法也稱作一般迭代法，下面我們再介紹兩種收斂階較高的迭代法——牛頓迭代法和弦截法?！?、牛頓迭代法一、迭代格式由f(x)=0

改變?yōu)閤=g(x)

往往只是線性收斂的，采用f(x)

近似代替可得出高階收斂方法。設(shè)x*

為

f(x)=0

的解，xk

為近似解，則由Taylor展式略去高次項得令故解得如果并稱（1）為方程求根的牛頓迭代格式。則（1）而f(x*)=0

方程求根的牛頓迭代法為又稱為切線法，可以通過其幾何意義明確這一稱呼，如下圖所示：x0xyoabx*x1x21).在解的附近任取一點x0

,在曲線上過點(x0,f(x0))作切線y=f(x0)+f’(x0)(x-x0)(x0

,f(x0))令y=0

,得到切線與x軸的交點2).再過點(x1,f(x1))作切線y=f(x1)+f’(x1)(x-x1)(x1,f(x1))令y=0

,得到切線與x軸的交點以此類推，最后得到的近似解x0,x1

,x2

,…越來越靠近x*。

二、收斂性與收斂階對于牛頓迭代格法迭代函數(shù)為導(dǎo)數(shù)為在精確解x*

處,由f(x*)=0得到|g’(x*)|=0=L<1

由局部收斂性知：牛頓法局部收斂（單根附近至少二階）。得到：關(guān)于收斂階，由牛頓迭代格式再由Taylor展式得到：兩式相減得：即：當(dāng)k∞

時xk

x*,ξx*這時如果則Newton迭代法具有二階收斂速度（重根線性收斂）

。例8.5

用牛頓迭代法求方程xex-1=0在x0=0.5

附近的根。解:已知方程在[0.5,0.6]內(nèi)有唯一實根,令f(x)=xex-1則f’(x)=(x+1)ex

,這樣可以得到Newton迭代格式：或者取初值進行計算：x0=0.5x1=0.57102043x2=0.56715556x3=0.56714329精度為10-5

。如果用一般迭代法xk+1=e-

xk

,k=0,1,2,…，要達到同樣精度，則需要迭代

22

次。x22=0.56714303例8.6

求的值(a>0).例如，對于

解：利用迭頓迭代法，令得計算格式則有xn=a再令f(x)=xn-a,得到f’(x)=nxn-1,

代入牛頓迭代格式將n=2

代入上式得到：如果分別取a=2,a=3,a=5,并要求精度為ε=10-5，計算結(jié)果如下：a=2,ε=10-5

a=3,ε=10-5

a=5,ε=10-5

x0=1.00000000x1=1.50000000x2=1.41666667x3=1.41421569x4=1.41421356x5=1.41421356x0=1.00000000x1=2.00000000x2=1.75000000x3=1.73214285x4=1.73205081x5=1.73205080x0=1.00000000x1=3.00000000x2=2.33333333x3=2.23809523x4=2.23606889x5=2.23606797x6=2.23606797簡化牛頓法（平行弦法：線性收斂）；擬牛頓法

§4弦截法（割線法）一、雙點弦截法對于牛頓迭代法當(dāng)f

’(x)不存在時，可以用作近似代替,得到并稱其為雙點弦截法。其幾何幾何解釋為：在曲線上任取兩點(x0,f(x0))、(x1

,f(x1))，作割線，方程為多點迭代法令y=0,解得：再過兩點(x1,f(x1))、(x2,f(x2))作割線，得割線方程：再令y=0,解得：以此類推，最后得到的近似解x0,x1

,x2

,…越來越靠近x*。x0xyoabx*x1x2(x0,f(x0))(x1,f(x1))x3x4yx1xoabx*x0x2(x1,f(x1))x3(x0,f(x0))(x2,f(x2))

二、單點弦截法x0xyoabx*x1x2(x0,f(x0))(x1,f(x1))x3在曲線上過兩點(x0,f(x0))、(x1,f(x1))作割線，方程為令y=0,解得：再過兩點(x0,f(x0))、(x2,f(x2))作割線得割線方程：再令y=0,解得：x4以此類推，可以得到單點弦截公