线性方程组的迭代算法研究
xxx学校 20 xx-20 xx下学期《数值方法》课程论文 题目：线性方程组的迭代算法研究 学科专业： xxxxxx 指导教师： xxx 学 生： xxx 学 号： xxxx 中国﹒xx 20 xx 年 xx 月 目 录 摘要I 1、问题的提出1 2、算法的基本思路1 3、算法的推导及(思路)步骤2 3.1、Yacobi迭代法2 3.1.1、分量形式推导2 3.1.2、矩阵形式推导2 3.1.3、Jacobi迭代的计算公式2 3.2、G-S迭代法3 3.2.1、分量形式推导3 3.2.2、矩阵形式推导3 3.2.3、G-S迭代法的计算公式4 3.3、SOR逐次超松弛迭代法4 3.3.1、基于Jacobi的SOR逐次超松弛迭代法4 3.3.2、基于G-S的SOR逐次超松弛迭代法5 4、算法分析6 4.1、误差分析6 4.2、收敛性分析7 4.2.1、对角占优定理7 4.2.2、雅可比迭代收敛性7 4.2.3、迭代法基本定理7 4.2.4、迭代法收敛速度7 4.3、稳定性分析7 5、算法实现(算例、代码)8 6、应用举例10 7、知识拓展10 附 录11 线性方程组的迭代算法研究 摘要:对于线性方程组AX=B的求解，主要有直接法与迭代法。对于阶数不太高的线性方程组，用直接法比较方便。但是，随着科学技术的飞速发展，需要求解的问题的规模越来越大，求解效率就显得尤为重要。因此，有必要深入研究Jacobi，Gauss-Seidel等古典迭代法，与此同时，SOR迭代法也为我们在寻求其他快速的迭代法时提供了思路，本文也就这三种迭代法的向量形式与矩阵形式做了些许研究。 关键字：线性方程组； 迭代； 分量； 矩阵 1、问题的提出 对于线性方程组： (1) 其中为非奇异矩阵, 当A为低阶稠密矩阵时,在求解这个线性方程组时，可以使用消元法，包括一般的高斯消元法以及改进的选主元的高斯消元法，其重心都是将线性方程组通过行变换为上三角线性方程组，再通过回代求得线性方程组的解；也可以使用三角法，包括直接分解法、选主元的直接分解法以及非直接分解法，其解决思路就是将矩阵表示为下三角矩阵与上三角矩阵的乘积：，即，利用向前替代法对方程组求解，利用回代法对方程组求解。但对于大型稀疏矩阵方程组(的阶数很大，但零元素较多), 我们有必要寻找一个更加有效的方法来求解线性方程组的解，这就是本文所研究的主题，线性方程组的迭代算法的研究。 2、算法的基本思路 首先将线性方程组的系数矩阵表示为： 上三角矩阵： 对角矩阵： 下三角矩阵： 由出发，通过一系列的变换后，得到一个迭代格式的线性方程组，然后再加上一个迭代的初始向量，就可以用迭代法来求解线性线性方程组的解。 分量形式的具体变换过程为： (2) 矩阵形式的具体变换过程为： (3) 3、算法的推导及(思路)步骤 3.1、Yacobi迭代法 3.1.1、分量形式推导 (4) 3.1.2、矩阵形式推导 (5) 3.1.3、Jacobi迭代的计算公式 综上所诉，解的Jacobi迭代的计算公式为 (6) 3.2、G-S迭代法 在Jacobi迭代中，计算时，使用代替，即可以得到G-S迭代法 3.2.1、分量形式推导 (7) 3.2.2、矩阵形式推导 (8) 3.2.3、G-S迭代法的计算公式 综上所诉，解的G-S迭代的计算公式为 (9) 3.3、SOR逐次超松弛迭代法 在Jacobi迭代法与G-S迭代法基础上为提高收敛速度，采用加权平均而得到的新算法，基于Jacobi的SOR逐次超松弛迭代法与基于G-S的SOR逐次超松弛迭代法。 3.3.1、基于Jacobi的SOR逐次超松弛迭代法 3.3.1.1、分量形式 (10) 3.3.1.2、向量形式 (11) 3.3.1.3、基于Jacobi的SOR逐次超松弛迭代的计算公式 综上所诉，解的基于Jacobi的SOR逐次超松弛迭代的计算公式为 (12) 3.3.2、基于G-S的SOR逐次超松弛迭代法 3.3.2.1、分量形式 (13) 3.3.2.3、矩阵形式 (14) 3.3.2.3、基于G-S的SOR逐次超松弛迭代的计算公式 综上所诉，解的基于G-S的SOR逐次超松弛迭代的计算公式为 (15) 4、算法分析 4.1、误差分析 设的真实解为，如果有一阶定常迭代法且收敛，即对任取，记，则。则误差向量满足，且如果，则误差估计满足： (16) 4.2、收敛性分析 4.2.1、对角占优定理 如果为严格对角占优矩阵()或为不可约弱对角占优矩阵(不存在置换阵，使得，其中为阶方阵，为阶方阵)，则为非奇异矩阵。 4.2.2、雅可比迭代收敛性 设矩阵具有严格对角优势，则有唯一解，利用迭代式可以产生一个向量序列，而且对于任意的初始向量，向量序列都将收敛到。 4.2.3、迭代法基本定理 设，对于任意的初始向量，迭代公式收敛的充要条件是：迭代矩阵的谱半径(存在某种范数，使得)，其中，为迭代矩阵的特征值。 4.2.4、迭代法收敛速度 由误差向量满足，可得。设为对称阵，则有，当误差缩小时，即使，所需要的最少迭代次数为。由此可得，如果且越小，迭代速度就越快。称为迭代法的渐进收敛速度。 4.3、稳定性分析 在收敛的情况下，一般说来，G-S法的收敛性能较Jacobi法好，然而情况并不总是如此，存在方程组按Jacobi法收敛，而按G-S法不然，因此两种方法均很重要。 5、算法实现(算例、代码) 例、用迭代法求解下列方程组 解 将上面方程组写成xxx学校 20 xx-20 xx下学期《数值方法》
