求解线性方程组(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…

技术

2018 · 07 · 21