xk g(xk1)
计 (2) 如果将原方程化为等价方程 x 2x3 1
算则迭代格式为：xk 1 2xk3 1
方
取初值
法
x0 0
x1 2x03 1 1 同样的方程
x2 2x13 1 3 ⇒ 不同的迭代格式 x3 2x23 1 55 有不同的结果
则迭代函数为：g(x)= 3 x+1
g(x)=
1 3（x+1）23
容易得到：g′(x)在包含x*的某邻域U(x*) 内
连续，且|g′(x*)|<1
因此迭代格式xk+1= 3 xk +1在x*附件收敛
计
算 例题
方 用一般迭代法求方程x-lnx＝2在区间（2，） 法 内的根，要求|xk-xk-1|/|xk|<=10-8
法 的大致位置。也可将f(x)=0等价变形为g1(x)=g2(x) 的形式，y=g1(x)与y=g2(x)两曲线交点的横坐标所
在的子区间即为含根区间。
例如，求方程3x-1-cosx=0的隔根区间。
将方程等价变形为3x-1=cosx ，易见y=3x-1与 y=cosx的图像只有一个交点位于[0.5，1]内。
意的x∈［a,b］(1),则g（x)是［a,b］
上的压缩映射
计 例题
算
已知方程2x-7-lgx＝0，求方程的含根区
方
间，考查用迭代法解此方程的收敛性。
法
计 算 方 法
计在这里我们考查在区间[3.5,4]的迭代法 算的收敛性
方 很容易验证：f(3.5)<0,f(4)>0 法 将方程变形成等价形式：x＝(lgx+7)/2

a
2
b
有误差
|x1

x*|

b
2
a
法 第 k 步产生的 xk 有误差
|xk

x*|
ba 2k
对于给定的精度 ,可估计二分法所需的步
数k：
ba
lnb a ln ε
2k ε k
ln 2
计 例1 用二分法求 x3 4x2 10 0
算 在(1,2)内的根，要求绝对误差不超过 1 102
（2）在行星轨道（ planetary orbits）的计算中, 对任意的a和b，我们需要求x-asinx=b的根
（3） 在数学中，需要求n次多项式xn
1+...+an-1 x + an ＝0的根
+
a1
xn-
求f(x)=0的根
计 算 方
法非线性方程的一般形式 f(x)=0 这里f(x)是单变量 x 的函数，它可以是代数多项式 f(x)=a0+a1x+……+anxn (an≠0) 也可以是超越函数，即不能表示为上述形式的函数。
法
x
因此， x0（2，），xk+1＝2＋lnxk产 生的序列 xk 收敛于X*
取初值x0＝3.0,计算结果如下：
计 k xi 算 0 3.000000000 方 1 3.098612289 法 2 3.130954362
3 3.141337866 4 3.144648781 5 3.145702209 6 3.146037143
计 (2)逐步搜索法
算
方 运用零点定理可以得到如下逐步搜索法：
法
先确定方程f(x)=0的所有实根所在的区间
为[a,b],从x0=a 出发,以步长
h=(b-a)/n
其中n是正整数，在[a,b]内取定节点：
xi=x0＋ih (i=0,1,2，……，n)
计算f(xi)的值,依据函数值异号及实根的个数确 定隔根区间,通过调整步长，总可找到所有隔根
重复上述过程
作为第一次近似值
xk1 xk

f (xk ) f (xk )
计 算
xk1 xk
计算步骤
f (xk ) f (xk )
(方1) 选定初值x0 ,计算f (x0) , f (x0)
(法2)
按公式 xk1 xk 得新的近似值xk+1
f (xk ) f (xk )
方 解：
2
法
f(1)=-5<0 f(2)=14>0 f(1.5)>0
有根区间 -(1,2)+ (1,1.5)
中点 x n
x1
x2
1.5
1.25
f(1.25)<0 (1.25,1.5)
x3 1.375
f(1.375)>0 (1.25,1.375)
x4 1.313
f(1.313)<0 (1.313,1.375) x5 1.344
区间。
§3.1 对分区间法
计
(Bisection Method )
算
方
法
a
aax121 x*
xb2 bb1
停机条件（termination condition ）：
xk1 xk ε1 或 f ( x) ε2
计
While(|a-b|>eps) x=(a+b)/2
算
计算f(x)
方
若(|f(x)|<eps) x为解 若f(x)*f(b)<0 修正区间为[x,b],即a=x
法
若f(a)*f(x)<0 修正区间为[a,x],即b=x
End while
什么时候停止？
a
xa1 x*
xb2 b
xk1 xk ε1 或 f ( x) ε2
计
算
方 法
x3 2x2 4x 7 0
在区间[3,4]内的根，精确到10-3
计 误差 分析：
算 方
第1步产生的
x1
x3 x1 2
方 法
3
x1
x0 1 2
3 1 0.7937 2
x2 3
x1 1 2
3
1.7937 2
0.9644
依此类推,得
x3 = 0.9940 x4 = 0.9990 x5 = 0.9998 x6 = 1.0000 x7 = 1.0000
已经收敛,故原方程的解为 x = 1.0000
f(1.344)<0 (1.344,1.375) x6 1.360
f(1.360)<0 (1.360,1.375) f(1.368)>0 (1.360,1.368)
x7 1.368 x8 1.364
例2，求方程f(x)= x 3 –e-x =0的一个实根。
计
因为 f(0)<0,f(1)>0。 故f(x)在(0,1)内有根
f (x)
f (x0 )
f (x0 )(x x0 )
f
(
2!
) (Nxewtxon0 )2
迭代公式
0 f (x*) f (x0) f (x0)(x * x0)
x*
x0

f (x0 ) f (x0 )
x1 x0
f ( x0 ) f ( x0 )
0 3.000000000 1 3.147918433 2 3.146193441 3 3.146193221
计 迭代法的收敛阶(收敛速度)
算
方
定义. :设序列{xk}收敛于x*，若存在p≥1和正数c， 使得成立
法
lim
k
xk 1 x* xk x* p
C
则称{xk}为 p 阶收敛的
什么形式的迭代 法能够收敛呢?
如何构造迭代函 数呢?
由此可见，这种迭代格式是发散的
计 若从任何可取的初值出发都能保证收敛，则称它 算 为大范围收敛。如若为了保证收敛性必须选取初值充 方 分接近于所要求的根，则称它为局部收敛。
法 通常局部收敛方法比大范围收敛方法收敛得快。 因此，一个合理的算法是先用一种大范围收敛方法求 得接近于根的近似值（如对分法），再以其作为新的 初值使用局部收敛法（如迭代法）。
解：令f(x)=x-lnx-2
f(2)<0,f(4)>0,故方程在（2,4）内至少有一个根
又 x （2，）,f (x)=1－ 1 0 x
因此方程 f (x)=0在（2，）内仅有一个根x*, 且x* （2，）
计 将方程化为等价方程：x＝2＋lnx
算
方 g(x)＝2＋lnx， |g (x)|=| 1 | 0.5 1, x （2，4）
迭代
(3) 对于给定的允许精度，如果
| xk1 xk | 则终止迭代，取 x* xk 1;否则k=k+1，再转
g(x2)
y=g(x)
y=g(x)
g(x1)
g(x2)
arctan(a) pi / 4
g(x1)
x
x1
x2
x
x1 x2
计 重要： （迭代法的局部收敛定理）
算
方
法
定理条件非必要条件，而且定理中的压
缩条件不好验证，一般来讲，
若知道迭代函数g(x)∈C1『a,b］(1),并
且满足|g′(x)|≤ ≤1(2), 对任
g (x) 的不动点 Fixed-Point
Picard Iteration
计 迭代法流图
算
开始
方
法
输入x0 ,
x1 g(x0)
x1 x0
N
x0 x1
Y
输 出 x1
结束
计 算 方 法
For example：2x3-x-1=0
计 (1) 如果将原方程化为等价方程
算仍取初值 x0 0

x x1 x*