数值分析学习笔记--最小二乘拟合

Google Doodles in memory of Akaike Hirotugu(赤池弘次), a Japanese statistician

如有疏漏，敬请指正。

如果一组数据点含有噪声或误差，无法同时满足某个特定函数，那么只能要求逼近函数尽量靠近数据点。按照误差最小的原则构造的逼近函数称为拟合函数。

误差可以用各种向量范数来定义

$$||Z-Y||_1=\sum_{i=1}^{m}|\varphi(x_i)-y_i|$$ $$||Z-Y||_2=\sqrt{\sum_{i=1}^m(\varphi(x_i)-y_i)^2}$$ $$||Z-Y||_{\infty}=\max_{1 \leq i \leq n}|\varphi(x_i)-y_i|$$

特别地，定义

$$Q=||Z-Y||_2^2=\sum_{i=1}^m(\varphi(x_i)-y_i)^2$$

为误差平方和，使误差平方和最小的方法称为最小二乘法。

最小二乘法的思想不仅可用于离散函数的拟合，也可用于连续函数的逼近。

多项式拟合

给定一组数据$\lbrace (x_i,y_i),i=1,2, \cdots ,m \rbrace$，当拟合函数$\varphi(x)$形如$a_0+a_1x+ \cdots +a_nx^n$时，拟合称为n次多项式拟合，即求$\alpha=(a_0,a_1, \cdots ,a_n)$使得

$$Q(\alpha)=\sum_{i=1}^{m}(a_0+a_ix_i+ \cdots +a_nx_i^n-y_i)^2$$

达到最小。

令最小值点$\alpha$满足

$$\frac{\partial Q}{\partial a_j}=2 \sum_{i=1}^{m} (a_0+a_1x_i+ \cdots +a_nx_i^n-y_i)x_i^j=0$$

其中$j=0,1, \cdots ,n$

整理得多项式拟合的法方程

$$\begin{bmatrix} m & \sum_{i=1}^{m} x_i & \cdots & \sum_{i=1}^m x_i^n \\ \sum_{i=1}^m x_i & \sum_{i=1}^{m} x_i^2 & \cdots & \sum_{i=1}^m x_i^{n+1} \\ \vdots & \vdots & & \vdots \\ \sum_{i=1}^m x_i^n & \sum_{i=1}^{m} x_i^{n+1} & \cdots & \sum_{i=1}^m x_i^{2n} \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_n \\ \end{bmatrix} = \begin{bmatrix} \sum_{i=1}^m y_i \\ \sum_{i=1}^m x_iy_i \\ \vdots \\ \sum_{i=1}^m x_i^n y_i \end{bmatrix}$$

这个方程的系数矩阵显然是对称的，此外还是半正定的。这个线性方程组也对任意$y_1,y_2, \cdots ,y_m$都有解。

在实际应用中，特别是进行高次多项式拟合时，系数矩阵很有可能是病态的，因此需要使用一些专门算法保证解的稳定性。

多项式拟合的方法可以推广到其它类型的函数拟合。

例如，对一组数据点作形如$\varphi (x)=ab^x$的函数拟合时，可以对数据作预处理，进行形如$ln \varphi(x) =lna+x lnb$的线性拟合，然后再求出a与b。

同样地，当进行双曲函数拟合$\varphi(x) =\frac{1}{a+bx}$时，不妨令

$$Q=\sum_{i=1}^{m} \left( a+bx_i-\frac{1}{y_i} \right)^2$$

如果进行有理函数拟合$\varphi(x)=\frac{a_0+a_1x+ \cdots +a_px^p}{1+b_1x+ \cdots +b_qx^q}$，则需要令

$$Q=\sum_{i=1}^{m}(a_0+a_1x_i+ \cdots +a_px_i^p-b_1x_iy_i- \cdots -b_qx_i^qy_i-y_i)^2$$

预处理的目的是提高求解效率，但是也有可能会降低求解精度。

矛盾方程组

给定一组数据$\lbrace (x_i,y_i),i=1,2, \cdots ,m \rbrace$，假设拟合函数有

$$\varphi (x)=\alpha_1 \varphi_1(x)+\alpha_2 \varphi_2(x)+ \cdots +\alpha_n\varphi_n(x)$$

的形式，其中$\varphi_i(x),1 \leq i \leq n$是已知参数，$\alpha_i ,1 \leq i \leq n$是未知参数。
令

$$A= \begin{bmatrix} \varphi_1(x_1) & \varphi_2(x_1) & \cdots & \varphi_n(x_1) \\ \varphi_1(x_2) & \varphi_2(x_2) & \cdots & \varphi_n(x_2) \\ \vdots & \vdots & & \vdots \\ \varphi_1(x_m) & \varphi_2(x_m) & \cdots & \varphi_n(x_m) \end{bmatrix}$$ $$\alpha = \begin{bmatrix} \alpha_1 \\ \alpha_2 \\ \vdots \\ \alpha_n \end{bmatrix} , Y= \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_m \end{bmatrix}$$

那么误差平方和

$$Q(\alpha)=\sum_{i=1}^{m}(\varphi(x_i)-y_i)^2=||A \alpha -Y ||_2^2$$

这样拟合问题就可以转化为：已知矩阵$A \in \mathbb{R}^{m \times n}$和向量$Y \in \mathbb{R}^m$，求向量$\alpha \in \mathbb{R}^n$使得$||A \alpha -Y||_2$最小。

当线性方程组$A \alpha=Y$有解$\alpha$时，拟合函数$\varphi(x)$经过所有数据点。无解时，称为矛盾方程组，使得$||A \alpha -Y||_2$最小当$\alpha$称为这个矛盾方程组的最小二乘解。

如果给定矩阵$A \in \mathbb{R}^{m \times n}$和向量$Y \in \mathbb{R}^m$，那么

• $\mathrm{rank} A^T A= \mathrm{rank} A^T$
• 线性方程组$A^T A \alpha = A^T Y$恒有解$\alpha$
• $||A \alpha -Y||_2$最小，当且仅当$A^T A \alpha = A^T Y$
• 使$||A \alpha -Y||_2$最小的$\alpha$是唯一的，当且仅当$\mathrm{rank}A=n$

线性方程组$A^T A \alpha = A^T Y$称为矛盾方程组$A \alpha =Y$的法方程。

通常情况下，若$m>>n$且$\mathrm{rank} A=n$，那么$A^T A$是正定的，矛盾方程组有唯一的最小二乘解。而有时$A^T A$是近似奇异的，这说明$\varphi_i(x),1 \leq i \leq n$之间存在一定的相关性，需要修改拟合函数$\varphi(x)$的形式。

如果重新考察多项式拟合问题的话，可以发现多项式拟合的过程与解矛盾方程组的过程本质上是一致的。