超定方程的求解、最小二乘解、Ax=0、Ax=b的解，求解齐次方程组，求解非齐次方程组（推导十分详细）

本篇主要介绍的是超定方程组的求解，如果你不想看繁琐的推导过程，你可以直接看红字部分的结论！

对于方程 A x = 0 \bm A \bm x = 0 Ax=0，在我们实际的使用中，多数情况下只考虑方程数量多于未知元素的情形——超定方程组。

通过数学表示，可以将超定方程表示为： A x = 0 \bm A \bm x = 0 Ax=0， A \bm A A是 m × n m \times n m×n，列满秩，且 m > n m > n m>n

第一种解法:（求导） 首先，要求解 A x = 0 \bm A \bm x = 0 Ax=0，我们可以想象当你方程个数多于未知数时，一般就不存在精确解了。

A x = 0 \bm A \bm x = 0 Ax=0 存在精确解的条件是：rank( A \bm A A) < n n n

既然不存在精确解，那么我们就可以找一组近似解 x + \bm x^+ x+使得: x + = arg min ⁡ ∥ A x ∥ 2 (1) \bm x^+ = \argmin \|\bm A \bm x\|^2 \tag1 x+=argmin∥Ax∥2(1)

显然，这种思路是正确，既然我们不能得到精确的解，那么我们就找一组最符合情况的解，也就是使得（1）式最小的 x \bm x x。

要想使得（1）式最小，很显然， x = 0 \bm x=0 x=0是它的解。但是多数情况下，我们对0解没有兴趣，我们想要的是非零解。

那么，对于（1）式，我们就不能任由它肆意的减小，必须给它加一些限制，让它在满足一个条件的情况下获得最小的 x + \bm x^+ x+。于是就想到既然不要0解，那么就要求 x \bm x x不能为零。于是可以构建一个带约束的最小二乘问题： x + = arg min ⁡ ∥ A x ∥ 2 , subject to ∥ x ∥ 2 = 1 (2) \bm x^+ = \argmin \|\bm A \bm x\|^2, \text{subject to} \|\bm x\|^2=1 \tag{2} x+=argmin∥Ax∥2,subject to∥x∥2=1(2)

如果 x \bm x x是方程 A x = 0 \bm A\bm x=0 Ax=0的一个解，那么 k x k\bm x kx显然也是( k k k是任意标量)，所以就可以限制 ∥ x ∥ = 1 \|\bm x\|=1 ∥x∥=1

对于（2）式这种带约束的优化问题，可以通过拉格朗日乘数法构建无约束优化： L ( x , λ ) = ∥ A x ∥ 2 + λ ( 1 − ∥ x ∥ 2 ) = x T A T A x + λ ( 1 − x T x ) (3) L(\bm x,\lambda)=\|\bm A\bm x\|^2+\lambda(1-\|\bm x\|^2)=\bm x^T\bm A^{T} \bm A \bm x+\lambda(1-\bm x^T\bm x) \tag3 L(x,λ)=∥Ax∥2+λ(1−∥x∥2)=xTATAx+λ(1−xTx)(3)

为了获得 L ( x , λ ) L(\bm x,\lambda) L(x,λ)的极值，可以分别对 x \bm x x和 λ \lambda λ求偏导数： ∂ L ( x , λ ) ∂ x = 2 A T A x − 2 λ x (4) \frac{\partial L(\bm x,\lambda)}{\partial \bm x} = 2\bm A^T\bm A\bm x - 2\lambda \bm x \tag 4 ∂x∂L(x,λ)​=2ATAx−2λx(4) ∂ L ( x , λ ) ∂ λ = 1 − x T x = 0 (5) \frac{\partial L(\bm x,\lambda)}{\partial \lambda}= 1-\bm x^T\bm x =0\tag 5 ∂λ∂L(x,λ)​=1−xTx=0(5)

令（4）式为0，得 A T A x = λ x (6) \bm A^T\bm A\bm x=\lambda\bm x \tag 6 ATAx=λx(6)

通过（6）式可以知道，要想获得 L ( x , λ ) L(\bm x,\lambda) L(x,λ)的极值，就必须使得 x , λ \bm x,\lambda x,λ满足（6）。观察不难发现， λ , x \lambda,\bm x λ,x分别是 A T A \bm A^T\bm A ATA的特征值和特征向量。

A T A \bm A^T \bm A ATA的特征值和特征向量很多，而且都满足（6）式子，那么究竟哪一个特征值和特征向量可以使（2）式取得极小值呢？ ∥ A x ∥ 2 = x T A T A x = x T λ x = λ x T x = λ (7) \|\bm A \bm x\|^2 = \bm x^T \bm A^T\bm A \bm x=\bm x^T\lambda\bm x = \lambda\bm x^T\bm x = \lambda \tag 7 ∥Ax∥2=xTATAx=xTλx=λxTx=λ(7)

不妨来看一下（7）式的推导，我们已经知道 A T A \bm A^T \bm A ATA的特征值和特征向量中的一个会使得（2）式子取得极小值，所以（7）式的推导就用上了特征值和特征向量的性质，也就是（6）式： A T A x = λ x \bm A^T \bm A \bm x=\lambda\bm x ATAx=λx，另外 x T x = 1 \bm x^T \bm x =1 xTx=1。

到目前为止，答案很显然了，最小的 λ \lambda λ的最小值就对应 ∥ A x ∥ 2 \|\bm A\bm x\|^2 ∥Ax∥2的最小值。

所以，对于超定方程 A x = 0 \bm A\bm x =0 Ax=0的解就是 A T A \bm A^T \bm A ATA最小特征值对应的特征向量。

第二种解法（SVD分解） 对于超定方程组 A x = 0 \bm A \bm x = 0 Ax=0，依然如前述一样，构建一个有约束的优化问题： arg min ⁡ ∥ A x ∥ , subject to ∥ x ∥ = 1 (8) \argmin\|\bm A \bm x\|,\text{subject to}\|x\|=1 \tag 8 argmin∥Ax∥,subject to∥x∥=1(8)

对 A \bm A A进行SVD分解获得： A = U D V T (9) \bm A = \bm U\bm D \bm V^T \tag 9 A=UDVT(9)

将（9）式子带入（8）式，得 arg min ⁡ ∥ A x ∥ = arg min ⁡ ∥ U D V T x ∥ = arg min ⁡ ∥ D V T x ∥ (10) \argmin\|\bm A\bm x\|=\argmin\| \bm U\bm D \bm V^T \bm x\|=\argmin\|\bm D\bm V^T\bm x\| \tag{10} argmin∥Ax∥=argmin∥UDVTx∥=argmin∥DVTx∥(10)

之所以可以去掉 U \bm U U，是利用了正交矩阵的保范性。 ∥ U D V T x ∥ = ∥ D V T x ∥ ， ∥ V T x ∥ = ∥ x ∥ \|\bm U\bm D \bm V^T \bm x\|=\|\bm D\bm V^T\bm x\|，\|\bm V^T\bm x\| = \|\bm x\| ∥UDVTx∥=∥DVTx∥，∥VTx∥=∥x∥

这里可以令: y = V T x (11) \bm y = \bm V^T\bm x \tag{11} y=VTx(11)

则（10）式就等价于： arg min ⁡ ∥ D y ∥ (12) \argmin \|\bm D \bm y\| \tag{12} argmin∥Dy∥(12)

那么问题就变成了，在 ∥ y ∥ = 1 \|\bm y\|=1 ∥y∥=1的条件下最小化 ∥ D y ∥ \|\bm D \bm y\| ∥Dy∥

矩阵 D \bm D D是由 A \bm A A矩阵SVD分解的特征值组成的对角矩阵，我们假设对角矩阵的特征值按照降序排列，那么势必最后一个特征值是最小。所以当我们的 y = ( 0 , 0 , ⋯   , 1 ) \bm y=(0,0,\cdots,1) y=(0,0,⋯,1)时不但满足 ∥ y ∥ = 1 \|\bm y\|=1 ∥y∥=1，而且还可以使得 ∥ D y ∥ \|\bm D\bm y\| ∥Dy∥最小。

如果你不理解。为什么 y = ( 0 , 0 , ⋯   , 1 ) \bm y=(0,0,\cdots,1) y=(0,0,⋯,1)，你可以自己拿一个降序排列的对角矩阵试一下

那么，根据（11）式可知： x = V y (13) \bm x = \bm V\bm y \tag{13} x=Vy(13)

而 V \bm V V是矩阵 A \bm A A的SVD分解之后特征向量组成的矩阵，每一个列都是一个特征向量，根据前面得到的 y = ( 0 , 0 , ⋯   , 1 ) \bm y=(0,0,\cdots,1) y=(0,0,⋯,1)，那么 x \bm x x就是 V \bm V V的最后一列。

所以，超定方程 A x = 0 \bm A\bm x =0 Ax=0的解，就是对 A \bm A A进行SVD分解之后的最小特征值对应的特征向量。

在求导的方法中，我们得到的是 A T A \bm A^T \bm A ATA最小特征值对应的特征向量，这与SVD分解方法道理是一样的，SVD求 V \bm V V也就是通过 A T A \bm A^T\bm A ATA

对于 A x = b \bm A \bm x = \bm b Ax=b

依然有多种推导方法，这里我就介绍SVD分解的方法吧！

主要是我懒，不想再推导了，哈哈

有了前面的铺垫，问题就变得简单很多了！

我们的目标是最小化： arg min ⁡ ∥ A x − b ∥ (14) \argmin \|\bm A\bm x-\bm b\| \tag{14} argmin∥Ax−b∥(14)

由于，这里不再存在恒0解，所以就无需加入约束了。

首先对 A \bm A A进行SVD分解，然后带入（14）式，得： arg min ⁡ ∥ A x − b ∥ = arg min ⁡ ∥ U D V T x − b ∥ (15) \argmin \|\bm A\bm x-\bm b\| =\argmin \|\bm U\bm D\bm V^T\bm x-\bm b\| \tag{15} argmin∥Ax−b∥=argmin∥UDVTx−b∥(15)

根据正交矩阵保范性，（15）式可以进一步简化： arg min ⁡ ∥ U D V T x − b ∥ = arg min ⁡ ∥ D V T x − U T b ∥ (16) \argmin \|\bm U\bm D\bm V^T\bm x-\bm b\|=\argmin\|\bm D \bm V^T\bm x-\bm U^T\bm b\| \tag{16} argmin∥UDVTx−b∥=argmin∥DVTx−UTb∥(16)

令 y = V T x \bm y=\bm V^T\bm x y=VTx和 b ′ = U T b \bm b' =\bm U^T\bm b b′=UTb，于是（16）式变成了： arg min ⁡ ∥ D y − b ′ ∥ (17) \argmin\|\bm D\bm y-\bm b'\| \tag{17} argmin∥Dy−b′∥(17)

矩阵 D \bm D D是 A \bm A A矩阵SVD分解之后的特征值对应的对角矩阵。

显然 D y \bm D\bm y Dy离 b ′ \bm b' b′越近，那么（17）式就会越小。而离 b ′ \bm b' b′最近的向量 D y = ( b 1 ′ , b 2 ′ , ⋯   , b n ′ , 0 , ⋯   , 0 ) T \bm D\bm y=(b'_1,b'_2,\cdots,b'_n, 0,\cdots,0)^T Dy=(b1′​,b2′​,⋯,bn′​,0,⋯,0)T

这里由于特征值组成的对角矩阵，对角线上不一定全部非零，所以只有非零项才会对(17)式的最小值有影响。

于是就可以通过 y i = b i ′ d i , ( i = 1 , ⋯   , n ) y_i=\frac{b'_i}{d_i},(i=1,\cdots,n) yi​=di​bi′​​,(i=1,⋯,n)

这里 d i , ( 1 , ⋯   , n ) d_i,(1,\cdots,n) di​,(1,⋯,n)是 A A A矩阵SVD分解之后的特征值

这里的 n n n等于矩阵 A \bm A A的秩。

于是就得到了 y \bm y y y = ( b 1 ′ d 1 , b 2 ′ d 2 , ⋯   , b n ′ d n ) (18) \bm y=(\frac{b'_1}{d_1},\frac{b'_2}{d_2},\cdots,\frac{b'_n}{d_n}) \tag{18} y=(d1​b1′​​,d2​b2′​​,⋯,dn​bn′​​)(18) 则， A x = b \bm A \bm x = \bm b Ax=b的超定解为： x = V y (19) \bm x = \bm V\bm y \tag{19} x=Vy(19)

《Multiple View Geometry in Computer Vision》