Krylov迭代法QR分解

《Krylov迭代法QR分解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数值模拟导论-第六讲Krylov子空间矩阵求解方法雅克比·怀特感谢DeepakRamaswamy,MichalRewienski,KarenVeroyandJacobWhite概述常规的子空间极小化算法——回顾学过的正交化和投射定理GCR算法－krylov-子空间－对称矩阵的简化－收敛条件回顾特征值和特征向量－范数和谱半径－谱映射定理GG{}w,⋅⋅⋅,w0k−1任意的子空间方法任意的子空间方法近似的解Mx＝b选择一个k维的子空间GG可以近似为向量{ww01,,⋅⋅⋅k−}的和k−1kG⇒=x∑αiiwi=0SM

2、A-HPC©2003MITGGGkkrxMx=b++−MxM...+=xMb1122NN任意子空间方法最小残向量kk·残向量定义为rbM=−xk−1k−1如果kGkkGxw=⇒∑αiirbM=−′x=−bM∑αiiwαsii=0i=0′残向量最小化的思路为：取αis，最小化式：Tkk−−11kk2Tk⎛⎞G⎛⎞GrrrbM≡=()()⎜⎟−∑∑ααiiwbM⎜⎟−iiw2⎝⎠ii==00⎝⎠SMA-HPC©2003MIT任意子空间方法最小残向量算法GGGG如果(Mwij)(Mw)=0或者(Mwi)正交于(Mwj)

3、，那么我22Gk们将很容易计算出rbM=−∑αiiw的最小值。22GGTGG如果()Mpij(Mp)=0或者(Mwi)于(Mwj)非正交GG那么要建立一组正交的向量{pp01,,⋅⋅⋅k−}使向量空间GGGGT＝向量空间{}ww01,,⋅⋅⋅k−并且()Mpij(Mp)=0，i≠jSMA-HPC©2003MIT任意子空间方法最小残向量运算步骤GG给定M，b并且一组搜索方向{}ww01,,⋅⋅⋅k−1）通过将Mws′正交化生成pG′sjjTk−1(Mw)()Mpjiforj＝0tok－1pjj=−wp∑Tii=0(

4、)Mpii()Mpk2）解计算xr的最小值TT0ikk−−11(rM)()p(rM)()pkiix==∑∑TTppiiii==00()Mpii()Mp()Mpii()MpSMA-HPC©2003MIT任意子空间方法最小残向量图示计算步骤′1）正交化Mwsj2）解计算r的最小值SMA-HPC©2003MIT任意子空间方法最小化算法00rbA=−xforj＝0tok－1pw=jjfori＝0toj-1Tpj←−pMjji(pM)()ppi正交搜索方向1p←pjTj标准化向量()Mpjj()MpTjjj+1xxrM=+

5、()(pjj)p更新结果Tjjj+1rrrM=+()(pj)Mpj更新残向量SMA-HPC©2003MIT任意子空间方法子空间的选择标准GG选择ww,,⋅⋅⋅的标准01k−GG对所有在空间{,,}ww⋅⋅⋅中的01k−k−1任意α′s，bMxbk=MwG的值都很小i−−∑αiii=0GG−1当kN≺≺时Ab≈在向量空间{,,}ww01⋅⋅⋅k−kGG一种选择，单位向量，xee∈{1,⋅⋅⋅k}向量空间如果k＝N进行QR分解如果k

6、T求f()xx=−Mxxb的最小值，其中假设M=M（对称2T矩阵）并且xMx>0−1∇=xfxMxbxMb()−⇒=推导出x最小化f.GG01k−取向量空间{}w01,,⋅⋅⋅wkx−=∇{fx(),,⋅⋅⋅∇xfx()}这便是f的最快下降方向，但f并不是残余值。T这种方法不能用于非对成矩阵，和不满足xMx>0的情况SMA-HPC©2003MIT子空间的选择任意子空间方法krylov子空间01k−01k−注意：向量空间{∇⋅xxfx(),,⋅⋅∇fx()}＝向量空间{rr,,⋅⋅⋅}GG01k−如果：向量空间{w

7、w01,,⋅⋅⋅k−}＝向量空间{rr,,⋅⋅⋅}k−1那么ki0rr=−∑αiMri=001k−00k−10并且向量空间{rr,,⋅⋅⋅}＝向量空间{rMr,,,⋅⋅⋅Mr}krylov子空间SMA-HPC©2003MITkrylov方法GCR算法GCP的第k步Tk(rM)()pk求解第k步搜索方向的步长α=kT()MpMkk()pTk(rM)()pkαk=T更新结果()MpMkk()pkk+1更新残向量rrM=−αpkkTk+1k(Mr)(Mp)kk++11jp=−rp∑Tj计算新的正交搜索方向j=0()Mp

8、jj()MpSMA-HPC©2003MITkrylov方法GCR算法k步逼近的计算耗时Tk(rM)()pk向量内积，O(n)矩阵向量的内积α=kT()MpMkk()pkk+1xxp=+αkkO(n)如果是稀疏矩阵需要O(n)步运算kk+1向量加，O(n)rrM=−αpkkkk+1rrM=−αkkpO(K)内积，总共需要O(nk)步运算如果M是稀疏矩阵，当用k步来逼近n时，