线性方程组的迭代法

1、线性方程组的迭代法,快速、高效地求解线性方程组是数值线性代数研究中的核心问题，也是目前科学计算中的重大研究课题之一。,各种各样的科学和工程问题，往往最终都要归结为求解一个线性方程组。,线性方程组的数值解法有：直接法和迭代法。,直接法：在假定没有舍入误差的情况下，经过有限次运算可以求得方程组的精确解；,迭代法：从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列。,引例：Cramer法则不可行,Cramer法则n20时，计算量太大，现实上不可行Cramer法则数学上很重要，计算上无价值,线性方程组的迭代法,迭代法：从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无

2、穷序列。,迭代解法是目前求解大规模线性方程组的主要方法。,只需存储系数矩阵中的非零元素,运算量不超过O(kn2)，其中k为迭代步数,(1)迭代格式的建立,(3)误差估计和收敛速度,(2)收敛性判断,解线性方程组迭代法的基本思想,迭代格式的建立,Ax=b,k=0,1,2,给定一个初始向量x(0)，可得迭代格式：,若产生的迭代序列x(k)收敛到一个确定的向量x*，则x*就是原方程组的解。,其中G称为迭代矩阵。,Jacobi迭代,k=0,1,2,则可得雅可比(Jacobi)迭代格式:,令A=D+L+U，其中,称为雅可比(Jacobi)迭代矩阵,Jacobi迭代,在计算时，如果用代替，则可能会得到更好

3、的收敛效果。此时的迭代公式为,Jacobi迭代的分量形式：,Gauss-Seidel迭代,写成矩阵形式:,称为GS迭代矩阵,此迭代格式称为高斯-塞德尔(Gauss-Seidel)迭代,SOR迭代,称为SOR迭代矩阵,在GS迭代中,解得,低松弛法01；=1Gauss-Seidel迭代；超松弛法12,为了得到更好的收敛效果，可选参数w作与上面右式的加权平均,于是就得到逐次超松弛迭代法,简称SOR迭代,其中w称为松弛因子。收敛的必要条件02。此时,Jacobi、GS和SOR算法,Jacobi算法,GS算法,SOR算法,举例,解：,Jacobi迭代格式,令则迭代得：,举例（续）,GS迭代格式,得,举例

4、（续）,SOR迭代格式,取w=1.1，得,如何确定SOR迭代中的最优松弛因子是一件很困难的事。,矩阵分裂法,Jacobi迭代,GS迭代,SOR迭代,A=M-N,M=D,N=MA=-(L+U),M=L+D,N=-U,5.2向量和矩阵的范数,问题：,如何判断向量序列是否收敛？,迭代格式产生的迭代序列是否收敛？,收敛与否和迭代矩阵G或向量f有没有联系？,迭代序列如果收敛，是否收敛于Ax=b的解向量？,向量范数,定义,1)|x|0，且等号当且仅当x=0时成立；(正定性),2)对任意实数，有|x|x|；(齐次性),3)对任意x和y，有|x+y|x|+|y|；(三角不等式),则称|x|为向量x的范数。,常

5、见向量范数：,对xRn，若存在对应的非负实数|x|，满足,5.2向量和矩阵的范数,例子：设求它的三种常用的向量范数。,向量范数,矩阵范数,定义,对ARmn，若存在对应的非负实数|A|，满足,1)|A|0，且等号当且仅当A=0时成立；(正定性),2)对任意实数，有|A|A|；(齐次性),3)对任意A和B，有|A+B|A|+|B|；(三角不等式),则称|A|为矩阵A的范数。,4)对任意A和B，有|AB|A|B|；(相容性),定义,设A是n阶方阵，则称,为A的谱半径，其中i为A的特征值。,常见的矩阵范数,矩阵范数：（诱导范数）,由向量范数|p导出关于矩阵ARnn的p范数:,典型代表：,(1-范数，列

6、范数),(-范数，行范数),(2-范数，谱范数),例子：设求它的行范数、列范数。,矩阵范数,相容范数,我们只考虑：(1)A为方阵；(2)具有相容性的范数。,算子范数总是相容的：,相容性：对任意A和B，有|AB|A|B|,向量序列的收敛,Rn上的所有向量范数都是等价的。,迭代收敛的判断条件,预备定理：若方阵G的某种范数则矩阵I-G为非奇异矩阵。,定理4(充分条件)：若方阵G的某种范数则迭代法对于任意初值x(0)都收敛于方程组的唯一解x*.,5.3迭代法过程的收敛性,定理(全局收敛性)设迭代矩阵G的某种范数|G|1，则x=Gx+f存在唯一解，且对任意初值,迭代序列x(k)=Gx(k-1)+f收敛于

7、x*，进一步有误差估计式,证明略,后验估计,先验估计,直接从Ax=b判断,定理若A按行严格对角占优(),则解Ax=b的Jacobi迭代和Gauss-Seidel迭代均收敛。,证明：由A严格对角占优，则无穷大范数|G|1Jacobi迭代(直接证|G|11)Gauss-Seidel迭代,令y=Gx，则y=-D-1(Ly+Ux)先证对任意|x|1=1,|y|11再证存在某|x|1=1,使|G|1=|y|1,定理若A按行严格对角占优(),则解的Jacobi迭代和Gauss-Seidel迭代均收敛。,由A按行严格对角占优,再由定理3.4知迭代收敛。,令，则有,即,写出分量形式有,证:令雅可比迭代公式的迭代矩阵为,再考察高斯-赛德尔迭代公式的迭代矩阵,设,而,由上式得,得,据定理4知G-S迭代法收敛。,取,记,充分必要条件,谱半径(G)：G的特征值模的最大值定理：迭代x(k)=Gx(k-1)+f对任意初值收敛(G)1.定理：若A为对称正定矩阵：Jacobi迭代法收敛的充分必要条件是2D-A为正定矩阵；SOR迭代收敛的充分必要条件是02。,三种方法比较,方法一:从系数矩阵A判断,A严格对角占优，则Jacobi迭代和Gauss-Seidel迭代收敛,充分条