最小平方QR分解法(LSQR)详细.pdf

b一Y-P,U,(7-4)将(7-2)式和(7-4)式分别带入(7-1)式，并注意到矩阵U.V的正交性可得到方程(7-1)式的解:小16,，，x=L二二r(7-5)为了计算稳定，可以将表示解的级数(7-5)式中对应较小的奇异值去掉，即选择一个正数、、、、。)，取女三戮作为问题(7-l)式的解。百(T;奇异值分解法的具体实现过程及其误差分析可参见刘伊克(1988).刘家琦(1993)以及杨文采(1997)等人文章。第二节最小平方QR分解法(LSQR)LSQR方法是Paige和Saunders于1982年提出的一种特别适合求解系数矩阵为大型、稀疏矩阵线性方程组的方法。LSQR方法求解的思路是首先把任意系数矩阵方程化为系数矩阵为方阵的方程，然后利用Lanczos方法，求解方程的最小二乘解。由于在求解过程中用到QR因子分解法，因此这种方法叫做LSQR(LeastSquareQR-factorization)方法。在参阅文献(刘伊克，1988;刘家琦，1993)的基础上，本文对LSQR算法进行了详细的推导，给出了无阻尼和有阻尼情况>`的LSQR算法。一、Lanczos方法考虑方程Bx=b(7-6)其中，B为nxn实数对称方阵，x和b为n维列向量，x为待求未知量。求解方程(7-6)的Lanczos方法是一种子空间投影法·设v,，h，一气，为”维空间咋m个无关向量。令V,=[VI,v2,.二，0J为nxm矩阵，Km=spanIV,,V21...IV.}为v,，v2，⋯，v.张成的子空间。投影法的基本思想是寻找(7-6)式的近似解x，，使得:XmEKm(7-7)(Bxm-b)lv;,i=1,2,...,m令X,=气Y}l，其中Y}，为mxl的实向量，则(7-7)式等价丁(叮BV)Ym=叮b(7-8)假设(7-8)式有唯一解，则通过解(7-8)式可得Ym，从而得x},。如何选择v,，v2，，v，使(7-8)式中的矩阵嵘B礁具有较简单的形式，使求解(7-8)式在计算机上容易实现。「面给出构造向量v,，v2，⋯，v，的Lanczos方法，使得矩阵叮B珠具有三对角形式。v,=b1,(i,,,Q,=Ilblhv.=0对i=1,2,...w,=By，一戏v,-,(7-9)a,=v厂w,v,+i=(wi一a:v)/戏，.这里Q,十.使!Iv.十:II，如不存在这样的Q,+,则停止按(7-9)式构造的Lanczos向量v,，v2,⋯，v。是m个标准正交向量，记r几.仪.11月刀几1几.尸..几.-....风.an，fl.则(7-9)式等价丁B珠=礁凡十/j,(0,0,...,0,V,,,,)(7-10)卜面计算V',BV，的形式:叮BV一叮[V.T.一V,V.,T,+/j,.,叮(0,0,、二，0,v,.,)注意到叹V.=I和vm*i-1Km，叮v-，二0，所以，嵘BV,一T，从而(3)式化为:T.Y}=叮b=,8,(1,0，二，0)(7-I1)(7-11)式是容易求解的。这就是Lanczos方法。二、系数矩阵的对角化在Lanczos方法中，系数矩阵为对称方阵。当系数矩阵不为对称方阵时，就不能直接应用该方法，不过，我们可以将方程Ax=b化成一系数矩阵为对称方阵的等价方程，然后再应用Lanczos方法。在这一竹，我们先介绍系数矩阵的对角化问题。设AER`-，令﹁0AlBes一es矛0l(7-12)esJ易知，B二B伙满足Lanczos方法所需条科设W矢量为:W一[w,w2w2tr(7-13)且附j那=1。欠量T为:rn叫.oaloesU0es川Cl‘al0几IJ01weT，o刀a01ees-，0(7-14)es﹄川.小二二‘e001月es。二二，L︺T是二对角矩阵。假设:BW=W了(7-IS)rl0we0-es一es、(7-16)BWIALATu4OA+逸u2⋯0au,十f"lu,+I.、、0(7-17)。⋯av,十flv,-,0⋯akvk十八Vk_,比较(7-16)式与(7-17)式的对应项，有:a,v,=ATU,p"lu'.1=Av一“u,i=1,2,，二(7-18)a,+Iv,+一ATu+一A.,v,令初始矢量:其中:。>0,刀，，。，且卜，卜伽卜la设，叭卫.Uk=LulJ.，.吸.vk=IV,J.由〔7-18)式可知Uk、长为正交矩阵，即:U风=vkTVk=I(7-19)则(7-18)式可以写成矩阵形式:喻(八e,)=b(7-20)A气=Uk+IBk(7-21)A'Uk，一vk可+ak+IVk+Iek+I(22)其中尸八!al引!n几a0引1B。刀n(7-23)-l气Ulwe︸二︸，a‘es0二︸，LOQA一、*+、、，日5由(7-21)，有A=Uk.,凡叮(7-24)同理，可以把A化成上双对角矩阵形式。令矩阵B:厂0才.B.-..A(7-25).o