《解线性方程组的几种迭代算法(共14页)》由会员分享，可在线阅读，更多相关《解线性方程组的几种迭代算法(共14页)（14页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上解线性方程组的几种迭代算法内容摘要:本文首先总结了分裂法解线性方程组的一些迭代算法,在此基础上分别通过改变系数矩阵A的分裂形式和对SSOR算法的改进提出了两种新的算法,并证明了这两种算法的收敛性.与其它方法相比,通过改变系数矩阵A的分裂形式得到的新算法具有更好的收敛性,改进的SSOR算法有了更快的收敛速度.最后通过数值实例验证了这两种算法在有些情况下确实可以更有效的解决问题.关键词:线性方程组 迭代法 算法 收敛速度Several kinds of solving linear equations iterative algorithmAbstract:In this
2、 paper, we firstly summarize some Iterative algorithms of Anti-secession law solution of linear equations. Based on these, two new algorithms are put forward by changing the fission form of coefficient matrix A and improving the algorithm of SSOR, and the convergence of the two algorithms is demonst
3、rated. Compared with other methods, the new algorithm acquired by changing the fission form of coefficient matrix A is possessed of a better convergence. And the improved SSOR algorithm has a faster convergence speed. Finally, some numerical examples verify that the two algorithms can solve problems
4、 more effectively in some cases.Key words:Linear equations Iteration method algorithm Convergence speed 专心-专注-专业目录1.引言12.迭代法原理13.基本迭代法23.1 Jacobi迭代23.2 Gauss-Seidel迭代法33.3 SOR算法33.4 SSOR算法43.5 收敛性分析44.几种新的迭代算法54.1 基于矩阵分裂形式的新迭代算法54.2 加权对称超松弛迭代法75.算法的不足与改进方法96.数值实例96.1渐进收敛速度96.2几种迭代方法的比较10附录11参考文献17解线
5、性方程组的几种迭代算法1.引言在工程技术、自然科学和社会科学中的许多问题最终都可归结为解线性方程组, 因此线性方程组的求解对于解决实际问题是极其重要的.线性方程组的解法有很多种,主要的方法有直接法和迭代法.迭代法就是用某种极限过程去逼近线性方程组精确解的方法,该方法具有对计算机的存贮单元需求少,程序计算简单,原始系数矩阵在计算过程中不变等优点,是求解大型稀疏矩阵方程组的重要方法.目前,人们已经得到了一些较为成熟的线性方程组的迭代解法,从某种意义上讲它们都可归结为分裂法.但在解决具体问题时我们仍面临着许多问题,如:怎样设计出满足要求的求解算法；如何分析、区别算法的好坏；可否改进现有的算法使其更有
6、效；求解所给问题最好可能的算法会是什么,等等.针对这些问题,很多人都做过了大量的研究.文献2对迭代法的原理及一些常用的迭代算法进行了研究.文献1,3,4,5给出了一些基本的迭代算法并证明了其收敛性.文献6,9,10,13,16研究了一些特殊方程组的迭代解法.文献7,8,12,14,15都是针对不同的问题对超松弛迭代算法进行了改进.文献11主要讨论了迭代法解线性方程组的MATLAB实现.本人在求解线性方程组的问题时,通过对现有迭代算法的改进得到了两种新的算法.本文对这两种算法的收敛性进行了证明,并通过数值实例验证了其在解决某些问题时具有的优势.2.迭代法原理设线性代数方程组为 (1)常常将系数矩
7、阵分裂成两个矩阵和之差,即 (2)且用迭代 (3)来解线性方程组(1).将(3)式表示为 (4)其中,称此迭代方法为分裂法,而将称为迭代格式(4)的迭代矩阵.然而迭代法需要解决的首要任务是迭代格式是否收敛的问题,任取初始向量代入(4)中,计算可得迭代序列若迭代序列收敛,设的极限为,对迭代式(4)两边取极限可得:即,是方程组(1)的解,此时称迭代法收敛,否则称迭代法发散.我们有如下的结果:定理2.11 迭代格式(4)收敛的充分必要条件是迭代矩阵的谱半径,而且越小,收敛越快.定理2.21 若为矩阵的某范数,则总有.对于矩阵的分裂应该说是有很多形式,但并不是所有分裂形式产生的迭代格式都有意义.于是我
8、们有正规分裂的概念:定义2.12对于实方阵,若矩阵和满足,且则称是的一个正规分裂.那么正规分裂与其他分裂形式相比到底有什么优势呢?我们有如下定理:定理2.32若为的正规分裂,且,则从而,此时相应的迭代格式(3)必收敛.如果针对矩阵给出两种正规分裂,如何来衡量它的好坏呢?定理2.42 若矩阵有两个正规分裂,设且,则有.3.基本迭代法下面给出常见的几种基本迭代格式.将分裂为 (5)其中,3.1 Jacobi迭代取 (6)则(4)式中迭代矩阵和右端向量分别为迭代格式(4)的分量形式为称它为Jacobi迭代法,该迭代法具有和中分量的计算次序无关,容易并行计算等优点.3.2 Gauss-Seidel迭代
9、法取 (7)此时(4)式中迭代矩阵和右端向量分别为迭代格式(4)的分量形式为称它为Gauss-Seidel迭代法.和Jacobi迭代法相比Gauss-Seidel迭代法使用了最新已经计算的分量.3.3 SOR算法取 (8)此时(4)式中迭代矩阵和右端向量分别为迭代格式(4)的分量形式为其中,称为松弛因子(总假定是实数).迭代格式的矩阵形式为:称它为对应于松弛因子的逐次超松弛迭代法(Successive Over Relaxation,简称SOR).它可以看成Gauss-Seidel迭代法与原向量的组合,但使用了最新已经计算的分量.也就是把取为Gauss-Seidel迭代法中与的某个平均值,即:
10、当时,它就是Gauss-Seidel迭代法.因此希望选取合适的使得它比Gauss-Seidel迭代法具有更快的收敛速度.3.4 SSOR算法SOR迭代格式还可以写为将上式和的位置互换就得到一个新的迭代格式,具体表示为:若消去,就得到迭代格式(4),其中称为对称逐次超松弛迭代法(Symmetric Successive Over Relaxation,简称SSOR).对一类椭圆微分方程离散后得到的线性方程组,Young3给出了最佳松弛因子,即为其中是Jacobi迭代法中的迭代矩阵.在实际问题中最佳松弛因子是很难计算的,但一般都在(0,2)之间.3.5收敛性分析定义3.13 若实矩阵,满足或则称为
11、严格对角占优矩阵；若满足或且上述不等式至少有一个严格成立,则称为弱严格对角占优矩阵.定义3.23 设为阶矩阵,.若存在阶排列矩阵,使得其中为阶矩阵,则称是可约的,否则称不可约.定理3.13 若为阶严格对角占优矩阵或不可约的弱严格对角占优矩阵,则对任意的初始值,(1)式中的Jacobi迭代法、Gauss-Seidel迭代法和关于的SOR迭代法均收敛.定理3.2 4 对所有均成立不等式当是实数时,SOR方法收敛的一个必要条件是.定理3.34 如果系数矩阵是Hermite矩阵,则SOR方法收敛的充要条件是:正定和.4.几种新的迭代算法4.1 基于矩阵分裂形式的新迭代算法上述几种基本迭代方法都是通过对
12、线性方程组(1)的系数矩阵进行分裂得到的,不同之处在于分裂成的形式时,和的取值不同.由(3),(4)可知此种格式下的迭代矩阵,所以当是一个很好的近似时,就会很小.再由定理2.1和定理2.2可知此时得到的迭代法收敛速度也更快.另一方面,我们构造的迭代格式为,由于每一次迭代都要解一个方程组,所以我们也要求非退化的矩阵的形式比较简单,如对角矩阵、下三角矩阵等.比较Jacobi迭代、Gauss-Seidel迭代及SOR算法中的取值,我们可以看到的形式都为对角矩阵或下三角矩阵,并且随着越近似等于,所得到的迭代方法的收敛速度也越快.满足上述两个条件,对取不同于这三种算法中取值的形式,我们可以得到下述新的算
13、法.4.1.1 算法的建立取, (9)作为的一个新分裂,在此分裂的基础上可得到一个新的迭代公式 (10)其中,.显然,当时就是Jacobi迭代法；当时就是Gauss-Seidel迭代法.4.1.2 收敛性分析引理13 可约的充要条件为存在非空子集,使得引理23 若为阶严格对角占优矩阵或不可约的弱严格对角占优矩阵,则是非退化的.定理4.1 若为阶严格对角占优矩阵或不可约的弱严格对角占优矩阵,则对任意的初始值,当时,(10)式表示的迭代格式收敛.证明:(10)式的迭代矩阵为我们有其中为的特征值.若为严格对角占优矩阵,则也为严格对角占优矩阵；若为不可约的弱对角占优矩阵,则也为不可约的弱对角占优矩阵.
14、由引理2,我们有所以令下面证明,用反证法.假设,由可知和的对应元素一定同时为0或非0.由引理1知,不可约推出也不可约.下面比较和的大小.当时,当时,由、知:当,时,.所以有:为弱对角占优矩阵时,也是弱对角占优矩阵；为严格对角占优矩阵时,也是严格对角占优矩阵.再由引理2,可以得到为非退化的矩阵.从而,.进而,.这与是的特征值矛盾,所以.进一步可得到,我们就证明了(10)式表示的迭代格式收敛. 4.2 加权对称超松弛迭代法4.2.1 算法的建立考虑SOR算法和4.1给出的新迭代算法,其实质都是给矩阵分裂以后的因子一个权重后得到的,目的是使得迭代格式(4)的收敛速度尽可能快.按照这种思想,如果在SOR和SSOR迭代中引入一个参数,就可以得到迭代格式 (11)其中,分别为SOR迭代和SSOR迭代算法的迭代矩阵.此时的迭代矩阵.显然,当时,该算法即为SSOR迭代；当时,即为SOR迭代.若迭代格式(11)收敛到某个向量,则有所以不管在0,1内如何取值,当迭代格
