第六章6[1].3迭代法的收敛性

迭代法的收敛性与误差估计一…的童滚.11/{安务刊迭代法的收敛性.与误差估计’\虞福星..Z冬}7.在许多工程技术问题中,常常会遇到求解一元非线性方程的问题.例如,代数方程一x—l一0或超越方程x+{x—l看上去形式很简单,但不易求出其准确根,只能求出方程达到一定精度的近似根.求解这类方程的方法很多,迭代法就是其中的一种.迭代法有许多优点:1.其算法的逻辑结构简单f2.收敛速度快I3.中间结果有扰动不会影响计算结论;4.计算误差容易控制.正因为如此,迭代法得到非常广泛的应用.一,迭代法的基本思想设有方程f(11=0首先,我们设法将式(1)代成下列等价形式x—g∽然后按式(2)构造迭代公式(1)(2)+l—g{-,k=o,1,2, (3)从给定的初始近似根x.出发,按迭代公式(3)可以得到一个敦列x.,x1,x2,...,x, (4)如果这个数列{}有极限,则称迭代公式(3)是收敛的,此时数列螅极限x=limx就是原方程(1)的根.二,迭代法的收敛性及误差估计具备怎样的条件,迭代公式(3)是收敛的,这就是我们要讨论的中心问题.对此,我们有定理:设方程x—g在(a,b)内有根x,若gt满足李普希茨条件,即对(a,b)内任意的x】和都有lg(x1)g(x2)l≤qlxl—x2l(5)q为某个正数,当q<1时,则方程在(a’b)内有唯一的根I且迭代公式(3)对任意初始近似值xo均收敛于根x;还有误差估计式一≤lXk--Xkil≤lXI--Xol(6)证明:先证唯一性由已知条件知,x’是方程x—g的根,即x一g66设i也是方程x=g(x)的根,则x=g于是1x一i1=1g)--g1由李普希茨条件,得1x一;1一Ig(-～g’;I≤q1x一il因为0<q<1,故必有x.=;,根的唯一性得证. 再证收敛性由李普希茨条件,得IXk+I--X.l=Ig’--g)l≤qI一x.I同样l一x’l≤qIXk一1一x.1,…,1x1--X.1≤qI～x’1于是有1+I—x’I≤?Ix.一x’1因为0<q<1,当k—o.时,一0,即有Ix…--X’j—O(k—oo)所以,limxx.k一收敛性得证.利用李普希茨条件,得l+1～f=fg’)--g(,一.I≤Ix,一一1I于是对任意正整数P,有l+p一1≤1Xk—p一+rII+1Xk+p一1--Xk+p一±1+…+1一1一I≤(q+qP 一+…+q)?j一l一lxr令P—oo,得一I≤一一l≤IX1--X0I三,选择迭代公式的原则如果方程(2)中的g’满足Ig’I]l≤M<IxE(a,b)则可取这里的M作为李普希茨(5)中的q,由式(6)可知,正数q越小,收敛速度越快.所以,选遗代公式要遵循使IgI在(a山)的最大值M为最小这个原则.由于把方程f㈨一0化成等价形式x;g的方法很多.例如,方程x一x一1—0可以化成以下四种形式(1)x一一167(2)x一+1㈣x=X--每=㈤x一一由此可得四个迭代公式x+?=x:一1(7);(8):(9)’(9)l一—)(,)式(1I)也可用牛顿切线法导出,可见牛顿切线法可视为谴代法的特殊情形.由于=苎【)所以.f(?f().因此,只要ll≤q<l,L”)J公式(II)就收敛68。

4 2 1
1 5 1
1
2
3
问题：该矩阵具有怎样的特点？ 结论：该矩阵是严格对角占优阵
定义：如果矩阵A的元素满足
jn
| aii | | aij | i 1,2,3,, n j 1 ji
则称A为严格对角占优矩阵。
9
特殊方程组迭代法的收敛性
定理：若线性方程组AX=b的系数矩阵A为 严格对角占优矩阵，则解该方程组的Jacobi 迭代法和G-S迭代法均收敛。
则: (k1) B (k ) B2 (k 1) Bk1 (0)
注意 (0) x(0) x * 为非零常数向量
因此迭代法收敛的充要条件
lim (k1) lim( x(k1) x*) 0
k
k
可转变为
lim Bk1 0
k

2
一阶定常迭代法的收敛性
定理：迭代格式 x(k1) Bx(k ) f 收敛 的充要条件为：lim Bk 0
k
lim Bk 0
k
即: (B) 1
B的所有特征值的绝对值小于1
B的谱半径
根据矩阵与其Jordan标准形及特征值的关系
3
一阶定常迭代法的收敛性
定理：设B为n阶实矩阵，则 lim Bk 0 k
的充要条件是 (B) 1
定理：迭代格式 x(k1) Bx(k ) f 收敛 的充要条件为：(B) 1
4
一阶定常迭代法的收敛性
例：判别下列方程组用Jacobi迭代法和G-S 法求解是否收敛。
1 2 2 x1 1 1 1 1 x2 1 2 2 1 x3 1
5
一阶定常迭代法的收敛性
解: (1) 求Jacobi法的迭代矩阵
1 0 0 0 2 2

１，故应先求迭代矩阵。而
1 2 2
A 1 1
1
2 2 1
故A分解后的各矩阵分别为
1
D
1
1
0 0 0
L
1
0
0
2 2 0
0 2 2
U 0 0 1 0 0 0
Jacobi迭代法的迭代矩阵为
0 2
1 2 2
2 A 1 1
2 2 1
0 2 1
于是迭代矩阵为
0 2 2
M (D L)1U 0 2 3 0 0 2
其特征方程为
2 2 | I M | 0 2 3 ( 2)3 0
0 0 2
故 (B) 2 1,
所以Gauss-Seidel迭代法发散。
请思考: (1) 若 记 不 住 Jacobi 迭 代 法 和 GaussSeidel迭代法的矩阵表示，怎么写出迭 代矩阵？
Ax b ,
其中A
9 3
4 10
显然Aˊ是严格对角占优阵，因此对方程组
Ax b 用Jacobi法和Gauss-Seidel法均收敛。
例 3 ： 设 A=(aij) 是 二 阶 方 阵 ， 且 a11a22≠0. 试 证 求 解 方 程 组 Ax=b 的 Jacobi 法 与 Gauss-Seidel 法 同时收敛或发散。
注：定理表明，迭代法收敛与否只决定于迭代 矩阵的谱半径，与初始向量及方程组的右 端项无关。对同一方程组，由于不同的迭 代法迭代矩阵不同，因此可能出现有的方 法收敛，有的方法发散的情形。
举例：解方程组
x1 x1
2x2 2x3 x2 x3 2
1
2 x1 2 x2 x3 3
讨论Jacobi法与Gauss-Seidel法的收敛性。

k
充分性: 若 ( A) 1, 取 1 ( A) 0
2
则存在一种矩阵范数||.||，使得
|| A || ( A) 1 ( A) 1
2 而 || Ak |||| A ||k 于是
lim || Ak || lim || A ||k 0
k
k
所以
lim Ak 0
k
二、迭代法的收敛条件
ln(
)
x(1) x(0)
x(1) x(0) k
ln B
下面对一些特殊的系数矩阵给出几个常用的判 断收敛的条件。
定义：若n阶方阵 A=(aij)满足
n
| aii | | aij |
(i 1,2,..., n)
j 1 ji
且至少有一个 i 值，使上式中不等号
严格成立，则称A为弱对角占优阵。
若对所有 i，不等号均严格成立，则 称A为严格对角占优阵。
例如：
10 1 2 矩阵 A 1 10 2 是严格对角占优阵
1 1 5
2 1 0 不是严格对角占优阵 矩阵 B 1 2 1
0 1 2
设有线性方程组Ax=b，下列结论成立：
1. 若A为严格对角占优阵，则Jacobi迭代法和 Gauss-Seidel迭代法均收敛。
例2：设方程组Ax=b的系数矩阵为
A
3 9
10 4
则 Jacobi 法 与 Gauss-Seidel 法 的 迭 代 矩 阵分别是
B
0 9/
4
10 / 3 0
M
0 0
10 / 3 15 / 2
其谱半径分别为
(B) 30 , (M ) 15
2
2
故这两种迭代法均不收敛。