求解线性方程组(1)

最小二乘分析

在本文中将讨论线性方程组中的一种情况的求解，即考虑线性方程组

Ax=bAx=b

其中，A∈Rm∗n,b∈Rm,m≥n,rank(A)=nA\in R^{m*n},b\in R^{m},m\ge n,rank(A)=n，在这种情况下，未知数的数量小于方程的数量，所以在很大可能上bb不在AA的值域空间中，即方程组无解，但是此时可以得到该线性方程方程的最小二乘解，即存在x∗x^{*}使得对于所有的x∈Rnx\in R^{n}都有

∣∣Ax−b∣∣2≥∣∣Ax∗−b∣∣2||Ax-b||^{2}\ge ||Ax^{*}-b||^{2}

即称x∗x^{*}为该线性方程的最小二乘解，当bb在AA的解空间中时，x∗x^{*}自然就是该方程的解，最小二乘解可以通过以下公式直接计算出来：

x∗=(ATA)−1ATbx^{*}=(A^{T}A)^{-1}A^{T}b

证明过程如下： 构造目标函数

f(x)=∣∣Ax−b∣∣2=(Ax−b)T(Ax−b)=12xT(2ATA)x−xT(2ATb)+bTbf(x)=||Ax-b||^{2}\\ =(Ax-b)^{T}(Ax-b)\\ =\frac{1}{2}x^{T}(2A^{T}A)x-x^{T}(2A^{T}b)+b^{T}b

显然函数ff为二次型函数，由于rank(A)=nrank(A)=n，因此该二次型为正定二次型，利用局部极小点的一阶必要条件可以得到极小点满足

∇f(x)=2ATAx−2ATb=0\nabla f(x)=2A^{T}Ax-2A^{T}b=0

该方程的唯一解为x∗=(ATA)−1ATbx^{*}=(A^{T}A)^{-1}A^{T}b，即为最小二乘解，最小二乘法对于直线拟合等应用是很方便的算法。##递推最小二乘法 上一节介绍了最小二乘法，我们可以用其来做直线拟合，如果要在拟合的数据中增加几组数据可以通过递推最小二乘法的方式来进行，即根据上次拟合的结果做部分修正即可，即利用上次拟合得到的最小二乘解x∗x^{*}来得到数据点增加后的最小二乘解x∗x^{*}。

某个优化问题为了寻找合适的xx，使得∣∣A0x−b(0)∣∣2||A_{0}x-b^{(0)}||^{2}最小，已知该问题的解为x(0)=G0−1A0Tb(0)x^{(0)}=G_{0}^{-1}A_{0}^{T}b^{(0)}，其中G0=A0TA0G_{0}=A^{T}_{0}A_{0}，如果增加了新的数据，用矩阵A1A_{1}和向量b1b_{1}来表示，那么这个问题即为寻找xx使得

∣∣[A0A1]x−[b(0)b(1)]∣∣2|| \begin{bmatrix} A_{0}\\A_{1} \end{bmatrix}x-\begin{bmatrix} b^{(0)}\\b^{(1)} \end{bmatrix}||^{2}

达到最小 其迭代公式为：

G1=G0+A1TA1x(1)=x(0)+G1−1A1T(b(1)−A1x(0))G_{1}=G_{0}+A_{1}^{T}A_{1}\\ x^{(1)}=x^{(0)}+G_{1}^{-1}A_{1}^{T}(b^{(1)}-A_{1}x^{(0)})

证明过程暂略，在一般情况下的迭代公式为：

Gk+=Gk+Ak+1TAk+1x(k+1)=x(k)+Gk+1−1Ak+1T(b(k+1)−Ak+1x(k))G_{k+}=G_{k}+A_{k+1}^{T}A_{k+1}\\ x^{(k+1)}=x^{(k)}+G_{k+1}^{-1}A_{k+1}^{T}(b^{(k+1)}-A_{k+1}x^{(k)})

对于线性方程组的求解，后面还将会介绍最小范数解和一般情况下的解法，以及伪逆等知识，To be continue…

#代码 & 数学