线性方程组的迭代方法.ppt

6.2基本迭代法，6 . 1 . 2雅可比迭代法和高斯-赛德尔迭代法，6.2.1迭代公式的构造，第6章线性方程的迭代解法，教学目的1。掌握求解大型线性方程组的雅可比迭代法、G-S迭代法及其收敛准则；2.掌握SOR迭代法和收敛的必要条件(02)；3.理解三种迭代方法之间的改进关系，掌握思维方法；4.理解迭代法的基本定理。教学的重点和难点是三种迭代方法和收敛判断方法。难点在于证明迭代法的基本定理和三种迭代法的收敛定理。迭代方法是一种迭代公式，它被连续地应用于逐步逼近方程的精度。迭代法的优点是：(1)计算量小，近似解精度高。(1)如何构造求解的有效迭代方法？直接法是求解低阶稠密线性方程并求解(真解)的方法。它适用于求解大型稀疏线性方程。用差分法或有限元法求解偏微分方程边值问题时得到的方程。电工技术中的网络问题；大的稀疏线性方程，(2)占用较少的存储单元。(3)设计程序简单(适合计算机计算)。(2)什么是收敛和收敛速度？第六章线性方程的迭代求解。迭代方法通常可以利用计算机内存和操作中大量的零元素。6.2.1。迭代法的基本思想，迭代法的基本思想是将线性方程组Ax=b(6.2.1)转化为便于迭代的等价方程组。对于任意一组初值，根据一些计算规则，不断修正得到的值，最终得到满足精度要求的方程组的近似解。如果它是非奇异的，那么线性方程组就有唯一的解。经过变换，构造了一个具有相同解的等价方程组。将上述公式改写为一步稳定迭代公式，选择初始向量，反复连续使用迭代公式逐步逼近方程组的精确解，直至满足精度要求。这种方法称为一步稳定迭代法(B和F与K无关)。如果有一个极限，迭代方法被称为是收敛的，否则就是发散的。当收敛发生时，在迭代公式中，则是方程组的解。为了讨论收敛性，引入了误差向量：例6.1，Ax=b首先被转换成等价方程，迭代公式：选择初始向量，通过10次迭代获得解：对于给定的方程，可以构造各种迭代公式，但不是所有的迭代公式都收敛。例6.2使用迭代法求解线性方程，求解并构造方程的等价方程，并在此基础上建立迭代公式。根据计算，迭代解离的精确解越来越远，迭代不收敛。6.1.2雅可比迭代法1雅可比迭代法算法构造。例6.3使用雅可比迭代法求解方程。解：从三个方程中分离和，建立迭代公式，取初始向量进行迭代。可以逐步获得一系列近似解：(k=1，2，)直到获得的近似解能够预先达到要求的精度，迭代过程结束，最终获得的近似解作为线性方程的解。当迭代次数达到第10次时，计算结果表明迭代过程收敛于方程的精确解x*=(3，2，1)T。复习一般方程，写出n元线性方程，如果，分离变量，则建立迭代公式，上述公式称为求解方程的雅可比迭代公式。雅可比迭代法的矩阵表明方程组的系数矩阵A是非奇异的，主对角线元素可以分成A，表示为A=-L D-U、也就是说，因为得到了一个迭代公式，所以(k=0，1，2.)被称为雅可比迭代公式，BJ被称为雅可比迭代矩阵，在例5.3中，它相当于雅可比迭代(3)存储和计算需要两组工作单元。前一个例子6.3是雅可比方法，这里不再给出更多的例子。algorithm : jacobiioperativemethodsolvenaninitialapproximation。输入： thenumberofequipmentandunknown；中心；)；公差公差公差。maximumnumberofiterationsMmax。output : approximatesolutionx或oramessageoffailure。步骤1设置=1；step2while(kmmax)dosteps3-6step3fori=1,nset；/* computexk */step 4 IftHenotput(X)；停止；/*成功*/步骤5Fori=1，nSetX0=X；/*更新x0 */步骤6设置；步骤7输出(超过最大数值迭代)；停下。/*不成功*/，Whatifaii=0？在迭代过程中，a的元素不变，所以a可以预先调整以使aii0，否则a是不可逆的。必须等到X(k)完全计算出来之后，才能计算X(k 1)，所以需要两组向量存储。有点浪费，不是吗？6.2.3高斯-塞德尔迭代法(G-S)，(I=1，2，NK=0，1，2，)，1高斯-塞德尔迭代法的基本思想在雅可比迭代法中，每次迭代只使用前一个迭代值。如果当前最新的迭代值在每次迭代中被充分利用，即使用新的组件代替旧的组件，则获得高斯-塞德尔迭代方法。迭代格式如下：只能存储一组向量。例如6.4，高斯赛德尔迭代方案用于求解方程。确切的要求是=0.005。高斯赛德尔迭代格式取初始迭代向量，迭代结果为：x * 2。高斯-塞德尔迭代法的矩阵表示将A分解为A=D-L-U，这相当于(D-L-U) x=B。因此，高斯-塞德尔迭代法的过程是，因为，高斯-塞德尔迭代法的形式是：因此，得到解的G-S迭代法如下：(6.2.3)，其中2)G-S称为G-S迭代法的迭代矩阵。从以上分析可以看出，G-S迭代法是一种改进的J迭代法。也就是说，在J方法中，在计算时已经计算了分量，因此可以认为：(1)从(6.2.10)可以看出，在计算I分量时，利用了已经计算的最新的G-S方法的优点；(2)G-S迭代法主要是每次迭代计算一次矩阵乘法向量，计算量小；(3)当J-迭代和G-S迭代都收敛时，G-S迭代的收敛速度快。G-S迭代法可以看作是对J迭代法的一种修正或改进。用G-S迭代法求解只需要一组工作单元，用于保存或组成。因此，组件的计算可以被冲掉，所以利息、G-S迭代存储较少。解采用J法计算，根据(6.2.8)，在情况6.6下，下列方程采用雅可比迭代法和G-S迭代法求解，精确解为，(1)迭代公式：其中，计算结果见表6-1。表6-1，其中有(2)G-S迭代公式，从这个例子可以看出，用G-S迭代方法求解这个方程组比用雅可比方法求解这个Ax=b收敛得更快(即，初始矢量相同，精度相同，所需迭代次数较少)。只有当A满足一定条件时，这个结论才是正确的。对于某些方程，用J迭代法收敛，用G-S迭代法发散。例如，李259页练习6中的2(b)。注：计算结果见：表6-2。雅可比迭代法和高斯-塞德尔迭代法的分量形式用于计算和编程，它们的矩阵形式用于理论分析，如迭代序列是否收敛。内容摘要：雅可比迭代法、高斯-塞德尔迭代法、矩阵形式、分量形式、矩阵形式、分量形式、6.4过松弛迭代法(SOR法)使用迭代法的困难在于很难估计其计算量。有时，虽然迭代过程收敛，但由于收敛速度慢，计算量变大，失去使用价值。因此，加速迭代过程具有重要意义。成功超松弛迭代法(简称SOR法)可视为带参数的高斯-塞德尔迭代法，本质上是高斯-塞德尔迭代法的加速方法。1、过松弛迭代法的基本思想过松弛迭代法的目的是改善conv(2)加权平均值取和，即组合表示为：其中系数称为松弛因子，当=1时，为高斯-塞德尔迭代法。为了确保迭代过程的收敛性，需要02。当01时，低松弛法；当1为2时，称为超松弛法。然而，它通常被称为过度松弛法(SOR)。2过松弛迭代方法的矩阵表明线性方程组的系数矩阵A是非奇异的，并且主对角元素分裂成A=D-L-U，那么过松弛迭代公式被表示为，或者，因此，很明显，对于任何值，(D L)是非奇异的，(由于假设)，那么过松弛迭代公式是，例如* *，SOR方法被用于求解线性方程组，取=1.46，这要求，求解：SOR迭代公式，k=0，1.初始值，方程的精确解只需要20次迭代就能达到精度要求。如果=1(即高斯-塞德尔迭代法)，并且采用相同的初始值，则需要110次迭代才能达到相同的精度。我们知道，对于给定的方程，6.3迭代法的收敛性可以构造为简单迭代公式、雅可比迭代公式、高斯-塞德尔迭代公式和超松弛迭代公式，但它不一定收敛。现在分析它们的趋同性。由等价变换构造的等价方程在什么条件下迭代序列收敛？如果有一个极限，那么迭代法就是收敛的，否则就是发散的。在迭代公式中，则是方程组的解。实际上，下述定理可以用B的约当标准型来证明。定理1收敛于任何初始向量迭代公式的充要条件是迭代矩阵B的谱半径。从这个定理可以看出，雅可比迭代法、高斯-塞德尔迭代法或超松弛迭代法收敛的是它们的迭代矩阵的谱半径。有时很难测试迭代方法是否收敛。然而，有些矩阵范数可以用B的元素来表示，所以用它们作为收敛的充分条件是很方便的。定理3(迭代法收敛的充分条件)如果使用迭代矩阵B的范数，迭代公式收敛，并且存在误差估计公式和误差估计公式，并且证明：矩阵的谱半径不超过已知的矩阵的任何范数。因此，迭代公式根据定理2收敛。此外，因为引理(引理-引理)为0，引理-引理是一个非奇异矩阵，所以X=引理F有唯一的解，也就是说，与迭代过程相比。取范数有两个方面，它是由迭代格式决定的，有两个方面，取范数，代入上述公式，得到，证明，并从定理中知道。那时，它的值越小，迭代收敛越快。在程序设计中，两个相邻的迭代(是给定的精度要求)通常用作控制迭代结束的条件。例如6.8，线性方程是已知的，并且当雅可比迭代和G-S迭代用于求解时，研究收敛解： (1)雅可比迭代矩阵。因此，雅可比迭代收敛，(2)系数矩阵分解，高斯-塞德尔迭代收敛。定理4严格对角占优线性方程的雅可比迭代公式和高斯-赛德尔迭代公式收敛。定理5的系数矩阵A是对称正定矩阵，雅可比迭代公式收敛的充要条件是2D-A也是对称正定矩阵，SQR方法收敛的充要条件是02。在定理6中，假设A是不可约对角占优矩阵，则雅可比迭代法和G-S迭代法收敛。在定理7中，假设A是N阶正定矩阵，则G-S迭代法收敛。以下是一些常见的结论和注意事项。(2)雅可比迭代法和高斯-塞德尔迭代法的收敛性不一定相关：即雅可比迭代法在高斯-塞德尔迭代法收敛时可能不收敛；当雅可比方法收敛时，高斯-塞德尔方法可能不收敛。(1)雅可比迭代法和高斯-塞德尔迭代法有不同的迭代矩阵：BJ=D-1(L-U)，BG-S=(D-L)-1U。例如，雅可比迭代法不收敛，但高斯-赛德尔法收敛。雅可比迭代迭代法是一种逐次逼近法，即对于任何给定的初始近似解向量，按照一定的方法逐步生成近似解序列，从而使解序列的极限是方程组的解。注意，当迭代方法用于求解方程时，其迭代矩阵B和迭代向量F在整个计算过程中保持不变。迭代法有一个循环计算公式。该方法简单，程序实现方便。它的优点是可以充分利用系数的稀疏性，适用于求解具有大稀疏系数矩阵的方程。迭代方法没有误差累积问题。使用迭代法的关键问题是它的收敛性和收敛速度，收敛性与迭代初值的选择无关，在求根方面优于一般的非线性方程。在实际计算中，很难判断迭代格式的收敛性。由于求迭代的谱半径需要特征值，当矩阵阶数较大时，特征值不易找到。通常，矩阵的任何范数小于1或对角占优来判断收敛性。有时在计算时可以观察到收敛性。如何加快迭代过程的收敛速度是一个非常重要的问题。SOR法在实践中应用较多，适当的松弛因子的选择取决于实践经验。对于不同的实际问题，我们应该采用适当的数值算法。补充1考察了用雅可比迭代法和高斯-塞德尔迭代法求解线性方程组Ax=b的收敛性，其中解：首先计算迭代矩阵并求出特征值，雅可比矩阵，(BJ)=01 当用高斯-塞德尔迭代法求解时，迭代过程发散，高斯-塞德尔迭代矩阵求出特征值，Ax=b系数矩阵严格对角占优，所以高斯-塞德尔迭代收敛，补充例2提供了迭代格式sub x (k1)=bx (k) g (k=0，1，2.如果a和b的特征值都是正数，试着证明迭代格式收敛。分析：根据A、B的特征值与