第二节 迭代法及其收敛性1

∵ f ( x0 ) < 0,∴令a1 = x0 = 1.25, b1 = b = 1.5,
[a 得新的有根区间 1 , b1 ]
如此二分下去即可。 如此二分下去即可。现估计二分次数
x − xn < 0.005 ⇒ n ≥ 5.64
*
所以二分6次可达到要求。 所以二分6次可达到要求。
精确解为: 精确解为: x =1.324718
y = ϕ( x) 又 x = ϕ( x) 的解⇔ 的解 y = x
（两条线的交点） 两条线的交点）
迭代法的几何意义
y
y=x
y
y = ϕ ( x)
x
x
迭代法的几何意义
y
y=x
y
y=x
y=ϕ(x)
y=ϕ(x)
0
x1
x3 x5ξ x4 x2 x0
x
0
x3 x1 ξ x0 x2
x4
x
简单迭代法例题
只要二分足够多次（即充分大）， 只要二分足够多次（ k充分大），
则有 x* −xk < ε
. ε 这里 为预定的精度
区间二分法
对分区间次数的估计
bn − an b − a 由 x * −xn ≤ = n+1 < ε 2 2
不难得出： 不难得出：
ln( b − a) − lnε n> −1 ln 2
= (L
p−1
+L
p−2
+⋯+ 1) xn+1 − xn
简单迭代法收敛定理
1− L 1− L n xn+1 − xn ≤ L x1 − x0 = 1− L 1− L
p p
即

Bk 0(零矩阵)(k )
定义 6.5 设有矩阵序列 Ak (aij(k ) ) Rnn 及 Ak (aij ) Rnn ，如果 n2 个数列极限存在
且有
lim
k
a (k) ij
aij
(i,
j
1,2,..., n)
则
Ak
称收敛于
A
记为 lim(k
)
。
定理 6.5
lim
k
Ak
A
lim
三 松弛法例题与程序
例 6.9 取 1.4, x(0) (1,1,1)T 用超松弛法解方程组
2x1 x2
1
x1 2x2 x3 0
x2 2x3 1.8
� � 解：由 xi(k1)
(1 )xik
aii
(bi
i 1 j 1
a x(k 1) ij j
n
aij
x
(k j
x j(k ) ) / aii xi(k )
j i
j i 1
i 1
n
(bi aij x j(k 1) aij x j(k ) ) / aii
ji
ji
(i 1,, n; k 0,1,).
� � i1
n
xi
b x(k 1) ij j
bij
x(k) j
gi
x(k) i
j 1
j i 1
a x(k1) ij j
aij x(jk ) ) / aii .
j 1
j i 1
(2) 再由 x(k) 与 ~xi(k 1) 加权平均定义 xi(k 1) ，即
x(k 1) i
(1 )xi(k)
x%i(k 1)

A 2.
一阶定常迭代法的基本定理
迭
设线性方程组 Ax b ,(3.1) 其中 A (aij ) Rnn 为非奇异矩阵，记 x* 为
代 (3.1) 精确解，且设有等价的方程组
法
的
Ax b x Bx f .
收 敛 于是 性
x Bx f (3.2)
与 稳
设有解 Ax b 的一阶定常迭代法
迭 代
(1) A为严格对角占优阵，则解Ax=b的Jacobi迭代法, Gauss-Seidel 迭代法均收敛.
法 (2) A为弱对角占优阵，且A为不可约矩阵, 则解Ax=b的Jacobi迭代法, Gauss-Seidel
的 收
迭代法均收敛.
敛
只证(1)，(2)作为练习
性 与
因为A是严格对角占优阵，所以 aii 0(i 1,L , n) Jacobi迭代阵
4
x1
11x2
x3
33,
的收敛性.
迭 代
6
x1
3 x2
12 x3
36.
法
解得
的
收 敛
1 0.3082,2 0.1841 0.3445i,3 0.1841 0.3445i,
性 与
1 0.3082 1, 2 3 0.3592 1.
稳
定
即(J ) 1 所以用Jacobi方法解方程组是收敛的.
Ak
x
Ax.
一阶定常迭代法的基本定理
例3
设有矩阵序列{ Ak } ，其中Ak Bk 而
迭 代 法
B
0
1
,
B2
2
0
2 2
,
, Bk
k
0
kk 1 k

3、求所有单重实根的算法核心
基本思想 —— 需求出区间 [a,
b] 上所有的单重 实根，满足两个求根精度控制量ε1或ε2。自a点 开始，以一个基本步长h，向右逐次分割出宽 度为h的小区间[a0, b0]。若小区间两端点处的 函数值f(a0)与f(b0)异号，则用二分法找出其中 存在的一个根；若同号，则继续向右分割，重 复上述操作，直至分割的小区间已超过定义或 求根区间[a, b]为止。 步长 h 可以选的小些，以便每个小区间内最多 只有一个根，这样并不浪费很多机时，根据问 题的性质h也没有必要太小。
参数说明： a，b——求根区间[a,
b]（实型变量，输入参数）； h——步长（实型变量，输入参数）； n —— 估计根的最多个数（与 x方次数有关，整型变 量，输入参数）； ep1 —— 函数值精度控制量 ε1 （实型变量，输入参 数）； ep2——根的精度控制量 ε2（实型变量，输入参数）； k——实际求出的根的个数（整型变量，输出参数）； x[n] —— 存放所求的根的一维实型数组（输出参 数）； f——求解方程的函数名，可以嵌套调用，但需要在 调用它的函数前出现。


3、迭代法的收敛性
如果从初值x0出发，按照迭代公式进行迭代计 算的过程中，xk逐次接近于方程的跟，则称迭 代公式是收敛的，否则是发散的。迭代法可行 的必要条件是迭代过程必须收敛，收敛越快， 则其收敛性越好。 判别条件——迭代函数的一阶导数在其定义区 间 [a,b] 内的绝对值小于 1 ，迭代过程收敛，否 则，则发散。
1、定义
二分法——也称对分法，是另一种简单易行的
求非线性方程数值解的方法。不仅克服了迭代 法可能不收敛的缺欠，即在有根区间用二分法 肯定收敛于极值，而且其收敛速度也很快。 假设有一个非线性方程f(x)=0，x在[a0, b0]区间 内，当f(x)在区间[a0, b0]上单调连续，且f(x)在 其 区 间 [a0, b0] 的 两 个 端 点 处 的 值 异 号 ， 即 f(a0)· f(b0)<0时，则方程在[a0, b0]区间内有根， 且只有一个根x*。