《krylov子空间算法知识讲解》由会员分享，可在线阅读，更多相关《krylov子空间算法知识讲解（13页珍藏版）》请在金锄头文库上搜索。
1、Krylov子空间的定义：定义：令RN，由，A丄，Am1所生成的子空间称之为由与A所生成的m维Krylov子空间，并记KmA,v。主要思想是为各迭代步递归地造残差向量，即第n步的残差向量rn通过系数矩阵A的某个多项式与第一个残差向量r0相乘得到。即n0rpAr。但要注意，迭代多项式的选取应该使所构造的残差向量在某种内积意义下相互正交，从而保证某种极小性（极小残差性），达到快速收敛的目的。Krylov子空间方法具有两个特征：1.极小残差性，以保证收敛速度快。2.每一迭代的计算量与存储量较少，以保证计算的高效性。投影方法线性方程组的投影方法方程组Axb,A是nn的矩阵。给定初始x0,在m维空间K（
2、右子空间）中寻找x的近似解X1满足残向量rbAX1与m维空间L（左子空间）正交，即bAx1l,此条件称为Petrov-Galerkin条件。当空间K=L时，称相应的投影法为正交投影法，否则称为斜交投影法.投影方法的最优性：1.（误差投影）设A为对称正定矩阵，x0为初始近似解，且K=L,则x1为采用投影方法得到的新近似解的充要条件是x1mjnzzx0K其中，zAxz,xz122.（残量投影）设A为任意方阵，x为初始近似解，且LAK,则x1为采用投影方法得到的新近似解的充要条件是x1minzzx0K其中z|bAz|2bAz,bAz2矩阵特征值的投影方法对于特征值问题Axx,其中A是nxn的矩阵，斜
3、交投影法是在m维右子空间K中寻找x和复数i满足AxiiXiL,其中L为m维左子空间当L=K时，称此投影方法为正交投影法.误差投影型方法：取L=K的正交投影法非对称矩阵的FOM方法（完全正交法）对称矩阵的IOM方法和DIOM方法对称矩阵的Lanczos方法对称正定矩阵的CG方法残量投影型方法：取L=AK时的斜交投影法GMERS方法（广义最小残量法）重启型GMERS方法、QGMERS、DGMERSArnoldi方法标准正交基方法：Arnoldi方法是求解非对称矩阵的一种正交投影方法。Arnoldi算法就是对非对称矩阵A,产生Krylov子空间ma,r0的一组标准正交基的方法。该算法构造mA,r0H
4、essenberg矩阵hnh12h13Lh1mh21h22h23Lh2mHm0h32h33LMMOOOhm1,m0L0hm,m1hmm基于Gram-Schmit正交化方法的组标准正交基V1，V2，K,Vm和hnh12h13Lh1mh21h22h23Lh2m0h32h33LM，HmMOOOhm1,m0L0hm,m1mm0L00hm1,m首先，选取一个Euclid范数为1的向量v1,对mA,通常可取112，在v1,v2,L,vj已知的情况下，不妨设v1,v2,L,vj,Avj线性无关（否则构造完毕）,则可求出与每个都正交的向量wjAvjhjV1h2jv2LhM而不难看出hjAvj,vi,i1,2,
5、L,j，再记hj1wj,wj/2，得到与jv1,v2,L,vj都正交的向量vj1，重复此过程，即可得到一组标准hju正交基。若期间某个j使得hj1,j0，则说明v的次数是j,且j是A的不变子空间。Arnoldi算法：（1）取向量v1，满足|v11,j1（2）按（2）式计算h,i1,2,L,j，再按（1）式计算wj（3）按（3）式计算h,j，若0，则停止，否则按（4）式计算vj1（4）若jm，则jj1，转（2），否则停止wjAvjh1jv1h2jv2Lhjjvj（1）hjAvj,vi,i1,2,L,j(3)(4)hj-wj,wj12定理：如果记以v1,v2,l,vm为列构成的矩阵为Vm,由hj定
6、义的(m+1)xm阶上Hessenberg矩阵(假设一个nn阶矩阵A，在iji时，它的a,o,那么这个矩阵A就叫做Hessenberg矩阵)为Hm,删除最后一行得到的矩阵为Hm，则:AVmVmHmW”eVm1HmV；AVmHm在Arnoldi算法中，可能有较大舍入误差，改写:1i1ihjAvh1jVLhi1,jV,v,i1,2,L,j修正的Arnoldi算法：(1) 取向量v1，满足卜11,j1(2) 计算wjAvj(3) 依次对i1,2,L,j，计算hijwj,vi与wjwjhijvi(4) 计算hj1,j，若h,jo，则停止，否则计算vj1若jm,则jj1，转(2),否则停止FOM(完全正
7、交化)方法非对称矩阵的FOM方法：解方程组的投影法的矩阵表示设nm阶矩阵Vv1,v2,L,vm与Ww1,w2,L,wm的列分别构成K与L的一组基。记zx1x0,zVy，有WTr0AVy0当WtAV非奇异时，有yWTAV1WTr，从而得到迭代公式:10xxVTWAV1T0WrFOM算法：(1)计算r0bAx000,r,r.121r,vr0,置j1(2)计算wjAvj(3)依次对i1,2,L,j，计算hjwj,vi与wjwjhjv(4)计算hj1,j，若hj1,j0，则置mj,转(6)(5)计算vj1，若jm，则置jj1,转(2)(6)按下式计m算xm0mm11xxVmy,yHme不难看出，当采用
8、上述FOM算法时，需要存储所有的v,(i=1,2,m),当m增大时，存储量以Omn量级增大.而FOM计算量是0m2n.可见其代价十分高昂因此我们考虑重启的FOM算法重启型FOM算法：(1) 计算r0bAx0,r,rlv1(2) 生成mA,r的一组标准正交基，得到Hm按下式计算xm，若xm满足精度要求，则停止，否则置xxm,转(1)。xmxVmym,ymHm1e1IOM方法非对称矩阵的IOM方法所谓不完全正交化方法(IOM),是指在正交化过程中,vj1仅与最近k个vjk1丄,vj1,vj正交，这样做虽然破坏的正交性，但是降低了计算量.当然k选得越小，对每个j对应的计算量也越小，但可能要选更大的m
9、才能取得满足精度要求的近似解.IOM算法仅仅是把FOM算法的第三步改为imax1,jk1,L,j，计算hj与wj。但采用IOM后，仍然需要存储v1,v2,L,vm,因为在第（Vi）步xmx0Vmym中仍然需要这些向量.解决这个问题可以考虑采用H的LU分解，通过自身分解的迭代更新以减少每一步的存储量DIOM算法:(1)计算r0bAx0001210，r,r，vr0，直m1(2)计算wm八mAv(3)对imax1,mk1,L,m，依次计算himmif-mmiw,v与wwhijV(4)计算hm1,mm,w(5)(4)式更新的LU分解，若Umm0,则停止(6)(3)式计算，按（2）式计算p，其中i0时，
10、umpi0(7)(1)式计算，若符合精度要求，则停止，否则mm1，转（2）(1)m11UmmiUimPUm10mlm,m1m1,m1k1,mmk1,m(3)(4)1m,m1每一步所需存储量和计算量是常量,不会随着子空间维数的增加而改Uimhimli,iiUii,m,imk1L,m1hm,m1、ummhmm1m,m1um1,mUm1,m1Lanczos方法Lanczos方法是求解大规模稀疏对称矩阵端部特征问题的一种常用的正交投影方法。它在Krylov子空间上对对称矩阵采用Rayleign-Ritz方法，得到某些特征值和特征向量的近似。基本思想是给定一初始向量，逐步地构造出由该初始向量和对称阵生成
11、的Krylov子空间的标准正交基。通过简单的三项递推公式将大规模对称阵投影为小规模对称三对角阵，然后用此三对角阵的特征对来得出原始矩阵的近似特征对。由于三对角阵好的结构和小的维数，在准确运算下，变。Lanczos算法:(1)计算r0bAx000r,r(2)计算wjAvjj1jV，其中当1时jvj10(3)计算jwj,vjjjV(4)计算jjw,wj120，则置mj转（5），否则置(5)1,若j置Tmtridiagi,i1,i1,Vm转（2）v1丄，v，计算m11yTme(6)计算xmX0VmymLanczos双正交化方法在双正交化过程中，取KmA,r0sparer0,Ar0,L,Am1r0TO
12、OTOTm10LmA,rspanr,Ar丄，Ar容易看出A和八在其中扮演对偶的角色，此方法特别适用于需要求解两个系数矩阵分别是A和at的方程组.基于Lanczos双正交化过程的双共轭梯度法BiCG算法:(1)计算r0bAx0，选取rt0使得r0,rt00，置方向向量rt0，并置m=0(2)mm：mmr,rt.As,stm1m与冋量xxmmrmAs，mmT丄mrtrtmAt,如果xm1满足精度要求,则停止(3)计算参数mm1m,rt，与冋量sr置m=m+1,转(2)CG方法CG法用来解对称且正定方程组十分有效，但若是拿来解非对称或是非正定的线性方程组则会发生中断。它是借由迭代的方式产生一序列的方
13、向向量用来更新迭代解以及残向量，虽然产生的序列会越来越大，但是却只需要存储少数的向量。当系数矩阵A相当大而且稀疏，此时CG法几乎就是高斯消去法。CG法理论上虽然保证最多n步能解出线性方程组Axb的解，但是若系数矩阵是病态的，此时累进误差会让CG法在n步后无法求得充分精确的近似解。CG算法：(1) 计算r0bAx0，选取s0r0，置j0(2) 计算参数jrj,rjAsj,sj,更新向量xj1xjsj与残向量j1jjrrjAs，若xj满足精度要求，则停止(3) 计算jirj1,rj1rj,rj,sj1rj1jisj，置jj1，转(2)CG法是解正定对称线性方程组最有效的方法之一，该方法充分利用了矩
14、阵A的稀疏性，每次迭代的主要计算量是向量乘法。GMRES方法GMR0S法要求系数矩阵A是非奇异，非对称的n维方阵。GMRES算法利用Arnoldi变换构造一正交基vvz,l,琳来表示Krylov子空间m。GMRES法把方程组的求解化为一个极小问题的求解，不去直接求x1,转而去解此极小问题，这是GMRE方法的独到之处。z|bAz|2|rAVmym|2|v1AVmym|2Vm1e1Hmym2|e1Hmym|2GMRES算法的收敛性完全取决于系数矩阵A的特征值的性质。GMRES算法：(1) 计算r0bAx0,r,r彳，v1r，置j1(2) 计算wjAvj(3) 依次对i1,2,L,j，计算hjwj,vi与wjwjhjv，(4) 计算hj1,j，若hj1,j0，则置mj，转(6)(5) 计算vj1，若jm,则置jj1，转(2)求ymargmin|e1Hm2，计算xmx0Vmym求解最小二乘问题yargmine1Hmz?的算法：(1令gi,i1(2) 计算h2h
