作为根的初始近似。
开 始 读入a, h a x0 f (x0) y0 x0 + h x0 是 继续扫描
f (x0) y0>0
打 印 否 结 束
例1：考察方程 f ( x) x 3 x 1 0 的含根区间
x f (x)符号
0 －
0.5 －
1.0 －
1.5 ＋
可见，含根区间为 [1, 1.5]
由定理4.2.1知，迭代格式xk+1＝(lgxk+7)/2 在[3.5,4]内收敛
局部收敛性定理
定理4.2.2 设x*为g的不动点，g(x)与g′(x)在 包含x*的某邻域U(x*) (即开区间)内连续， 且|g′(x*)|<1,则存在>0，当x0∈［x* ，x*+ ］时，迭代法(3)产生的序列 {xk} ［x* - ，x*+ ］且收敛于x*. 证明略（作为练习）
Remark3:二分法不能用来求重根
§4.2 单个方程的迭代法
等价变换
f (x) = 0 f (x) 的根
x = g (x)
xk+1 = g(xk)
(3)
g (x) 的不动点
f(x)=0化为等价方程 x=g(x)的方式是不唯一 的,有的收敛,有的发散 For example：2x3-x-1=0
(1) 如果将原方程化为等价方程 x 2 x3 1
Remark：
定理条件非必要条件，而且定理4.2.1中 的压缩条件不好验证，一般来讲， 若知道迭代函数g(x)∈C1『a,b］,并 且满足|g′(x)|≤ < 1,对任意的 x∈［a,b］, 则g（x)是［a,b］上的压缩映射
y p1 p0
y=x y=g(x)
y p0
y=x

x x0 y y=g(x) x1 x* y=x y y=g(x) p0 x0 x*
§4.1 对分区间法 (Bisection Method )
原理：若 f(x) C[a, b]，且 f (a) · (b) < f 0，则f(x) 在 (a, b) 上必有一根。
a
a12 ax1
x* b x2
b b1
停机条件： k 1 xk ε1 或 x
f ( x ) ε2
不能保证 x 的精 度
ln 2
定义f (x)
输入
a,b,
k=0
f (a) f (b)>0 否 否 m=(a+b)/2 |a-b|< 是 a=m 是 打印m, k 结束 f (a) f (b)=0
是
是 是
f (a) =0
否
否 f(a)f(b)>0 否 b=m
打印b, k
结束
打印a, k
k=k+1
x 3 4 x 2 10 0 例2 用二分法求 1 在(1,2)内的根，要求绝对误差不超过 10 2 2 解：
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 of iterations to use..
2
x* x
执行步骤 1．计算f (x)在有解区间[a, b]端点处的值，f (a)，f (b)。 2．计算f (x)在区间中点处的值f (x1)。 3．判断若f (x1) = 0，则x1即是根，否则检验： （1）若f (x1)与f (a)异号，则知解位于区间[a, x1]， b1=x1, a1=a; （2）若f (x1)与f (a)同号，则知解位于区间[x1, b]，
第四章 非线性方程的数值解法
非线性方程求根
1．根的存在性。方程有没有根？如果有根，有几个根？ 2．这些根大致在哪里？如何把根隔离开来？ 3．根的精确化 定理1：设函数 f (x) 在区间[a, b]上连续，如果f (a) f (b) < 0，
则方程 f (x) = 0 在[a, b]内至少有一实根x*。

p1 y=g(x) x x1 y=x
p0 p1

x x0 x*
p1

x
x1 x0 x*
x1
改进、加速收敛 /* accelerating convergence */
待定参数法： 若 | g’(x) | 1，则将 x = g(x) 等价地改造为
x x Kx Kg( x ) (1 K ) x Kg( x ) ( x ) 求K，使得 | ( x ) | | 1 K Kg( x ) | 1
在这里我们考查在区间[3.5,4]的迭代法 的收敛性
• 很容易验证：f(3.5)<0,f(4)>0 • 将方程变形成等价形式：x＝(lgx+7)/2
1 g(x)= (lg( x) 7) 2 1 1 g ( x) 2 ln10 x
3.5 x 4
max | g ( x) | 0.063 1
x0 1 2
3
1 2
0.7937
x2
3
x1 1 3 1.7937 0.9644 2 2
依此类推,得 x3 = 0.9940 x4 = 0.9990 x5 = 0.9998 x6 = 1.0000 x7 = 1.0000
同样的方程
⇒ 不同的迭代格式
有不同的结果
什么形式的迭代 法能够收敛呢?
（3）k次迭代所得到的近似不动点xk与精确不动点x*有误差估计 式：
xk x xk xk 1 (6) 1 k * xk x x1 x0 (7) 1
*
§3 Fixed-Point Iteration
证明：① g(x) 在[a, b]上存在不动点？
令G(x)=g(x)-x, x∈［a,b］，由条件①知 G(a)=g(a)-a≥0, G(b)=g(b)-b≤0.
已经收敛,故原方程的解为 x = 1.0000
收敛性分析
定义2 若存在常数(0≤ <1),使得对一 切x1,x2∈［a,b］, 成立不等式 |g(x1)-g(x2)|≤ |x1-x2|， (5) 则称g(x)是［a,b］上的一个压缩映射， 称为压缩系数
定理4.2.1 考虑方程 x = g(x), g(x)C[a, b], 若
f(1)=-5<0 f(2)=14>0 f(1.5)>0 f(1.25)<0 f(1.375)>0 f(1.313)<0 f(1.344)<0 f(1.360)<0 f(1.368)>0
有根区间 -(1,2)+ (1,1.5) (1.25,1.5) (1.25,1.375) (1.313,1.375) (1.344,1.375) (1.360,1.375) (1.360,1.368)
a1=x1, b1=b。 反复执行步骤2、3，便可得到一系列有根区间：
(a, b), (a1, b1), …, (ak, bk), …
4、当 bk 1 ak 1 时，则 xk 1
即为根的近似。
1 ( a k bk ) 2
①简单; ② 对f (x) 要求不高(只要连续即可) .
1．画出 f(x) 的略图，从而看出曲线与x 轴交点的位臵。 f(x)
x0
a x0 h
x *
b
2．从左端点x = a出发，按某个预先选定的步长h 一步一步地向右跨，每跨一步都检验每步起点x0
和终点x0 + h的函数值，若 f ( x0 ) f ( x0 h ) 0
那么所求的根x*必在x0与x0+h之间，这里可取x0或x0+h
[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. （如下图）
( I ) 当 x[a, b] 时， g(x)[a, b]；
( II )在［a,b］上成立不等式：|g(x1)-g(x2)|≤ |x1-x2| 。 则（1）g在［a,b］上存在惟一不动点x* （2）任取 x0[a, b]，由 xk+1 = g(xk)
得到的序列 {xk}（［a,b】） 收敛于x* 。
可用 | xk 1 xk | 来 控制收敛精度
这就证明了估计式(6).
(5) |xk-xk-1| = |g(xk-1)-g(xk-2)|
≤

|x k-1-xk-2|≤…≤

k-1|x
1-x0|
联系估计式(6)可得
|xk-x*| ≤
k-1/(1-)|x1-x0|.

越小，收敛越快
即估计式(7)成立
3 则迭代格式为：xk 1 2 xk 1
取初值
x0 0
x1 2 x 1 1
3 0
x2 2 x 1 3
3 1
x3 2 x 1 55
3 2
由此可见，这种迭代格式是发散的
(2) 如果将原方程化为等价方程
仍取初值
x0 0
3
x3
x1 2
x1
f ( x ) x 3 3 x 1 0 在 (1, 2) 的实根。 例：求