文献综述-关于方程Ax + d = λx的求解.doc

本 科 生 毕 业 论 文（设计）文献综述 姓名与学号指导教师 年级与专业2010 信息与计算科学 所在学院数学系 1、 求解特征值和特征向量的方法1.1非对称特征值问题的计算方法（1）幂法。幂法是就是那种一个矩阵的模最大特征值和对应的特征向量的一种迭代方法。假定A是可对角化的矩阵。那么可以得到一个式子uk = Ak*u0 / k，其中uk是A的特征向量空间中的某个向量，那么当k充分大时，uk就是特征值k的对应的一个特征向量。可以由此得到一个迭代格式：yk = Auk-1，k = (k)j, (k)j是yk的模最大分量，uk = yk/k，其中u0是任意给定的初始向量，通常要求|u0| = 1。如果们想要接着求接下来的特征向量和特征值，那么就需要利用已经求得的特征值把原矩阵降阶。最简单实用的收缩技巧是利用正交变换。假设 Ax1 = 1x1并假设酉矩阵P使得 Px1 = e1这里e1 = (1,0,0)T。将上式带入上上式并整理可得 PAP*e1 = 1e1即PAP*的右下为一个n-1的矩阵，它的特征值就是A除了1以外的特征值。那么对PAP*的右下矩阵继续做幂法即可。而得到P的变换可以使用复的Householder变换来实现。（2）反幂法。反幂法又称作反迭代法，就是应用幂法作用在A-1上，来求A的模最小特征值和对应的特征向量。因此，其基本迭代格式为Ayk = zk-1，k = i, i是yk的模最大分量，zk = yk/k。反幂法主要用来求特征向量，是在用某种方法求得A的某个特征值i的近似值i之后，应用反幂法于A-iI上。也就是说，在实际计算中，常用的是带位移的反幂法。设是给定的位移。带原点位移的反幂法的迭代格式如下：(A-I)vk = zk-1，zk = vk / |vk|2，从上述的迭代格式上可以看出，反幂法每迭代一次就需要解一个线性方程组，这比幂法的运算量大得多。但是，由于方程组的系数矩阵不随着k变化，所以，可以先把系数矩阵做LU分解，然后就只需要解两个三角矩阵方程组就可以了。（3）QR方法。QR方法是自电子计算机问世以来矩阵计算的重大进展之一，也是目前计算一般矩阵的全部特征值和特征向量的最有效方法之一。QR方法是利用正交相似变换将一个给定的矩阵逐步约化为上三角矩阵或拟上三角矩阵的一种迭代方法，其基本收敛速度是二次的，当然原矩阵实对称时，可以达到三次收敛。QR算法的基本迭代格式如下：Am-1 = QmRm，Am = RmQm，其中Qm为酉矩阵，Rm为上三角矩阵。QR方法有很多加速和优化的方法，例如双重步位移的QR迭代方法。考虑如下的迭代格式（带位移的QR方法）：H1 = Q0TAQ0，Hk kI = QkRk，Hk+1 = RkQk + kI，这样可以在迭代的过程中会有复数的产生。如果一开始就给出两个值，就可以使用双重步位移的QR方法。可以提供的代码：function h=DoubleStepQR( H,n )%双重歩位移QR迭代法% 输入数据为Hessenberg矩阵H以及矩阵H的阶数neps=1E-10;m=n-1;s=H(m,m)+H(n,n);t=H(m,m)*H(n,n)-H(m,n)*H(n,m);x=H(1,1)*H(1,1)+H(1,2)*H(2,1)-s*H(1,1)+t;y=H(2,1)*(H(1,1)+H(2,2)-s);z=H(2,1)*H(3,2);for k=0:n-3 v,beta=house(x,y,z); if (k1) q=k; else q=1; end i=eye(length(v)-beta*(v*v); H(k+1:k+3,q:n)=i*H(k+1:k+3,q:n); if (k+4n) r=k+4; else r=n; end H(1:r,k+1:k+3)=H(1:r,k+1:k+3)*i; x=H(k+2,k+1); y=H(k+3,k+1); if (kn-3) z=H(k+4,k+1); endendv,beta=house(x,y);i=eye(length(v)-beta*(v*v);H(n-1:n,n-2:n)=i*H(n-1:n,n-2:n);H(1:n,n-1:n)=H(1:n,n-1:n)*i;h=H;for i=2:n if (abs(h(i,i-1)max) max=abs(U(p(i),k); j=i; end end t=p(k); p(k)=p(j); p(j)=t; for i=k+1:n L(p(i),k)=U(p(i),k)/U(p(k),k); for j=k:n U(p(i),j)=U(p(i),j)-L(p(i),k)*U(p(k),j); end endend（3）Cholesky分解代码（中间过程不使用开根号的计算）：function Cholesky_imp( fn )%CHOLESKY_IMP Summary of this function goes here% Detailed explanation goes herefin=fopen(fn,r);n=fscanf(fin,%d,1);A=fscanf(fin,%f,n,n);b=fscanf(fin,%f,n);fclose(fin);A=A;L=A;v=zeros(n,1);for j=1:n for i=1:j-1 v(i)=L(j,i)*L(i,i); end L(j,j)=L(j,j)-L(j,1:j-1)*v(1:j-1); L(j+1:n,j)=(L(j+1:n,j)-L(j+1:n,1:j-1)*v(1:j-1)/L(j,j);endx=b;for k=2:n x(k)=x(k)-L(k,1:k-1)*x(1:k-1);endU=L;x(n)=x(n)/U(n,n);for k=n-1:-1:1 x(k)=x(k)/U(k,k); x(k)=x(k)-U(k,k+1:n)*x(k+1:n);endrx=0;xx=Ab;for k=1:n rx=rx+(xx(k)-x(k)2;endrxrb=0;bb=A*x;for k=1:n rb=rb+(bb(k)-b(k)2;endrbend2.2对于规模较大的矩阵，我们一般会采用迭代法的方法来解方程。符号定义：Ax = b，A = D L U，D为对角元矩阵，-L为下三角（无对角元）矩阵，-U为上三角（无对角元）矩阵。记B = D-1(L+U)，M = (D - L)-1U。 （1）Jacobi迭代。 xk+1 = Bxk + D-1b （2）G-S迭代。xk+1 = Mxk + (D - L)-1b。 （3）SOR迭代。xk+1 = Lxk + (D - L)-1b,其中L = (D - L)-1(1 - )D + U，称作松弛因子。当1时，相应的迭代法叫做超松弛迭代法；当1时，叫做低松弛迭代法；当=1时，就是G-S迭代法。其中超松弛迭代法简称为SOR迭代法。SOR迭代法的收敛速度与的选取有很大的关系。参考文献1 徐树方，高立，张平文.数值线性代数.北京：北京大学出版社，2013.2 曹志浩.矩阵特征值问题.上海：上海科学技术出版社，1980.3 曹志浩，张玉德，李瑞遐.矩阵计算和方程求根.北京：高等教育出版社，1979.4 徐树方.矩阵计算的理论与方法.北京：北京大学出版社，1995.5 黄正达，李方，温道伟，汪国军. 高等代数. 浙江：浙江大学出版社，2010.6 叶兴德，程晓良，陈明飞，薛莲.数值分析基础.浙江：浙江大学出版社，2008.7 王能超编著.计算方法算法设计及其Matlab实现.北京：高等教育出版社，2005.8 Wilkinson J H. The Algebraic Eigenvalue Problem.Oxford: Clarendon P