第 2章
非线性方程与方程组的数值解法
本章重点介绍求解非线性方程 的几种常见和有
效的数值方法,同时也对非线性方程组
求解,简单介绍一些最基本的解法,无论在理论上,还是在
实际应用中,这些数值解法都是对经典的解析方法的突
破性开拓和补充,许多问题的求解,在解析方法无能为力
时,数值方法则可以借助于计算机出色完成,
0)( ?xf
),,2,1(0),,,( 21 nixxxf ni ?? ??
2.1二分法
求非线性方程 0)( ?xf
确定方程的有根区间
计算根的近似值
的根的方法
分为两步,
? 首先确定有限区间：依据零点定理。
设,且,
则方程 在区间 上至少有一个根。
如果 在 上恒正或恒负，则此根唯
一。
],[)( baCxf ? 0)()( ?bfaf
0)( ?xf ),( ba
)(' xf ),( ba
等步长扫描法求有根区间
? 用计算机求有根区间：等步长扫描法。
设 h>0是给定的步长，取,
若 则扫描成功；否则令
,继续上述方法，直到成
功。如果 则扫描失败。再将 h 缩小,
继续以上步骤。
haxax ??? 10,
0)()( 10 ?? xfxf
hxxxx ??? 0110,
bx ?1
等步长扫描算法
? 算法：（求方程 的有根区间）
(1) 输入 ；
(2) ；
(3),若 输出失败信息，
停机。
(4)若 。输出,已算出方程的一个根，停
机。
0)( ?xf
hba,,
)(0 aff ?
)(,1 xffhax ??? bx?
01 ?f x
等步长扫描算法
(5) 若 。输出 为有根区间，
停机
(6),转 3）
? 注：如果对足够小的步长 h扫描失败。
说明,
? 在 内无根
? 在 内有偶重根
010 ?ff ],[,,xaxa
xa ?
],[ ba
],[ ba
二分法
? 用二分法 (将区间对平分 )求解。
令
若,则 为有根区间，否
则 为有根区间
记新的有根区间为, 则
且
)(,,1121111 bacbbaa ????
0)()( 11 ?cfaf ],[
11 ca
],[ 11 bc
],[ 22 ba
],[],[ 2211 baba ?
)( 112122 abab ???
二分法
? 对 重复上述做法得
? 且
],[ 22 ba
......],[......],[],[ 2211 ???? nn bababa
)(2 1 1 abab nnn ??? ?
二分法
设 所求的根为,
则
即
取 为 的近似解
?x
.,.,,.2,1],[ ??? nbax nn
......2,1??? ? nbxa nn
0)(2 1l i m)(l i m 1n ???? ????? abab nnnn?
???? ???? xba nnnn limlim
)(21 nnn bacx ????
?x
求方程 f(x)=0的根的二分法算法
).(
2
1
)4(;e n d w h i l e
].,[],[
];,[],[0)()()2
);(),(
2
1
)1
||)3(;3,
,10)()()2(;,],[:)1(
bax
bxbae l s e
xabat h e nxfafif
xfbax
baw h i l e
e l s eba
t h e nbfafif
baba
??
?
??
??
??
?
输出
计算令
时做
步转第值输入
重新步返回第
值及精度控制量的有根区间输入
?
?
求方程 f(x)=0的全部实根的二分法算法
);();(
2
1
1
||wh i l e)2
e n d wh i l e ;;;0)()(wh i l e)1
wh i l e)3(;;)2(;,,,:)1(
11
0
11
11111
1
111
xfbax
ab
habaabfaf
bb
habaa
hba
计算
时做
做
时做
输入
??
??
????
?
???
?
?
求方程 f(x)=0的全部实根的二分法算法;e n d w h i l e;;
10;:)3;e n d w h i l e
].,[],[
],[],[0)()(if3
);3(0)(if2
111
111
1111
0
0
hab
h
xax
bxbae l s e
xabat h e nxfaf
xf
????
?
??
?
输出
转
例题
? 例 1 设方程
解：取 h=0.1,扫描得,
又
即 在 有唯一根。
]2,1[],[,1)( 3 ???? baxxxf
0344.0)4.1(
061.0)3.1(
??
???
f
f
].4.1,3.1[方程的有根区间为?
]4.1,3.1[,013)( 2' ???? xxxf?
0)( ?xf ]4.1,3.1[
2.2一般迭代法
? 2.2.1 迭代法及收敛性
对于 有时可以写成 形式
如,
0)( ?xf )( xx ??
3
33
1
101
xx
xxxx
??
??????
xxxx c o s0c o s ????
迭代法及收敛性
考察方程 。这种方程是隐式方
程，因而不能直接求出它的根，但如果
给出根的某个猜测值, 代入 中
的右端得到,再以 为一个猜
测值，代入 的右端得
反复迭代得
)( xx ??
0x
)( xx ??
)( 01 xx ?? 1x
)( xx ?? )(
12 xx ??
,......1,0)( k1k ??? kxx ?
迭代法及收敛性
若 收敛，即
则得 是 的一个根
}{ kx ?
?? ? xxk klim
?x )( xx ??
)()l i m()(l i ml i m 1n ????? ???????? xxxxx nnnnn ????
迭代法的几何意义
? 交点的横坐标
*x
??
?
?
???
)()( xy
xyxx
??
y=x
2x 0x1x
简单迭代法
将 变为另一种等价形式 。
选取 的某一近似值,则按递推
关系 产生的迭代序列
。这种方法算为简单迭代法。
0)( ?xf )( xx ??
?x ],[
0 bax ?
,......1,0)( k1k ??? kxx ?
}{ kx
例题
例 2.2.1 试用迭代法求方程
在区间 (1,2)内的实根。
解：由 建立迭代关系
k=10,1,2,3……,
计算结果如下,
3 1?? xx
01)( 3 ???? xxxf
31 1??? kk xx
例题
? 精确到小数点后五位
5102132472.1 ?? ??? ?x
例题
? 但如果由 建立迭代公式
仍取,则有,
显然结果越来越大,是发散序列
1x 3 ??x
,...2,1131 ???? kxx kk
5.10 ?x 2,3 7 51 ?x 1 2,3 92 ?x
}{ kx
迭代法的收敛性
? 定理 2.2.1（压缩映像原理）
设迭代函数 在闭区间 上满足
（ 1）
（ 2） 满足 Lipschitz条件
即 有
且 。
)(x? ],[ ba
],[)(],[ baxbax ??? ?
)(x?
],[,21 baxx ?? )()( 2121 xxLxx ??? ??
10 ?? L
压缩映像原理
则 在 上存在 唯一解,
且对,由 产生
的序列 收敛于 。
)( xx ??
],[0 bax ?? )( k1k xx ???
}.{ 1?kx ?x
],[ ba ?x
压缩映像原理
? 证明：不失一般性,不妨设
否则 为方程的根。
? 首先证明根的存在性
令
bbaa ?? )(,)( ??
ba或
xxx ?? )()( ??
压缩映像原理
则, 即
由条件 2） 是 上的连续函数
是 上的连续函数。
故由零点定理 在 上至少有一根
0)()( ??? aaa ?? 0)( ?b? 0)()( ?? ba ??
)(x? ],[ ba
)( x?所以
],[ ba0)( ?x?
],[ ba
),( bax ??
压缩映像原理
? 再证根的唯一性
设有 均为方程的根
则
因为 0<L<1,所以只可能,
即根是唯一的。
],[,21 baxx ???
|||)()(||| 212121 ?????? ????? xxLxxxx ??
?? ? 21 xx
压缩映像原理
? 最后证迭代序列的收敛性
与 n 无关，而 0<L<1
即
|)()(||| 1 ??? ??? xxxx nn ??由于
|| 1 ?? ?? xxL n
|| 0 ??? xxL n
......?
?xx,
0因为
0l i m||||l i m 0 ???? ?????? nnnn Lxxxx所以
?
?? ? xx nnlim
压缩映像原理
? 误差估计
? 若 满足定理 2.2.1条件，则
?
这是事后估计，也就是停机标准。 L越小，收敛速度越快。
?
这是事前估计。选取 n，预先估计迭代次数。
)( xx ??
||L1 L|| 1nn ?? ???? xxxx n
||L1 L|| 01
n
xxxx n ???? ?
例题
? 例 2.2.2 证明函数 在区间 [1，
2]上满足迭代收敛条件。
? 证明,
3 1)x( ?? x?
上严格单调增函数。是区间所以
因为
],[)(
]2,1[0)1(
3
1
)x( 3
2
'
bax
xx
?
? ????
?
例题
]2,1[143 1|)1(31||)(| 33
2
' ?????? ? xLxx?又
23)2(12)1( 33 ???? ??,而
）。满足条件（，所以即 1)(]2,1[)]2(),1([ x??? ?
）。满足条件（所以 2)( x?
满足压缩映像原理。在故 ]2,1[1)x( 3 ?? x?
例题
? 若取迭代函数,
不满足压缩映像原理，故不能肯定
收敛到方程的根。
1)x( 3 ?? x?
]2,1[3|3||)(| 2' ??? xxx?因为
,...,1,0)(1 ??? nxx nn ?
简单迭代收敛情况的几何解释
2.2.2 Steffensen加速收敛法
? 迭代法收敛的阶
定义 2.2.1 设序列 收敛到,若有实
数 和非零常数 C,使得
其中，,则称该序列是 p 阶收敛的，
C 称为渐进误差常数。
?0n}x{ *x
1?p
Cee p
n
n
n
??
??
1lim
*xxe nn ??
迭代法收敛的阶
当 p=1时，称为线性收敛；
当 p>1时，称为超线性收敛；
当 p=2时，称为平方收敛或二次收敛。
迭代法收敛的阶
? 定理 2.2.2 设 是方程 的不动
点,若为足够小的正数 。
如果 且,则从任意
出发，由 产生的序列 收
敛到,当 时敛速是线性的。
*x )(xx ??
? ],[ ** ?? ???? xx
??? Cx)(? 1|)(| * ?? x? ??0x
)(1 kk xx ??? ?0}{ nx
*x 0)( ?? x?
迭代法收敛的阶
? 证明,
? 满足压缩映像原理
知，及由 ???? Cxx )(1|)(| '* ??
足够小时，有? )(1|)(| ????? xLx?
?????? ?????????
??
|||||)(||)()(||)(| **** xxxxxxxx
x 有因此，对于
迭代法收敛的阶
? 敛速是线性的
线性收敛到 。
0)()()(l i ml i m **
*
1
n
??????
??
?
??
xxx xxee
n
n
nn
n ???因为
。收敛到故 *0}{ xx n ?
满足压缩映像原理，所以即 )(,)( xx ?? ??
?0}{ nx所以 *x
Steffensen迭代格式
? 由线性收敛知
当 n充分大时有
即
0limlim 1
1
2
n ???
?
???
?
?? Ce
e
e
e
n
n
nn
n
n
n
n
n
e
e
e
e 1
1
2 ?
?
? ?
*
*
1
*
1
*
2
xx
xx
xx
xx
n
n
n
n
?
??
?
? ?
?
?
Steffensen迭代格式
? 展开有,
nnn
nn
n xxx
xxxx
??
???
??
?
12
2
1*
2
)(
2**12 1**2 )(2))(( xxxxxxxx nnnn ????? ???
2**12 12**2*2 )(2)( xxxxxxxxxxx nnnnnn ?????? ????
*12 1*2*2 2 xxxxxxxxx nnnnnn ???? ????
2 1212* )2( ???? ????? nnnnnn xxxxxxx
Steffensen迭代格式
? 已知,则,
? 改成
nx
)(1 nn xx ??? ))((2 nn xx ????
nnn
nn
nn
nn
nn
xyz
xy
xx
yz
xy
??
?
??
?
?
?
2
)(
)(
)(
2
1
?
?
n=0,1,2,…
Steffensen迭代格式
? 也可以改写成
? 其中迭代函数
,......)1,0()(1 ??? nxx nn ?
xxx
xxxx
??
???
)(2))((
])([)( 2
???
??
Steffensen迭代法收敛的充要条件
? 定理 2.2.3
],,[)( **1 ??? ????? ? xxCx,设函数
。件是的不动点的充分必要条是 )()( *** xxxxx ?? ??
，则为足够小的正数，且 1)( * ?? x??
Steffensen迭代法收敛的充要条件
? 证明：必要性
的不动点，是因为 )(* xxx ??
])(2))(()][([])([ 2 xxxxxxx ????? ?????由于
，所以 0))((lim * ??? xxxx ?
，故有 0))((lim * ??? xxxx ? )( ** xx ??即
的不动点。是所以 )(* xxx ??
Steffensen迭代法收敛的充要条件
? 充分性
的不动点有是由 )(* xxx ??
xxx
xxxx
xxxx ??
???
?? )(2))((
])([l i m)]([l i m 2
** ???
??
1)(2)())((
]1)(][)([2l i m
* ?????
????
? xxx
xxx
xx
o
o
????
??型
0]1)([ ]1)(][)([2lim 2*
***
*
??? ????
? x
xxx
xx ?
??
的不动点。是所以 )(* xxx ??
Steffensen算法的收敛速度
!
)(
)(
l i m
}{
)(0)(
0)(...)()(
,],,[
),1()(,)(4.2.2
*)(
*
*
1
*
0
10
*)1(
*)1(**
**
*
p
x
xx
xx
xpx
xxxx
xxx
xx
pCxxxx
p
p
n
n
n
n
kk
p
p
p
?
??
???
???
??
?
?
?
?????
???????
????
???
?
??
?
?
?
?
?
，且阶收敛速度收敛到，以列
产生的序，由，则而
如果为足够小的正数
的不动点是设定理
Steffensen算法的收敛速度
? 定理 2.2.5 在定理 2.2.3假设下，若
产生的序列 至少平方收敛到 。
,.,,,2,1,0
2
)(
)(
)(
2
1
?
?
?
?
?
?
?
?
??
?
??
?
?
?
n
xyz
xy
xx
yz
xy
S t e f f e n s e n
nnn
nn
nn
nn
nn
?
?
迭代格式则由
2C)( ??x?
?0}{ nx *x
*x
Steffensen算法的收敛速度
的不动点，是证明,)(* xxx ?? 。即 )( ** xx ??
1)(
1
1)(
l i m
)(
l i m *
* **
???
??
?
?
?
??
x
x
xx
xx
xx
o
o
xx
?
??
型
又因为
Steffensen算法的收敛速度
*
)(2))((l i m
* xx
xxx
xx ?
??
?
???及
)1)(2)())(((l i m
*
??????
?
xxx
xx
o
o
????
型
1)(2)()( *** ?????? xxx ???
2* ]1)([ ??? x?
Steffensen算法的收敛速度
*
*
* )()(l i m)(
* xx
xxx
xx ?
???
?
???于是有
*
*
2
)(2))((
])([
l i m
* xx
x
xxx
xx
x
xx ?
?
??
?
?
?
?
???
?
*
2
*
)(2))((
]
)(
[
lim1
*
xx
xxx
xx
xx
xx
?
??
?
?
??
? ???
?
0]1)([ ]1([1 2*
2*
??? ???? xx??
Steffensen算法的收敛速度
由定理 2.2.4知 至少以平方速度
收敛到 。
也就是说：简单迭代法是线性收敛；
Steffensen迭代至少平方以上收敛（加速
收敛）。
?0}{ nx
*x
例题
? 例 2.2.3试用 Steffensen算法求解方程
? 解法一、取,由
013 ??? xx
3 1)( ?? xx?
nnn
nn
nn
nn
nn
xyz
xy
xx
yz
xy
??
?
??
?
?
?
2
)(
)(
)(
2
1
?
?
n = 0,1,2,…
例题
? 取初值,计算结果如下,5.1
0 ?x
N Xn Yn Zn
0 1.5 1.357208808 1.330860959
1 1.324899181 1.324752379 1.324724496
2 1.324717957 1.324717957 1.324717957
例题
? 解法二、取,由
? 对于该迭代函数在一般迭代法中是发散的，
而 Steffensen格式却是收敛的。
1)( 3 ?? xx?
nnn
nn
nn
nn
nn
xyz
xy
xx
yz
xy
??
?
??
?
?
?
2
)(
)(
)(
2
1
?
?
n=0,1,2,…
例题
? 取初值,计算结果如下,
N Xn Yn Zn
0 1.5 2.375 1.239648437
1 1.416292975 1.840921915 5.238872769
2 1.355650442 1.491398279 2.317270699
3 1.328948777 1.347062883 1.444351224
4 1.324804489 1.325173544 1.327117281
5 1.324717944 1.324718152 1.324718980
6 1.324717957
5.10 ?x
Steffensen迭代格式几何解释
Steffensen迭代算法
1
10
0
2
001
20
0
100
210
:)3(;
)4
);2/()()3;3|2|)2
);();()1
|)(|wh i l e)2(;,,)1(
x
e n d w h i l e
xx
xyzxyxx
t h e nxyzif
yzxy
xx
x
输出
步做第
做
输入
?
?????
???
??
??
?
??
??
??
Steffensen迭代算法
2.3 Newton迭代法
? 设 x * 是方程 f (x ) = 0的根，又 x0 为 x *
附近的一个值,将 f (x ) 在 x0附近做泰勒
展式
令,则
之间和在其中 0
2
0000 )()(2
1)()()()(
xx
fxxxfxxxfxf
?
?????????
*xx ?
)()(21)()()()(0 20*00*0* ?fxxxfxxxfxf ?????????
Newton迭代法
去掉 的二次项，有,
即
以 x1代替 x0重复以上的过程，继续下去得,
0* xx ?
0)()()( 000*0 ????? xfxxfxxf
)(
)(
0
0
01
*
xf
xfxxx
????
Newton迭代法
,.,,,,,1,0)( )(1 ????? nxf xfxx
n
n
nn
以此产生的序列 {Xn}得到 f(x)=0的近似
解，称为 Newton法，又叫切线法。
Newton迭代法几何解释
? 几何意义
例题
例 2.3.1 用 Newton法求 的
近似解。
解：由零点定理。
0c o s)( ??? xxxf
内有根。在 )2,0(0c o s ??? xx
迭代公式得及由 N e w t onxxf s i n1)( ???
,.,,,,,1,0si n1 c o s1 ?????? nx xxxx
n
nn
nn
例题
0 8 5 1 3 37 3 9.0
7 3 9 0 8 5 1 3 3.07 3 9 0 8 5 1 3 3.0
7 3 9 0 8 5 1 7 8.0;7 3 9 3 6 1 3 3.0
4
4
*
43
21
0
??
??
??
?
xx
xx
xx
x
故取
得取
?
例题
? 例 2.3.2 用 Newton法计算 。
解,
2
20)( 2 ???? aaxxf 其中
迭代公式得及由 N e w t onxxf 2)( ??
,.,,,,,1,0)2(212 2
2
1 ???
???
? nxxx
xxx
n
n
n
n
nn
。有十位有效数的近似值
是已的精确值相比，。与
，，则取
33
210
24 1 4 2 1 3 5 6 2.1
4 1 4 2 1 5 6 8 6.11, 4 1 6 6 6 6 6 75.1
xx
xxx
?
???
Newton迭代法算法框图
Newton迭代法算法
。输出
）转（
做
输入
1
10
1001
0
0100
0
:)4(;2)3;)2;/)1
||wh i l e( 3 )
);();()2(;,)1(
x
e n d w h i l e
xx
ffxx
f
xffxff
x
?
??
?
???
?
?
Newton迭代法收敛性
定理 2.3.1 设函数,且满足
若初值 满足 时，由 Newton
法产生的序列收敛到 在 [a,b]上的唯一根。
],[)( 2 baCxf ?
上恒正或恒负。在 ],[)()3
]);,[(,0)()2;0)()()1
baxf
baxxf
bfaf
??
???
?
],[0 bax ? 0)()( 00 ??? xfxf
0)( ?xf
Newton迭代法收敛性
证明,根的存在性
? 根的唯一性
内至少有一个根。
在知）及由条件（
),(
0)(],,[)(1
ba
xfbaCxf ??
。记此根为内有唯一根在
上严格单调函数，因此是故
保号，知及由
*,),(
0)(],[)(
)(],bC [ a,)(,0)(
xba
xfbaxf
xfxfxf
?
?????
Newton迭代法收敛性
? 收敛性
))(()(0
)(
)(
0)(,0)(
,0)(],,[0)()(
0)(,0)(,0)(,0)(
0100
0
0
0
01
00
0
*
000
xxxfxf
x
xf
xf
xx
xfxf
xfbxxxfxf
xfxfbfaf
????
?
?
??
?????
?????
???????
即有
，所以
知，由
，不妨设
Newton迭代法收敛性
继续上述推理有代替。再以因此有
两式相减
展式由另一方面
0101
*
2
0
*
0
1
*
2
0
*
0
*
00
*
0)(
)(
)(
2
1
))((
2
1
))(()()(0
T a y l o r,
xxxxx
xx
xf
f
xx
xxfxxxfxfxf
??
??
?
??
???
?????????
?
?
Newton迭代法收敛性
。，由根的唯一性知可得时当
由
。故必有极限，记
。是单调减有下界的序列故序列
*
1
0
011
*
0)(,
,.,,2,1
)(
)(
l i m
}{
.,,.,,
xaafn
n
xf
xf
xx
ax
x
xxxxx
n
n
nn
n
n
n
nn
????
?
?
??
?
??????
?
??
?
?
Newton迭代法收敛性
? 推论 在定理 2.3.1条件下,Newton迭代
法具有平方收敛速度。
故结论成立。
之间，则与介于其中，
证明，一般有类似定理证明
0
)(
)(
2
1
l i m
)(
)(
)(
2
1
1.3.2
*'
*''
2
1
*
2*
1n
*
??
?
?
??
???
?
??
?
xf
xf
e
e
xx
xx
xf
f
xx
n
n
n
nn
n
n
n
?
?
代数方程的 Newton迭代法
? 代数方程的 Newton迭代法推导
设 n次代数方程
用 Newton迭代法求有限区间的实根，则要计算
,一般采用秦九韶算法。
,.,,2,1)( )(1 ????? nxf xfxx
n
n
nn
)0(0)( 0110 ????????? ? aaxaxaxf nnn
)(),( nn xfxf ?
代数方程的 Newton迭代法
? 由 Taylor展式
)2(
!
)(
)(.,,
!2
)(
)()()(
)1()()()(
!
)(
)(
.,,
!2
)(
)()()()()(
)(
1'
)(
2'
n
xf
xx
xf
xxxfxQ
xQxxxf
n
xf
xx
xf
xxxfxxxfxf
n
n
n
n
n
nn
nn
n
n
n
n
n
nnnn
?
???
??
???
?????
?
??
?????
其中
代数方程的 Newton迭代法
)3()(
)(
)()(),()()2(
1
2
1
1
0
''
?
?? ???????
??
n
nn
nnnn
bxbxbxQ
xQ
xxxfxfxQ
的余式，令除以
为且式知，由
);()(1
)()1(
n
n
xfxQn
xfxx
，余式为次多项式为
，得商）去除式表示，用（
?
?
nn
nn
n
nn
nn
axaxaxa
bxbxbxxxfxf
?????
?????????
?
?
?
??
1
1
10
1
2
1
1
0
...
])[()()(
1)3( ）式得式代入（
),.,,,2,1(
)(
1
00
nkx
xfb
bab
ab
x
n
nn
kkk
?
?
?
?
??
?
?
?
??
?
?
的同次幂系数得比较等式两边
代数方程的 Newton迭代法
同理
)()()()(
)(
' xRxxxfxQ
xQxx
nn
n
???
? 有取除以用
)4()( 23120 ??? ??????? nnn cxcxcxR令
12
2
1
1
0
2
3
1
2
0
.,,
])[()()(
)3()4(
??
??
?
??
?????
??????????
nn
nn
n
nn
nn
bxbxbxb
cxcxcxxxfxQ
式得式代入
代数方程的 Newton迭代法
比较 x的同次幂系数得,
故代数方程的 Newton迭代公式
)1,.,,,2,1(
)(1
1
00
??
?
?
?
?
?
??
??
?
?
? nkx
xfc
cbc
bc
n
nn
kkk
,.,, )2,1(
1
1 ???
?
? nc
bxx
n
n
nn
代数方程的 Newton迭代法算法
步。返回第
停止计算输出
做对
计算
输入
2)(,;,||( 4 );)(3;;
1,.,,,2,1)2;;)1
);(),()2(;,),,.,,,2,1,0(:)1(
10
1
*
01
1
0
01
0101000
0100
00
0
xxe l s e
xxt h e nxxif
f
f
xx
xfffxfaf
nk
ffaf
xfxf
xnia
k
i
?
???
??
????
??
??
?
?
?
?
2.4弦截法
? Newton迭代法有一个较强的要求是
且存在。因此，用弦的斜率
近似的替代 。
0)( ?? xf
)(xf ?
)(
)()(
)(
))(,(P))(,(P
,,],[)(
1
01
01
1
111000
10
*
xx
xx
xfxf
xfy
xfxxfx
bxaxxbaxf
?
?
?
??
??
得弦的方程及则过
，取上有唯一零点在设
弦截法
? 令 y=0,解得弦与 x轴的交点是坐标 x2
.
,.,, )2,1()(
)()(
.,,,,,,
)(
)()(
0)(
)()(
)(
0
0
1
320
1
01
01
12
12
01
01
1
称之为定端点弦截法
计算再由
解得
?
?
?
??
?
?
??
??
?
?
?
?
nxf
xfxf
xx
xx
xxx
xf
xfxf
xx
xx
xx
xx
xfxf
xf
n
n
n
nn
弦截法
.,
,.,, )2,1()(
)()(
,,
1
1
1
321
又称快速弦截法称之为变端点弦截法
以此类推计算若由
?
?
?
??
?
?
?
nxf
xfxf
xx
xx
xxx
n
nn
nn
nn
弦截法的几何解释
例题
例 2.4.1 用快速弦截法求方程
在区间（ 1,2）内的实根。
解：取 x0=1,x1=2,代入公式 2.4.2计算结果,如
表 2.4.1所示。
01)( 3 ???? xxxf
k xk f(xk)
0 1 -1
1 2 5
2 1.166666667 -0.57870369
3 1.253112023 -0.28536302
4 1.337206444 0.053880579
5 1.323850096 -0.0036981168
6 1.324707936 -4.273521*10E-5
7 1.324717965 3.79*10E-8
弦截法收敛定理
则
其中
如果的根是为足够小的正数
设定理
0|)(|m a x|,)(|m a x
1
2
,0)(,
],,[],[,],[)(1.4.2
12
1
2
*
**2
??????
??
?
????
????
xfmxfM
m
M
q
xfx
xxbabaCxf
bxabxa
?
?
??
弦截法收敛定理
。的敛速收敛到以确定的序列
由
线性收敛到确定的序列
由
*
0
1
1
*
0
0
1
2
15
}{
,.,,2,1)(
)()(
)2(;}{
,.,,2,1)(
)()(
)1(
xpx
nxf
xfxf
xx
xx
xx
nxf
xfxf
xx
xx
n
n
n
nn
nn
n
n
n
n
nn
?
?
?
?
?
??
?
?
?
??
?
?
?
求解方程 f(x)=0的快速弦截法
。输出
停止计算输出失败信息
时做
输入
Lx
NL
ffffxxxx
LLxfff
ff
xx
xx
f
xffxffL
Nxx
,)4(;e n d w h i l e
,t h e nif)3;;;;)2;1);(;)1
||w h i l e)3(
);(),(,0)2(;,,,:)1(
2
2110210
221
01
01
12
1
1100
10
?
????
???
?
?
??
?
???
?
?
非线性方程与方程组的数值解法
本章重点介绍求解非线性方程 的几种常见和有
效的数值方法,同时也对非线性方程组
求解,简单介绍一些最基本的解法,无论在理论上,还是在
实际应用中,这些数值解法都是对经典的解析方法的突
破性开拓和补充,许多问题的求解,在解析方法无能为力
时,数值方法则可以借助于计算机出色完成,
0)( ?xf
),,2,1(0),,,( 21 nixxxf ni ?? ??
2.1二分法
求非线性方程 0)( ?xf
确定方程的有根区间
计算根的近似值
的根的方法
分为两步,
? 首先确定有限区间：依据零点定理。
设,且,
则方程 在区间 上至少有一个根。
如果 在 上恒正或恒负，则此根唯
一。
],[)( baCxf ? 0)()( ?bfaf
0)( ?xf ),( ba
)(' xf ),( ba
等步长扫描法求有根区间
? 用计算机求有根区间：等步长扫描法。
设 h>0是给定的步长，取,
若 则扫描成功；否则令
,继续上述方法，直到成
功。如果 则扫描失败。再将 h 缩小,
继续以上步骤。
haxax ??? 10,
0)()( 10 ?? xfxf
hxxxx ??? 0110,
bx ?1
等步长扫描算法
? 算法：（求方程 的有根区间）
(1) 输入 ；
(2) ；
(3),若 输出失败信息，
停机。
(4)若 。输出,已算出方程的一个根，停
机。
0)( ?xf
hba,,
)(0 aff ?
)(,1 xffhax ??? bx?
01 ?f x
等步长扫描算法
(5) 若 。输出 为有根区间，
停机
(6),转 3）
? 注：如果对足够小的步长 h扫描失败。
说明,
? 在 内无根
? 在 内有偶重根
010 ?ff ],[,,xaxa
xa ?
],[ ba
],[ ba
二分法
? 用二分法 (将区间对平分 )求解。
令
若,则 为有根区间，否
则 为有根区间
记新的有根区间为, 则
且
)(,,1121111 bacbbaa ????
0)()( 11 ?cfaf ],[
11 ca
],[ 11 bc
],[ 22 ba
],[],[ 2211 baba ?
)( 112122 abab ???
二分法
? 对 重复上述做法得
? 且
],[ 22 ba
......],[......],[],[ 2211 ???? nn bababa
)(2 1 1 abab nnn ??? ?
二分法
设 所求的根为,
则
即
取 为 的近似解
?x
.,.,,.2,1],[ ??? nbax nn
......2,1??? ? nbxa nn
0)(2 1l i m)(l i m 1n ???? ????? abab nnnn?
???? ???? xba nnnn limlim
)(21 nnn bacx ????
?x
求方程 f(x)=0的根的二分法算法
).(
2
1
)4(;e n d w h i l e
].,[],[
];,[],[0)()()2
);(),(
2
1
)1
||)3(;3,
,10)()()2(;,],[:)1(
bax
bxbae l s e
xabat h e nxfafif
xfbax
baw h i l e
e l s eba
t h e nbfafif
baba
??
?
??
??
??
?
输出
计算令
时做
步转第值输入
重新步返回第
值及精度控制量的有根区间输入
?
?
求方程 f(x)=0的全部实根的二分法算法
);();(
2
1
1
||wh i l e)2
e n d wh i l e ;;;0)()(wh i l e)1
wh i l e)3(;;)2(;,,,:)1(
11
0
11
11111
1
111
xfbax
ab
habaabfaf
bb
habaa
hba
计算
时做
做
时做
输入
??
??
????
?
???
?
?
求方程 f(x)=0的全部实根的二分法算法;e n d w h i l e;;
10;:)3;e n d w h i l e
].,[],[
],[],[0)()(if3
);3(0)(if2
111
111
1111
0
0
hab
h
xax
bxbae l s e
xabat h e nxfaf
xf
????
?
??
?
输出
转
例题
? 例 1 设方程
解：取 h=0.1,扫描得,
又
即 在 有唯一根。
]2,1[],[,1)( 3 ???? baxxxf
0344.0)4.1(
061.0)3.1(
??
???
f
f
].4.1,3.1[方程的有根区间为?
]4.1,3.1[,013)( 2' ???? xxxf?
0)( ?xf ]4.1,3.1[
2.2一般迭代法
? 2.2.1 迭代法及收敛性
对于 有时可以写成 形式
如,
0)( ?xf )( xx ??
3
33
1
101
xx
xxxx
??
??????
xxxx c o s0c o s ????
迭代法及收敛性
考察方程 。这种方程是隐式方
程，因而不能直接求出它的根，但如果
给出根的某个猜测值, 代入 中
的右端得到,再以 为一个猜
测值，代入 的右端得
反复迭代得
)( xx ??
0x
)( xx ??
)( 01 xx ?? 1x
)( xx ?? )(
12 xx ??
,......1,0)( k1k ??? kxx ?
迭代法及收敛性
若 收敛，即
则得 是 的一个根
}{ kx ?
?? ? xxk klim
?x )( xx ??
)()l i m()(l i ml i m 1n ????? ???????? xxxxx nnnnn ????
迭代法的几何意义
? 交点的横坐标
*x
??
?
?
???
)()( xy
xyxx
??
y=x
2x 0x1x
简单迭代法
将 变为另一种等价形式 。
选取 的某一近似值,则按递推
关系 产生的迭代序列
。这种方法算为简单迭代法。
0)( ?xf )( xx ??
?x ],[
0 bax ?
,......1,0)( k1k ??? kxx ?
}{ kx
例题
例 2.2.1 试用迭代法求方程
在区间 (1,2)内的实根。
解：由 建立迭代关系
k=10,1,2,3……,
计算结果如下,
3 1?? xx
01)( 3 ???? xxxf
31 1??? kk xx
例题
? 精确到小数点后五位
5102132472.1 ?? ??? ?x
例题
? 但如果由 建立迭代公式
仍取,则有,
显然结果越来越大,是发散序列
1x 3 ??x
,...2,1131 ???? kxx kk
5.10 ?x 2,3 7 51 ?x 1 2,3 92 ?x
}{ kx
迭代法的收敛性
? 定理 2.2.1（压缩映像原理）
设迭代函数 在闭区间 上满足
（ 1）
（ 2） 满足 Lipschitz条件
即 有
且 。
)(x? ],[ ba
],[)(],[ baxbax ??? ?
)(x?
],[,21 baxx ?? )()( 2121 xxLxx ??? ??
10 ?? L
压缩映像原理
则 在 上存在 唯一解,
且对,由 产生
的序列 收敛于 。
)( xx ??
],[0 bax ?? )( k1k xx ???
}.{ 1?kx ?x
],[ ba ?x
压缩映像原理
? 证明：不失一般性,不妨设
否则 为方程的根。
? 首先证明根的存在性
令
bbaa ?? )(,)( ??
ba或
xxx ?? )()( ??
压缩映像原理
则, 即
由条件 2） 是 上的连续函数
是 上的连续函数。
故由零点定理 在 上至少有一根
0)()( ??? aaa ?? 0)( ?b? 0)()( ?? ba ??
)(x? ],[ ba
)( x?所以
],[ ba0)( ?x?
],[ ba
),( bax ??
压缩映像原理
? 再证根的唯一性
设有 均为方程的根
则
因为 0<L<1,所以只可能,
即根是唯一的。
],[,21 baxx ???
|||)()(||| 212121 ?????? ????? xxLxxxx ??
?? ? 21 xx
压缩映像原理
? 最后证迭代序列的收敛性
与 n 无关，而 0<L<1
即
|)()(||| 1 ??? ??? xxxx nn ??由于
|| 1 ?? ?? xxL n
|| 0 ??? xxL n
......?
?xx,
0因为
0l i m||||l i m 0 ???? ?????? nnnn Lxxxx所以
?
?? ? xx nnlim
压缩映像原理
? 误差估计
? 若 满足定理 2.2.1条件，则
?
这是事后估计，也就是停机标准。 L越小，收敛速度越快。
?
这是事前估计。选取 n，预先估计迭代次数。
)( xx ??
||L1 L|| 1nn ?? ???? xxxx n
||L1 L|| 01
n
xxxx n ???? ?
例题
? 例 2.2.2 证明函数 在区间 [1，
2]上满足迭代收敛条件。
? 证明,
3 1)x( ?? x?
上严格单调增函数。是区间所以
因为
],[)(
]2,1[0)1(
3
1
)x( 3
2
'
bax
xx
?
? ????
?
例题
]2,1[143 1|)1(31||)(| 33
2
' ?????? ? xLxx?又
23)2(12)1( 33 ???? ??,而
）。满足条件（，所以即 1)(]2,1[)]2(),1([ x??? ?
）。满足条件（所以 2)( x?
满足压缩映像原理。在故 ]2,1[1)x( 3 ?? x?
例题
? 若取迭代函数,
不满足压缩映像原理，故不能肯定
收敛到方程的根。
1)x( 3 ?? x?
]2,1[3|3||)(| 2' ??? xxx?因为
,...,1,0)(1 ??? nxx nn ?
简单迭代收敛情况的几何解释
2.2.2 Steffensen加速收敛法
? 迭代法收敛的阶
定义 2.2.1 设序列 收敛到,若有实
数 和非零常数 C,使得
其中，,则称该序列是 p 阶收敛的，
C 称为渐进误差常数。
?0n}x{ *x
1?p
Cee p
n
n
n
??
??
1lim
*xxe nn ??
迭代法收敛的阶
当 p=1时，称为线性收敛；
当 p>1时，称为超线性收敛；
当 p=2时，称为平方收敛或二次收敛。
迭代法收敛的阶
? 定理 2.2.2 设 是方程 的不动
点,若为足够小的正数 。
如果 且,则从任意
出发，由 产生的序列 收
敛到,当 时敛速是线性的。
*x )(xx ??
? ],[ ** ?? ???? xx
??? Cx)(? 1|)(| * ?? x? ??0x
)(1 kk xx ??? ?0}{ nx
*x 0)( ?? x?
迭代法收敛的阶
? 证明,
? 满足压缩映像原理
知，及由 ???? Cxx )(1|)(| '* ??
足够小时，有? )(1|)(| ????? xLx?
?????? ?????????
??
|||||)(||)()(||)(| **** xxxxxxxx
x 有因此，对于
迭代法收敛的阶
? 敛速是线性的
线性收敛到 。
0)()()(l i ml i m **
*
1
n
??????
??
?
??
xxx xxee
n
n
nn
n ???因为
。收敛到故 *0}{ xx n ?
满足压缩映像原理，所以即 )(,)( xx ?? ??
?0}{ nx所以 *x
Steffensen迭代格式
? 由线性收敛知
当 n充分大时有
即
0limlim 1
1
2
n ???
?
???
?
?? Ce
e
e
e
n
n
nn
n
n
n
n
n
e
e
e
e 1
1
2 ?
?
? ?
*
*
1
*
1
*
2
xx
xx
xx
xx
n
n
n
n
?
??
?
? ?
?
?
Steffensen迭代格式
? 展开有,
nnn
nn
n xxx
xxxx
??
???
??
?
12
2
1*
2
)(
2**12 1**2 )(2))(( xxxxxxxx nnnn ????? ???
2**12 12**2*2 )(2)( xxxxxxxxxxx nnnnnn ?????? ????
*12 1*2*2 2 xxxxxxxxx nnnnnn ???? ????
2 1212* )2( ???? ????? nnnnnn xxxxxxx
Steffensen迭代格式
? 已知,则,
? 改成
nx
)(1 nn xx ??? ))((2 nn xx ????
nnn
nn
nn
nn
nn
xyz
xy
xx
yz
xy
??
?
??
?
?
?
2
)(
)(
)(
2
1
?
?
n=0,1,2,…
Steffensen迭代格式
? 也可以改写成
? 其中迭代函数
,......)1,0()(1 ??? nxx nn ?
xxx
xxxx
??
???
)(2))((
])([)( 2
???
??
Steffensen迭代法收敛的充要条件
? 定理 2.2.3
],,[)( **1 ??? ????? ? xxCx,设函数
。件是的不动点的充分必要条是 )()( *** xxxxx ?? ??
，则为足够小的正数，且 1)( * ?? x??
Steffensen迭代法收敛的充要条件
? 证明：必要性
的不动点，是因为 )(* xxx ??
])(2))(()][([])([ 2 xxxxxxx ????? ?????由于
，所以 0))((lim * ??? xxxx ?
，故有 0))((lim * ??? xxxx ? )( ** xx ??即
的不动点。是所以 )(* xxx ??
Steffensen迭代法收敛的充要条件
? 充分性
的不动点有是由 )(* xxx ??
xxx
xxxx
xxxx ??
???
?? )(2))((
])([l i m)]([l i m 2
** ???
??
1)(2)())((
]1)(][)([2l i m
* ?????
????
? xxx
xxx
xx
o
o
????
??型
0]1)([ ]1)(][)([2lim 2*
***
*
??? ????
? x
xxx
xx ?
??
的不动点。是所以 )(* xxx ??
Steffensen算法的收敛速度
!
)(
)(
l i m
}{
)(0)(
0)(...)()(
,],,[
),1()(,)(4.2.2
*)(
*
*
1
*
0
10
*)1(
*)1(**
**
*
p
x
xx
xx
xpx
xxxx
xxx
xx
pCxxxx
p
p
n
n
n
n
kk
p
p
p
?
??
???
???
??
?
?
?
?????
???????
????
???
?
??
?
?
?
?
?
，且阶收敛速度收敛到，以列
产生的序，由，则而
如果为足够小的正数
的不动点是设定理
Steffensen算法的收敛速度
? 定理 2.2.5 在定理 2.2.3假设下，若
产生的序列 至少平方收敛到 。
,.,,,2,1,0
2
)(
)(
)(
2
1
?
?
?
?
?
?
?
?
??
?
??
?
?
?
n
xyz
xy
xx
yz
xy
S t e f f e n s e n
nnn
nn
nn
nn
nn
?
?
迭代格式则由
2C)( ??x?
?0}{ nx *x
*x
Steffensen算法的收敛速度
的不动点，是证明,)(* xxx ?? 。即 )( ** xx ??
1)(
1
1)(
l i m
)(
l i m *
* **
???
??
?
?
?
??
x
x
xx
xx
xx
o
o
xx
?
??
型
又因为
Steffensen算法的收敛速度
*
)(2))((l i m
* xx
xxx
xx ?
??
?
???及
)1)(2)())(((l i m
*
??????
?
xxx
xx
o
o
????
型
1)(2)()( *** ?????? xxx ???
2* ]1)([ ??? x?
Steffensen算法的收敛速度
*
*
* )()(l i m)(
* xx
xxx
xx ?
???
?
???于是有
*
*
2
)(2))((
])([
l i m
* xx
x
xxx
xx
x
xx ?
?
??
?
?
?
?
???
?
*
2
*
)(2))((
]
)(
[
lim1
*
xx
xxx
xx
xx
xx
?
??
?
?
??
? ???
?
0]1)([ ]1([1 2*
2*
??? ???? xx??
Steffensen算法的收敛速度
由定理 2.2.4知 至少以平方速度
收敛到 。
也就是说：简单迭代法是线性收敛；
Steffensen迭代至少平方以上收敛（加速
收敛）。
?0}{ nx
*x
例题
? 例 2.2.3试用 Steffensen算法求解方程
? 解法一、取,由
013 ??? xx
3 1)( ?? xx?
nnn
nn
nn
nn
nn
xyz
xy
xx
yz
xy
??
?
??
?
?
?
2
)(
)(
)(
2
1
?
?
n = 0,1,2,…
例题
? 取初值,计算结果如下,5.1
0 ?x
N Xn Yn Zn
0 1.5 1.357208808 1.330860959
1 1.324899181 1.324752379 1.324724496
2 1.324717957 1.324717957 1.324717957
例题
? 解法二、取,由
? 对于该迭代函数在一般迭代法中是发散的，
而 Steffensen格式却是收敛的。
1)( 3 ?? xx?
nnn
nn
nn
nn
nn
xyz
xy
xx
yz
xy
??
?
??
?
?
?
2
)(
)(
)(
2
1
?
?
n=0,1,2,…
例题
? 取初值,计算结果如下,
N Xn Yn Zn
0 1.5 2.375 1.239648437
1 1.416292975 1.840921915 5.238872769
2 1.355650442 1.491398279 2.317270699
3 1.328948777 1.347062883 1.444351224
4 1.324804489 1.325173544 1.327117281
5 1.324717944 1.324718152 1.324718980
6 1.324717957
5.10 ?x
Steffensen迭代格式几何解释
Steffensen迭代算法
1
10
0
2
001
20
0
100
210
:)3(;
)4
);2/()()3;3|2|)2
);();()1
|)(|wh i l e)2(;,,)1(
x
e n d w h i l e
xx
xyzxyxx
t h e nxyzif
yzxy
xx
x
输出
步做第
做
输入
?
?????
???
??
??
?
??
??
??
Steffensen迭代算法
2.3 Newton迭代法
? 设 x * 是方程 f (x ) = 0的根，又 x0 为 x *
附近的一个值,将 f (x ) 在 x0附近做泰勒
展式
令,则
之间和在其中 0
2
0000 )()(2
1)()()()(
xx
fxxxfxxxfxf
?
?????????
*xx ?
)()(21)()()()(0 20*00*0* ?fxxxfxxxfxf ?????????
Newton迭代法
去掉 的二次项，有,
即
以 x1代替 x0重复以上的过程，继续下去得,
0* xx ?
0)()()( 000*0 ????? xfxxfxxf
)(
)(
0
0
01
*
xf
xfxxx
????
Newton迭代法
,.,,,,,1,0)( )(1 ????? nxf xfxx
n
n
nn
以此产生的序列 {Xn}得到 f(x)=0的近似
解，称为 Newton法，又叫切线法。
Newton迭代法几何解释
? 几何意义
例题
例 2.3.1 用 Newton法求 的
近似解。
解：由零点定理。
0c o s)( ??? xxxf
内有根。在 )2,0(0c o s ??? xx
迭代公式得及由 N e w t onxxf s i n1)( ???
,.,,,,,1,0si n1 c o s1 ?????? nx xxxx
n
nn
nn
例题
0 8 5 1 3 37 3 9.0
7 3 9 0 8 5 1 3 3.07 3 9 0 8 5 1 3 3.0
7 3 9 0 8 5 1 7 8.0;7 3 9 3 6 1 3 3.0
4
4
*
43
21
0
??
??
??
?
xx
xx
xx
x
故取
得取
?
例题
? 例 2.3.2 用 Newton法计算 。
解,
2
20)( 2 ???? aaxxf 其中
迭代公式得及由 N e w t onxxf 2)( ??
,.,,,,,1,0)2(212 2
2
1 ???
???
? nxxx
xxx
n
n
n
n
nn
。有十位有效数的近似值
是已的精确值相比，。与
，，则取
33
210
24 1 4 2 1 3 5 6 2.1
4 1 4 2 1 5 6 8 6.11, 4 1 6 6 6 6 6 75.1
xx
xxx
?
???
Newton迭代法算法框图
Newton迭代法算法
。输出
）转（
做
输入
1
10
1001
0
0100
0
:)4(;2)3;)2;/)1
||wh i l e( 3 )
);();()2(;,)1(
x
e n d w h i l e
xx
ffxx
f
xffxff
x
?
??
?
???
?
?
Newton迭代法收敛性
定理 2.3.1 设函数,且满足
若初值 满足 时，由 Newton
法产生的序列收敛到 在 [a,b]上的唯一根。
],[)( 2 baCxf ?
上恒正或恒负。在 ],[)()3
]);,[(,0)()2;0)()()1
baxf
baxxf
bfaf
??
???
?
],[0 bax ? 0)()( 00 ??? xfxf
0)( ?xf
Newton迭代法收敛性
证明,根的存在性
? 根的唯一性
内至少有一个根。
在知）及由条件（
),(
0)(],,[)(1
ba
xfbaCxf ??
。记此根为内有唯一根在
上严格单调函数，因此是故
保号，知及由
*,),(
0)(],[)(
)(],bC [ a,)(,0)(
xba
xfbaxf
xfxfxf
?
?????
Newton迭代法收敛性
? 收敛性
))(()(0
)(
)(
0)(,0)(
,0)(],,[0)()(
0)(,0)(,0)(,0)(
0100
0
0
0
01
00
0
*
000
xxxfxf
x
xf
xf
xx
xfxf
xfbxxxfxf
xfxfbfaf
????
?
?
??
?????
?????
???????
即有
，所以
知，由
，不妨设
Newton迭代法收敛性
继续上述推理有代替。再以因此有
两式相减
展式由另一方面
0101
*
2
0
*
0
1
*
2
0
*
0
*
00
*
0)(
)(
)(
2
1
))((
2
1
))(()()(0
T a y l o r,
xxxxx
xx
xf
f
xx
xxfxxxfxfxf
??
??
?
??
???
?????????
?
?
Newton迭代法收敛性
。，由根的唯一性知可得时当
由
。故必有极限，记
。是单调减有下界的序列故序列
*
1
0
011
*
0)(,
,.,,2,1
)(
)(
l i m
}{
.,,.,,
xaafn
n
xf
xf
xx
ax
x
xxxxx
n
n
nn
n
n
n
nn
????
?
?
??
?
??????
?
??
?
?
Newton迭代法收敛性
? 推论 在定理 2.3.1条件下,Newton迭代
法具有平方收敛速度。
故结论成立。
之间，则与介于其中，
证明，一般有类似定理证明
0
)(
)(
2
1
l i m
)(
)(
)(
2
1
1.3.2
*'
*''
2
1
*
2*
1n
*
??
?
?
??
???
?
??
?
xf
xf
e
e
xx
xx
xf
f
xx
n
n
n
nn
n
n
n
?
?
代数方程的 Newton迭代法
? 代数方程的 Newton迭代法推导
设 n次代数方程
用 Newton迭代法求有限区间的实根，则要计算
,一般采用秦九韶算法。
,.,,2,1)( )(1 ????? nxf xfxx
n
n
nn
)0(0)( 0110 ????????? ? aaxaxaxf nnn
)(),( nn xfxf ?
代数方程的 Newton迭代法
? 由 Taylor展式
)2(
!
)(
)(.,,
!2
)(
)()()(
)1()()()(
!
)(
)(
.,,
!2
)(
)()()()()(
)(
1'
)(
2'
n
xf
xx
xf
xxxfxQ
xQxxxf
n
xf
xx
xf
xxxfxxxfxf
n
n
n
n
n
nn
nn
n
n
n
n
n
nnnn
?
???
??
???
?????
?
??
?????
其中
代数方程的 Newton迭代法
)3()(
)(
)()(),()()2(
1
2
1
1
0
''
?
?? ???????
??
n
nn
nnnn
bxbxbxQ
xQ
xxxfxfxQ
的余式，令除以
为且式知，由
);()(1
)()1(
n
n
xfxQn
xfxx
，余式为次多项式为
，得商）去除式表示，用（
?
?
nn
nn
n
nn
nn
axaxaxa
bxbxbxxxfxf
?????
?????????
?
?
?
??
1
1
10
1
2
1
1
0
...
])[()()(
1)3( ）式得式代入（
),.,,,2,1(
)(
1
00
nkx
xfb
bab
ab
x
n
nn
kkk
?
?
?
?
??
?
?
?
??
?
?
的同次幂系数得比较等式两边
代数方程的 Newton迭代法
同理
)()()()(
)(
' xRxxxfxQ
xQxx
nn
n
???
? 有取除以用
)4()( 23120 ??? ??????? nnn cxcxcxR令
12
2
1
1
0
2
3
1
2
0
.,,
])[()()(
)3()4(
??
??
?
??
?????
??????????
nn
nn
n
nn
nn
bxbxbxb
cxcxcxxxfxQ
式得式代入
代数方程的 Newton迭代法
比较 x的同次幂系数得,
故代数方程的 Newton迭代公式
)1,.,,,2,1(
)(1
1
00
??
?
?
?
?
?
??
??
?
?
? nkx
xfc
cbc
bc
n
nn
kkk
,.,, )2,1(
1
1 ???
?
? nc
bxx
n
n
nn
代数方程的 Newton迭代法算法
步。返回第
停止计算输出
做对
计算
输入
2)(,;,||( 4 );)(3;;
1,.,,,2,1)2;;)1
);(),()2(;,),,.,,,2,1,0(:)1(
10
1
*
01
1
0
01
0101000
0100
00
0
xxe l s e
xxt h e nxxif
f
f
xx
xfffxfaf
nk
ffaf
xfxf
xnia
k
i
?
???
??
????
??
??
?
?
?
?
2.4弦截法
? Newton迭代法有一个较强的要求是
且存在。因此，用弦的斜率
近似的替代 。
0)( ?? xf
)(xf ?
)(
)()(
)(
))(,(P))(,(P
,,],[)(
1
01
01
1
111000
10
*
xx
xx
xfxf
xfy
xfxxfx
bxaxxbaxf
?
?
?
??
??
得弦的方程及则过
，取上有唯一零点在设
弦截法
? 令 y=0,解得弦与 x轴的交点是坐标 x2
.
,.,, )2,1()(
)()(
.,,,,,,
)(
)()(
0)(
)()(
)(
0
0
1
320
1
01
01
12
12
01
01
1
称之为定端点弦截法
计算再由
解得
?
?
?
??
?
?
??
??
?
?
?
?
nxf
xfxf
xx
xx
xxx
xf
xfxf
xx
xx
xx
xx
xfxf
xf
n
n
n
nn
弦截法
.,
,.,, )2,1()(
)()(
,,
1
1
1
321
又称快速弦截法称之为变端点弦截法
以此类推计算若由
?
?
?
??
?
?
?
nxf
xfxf
xx
xx
xxx
n
nn
nn
nn
弦截法的几何解释
例题
例 2.4.1 用快速弦截法求方程
在区间（ 1,2）内的实根。
解：取 x0=1,x1=2,代入公式 2.4.2计算结果,如
表 2.4.1所示。
01)( 3 ???? xxxf
k xk f(xk)
0 1 -1
1 2 5
2 1.166666667 -0.57870369
3 1.253112023 -0.28536302
4 1.337206444 0.053880579
5 1.323850096 -0.0036981168
6 1.324707936 -4.273521*10E-5
7 1.324717965 3.79*10E-8
弦截法收敛定理
则
其中
如果的根是为足够小的正数
设定理
0|)(|m a x|,)(|m a x
1
2
,0)(,
],,[],[,],[)(1.4.2
12
1
2
*
**2
??????
??
?
????
????
xfmxfM
m
M
q
xfx
xxbabaCxf
bxabxa
?
?
??
弦截法收敛定理
。的敛速收敛到以确定的序列
由
线性收敛到确定的序列
由
*
0
1
1
*
0
0
1
2
15
}{
,.,,2,1)(
)()(
)2(;}{
,.,,2,1)(
)()(
)1(
xpx
nxf
xfxf
xx
xx
xx
nxf
xfxf
xx
xx
n
n
n
nn
nn
n
n
n
n
nn
?
?
?
?
?
??
?
?
?
??
?
?
?
求解方程 f(x)=0的快速弦截法
。输出
停止计算输出失败信息
时做
输入
Lx
NL
ffffxxxx
LLxfff
ff
xx
xx
f
xffxffL
Nxx
,)4(;e n d w h i l e
,t h e nif)3;;;;)2;1);(;)1
||w h i l e)3(
);(),(,0)2(;,,,:)1(
2
2110210
221
01
01
12
1
1100
10
?
????
???
?
?
??
?
???
?
?
