《第6章解线性方程组的迭代法》由会员分享，可在线阅读，更多相关《第6章解线性方程组的迭代法（79页珍藏版）》请在金锄头文库上搜索。
1、上页下页第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 求解方程组记为Ax=b，其
2、中此方程组的精确解是x*=(3,2,1)T. 现将(1.2)改写为上页下页或写为x=B0x+f，其中上页下页我们任取初始值，例如取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)，反复利用这个计算程序，得到一向量序列和一般的计 算公式(迭代公式)上页下页简写为 x(k+1)=B0x(k) +f，其中k表示迭代次数(k=0,1,2,).迭代到第10次有上页下页从此例看出，由迭代法产生
3、的向量序列x(k)逐步 逼近方程组的精确解是x*=(3,2,1)T. 即有 对于任何一个方程组x=Bx+f(由Ax=b变形得到的 等价方程组)，由迭代法产生的向量序列x(k)是否一定 逐步逼近方程组的解x*呢？回答是不一定. 请同学们考虑用迭代法解下述方程组但但 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 ,
4、 用公式(1.6)逐步代入求近似解的方法称为迭代法(或称为一阶定常迭代法，这里B与k无关). B称为迭代矩阵.(2) 如果limx(k) (k)存在(记为x*), 称此迭代法收敛, 显然x*就是方程组的解, 否则称此迭代法发散.上页下页由上述讨论，需要研究x(k)的收敛性. 引进误差向量由(1.6)减去(1.5)式，得(k+1)=B(k) (k=0,1,2,)，递推得要考察x(k)的收敛性，就要研究B在什么条件下有lim(k)=0 (k)，亦即要研究B满足什么条件时有Bk0(零矩阵) (k) . 上页下页6.1.2 向量序列与矩阵序列的极限定义2 设向量序列x(k)Rn, x(k)= (x1(
5、k),xn(k)T, 如果存在x= (x1, x2, , xn)TRn，使则称向量序列x(k)收敛于x ，记作显然，其中为任一向量范数.上页下页定义3 设矩阵序列Ak=aij(k)Rnn及A=aijRnn, 如果n2个数列极限存在，且有则称矩阵序列Ak收敛于A ，记作例2 设有矩阵序列且设| |(2) 用反证法，假定B有一个特征值, 满足|1,则存在x0,使Bx=x,由此可得|Bkx|= |k|x|,当k时Bkx不收敛于零向量. 由定理2可知 (1)不成立，从而知| |(3) 根据第5章定理18，对任意 0，存在一 种从属范数| ，使|B|(B)+，由(2)有(B)0，可使|B|(1) 由(3
6、) 给出的矩阵范数|B|N 时有证明 由第5章定理18，对一切k有另一方面对任意 0，记 显然有(B)N 时，由的任意性即得定理结论.上页下页6.1.3 迭代法及其收敛性其中，A=(aij)Rnn为非奇异矩阵，下面研究如何建 立解Ax=b的迭代法.设有线性方程组Ax=b，其中，M为可选择的非奇异矩阵，且使Mx=d容易求 解，一般选择A的某种近似，称M为分裂矩阵.将A分裂为A=M-N. (1.9) 上页下页于是，求解Ax=b转化为求解Mx=Nx+b ，即求解从而可构造一阶定常迭代法：其中 B=M-1N=M-1(M-A)=I-M-1A ， f=M-1b. 称 B=I-M-1A为迭代法的迭代矩阵，选
7、取M矩阵，就得 到解Ax=b的各种迭代法.下面给出迭代法(1.11)式收敛的充分必要条件.也就是求解线性方程组x=Bx+f. (1.10) 上页下页定理5(一阶定常迭代法的基本定理) 给定线性 方程组(1.10)及一阶定常迭代法(1.11)式，对任意选取 初始向量x(0)，迭代法(1.11)式收敛的充分必要条件是 矩阵B的谱半径(B) 设对任意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)式 的收敛
8、性.解 先求迭代矩阵B0的特征值. 由特征方程可得解得即(B0)1，这说明用迭代法解此方程组不收敛.迭代法的基本定理在理论上是重要的，由于 (B)|B|，下面利用矩阵B的范数建立判别迭代法收 敛的充分条件.上页下页定理6(迭代法收敛的充分条件) 设有线性方程组x=Bx+f， A=(aij)Rnn， 及一阶定常迭代法x(k+1)=Bx(k)+f. 如果有B的某种算子范数|B|=q0, 则(1) 解线性方程组Ax=b的Jacobi迭代法收敛的充 分条件是A及2D-A均为正定矩阵, 其中D=(a11,ann).(2) 解线性方程组Ax=b的Gauss-Seidel 迭代法收 敛的充分条件是A正定.如
9、果线性方程组系数矩阵A对称正定，则有以下 的收敛定理.定理证明可见文献2，其中第(2)部分为下面定 理12的一部分. 定理表明若A对称正定，则高斯-塞 德尔法一定收敛，但雅可比法不一定收敛.上页下页我们这里给出(2)的证明. 证 因为A对称，则A=D-L-LT，G=(D-L)-1LT，设 为迭代矩阵G =(D-L)-1LT的特征值，y为G 的对应的 特征(复)向量，即有(D-L)-1LTy=y，LTy=(D-L)y，则内积 (LTy, y)=(D-L)y, y).从而解得因为A正定，所以D也正定，故记(Dy, y)=0.上页下页所以|1，雅可比不收敛，此时2D-A不是正定的. 对雅可比法迭代矩
10、阵当(J)=|2a|0为可选择的松弛因子.于是, 由(1.11)可构造一个迭代法, 其迭代矩阵为上页下页解Ax=b的SOR方法为.其中下面给出解Ax=b的SOR方法的分量计算公式. 记由(3.1)式可得或上页下页由此，得到解Ax=b的SOR方法的计算公式或上页下页(1) 显然，当=1时即为GaussSeidel 迭代法.(2) SOR方法每迭代一次主要运算量是计算一次 矩阵与向量的乘法.(3) 当1时，称为超松弛法；当0. (3.7)令 -(Ly, y)=a+ib，则由复向量内积的性质有上页下页当02时，有(分子减分母)即L的任一特征值满足|1, 故SOR迭代法收敛.上页下页定理13 设有方程
11、组 Ax=b，如果：(1) A为严格对角占优矩阵(或A为弱对角占优不可 约矩阵);(2) 01.则解方程组 Ax=b的SOR迭代法收敛. (不证明)SOR迭代法的收敛速度与松弛因子有关，例9中 也看到不同的迭代次数差别.对于SOR迭代法希望选择松弛因子使迭代过程 (3.1)式收敛较快，在理论上即确定opt使上页下页对某些特殊类型的矩阵，建立了SOR方法最佳松 弛因子理论. 例如，对所谓具有“性质A”等条件的线性方程组建立了最佳松弛因子公式其中(J) 为解 Ax=b 的雅可比迭代法的迭代矩阵的谱半径.由于 6.3.3 块迭代法 及 6.4 共轭梯度法 是解线性方程组的应用，大家自学.评 注 见书p208页.
