chap8非線性方程及非線性方程組解法

第八章

非線性方程(組)的解法例8‐1:

一個半徑為r

,密度為

的木質(zhì)球體投入水中,如圖,問球體浸入水中部分的深度d

等于多少?球質(zhì)量為34

r3

,

而球浸入水中排出的水質(zhì)量30d

[r

2

(x

r)2

]

dx

1

d

2

(3r

d

)根據(jù)Archimedes

定律,有2

31343d

(3r

d

)

r

即d

滿足代數(shù)方程d

3

3rd

2

4r3

0例如某種木材0.638kg/cm3,球半徑r

5cm

，則d

滿足三次方程d

3

15d

2

319

0設(shè)f(d

)

d

3

15d

2

319

，不難驗證

f

(0)

319,

f

(5)

69

f

(10)

181，區(qū)間(,0)和(10,)上，方程各有一實根，但這都不是物理問題的解。而方程另有一個實根d

(5,10)，這才是

感

的解。例8‐2：公元1225

年，比薩的數(shù)學(xué)家Leonardo（即Fibonacci，1170‐1250）研究了方程x3

2x2

10x

20

0得到一個根x*

1.368808107

.沒有人知道他用什么方法得到這個值.例

8‐3:

數(shù)學(xué)上求非線性方程組的問題21

23

32

14x

3x2

1x

8x

1在（0.25，‐0.5）附近的解。若

f

(a)

0,

f

(l)(a)

0

(l

1,,k1),

f

(k)(a)

0

(k

1,2,)則稱x

a是方程的k重根或函數(shù)f

(x)的k重零點.非線性方程:設(shè)f

(x)為非線性函數(shù),方程f

(

x)

0

(8

1)稱為非線性方程.例:

方程重根:f

(x)

0

有k重根f

(

x)

(x

a)k

(

x),

(a)

0f

(x)

ex

sin

x

010n1n

n1例:代數(shù)方程

f

(x)

a

xn

ax

a

x

a

0，n

1abb1a2a1x0

x*x1b2§8.1對分區(qū)間法（二分法）確定有根區(qū)間:若

f

(

x

)

C

a,

b,

f(a

)f(b)

0,

則(a,

b)內(nèi)必有方程(8

1)的根,

稱其為有根區(qū)間.逐次對分區(qū)間.取根的近似值.a,b

a

,

b

a

,

b

a

,

b

1

1

2

2

n

nf

(an

)

f

(bn

)

0,

x

(a,b)是方程(8

1)的根.2n

b

a

,bn

ann

nn

nlim

a

lim

b二分法的誤差:2n12

x

bn

an

b

anxx

an

bn

xn2根的近似值:逐次對分區(qū)間得區(qū)間套ax1b2bb1a2a1x0

x*其誤差為:用對分區(qū)間法求根步驟：2

bn

(n

0,1,)

ann2.逐次對分求根區(qū)間求近似根x若

f

(an

)

f

(

xn

)

0

則

an1

an

,

bn1

xn否則an1

xn

,bn1

bn1.確定求根區(qū)間[a,

b]

f

(a)

f

(b)

0n

ln(b

a)

ln

1ln

2直到滿足精度.注釋:誤差公式事先估計等分的次數(shù)2n1b

a

n

4ln10

13.3ln0.5故n

14,x14即為滿足精度要求的近似解.2解

:

確定有根區(qū)間誤差不超過1

104

(精確到小數(shù)后第四位)例:

求方程

f

(

x)

x3

10x

20

0的一實根,

要求

f

(1)

9

0,

f

(2)

8

0n2n11,2為有根區(qū)間,

取

x

做為近似值,

誤差為b

a2nln

0.5

4ln10為使誤差不超過

1

104

,

只需12n12

1

104zbisection(inline('x^3+10*x-20','x'),1,2,1e-4)k[ab]xf(x)01.500000000000002.000000000000001.750000000000002.859375000000001.000000000000001.500000000000001.750000000000001.625000000000000.541015625000002.000000000000001.500000000000001.625000000000001.56250000000000-0.560302734375003.000000000000001.562500000000001.625000000000001.59375000000000-0.014312744140634.000000000000001.593750000000001.625000000000001.609375000000000.262172698974615.000000000000001.593750000000001.609375000000001.601562500000000.123636722564706.000000000000001.593750000000001.601562500000001.597656250000000.054588854312907.000000000000001.593750000000001.597656250000001.595703125000000.020119793713098.000000000000001.593750000000001.595703125000001.594726562500000.002898962236949.000000000000001.593750000000001.594726562500001.59423828125000-0.0057080312399210.000000000000001.594238281250001.594726562500001.59448242187500-0.0014048196171611.000000000000001.594482421875001.594726562500001.594604492187500.0007470000255112.000000000000001.594482421875001.594604492187501.59454345703125-0.0003289276162413.000000000000001.594543457031251.594604492187501.594573974609380.0002090317494514.000000000000001.594543457031251.594573974609381.59455871582031-0.00005994904718x

=

1.59455871582031kxf(x)01.750000000000002.859375000000001.000000000000001.625000000000000.541015625000002.000000000000001.56250000000000-0.560302734375003.000000000000001.59375000000000-0.014312744140634.000000000000001.609375000000000.262172698974615.000000000000001.601562500000000.123636722564706.000000000000001.597656250000000.054588854312907.000000000000001.595703125000000.020119793713098.000000000000001.594726562500000.002898962236949.000000000000001.59423828125000-0.0057080312399210.000000000000001.59448242187500-0.0014048196171611.000000000000001.594604492187500.0007470000255112.000000000000001.59454345703125-0.0003289276162413.000000000000001.594573974609380.0002090317494514.000000000000001.59455871582031-0.00005994904718zbisection(inline('x^3+2*x^2+10*x-20','x'),1,2,1e-8)k

=28ans

=1.36880810745060與1225年Leonardo

的結(jié)果一致！§8.2簡單迭代法簡單迭代法的一般形式及其幾何意義x

(

x)(n

0,1,

2,)從初值x0出發(fā),逐次代入迭代公式產(chǎn)生序列xn

,以xn

近似f

(x)

0的根,(x)稱為迭代函數(shù).f

(

x)

0

構(gòu)造迭代格式:xn1

(xn

)結(jié)論:若xn

x

,(x)在x處連續(xù),則x

是方程的根,即f

(

x*

)

08.2.1迭代過程的幾何表示y

(x)Ox*x2x1x0xyP0P1P2Q

2P

*x

yy

xQ1x

(x)

y

(x)交點即為真實根xyy

=

xxyy

=

xxyy

=

xxyx*x0p0p1x0p0x1p1p0x1

x0

x*p1p0x0

x*

x1p1y

(x)x1

x*y

(x)y

=

xy

(x)y

(x)例:用簡單迭代法求方程f

(x)

x3

10

x

20

0的根,

要求精確到六位小數(shù),

取

x0

1.5解:(1)f

(x)

0

x

x3

11x

20迭代格式:x

x3

11x

20n

nn1將初值代入得:x1

0.125,

x2

21.376953,

x3

10023.861此迭代序列發(fā)散。20x2

10

x

n120迭代格式

:

x

nx

2

1011.52

1020

1.6326531

x

15

14x15

1.5945622x14

1.59456182x

x

4

107

1

106

x*

x

1.594562215(2)

f

(

x)

x3

10x

20

0ziteration(inline('20/(x^2+10)'),1.5,1e-6)1.000000000000001.632653061224492.000000000000001.579085827030583.000000000000001.600830888972854.000000000000001.592019583443835.000000000000001.595592799843466.000000000000001.594144213111477.000000000000001.594731546347768.000000000000001.594493422715459.000000000000001.5945899676334610.000000000000001.5945508247610811.000000000000001.5945666947799912.000000000000001.5945602604756713.000000000000001.5945628691868214.000000000000001.5945618115165615.000000000000001.5945622403361610x3

x

2

10x

3迭代格式

:

xn

1

2

n代入初值得：x1

1.6625x2

1.5405006x3

1.6344175x4

1.5633947x5

1.6178746x6

1.5765184x7

1.6081705x8

1.5840930x9

1.6024955x10

1.5884803x11

1.5991837x12

1.5910265x15

1.5961284x13

1.5972529x14

1.5925061

x14

0.0036223x153(3)

f

(

x)

x

10x

20

0誤差比(2)的迭代格式大ziteration(inline('2-0.1*(x^3)'),1.5,1e-6)例2表明:對同一方程可構(gòu)造不同的迭代格式，產(chǎn)生的迭代序列收斂性也不同。迭代序列的收斂性取決于迭代函數(shù)在方程根的鄰近區(qū)間的性態(tài)。8.2.2迭代法的收斂條件定理8.1

:(壓縮映像原理)設(shè)函數(shù)

(x

)在區(qū)間上滿足:對任意的

x

[a

,

b],

都有a

(

x

)

b存在常數(shù)0

L

1,

使得對一切

x

,

y

a

,

b

,

都有

(

x

)

(

y

)

L

x

y則方程x

(x

)在[a,b]內(nèi)有唯一的根x*

.且對任意初值x0

a,b,迭代格式:xn1

(

xn

)(n

0,1,2,)*n所產(chǎn)生的序列

x均收斂于x

,

x01

L

x1Ln

并有

x

xn

結(jié)論1結(jié)論2結(jié)論3證明:函數(shù)

(

x

)在區(qū)間[a

,

b]上連續(xù),

令

(

x

)

x

(

x，)

則

(x)在[a,b]上連續(xù)，且

(a)

a

(a)

0，(b)

b

(b)

0由連續(xù)函數(shù)介值定理,存在

[a,b，]即

(

)再證唯一性:使得

(

)

0,設(shè)

x1

x2

[a,

b，]

x1

(

x1

),

x2

(

x2

),|

x1

x2

||

(

x1

)

(

x2

)

|

L

|

x1

x2

||

x1

x2

|，唯一性得證。|

xn1

x

||

(

x

)

(

x

)

|

L

|

x

x*

|設(shè)方程x

(x

)在區(qū)間[a,b]上有根x*

,由迭代公式*

*n

n依次類推，得*

n

*|

xn

x

|

L

|

x

x

|0

x*。n由于0

L

1,因此

lim

xnxk1

xk

(

xk

)

(

xk1)

L

xk

xk1

Lk

x

x10類似的，對任意正整數(shù)k

,有xn

p

xn

xn

p

xn

p1

xn

p1

xn

p2

xn1

xn于是，對任意正整數(shù)n，p,有令p

,有x1

x0Ln1

Lnx*

x

證畢x1

x0

(1

Lp)Ln1

L

(Lnp1

Lnp2

Ln)

x

x10定理8.2

:設(shè)(x)在區(qū)間[a,b]上滿足條件:(2)存在常數(shù)0

L

1,使得對x

a,b,都有(

x)

L則方程x

(x)在[a,b]上有唯一的根x*

.且對任意初值x0

a,b,迭代格式:(1)對任意x

[a,b],有

(

x)

[a,

b]xn1

(

xn

)(n

0,1,

2,)*所產(chǎn)生的序列n

x

均收斂于x

,Lnx

x11

L0并有

x

xn解:(1)f

(x)

(x

1)ex

1(,

0)

0例:給定方程f

(x)

(x

1)ex

1

0;(1)分析該方程存在幾個根;(2)用迭代法求出這些根,精確至5位有效數(shù)字;(3)說明所用迭代格式是收斂的.f

(

x)

xe

x(0,

)0極小值f

(0)

2x

單調(diào)下降lim

f

(

x)

1單調(diào)上升lim

f

(

x)

x

f

f

f

(x)在R上只有一個根f

(

x)

(

x

1)e

x

1

0

x

1

e

xf

(x)

0的近似根為1.2785.(3)迭代函數(shù)(x)

1

e

xn1(n

0,1,2,)令

x

1

e

xn取x0

1(

x)

e

xx[1,2]max

|

(x)

|

e1

1x

[1,2]時,(x)[1,2]由壓縮映像原理,上述迭代格式收斂.

1

0(2)

f

(1)

1

0

f

(2)

e2有根區(qū)間為[1,2]ziteration(inline('1+exp(-x)'),1,1e-4)x1

1.3679,x5

1.2790,x2

1.2546,x6

1.2783,x3

1.2852,x7

1.2785,x4

1.2766,x8

1.2785,迭代序列

xn1

(

xn

)(n

0,1,

2,),

收斂于x證明:

,

使得x

x

,x

,|

'(x)|

L

1|

(

x)

x*

||(

x)

(

x*

)

|

L

|

x

x*

|

定理8.3(局部收斂性定理)如果(x)在x*的鄰域O(x*

,

*

)內(nèi)一階連續(xù)可微,且x

(

x

),

(

x

)

10

對任意

x

[

x

,

x

]則存在正數(shù)

,

,

使得(x)x

,

x

由定理8.2得證.

80

0.6611

1(

x2

10)2

112(

x)

x

1,214

40

x1

20

(

x)

20

20

2x2

10

1110(

x)

3

x2在1,2上不滿足定理8.2的條件.20

10(2)

f

(

x)

0

x

x

2由定理8.2，迭代收斂(3)

f

(

x)

0

x

2

x

310前邊例題:f

(x)

x3

10x

20

0(1)

f

(

x)

0

x

x3

11x

20(x)

3x2

11

11,不滿足定理8.210(

x)

3

x

0.867

1考慮區(qū)間1.5,1.7,則有2103

x2(

x)

10(3)

f

(

x)

0

x

2

x3

1.7x

1.5,1.7101.5

(

x)

2

x

3x*

1.5,1.7(

x*

)

1*由局部收斂性,當(dāng)x0充分接近x

時，迭代收斂10(

x)

3

x2

0.867

1由定理8.2對x0

[1.5,1.7，]

迭代收斂,

但速度比(2)慢8.2.3

Steffensen方法－簡單迭代法的加速n（一）收斂速度lim

xn

x

,

r,

a

0,

s.t.nx

x

rx

xlimnn1

a*則稱

xn

是

r階收斂于

x

(或

x

的收斂階是r

).n特別地,r

1稱為線性收斂.r

1為超線性收斂,

r

2為平方收斂.（二）Steffensen(斯蒂芬森)方法nn1n

n

n(

y

x

)2

n

n

z

2

y

xx

x可證,當(dāng)(x

)

0,Steffensen方法至少是二次局部收斂的.xn2(

x

x

)2

n1

n

2xn1

xn若{xn

}線性收斂于x,則xn

xn以更快速度收斂于x.將Aitken（埃特肯）加速技巧用于線性收斂的迭代序列，即得Steffensen方法，其計算過程為yn

(

xn

)zn

(

yn

)定理8.4

:設(shè)(x)在x*鄰近有r階導(dǎo)數(shù)(r

2),且*x

(

x

),

(

k

)

(

x

)

0 (k

1,r

1),

(

r

)

(

x

)

0則迭代公式xn1

(xn

)(n

0,1,2,)產(chǎn)生的迭代序列xn

是r階收斂于x

的.證明:由定理8.3,

0,使得0

x

x

,

x

迭代序列xn1

(xn)(n

0,1,2,)收斂于x

*n

且

x

x

,

x

nnnnr!

r

r1

(x

x

)(r

1)!

(x

x

)(r

)()(r1)(x

)

x

)

(x

)

(x

)

(x

)(x*x

之間.n

在

x

和

(

r

)

(

)n(

x

x

)rr!x

x

n1

limn(

r

)

(

x

)

0r

!rnx

xxn1

x*故迭代序列

xn

r階收斂于

x

,注:若0

|

'(x*

)|

1,迭代法是線性收斂的.*

*nx

x

(

x

)

(

x

)n1n(

x

x

)rx

x

n1

r!(

xn

x

)r

(

r

)

(

)

(

x

)

目標(biāo)式子xn1x

(

x2

3a)

n

n

3x2

a(n

0,1,)n產(chǎn)生的迭代序列{

xn

}收斂于

a

,

且收斂階為3.例:

證明當(dāng)

x0充分接近

a時,按迭代公式x(

x2

3a)3x2

a解

:

迭代函數(shù)

(x)

'(x)

(3

x2

a)(3

x2

3a)

x(

x2(3

x2

a)2

3a)6

x

(

x2

a)2(3

x2

a)2x*[(

x*

)23(

x*

)2

a

3a]*解

(x*

)

x*

,

即

x

得

x*

0,

x*

a

,由定理

8.4,

{

xn

}是3階收斂的.(

x

2

a)2(3

x

2

a)2'(

x)

16

xa(

x

2

a)(3

x

2

a)3(

x)a(9x4

18x2a

a2

)(3x2

a)4(

x)

16(3)

18a

1

0

,'(

a

)

0

,

(

a

)

0

,a(3a

1)3a

)

16

9a

2

(

3)

(由定理

8.3,

x0充分接近

a

時，迭代格式收斂到

aa

xk

)3lima

xk

1k

(證明收斂階的另法k(

a

x

)3(3

x2

a)2x

(

x

3a)a

k

k

lim

k

k

1k

a)

limk

(3

x

2

0(4a)1則{xk

}是3

階收斂的.§8.3

Newton法與弦截法y

f

(

x~)

f

(

x~)(

x

x~)當(dāng)f

(x)

0時,切線方程有根,8.3.1

Newton法基本思想：將非線性方程線性化，以線性方程的解

近非線性方程的解。設(shè)f

(x)連續(xù)可導(dǎo),x是方程f

(x)

0的根,曲線

y

f

(

x),

過(

x,

f

(

x))的切線方程~f

(x

)x

x~

f

(

x~)當(dāng)x充分接近x*

,用切線方程的根近似原方程的根.xyx*x01x由此導(dǎo)出迭代公式(n

0,1,2,)f

(

x

)f

(

x

)nnxn1

xn

按此迭代公式求方程f

(x)

0的近似解稱為Newton法.幾何意義:以曲線

y

f

(

x)在點(

xn

,

f

(

xn

))的切線與x軸的交點近似曲線與

x軸的交點,

故Newton法又稱切

.001f

(

x

)

f

(

x0

)x

xxyx01

f

(

x

)f

(

x

)1x2

x1f

(

x~)x

x~

f

(

x~)1xx*x2例:用Newton法求方程f

(x)

x3

10

x

20

0的根,取初值

x0

1.5xn1

xn代入初值得：n3x2

10x1

1.5970149x3

1.5945621f

(

x)

3

x2

10Newton法迭代公式

xn3

10xn

20x2

1.5945637x4

1.5945621f

(x

)nx

x

f

(xn

)(n

0,1,2,)n1n

10

x

20解：f

(x)

x

3znewton(inline('x^3+10*x-20'),inline('3*x^2+10'),1.5,1e-4,200)定理

8.5

:

設(shè)

f

(

x)在其零點

x*

鄰近二階可微,

且f

'(

x*

)

0,

則

0,

對x

O(

x*

,

),

Newton法0產(chǎn)生的迭代序列至少二階收斂于x*

.證明:Newton法的迭代函數(shù)為由定理8.4，Newton法至少二階收斂。f

(

x)(

x)

x

f

(

x)(

x

)

x

f

(

x

)2

f

(

x

)

f

(

x

)2f

(

x

)(

x

)

1

f

(

x

)2f

(

x

)

f

(

x

)

0說明:當(dāng)x是單根時,Newton法收斂快,

精度高,

穩(wěn)定性好,但對初值要求苛刻.由于每次迭代需計算函數(shù)值,

導(dǎo)數(shù)值各一次,計算量大,只適用于導(dǎo)數(shù)易求的情況.當(dāng)x為r重根(r

1)時,Newton法是線性收斂的,且rr

1xn`

xxn1

xlimn(a)令(x)

f

(x)

,可以證明x*是(x)的單根,f

(

x)對(x)用Newton法得迭代公式xn1

xn

2f

(

xn

)f

(

xn

)f

(

x

)

f

(

xn

)

f

(

xn

)

n

r

f

(

xn

)nn1(b)

x

xnf

(x

)以上兩種改進都是至少二階收斂的。改進的Newton法(重數(shù)r

2)nnn1

x

f

(

xn

)f

(

x

)Newton

迭代x一個反常的例子f

(

x)

sign(

x

2)|

x

2

|在Newton公式中，用差商代替導(dǎo)數(shù)，即f

(

x

)

f

(

xn

)

f

(

xn1

)n

n1x

xn即得迭代公式n

n1f

(xn

)f

(x

)

f

(x

)xn1

xn

(x

x

)

(n

1,2,)n

n1按此公式求方稱

f

(

x)

0的近似解稱為弦截法.

幾何意義:

以過曲線上兩點(

xn1

,

f

(

xn1

)),(

xn

,

f

(

xn

))的直線與x軸的交點為曲線與x軸交點的近似,

故弦截法又稱為割

,

線性插值法.8.3.2弦截法x1

x0切線/*

tangent

line

*/割線/*

secant

line

*/切線斜率

割線斜率k

k

1f

(

x

)

f

(

xk

)

f

(

xk1

)x

xkf

(

xk

)

f

(

xk1

)

f

(

xk

)(xk

xk

1

)kk

1

x

x注:弦截法需要兩個初值x0

,x1才能運行,通常取有根區(qū)間的兩個端點作為初值.定理8.6

:設(shè)f

(x)在x*鄰近二階連續(xù)可微,且f

(

x

)

0,

f

(

x

)

0則

0,當(dāng)x

,

x

O(

x

,

)時,由弦截法產(chǎn)生的序列0

1*{

xn

}收斂于x

,

且收斂階至少為

1.618.證明略,因弦截法非單步法,不能用定理8.4判別例:

用割 求

f

(

x)

x3

2x2

10

x

20的根,

要求2|

xk

1

xk

|

10解

:

因為

f

(1)

7

0,

f

(2)

12

0,在[1,2]上

f

'(

x)

3x2

4

x

10

0,

所以

f

(

x)在

[1,2]

內(nèi)存在唯一的

零點,割 的迭代公式

:取區(qū)間端點分別為迭代初始兩點,即x0

1,x1

2,代入x2

1.304347826,

x3

1.357912305,x4

1.369013326,x5

1.36880746,

取x*

1.37(k

1,2)f

(

x

)f

(

x

)

f

(

x

)kk

k

1xk

xk

1xk

1

xk

znewton2(inline('x^3+2*x^2+10*x-20'),1,2,1e-2,200)類似割

，過三點做

f(x)

的二次插值多項式§8.4

拋物

（Muller法）y(x)xSecant

linex1x2x3Parabola過(x1,f

(x1

)),(x2

,f

(x2

))和(x3

,f

(x3

))做二次插值多項式y(tǒng)

f

(x3

)

f

[x3,

x2](x

x3)

f

[x3,

x2,

x1](x

x3)(x

x2)y

c

b(

x

x3

)

a(

x

x3

)2c

f

(

x3

)3

2

1a

f

[

x

,

x

,

x

]3

2

3

2

1

3

2b

f

[

x

,

x

]

f

[

x

,

x

,

x

](

x

x

)*已知

x

的三個近似值

x

,

x

,

x1

2

3

3，求與x

更接近的根b2|

b

|

4acx

x

2c

sign(b)

32c

sign(b)|

b

|

b2

4ac令x4

x3

算法說明：stepxy11.594900337514760.0059626661120521.59456090312589-0.0000213915241731.594562116640590.00000000016641例:

用拋物

求方程

f

(

x)

x3

10

x

20

0的根zmuller(1.5,1.75,2,1e-6,

100)001f

(

x

)

f

(

x0

)x

xxyx*x011f

(

x

)f

(

x

)x2

x1

1x2xx1

x0/*tangent

line

*//*

secant

line

*/y(x)xSecant

linex1x2x3Parabola求根問題的敏感性與代數(shù)方程

a

xn

1n

1f

(

x)

a

xnn

a

x

a

0，1

0a

0，n

1n多項式方程20若系數(shù)有微小擾動其根變化很大，這種根對系數(shù)變化的敏感性成為

的代數(shù)方程Wilkinson多項式W(

x)

(

x

i)

(

x

1)(

x

2)

(

x

20)i=1

x20

210

x19

20!20W(

x)

(

x

i)

(

x

1)(

x

2)

(

x

20)i=1x19的系數(shù)有小的擾動10-7§8.5非線