最小二乘法求解矛盾方程组
矛盾方程组：方程个数多于未知数个数，不能得到精确解析解。
使用最小二乘拟合得近似解。
例题，矛盾方程组 { x 1 − x 2 = 1 − x 1 + x 2 = 2 2 x 1 − 2 x 2 = 3 − 3 x 1 + x 2 = 4 \left\{\begin{matrix} x_1 – x_2 = 1 \\ -x_1 + x_2 = 2 \\ 2x_1-2 x_2 = 3 \\ -3x_1+ x_2 = 4 \end{matrix}\right. ⎩⎪⎪⎨⎪⎪⎧x1−x2=1−x1+x2=22x1−2x2=3−3x1+x2=4
A = [ 1 − 1 − 1 1 2 − 2 − 3 1 ] , b = [ 1 2 3 4 ] A=\begin{bmatrix}1 & -1\\-1 & 1\\2 & -2\\-3 & 1\end{bmatrix},b=\begin{bmatrix}1\\2\\3\\4\end{bmatrix} A=⎣⎢⎢⎡1−12−3−11−21⎦⎥⎥⎤,b=⎣⎢⎢⎡1234⎦⎥⎥⎤
A ⊤ A = [ 15 − 9 − 9 7 ] , A ⊤ b = [ − 7 − 1 ] A^{\top}A=\begin{bmatrix}15&-9\\-9&7\end{bmatrix},A^{\top}b=\begin{bmatrix}-7\\-1\end{bmatrix} A⊤A=[15−9−97],A⊤b=[−7−1]
最小二乘拟合多项式
将 n 个数据 ( x i , y i ) (x_i,y_i) (xi,yi) 代入 多项式 就得到 n 个方程和 m+1 个未知数的矛盾方程组：
{ a 0 + a 1 x 1 + a 2 x 1 2 + ⋯ + a m x 1 m = y 1 a 0 + a 2 x 1 + a 2 x 2 2 + ⋯ + a m x 2 m = y 2 ⋮ a 0 + a 2 x n + a 2 x n 2 + ⋯ + a m x n m = y 3 \left\{\begin{matrix} a_0 + a_1 x_1 + a_2 x_1^2 + \cdots + a_m x_1^m = y_1 \\ a_0 + a_2 x_1 + a_2 x_2^2 + \cdots + a_m x_2^m = y_2 \\ \vdots \\ a_0 + a_2 x_n + a_2 x_n^2 + \cdots + a_m x_n^m = y_3 \end{matrix}\right. ⎩⎪⎪⎪⎨⎪⎪⎪⎧a0+a1x1+a2x12+⋯+amx1m=y1a0+a2x1+a2x22+⋯+amx2m=y2⋮a0+a2xn+a2xn2+⋯+amxnm=y3
α = ( a 0 , a 1 , ⋯ , a m ) ⊤ \alpha = (a_0,a_1,\cdots,a_m)^{\top} α=(a0,a1,⋯,am)⊤
y = ( y 0 , y 1 , ⋯ , y m ) ⊤ y = (y_0,y_1,\cdots,y_m)^{\top} y=(y0,y1,⋯,ym)⊤
A ⊤ A = [ 1 1 1 ⋯ 1 x 1 x 2 x 3 ⋯ x n x 1 2 x 2 2 x 3 2 ⋯ x n 2 ⋯ x 1 m x 2 m x 3 m ⋯ x n m ] [ 1 x 1 x 1 2 ⋯ x 1 m 1 x 2 x 3 2 ⋯ x 2 m ⋮ 1 x n x n 2 ⋯ x n m ] = [ n ∑ i = 1 n x i ∑ i = 1 n x i 2 ⋯ ∑ i = 1 n x i m ∑ i = 1 n x i ∑ i = 1 n x i 2 ∑ i = 1 n x i 3 ⋯ ∑ i = 1 n x i m + 1 ⋮ ⋮ ⋮ ⋱ ⋮ ∑ i = 1 n x i m ∑ i = 1 n x i m + 1 ∑ i = 1 n x i m + 2 ⋯ ∑ i = 1 n x i 2 m ] \begin{aligned} A^{\top}A &=\begin{bmatrix} 1&1&1& \cdots &1\\ x_1&x_2&x_3&\cdots &x_n \\ x_1^2&x_2^2&x_3^2&\cdots &x_n^2 \\ \cdots \\ x_1^m&x_2^m&x_3^m&\cdots &x_n^m \end{bmatrix} \begin{bmatrix} 1& x_1 & x_1^2 & \cdots & x_1^m \\ 1& x_2 & x_3^2 & \cdots & x_2^m \\ \vdots\\ 1& x_n & x_n^2 & \cdots & x_n^m \\ \end{bmatrix}\\ &=\begin{bmatrix} n&\sum_{i=1}^n x_i &\sum_{i=1}^n x_i^2 & \cdots &\sum_{i=1}^n x_i^m\\ \sum_{i=1}^n x_i&\sum_{i=1}^n x_i^2 &\sum_{i=1}^n x_i^3 & \cdots &\sum_{i=1}^n x_i^{m+1}\\ \vdots &\vdots &\vdots& \ddots &\vdots\\\\ \sum_{i=1}^n x_i^m&\sum_{i=1}^n x_i^{m+1} &\sum_{i=1}^n x_i^{m+2} & \cdots &\sum_{i=1}^n x_i^{2m}\\ \end{bmatrix} \end{aligned} A⊤A=⎣⎢⎢⎢⎢⎡1x1x12⋯x1m1x2x22x2m1x3x32x3m⋯⋯⋯⋯1xnxn2xnm⎦⎥⎥⎥⎥⎤⎣⎢⎢⎢⎡11⋮1x1x2xnx12x32xn2⋯⋯⋯x1mx2mxnm⎦⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎢⎡n∑i=1nxi⋮∑i=1nxim∑i=1nxi∑i=1nxi2⋮∑i=1nxim+1∑i=1nxi2∑i=1nxi3⋮∑i=1nxim+2⋯⋯⋱⋯∑i=1nxim∑i=1nxim+1⋮∑i=1nxi2m⎦⎥⎥⎥⎥⎥⎤
A ⊤ y = [ 1 1 1 ⋯ 1 x 1 x 2 x 3 ⋯ x n x 1 2 x 2 2 x 3 2 ⋯ x n 2 ⋯ x 1 m x 2 m x 3 m ⋯ x n m ] [ y 0 y 1 y 2 ⋮ y m ] = [ ∑ i = 1 n y i ∑ i = 1 n y i x i ∑ i = 1 n y i x i 2 ⋯ ∑ i = 1 n y i x i m ] \begin{aligned} A^{\top}y &=\begin{bmatrix} 1&1&1& \cdots &1\\ x_1&x_2&x_3&\cdots &x_n \\ x_1^2&x_2^2&x_3^2&\cdots &x_n^2 \\ \cdots \\ x_1^m&x_2^m&x_3^m&\cdots &x_n^m \end{bmatrix} \begin{bmatrix}y_0\\y_1\\y_2\\\vdots \\y_m \end{bmatrix}\\ &=\begin{bmatrix} \sum_{i=1}^n y_i\\ \sum_{i=1}^n y_i x_i\\ \sum_{i=1}^n y_i x_i^2\\ \cdots \\ \sum_{i=1}^n y_i x_i^{m} \end{bmatrix} \end{aligned} A⊤y=⎣⎢⎢⎢⎢⎡1x1x12⋯x1m1x2x22x2m1x3x32x3m⋯⋯⋯⋯1xnxn2xnm⎦⎥⎥⎥⎥⎤⎣⎢⎢⎢⎢⎢⎡y0y1y2⋮ym⎦⎥⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎡∑i=1nyi∑i=1nyixi∑i=1nyixi2⋯∑i=1nyixim⎦⎥⎥⎥⎥⎤
可以看到 A ⊤ A A^{\top}A A⊤A 和 A ⊤ y A^{\top}y A⊤y 只与输入数据有关，因此可以解得 α = ( a 0 , a 1 , a 2 , ⋯ , a m ) \alpha=(a_0, a_1,a_2,\cdots , a_m) α=(a0,a1,a2,⋯,am) ，多项式表达式如下
P ( x ) = a 0 + a 1 x + a 2 x 2 + ⋯ + a m x m P(x)=a_0 + a_1x + a_2 x^2 + \cdots + a_m x^m P(x)=a0+a1x+a2x2+⋯+amxm
例题
| x i x_i xi | 1 | 2 | 3 | 4 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| y i y_i yi | 2 | 3 | 6 | 7 | 5 | 3 | 2 |
首先计算
| n n n | ∑ i = 1 7 x i \sum_{i=1}^7 x_i ∑i=17xi | ∑ i = 1 7 x i 2 \sum_{i=1}^7 x_i^2 ∑i=17xi2 | ∑ i = 1 7 x i 3 \sum_{i=1}^7 x_i^3 ∑i=17xi3 | ∑ i = 1 7 x i 3 \sum_{i=1}^7 x_i^3 ∑i=17xi3 |
|---|---|---|---|---|
| 7 | 31 | 179 | 1171 | 8147 |
| ∑ i = 1 7 y i \sum_{i=1}^7 y_i ∑i=17yi | ∑ i = 1 7 y i x i \sum_{i=1}^7 y_i x_i ∑i=17yixi | ∑ i = 1 7 y i x i 2 \sum_{i=1}^7 y_i x_i^2 ∑i=17yixi2 |
|---|---|---|
| 28 | 121 | 635 |
{ 7 a 0 + 31 a 1 + 179 a 2 = 28 31 a 0 + 179 a 1 + 1171 a 2 = 121 179 a 0 + 1171 a 1 + 8147 a 2 = 635 \left\{\begin{matrix} 7a_0 + 31a_1 + 179a_2 = 28 \\ 31a_0 + 179a_1 + 1171a_2 = 121 \\ 179a_0 + 1171a_1 + 8147a_2 = 635 \end{matrix}\right. ⎩⎨⎧7a0+31a1+179a2=2831a0+179a1+1171a2=121179a0+1171a1+8147a2=635
P ( x ) = − 1.3185 + 3.4321 x − 0.3864 x 2 P(x)=-1.3185 + 3.4321x – 0.3864x^2 P(x)=−1.3185+3.4321x−0.3864x2
正交多项式
正规方程组（法方程）不一定是线性方程组。
假设有 n 组数据 ( x i , y i ) (x_i, y_i) (xi,yi)， i = 1 , 2 , ⋯ , n i=1,2,\cdots,n i=1,2,⋯,n，那么误差函数表示为
L = ∑ i = 1 n [ a 0 φ 0 ( x i ) + a 1 φ 2 ( x i ) + ⋯ + a m φ m ( x i ) − y i ] 2 L = \sum_{i=1}^n [a_0 \varphi_0(x_i) + a_1 \varphi_2(x_i) + \cdots + a_m \varphi_m(x_i) – y_i]^2 L=i=1∑n[a0φ0(xi)+a1φ2(xi)+⋯+amφm(xi)−yi]2
目标是最小化误差函数，求误差函数关于参数 a 0 , a 1 , ⋯ , a m a_0,a_1,\cdots,a_m a0,a1,⋯,am的偏导数：
∂ L ∂ a 0 = 2 ∑ i = 1 n [ a 0 φ 0 ( x i ) + a 1 φ 2 ( x i ) + ⋯ + a m φ m ( x i ) − y i ] φ 0 ( x i ) = 0 ∂ L ∂ a 1 = 2 ∑ i = 1 n [ a 0 φ 0 ( x i ) + a 1 φ 2 ( x i ) + ⋯ + a m φ m ( x i ) − y i ] φ 1 ( x i ) = 0 ⋮ ∂ L ∂ a m = 2 ∑ i = 1 n [ a 0 φ 0 ( x i ) + a 1 φ 2 ( x i ) + ⋯ + a m φ m ( x i ) − y i ] φ m ( x i ) = 0 \frac{\partial L}{\partial a_0} = 2 \sum_{i=1}^n [a_0 \varphi_0(x_i) + a_1 \varphi_2(x_i) + \cdots + a_m \varphi_m(x_i) – y_i]\varphi_0(x_i) = 0\\ \frac{\partial L}{\partial a_1} = 2 \sum_{i=1}^n [a_0 \varphi_0(x_i) + a_1 \varphi_2(x_i) + \cdots + a_m \varphi_m(x_i) – y_i]\varphi_1(x_i) = 0\\ \vdots \\ \frac{\partial L}{\partial a_m} = 2 \sum_{i=1}^n [a_0 \varphi_0(x_i) + a_1 \varphi_2(x_i) + \cdots + a_m \varphi_m(x_i) – y_i]\varphi_m(x_i) = 0 ∂a0∂L=2i=1∑n[a0φ0(xi)+a1φ2(xi)+⋯+amφm(xi)−yi]φ0(xi)=0∂a1∂L=2i=1∑n[a0φ0(xi)+a1φ2(xi)+⋯+amφm(xi)−yi]φ1(xi)=0⋮∂am∂L=2i=1∑n[a0φ0(xi)+a1φ2(xi)+⋯+amφm(xi)−yi]φm(xi)=0
a 0 ∑ i = 1 n φ 0 ( x i ) φ k ( x i ) + a 1 ∑ i = 1 n φ 1 ( x i ) φ k ( x i ) + ⋯ + a m ∑ i = 1 n φ m ( x i ) φ k ( x i ) = ∑ i = 1 n y i φ k ( x i ) k = 0 , 1 , ⋯ , m a_0 \sum_{i=1}^n \varphi_0(x_i) \varphi_k(x_i) + a_1 \sum_{i=1}^n \varphi_1(x_i) \varphi_k(x_i) + \cdots+ a_m \sum_{i=1}^n \varphi_m(x_i) \varphi_k(x_i) =\sum_{i=1}^n y_i \varphi_k(x_i)\\ k = 0,1,\cdots,m a0i=1∑nφ0(xi)φk(xi)+a1i=1∑nφ1(xi)φk(xi)+⋯+ami=1∑nφm(xi)φk(xi)=i=1∑nyiφk(xi)k=0,1,⋯,m
其中， ∑ i = 1 n φ j ( x i ) φ k ( x i ) \sum_{i=1}^n \varphi_j(x_i) \varphi_k(x_i) ∑i=1nφj(xi)φk(xi) 表示 φ j ( x ) \varphi_j(x) φj(x) 和 φ k ( x ) \varphi_k(x) φk(x) 的卷积，简记为 ( φ j , φ k ) (\varphi_j, \varphi_k) (φj,φk)，如果 φ j ( x ) \varphi_j(x) φj(x) 和 φ k ( x ) \varphi_k(x) φk(x) 是正交关系，则它们的卷积为零，即 ∑ i = 1 n φ j ( x i ) φ k ( x i ) = 0 \sum_{i=1}^n \varphi_j(x_i) \varphi_k(x_i) = 0 ∑i=1nφj(xi)φk(xi)=0 。
a 0 ( φ 0 , φ k ) + a 1 ( φ 1 , φ k ) + ⋯ + a m ( φ m , φ k ) = ( f , φ k ) k = 0 , 1 , ⋯ , m a_0 (\varphi_0, \varphi_k) + a_1 (\varphi_1, \varphi_k) + \cdots+ a_m (\varphi_m, \varphi_k) = (f, \varphi_k) \\ k = 0,1,\cdots,m a0(φ0,φk)+a1(φ1,φk)+⋯+am(φm,φk)=(f,φk)k=0,1,⋯,m
因为在正交函数系中，相同函数的卷积大于零，不同函数卷积等于零。证明过程请移步至《傅立叶级数与变换》。所以有
[ ( φ 0 , φ 0 ) ( φ 1 , φ 1 ) ⋱ ( φ m , φ m ) ] [ a 0 a 1 ⋮ a m ] = [ ( f , φ 0 ) ( f , φ 1 ) ⋮ ( f , φ m ) ] \begin{bmatrix} (\varphi_0, \varphi_0) & & \\ & (\varphi_1, \varphi_1) & \\ & & \ddots &\\ & & &(\varphi_m, \varphi_m) \end{bmatrix} \begin{bmatrix} a_0\\ a_1\\ \vdots\\ a_m \end{bmatrix}= \begin{bmatrix} (f,\varphi_0)\\ (f,\varphi_1) \\ \vdots \\ (f,\varphi_m) \end{bmatrix} ⎣⎢⎢⎡(φ0,φ0)(φ1,φ1)⋱(φm,φm)⎦⎥⎥⎤⎣⎢⎢⎢⎡a0a1⋮am⎦⎥⎥⎥⎤=⎣⎢⎢⎢⎡(f,φ0)(f,φ1)⋮(f,φm)⎦⎥⎥⎥⎤
a k = ( f , φ k ) ( φ k , φ k ) = ∑ i = 1 n y i φ k ( x i ) ∑ i = 1 n φ k 2 ( x i ) a_k = \frac{ (f,\varphi_k)}{(\varphi_k, \varphi_k)} = \frac{\sum_{i=1}^n y_i \varphi_k(x_i)}{\sum_{i=1}^n \varphi_k^2(x_i)} ak=(φk,φk)(f,φk)=∑i=1nφk2(xi)∑i=1nyiφk(xi)
其中， A k + 1 = ∑ i = 1 n x i φ k 2 ( x i ) ∑ i = 1 n φ k 2 ( x i ) = ( x φ k ( x ) , φ k ( x ) ) ( φ k ( x ) , φ k ( x ) ) k = 1 , 2 , ⋯ , m − 1 A_{k+1} = \frac{\sum_{i=1}^n x_i \varphi_k^2(x_i)}{\sum_{i=1}^n \varphi_k^2(x_i)}=\frac{(x \varphi_k(x),\varphi_k(x))}{(\varphi_k(x),\varphi_k(x))} \quad k=1,2,\cdots,m-1 Ak+1=∑i=1nφk2(xi)∑i=1nxiφk2(xi)=(φk(x),φk(x))(xφk(x),φk(x))k=1,2,⋯,m−1
B k = ∑ i = 1 n φ k 2 ( x i ) ∑ i = 1 n φ k − 1 2 ( x i ) = ( φ k ( x ) , φ k ( x ) ) ( φ k − 1 ( x ) , φ k − 1 ( x ) ) k = 1 , 2 , ⋯ , m − 1 B_{k} = \frac{\sum_{i=1}^n \varphi_k^2(x_i)}{\sum_{i=1}^n \varphi_{k-1}^2(x_i)}=\frac{( \varphi_k(x),\varphi_k(x))}{(\varphi_{k-1}(x),\varphi_{k-1}(x) )} \quad k=1,2,\cdots,m-1 Bk=∑i=1nφk−12(xi)∑i=1nφk2(xi)=(φk−1(x),φk−1(x))(φk(x),φk(x))k=1,2,⋯,m−1
验证构造的函数系（多项式）的 正交性
对 φ 0 \varphi_0 φ0 和 φ 1 \varphi_1 φ1 求积分：
∑ φ 0 φ 1 = ∑ i ( x i − A 1 ) φ 0 = ∑ i ( x i − ( x i φ 0 , φ 0 ) ( φ 0 , φ 0 ) ) φ 0 = ∑ i ( x i − x i ( φ 0 , φ 0 ) ( φ 0 , φ 0 ) ) φ 0 = 0 \begin{aligned}\sum \varphi_0 \varphi_1 &= \sum_i (x_i-A_1) \varphi_0 \\ & = \sum_i (x_i-\frac{(x_i \varphi_0,\varphi_0)}{(\varphi_0,\varphi_0)}) \varphi_0 \\ & = \sum_i (x_i-x_i\frac{( \varphi_0,\varphi_0)}{(\varphi_0,\varphi_0)}) \varphi_0 \\ & = 0 \end{aligned} ∑φ0φ1=i∑(xi−A1)φ0=i∑(xi−(φ0,φ0)(xiφ0,φ0))φ0=i∑(xi−xi(φ0,φ0)(φ0,φ0))φ0=0
φ 0 \varphi_0 φ0 和 φ 1 \varphi_1 φ1 积分为零，所以它们是正交的。
对 φ 1 \varphi_1 φ1 和 φ k + 1 \varphi_{k+1} φk+1 求积分：
∑ φ 1 φ k + 1 = ∑ i ( ( x i − A k + 1 ) φ k ⋅ φ 1 − B k φ k − 1 ⋅ φ 1 ) = ∑ i ( ( x i − ( x i φ k , φ k ) ( φ k , φ k ) ) φ k ⋅ φ 1 − ( φ k , φ k ) ( φ k − 1 , φ k − 1 ) φ k − 1 φ 1 ) = ∑ i ( 0 − ( φ k , φ k ) ( φ k − 1 , φ k − 1 ) φ k − 1 φ 1 ) = ( φ k , φ k ) ( φ k − 1 , φ k − 1 ) ∑ i φ k − 1 φ 1 \begin{aligned}\sum \varphi_1 \varphi_{k+1} &= \sum_i( (x_i-A_{k+1}) \varphi_k \cdot\varphi_1 – B_k \varphi_{k-1} \cdot\varphi_1) \\ & = \sum_i ((x_i-\frac{(x_i \varphi_k,\varphi_k)}{(\varphi_k,\varphi_k)}) \varphi_k \cdot\varphi_1 – \frac{( \varphi_k,\varphi_k)}{(\varphi_{k-1},\varphi_{k-1} )} \varphi_{k-1} \varphi_1)\\ & = \sum_i (0-\frac{( \varphi_k,\varphi_k)}{(\varphi_{k-1},\varphi_{k-1} )} \varphi_{k-1} \varphi_1)\\ & = \frac{( \varphi_k,\varphi_k)}{(\varphi_{k-1},\varphi_{k-1} )}\sum_i \varphi_{k-1} \varphi_1 \end{aligned} ∑φ1φk+1=i∑((xi−Ak+1)φk⋅φ1−Bkφk−1⋅φ1)=i∑((xi−(φk,φk)(xiφk,φk))φk⋅φ1−(φk−1,φk−1)(φk,φk)φk−1φ1)=i∑(0−(φk−1,φk−1)(φk,φk)φk−1φ1)=(φk−1,φk−1)(φk,φk)i∑φk−1φ1
可以看出， ∑ φ 1 φ k + 1 ⟶ ∑ φ 1 φ k − 1 ⟶ ⋯ ∑ φ 1 φ 0 = 0 \sum \varphi_1 \varphi_{k+1} \longrightarrow \sum \varphi_1\varphi_{k-1} \longrightarrow \cdots \sum \varphi_1 \varphi_0=0 ∑φ1φk+1⟶∑φ1φk−1⟶⋯∑φ1φ0=0
因此 ∑ φ 1 φ k + 1 = 0 \sum \varphi_1 \varphi_{k+1}=0 ∑φ1φk+1=0， 即 φ 1 \varphi_1 φ1 和 φ k + 1 \varphi_{k+1} φk+1正交。
参考资料
- 最小二乘曲线拟合
- 河南理工大学 正交多项式
- 正交多项式与最小二乘拟合
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/212176.html原文链接：https://javaforall.net
