用共轭梯度法求解最小二乘问题
摘要  本文先讨论了求解对称正定线性方程组的共轭梯度法.然后对系数矩阵列满秩的线性方程组运用正则化方法将其转化为对称正定线性方程组后再运用实用共轭梯度法进行求解，最后举例并通过Matlab程序实现其结果.
关键词  共轭梯度法；正则化方法；最小二乘问题；Krylov子空间
1  引言
在实际的科学与工程问题中，常常将问题归结为一个线性方程组的求解问题，而求解线性方程组的数值解法大体上可分为直接法和迭代法两大类.直接法是指在没有舍入误差的情况下经过有限次运算可求得方程组的精确解的方法.因此，直接法又称为精确法.迭代法则是采取逐次逼近的方法，亦即从一个初始向量出发，按照一定的计算格式，构造一个向量的无穷序列,其极限才是方程组的精确解，只经过有限次运算得不到精确解.当线性方程组的系数矩阵为对称正定矩阵时，我们常用共轭梯度法（或简称CG法）求解，目前有关的方法与理论已经相当成熟，并且已成为求解大型稀疏线性方程组最受欢迎的一类方法.
2  最小二乘问题
定义1[1] 给定矩阵，列满秩及向量，确定使得
.
该为问题称为最小二乘问题，简记为LS（Least Squares）问题，其中称为残向量.
最小二乘问题的解又可称为线性方程组
，
的最小二乘解，即在残向量的2范数最小的意义下满足线性方程组
，.
3  共轭梯度法
考虑线性方程组
的求解问题，其中A是给定的n阶对称正定矩阵，b是给定的n维向量，是待求解的n维向量.为此,定义二次泛函
.
定理1[1] 设A对称正定,求方程组的解，等价于求二次泛函的极小点.
    定理1表明，求解线性方程组问题就转化为求二次泛函的极小点问题.求解二次函数极小值问题，通常好像盲人下山那样，先给定一个初始向量，确定一个下山方向，沿着经过点而方向为的直线一个点
，
使得对所有实数有
，
即在这条直线上使达到极小.然后从出发，再确定一个下山的方向，沿着直
线再跨出一步，即到使得在达到极小：          .
重复此步骤，得到一串
和 ，
称为搜索方向，为步长.一般情况下，先在点下山方向，再在直线上确定步长使
最后求出.然而对不同的搜索方向和步长，得到各种不同的算法.
由此，先考虑如何确定.设从出发，已经选定下山方向.令
                 
        ，
其中.由一元函数极值存在的必要条件有
所确定的即为所求步长，即
.
步长确定后，即可算出
.正则化定义
此时，只要，就有
                           
即.
再考虑如何确定下山方向.易知负梯度方向是减小最快的方向，但简单分析就会发现负梯度方向只是局部最佳的下山方向，而从整体来看并非最佳.故采用新的方法寻求更好的下山方向——共轭梯度法.
定义2[2] 若n维非零向量满足
其中为n阶对称正定矩阵，则称与是相互共轭（共轭）的.
下面给出共轭梯度法的具体计算过程:
给定初始向量，第一步仍选用负梯度方向为下山方向，即，于是有
.
对以后各步，例如第k+1步（k1）,下山方向不再取，而是在过点由向量和所张成的二维平面
内出使函数下降最快的方向作为新的下山方向.考虑在上的限制：
                       
            .
计算关于的偏导得：
其中最后一式用到了，这可由的定义直接验证.令
，
即知在内有唯一的极小值点
，
其中和满足
由于必有，所以可取
作为新的下山方向.显然，这是在平面内可得的最佳下山方向.令，则可得
注：这样确定的满足，即与是相互共轭的.
总结上面的讨论，可得如下的计算公式：
，      ，
                    ，
，      .
在实际计算中，常将上述公式进一步简化，从而得到一个形式上更为简单而且对称的计算公式.首先来简化的计算公式：
.
因为在计算是已经求出，所以计算时可以不必将代入方程计算，而是从递推关系得到.
再来简化和的计算公式.此处需要用到关系式
    .
从而可导出
，
    .
由此可得

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。