吴文刚的论文.doc

安庆师范学院数学与计算科学学院2012届毕业论文线性方程组迭代方法的总结及程序实现作者：吴文刚 指导老师：盛敏摘要 线性方程组的求解问题是大规模科学与工程计算的核心. 随着计算机的发展迭代法已取代直接法成为求线性方程组最重要的一类方法. 本文从线性方程的迭代问题出发，利用不同的迭代方法的优劣势，通过给求线性方程组的解提供三种已有迭代方法. 对于方程的迭代方法选取一种经典的.高斯-赛德尔法迭代法和两种非经典的外推法迭代法，切比雪夫加速迭代法，通过比较得出线性方程迭代方法的的有效途径. 关键字 线性方程组 高斯-塞德尔迭代法 外推法 切比雪夫加速 MATLAB1 引言 线性方程组是线性方程组线性方程组是各个方程关于未知量均为一次的方程组(例如2元1次方程组). 对线性方程组的研究，中国比欧洲至少早1500年，记载在公元初九章算术方程章中. 称为系数矩阵和增广矩阵. 若，代入所给方程各式均成立，则称为一个解.若不全为0，则称为非零解。若常数项均为0，则称为齐次线性方程组，它总有零解（0，0，0）.两个方程组，若它们的未知量个数相同且解集相等，则称为同解方程组。线性方程组主要讨论的问题是：一个方程组何时有解.有解方程组解的个数.对有解方程组求解，并决定解的结构.这几个问题均得到完满解决：所给方程组有解，则秩(A）=秩（增广矩阵）；若秩(A）=秩=r，则r=n时，有唯一解；r GauS(A,0.005)迭代次数为5ans =1.94762.42091.42103.1 外推迭代法的定义及其性质可以用来改进线性迭代过程的收敛性质考察的迭代公式 （6）引进参数0，并把方程（6）嵌入到下面参数迭代方程族中，其中注意：当=1时，我们重新获得（6）式中原来的迭代。 若（7）中的迭代收敛于x,则取极限，我们得到 x=(Gx+c)+(1-)x或者，因为0,可得到 x=Gx+c记得迭代（6）的目标产生方程x=Gx+c的解。若G=I-Q-1A及c=Q-1b,则这个方法对应于求解Ax=b.在试图确定参数的最优值之前，我们需要一个有关特征值的结果。定理1（p（A）的特征值定理） 若是矩阵A的特征值，并且p是一个多项式，则p（）是p（A）的特征值。 证明 设Ax=x，x0.则A2x=Ax=2x.由归纳法及对k=0的单独验证，有 Ak=kx（k0）因此，k是Ak的特征值，多项式p，记 由定理1，（7）式中的外推法收敛的充要条件是（）1或者b1.给出第二种情况的证明，因为ab0且d=1-b.因此，如前段所注明的那样，的任意特征值满足不等式a+1-b+1- （9）因此，b+1-=1+(b-1)=1-d此外a+1-=（a+b-2）+1+（1-b）=-1+d因而，我们证得 -1+d1-d因此.为了看出选择的是最佳的，注意当递增时，（9）式中区间的左端点向左移动.如果那个点碰巧是的一个特征值，那么就递增.当递减时，类似可证.应该看到刚才所讨论的外推的过程也可以应用于它本身并不收敛的方法中，而这一切所需要的是G的特征值是实的且位于不包含1的一个区间中.若A是一个矩阵，其特征值是全部是实的，我们定义 （10）因而在定理2中，我们可设a=m(G),b=M(G). 3.3 可以确定最佳外推理查森方法的半径在理查森迭代情况中，Q=I,G=I-A.若A只有实特征值，则G的特征值也是实的，由定理2，有 M(G)=1-m(A) m(G)=1-M(A) （11）若m(A)0或M(A) WaiT(A,0.001,0.5)迭代次数为4ans =1.1296 1.3423 1.04984.1 切比雪夫加速定义及其性质 更一般类型的加速过程称为切比雪夫加速，也可以应用线性迭代算法.如前面一样，先考察基本迭代法 假定问题的解满足x=Gx+c的向量x.在过程中的第k步，我们已算得向量x（1），x（2），.,x(k),这个向量的某个线性组合比x（k）更好地逼近于解.假定，并取 利用熟悉的方法，我们得到其中P是由定义的多项式.去范数,得到这里可以使用任何范数及从属矩阵范数.取遍全体从属矩阵范数的，其下确界是（P（G）；这个下确界就是应该使其为最小的值.若G的特征值位于复平面上某个有界集S中，由定理1，得应该极小化最后的表达式来选定多项式P，并且服从约束这里P（1）=1.这是逼近论中的一个标准问题，某些情况其显式解是已知的. 4.1 例如，若S是实直线上一个不包含1的区间，则一个尺度化和位移的切比雪夫多项式可以解决这个问题.经典的切比雪夫多项式是极小化表达式服从首项系数为约束的唯一k次多项式这些多项式由下列公式递归地生成：现假定G的特征值位于不含1的区间中，譬如说b0这表明多项式在点上交替取正值和负值.因此，这个多项式在区间（-1,1）中至少有k个零点.因为在点它也为零，所以这个多项式至少共有k+1个零点.因为的次数至多为k次，所以它必须为0，矛盾.4.3 引理2（规范多项式第二引理） 设ab1.由引理1立即可得.等价地，.若，则显然p(1)=1且4.4 引理3 （多项式，递归关系引理） 多项式可由递归关系：生成，其中系数由下列等式得到 证明 定义.借助于关系和，得到 = =这里，利用容易易证的等式.定义是很方便的.再利用切比雪夫多项式地推关系，得到 于是，的递归关系可以写成系数满足等式= = = =4.4.1 例子 利用雅克比方法的切比雪夫加速求解下列问题： 解 首先我们用尺度化方程组，这里D=diag（A），得到雅克比迭代矩阵，其特征值位于区间-1/2,1/2中.可应用切比雪夫加速法来加速这个基本方法的收敛性质.一开始用初始向量，利用类似于Marc-32的计算机，10步迭代后收敛于近似解（-0.999996，-0.500002,0.500002，-0.999996）T. 结束语 文章提供三种解线性方程组的的迭代方法，三种方法都相互涉及，各有各的优缺点，迭代法有储存空间小，程序简单等特点，通过对一些矩阵和函数的操作可以轻松地得到线性方程组的解,不需要使用者掌握任何程序设计语言,迭代法只需编写简单的程序.我期待将切比雪夫加速迭代法在MATLAB实现.参考文献1邓建中，葛仁杰，计算方法,M西安交通大学出版社.19942David Kincaid,Ward Cheneny,数值分析M，机械工业出版社,2005.3林成森，数值分析M，科学出版社,2006.4赵慎行，线性方程组 AX=b 几种解法的比较研究C.科技咨询导报,2007.5李庆扬,王能超,易大义.数值分析(第7、8章)M.武汉:华中理工大学出版社,1987.6 刘敬.n阶方阵乘幂的一种简单求法J.工科数学,1994.7Abafly,aj.and Spedicato,E,ABS Project Algonrithms:Mathermatical Techniques for liner and Nonlineae Equations Ellis Horwood, Chichester,1989. linear equations of iteration method summary and realizingAuthor:wuwengang Guiding teacher：shengmin Abstract: linear equations of solving problem large-scale science and the core engineering calculation.With the computer developing,iteration method has be the important method instead of direct method.Based on the linear equations iterative,using of the advantages and disadvantages of different iterative methods.Three existing iterative method to seek the solution of linear equations,they are Gauss-Seidel method, and Chebyshev acceleration method.Effective way through comparisons of the iterative method of linear equations . Key words:linear equations Gauss-Seidel method extrapolation method Chebyshev acceleration method MATLAB附注1：高斯-塞德尔迭代法的MATLAB编程function y=GauS(A,ep)n,m=size(A);%G-S方法求解现行方程组%=s=0;k=0;x=zeros(n,1);epsilon=1;while epsilon=ep x1=x; for i=1:n for j=1:n s=s+A(i,j)*x(j); end x(i)=x(i)+1/A(i,i)*(A(i,m)-s); s=0; end epsilon=max(abs(x1-x); k=k+1; if k100 disp(G-S方法不适用求解该方程组) break; endend disp(迭代次数为)disp(k);y=x;附注2外推迭代法的MATLAB编程function y=WaiT(A,ep,w)n,m=size(A);%W-T方法求解现行方程组%=s=0;k=0;x=zeros(n,1);epsilon=1;while epsilon=ep x1=x; for i=1:n for j=1:n s=s+A(i,j)*x(j); end x(i)=(1-w)*x(i)+w*(1/A(i,i)*(A(i,m)-s); s=0; end epsilon=max(abs(x1-x); k=k+1; if k100 disp(W-T方法不适用求解该方程组) break; endend disp(迭代次数为)disp(k);y=x;附注3可用切比雪夫加速方法的算法如下： Input u,a,b,M, 2/(2-b-a) Output 0,u Call Ertrap(,n,G,c,u,v) Output 2,v 1/(1-2) Call Cheb(,n,G,c,u,v) Output 2,u for k=3 to M step 2 do (1-) Call Cheb(,n,G,c,v,u) Output k,v (1-) Call Cheb(,n,G,c,u,v) Output k+1,u