|b-a|< ε
0 y
输 出x 结束
n
x a
n
例2 证明方程 x3 2x 5 0 在区间[2, 3]内有一个根,
使用二分法求误差不超过0.5×10-3 的根要二分多少 次？ 证明 令 f ( x) x3 2x 5则 f (2) 1 0, f (3) 16 0 且f(x)在[2, 3]上连续,故方程f(x) =0在[2,3]内至少有一
第六章 非线性方程的数值解法
6.1 引言
在科学研究和工程设计中, 经常会遇到的一大类 问题是非线性方程
f(x)=0
(6.1)
的求根问题，其中f(x)为非线性函数。
方程f(x)=0的根, 亦称为函数f(x)的零点.
如果f(x)是多项式函数，则称为代数方程，否则 称为超越方程（三角方程，指数、对数方程等）。一 般称n次多项式构成的方程
an xn an1xn1 L a1x a0 0 (an 0)
为n次代数方程,当n＞1时,方程显然是非线性的 一般稍微复杂的3次以上的代数方程或超越方程,
很难甚至无法求得精确解。本章将介绍常用的求解 非线性方程的近似根的几种数值解法
通常方程根的数值解法大致分为三个步骤进行
① 判定根的存在性。即方程有没有根？如果有 根，有几个根？
满足不等式
|
xn
x*
|
ba 2n1
证 因为an x* bn , 所以
|xn
x
*|=|1 2
(an
bn )-x*|
=
1 2
|
(an
-x*
)
(bn
-x
*
)|
1 2
(|
(an
-x*
)
|
|
(bn
-x*)|)
故有
=
1 2
[(
x*
an
)
(bn
-x*)]
|
xn
x*
|
bn
an 2
ba 2n1
.
当给定精度ε＞0后,要想 x* xn 成立,只要
,将区间
a1,
b1
再分为两半,然
后再确定有根区间 a2,b2 ,其长度是a1, b1 的
二分之一。
③ 如此反复下去,若不出现 f (xk ) 0，即可得出一 系列有根区间序列：
a, b a1, b1 a2 , b2 L an , bn L
上述每个区间都是前一个区间的一半,因此 an,bn 的长度
x
用逐步搜索法进行实根隔离的关键是选取步长h 要选择适当h ，使之既能把根隔离开来，工作量 又不太大。 为获取指定精度要求的初值,可在以上隔离根的 基础上采用对分法继续缩小该含根子区间
二分法可以看作是搜索法的一种改进。
开始 输 入 a , b,ε
二
分
y
法
算
xb
法
实
现
(a+b)/2 x
f(a) f(x )<0 ?
二分法的基本思想: 据定理6.1，首先确定有根区间, 将区间二等分, 通过判断f(x)的符号, 逐步将有根区间 缩小, 直至有根区间足够地小, 便可求出满足精度要 求的近似根。
6.2.1 二分法求根过程
设方程f(x)=0在区间[a,b]内有根,二分法就是逐步
收缩有根区间，最后得出所求的根。具体过程如下
② 确定根的分布范围。即将每一个根用区间隔 离开来，这个过程实际上是获得方程各根的 初始近似值。
③ 根的精确化。将根的初始近似值按某种方法
逐步精确化，直到记满笔足记预先要求的精度为止
求方程
o
b
x
基本定理
Th6如.1果函数 在f ( x)上连[a续, b，] 且
1
1
bn an 2 (bn1 an1 ) L 2n (b a )
当n→∞时趋于零,这些区间最终收敛于一点x* 即为
所求的根 。
在此过程中，可得：
每次二分后,取有根区间 an,bn
的中点
xn
1 2 (an bn )
作为根的近似值，得到一个近似根的序列
x0 , x1 , x2 ,L , xn ,L 该序列以根x*为极限
取k满足
1 2n1
(b
a
)
即可，亦即当:
n lg(b a) lg 1
lg 2
时,做到第n+1次二分,计算得到的 xn就是满足精
度要求的近似根 。
在程序中通常用相邻的
x
n与x
n
的差的绝对值
1
或 bn 与 an 的差的绝对值是否小于ε来决定二分区
间的次数。
逐步搜索法
对于给定的f (x),设有根区间为[A,B],从x0=A出发,以 步长h=(B-A)/n(n是正整数),在[A,B]内取定节点:xi=x0 ＋ih (i=0,1,2,…,n),从左至右检查f (xi)的符号,如发现xi 与端点x0的函数值异号,则得到一个缩小的有根子区 间［xi-1,xi］。
y
y=f(x)
a
x1
x* x0
b
a1 a2
b1 b2
y
y=f(x)
x*
a
x0
x1
b
a1
b1
a2
b2
y f (x)
a
x0
o
b
x
若前两种情况出现之一，则就意味着找到了一个比
原区间长度小一半的隔根区间了。设为 a1,b1 .
② 对压缩了的有根区间 a1,b1 施行同样的手法,
即取中点
x
1
a1
2
b1
① 取有根区间[a,b]之中点, 将它分为两半,分点
x0
a
2
b
，这样就可缩小有根区间。
注意可能会出现三种情况
若f ( x0 ) f (a) 0,则f ( x)在区间[a, x0 ]内有零点；
若f ( x0 ) f (b) 0,则f ( x)在区间[ x0 , b]内有零点；
若f ( x0 ) 0,则x0为区间[a, b]内的零点；
则至少有一个数 使得 f (，) 若0同时
在 内f (存x)在且[a保, b持] 定号，即
(或
在 f 内( x唯) 一0。
[a,b]
f (a) f (b) 0 的一f 阶( x导) 数
)则f (这x)样的0
6.2 二分法
二分法又称二分区间法，是求解方程(6.1)的近似 根的一种常用的简单方法。
只要二分足够多次(即k足够大),便有 x* xn 这里ε为给定精度,由于x* a n ,bn ,则
x* xn
bn an 2
ba 2n1
Q
bn
an 2
bn1 an1
ba 2n1
定理6.2 设x*为方程f ( x) 0在区间[a, b]内的唯一根，f ( x)
满足f (a) f (b) 0,则二分法计算过程中第n个区间的中点xn
y
0 A a1 b1a2 b2
Bx
例1 方程f(x)=x3-x-1=0 确定其有根区间 解：用试凑的方法，不难发现
f(0)<0 f(2)>0 在区间（0，2）内至少有一个实根 设从x=0出发,取h=0.5为步长向右进行根的 搜索,列表如下
0 0.5 1.0 1.5 2
f(x) – – – + +
可以看出，在[1.0,1.5]内必有一根