大规模矩阵问题的Krylov.ppt

大规模矩阵问题的Krylov 子空间方法综述 Krylov子空间方法综述 背景介绍 投影方法 Krylov子空间及其标准正交基 Krylov子空间方法求解线性方程组 Krylov子空间方法求解矩阵的特征值 研究热点和尚未解决的问题 背景 大规模线性方程组的求解 很多科学工程计算问题都转化为求解方程组Ax=b.如偏微分方程组的差分格式，有限元方法离散得到刚度矩阵. 大规模矩阵特征值和特征向量的计算 工程计算领域十分常见。如量子物理中的Kohn-Sham方程求解化为哈密顿矩阵某些关键特征值对的计算. 投影方法 线性方程组的投影方法 方程组Ax=b,A是n×n的矩阵. 给定初始x(0),在m维空间K(右子空间）中寻找x的近似解x(1) 满足残向量r=b-Ax(1) 与m维空间L(左子空间）正交，即 b-Ax(1) ⊥L 此条件称为Petrov-Galerkin条件 . 当空间K=L时，称相应的投影法为正交投影法，否则称为斜交投影法. 解方程组的投影法的矩阵表示 　　设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），有 从而得到迭代公式 投影方法的最优性 １. (误差投影)设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＝０的非零首一多项式的最低次数 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(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），有 从而得到迭代公式 　　 不难看出，当采用上述FOM算法时，需要存储所有的vi，(i=1,2,…m)，当m增大时，存储量以O(mn)量级增大.而FOM计算量是O(m2 n).可见其代价十分高昂.因此我们考虑重启的?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才能取得满足精度要求的近似解. IOM算法仅仅是把FO