计算方法 5 解线性方程组的迭代法.ppt

《计算方法 5 解线性方程组的迭代法.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第五章解线性代数方程组的迭代法–适用于求解大型稀疏方程组的解解线性代数方程组：需考虑如下几个问题：1.如何选取初始向量？初始向量任选.2.如何构造迭代序列？3.迭代序列是否收敛？在什么条件下收敛？4.若收敛，收敛速度如何？并给出定量的刻画.5.讨论近似解的误差估计.1.Jacobi迭代法同解构造①②简单迭代法的基本思想:是构造不动点方程，以求得近似根。构造迭代格式此迭代格式称为Jacobi迭代格式（或简单迭代法），称B为Jacobi迭代矩阵.迭代格式的收敛性于是可证明：1.各分量的计算顺序无关。2.迭代格式仅有前后两步有关。3.新的近似解是已知近似解的线性函数。

2、收敛速度的定量刻画根据系数矩阵的特点，给出判断收敛的几个常用条件：1.若A是严格对角占优阵，则Jacobi迭代收敛.2.若A是对称正定阵，2D-A也是对称正定阵，则Jacobi迭代格式收敛.若A是对称正定阵，2D-A是非对称正定阵，则Jacobi迭代格式不收敛.2.Gauss-Seidel迭代法–可看作Jacobi迭代的一种改进构造迭代格式矩阵格式：B=L+U,方程组x=Bx+fx=Lx+Ux+b此迭代格式称为Gauss-Seidel迭代格式。注意到，这表明：Gauss-Seidel迭代实际上是Jacobi迭代!上面的迭代矩阵被称为G-S迭代法的迭代矩阵.迭代格

3、式的收敛性若方程组为：Ax=b.则令A=D-L-U,于是根据系数矩阵的特点，给出判断收敛的几个常用条件：1.若A是严格对角占优阵，则G-S迭代收敛.2.若A是对称正定阵，则G-S迭代格式收敛.3.SOR迭代法–解大型稀疏矩阵方程组的有效方法解得构造迭代格式迭代格式的收敛性根据系数矩阵的特点，给出判断收敛的几个常用条件：1.若A是对称正定阵，则SOR迭代格式对是收敛的.2.若A是严格对角占优的，且松弛因子，则SOR收敛.4.最速下降法与共轭梯度法–解对称正定线性方程组的方法最速下降法与共轭梯度法，是求最优化问题的重要方法.在此，使用它们解线性方程组。途径：求解线性

4、方程组问题等价地转化成求极值问题！和之间的关系求极小值的数值方法：如此不断地修正下去初始点两个关键步骤：1.如何选取搜索方向P？2.如何确定搜索步长λ？1)最速下降法或梯度法最速下降法：每步选择的搜索方向P都是F(x)的负梯度方向！=如何选择搜索方向？r几个常用的梯度公式1.f(x)=C（常数）,则▽f(x)=0。2.f(x)=bTx,则▽f(x)=b；3.▽(xTx)=2x;4.若A是实对称方阵,则有▽(xTAx)=2Ax；1847年,Cauchy提出最速下降法的迭代公式推导：利用极值的必要条件，我们有于是有前后两步迭代的搜索方向是相互正交的!重复上述过程，

5、可得最速下降法计算公式：梯度法算法步骤：等高线最速下降法具有算法简单，对初始点没有特别要求，具有全局收敛性，但收敛速度不理想（其收敛速度是线性的）.注：最速下降方向反映了F(x)在点xk处的局部性质，即它只是F(x)局部下降最快的方向.但从整体上看下降路径却经历了不少弯路（折线），因此使收敛速度大大减慢！当接近最优解时，收敛很慢！2)共轭梯度法如何选择搜索方向？A-共轭是正交的推广.共轭梯度法的迭代公式推导：以共轭方向作为搜索方向1952年,Hesteness和Stiefel为了解线性方程组而提出的利用极值的必要条件，可得因为每一个共轭方向都依赖于迭代点处的负梯

6、度，故称之为共轭梯度法.等值线当接近最优解时，收敛很慢！图示：共轭梯度法的搜索方向克服了最速下降法的锯齿现象!共轭梯度法算法步骤：1.假设在计算过程中没有误差，则至多用n步就能得到方程组的准确解，即具有二次终止性．2.克服了最速下降法的锯齿现象，一种有效的算法.3.算法简单，易于编程，无需计算二阶导数，存储空间小等优点．优点：