MIT 18.02 · 第 9 课

Max-Min Problems; Least Squares (极值与最小二乘)

利用偏导数求多元函数的极值,定义临界点(critical point),并引入最小二乘法(least squares)拟合实验数据。

授课:Denis Auroux 日期:2007-09-27 难度:中等

学习目标


线性近似回顾

在 \((x_0,y_0)\) 附近,函数的变化可以用切平面近似:

\[ \Delta f \approx f_x(x_0,y_0)\,\Delta x + f_y(x_0,y_0)\,\Delta y \]

两条分别平行于 \(xz\) 与 \(yz\) 平面的切线共同决定了切平面的方向。


临界点与极值

若 \((x_0,y_0)\) 是 \(f\) 的局部极大或极小值点,则在 \(y=y_0\) 截面上的单变量函数在 \(x_0\) 处取极值,因此 \(f_x(x_0,y_0)=0\);同理 \(f_y(x_0,y_0)=0\)。

定义(临界点):满足 \(f_x(x_0,y_0)=0\) 且 \(f_y(x_0,y_0)=0\) 的点称为临界点(critical point)。
临界点可能是局部极大、局部极小或鞍点(saddle point)。

几何直观:在临界点处切平面是水平的(\(z \approx z_0\)),即 \(\Delta f \approx 0\)。


极大、极小与鞍点

三种典型的标准形状:

例题:设 \(f(x,y) = x^2 - 2xy + 3y^2 + 2x - 2y\)。
解 \(f_x = 2x-2y+2=0\),\(f_y = -2x+6y-2=0\),得唯一临界点 \((-1,0)\)。
配方:\(f = (x-y+1)^2 + 2y^2 - 1 \ge -1\),故 \((-1,0)\) 是极小值点,极小值为 \(-1\)。

注意:本课只通过配方判断;系统的判别法(二阶导数检验)将在下一课给出。


最小二乘法(Least Squares)

问题背景:给定实验数据点 \((x_i, y_i)\)(\(i=1,\dots,n\)),求一条最佳拟合直线 \(y = ax + b\)。这里的未知数是斜率 \(a\) 和截距 \(b\),而不是 \(x, y\)。

设第 \(i\) 个数据点的偏差(deviation)为 \(y_i - (ax_i+b)\)。定义总平方偏差

\[ D(a,b) = \sum_{i=1}^{n} \bigl(y_i - (ax_i+b)\bigr)^2 \]

使 \(D\) 最小的 \(a,b\) 就是最小二乘解。

核心思想:把求极值的方法用在新变量 \(a,b\) 上——令 \(\displaystyle\frac{\partial D}{\partial a}=0\),\(\displaystyle\frac{\partial D}{\partial b}=0\)。

对 \(D\) 求偏导并令其为零,得到关于 \(a,b\) 的二元线性方程组——法方程(normal equations):

\[ \begin{cases} \displaystyle \Bigl(\sum x_i^2\Bigr)\, a + \Bigl(\sum x_i\Bigr)\, b = \sum x_i y_i \\ \displaystyle \Bigl(\sum x_i\Bigr)\, a + n\, b = \sum y_i \end{cases} \]

解此方程组即得最佳拟合的 \(a,b\)。

推广:
• 指数律 \(y = ce^{ax}\):取对数 \(\ln y = \ln c + ax\),令 \(b=\ln c\) 化为线性情形。
• 二次律 \(y = ax^2 + bx + c\):最小化平方偏差得到关于 \(a,b,c\) 的三元线性方程组。

实例:Moore 定律(Moore's Law)——芯片上晶体管数目随时间指数增长,在 \(\ln N\)–时间图上呈直线。


知识检查

问题 1:若 \((x_0,y_0)\) 是 \(f(x,y)\) 的局部极值点且偏导数存在,则必有?

问题 2:下列哪个函数在原点处具有鞍点?

问题 3:最小二乘法极小化的是关于哪个变量的函数?


本课要点

临界点

极值点必满足 \(f_x=f_y=0\),反之未必。

三种类型

局部极小、局部极大、鞍点——第 10 课将给出系统判别法。

最小二乘

极小化平方偏差之和,导出法方程。

推广

指数律、高次多项式均可通过变量替换或建立多元线性方程组拟合。


一手资料