of iterations to use..
[0,1], [1.5, 2.5] and [3,4]， 利用前面的公式可计算 迭代次数为k=23.
Remark2:要区别根与奇异 点
Consider f(x) = tan(x) on the interval (0,3).Use the 20 iterations of the bisection method and see what happens. Explain the results that you obtained. （如下图）
2k ε k
ln 2
例1 用二分法求 x 3 4 x 2 10 0
在(1,2)内的根，要求绝对误差不超过 解：
1 102 2
f(1)=-5<0 有根区间
中点 xn
f(2)=14>0 f(1.5)>0 f(1.25)<0
-(1,2)+ (1,1.5) (1.25,1.5)
xx21
1.5
xb2
bb1
停机条件（termination condition ）：
xk1 xk ε1 或 f ( x) ε2
误差 分析：
第1步产生的
x1
a
2
b
有误差
|x1
x*|
b
2
a
第 k 步产生的 xk 有误差
|xk
x*|
ba 2k
对于给定的精度 ,可估计二分法所需的步数
k：
ba
lnb a ln ε
Remark3:二分发不能用来求重根
§3.2 单个方程的迭代法
f (x) = 0
等价变换
x = g (x)
f (x) 的根
g (x) 的不动点
f(x)=0化为等价方程 x=g(x)的方式是不唯一 的,有的收敛,有的发散
For example：2x3-x1=0
(1) 如果将原方程化为等价方程
则迭代格式为：xk1 2xk3 1
x7 1.368 x8 1.364
例2，求方程f(x)= x 3 –e-x =0的一个实根。
因为 f(0)<0,f(1)>0。 故f(x)在(0,1)内有根
用二分法解之，(a,b）=（0,1)’计算结果如表：
k
a
bk
0
0
1
xk 0.5000
f(xk)符号 －
1
0.5000 －
0.7500
－
2
0.7500 －
12
Remark1：求奇数个根
Find solutions to the equation
on the intervals [0, 4]，Use the bisection method to compute a solution with an accuracy of 10－7. Determine the number
简介（Introduction）
❖ 我们知道在实际应用中有许多非线性方程的 例子，例如
❖ （1）在光的衍射理论（the theory of diffraction of light)中,我们需要求x-tanx=0的 根
❖ （2）在行星轨道（ planetary orbits）的计算 中,对任意的a和b，我们需要求x-asinx=b的根
|g(x1)-g(x2)|≤ |x1-x2|， (5) 则称g(x)是［a,b］上的一个压缩映射，
称为压缩系数
定理3.2.1 考虑方程 x = g(x), g(x)C[a, b], 若
( I ) 当 x[a, b] 时， g(x)[a, b]；
( II )在［a,b］上成立不等式：|g(x1)-g(x2)|≤ |x1-x2| 。
取初值 x0 0
x 2x3 1
x1 2x03 1 1
x2 2x13 1 3 x3 2x23 1 55
由此可见，这种迭代格式是发散的
(2) 如果将原方程化为等价方程
仍取初值
x0 0
3
x1
x0 1 2
3 1 2
x3 x1 2
0.7937
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
收敛性分析
定义2 若存在常数(0≤ <1),使得对一 切x1,x2∈［a,b］,
1.25
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
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)
❖
（3） 在数学中，需要求n次多项式xn
1+...+an-1 求x f+(xa)n=＝0的0的根 根
+
a1
xn-
§3.1 对分区间法 (Bisection Method )
原理：若 f(x) C[a, b]，且 f (a) ·f (b) < 0，则f(x) 在 (a, b) 上必有一根。
a
aax211 x*
0.8750
＋
ห้องสมุดไป่ตู้
3
－
0.8750 0.8125
＋
4
－
0.8125 0.7812
＋
5
－
0.7812 0.7656
－
6
0.7656 －
0.7734
＋
7
－
0.7734 0.7695 －
8 0.7695 －
0.7714
－
9
0.7714 －
0.7724
－
10
0.7724 －
0.7729
＋
取x10=0.7729，误差为| x* -x10|<=1/211 。
则（1）g在［a,b］上存在惟一不动点x*
（2）任取 x0[a, b]，由 xk+1 = g(xk) 得到的序列 {xk}（ ［a,b】） 收敛于x* 。
（3）k次迭代所得到的近似不动点xk与精确不动点x*有有误差估
计式：
xk x*
1
xk xk 1
xk x*
k
1
x1 x0
证明：① g(x) 在[a, b]上存在不动点？
§3 Fixed-Point Iteration
令G(x)=g(x)-x, x∈［a,b］，由条件①知G(a)=g(a)-a≥0, G(b)=g(b)-b≤0.
由条件②知G(x)在［a,b］上连续，又由介值定理知
存在x*∈［a,b］，使G(x*)=0，即x*=g(x*).
✓
② 不动点唯一？
若有x′∈［a,b］,满足g(x′)=x′，