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

本文格式为Word版，下载可任意编辑——第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求解方程组

8x13x22x320,4x111x2x333,6x3x12x36.231记为Ax=b,其中

(1.2)

x183230A4111,xx2,b33.x6312363此方程组的确切解是x*=(3,2,1)T.现将(1.2)改写为

上页

下页

13x22x320),x18(1x333),x2(4x111136).x312(6x13x2或写为x=B0x+f,其中328020884331B011011,f11.63036121212

(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)x2,xx2,,x(k)x2,(0)(1)(k)x3x3x3

x(0)

上页

下页

(((x1k1)(3x2k)2x3k)20)/8,(k1)((x2(4x1k)x3k)33)/11,(k1)(k)(k)(6x13x236)/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.即有

limx(k)xk

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

x12x25,x23x15.

但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)}的收敛性.引进误差向量

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

(k)B(k1)Bk(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)TRn,使

limxk

(k)i

xi,

i1,2,,n.limx(k)x.,记作k

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

xlimxk

(k)

x0.

其中为任一向量范数.

上页

下页

定义3设矩阵序列Ak={aij(k)}Rnn及A={aij}Rnn,假使n2个数列极限存在，且有

i,j1,2,,n.k则称矩阵序列{Ak}收敛于A,记作limAkA.lima(k)ij

aij,

k1222A,A,,Ak2000且设||1,考察其极限.解显然，当||1时，则有

例2设有矩阵序列

k

kk1,.k

00limAklimA00.kkk

上页

下页

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

定理1

limAkAlimAkA0,kk

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

limAkAlimAkA0.kk

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

上页

下页

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

limAkx0,xRn.k

(1.7)

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

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

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

(3)至少存在一种附属的矩阵范数||,使||B||1.||证明(1)=(2)用反证法，假定B有一个特征值,满足||1,则存在x0,使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设BRnn,||||为任一种矩阵范数，则

limBk

1kk

(B).

(1.8)

(B)(Bk)kBkk.1另一方面对任意0,记B(B)B.Bk

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

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

即kN时有

(B)B

(B)1kk

Bk

k

1.

(B).上页下页

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

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

A=M-N.

(1.9)

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

上页

下页

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

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

1

1

x(0)(初始向量),(k1)xBx(k)f(k0,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的特征值.由特征方程

38

det(IB0)可得3

41112

14

14111

0.

det(IB0)0.0340909090.0397727270.

解得

10.3082,20.1541i0.3245,20.1541i0.3245.

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

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

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

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

定理6(迭