第五章 线性方程组的迭代法53.ppt

第五章线性方程组的迭代法快速、高效地求解线性方程组是数值线性代数研究中的核心问题，也是目前科学计算中的重大研究课题之一。各种各样的科学和工程问题，往往最终都要归结为求解一个线性方程组。线性方程组的数值解法有：直接法和迭代法。直接法：在假定没有舍入误差的情况下，经过有限次运算可以求得方程组的精确解；迭代法：从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列。引例：Cramer法则不可行Cramer法则n20时，计算量太大，现实上不可行Cramer法则数学上很重要，计算上无价值线性方程组的迭代法迭代法：从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列。迭代解法是目前求解大规模线性方程组的主要方法。只需存储系数矩阵中的非零元素运算量不超过O(kn2)，其中k为迭代步数(1)迭代格式的建立(3)误差估计和收敛速度(2)收敛性判断解线性方程组迭代法的基本思想迭代格式的建立Ax=bk=0,1,2,…给定一个初始向量x(0)，可得迭代格式：若产生的迭代序列{x(k)}收敛到一个确定的向量x*，则x*就是原方程组的解。其中G称为迭代矩阵。Jacobi迭代k=0,1,2,…则可得雅可比(Jacobi)迭代格式:Jacobi迭代Gauss-Seidel迭代此迭代格式称为高斯-塞德尔(Gauss-Seidel)迭代SOR迭代低松弛法01；=1Gauss-Seidel迭代；超松弛法12Jacobi、GS和SOR算法Jacobi算法GS算法SOR算法举例解：举例（续）得举例（续）取w=1.1，得如何确定SOR迭代中的最优松弛因子是一件很困难的事。矩阵分裂法A=M-NM=D,N=M–A=-(L+U)M=L+D,N=-U5.2向量和矩阵的范数问题：如何判断向量序列是否收敛？迭代格式产生的迭代序列是否收敛？收敛与否和迭代矩阵G或向量f有没有联系？迭代序列如果收敛，是否收敛于Ax=b的解向量？向量范数定义1)||x||0，且等号当且仅当x=0时成立；(正定性)2)对任意实数，有||x||＝||·||x||；(齐次性)3)对任意x和y，有||x+y||||x||+||y||；(三角不等式)则称||x||为向量x的范数。常见向量范数：对xRn，若存在对应的非负实数||x||，满足5.2向量和矩阵的范数例子：设求它的三种常用的向量范数。向量范数矩阵范数定义对ARmn，若存在对应的非负实数||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导出关于矩阵ARnn的p范数:典型代表：(1-范数，列范数)(-范数，行范数)(2-范数，谱范数)例子：设求它的行范数、列范数。矩阵范数相容范数我们只考虑：(1)A为方阵；(2)具有相容性的范数。算子范数总是相容的：相容性：对任意A和B，有||AB||||A||||B||向量序列的收敛Rn上的所有向量范数都是等价的。迭代收敛的判断条件预备定理：若方阵G的某种范数则矩阵I-G为非奇异矩阵。5.3迭代法过程的收敛性定理(全局收敛性)设迭代矩阵G的某种范数||G||1，则x=Gx+f存在唯一解，且对任意初值,迭代序列x(k)=Gx(k-1)+f收敛于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迭代收敛的充分必要条件是02。三种方法比较方法一:从系数矩阵A判断,A严格对角占优，