4.3 最小二乘近似
一、最小二乘解
A x = b A\boldsymbol x=\boldsymbol b Ax=b 经常无解，一般是因为方程太多了。矩阵 A A A 的行比列要多，即方程要多余未知数（ m > n m>n m>n）。 n n n 个列只能张成 m m m 空间的一小部分，除非测量的值都非常完美，否则 b \boldsymbol b b 将会落在 A A A 的列空间之外。此时使用消元法将会得到不可能存在的方程，因为测量值包含噪声，我们要找到最优解。
重复：我们不可能能一直把误差 e = b − A x \boldsymbol e=\boldsymbol b-A\boldsymbol x e=b−Ax 降为零，当 e \boldsymbol e e 为零时， x \boldsymbol x x 是 A x = b A\boldsymbol x=\boldsymbol b Ax=b 的确切解；否则我们要使得 e \boldsymbol e e 的长度尽可能的小，此时 x ^ \boldsymbol {\hat x} x^ 就是最小二乘解（least squares solution）。本节的目的就是计算并使用 x ^ \boldsymbol {\hat x} x^，因为有许多实际问题需要答案。
以前强调 p \boldsymbol p p（投影），现在强调 x ^ \boldsymbol {\hat x} x^（最小二乘解），它们由 p = A x ^ \boldsymbol p=A\boldsymbol {\hat x} p=Ax^ 联系起来。基本的方程任然是 A T A x ^ = A T b A^TA\boldsymbol {\hat x}=A^T\boldsymbol b ATAx^=ATb，这里有一个非正式的方法得到这个 “正态方程”：
当 A x = b 没有解时，两边同时左乘 A T 然后求解 A T A x ^ = A T b 当\,A\boldsymbol x=\boldsymbol b\,没有解时，两边同时左乘\,A^T\,然后求解\,\colorbox{white}{$A^TA\boldsymbol{\hat x}=A^T\boldsymbol b$} 当Ax=b没有解时，两边同时左乘AT然后求解ATAx^=ATb
【例1】最小二乘的一个重要应用就是对于 m m m 个点拟合成一条直线。从三个点开始：求出最接近点 ( 0 , 6 ) , ( 1 , 0 ) (0,6),(1,0) (0,6),(1,0) 和 ( 2 , 0 ) (2,0) (2,0) 的直线。
没有任何一条直线可以同时过着三个点，假设直线方程为 b = C + D t b=C+Dt b=C+Dt，我们要求出两个数字 C C C 和 D D D，它满足三个方程： n = 2 n=2 n=2 且 m = 3 m=3 m=3。这三个方程在 t = 0 , 1 , 2 t=0,1,2 t=0,1,2 时要适配给定的值 b = 6 , 0 , 0 b=6,0,0 b=6,0,0： t = 0 如果 C + D ⋅ 0 = 6 ，则第一个点在直线 b = C + D t 上 t = 1 如果 C + D ⋅ 1 = 0 ，则第二个点在直线 b = C + D t 上 t = 2 如果 C + D ⋅ 2 = 0 ，则第三个点在直线 b = C + D t 上 t=0\kern 10pt如果\,\colorbox{lightgray}{$C+D\cdot 0=6$}，则第一个点在直线\,b=C+Dt\,上\\t=1\kern 10pt如果\,\colorbox{lightgray}{$C+D\cdot1=0$}，则第二个点在直线\,b=C+Dt上\\t=2\kern 10pt如果\,\colorbox{lightgray}{$C+D\cdot 2=0$}，则第三个点在直线\,b=C+Dt\,上 t=0如果C+D⋅0=6，则第一个点在直线b=C+Dt上t=1如果C+D⋅1=0，则第二个点在直线b=C+Dt上t=2如果C+D⋅2=0，则第三个点在直线b=C+Dt上这个 3 × 2 3\times2 3×2 的系统是没有解的： b = ( 6 , 0 , 0 ) \boldsymbol b=(6,0,0) b=(6,0,0) 不是列 ( 1 , 1 , 1 ) (1,1,1) (1,1,1) 和 ( 0 , 1 , 2 ) (0,1,2) (0,1,2) 的线性组合。从这些方程中得到 A ， x A，\boldsymbol x A，x 和 b \boldsymbol b b： A = [ 1 0 1 1 1 2 ] x = [ C D ] b = [ 6 0 0 ] A x = b 无解 A=\begin{bmatrix}1&0\\1&1\\1&2\end{bmatrix}\kern 8pt\boldsymbol x=\begin{bmatrix}C\\D\end{bmatrix}\kern 8pt\boldsymbol b=\begin{bmatrix}6\\0\\0\end{bmatrix}\kern 10ptA\boldsymbol x=\boldsymbol b\,无解 A= 111012 x=[CD]b= 600 Ax=b无解我们计算出 x ^ = ( 5 , − 3 ) \boldsymbol {\hat x}=(5,-3) x^=(5,−3)，这两个数字是最好的 C C C 和 D D D，所以 5 − 3 t 5-3t 5−3t 是对于这三个点最优的直线。我们要让投影和最小二乘联系起来，就要解释为什么 A T A x ^ = A T b A^TA\boldsymbol {\hat x}=A^T\boldsymbol b ATAx^=ATb。
在实际问题中，可能很轻易就有 m = 100 m=100 m=100 个点而不是 m = 3 m=3 m=3，它们不会精确的匹配到任何直线 C + D t C+Dt C+Dt。本例中的数字 6 , 0 , 0 6,0,0 6,0,0 夸大了误差，误差 e 1 ， e 2 \boldsymbol e_1，\boldsymbol e_2 e1，e2 和 e 3 \boldsymbol e_3 e3 如 Figure 4.6所示。
二、最小化误差
我们如何让误差 e = b − A x \boldsymbol e=\boldsymbol b-A\boldsymbol x e=b−Ax 尽可能小呢？这个问题很重要，答案也很美妙。最好的 x \boldsymbol x x（称为 x ^ \boldsymbol{\hat x} x^）可以通过几何学（误差 e \boldsymbol e e 与 A A A 列空间的夹角是 90 ° 90° 90°）；也可以由代数： A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb；还可以通过微积分得到相同的 x ^ \boldsymbol {\hat x} x^：误差 ∣ ∣ A x − b ∣ ∣ 2 ||A\boldsymbol x-\boldsymbol b||^2 ∣∣Ax−b∣∣2 的导数在 x ^ \boldsymbol{\hat x} x^ 处为零。
由几何学： 每个 A x A\boldsymbol x Ax 都落在由列 ( 1 , 1 , 1 ) (1,1,1) (1,1,1) 和 ( 0 , 1 , 2 ) (0,1,2) (0,1,2) 所张成的平面内。在这个平面中，我们要找到最靠近 b \boldsymbol b b 的点，这个最近的点就是投影 p \boldsymbol p p。
A x ^ A\boldsymbol {\hat x} Ax^ 最好的选择就是 p \boldsymbol p p，最小的误差是 e = b − p \boldsymbol e=\boldsymbol b-\boldsymbol p e=b−p，它垂直于 A A A 的列。这三个点的高度为 ( p 1 , p 2 , p 3 ) (p_1,p_2,p_3) (p1,p2,p3) 时，它们是在一条直线上，因为 p \boldsymbol p p 在 A A A 的列空间。拟合成一条直线时， x ^ \boldsymbol{\hat x} x^ 最好的选择就是 ( C , D ) (C,D) (C,D)。
由代数： 每个向量 b \boldsymbol b b 都可以分为两部分，在列空间中的部分是 p \boldsymbol p p，还有垂直的部分是 e \boldsymbol e e。我们无法求解方程 A x = b A\boldsymbol x=\boldsymbol b Ax=b，但是我们可以求解方程 A x ^ = p A\boldsymbol{\hat x}=\boldsymbol p Ax^=p（移除 e \boldsymbol e e 然后求解 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb）： A x = b = p + e 无解 A x ^ = p 有解 x ^ 就是 ( A T A ) − 1 A T b ( 4.3.1 ) A\boldsymbol x=\boldsymbol b=\boldsymbol p+\boldsymbol e\,无解\kern 10ptA\boldsymbol{\hat x}=\boldsymbol p\,有解\kern 10pt\boldsymbol{\hat x}\,就是\,(A^TA)^{-1}A^T\boldsymbol b\kern 15pt(4.3.1) Ax=b=p+e无解Ax^=p有解x^就是(ATA)−1ATb(4.3.1) A x ^ = p A\boldsymbol{\hat x}=\boldsymbol p Ax^=p 的解得到最小可能误差 e \boldsymbol e e： 任意 x 的长度平方 ∣ ∣ A x − b ∣ ∣ 2 = ∣ ∣ A x − p ∣ ∣ 2 + ∣ ∣ e ∣ ∣ 2 ( 4.3.2 ) \pmb{任意\,\boldsymbol x\,的长度平方}\kern 12pt||A\boldsymbol x-\boldsymbol b||^2=||A\boldsymbol x-\boldsymbol p||^2+||\boldsymbol e||^2\kern 14pt(4.3.2) 任意x的长度平方∣∣Ax−b∣∣2=∣∣Ax−p∣∣2+∣∣e∣∣2(4.3.2)这就是直角三角形中的勾股定理 c 2 = a 2 + b 2 c^2=a^2+b^2 c2=a2+b2，向量 A x − p A\boldsymbol x-\boldsymbol p Ax−p 在列空间中，它与在左零空间中的 e \boldsymbol e e 垂直。我们通过选择 x = x ^ \boldsymbol x=\boldsymbol{\hat x} x=x^ 将 A x − p A\boldsymbol x-\boldsymbol p Ax−p 减小至零，留下了我们不能再减小的最小可能误差 e = ( e 1 , e 2 , e 3 ) \boldsymbol e=(e_1,e_2,e_3) e=(e1,e2,e3)。
注意 “最小” 的意思是 A x − b A\boldsymbol x-\boldsymbol b Ax−b 长度的平方最小化： 最小二乘解 x ^ 使得 E = ∣ ∣ A x − b ∣ ∣ 2 尽可能的小。 \pmb{最小二乘解\,\boldsymbol{\hat x}\,使得\,E=||A\boldsymbol x-\boldsymbol b||^2\,尽可能的小。} 最小二乘解x^使得E=∣∣Ax−b∣∣2尽可能的小。Figure 4.6a 展示了最近的直线，它的误差距离是 e 1 , e 2 , e = 1 , − 2 , 1 e_1,e_2,e=1,-2,1 e1,e2,e=1,−2,1。这些都是竖直的距离，最小二乘直线最小化 E = e 1 2 + e 2 2 + e 3 2 E=e_1^2+e_2^2+e_3^2 E=e12+e22+e32。
Figure 4.6b 显示了在三维空间（
b
,
p
,
e
\boldsymbol b,\boldsymbol p,\boldsymbol e
b,p,e 的空间）中的同样问题。向量
b
\boldsymbol b
b 不在
A
A
A 的列空间中，这也就是为什么
A
x
=
b
A\boldsymbol x=\boldsymbol b
Ax=b 的原因，没有任何直线可以同时穿过这三点。最小可能的误差就是垂直向量
e
=
b
−
A
x
^
\boldsymbol e=\boldsymbol b-A\boldsymbol{\hat x}
e=b−Ax^，误差向量
(
1
,
−
2
,
1
)
(1,-2,1)
(1,−2,1) 在这三个方程中，它就是与这条最优直线的垂直距离。这两张图的背后就是基本方程
A
T
A
x
^
=
A
T
b
A^TA\boldsymbol{\hat x}=A^T\boldsymbol b
ATAx^=ATb。
注意误差 1 , − 2 , 1 1,-2,1 1,−2,1 相加等于零。这是因为：误差 e = ( e 1 , e 2 , e 3 ) \boldsymbol e=(e_1,e_2,e_3) e=(e1,e2,e3) 垂直于 A A A 的第一列 ( 1 , 1 , 1 ) (1,1,1) (1,1,1)，它们的点积就是 e 1 + e 2 + e 3 = 0 e_1+e_2+e_3=0 e1+e2+e3=0。
由微积分： 大部分函数的最小值都是用微积分解决！图形降到最低点并且在每一个方向的导数都为零。这里要使得误差函数 E E E 最小化， E E E 就是平方和 e 1 2 + e 2 2 + e 3 2 e_1^2+e_2^2+e_3^2 e12+e22+e32（每个方程中误差的平方）： E = ∣ ∣ A x − b ∣ ∣ 2 = ( C + D ⋅ 0 − 6 ) 2 + ( C + D ⋅ 1 ) 2 + ( C + D ⋅ 2 ) 2 ( 4.3.3 ) E=||A\boldsymbol x-\boldsymbol b||^2=(C+D\cdot0-6)^2+(C+D\cdot1)^2+(C+D\cdot2)^2\kern 18pt(4.3.3) E=∣∣Ax−b∣∣2=(C+D⋅0−6)2+(C+D⋅1)2+(C+D⋅2)2(4.3.3)未知数是 C C C 和 D D D，两个未知数有两个偏导数，它们在极小值处都为零。称为偏导数是因为求 ∂ E ∂ C \displaystyle\frac{\partial E}{\partial C} ∂C∂E 时将 D D D 当做常数，求 ∂ E ∂ D \displaystyle\frac{\partial E}{\partial D} ∂D∂E 时将 C C C 当做常数： ∂ E ∂ C = 2 ( C + D ⋅ 0 − 6 ) + 2 ( C + D ⋅ 1 ) + 2 ( C + D ⋅ 2 ) = 0 ∂ E ∂ D = 2 ( C + D ⋅ 0 − 6 ) ⋅ ( 0 ) + 2 ( C + D ⋅ 1 ) ⋅ ( 1 ) + 2 ( C + D ⋅ 2 ) ⋅ ( 2 ) = 0 \frac{\partial E}{\partial C}=2(C+D\cdot0-6)+2(C+D\cdot1)+2(C+D\cdot2)=0\\\frac{\partial E}{\partial D}=2(C+D\cdot0-6)\cdot(0)+2(C+D\cdot1)\cdot(1)+2(C+D\cdot2)\cdot(2)=0 ∂C∂E=2(C+D⋅0−6)+2(C+D⋅1)+2(C+D⋅2)=0∂D∂E=2(C+D⋅0−6)⋅(0)+2(C+D⋅1)⋅(1)+2(C+D⋅2)⋅(2)=0因为求导的链式法则， ∂ E ∂ D \displaystyle\frac{\partial E}{\partial D} ∂D∂E 含有额外的因子 0 , 1 , 2 0,1,2 0,1,2（最后的 ( C + 2 D ) 2 (C+2D)^2 (C+2D)2 的导数是 2 2 2 乘 C + 2 D C+2D C+2D 再乘 2 2 2）。这些因子在 ∂ E ∂ C \displaystyle\frac{\partial E}{\partial C} ∂C∂E 中就是 1 , 1 , 1 1,1,1 1,1,1。
毫无意外的 ∣ ∣ A x − b ∣ ∣ ||A\boldsymbol x-\boldsymbol b|| ∣∣Ax−b∣∣ 导数的因子 1 , 1 , 1 1,1,1 1,1,1 和 0 , 1 , 2 0,1,2 0,1,2 就是 A A A 的列，现在消去每一项的 2 2 2 然后将 C C C 和 D D D 的同类项进行合并： C 的导数为零： 3 C + 3 D = 6 D 的导数为零： 3 C + 5 D = 0 矩阵 [ 3 3 3 5 ] 就是 A T A ( 4.3.4 ) \begin{matrix}C\,的导数为零：3C+3D=6\\D\,的导数为零：3C+5D=0\end{matrix}\kern 15pt\pmb{矩阵}\begin{bmatrix}3&3\\3&5\end{bmatrix}就是\,A^TA\kern 16pt(4.3.4) C的导数为零：3C+3D=6D的导数为零：3C+5D=0矩阵[3335]就是ATA(4.3.4)这些方程与 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb 完全相同。 最优的 C C C 和 D D D 就是 x ^ \boldsymbol{\hat x} x^ 的分量。从微积分得到的方程与从线性代数得到的 “正规方程” 完全一致。这是最小二乘的关键方程：
当 A T A x ^ = A T b 时， ∣ ∣ A x − b ∣ ∣ 2 的偏导数为零。 当\,A^TA\boldsymbol{\hat x}=A^T\boldsymbol b\,时，||A\boldsymbol x-\boldsymbol b||^2\,的偏导数为零。 当ATAx^=ATb时，∣∣Ax−b∣∣2的偏导数为零。
解是 C = 5 ， D = − 3 C=5，D=-3 C=5，D=−3，因此 b = 5 − 3 t b=5-3t b=5−3t 就是最优的直线 —— 它与这三点最近。当 t = 0 , 1 , 2 t=0,1,2 t=0,1,2 时，这条直线经过 p = 5 , 2 , − 1 \boldsymbol p=5,2,-1 p=5,2,−1，它不通过 b = 6 , 0 , 0 \boldsymbol b=6,0,0 b=6,0,0。误差是 1 , − 2 , 1 1,-2,1 1,−2,1，就是误差向量 e \boldsymbol e e！
三、最小二乘的大图
Figure 4.3 是关键的一张图，它显示了 4 4 4 个基本子空间和矩阵的真正作用，左边的向量 x \boldsymbol x x 到右边的 b = A x \boldsymbol b=A\boldsymbol x b=Ax，这张图将 x \boldsymbol x x 分成 x r + x n \boldsymbol x_r+\boldsymbol x_n xr+xn， A x = b A\boldsymbol x=\boldsymbol b Ax=b 可能存在很多解。
现在的情况与上述正好相反，
A
x
=
b
A\boldsymbol x=\boldsymbol b
Ax=b 无解，这里我们不再分解
x
\boldsymbol x
x，而是将
b
\boldsymbol b
b 分成
b
=
p
+
e
\boldsymbol b=\boldsymbol p+\boldsymbol e
b=p+e。Figure 4.7 显示了最小二乘的大图，我们不解
A
x
=
b
A\boldsymbol x=\boldsymbol b
Ax=b,而是求解
A
x
^
=
p
A\boldsymbol{\hat x}=\boldsymbol p
Ax^=p，误差
e
=
b
−
p
\boldsymbol e=\boldsymbol b-\boldsymbol p
e=b−p 无法避免。
注意这里的零空间 N ( A ) \pmb N(A) N(A) 很小 —— 仅有一个点，这是因为 A A A 的列线性无关， A x = 0 A\boldsymbol x=\boldsymbol 0 Ax=0 的唯一解就是 x = 0 \boldsymbol x=\boldsymbol 0 x=0，此时 A T A A^TA ATA 是可逆的。方程 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb 就决定了最优向量 x ^ \boldsymbol{\hat x} x^，对于误差有 A T e = 0 A^T\boldsymbol e=\boldsymbol 0 ATe=0。
四、拟合一条直线
最小二乘最常见的应用就是拟合一条直线，从 m > 2 m>2 m>2 个点开始，希望找到一条最接近这些点的直线。在时间点 t 1 , t 2 , ⋯ , t m t_1,t_2,\cdots,t_m t1,t2,⋯,tm 时，这 m m m 个点的高度是 b 1 , b 2 , ⋯ , b m b_1,b_2,\cdots,b_m b1,b2,⋯,bm。最优直线 C + D t C+Dt C+Dt 距这些点的垂直距离是 e 1 , e 2 , ⋯ , e m e_1,e_2,\cdots,e_m e1,e2,⋯,em。没有完全经过这些点的直线，我们要使得这些误差的平方 E = e 1 2 + e 2 2 + ⋯ + e m 2 E=e_1^2+e_2^2+\cdots+e_m^2 E=e12+e22+⋯+em2 最小。
第一个例子是 Figure 4.6 中的三点问题，现在我们将允许 m m m 个点（ m m m 可以很多）， x ^ \boldsymbol{\hat x} x^ 的两个分量仍然是 C C C 和 D D D。
如果我们要求 A x = b A\boldsymbol x=\boldsymbol b Ax=b 的确切解时，它需要一条完全通过这 m m m 个点的直线，通常这是不现实的。两个未知数 C C C 和 D D D 决定了一条直线，所以 A A A 仅有 n = 2 n=2 n=2 列。为了拟合这 m m m 个点，我们需要求解 m m m 个方程（但是只有两个未知数！） A x = b 是 C + D t 1 = b 1 C + D t 2 = b 2 ⋮ C + D t m = b m 其中 A = [ 1 t 1 1 t 2 ⋮ ⋮ 1 t m ] ( 4.3.5 ) A\boldsymbol x=\boldsymbol b\kern 5pt是\kern 5pt\begin{matrix}C+Dt_1=b_1\\C+Dt_2=b_2\\\vdots\\C+Dt_m=b_m\end{matrix}\kern 10pt其中\,A=\begin{bmatrix}1&t_1\\1&t_2\\\vdots&\vdots\\1&t_m\end{bmatrix}\kern 15pt(4.3.5) Ax=b是C+Dt1=b1C+Dt2=b2⋮C+Dtm=bm其中A= 11⋮1t1t2⋮tm (4.3.5) A A A 的列空间很细，这使得大部分的 b \boldsymbol b b 都落在列空间外。如果 b \boldsymbol b b 恰好落在列空间中，那么这些点就很正好落在一条直线上。这种情况下 b = p \boldsymbol b=\boldsymbol p b=p， A x = b A\boldsymbol x=\boldsymbol b Ax=b 可解，误差是 e = ( 0 , 0 , ⋯ , 0 ) \boldsymbol e=(0,0,\cdots,0) e=(0,0,⋯,0)。 最接近的直线 C + D t 的高度是 p 1 , p 2 , ⋯ , p m ，误差是 e 1 , e 2 , ⋯ , e m . 求解 A T A x ^ = A T b ，得到 x ^ = ( C , D ) ，误差是 e i = b i − C − D t i . {\color{blue}\begin{array}{l}最接近的直线\,C+Dt\,的高度是\,p_1,p_2,\cdots,p_m，误差是\,e_1,e_2,\cdots,e_m.\\求解\,A^TA\boldsymbol{\hat x}=A^T\boldsymbol b，得到\,\boldsymbol{\hat x}=(C,D)，误差是\,e_i=b_i-C-Dt_i.\end{array}} 最接近的直线C+Dt的高度是p1,p2,⋯,pm，误差是e1,e2,⋯,em.求解ATAx^=ATb，得到x^=(C,D)，误差是ei=bi−C−Dti.直线拟合非常重要，我们给定方程 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb， A A A 的两列是线性无关的（除非所有的点 t i t_i ti 都一样），我们转到最小二乘并求解 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb。 点积矩阵 A T A = [ 1 1 ⋯ 1 t 1 t 2 ⋯ t m ] [ 1 t 1 1 t 2 ⋮ ⋮ 1 t m ] = [ m ∑ t i ∑ t i ∑ t i 2 ] ( 4.3.6 ) \pmb{点积矩阵}\kern 6ptA^TA=\begin{bmatrix}1&1&\cdots&1\\t_1&t_2&\cdots&t_m\end{bmatrix}\begin{bmatrix}1&t_1\\1&t_2\\\vdots&\vdots\\1&t_m\end{bmatrix}=\begin{bmatrix}m&\sum t_i\\\sum t_i&\sum t^2_i\end{bmatrix}\kern 13pt(4.3.6) 点积矩阵ATA=[1t11t2⋯⋯1tm] 11⋮1t1t2⋮tm =[m∑ti∑ti∑ti2](4.3.6)正规方程的右侧是 2 × 1 2\times1 2×1 的向量 A T b A^T\boldsymbol b ATb： A T b = [ 1 1 ⋯ 1 t 1 t 2 ⋯ t m ] [ b 1 b 2 ⋮ b m ] = [ ∑ b i ∑ t i b i ] ( 4.3.7 ) A^T\boldsymbol b=\begin{bmatrix}1&1&\cdots&1\\t_1&t_2&\cdots&t_m\end{bmatrix}\begin{bmatrix}b_1\\b_2\\\vdots\\b_m\end{bmatrix}=\begin{bmatrix}\sum b_i\kern 8pt\\\sum t_ib_i\end{bmatrix}\kern 15pt(4.3.7) ATb=[1t11t2⋯⋯1tm] b1b2⋮bm =[∑bi∑tibi](4.3.7)在特定问题中，这些数字都是给定的，最优的 x ^ = ( C , D ) \boldsymbol{\hat x}=(C,D) x^=(C,D) 是 ( A T A ) − 1 A T b (A^TA)^{-1}A^T\boldsymbol b (ATA)−1ATb.
当 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb 时，直线 C + D t C+Dt C+Dt 使得 e 1 2 + e 2 2 + ⋯ + e m 2 = ∣ ∣ A x − b ∣ ∣ 2 e_1^2+e_2^2+\cdots+e_m^2=||A\boldsymbol x-\boldsymbol b||^2 e12+e22+⋯+em2=∣∣Ax−b∣∣2 最小： A T A x ^ = A T b [ m ∑ t i ∑ t i ∑ t i 2 ] [ C D ] = [ ∑ b i ∑ t i b i ] ( 4.3.8 ) A^TA\boldsymbol{\hat x}=A^T\boldsymbol b\kern 20pt\begin{bmatrix}m&\sum t_i\\\sum t_i&\sum t^2_i\end{bmatrix}\begin{bmatrix}C\\D\end{bmatrix}=\begin{bmatrix}\sum b_i\\\sum t_ib_i\end{bmatrix}\kern 18pt(4.3.8) ATAx^=ATb[m∑ti∑ti∑ti2][CD]=[∑bi∑tibi](4.3.8)
这 m m m 个点与这条直线的垂直误差是 e = b − p \boldsymbol e=\boldsymbol b-\boldsymbol p e=b−p 的分量，这个误差向量 b − A x ^ \boldsymbol b-A\boldsymbol{\hat x} b−Ax^ 与 A A A 的列是垂直的（几何学），误差向量在 A T A^T AT 的零空间中（线性代数）。最优的 x ^ = ( C , D ) \boldsymbol{\hat x}=(C,D) x^=(C,D) 使得总误差 E E E 最小，即平方和最小（微积分）： E ( x ) = ∣ ∣ A x − b ∣ ∣ 2 = ( C + D t 1 − b 1 ) 2 + ( C + D t 2 − b 2 ) + ⋯ ( C + D t m − b m ) 2 E(\boldsymbol x)=||A\boldsymbol x-\boldsymbol b||^2=(C+Dt_1-b_1)^2+(C+Dt_2-b_2)+\cdots(C+Dt_m-b_m)^2 E(x)=∣∣Ax−b∣∣2=(C+Dt1−b1)2+(C+Dt2−b2)+⋯(C+Dtm−bm)2微积分中令 ∂ E ∂ C \displaystyle\frac{\partial E}{\partial C} ∂C∂E 和 ∂ E ∂ D \displaystyle\frac{\partial E}{\partial D} ∂D∂E 等于零，就可以得到 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb。
其它的最小二乘问题未知数可能多于两个，拟合成最优的抛物线有 n = 3 n=3 n=3 个系数 C , D , E C,D,E C,D,E。一般情况下，我们用 n n n 个参数拟合 m m m 个数据点，矩阵 A A A 有 n n n 列，且 n 3 个点时，这 m m m 个方程一般是无解的： C + D t 1 + E t 1 2 = b 1 C + D t 2 + E t 2 2 = b 2 ⋯ C + D t m + E t m 2 = b m 是 A x = b ，其中 A 是 m × 3 的矩阵 A = [ 1 t 1 t 1 2 1 t 2 t 2 2 ⋮ ⋮ ⋮ 1 t m t m 2 ] ( 4.3.10 ) \begin{matrix}C+Dt_1+Et_1^2=b_1\\C+Dt_2+Et_2^2=b_2\\\cdots\\C+Dt_m+Et_m^2=b_m\end{matrix}\kern 5pt\begin{matrix}是\,A\boldsymbol x=\boldsymbol b，其中\,\\A\,是\,m\times3\,的矩阵\end{matrix}\kern 5ptA=\begin{bmatrix}1&t_1&t_1^2\\1&t_2&t_2^2\\\vdots&\vdots&\vdots\\1&t_m&t_m^2\end{bmatrix}\kern 15pt(4.3.10) C+Dt1+Et12=b1C+Dt2+Et22=b2⋯C+Dtm+Etm2=bm是Ax=b，其中A是m×3的矩阵A= 11⋮1t1t2⋮tmt12t22⋮tm2 (4.3.10)最小二乘： 最接近的抛物线 C + D t + E t 2 C+Dt+Et^2 C+Dt+Et2 是 x ^ = ( C , D , E ) \boldsymbol{\hat x}=(C,D,E) x^=(C,D,E) 满足三个正规方程 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb。
下面将这个变成投影问题： A A A 的列空间维度是 3 3 3， b \boldsymbol b b 的投影是 p = A x ^ \boldsymbol p=A\boldsymbol{\hat x} p=Ax^，其中 p \boldsymbol p p 是系数 C , D , E C,D,E C,D,E 对三列进行组合。第一个数据点的误差是 e 1 = b 1 − C − D t 1 − E t 1 2 e_1=b_1-C-Dt_1-Et_1^2 e1=b1−C−Dt1−Et12，误差的总平方和是 e 1 2 + e 2 2 + ⋯ + e m 2 e_1^2+e_2^2+\cdots+e_m^2 e12+e22+⋯+em2。如果用微积分来最小化误差，就是计算 E E E（误差总的平方和，与系数 E E E 不同）对于 C , D , E C,D,E C,D,E 的偏导数，当 x ^ = ( C , D , E ) \boldsymbol{\hat x}=(C,D,E) x^=(C,D,E) 是 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb 这个 3 × 3 3\times3 3×3 的方程系统的解时，这三个偏导数等于零。
傅里叶级数也是最小二乘的应用 —— 这里是近似函数而不是近似向量，函数的近似从误差的平方和 e 1 2 + e 2 2 + ⋯ + e m 2 e_1^2+e_2^2+\cdots+e_m^2 e12+e22+⋯+em2 变成了误差平方的积分。
【例3】一个抛物线 b = C + D t + E t 2 b=C+Dt+Et^2 b=C+Dt+Et2 当 t = 0 , 1 , 2 t=0,1,2 t=0,1,2 时，经过三个高度 b = 6 , 0 , 0 b=6,0,0 b=6,0,0，关于 C , D , E C,D,E C,D,E 的三个方程是 C + D ⋅ 0 + E ⋅ 0 2 = 6 C + D ⋅ 1 + E ⋅ 1 2 = 0 C + D ⋅ 2 + E ⋅ 2 2 = 0 ( 4.3.11 ) \begin{matrix}C+D\cdot0+E\cdot0^2=6\\C+D\cdot1+E\cdot1^2=0\\C+D\cdot2+E\cdot2^2=0\end{matrix}\kern 35pt(4.3.11) C+D⋅0+E⋅02=6C+D⋅1+E⋅12=0C+D⋅2+E⋅22=0(4.3.11)这个就是 A x = b A\boldsymbol x=\boldsymbol b Ax=b，它是有解的，这三个数据点得到三个方程和一个方阵，解是 x = ( C , D , E ) = ( 6 , − 9 , 3 ) \boldsymbol x=(C,D,E)=(6,-9,3) x=(C,D,E)=(6,−9,3)，如 Figure 4.8a 所示，这条抛物线 b = 6 − 9 t + 3 t 2 b=6-9t+3t^2 b=6−9t+3t2 通过这三个点。
上述对于投影来说意味着什么？矩阵有三列，它张成整个 R 3 \pmb{\textrm R}^3 R3 空间，投影矩阵就是单位矩阵， b \boldsymbol b b 的投影就是 b \boldsymbol b b，误差是零。这里不需要 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb，因为 A x = b A\boldsymbol x=\boldsymbol b Ax=b 有解。当然两边也可以左乘 A T A^T AT，只是我们没什么理由这样做。
Figure 4.8 显示了在 t 4 t_4 t4 时刻的第四点是 b 4 b_4 b4，如果它正好落在抛物线上，则新的 A x = b A\boldsymbol x=\boldsymbol b Ax=b（ 4 4 4 个方程）任然有解，如果第四点不在抛物线上，我们就需要 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb，那么最小二乘的抛物线就不一定让四个点都落在它上面。
最小二乘会平衡四个误差得到三个关于
C
,
D
,
E
C,D,E
C,D,E 的方程。
七、主要内容总结
- 最小二乘解 x ^ \boldsymbol{\hat x} x^ 使得 ∣ ∣ A x − b ∣ ∣ 2 = x T A T A x − 2 x T A T b + b T b ||A\boldsymbol x-\boldsymbol b||^2=\boldsymbol x^TA^TA\boldsymbol x-2\boldsymbol x^T\boldsymbol A^T\boldsymbol b+\boldsymbol b^T\boldsymbol b ∣∣Ax−b∣∣2=xTATAx−2xTATb+bTb 最小，这个就是 E E E，它是 m m m 个方程误差的平方和（ m > n m>n m>n）。
- 最优的 x ^ \boldsymbol{\hat x} x^ 由正规方程 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb 得来， E E E 是最小值。
- 通过直线 b = C + D t b=C+Dt b=C+Dt 拟合 m m m 个点，正规方程可以得到 C C C 和 D D D。
- 最优直线的高度是 p = ( p 1 , p 2 , ⋯ , p m ) \boldsymbol p=(p_1,p_2,\cdots,p_m) p=(p1,p2,⋯,pm)，和数据点的竖直距离就是误差 e = ( e 1 , e 2 , ⋯ , e m ) \boldsymbol e=(e_1,e_2,\cdots,e_m) e=(e1,e2,⋯,em)，关键方程是 A T e = 0 A^T\boldsymbol e=\boldsymbol 0 ATe=0。
- 如果有 m m m 个数据点（ m > n m>n m>n），我们可以得到 n n n 个方程，这 n n n 个方程 A x = b A\boldsymbol x=\boldsymbol b Ax=b 通常是无解的。但是 n n n 个 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb 方程可以得到最小二乘解 —— 最小 MSE（均方值：mean square error）的组合。
八、例题
【例4】在时刻 t = 1 , 2 , ⋯ , 9 t=1,2,\cdots,9 t=1,2,⋯,9 时， 9 9 9 个测量值 b 1 b_1 b1 到 b 9 b_9 b9 全为零。第 10 10 10 个测量值 b 10 = 40 b_{10}=40 b10=40，它是一个离群值。找到一条最优的水平直线 y = C y=C y=C 来拟合这 10 10 10 个点 ( 1 , 0 ) , ( 2 , 0 ) , ⋯ , ( 9 , 0 ) , ( 10 , 40 ) (1,0),(2,0),\cdots,(9,0),(10,40) (1,0),(2,0),⋯,(9,0),(10,40)，使用下面三种情况的误差 E E E：
（1）最小二乘误差 E 2 = e 1 2 + e 2 2 + ⋯ + e 10 2 E_2=e_1^2+e_2^2+\cdots+e^2_{10} E2=e12+e22+⋯+e102（ C C C 的正规方式是线性的）
（2）最小极大误差（least maximum error） E ∞ = ∣ e max ∣ E_\infty=|e_{\textrm{max}}| E∞=∣emax∣
（3）最小误差和 E 1 = ∣ e 1 ∣ + ∣ e 2 ∣ + ⋯ + ∣ e 10 ∣ E_1=|e_1|+|e_2|+\cdots+|e_{10}| E1=∣e1∣+∣e2∣+⋯+∣e10∣
解： （1）最小二乘法对 0 , 0 , ⋯ , 0 , 40 0,0,\cdots,0,40 0,0,⋯,0,40 这 10 10 10 个点拟合出来的水平直线是 C = 4 C=4 C=4： A 是 10 × 1 的全 1 矩阵 A T A = 10 A T b = ∑ i = 1 10 b i = 40 所以 10 C = 40 A\,是\,10\times1\,的全\,1\,矩阵\kern 10ptA^TA=10\kern 10ptA^T\boldsymbol b=\sum^{10}_{i=1}b_i=40\kern 10pt所以\,10C=40 A是10×1的全1矩阵ATA=10ATb=i=1∑10bi=40所以10C=40（2）最小极大误差是 C = 20 C=20 C=20，是 0 0 0 和 40 40 40 的一半。
（3）最小误差和是 C = 0 C=0 C=0。误差和是 9 ∣ C ∣ + ∣ 40 − C ∣ 9|C|+|40-C| 9∣C∣+∣40−C∣，可得当 C = 0 C=0 C=0 时最小。
最小和来自中位测量（median measurement）， 0 , 0 , ⋯ , 0 , 40 0,0,\cdots,0,40 0,0,⋯,0,40 的中位数是 0 0 0。统计学中，最小二乘解受离群值影响很大，例如此例中的 b 10 = 40 b_{10}=40 b10=40，有时使用最小误差和会比较好。但是这样的话，方程就是一个非线性的了。
下面使用最小二乘法用一条直线 C + D t C+Dt C+Dt 来拟合这 10 10 10 个点， ( 1 , 0 ) (1,0) (1,0) 到 ( 10 , 40 ) (10,40) (10,40)： A T A = [ 10 ∑ t i ∑ t i ∑ t i 2 ] = [ 10 55 55 385 ] A T b = [ ∑ b i ∑ t i b i ] = [ 40 400 ] A^TA=\begin{bmatrix}10&\sum t_i\\\sum t_i&\sum t^2_i\end{bmatrix}=\begin{bmatrix}10&55\\55&385\end{bmatrix}\kern 20ptA^T\boldsymbol b=\begin{bmatrix}\sum b_i\\\sum t_ib_i\end{bmatrix}=\begin{bmatrix}40\\400\end{bmatrix} ATA=[10∑ti∑ti∑ti2]=[105555385]ATb=[∑bi∑tibi]=[40400]这些就是由方程（4.3.8）而来，然后求解 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb，得到 C = − 8 ， D = 24 / 11 C=-8，D=24/11 C=−8，D=24/11。
如果将 b = ( 0 , 0 , ⋯ , 40 ) \boldsymbol b=(0,0,\cdots,40) b=(0,0,⋯,40) 乘上 3 3 3 再加上 30 30 30 得到 b new = ( 30 , 30 , ⋯ , 150 ) \boldsymbol b_{\textrm{new}}=(30,30,\cdots,150) bnew=(30,30,⋯,150)，那么 C C C 和 D D D 会发生什么样的变化呢？线性将允许我们重新设定 b \boldsymbol b b 的比例， 3 3 3 乘 b \boldsymbol b b 可以得到 C C C 和 D D D 都乘 3 3 3，对所有的 b i b_i bi 都加上 30 30 30，相当于对 C C C 加上 30 30 30，得到新的 C new = 3 C + 30 = 6 C_{\textrm {new}}=3C+30=6 Cnew=3C+30=6， D new = 3 D = 72 / 11 D_{\textrm{new}}=3D=72/11 Dnew=3D=72/11。
【例5】在时刻 t = − 2 , − 1 , 0 , 1 , 2 t=-2,-1,0,1,2 t=−2,−1,0,1,2 时， b = ( 0 , 0 , 1 , 0 , 0 ) \boldsymbol b=(0,0,1,0,0) b=(0,0,1,0,0)，找到一条离这些点最近（最小二乘误差）的抛物线 C + D t + E t 2 C+Dt+Et^2 C+Dt+Et2。首先写出 5 5 5 个方程 A x = b A\boldsymbol x=\boldsymbol b Ax=b，它有三个未知数 x = ( C , D , E ) \boldsymbol x=(C,D,E) x=(C,D,E)，这些方程分别过这 5 5 5 个点。但是它们没有解，因为并不存在这样的抛物线，我们要求解 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb。
这里可以预测 D = 0 D=0 D=0，最优的抛物线应该是关于 t = 0 t=0 t=0 对称。在 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb 中，方程 2 2 2 中的 D D D 与方程 1 1 1 和 3 3 3 是解耦的。
解： A x = b A\boldsymbol x=\boldsymbol b Ax=b 的 5 5 5 个方程有一个矩形的范德蒙德（Vandermonde）矩阵 A A A： C + D ( − 2 ) + E ( − 2 ) 2 = 0 C + D ( − 1 ) + E ( − 1 ) 2 = 0 C + D ( 0 ) + E ( 0 ) 2 = 1 C + D ( 1 ) + E ( 1 ) 2 = 0 C + D ( 2 ) + E ( 2 ) 2 = 0 A = [ 1 − 2 4 1 − 1 1 1 0 0 1 1 1 1 2 4 ] A T A = [ 5 0 10 0 10 0 10 0 34 ] \begin{matrix}C+D(-2)+E(-2)^2=0\\C+D(-1)+E(-1)^2=0\\C+D\kern 8pt(0)+E\kern 8pt(0)^2=1\\C+D\kern 8pt(1)+E\kern 8pt(1)^2=0\\C+D\kern 8pt(2)+E\kern 8pt(2)^2=0\end{matrix}\kern 10ptA=\begin{bmatrix}1&-2&4\\1&-1&1\\1&\kern 7pt0&0\\1&\kern 7pt1&1\\1&\kern 7pt2&4\end{bmatrix}\kern 10ptA^TA=\begin{bmatrix}5&\pmb0&10\\\pmb0&10&\pmb0\\10&\pmb0&34\end{bmatrix} C+D(−2)+E(−2)2=0C+D(−1)+E(−1)2=0C+D(0)+E(0)2=1C+D(1)+E(1)2=0C+D(2)+E(2)2=0A= 11111−2−101241014 ATA= 5010010010034 A T A A^TA ATA 中的零表示 A A A 的列 2 2 2 和它的列 1 1 1 和列 3 3 3 正交，在 A A A 中可以直接看出来（时间 − 2 , − 1 , 0 , 1 , 2 -2,-1,0,1,2 −2,−1,0,1,2 是对称的）。抛物线 C + D t + E t 2 C+Dt+Et^2 C+Dt+Et2 中最优的 C , D , E C,D,E C,D,E 由 A T A x ^ = A T b A^TA\boldsymbol{\hat x}=A^T\boldsymbol b ATAx^=ATb 解得，这里 D D D 和 C C C 与 E E E 是解耦的： [ 5 0 10 0 10 0 10 0 34 ] [ C D E ] = [ 1 0 0 ] 解得 C = 17 35 D = 0 ，与预测一致 E = − 1 7 \begin{bmatrix}5&0&10\\0&10&0\\10&0&34\end{bmatrix}\begin{bmatrix}C\\D\\E\end{bmatrix}=\begin{bmatrix}1\\0\\0\end{bmatrix}\kern 5pt解得\kern 5pt\begin{array}{l}C=\displaystyle\frac{17}{35}\\D=0，与预测一致\\E=-\displaystyle\frac{1}{7}\end{array} 5010010010034 CDE = 100 解得C=3517D=0，与预测一致E=−71
