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

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

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

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

4、方程组的方法最速下降法与共轭梯度法，是求最优化问题的重要方法. 在此，使用它们解线性方程组。 途径：求解线性方程组问题等价地转化成求极值问题！和之间的关系求极小值的数值方法：如此不断地修正下去初始点两个关键步骤：1. 如何选取搜索方向P？ 2. 如何确定搜索步长？第9页，共18页。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、第10页，共18页。最速下降法的迭代公式推导：利用极值的必要条件，我们有于是有前后两步迭代的搜索方向是相互正交的!第11页，共18页。重复上述过程，可得最速下降法计算公式：梯度法算法步骤：第12页，共18页。等高线最速下降法具有算法简单，对初始点没有特别要求，具有全局收敛性，但收敛速度不理想（其收敛速度是线性的）.注：最速下降方向反映了F(x)在点xk处的局部性质，即它只是F(x)局部下降最快的方向. 但从整体上看下降路径却经历了不少弯路（折线），因此使收敛速度大大减慢！当接近最优解时，收敛很慢！第13页，共18页。2) 共轭梯度法如何选择搜索方向？A-共轭是正交的推广.共轭梯度法的迭代公式推导：以共轭方向作为搜索方向1952年,Hesteness和Stiefel为了解线性方程组而提出的第14页，共18页。利用极值的必要条件，可得因为每一个共轭方向都依赖于迭代点处的负梯度，故称之为共轭梯度法.第15页，共18页。等值线当接近最优解时，收敛很慢！图示：共轭梯度法的搜索方向克服了最速下降法的锯齿现象!第16页，共18页。共轭梯度法算法步骤：第17页，共18页。1. 假设在计算过程中没有误差，则至多用n