求解线性方程组(2)

线性方程组的最小范数解

上一篇博文介绍了线性方程组的情况之一，即未知数数量小于方程个数的情况，介绍了最小二乘法，在本文中将介绍线性方程组的另一种情况，即方程个数小于未知数数量的情况，此时方程组有无限多的解，但是最接近原点的解，即范数最小的解只有一个，也就是这里将会介绍的线性方程组的最小范数解。

考虑线性方程组\(Ax=b\)，其中$A\in R^{m*n},m\le n$，要寻找其最小范数解，即相当于求解下列最优化问题：

$$\begin{align*} minimize\ ||x|| \\ subject\ to\ Ax=b \end{align*}$$

这个问题属于等式约束的最优化问题，可以利用拉格朗日乘子法求解，在这里我们介绍另外一种方法。

先给出结论，该方程组的最小范数解为$x^{*}=A^{T}(AA^{T})^{-1}b$，下面给出证明：

$$||x||^{2}=||(x-x^{*})+x^{*}||^{2}\\ =||x-x^{*}||^{2}+||x^{*}||^{2}+2x^{*T}(x-x^{*})$$

令$x^{*}=A^{T}(AA^{T})^{-1}b$代入上式最右边项可以得到$2x^{*T}(x-x^{*})=0$，于是$||x||^{2}=||x-x^{*}||^{2}+||x^{*}||^{2}$，$||x^{*}||^{2}$是一个定值，而当$x\neq x^{*}$时，$||x-x^{*}||^{2}>0$恒成立，因此可以得到$x=x^{*}$是该优化问题的唯一最小解，即最小范数解。 ##Kaczmarz算法 Kaczmarz算法是一种迭代求解最小范数解的算法，可以省去求解$(AA^{T})^{-1}$的步骤，使计算更为高效，假设$A\in R^{m*n}$，直接给出迭代公式如下： 在前$m$次迭代中，即$k=0,1,...,m-1$时，有：

$$x^{(k+1)}=x^{(k)}+\mu(b_{k+1}-a_{k+1}^{T}x^{(k)})\frac{a_{k+1}}{a_{k+1}^{T}a_{k+1}}$$

对于第$(m+1)$次迭代，重新使用$A$的第1行以及$b$的第1个元素，即

$$x^{(m+1)}=x^{(m)}+\mu(b_{1}-a_{1}^{T}x^{(m)})\frac{a_{1}}{a_{1}^{T}a_{1}}$$

每迭代m次便从头循环一次，$\mu$可以视为迭代算法的过程。可以证明得到在Kaczmarz算法中，如果$x^{(0)}=0$，则当$k\to \infty$时，$x^{(k)}\to x^{*}=A^{T}(AA^{T})^{-1}b$，详细证明过程在这里省略。

后面的文章还会介绍线性方程组的一般解法，伪逆等相关内容，To be continue…