大规模矩阵问题的krylov 子空间方法综述

《大规模矩阵问题的krylov 子空间方法综述》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、大规模矩阵问题的Krylov子空间方法综述Krylov子空间方法综述背景介绍投影方法Krylov子空间及其标准正交基Krylov子空间方法求解线性方程组Krylov子空间方法求解矩阵的特征值研究热点和尚未解决的问题背景大规模线性方程组的求解很多科学工程计算问题都转化为求解方程组Ax=b.如偏微分方程组的差分格式，有限元方法离散得到刚度矩阵.大规模矩阵特征值和特征向量的计算工程计算领域十分常见。如量子物理中的Kohn-Sham方程求解化为哈密顿矩阵某些关键特征值对的计算.投影方法线性方程组的投影方法方程组Ax=b,A是n×n的矩阵.给定初始x(0),

2、在m维空间K(右子空间）中寻找x的近似解x(1)满足残向量r=b-Ax(1)与m维空间L(左子空间）正交，即b-Ax(1)⊥L此条件称为Petrov-Galerkin条件.当空间K=L时，称相应的投影法为正交投影法，否则称为斜交投影法.K(L)X(0)X(1)KLX(0)X(1)解方程组的投影法的矩阵表示设n×m阶矩阵V=[v(1),v(2),…v(m)]与W=[w(1),w(2),…w(m)]的列分别构成K与L的一组基.记z=x(1)-x(0),z=Vy,有当　　　非奇异时（通常情况成立，见定理1.1），有从而得到迭代公式投影方法的最优性１.(误

3、差投影)设A为对称正定矩阵,x(0)为初始近似解,且K=L,则x(1)为采用投影方法得到的新近似解的充要条件是其中,且x为(1.1)的精确解.２.(残量投影)设A为任意方阵,x(0)为初始近似解,且L=AK,则x(1)为采用投影方法得到的新近似解的充要条件是其中矩阵特征值的投影方法对于特征值问题Ax=λx,其中A是n×n的矩阵，斜交投影法是在m维右子空间K中寻找xi和复数λi满足Axi-λixi⊥L,其中L为m维左子空间.当L=K时，称此投影方法为正交投影法.Kyrlov子空间定义为m维Krylov子空间μ为v的次数，即使得q(A)v＝０的非零首一

4、多项式的最低次数Krylov子空间的标准正交基Arnoldi方法基于Gram-Schmit正交化方法首先，选取一个Euclid范数为1的向量v(1),对,通常可取在已知v(1),v(2),……v(j)的情况下,不妨设v(1),v(2),……v(j),Av(j)线性无关(否则构造完毕),则可求出与每个都正交的向量而不难看出　　　　　　　　　　　，再记,得到与v(1),v(2),……v(j)都正交的向量　　　　　　重复此过程，即可得到一组标准正交基.若期间某个j使得hj+1,j=0,则说明v的次数是j,且Kj是A的不变子空间.定理如果记以v(1),v(

5、2),……v(m)为列构成的矩阵为Vm,由hij定义的(m+1)×m阶上Hessenberg矩阵为,删除最后一行得到的矩阵为Hm,则在Arnoldi算法中，可能有较大舍入误差，改写Krylov子空间方法解线性方程组误差投影型方法取L=K时的正交投影法１）非对称矩阵的FOM方法解方程组的投影法的矩阵表示设n×m阶矩阵V=[v(1),v(2),…v(m)]与W=[w(1),w(2),…w(m)]的列分别构成K与L的一组基.记z=x(1)-x(0),z=Vy,有当　　　非奇异时（通常情况成立，见定理1.1），有从而得到迭代公式回顾不难看出，当采用上述FO

6、M算法时，需要存储所有的vi，(i=1,2,…m)，当m增大时，存储量以O(mn)量级增大.而FOM计算量是O(m2n).可见其代价十分高昂.因此我们考虑重启的FOM算法Krylov子空间方法解线性方程组误差投影型方法取L=K时的正交投影法１）非对称矩阵的FOM方法2)非对称矩阵的IOM方法和DIOM方法所谓不完全正交化方法(IOM),是指在正交化过程中,v(j+1)仅与最近k个v(j-k+1),…v(j-1),v(j)正交,这样做虽然破坏的正交性,但是降低了计算量.当然k选得越小，对每个j对应的计算量也越小,但可能要选更大的m才能取得满足精度要求

7、的近似解.IOM算法仅仅是把FOM算法的第三步改为(iii’)对i=max(1,j-k+1),…,j,计算hij与w(j).但采用IOM后，仍然需要存储v(1),v(2),…v(m),因为在第(vi)步　　　　　　　　　中仍然需要这些向量.解决这个问题可以考虑采用H的LU分解，通过自身分解的迭代更新以减少每一步的存储量Krylov子空间方法解线性方程组误差投影型方法取L=K时的正交投影法１）非对称矩阵的FOM方法2)非对称矩阵的IOM方法和DIOM方法３）对称矩阵Lanczos算法回顾定理如果记以v(1),v(2),……v(m)为列构成的矩阵为Vm

8、,由hij定义的(m+1)×m阶上Hessenberg矩阵为,删除最后一行得到的矩阵为Hm,则在Arnoldi算法中，可能