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

上页下页第6章解线性方程组的迭代方法•6.1迭代法的基本概念•6.2雅可比迭代法与高斯-赛德尔迭代法•6.3超松弛迭代法•6.4*共轭迭代法上页下页其中A为非奇异矩阵,当A为低阶稠密矩阵时,第5章讨论的选主元消去法是有效的.但对于大型稀疏矩阵方程组(A的阶数n很大104，但零元素较多),利用迭代法求解是合适的.本章将介绍迭代法的一些基本理论及雅可比迭代法，高斯-赛德尔迭代法，超松弛迭代法，而超松弛迭代法应用很广泛。下面举简例，以便了解迭代法的思想.对线性方程组Ax=b，(1.1)6.1迭代法的基本概念6.1.1引言上页下页例1求解方程组)2.1(.361236,33114,20238321321321xxxxxxxxx记为Ax=b，其中.363330,,12361114238321bxxxxA此方程组的精确解是x*=(3,2,1)T.现将(1.2)改写为上页下页)3.1().3636(121),334(111),2023(81213312321xxxxxxxxx或写为x=B0x+f，其中.,0001236113382012312611111482830fB上页下页我们任取初始值，例如取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)，反复利用这个计算程序，得到一向量序列和一般的计算公式(迭代公式),,,,)(3)(2)(1)()1(3)1(2)1(1)1()0(3)0(2)0(1)0(kkkkxxxxxxxxxxxx上页下页)4.1(.12/)3636(,11/)334(,8/)2023()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx简写为x(k+1)=B0x(k)+f，其中k表示迭代次数(k=0,1,2,).迭代到第10次有;)999813.0,999838.1,000032.3()10(Tx).(000187.0)10()10()10(xx上页下页从此例看出，由迭代法产生的向量序列x(k)逐步逼近方程组的精确解是x*=(3,2,1)T.即有对于任何一个方程组x=Bx+f(由Ax=b变形得到的等价方程组)，由迭代法产生的向量序列x(k)是否一定逐步逼近方程组的解x*呢？回答是不一定.请同学们考虑用迭代法解下述方程组.53,521221xxxx但x(k)并不是所有的都收敛到解x*！xxkk)(lim上页下页对于给定方程组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)}的收敛性.引进误差向量,)1()1(xxkk由(1.6)减去(1.5)式，得(k+1)=B(k)(k=0,1,2,)，递推得.)0()1()(kkkBB要考察{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，使.,,2,1,lim)(nixxikik则称向量序列{x(k)}收敛于x，记作.lim)(xxkk显然，.0limlim)()(xxxxkkkk其中·为任一向量范数.上页下页定义3设矩阵序列Ak={aij(k)}Rn×n及A={aij}Rn×n,如果n2个数列极限存在，且有.,,2,1,,lim)(njiaaijkijk则称矩阵序列{Ak}收敛于A，记作.limAAkk例2设有矩阵序列.,0,,02,01122kkkkkAAA且设||1，考察其极限.解显然，当||1时，则有.0000limlimkkkkAA上页下页矩阵序列极限概念可以用矩阵算子范数来描述.定理1证明显然有,0limlimAAAAkkkk其中·为矩阵的任意一种算子范数.再利用矩阵范数的等价性,可证定理对其它范数成立..0limlimAAAAkkkk上页下页定理2limAk=0的充分必要条件是证明对任一种矩阵范数的从属范数有)7.1(.,0limnkkRxxA若limAk=0,则lim||Ak||=0,故对一切xRn有lim||Akx||=0.故(1.7)式成立..xAxAkk反之，若(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)=(2)用反证法，假定B有一个特征值,满足||1,则存在x0,使Bx=x,由此可得||Bkx||=||k||x||,当k→时{Bkx}不收敛于零向量.由定理2可知(1)不成立，从而知||1，即(2)成立.(1)limBk=0;(2)(B)1;(3)至少存在一种从属的矩阵范数||·||，使||B||1.(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，||·||为任一种矩阵范数，则即kN时有)8.1().(lim1BBkkk证明由第5章定理18，对一切k有.)()(11kkkkBBB另一方面对任意0，记.)(1BBB显然有(B)1.由定理3有limBk=0，所以存在正整数N=N()，使当kN时，.1)(kkkBBB.)()(1BBBkk由的任意性即得定理结论.上页下页6.1.3迭代法及其收敛性其中，A=(aij)∈Rn×n为非奇异矩阵，下面研究如何建立解Ax=b的迭代法.设有线性方程组Ax=b，其中，M为可选择的非奇异矩阵，且使Mx=d容易求解，一般选择A的某种近似，称M为分裂矩阵.将A分裂为A=M-N.(1.9)上页下页于是，求解Ax=b转化为求解Mx=Nx+b，即求解.11bMNxMxbAx求解从而可构造一阶定常迭代法：)11.1(),,,1,0()()()1()0(kfBxxxkk，初始向量其中B=M-1N=M-1(M-A)=I-M-1A，f=M-1b.称B=I-M-1A为迭代法的迭代矩阵，选取M矩阵，就得到解Ax=b的各种迭代法.下面给出迭代法(1.11)式收敛的充分必要条件.也就是求解线性方程组x=Bx+f.(1.10)上页下页定理5(一阶定常迭代法的基本定理)给定线性方程组(1.10)及一阶定常迭代法(1.11)式，对任意选取初始向量x(0)，迭代法(1.11)式收敛的充分必要条件是矩阵B的谱半径(B)1.由定理2知limBk=0，再由定理3，即得(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→).上页下页例3考察线性方程组(1.2)给出的迭代法(1.4)式的收敛性.解先求迭代矩阵B0的特征值.由特征方程.0)det(412111111441830BI可得.0039772727.0034090909.0)det(30BI解得.3245.01541.0,3245.01541.0,3082.0221ii.13592.0,13082.0221即(B0)1，所以用迭代法(1.4)式解(1.2)是收敛的.上页下页例4考察用迭代法解线性方程组的收敛性，其中x(k+1)=Bx(k)+f.解特征方程为det(I-B)=2-6=0，特征值.55,0320fB,62,1即(B)1，这说明用迭代法解此方程组不收敛.迭代法的基本定理在理论上是重要的，由于(B)||B||，下面利用矩阵B的范数建立判别迭代法收敛的充分条件.上页下页定理6(迭代法收敛的充分条件)设有线性方程组x=Bx+f，A=(aij)∈Rn×n，及一阶定常迭代法x(k+1)=Bx(k)+f.如果有B的某种算子范数||B||=q1，则(1)迭代法收敛，即对任取x(0)有limx(k)=x*，且x*=Bx*+f..)2()0()(xxqxxkk.1)3()1()()(kkkxxqqxx.1)4()0()1()(xxqqxxkk上页下页证明由基本定理知，结论(1)是显然的.(2)显然有关系式x*-x(k+1)=B(x*-x(k))及x(k+1)-x(k)=B(x(k)-x(k-1)).于是有反复利用②即得(2).;)1()()()1(kkkkxxqxx①.)()1(kkxxqxx②(4)反复利用①，则得到(4).(3)考察,)1()()()1()()1()()()1(kkkkkkkxxqxxxxxxxxxx即有.111)1()()()1()(kkkkkxxqqxxqxx上页下页注意，定理6只给出迭代法(1.11)式收敛的充分性，即使条件||B||1对任何常用范数均不成立，迭代序列仍可能收敛.例5迭代法x(k+1)=Bx(k)+f，其中显然||B||=1.1,||B||1=1.2,||B||2=1.043,||B||F=(1.54)1/2,.21,8.03.009.0fB但由于(B)=0.91，故由此迭代法产生的迭代序列{x(k)}是收敛的.上页下页下面考察迭代法(1.11)式的收敛速度.假定迭代法(1.11)式是收敛的,即(B)1,由(k)=Bk(0),(0)=x(0)-x*,得于是.0,)0()0()(kkB.)0()(kkB根据矩阵从