《GMRES隐式格式.pdf》由会员分享，可在线阅读，更多相关《GMRES隐式格式.pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1GMRES 方法GMRES（generalize minimal residuals，广义极小剩余）方法以 Galerkin原理为基础，首先建立 Krylov 子空间的一组标准正交基，然后在 Krylov 子空间中利用最小二乘法得到方程 Ax=b 解向量。Krylov 子空间 Kn为由向量 b,Ab,.,An1b 张成的子空间，我们希望在 Krylov 子空间 Kn中找到一个向量 x 使得|Ax b|达到极小。直接使用 b,Ab,.,An1b 作为基向量的计算是复杂的，我们希望建立一组基向量q1,q2,.,qn，满足正交归一化条件。令 Qn=q1|q2|.|qn，则向量 x 可以写成 Qny
2、 的形式，y 为 n 维向量。接下来将介绍 qn的构造方法和求|AQny b|极小值的方法。1.1阿诺尔迭代阿诺尔迭代可以构造 Krylov 子空间的一组标准正交基，同时将矩阵 A 用正交相似变换完全约化到海森伯格型，可以写成 A=QHQT或 AQ=QH，QQT=I。H=h11h12h1Nh21h22h1N.hN1,NhNN(1)考虑 AQ=QH 的前 n 列，有 AQn=Qn+1eHn，其中 Qn=q1|q2|.|qn，eHn是 H 的(n+1)n 左上角部分。eHn=h11h12h1nh21h22h1n.hn,n1hnnhn+1,n(2)AQn=Qn+1eHn可以写为Aq1|q2|.|qn
3、=q1|q2|.|qn+1h11h12h1nh21h22h1n.hn,n1hnnhn+1,n(3)方程组的第 n 列可以写为Aqn=h1nq1+hnnqn+hn+1,nqn+1(4)左乘向量 qTi,i=1,2,n，利用 qi的正交归一化条件有hin=qTiAqn(5)1由此，阿诺尔迭代算法为q1=b/|b|(6)m=1,2,N 1 迭代w=A qm(7)hl,m=(w,ql),l=1,2,m(8)e qm+1=w mXl=1hl,mql(9)hm+1,m=|e qm+1|,qm+1=e qm+1hm+1,m(10)1.2残差极小化方法我们已经构造了基向量 qi，下面的任务是在空间 Kn中求解
4、 J(y)=|AQny b|的极小化问题。由 AQn=Qn+1eHn，极小化问题转化为J(y)=|Qn+1eHny b|(11)进一步可以转化为J(y)=|eHny QTn+1b|(12)的极小化问题。由 QTn+1b=QTn+1q1|b|=|b|e1=e1，其中 =|b|,e1=(1,0,0,)T，则J(y)=|eHny e1|(13)我们希望进一步简化极小化的过程，使得计算量变小。如果我们在第 l 1步迭代后，对矩阵eHl1左乘一个正交阵，使得矩阵eHl1在(l1,l)位置的元素变为 0，有eRl1=Ql1eHl1=r11r12r1,l1r21r22r2,l1.rl2,l2rl2,l1rl
5、1,l10l(l1)(14)在完成第 l 次迭代后，左乘正交矩阵之前有Rl=r11r12r1,l1h1lr21r22r2,l1h2l.rl2,l2rl2,l1hl2,lrl1,l1hl1,l0hll0hl+1,l(l+1)l(15)2这时，如果将位于(l+1,l)处的元素变为 0，则需要对矩阵 Rl左乘正交矩阵Fl来完成Fl=1.1ClSlSlCl(l+1)(l+1)(16)其中Cl=rr2+h2,Sl=hr2+h2,r=hll,h=hl+1,l(17)由此可得eRl1=FlRl=QleHl(18)进一步J(y)=|eHny e1|=|Qn(eHny e1)|=|gneRny|(19)由此函数
6、 J(y)的最小二乘误差极为向量 gn的最后一个元素的绝对值，y 为方程eRny=gn去掉最后一行的解。1.3GMRES 算法的原始形式第一步，计算=|b|,q1=b/(20)第二步，m=1,2,kmax迭代w=A qm(21)hl,m=(w,ql),l=1,2,m(22)e qm+1=w mXl=1hl,mql(23)hm+1,m=|e qm+1|,qm+1=e qm+1hm+1,m(24)求 J(y)=|eHmy e1|的最小二乘解 ym，如果 miny|eHmy e1|/，则迭代结束。第三步Xk=Qkyk(25)31.4GMRES 算法的一般形式对方程 AX=b 进行预处理M1LAM1R
7、MRX=M1Rb(26)并给定解的初始猜值 X0M1LAM1RMRX M1LAM1RMRX0=M1Rb M1LAX0(27)M1LAM1RMR(X X0)=M1R(b AX0)(28)因此有AX=b(29)A=M1LAM1R(30)X=MR(X X0)(31)b=M1R(b AX0)(32)第一步，计算r0=b A X0,r1=M1Lr0,=|r1|,q1=r1/(33)第二步，m=1,2,kmax迭代w=A qm=M1L A M1R qm(34)hl,m=(w,ql),l=1,2,m(35)e qm+1=w mXl=1hl,mql(36)hm+1,m=|e qm+1|,qm+1=e qm+1hm+1,m(37)求 J(y)=|eHmy e1|的最小二乘解 ym，如果 miny|eHmy e1|/，则迭代结束。第三步Xk=MR(Xk X0)=Qkyk(38)Xk=X0+M1RQkyk(39)4