第七章线性方程组的解法课件.ppt
2023/4/3,1,1 迭代法的一般形式及其收敛性,下面考虑,事实上，令，则,设,(1),给定初值x(0)，可以构造序列,迭代格式,(2),2023/4/3,2,若,并且，,(与初值x(0)的选取无关!),所以，,(3),定理1,2023/4/3,3,定义1 迭代法（2）的平均收敛速度定义为。,由（3）式可得,引理 设ARnn，为任一矩阵范数，则,注：平均收敛速度与范数和迭代次数有关，计算不便！,定义2 迭代法（2）的渐近收敛速度定义为,2023/4/3,4,定理2,若，则,(1)方程组(1)的解x*存在并且唯一；,(2)对迭代格式(2)有,并且,下面给出迭代格式(2)收敛的一个充分条件及误差估计，,证明：,(1),非奇异,2023/4/3,5,(2),下证误差估计式，,由迭代公式(3),得证！,注：,可作为迭代是否停止的判断条件！,得证！#,即 迭代格式收敛。,2023/4/3,6,2 线性代数方程组的常用迭代法,迭代矩阵G的构造原则：,充分利用矩阵的稀疏性，使运算量和存贮量尽量少，办法就是使迭代矩阵G与原矩阵A有相同的稀疏结构。,具体构造方法:,令,其中,2023/4/3,7,1、Jacobi 迭代算法,从而可得Jacobi 迭代算法：,算法的分量形式为(具有并行性)：,若D非奇异，,Jacobi迭代矩阵,2023/4/3,8,2、Gauss-Seidel 迭代算法,从而可得Gauss-Seidel迭代算法：,算法的分量形式为(只能逐个元素进行计算)：,也可写成如下形式：,易于编程实现,G-S迭代矩阵,2023/4/3,9,迭代算法的收敛性：,(1),Jacobi迭代算法收敛,(2),若A按行（列）严格对角占优，则Jacobi迭代和Gauss-Seidel迭代收敛；#,Jacobi迭代收敛；,Gauss-Seidel迭代收敛；,(3),(4),若A为正定矩阵，则Gauss-Seidel迭代收敛。#,两种方法都存在收敛性问题，但两者的收敛性没有必然联系！有例子表明：Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时，Gauss-Seidel法也可能不收敛。,注:,G-S迭代算法收敛,2023/4/3,10,算法描述:,Jacobi迭代算法：,给定迭代初始向量x(0)，置迭代次数k=0，精度要求 和最大迭代次数N；,计算，k=k+1；,(1),(2),若，则停止计算（x(1)作为方程的解）；,(3),若 k=N，则停止计算（输出某些信息），否则x(0)=x(1)，转(1)；,注：,将(1)中的迭代公式换作,即为G-S迭代的算法描述！,1）,2）,通常取向量的无穷范数！,2023/4/3,11,3 超松弛(SOR)迭代算法,设已得到,利用松弛技术对由高斯-赛德尔迭代进行加速：,注：=1 时，即为Gauss-Seidel迭代算法。,SOR算法的分量形式(只能逐个元素进行计算)：,2023/4/3,12,注：,若令,则可以得到矩阵表示形式：,其中,2023/4/3,13,SOR迭代算法的收敛性：,（5）若A为正定矩阵，则当02时，SOR迭代算法收敛；#,（4）若A为严格对角占优阵，则当01时，SOR迭代算法收敛；#,（2）SOR迭代收敛的必要条件02#,注：,松弛因子的选择通常靠经验或用试算的方法来确定！,2023/4/3,14,4 解线性代数方程组的共轭梯度法,我们知道二次函数,当A是对称正定矩阵时，有唯一的极小值点x*。,由多元函数取得极值的必要条件，得,可以证明,即解对称正定矩阵方程组的问题等价于求二次函数极小值的问题。,2023/4/3,15,如何寻找 的极小点呢？,从某点x(0)出发，逐步产生一串点：,以“最快”的速度，下降到 的极小值。,基本思想就是下降法：,2023/4/3,16,下降法的算法描述：,假设已经求得x(k)，考虑如何确定x(k+1)，,根据下降方向的选择不同，我们有不同的下降算法！,下面主要介绍最速下降法和共轭梯度法。,2023/4/3,17,4.1 最速下降法,我们知道，函数的负梯度方向是函数值下降最快的方向。,取,的下降算法称为最速下降算法。,2023/4/3,18,算法描述如下：,注：,r(k+1)和r(k)正交!这是因为,2023/4/3,19,收敛定理：,其中,1 该算法简单易行，可充分利用A的稀疏性等特点，但当A的最大特征值远远大于最小特征值时收敛速度变得非常慢，以至于完全不适用。,注：,2 最速下降法并非最速！,2023/4/3,20,4.2 共轭梯度(CG)算法,有比负梯度方向更好的下降方向吗？,设x(k)是沿下降方向p(k-1)求得的，且x(k)的最速下降方向为r(k)=b-Ax(k)。,下面确定x(k)的下降方向p(k)，使之满足：,从而由极小值问题：,可以确定x(k+1)。,注：A共轭向量是线性无关的!#,2023/4/3,21,由,令,则,具体做法如下：,共轭梯度方向,2023/4/3,22,算法如下：,共轭梯度算法！,确定下降方向,计算极小值点,2023/4/3,23,共轭梯度算法的收敛性：,对于共轭梯度算法，可以证明：,(1),(2),(3),(4),说明，共轭梯度算法至多n步就能得到精确解,注：,1、实际计算中由于误差的影响，r(k)之间的正交性很快就会消失，以 至于有限步内不能得到精确解，所以CG算法实际是一种迭代算法。,2、cond(A)2 越小，CG算法收敛越快！,2023/4/3,24,实用的共轭梯度算法：,在CG算法中，令,可见计算量减少了！,本节可参考：运筹学教材编写组，运筹学，清华大学出版社，1990.(P158第六章),
