第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）

設

f(x)∈C[a,b]

，且

f(a)f(b)<0

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

內至少有一實根x*

。如果在(a,b)內有(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]內的實根，要求誤差不超過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]

內有唯一實根x*

。這時f(1)f(1.5)<0x*Ox1.01.5y我們采用二分法進行計算，每一次的計算結果由下表給出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ù)，這時利用關系式

—>

(k+1)lg

2

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

x0

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

的迭代法，g(x)

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

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

為

(8.1)

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

}

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

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

在[1,2]內的根。解：容易驗證方程[1,2]在

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

，由上面的迭代格式求得近似解如下：這里……………由于x8、x9相當接近，故可取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)

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

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

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

二、收斂性條件定理8.1

設迭代函數(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）當x∈[a,b]

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

;則有以下結論：全局收斂定理連續(xù)性映內性壓縮性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）解存在惟一性收斂性事先誤差估計事后誤差估計與收斂速度有關無窮小之比

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

確定xex–1=0

在[0.5，0.65]

內是否存在唯一實根，如果存在，試構造一收斂的迭代格式，并求出近似解，精度要求為ε=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]在內遞減,而且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次,計算結果為按照誤差估計式于是兩邊取對數(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關于解的唯一性的判別，還可以借助于根的存在性定理。我們用另一種方法完成上面的例子。再由xex

–1=0

得x=e-x,x∈[0.5,0.65],其中g(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]上嚴格遞增，所以在[0.5,0.65]

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

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

根的x*在在某點x0

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

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

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

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

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

，且在x*附近|g’

(x*)|≤L

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

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

∞時則稱迭代法是p

階收斂的，當p=1

且0<c<1時稱為線性收斂，當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ù)導函數(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)

近似代替可得出高階收斂方法。設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ù)為導數(shù)為在精確解x*

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

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

時xk

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

。例8.5

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

附近的根。解:已知方程在[0.5,0.6]內有唯一實根,令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，計算結果如下：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弦截法（割線法）一、雙點弦截法對于牛頓迭代法當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以此類推，可以得到單點弦截公