chap8非线性方程及非线性方程组解法

第八章

非线性方程(组)的解法例8‐1:

一个半径为r

,密度为

的木质球体投入水中,如图,问球体浸入水中部分的深度d

等于多少?球质量为34

r3

,

而球浸入水中排出的水质量30d

[r

2

(x

r)2

]

dx

1

d

2

(3r

d

)根据Archimedes

定律,有2

31343d

(3r

d

)

r

即d

满足代数方程d

3

3rd

2

4r3

0例如某种木材0.638kg/cm3,球半径r

5cm

，则d

满足三次方程d

3

15d

2

319

0设f(d

)

d

3

15d

2

319

，不难验证

f

(0)

319,

f

(5)

69

f

(10)

181，区间(,0)和(10,)上，方程各有一实根，但这都不是物理问题的解。而方程另有一个实根d

(5,10)，这才是

感

的解。例8‐2：公元1225

年，比萨的数学家Leonardo（即Fibonacci，1170‐1250）研究了方程x3

2x2

10x

20

0得到一个根x*

1.368808107

.没有人知道他用什么方法得到这个值.例

8‐3:

数学上求非线性方程组的问题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重根或函数f

(x)的k重零点.非线性方程:设f

(x)为非线性函数,方程f

(

x)

0

(8

1)称为非线性方程.例:

方程重根:f

(x)

0

有k重根f

(

x)

(x

a)k

(

x),

(a)

0f

(x)

ex

sin

x

010n1n

n1例:代数方程

f

(x)

a

xn

ax

a

x

a

0，n

1abb1a2a1x0

x*x1b2§8.1对分区间法（二分法）确定有根区间:若

f

(

x

)

C

a,

b,

f(a

)f(b)

0,

则(a,

b)内必有方程(8

1)的根,

称其为有根区间.逐次对分区间.取根的近似值.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根的近似值:逐次对分区间得区间套ax1b2bb1a2a1x0

x*其误差为:用对分区间法求根步骤：2

bn

(n

0,1,)

ann2.逐次对分求根区间求近似根x若

f

(an

)

f

(

xn

)

0

则

an1

an

,

bn1

xn否则an1

xn

,bn1

bn1.确定求根区间[a,

b]

f

(a)

f

(b)

0n

ln(b

a)

ln

1ln

2直到满足精度.注释:误差公式事先估计等分的次数2n1b

a

n

4ln10

13.3ln0.5故n

14,x14即为满足精度要求的近似解.2解

:

确定有根区间误差不超过1

104

(精确到小数后第四位)例:

求方程

f

(

x)

x3

10x

20

0的一实根,

要求

f

(1)

9

0,

f

(2)

8

0n2n11,2为有根区间,

取

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

的结果一致！§8.2简单迭代法简单迭代法的一般形式及其几何意义x

(

x)(n

0,1,

2,)从初值x0出发,逐次代入迭代公式产生序列xn

,以xn

近似f

(x)

0的根,(x)称为迭代函数.f

(

x)

0

构造迭代格式:xn1

(xn

)结论:若xn

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的根,

要求精确到六位小数,

取

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此迭代序列发散。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表明:对同一方程可构造不同的迭代格式，产生的迭代序列收敛性也不同。迭代序列的收敛性取决于迭代函数在方程根的邻近区间的性态。8.2.2迭代法的收敛条件定理8.1

:(压缩映像原理)设函数

(x

)在区间上满足:对任意的

x

[a

,

b],

都有a

(

x

)

b存在常数0

L

1,

使得对一切

x

,

y

a

,

b

,

都有

(

x

)

(

y

)

L

x

y则方程x

(x

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

.且对任意初值x0

a,b,迭代格式:xn1

(

xn

)(n

0,1,2,)*n所产生的序列

x均收敛于x

,

x01

L

x1Ln

并有

x

xn

结论1结论2结论3证明:函数

(

x

)在区间[a

,

b]上连续,

令

(

x

)

x

(

x，)

则

(x)在[a,b]上连续，且

(a)

a

(a)

0，(b)

b

(b)

0由连续函数介值定理,存在

[a,b，]即

(

)再证唯一性:使得

(

)

0,设

x1

x2

[a,

b，]

x1

(

x1

),

x2

(

x2

),|

x1

x2

||

(

x1

)

(

x2

)

|

L

|

x1

x2

||

x1

x2

|，唯一性得证。|

xn1

x

||

(

x

)

(

x

)

|

L

|

x

x*

|设方程x

(x

)在区间[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类似的，对任意正整数k

,有xn

p

xn

xn

p

xn

p1

xn

p1

xn

p2

xn1

xn于是，对任意正整数n，p,有令p

,有x1

x0Ln1

Lnx*

x

证毕x1

x0

(1

Lp)Ln1

L

(Lnp1

Lnp2

Ln)

x

x10定理8.2

:设(x)在区间[a,b]上满足条件:(2)存在常数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,)*所产生的序列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位有效数字;(3)说明所用迭代格式是收敛的.f

(

x)

xe

x(0,

)0极小值f

(0)

2x

单调下降lim

f

(

x)

1单调上升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)迭代函数(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有根区间为[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*

,

*

)内一阶连续可微,且x

(

x

),

(

x

)

10

对任意

x

[

x

,

x

]则存在正数

,

,

使得(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考虑区间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*由局部收敛性,当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可证,当(x

)

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

x

x

)2

n1

n

2xn1

xn若{xn

}线性收敛于x,则xn

xn以更快速度收敛于x.将Aitken（埃特肯）加速技巧用于线性收敛的迭代序列，即得Steffensen方法，其计算过程为yn

(

xn

)zn

(

yn

)定理8.4

:设(x)在x*邻近有r阶导数(r

2),且*x

(

x

),

(

k

)

(

x

)

0 (k

1,r

1),

(

r

)

(

x

)

0则迭代公式xn1

(xn

)(n

0,1,2,)产生的迭代序列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

)

目标式子xn1x

(

x2

3a)

n

n

3x2

a(n

0,1,)n产生的迭代序列{

xn

}收敛于

a

,

且收敛阶为3.例:

证明当

x0充分接近

a时,按迭代公式x(

x2

3a)3x2

a解

:

迭代函数

(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~)当f

(x)

0时,切线方程有根,8.3.1

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

近非线性方程的解。设f

(x)连续可导,x是方程f

(x)

0的根,曲线

y

f

(

x),

过(

x,

f

(

x))的切线方程~f

(x

)x

x~

f

(

x~)当x充分接近x*

,用切线方程的根近似原方程的根.xyx*x01x由此导出迭代公式(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

:

设

f

(

x)在其零点

x*

邻近二阶可微,

且f

'(

x*

)

0,

则

0,

对x

O(

x*

,

),

Newton法0产生的迭代序列至少二阶收敛于x*

.证明:Newton法的迭代函数为由定理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说明:当x是单根时,Newton法收敛快,

精度高,

稳定性好,但对初值要求苛刻.由于每次迭代需计算函数值,

导数值各一次,计算量大,只适用于导数易求的情况.当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法(重数r

2)nnn1

x

f

(

xn

)f

(

x

)Newton

迭代x一个反常的例子f

(

x)

sign(

x

2)|

x

2

|在Newton公式中，用差商代替导数，即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才能运行,通常取有根区间的两个端点作为初值.定理8.6

:设f

(x)在x*邻近二阶连续可微,且f

(

x

)

0,

f

(

x

)

0则

0,当x

,

x

O(

x

,

)时,由弦截法产生的序列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]

内存在唯一的

零点,割 的迭代公式

:取区间端点分别为迭代初始两点,即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

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求根问题的敏感性与代数方程

a

xn

1n

1f

(

x)

a

xnn

a

x

a

0，1

0a

0，n

1n多项式方程20若系数有微小扰动其根变化很大，这种根对系数变化的敏感性成为

的代数方程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的系数有小的扰动10-7§8.5非线