用共轭梯度法解最小二乘问题

PAGEPAGE1用共轭梯度法求解最小二乘问题摘要本文先讨论了求解对称正定线性方程组的共轭梯度法.然后对系数矩阵列满秩的线性方程组运用正则化方法将其转化为对称正定线性方程组后再运用实用共轭梯度法进行求解，最后举例并通过Matlab程序实现其结果.关键词共轭梯度法；正则化方法；最小二乘问题；Krylov子空间1引言在实际的科学与工程问题中，常常将问题归结为一个线性方程组的求解问题，而求解线性方程组的数值解法大体上可分为直接法和迭代法两大类.直接法是指在没有舍入误差的情况下经过有限次运算可求得方程组的精确解的方法.因此，直接法又称为精确法.迭代法则是采取逐次逼近的方法，亦即从一个初始向量出发，按照一定的计算格式，构造一个向量的无穷序列,其极限才是方程组的精确解，只经过有限次运算得不到精确解.当线性方程组的系数矩阵为对称正定矩阵时，我们常用共轭梯度法（或简称CG法）求解，目前有关的方法与理论已经相当成熟，并且已成为求解大型稀疏线性方程组最受欢迎的一类方法.2最小二乘问题定义1[1]给定矩阵，列满秩及向量，确定使得.该为问题称为最小二乘问题，简记为LS（LeastSquares）问题，其中称为残向量.最小二乘问题的解又可称为线性方程组，的最小二乘解，即在残向量的2范数最小的意义下满足线性方程组，.3共轭梯度法考虑线性方程组的求解问题，其中A是给定的n阶对称正定矩阵，b是给定的n维向量，是待求解的n维向量.为此,定义二次泛函.定理1[1]设A对称正定,求方程组的解，等价于求二次泛函的极小点.定理1表明，求解线性方程组问题就转化为求二次泛函的极小点问题.求解二次函数极小值问题，通常好像盲人下山那样，先给定一个初始向量，确定一个下山方向，沿着经过点而方向为的直线找一个点，使得对所有实数有，即在这条直线上使达到极小.然后从出发，再确定一个下山的方向，沿着直线再跨出一步，即找到使得在达到极小：.重复此步骤，得到一串和，称为搜索方向，为步长.一般情况下，先在点找下山方向，再在直线上确定步长使最后求出.然而对不同的搜索方向和步长，得到各种不同的算法.由此，先考虑如何确定.设从出发，已经选定下山方向.令，其中.由一元函数极值存在的必要条件有所确定的即为所求步长，即.步长确定后，即可算出.此时，只要，就有即.再考虑如何确定下山方向.易知负梯度方向是减小最快的方向，但简单分析就会发现负梯度方向只是局部最佳的下山方向，而从整体来看并非最佳.故采用新的方法寻求更好的下山方向——共轭梯度法.定义2[2]若n维非零向量满足其中为n阶对称正定矩阵，则称与是相互共轭（共轭）的.下面给出共轭梯度法的具体计算过程:给定初始向量，第一步仍选用负梯度方向为下山方向，即，于是有.对以后各步，例如第k+1步（k1）,下山方向不再取，而是在过点由向量和所张成的二维平面内找出使函数下降最快的方向作为新的下山方向.考虑在上的限制：.计算关于的偏导得：其中最后一式用到了，这可由的定义直接验证.令，即知在内有唯一的极小值点，其中和满足由于必有，所以可取作为新的下山方向.显然，这是在平面内可得的最佳下山方向.令，则可得注：这样确定的满足，即与是相互共轭的.总结上面的讨论，可得如下的计算公式：，，，，.在实际计算中，常将上述公式进一步简化，从而得到一个形式上更为简单而且对称的计算公式.首先来简化的计算公式：.因为在计算是已经求出，所以计算时可以不必将代入方程计算，而是从递推关系得到.再来简化和的计算公式.此处需要用到关系式.从而可导出，.由此可得，.从而有求解对称正定方程组的共轭梯度法算法如下：初值；whileifelseendend注：该算法每迭代一次仅需要使用系数矩阵做一次矩阵向量积运算.定理2[1]由共轭梯度法得到的向量组和具有如下基本性质：（1），（2），，（3），，（4），其中，通常称之为Krylov子空间.下面给出共轭梯度法全局最优性定理：定理3[1]用共轭梯度法计算得到的近似解满足或，其中，是方程组的解，是由所定义的Krylov子空间.定理2表明，向量组和分别是Krylov子空间的正交基和共轭正交基.由此可知，共轭梯度法最多n步便可得到方程组的解.因此，理论上来讲，共轭梯度法是直接法.然而实际使用时，由于误差的出现，使之间的正交性很快损失，以致于其有限步终止性已不再成立.此外，在实际应用共轭梯度法时，由于一般很大，以至于迭代次所耗费的计算时间就已经使用户无法接受了.因此，实际上将共轭梯度法作为一种迭代法使用，而且通常是是否已经很小及迭代次数是否已经达到最大允许的迭代次数来终止迭代.从而得到解对称正定线性方程组的实用共轭梯度法，其算法如下：初值whileifelseendend算法中，系数矩阵的作用仅仅是用来由已知向量产生向量，这不仅可以充分利用的稀疏性，而且对某些提供矩阵较为困难而由已知向量产生向量又十分方便的应用问题有益.4共轭梯度法求解最小二乘问题的正则化方程组（法方程组）定理4[1]当列满秩时，求最小二乘问题的解等价于解.应用共轭梯度法于对称正定方程组来求方程组，且列满秩的最小二乘解，即为Krylov子空间法中的正则化方法.由列满秩有对称正定，则方程组，存在唯一解.下面给出其实用共轭梯度法的详细算法且算法中不出现计算情形:初值whileifelseendend注：算法中采用了两次矩阵向量积来避免出现计算情形.算例编写实用共轭梯度法的Matlab程序求解方程组，其中,.解先建立conjgrad.m文件，内容如下:function[x]=conjgrad(A,b,x)A=[1-1;-11;2-2;-31];b=[1;2;3;4];x=rand(2,1);k=0;b=A'*b;m=A*x;r=b-A'*m;T=r'*r;Whilenorm(r)>1e-10*norm(b)k=k+1;ifk==1p=r;elseB=T/t;p=r+B*p;endn=A*p;w=A'*n;a=T/(p'*w);x=x+a*p;r=r-a*w;t=T;T=r'*r;end然后运行后得ans=-2.4167-3.2500即有方程组的数值解.而其精确解可由如下方法求得:，，则有，解得，即方程精确解为，故可验证通过Matlab程序求得的数值解满足精度要求.5总结本文首先给出最小二乘问题的定义，随后从盲人下山法开始讨论了共轭梯度法的具体推导过程及其相关性质与算法.继而重点给出正则化方法的实用共轭梯度算法并举例进行检验.最后，需要说明虽然正则化方法是求一般线性方程组，且列满秩的最小二乘解的一种方法且简单易行，但是也有许多不足之处，如时一般无解；形成时运算量大，中某些信息会丢失；当病态时其收