数值分析 迭代法 二分法和迭代法原理

第三章迭代法§3.1 二分法 §3.2 迭代法原理 §3.3 Newton迭代法和迭代加速 §3.4 解线性方程组的迭代法

§3.1 二分法根的估计 二分法

非线性方程的根求 f (x) = 0 的根 代数方程： f (x) = a0 + a1x + . . . + anxn 超越方程： f (x) 含超越函数，如 sin(x), ex, lnx 等 实根与复根 根的重数f (x) = ( x – x*)m · g(x) 且 g(x*) 0, 则称 x* 为 f (x) 的 m 重根如果有k 1, f ( x* ) f '( x* ) ... f ( k 1) ( x* ) 0, f ( k ) ( x* ) 0, 则x*为k重根.

有根区间：[a, b] 上存在 f (x) = 0 的一个实根 研究 内容: 在有根的前提下求出方程的近似根。

根的估计引理3.1(连续函数的介值定理) 设f(x)在 [a,b]上连续，且f(a) f(b)<0,则存在x* (a,b) 使f(x*)=0。 例3.1 证明x3 3x 1 = 0 有且仅有3个实根，并 确定根的大致位置使误差不超过 =0.5。 解:单调性分析和解的位置 选步长h=2 , 扫描节点函数值 异号区间内有根

第一节 二分法 基本原理：若 f C[a, b],且 f (a) · f (b) < 0,则 f 在 (a, b) 上必有一根。

具体方法：通过二等分不断缩小有根区间的长度，直到满足精度为止。 何时终止?a x0 x* x1 b

xk 1 xk ε 或 f ( xk ) ε不能保证 x 的精 度

算法算法 3.1 (二分法)给定有根区间 [a, b] ( f(a) · f(b) < 0) 和 精度要求 1. 令 x = (a+b)/2 2. 如果 b – a <= 2 , 停止计算，输出 x ,否则执行第3步 3. 如果 f (a) f (x) < 0 , 则令 b = x,否则令 a = x, 返回第1步 P50. Matlab源程序：nabisect.m 用二分法求根，通常先给出 f (x) 草图以确定根的大概位置。

误差分析记 a0 = a, b0 = b, 第 k 步的有根区间为 [ak, bk]

bk ak bk ak bk 1 ak 1 xk x x 2 2 2 2

b0 a0 b a k 1 k 1 2 2

对于给定的精度 ,可估计二分法所需的步数 k : b a b a b a 1 ε k log 2 1, 取 k log 2 k 1 2 简单易用 对 f (x) 要求不高，只要连续即可 收敛速度慢 无法求复根及偶重根

例3.2 求x3 3x 1 = 0在 [1,2]内的根两位有效数字 =0.5*10-1 , k≥ (ln 20/ ln 2)-1, 取k=4

§3.2 迭代法原理迭代法的思想 不动点原理 局部收敛性 收敛性的阶

第二节 迭代法原理 基本思想f (x) = 0 f (x) 的零点x* xk+1 = (xk)等价变换

x = (x) 称为迭代函数

(x) 的不动点x*不动点迭代

具体做法：从一个给定的初值 x0 出发，计算 x1 = (x0), x2 = (x1), … x 若 k k 0 收敛，即存在 x* 使得 lim x k x *,则由 的连续k

xk 1 lim xk 可得 x* = (x*),即 x* 是 的不 性和 lim k k

动点，也就是 f (x) 的零点。

几何含义：求曲线 y = (x)

与直线 y = x 的交点

例

x3 x 1 = 0, [1,2], 取 x0=1.53 x x 迭代公式1: k 1 k 1

迭代公式2: x 计算结果：公式1:

k 1

( xk 1)

1 3

k 0公式2:

xk 1.5

k

xk

1 1.35721 2 1.33086 3 1.32588 4 1.32494 5 1.32476 6 1.32473 7 1.32472

0 1.5 1 2.375 2 3 12.4 1904

精确解x* =

1.3247179...

怎么判断迭代公式收敛或发散呢？

不动点原理定理 (不动点原理，压缩映像定理) 3.1 设 (x)在[a, b]上连续， 且一阶导数连续，若 (1) a (x) b 对一切 x [a, b] 都成立, 封闭性 (2) 存在 0 L < 1,使得 | ’(x) | L 对 x [a, b] 成立, 压缩性

则函数 f (x) = x - (x) 在 [a, b] 中有唯一的零点 x*。x* 称为 (x) 的不动点

(x*) = x*

简证： f(a) = a - (a) 0 , f(b) = b - (b) 0

f(x) 在[a, b] 上有零点。 唯一性：反证法，假设存在 x*, y* [a, b] 使得

x* = (x*) y* = (y*)

x * y * ( x*) ( y*) '( ) x * y * L x * y * 矛盾！

收敛性分析定理 设 (x)在[a, b]上连续，且一阶导数连续，若 3.1 (1) a (x) b 对一切 x [a, b] 都成立, (2) 存在 0 L < 1,使得 | ’(x) | L 对 x [a, b] 成立, 则有 (a) 对任意 x0 [a, b],由 xk+1 = (xk) 产生的迭代序列 均收敛到 (x) 在 [a, b] 中的唯一不动点 x*。 xk k 0 (b) 有如下的误差估计: 后验估计:L | xk x* | | xk xk 1 | 1 LLk | xk x* | | x1 x0 | 1 L

可用| x k-xk-1 | 来控制收敛精度 L 越小收敛越快

先验估计:

证： (a) 由压缩映像定理可知，不动点 x* 存在且唯一。| xk x*| ( xk 1 ) ( x*) | '( ) | | xk 1 x*| L | xk 1 x*|| xk x*| L | xk 1 x*| L2 | xk 2 x*| Lk | x0 x*|

lim | xk x* | 0k

即 lim xk x *.k

(b) | xk 1 x*| L | xk x*|| xk 1 xk | | ( xk 1 x*) ( xk x*) | xk x * xk 1 x * (1 L) xk x * 1 xk x * xk 1 xk 1 L 又 | xk 1 xk | ( xk ) ( xk 1 ) | '( ) | | xk xk 1 | L | xk xk 1 |1 L xk x * xk 1 xk xk xk 1 1 L 1 L Lk x1 x0 1 L

全局收敛与局部收敛 定理的条件保证了不动点迭代的全局收敛性。 即迭代的收敛性与初始点的选取无关。 定理中的条件 | ’(x) | L < 1 可以适当放宽(2’) ’(x) 在 x* 的某个邻域内连续，且 | ’(x*) | <1 由 ’(x) 的连续性及 | ’(x*) | <1 即可推出：定理3.2 若条件(2’)成立, 则存在 x* 的某个 邻域 N(x*) =[x*- , x* + ], 使得对 x N(x*)都有 | ’(x) | L < 1, 则由 x0 N(x*) 开始的迭代都收敛。

这种在 x* 的邻域内具有的收敛性称为

局部收敛性。具有局部收敛性的迭代计算上不一定收敛，它是否收敛还 要看初值是否取的恰当； 而不具有局部收敛性的迭代对任何初值都不可能收敛。