苏州大学本科生毕业设计（论文）目录 摘要 31 前言 52 迭代法的思想 62.1 迭代法的基本概念 62.2 迭代法的收敛条件 63 常见迭代法 73.1 Jacobi迭代法 73.1.1 Jacobi迭代法的计算公式 73.1.2 Jacobi迭代法的收敛条件 83.2 Gauss迭代法 93.2.1 Gauss迭代法的计算公式 93.2.2 Gauss迭代法的收敛条件 103.3 SOR迭代法 103.3.1 SOR迭代法的计算公式 103.3.2 SOR迭代法的收敛条件 113.4 CG迭代法 113.5 PCG迭代法 123.6 GMRES迭代法 134 数值算例分析 13算例4.1 13算例4.2 145 总结 16参考文献 17致谢 18摘要这篇论文介绍了大型矩阵运算时要用到的迭代法和其思想，并简单介绍了常用的几种迭代方法：如基于矩阵分解原理的Jacobi迭代法，Gauss迭代法和SOR迭代法；属于共轭方向法的CG法和PCG法；最后介绍了适用于解决非线性方程组的GMRES迭代法及他们其中一些迭代法的收敛条件.并通过对不同矩阵的具体运算比较了他们的迭代次数，简单分析了几种迭代方法的优劣.关键字:迭代法思想，Jacobi迭代法，Gauss迭代法，SOR迭代法,CG迭代法,PCG迭代法，GMRES迭代法，迭代次数，收敛体条件.AbstractThis essay introduces the iterative method which is needed during large matrix operation. Meanwhile, some of common methods of iteration are also suggested in this essay, for instance: Jacobian interation, Gauss interation and successive over relaxation method which were all based on the Matrix decomposition technique; conjugate gradient algorithm and Preprocessing conjugate gradient algorithm which both belong to conjugate direction method; GMRES algorithm which is used to solve non-linear equation and some of their own condition of convergence. In addition, by comparing their iteration steps, I roughly analysed their merits and demerits.Keywords: iterative method，Jacobian interation, Gauss interation, successive over relaxation method, conjugate gradient algorithm, Preprocessing conjugate gradient algorithm, GMRES algorithm, iteration steps and condition of convergence.1 前言矩阵自19世纪被英国数学家凯利提出来，历经了200多年的发展，在现代生活中有及其广泛的应用，下面我将列举几项矩阵在现实生活中的应用：矩阵可用于预测水质量状况以及用于处理水污染等问题;矩阵还可以用于模拟飞机飞行所需要的飞行环境;在物理学领域的磁电场的探查测量方面也有很广泛的应用;许多图片在电脑上的存储方式就是以矩阵的格式存储的,以便对图片进行调整和美化的时候可以利用数学公式对图片进行处理等。除此以外，矩阵还在许多领域有着极为广泛的应用，这里就不一一举例了。而这些矩阵通常都是大型矩阵，如何高效的处理大型矩阵和与其相关的线性方程组成了一个值得深思的问题。而迭代法在处理零元素较多的大型稀疏矩阵时具有运算和存储两方面的优势。比较典型的有基于矩阵分解原理的Jacobi迭代法，这是由伟大的普鲁士数学家雅可比在19世纪提出来的，在当时Jacobi迭代法具有许多优点，其计算公式简单，每一次的迭代中只需计算一次矩阵和向量的乘法。这也是最早期的迭代法。同雅可比迭代法一样，高斯-塞德尔和超松弛迭代法也是基于矩阵分解原理，这些都是传统的迭代法，出现时间较久。此外，还有其他一些优异的矩阵迭代算法，如以极小化的方法来讨论方程组的解的著名的共轭梯度（CG）算法，CG法出现在20世纪中期，它有许多优异的性质：比如相较于传统迭代法，CG法收敛速度较快；此外CG法只有极少量的非向量运算。然而由于实际运算中舍入误差的积累以及正交性的逐渐丧失，CG法长时间并未得到广泛应用。直到20世纪70年代，预处理共轭梯度算法（PCG算法）出现了，它通过对CG算法中未加工过的矩阵进行某种形式的加工改造，使它具有更适宜迭代的特点。近些来，PCG法有了进一步的发展。它现在已经有了MICCG，块预处理，高阶LU分解和行和一致预处理等预处理方法，预处理技术正在不断完善中；此外共轭梯度算法也发展为可应用于不定阵，非奇异阵及复矩阵等多种矩阵形式的较为系统的方法。经过了近200年的发展，迭代法变得越来越系统，且新的优异的迭代法也不断涌出，本文主要对其中几种比较典型的迭代方法进行介绍和探究，本文的内容主要分为：迭代法基本概念及收敛性的介绍，几种迭代法步骤及特性的介绍(Jacobi,Gauss,SOR,CG,PCG,GMRES)，具体的算例分析和总结。2 迭代法的思想2.1 迭代法的基本概念迭代法的由来与线性方程组的求解有较深的关系，下面我们来举例说明有线性方程组Ax=b, （2.1）其中A为大型稀疏矩阵（具有较多的零元素），此时直接求解很困难，而用迭代法是比较合理有效的.例如：求解线性方程组8x13x2+2x3=20,4x1+11x2x3=33,6x1+3x2+12x3=36, （2.2）记为Ax=b，其中有A=83241116312, x=x1x2x3, b=203336.该方程组的精确解为x=3，2，1T.线性方程组（2.2）可以恒等变形为下式x1=183x22x3+20,x2=1114x1+x3+33,x3=1126x13x2+36; (2.3)则有x=B0x+f，其中B0=0382841101116123120， f=82233113612.任意选取初始值，例如x(0)=0，0，0T，代入（2.3）式可以得到新的值x(1)=x1(1)，x2(1)，x3(1)T，再将新的x(1)分量代入得到x(2)，反复利用这个计算程序，即可得到迭代法的一般式x(k+1)=B0 x(k)+f，（k为迭代次数）.除（2.3）外，线性方程组（2.2）的恒等变形方式还有很多种，不同的恒等变形可得到不同的迭代式，均可写成如下形式x(k+1)=B0 x(k)+f然而向量序列x(k)并非都可以逐步逼近方程组的解x.2.2 迭代法的收敛条件不难看出若有lim kx(k)=x存在，则此迭代法是收敛的（ x为上面方程组的解），否则该迭代法即为发散的.由上可知，若要研究x(k)的收敛性，可以引入一个误差向量(k+1)=x(k+1)x,对于线性方程组x=Bx+f,设有唯一解为x，则x=Bx+f.与x(k+1)=B0 x(k)+f 相减得， (k+1)=B(k)(k=0,1,2),递推得(k)=B(k1)=Bk0.要考察x(k)的收敛性，就要研究B在什么条件下limk(k)=0 ，此时有定理：迭代公式收敛的充要条件是矩阵的谱半径B1 13 常见的几种迭代法3.1 Jacobi迭代法3.1.1 Jacobi迭代法的计算公式上面迭代法的思想是从线性方程组的角度来看，我们不妨从矩阵的角度来看.矩阵分解技术在矩阵中具有广泛应用，它通过对矩阵的分解来构造迭代格式.如将矩阵A分解为M+N故此Ax=b即可写成Mx+Nx=b即Mx =b-Nx当M可逆时有x=M1bM1Nx由此可构造迭代格式x(k+1)=M1Nxk+M1b其中M1N为迭代矩阵，且M要满足是可逆的且逼近A.下面我们将讨论几种基于矩阵分解原理的常见迭代法.将线性方程组中的系数A=(aij)Rnn分成三部分A=a11 a22 ann_0 a210 an1,1an1,20 an1an2an,n10_0a12a1,n1a1n 0a2,n1a2n