研究线性方程组迭代收敛速度.docVIP

研究解线性方程组迭代收敛速度 实验目的 科学研究与生产实践中许多问题都可归结为线性方程组的求解，高效求解线性方程组成为了许多科学与工程计算的核心．迭代法就是用某种极限过程去逼近线性方程组精确解的方法，该方法具有对计算机的存贮单元需求少，程序计算简单，原始系数矩阵在计算过程中不变等优点，是求解大型稀疏矩阵方程组的重要方法。常用的迭代法有Jacobi迭代法、Gauss—seidel迭代法、逐次超松驰法(SOR法)等。 实验摘要 由迭代法平均收敛速度与渐进收敛速度的关系引入近似估计法，即通过对迭代平均收敛速度取对数，然后利用Mathematica软件对其进行拟合，给出拟合函数，最终得到了Jacobi迭代法、Gauss—seidel法的平均收敛速度收敛到渐进收敛速度的近似收敛阶，以及逐次超松驰法(SOR法)的渐进收敛速度，且该法适用于其他迭代法收敛速度的估计。 迭代法原理 Jacobi迭代法(J法) 设方程组，其中，， 为可逆矩阵，可分裂为其中， 从而由得到， 令 , , 由此可构造出迭代公式： 令初始向量，即可得到迭代序列，从而逼近方程组的解 这种方法称为Jacobi迭代法，其中称为Jacobi迭代矩阵。 2. Gauss-Seidel迭代法(GS法) 与Jacobi迭代法类似，将方程组中的系数矩阵分裂为,其中与前面相同。 与Jacobi迭代法所不同的是，Gauss-Seidel迭代法将Jacobi迭代公式中的 改为 从而可写成矩阵形式 ， 若设存在，则 ， 其中， ,， 于是Gauss—Seidel迭代公式的矩阵形式为。 其中，称为式（1）的Gauss—Seidel迭代法的迭代矩阵。 注：由于Gauss-Seidel迭代充分利用了迭代过程的新信息，一般来说，它的迭代效果要比Jacobi迭代好。 3.逐次超松弛方法（SOR法） 根据Gauss-Seidel迭代法的迭代原理，我们将其修改为，即对和加入一个权因子，在这里我们称为迭代公式的松弛系数。 令（Gauss—Seidel迭代法），则 从而 ， 所以 将其写成分量的形式 我们称该公式为基于Gauss—Seidel迭代下的超松弛迭代公式。 注： 关于松弛系数的选取，我们有以下性质： （i）.设方程组，其中，，，则解方程的SOR迭代法收敛的必要条件是为正定的对称矩阵，且，则方程组关于SOR迭代法收敛为正定的对称三对角矩阵，，若，记，则SOR法的最优松弛因子为 且 由松弛系数的性质可知，通常只有当方程组的系数矩阵为正定的对称矩阵时我们才使用SOR法； 当松弛系数时，SOR法记为GS方法； 关于（iii）提到的谱半径定义为： 假设为阶可逆矩阵，是它的个特征值，我们称 为的谱半径。容易证明的谱半径是的所有诱导范数的下确界，即 其中，矩阵的范数如：，， 。 下面我们就来讨论以上方法的迭代收敛速度，首先我们介绍收敛速度快慢的比较方法。 迭代法收敛速度的比较 1.这两种迭代方法收敛性与是否成立有关，且收敛速度与的速度有关。 当时， 趋于零矩阵的速度有赖于的大小。一般说来，越小，则趋于零矩阵的速度越快，反之就越慢。通常，当时，可以用正数的大小作为迭代法渐进收敛速度的度量。这时越大，迭代法的收敛速度愈大。 2.平均收敛速度与渐进收敛速度之间的联系 对于收敛的迭代法，称为平均收敛速度(它与所用的范数以及k有关)；称为渐进收敛速度。可以证明，因此当时假设成立下列渐近关系式 (常数)，为估计平均收敛速度收敛到渐进收敛速度的阶，当充分大时有如下近似形式： 两边取对数得： 此式说明当k比较大时，与有近似的线性关系，而它们的斜率刚好为收敛阶P，这样可以通过当k比较大时作出与 的拟合曲线来估计出P值。 实验举例 例1：考虑五阶方程组 1. 其Jacobi迭代法的迭代矩阵为 渐进收敛速度为： 则迭代平均收敛速度（见表1）以及取对数后作最小二乘拟合图像（见图1）如下所示： 表1 1 0-1 2 0-1 3 0-1 4 0-1 5 0-0 6 0-0 7 0-0 8 0-0 图1 即 从而得到收敛阶为 p=0 2. 该方程组的Gauss—Seidel迭代矩阵为：