数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
第 4章 非线性方程求根
非线性科学是当今科学发展的一个重要研究方向，而非线性方程的求根也成了一
个不可缺的内容。但是，非线性方程的求根非常复杂。
通常非线性方程的根的情况非常复杂：
?
?
?
?
?
?
?
2
1
)
2
s in (
y
yx
?
无穷组解
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
??
??
1
0
4
1
1
2
2
a
a
a
a
ayx
axy
无解
一个解
两个解
四个解
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
所以，只在某个区域内可能解存在唯一，而且经常很简单的形式得不到精确解：
因此，通常我们用迭代法解非线性方程
看迭代法之前，先看看一种简单直观的方法
原理,0)(.,.,0)()( ????? xftsxbfaf
0)c o s ( ?? xe x ?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
4.1对分法
a
b
x1
x2
a
b
什么时候停止？
11 εxx kk ??? 2)( εxf ?或
x*
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
While(|a-b|>eps)
x=(a+b)/2
f(x)
若 (|f(x)|<eps) x为解
若 f(x)*f(b)<0 修正区间为 [x,b]
若 f(a)*f(x)<0 修正区间为 [a,x]
End while
每次缩小一倍的区间，收敛速度为 1/2，较慢，且只能求一个根，使用条件限制较大
算法
?2
xx*
不能保证 x 的精度
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
4.2 迭代法
f (x) = 0 x = g (x)
等价变换
f (x) 的根 g (x) 的不动点
思
路
从一个初值 x0 出发，计算 x1 = g(x0),x2 = g(x1),…,
xk+1 = g(xk),… 若 收敛，即存在 x* 使得
，且 g 连续，则由 可
知 x* = g(x* )，即 x* 是 g 的不动点，也就是 f 的根。
? ???0kkx
*lim xx kk ??? ? ?
kkkk xgx ????? ? l i ml i m 1
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
迭代法的基本步骤如下：
1、给出方程的局部等价形式 )(0)( xxxf ????
2、取合适的初值，产生迭代序列 )(,10 ii xxx ???
3、求极限
nn xx ???? lim*
易知，该值为方程的根
一定收敛吗？
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
x
y y = x
x*
y=g(x)
x0
p0
x1
p1
?
x
y y = x
x*
y=g(x)
x0
p0
x1
p1
?
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
],[),( baxx ?? 若满足：
1,],[,)( baxbxa ??? ?
2,)(x? 可导，且存在正数 L<1，使得对任意的 x，有 Lx ?)('?
则有：
1、存在唯一的点 *)(**,xxx ??
2,? ?bax,0 ?? 迭代收敛，且有误差估计
011* xxL
Lxx k
k ????
定理
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
① 存在唯一性
②
做辅助函数 )()( xxx ?? ??,则有 0)(,0)( ?? ba ??
所以，存在点 *)(*0*)(.,.*,xxxtsx ?? ???
若 *)*(** xx ??,则有：
****)**)(('*)*(*)(*** xxLxxxxxx ??????? ????
又,1?L *** xx ??
],[0 bax ?? 则
*))(('*)()(*1 xxxxxx kkk ?????? ????
*** 011 xxLxxLxx kkk ?????? ?? ?
所以，任意的初值都收敛
证明：
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
③ 误差估计
01111 )()( xxLxxLxxxx kkkkkkk ???????? ??? ???
kkpkpkkpk xxxxxx ??????? ????? 11 ?
? ? 011 xxLL kpk ???? ?? ?
? ?
0101 11
1 xx
L
Lxx
L
LL kpk ?
????
??
由 p的任意性，令
011* xxL
Lxx k
k ????
???p
证毕
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
构造满足定理条件的等价形式一般难于做到。要构造收敛迭代格式有两个要素：
1、等价形式
2、初值选取
下面我们开始介绍若干种迭代法的构造方法
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
4.3 Newton迭代法
将 f(x)在初值处作 Taylor展开
??????? 200000 )(!2 )(''))((')()( xxxfxxxfxfxf
取线性部分作为 f(x)的近似，有：
0))((')( 000 ??? xxxfxf
若 0)(' 0 ?xf,则有
)('
)(
0
0
0 xf
xfxx ?? 记为 1x
类似，我们可以得到
)('
)(
1
1
12 xf
xfxx ??
x
y
x*
x0
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
这样一直下去，我们可以得到迭代序列
)('
)(
1
k
k
kk xf
xfxx ??
?
Newton迭代的等价方程为：
)('
)()(0)(
xf
xfxxxxf ????? ?
所以
? ? 2)('
)('')()'
)('
)(()('
xf
xfxf
xf
xfxx ????
若 f(x)在 a处为单根，则 0)(',0)(',0)( ???? aafaf ?
所以，迭代格式收敛
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
收敛速度
)(''2 )()(')()()(
2
1 n
n
nnn
axaaxaxax ????? ???????
?
)(''2 )()(''2 )(
22
aaxax nnn ??? ????
函数在 a处作 Taylor展开
若 a为 p重根，取迭代格式为：
)('
)(
1
k
k
kk xf
xfpxx ??
?
即
M
e
e
n
n ??
2
1
Newton迭代收敛速度快，格式简单，应用广泛
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
例 用 Newton迭代法求方程 xex-1=0在 0.5附近的根,精度要求 ?=10-5.
解 Newton迭代格式为
?,2,1,0,111 ?????? ???
?
? kx
exx
exe
exxx
k
x
k
kx
k
x
x
k
kk
k
kk
k
k xk ?(xk) |xk-xk-1|
0
1
2
3
4
0.5
0.57102044
0.56715557
0.56714329
0.56714329
-0.17563936
0.01074751
0.00003393
0.0000000003
0.0000000003
0.07102044
0.00386487
0.00001228
0.00000000
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
注,Newton’s Method 收敛性依赖于 x0 的选取。
x*
x0?x0? x0
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
4.4 弦截法
将 Newton迭代中的导数，用差商代替，有格式
)()()( 1
1
1
?
?
? ?
???
kk
kk
kkk xfxf
xxxfxx
是 2步格式。收敛速度比 Newton迭代慢
M
e
e
n
n ??
618.1
1
x0x1
切线割线
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
定义 设迭代 xk+1 = g(xk) 收敛到 g(x) 的不动点 x*。
设 ek = xk ? x*,若,则称该迭代为 p 阶收敛,
其中 C 称为 渐进误差常数 。
0|| ||lim 1 ????? Cee p
k
k
k
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
4.4 非线性方程组的 Newton迭代法
)())(()(' )( 11 kkk
k
k
kk XFXJXxF
xFXX ?
? ????
TnTn xxxXfffFXF ),,,(,),,,(,0)( 2121 ?? ???
则，直接推广 Newton迭代为：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
n
nn
n
x
f
x
f
x
f
x
f
XJ
?
???
?
1
1
1
1
)(
数 学 系
University of Science and Technology of China
DEPARTMENT OF MATHEMATICS
实际中，用解方程组的形式
)())(( 1 kkkk XFXXXJ ???