数学-超定方程组求解

一、概念

什么是超定方程组？

超定方程组即为有效方程个数大于未知数个数的方程组，就像这样：

$$\left( \begin{array}{} {x_{11}}&{x_{12}}\\ {x_{21}}&{x_{22}}\\ {x_{31}}&{x_{32}}\\ {x_{41}}&{x_{42}}\\ {x_{51}}&{x_{52}} \end{array} \right) \left( \begin{array}{} a\\ b \end{array} \right) = \left( \begin{array}{} {y_1}\\ {y_2}\\ {y_3}\\ {y_4}\\ {y_5} \end{array} \right)$$

求$a,b$的值？

很明显，无解。所以采用最小二乘法求得最优解，就像下图¹这样：

二、最小二乘法原理

既然没办法使用一条直线连接所有的点，那么就选择一条直线，使得误差最小，损失函数设计如下：

$$Loss = \sum(f(x_i) - y_i)^2$$

假设拟合的直线函数为：

$$f(x) = ax + b$$

则代入到损失函数中为（其实4次方也行，但是求导后2次方刚好为1，妙啊，主要是为了损失取正数）：

$$Loss= \sum(ax_i + b - y_i)^2$$

求取误差最小的值，即为求对$a,b$偏导数为0的值，分别对$a,b$求偏导如下：

$$\left\{ \begin{array}{} \frac{\partial Loss}{\partial a} = 2 \sum(ax_i + b - y_i)x_i &= 0 \\ \frac{\partial Loss}{\partial b} = 2 \sum(ax_i + b - y_i) &= 0 \end{array} \right.$$

化简后为:

$$\left\{ \begin{array}{} \sum(ax_i^2 + bx_i) &= \sum x_iy_i \\ \sum(ax_i + b) &= \sum y_i \end{array} \right.$$

转化为矩阵形式为:

$$\left( \begin{array}{} {\sum x_{i}^2}&{\sum x_{i}}\\ {\sum x_{i}}&{\sum 1^2} \end{array} \right) \left( \begin{array}{} {a}\\ {b} \end{array} \right) = \left( \begin{array}{} {\sum x_{i}y_i}\\ {\sum y_i} \end{array} \right)$$

化简：

$$A^TAp = A^TB$$

其中A为(注：这里认为b的系数为1)：

$$\left( \begin{array}{} {x_{1}}&{1}\\ {x_{2}}&{1}\\ {x_{3}}&{1}\\ {x_{4}}&{1}\\ {x_{5}}&{1} \end{array} \right )$$

p为：

$$\left( \begin{array}{} {a}\\ {b} \end{array} \right )$$

B为：

$$\left( \begin{array}{} {y_1}\\ {y_2}\\ {y_3}\\ {y_4}\\ {y_5} \end{array} \right )$$

故而p的求解为：

$$p = (A^TA)^{-1} A^T B$$

注：此公式可以通用。

参考文献

¹. 如何理解最小二乘法？ ↩