第6章 解线性方程组的迭代法

第6章

解线性方程组的迭代方法

6.1 迭代法的基本概念 6.2 雅可比迭代法与高斯-赛德尔迭代法

6.3 超松弛迭代法 6.4* 共轭迭代法

上页

下页

6.1 迭代法的基本概念6.1.1 引 言 对线性方程组 Ax=b, (1.1) 其中A为非奇异矩阵, 当A为低阶稠密矩阵时, 第5章 讨论的选主元消去法是有效的. 但对于大型稀疏矩 阵方程组(A的阶数n很大 104,但零元素较多), 利 用迭代法求解是合适的. 本章将介绍迭代法的一些基本理论及雅可比 迭代法，高斯-赛德尔迭代法，超松弛迭代法，而 超松弛迭代法应用很广泛。 下面举简例，以便了解迭代法的思想.上页 下页

例1 求解方程组

8 x1 3 x2 2 x3 20, 4 x1 11 x2 x3 33, 6 x 3 x 12 x 36. 2 3 1记为Ax=b,其中

(1.2)

x1 8 3 2 30 A 4 11 1 , x x2 , b 33 . x 6 3 12 36 3 此方程组的精确解是x*=(3,2,1)T. 现将(1.2)改写为

上页

下页

1 3 x 2 2 x 3 20), x1 8 ( 1 x 3 33), x 2 ( 4 x1 11 1 36). x 3 12 ( 6 x1 3 x 2 或写为x=B0x+f,其中3 2 8 0 20 8 8 4 33 1 B0 11 0 11 , f 11 . 6 3 0 36 12 12 12

(1.3)

上页

下页

我们任取初始值，例如取x(0)=(0, 0, 0)T. 将这些值代入(1.3)式右边(若(1.3)式为等式即求得方程组的解， 但一般不满足),得到新的值 x(1)=(x1(1), x2(1), x3(1))T =(3.5, 3, 3)T ,再将x(1)分量代入(1.3)式右边得到 x(2), 反复利用这个计算程序，得到一向量序列和一般的计

算公式(迭代公式)( ( ( x10 ) x11) x1k ) ( 0 ) (1) (1) (k ) x 2 , x x 2 , , x ( k ) x 2 , (0) (1) (k ) x3 x3 x3

x (0)

上页

下页

( ( ( x1k 1) ( 3 x2k ) 2 x3k ) 20) / 8, ( k 1) ( ( x2 ( 4 x1k ) x3k ) 33) / 11, ( k 1) (k ) (k ) ( 6 x1 3 x2 36) / 12. x3

(1.4)

简写为

x(k+1)=B0x(k) +f,

其中k表示迭代次数(k=0,1,2, ). 迭代到第10次有(10)

x

(3.000032 , 1.999838 , 0.999813 ) ;T

(10)

0.000187

( (10) x (10) x ).上页 下页

从此例看出，由迭代法产生的向量序列x(k)逐步 逼近方程组的精确解是x*=(3,2,1)T. 即有

lim x ( k ) x k

对于任何一个方程组x=Bx+f(由Ax=b变形得到的 等价方程组),由迭代法产生的向量序列x(k)是否一定 逐步逼近方程组的解x*呢？回答是不一定. 请同学们 考虑用迭代法解下述方程组

x1 2 x2 5, x2 3 x1 5.

但 x

(k)并不是 所有的都收 敛到解x*!

上页

下页

对于给定方程组x=Bx+f,设有唯一解x*,则 x*=Bx*+f . (1.5)又设x(0)为任取的初始向量, 按下述公式构造向量序列 x(k+1)=Bx(k)+f , k=0,1,2, . (1.6) 其中k表示迭代次数. 定义1 (1)对于给定的方程组x=Bx+f , 用公式(1.6) 逐步代入求近似解的方法称为迭代法(或称为一阶定 常迭代法，这里B与k无关). B称为迭代矩阵.

(2) 如果limx(k) (k→ )存在(记为x*), 称此迭代法收敛, 显然x*就是方程组的解, 否则称此迭代法发散.上页 下页

由上述讨论，需要研究{x(k)}的收敛性. 引进误 差向量

( k 1) x ( k 1) x ,由(1.6)减去(1.5)式，得 (k+1)=B (k) (k=0,1,2, ), 递推得

( k ) B ( k 1) B k ( 0 ) .要考察{x(k)}的收敛性，就要研究B在什么条件下 有limε(k)=0 (k→∞),亦即要研究B满足什么条件时有 Bk→0(零矩阵) (k→∞) .上页 下页

6.1.2 向量序列与矩阵序列的极限定义2 设向量序列{x(k)} Rn, x(k)= (x1(k),…,xn(k))T, 如果存在x= (x1, x2, …, xn)T Rn,使

lim xk

(k ) i

xi ,

i 1,2, , n. lim x ( k ) x. ,记作k

则称向量序列{x(k)}收敛于x 显然， lim xk (k )

x lim xk

(k )

x 0.

其中 · 为任一向量范数.

上页

下页

定义3 设矩阵序列Ak={aij(k)} Rn×n及A={aij} Rn×n, 如果n2个数列极限存在，且有

i , j 1,2, , n. k 则称矩阵序列{Ak}收敛于A ,记作 lim Ak A. lim a(k ) ij

aij ,

k 1 2 2 2 A ,A , , Ak 2 0 0 0 且设| |<1,考察其极限.解 显然，当| |<1时，则有

例2 设有矩阵序列

k

k k 1 , . k

0 0 lim Ak lim A 0 0 . k k k

上页

下页

矩阵序列极限概念可以用矩阵算子范数来描述.

定理1

lim Ak A lim Ak A 0,k k

其中 · 为矩阵的任意一种算子范数. 证明 显然有

lim Ak A lim Ak A 0.k k

再利用矩阵范数的等价性, 可证定理对其它范数成立.

上页

下页

定理2 limAk=0 的充分必要条件是

lim Ak x 0, x R n .k

(1.7)

证明 对任一种矩阵范数的从属范数有

Ak x Ak x .若limAk=0, 则lim||Ak||=0, 故对一切x Rn有lim||Akx||=0. 故(1.7)式成立. 反之，若(1.7)式成立，取x为第j个坐标向量ej, 则若limAkej =0, 表示Ak的第j列元素极限均为零，当 j=1,2, …,n时就证明了limAk=0. 证毕. 下面讨论一种与迭代法(1.6)有关的矩阵序列的收 敛性, 这种序列由矩阵的幂构成,即{Bk}, 其中B Rn×n.上页 下页

定理3 设B Rn×n,则证明3个命题等价： (1) limBk =0; (2) (B)<1;

(3)至少存在一种从属的 矩阵范数||· ,使||B|| <1. ||证明 (1)=>(2) 用反证法，假定B有一个特征值 , 满足| | 1,则存在x 0,使Bx= x,由此可得||Bkx||= | |k||x||, 当k→ 时{Bkx}不收敛于零向量. 由定理2可知(1)不成 立，从而知| |<1 ,即(2)成立. (2)=>(3) 根据第5章定理18,对任意 >0,存在一 种从属范数||· ,使||B|| (B)+ ,由(2)有 (B)<1,适 || 当选取 >0,可使||B|| <1,即(3)成立. (3)=>(1) 由(3) 给出的矩阵范数||B|| <1,由于 ||Bk|| ||B|| k, 可得lim||Bk||=0, 从而有limBk =0.上页 下页

定理4 设B Rn×n,||· ||为任一种矩阵范数，则

lim Bk

1 k k

( B ).

(1.8)

( B) ( B k ) k B k k . 1 另一方面对任意 >0,记 B ( B) B.B k

证明 由第5章定理18,对一切k有 1 1

显然有 (B )<1. 由定理3有limB k=0 ,所以存在正整 数N=N( ),使当k>N 时，

即k>N 时有

( B) B

( B ) 1k k

Bk

k

1.

( B) .上页 下页

由 的任意性即得定理结论.

6.1.3 迭代法及其收敛性设有线性方程组 Ax=b, 其中，A=(aij)∈Rn×n为非奇异矩阵，下面研究如何建 立解Ax=b的迭代法. 将A分裂为

A=M-N.

(1.9)

其中，M为可选择的非奇异矩阵，且使Mx=d容易求 解，一般选择A的某种近似，称M为分裂矩阵.

上页

下页

于是，求解Ax=b转化为求解Mx=Nx+b ,即求解

Ax b 求解 x M Nx M b.也就是求解线性方程组 x=Bx+f. 从而可构造一阶定常迭代法： (1.10)

1

1

x ( 0 ) (初始向量), ( k 1) x Bx ( k ) f ( k 0,1, , ),

(1.11)

其中 B=M-1N=M-1(M-A)=I-M-1A , f=M-1b. 称 B=I-M-1A为迭代法的迭代矩阵，选取M矩阵，就得 到解Ax=b的各种迭代法. 下面给出迭代法(1.11)式收敛的充分必要条件.上页 下页

定理5(一阶定常迭代法的基本定理) 给定线性 方程组(1.10)及一阶定常迭代法(1.11)式，对任意选 取初始向量x(0),迭代法(1.11)式收敛的充分必要条件 是矩阵B的谱半径 (B)<1. 证明 (<=) 设 (B)<1,易知Ax=f(其中A=I-B)有 唯一解，记为x*,则 x*=Bx*+f. 误差向量 (k)=x(k)-x*=Bk (0), (0)=x(0)-x* . 由设 (B)<1,应用定理3,有limBk=0. 于是对任意x(0) 有lim (k)=0,limx(k)=x*. (=>) 设对任意x(0)有limx(k)=x*, 其中x(k+1)=Bx(k)+f. 显然, 极限x*是线性方程组(1.10)的解, 且对任意x(0)有 (k)=x(k)-x*=Bk (0)→0 (k→ ) . 由定理2知limBk=0,再由定理3,即得 (B)<1.上页 下页

例3 考察线性方程组(1.2)给出的迭代法(1.4)式 的收敛性.解 先求迭代矩阵B0的特征值. 由特征方程

3 8

det( I B0 ) 可得3

4 11 1 2

1 4

1 4 1 11

0.

det( I B0 ) 0.034090909 0.039772727 0.

解得

1 0.3082 , 2 0.1541 i 0.3245 , 2 0.1541 i 0.3245 .

1 0.3082 1, 2 2 0.3592 1.即 (B0)<1,所以用迭代法(1.4)式解(1.2)是收敛的.上页 下页

例4 考察用迭代法解线性方程组x(k+1)=Bx(k)+f.

0 2 5 的收敛性，其中 B 3 0 , f 5 . 解 特征方程为det( I-B)= 2-6=0,特征值

1, 2 6 ,即 (B)>1,这说明用迭代法解此方程组不收敛. 迭代法的基本定理在理论上是重要的，由于 (B) ||B||,下面利用矩阵B的范数建立判别迭代法收 敛的充分条件.上页 下页

定理6(迭代法收敛的充分条件) 设有线性方程组 x=Bx+f, A=(aij)∈Rn×n, 及一阶定常迭代法 x(k+1)=Bx(k)+f. 如果有B的某种算子范数||B||=q<1,则 (1) 迭代法收敛，即对任取x(0)有 limx(k)=x*,且 x*=Bx*+f.

( 2) x x ( k ) q k x x ( 0 ) .( 3) x x (k )

( 4) x x ( k )

q x ( k ) x ( k 1 ) . 1 q k q x (1) x ( 0 ) . 1 q上页 下页