投影与正交分解
任何向量都能拆成两份:一份沿着某个方向,一份垂直于它。沿着的那份就是投影,它落在离原向量最近的那个点上。机器人用它回答"我偏离路径多远"、"这股力有多少压进表面、有多少在滑",最小二乘也只是它换了件衣服。
1为什么机器人需要它
一台移动机器人沿着规划好的路径行驶。控制器每个周期都要回答一个问题:我偏离路径多远,偏向哪一边?这里的"多远"不是离起点多远,而是离路径上最近的那一点多远。找这个最近点,就是把机器人的位置投影到路径上。
同样的拆分在机器人里随处可见:
- 接触力。手指按在物体表面,总的力有多少"压进"表面(法向力),有多少沿表面"滑动"(切向力)?摩擦锥 (friction cone) 规定:切向力不能超过 μ 倍的法向力,否则就打滑。抓取规划每时每刻都在做这个分解。
- 速度指令。规划器让机器人径直冲向一堵墙,安全层要把指令里"撞墙"的那一份去掉,只保留沿墙的那一份。被去掉的,就是指令在墙的法向上的投影。
- 最小二乘(1.13 节)。方程无解时,我们改找离 \(\mathbf b\) 最近的 \(A\mathbf x\)。这恰好是把 \(\mathbf b\) 投影到 \(A\) 的列空间。
1.7 节里,\(\hat{\mathbf u}\cdot\mathbf b\) 告诉我们 \(\mathbf b\) 在 \(\hat{\mathbf u}\) 方向上有多长。这一节把这个长度变成一支真正的向量,再把剩下的部分也一起管起来。
2直觉:影子,和最近的那一点
想象地上有一条直线,空中悬着一个点 \(\mathbf b\)。用手电筒从 \(\mathbf b\) 的上方照下来,\(\mathbf b\) 会在直线上留下一个影子。光从不同方向照,影子落在不同的地方。
问题是:哪一个影子离 \(\mathbf b\) 最近?下面这张图里,拖动滑块改变光线的方向,看影子到 \(\mathbf b\) 的距离怎么变。也可以拖动 \(\mathbf b\)。
- 把光线调到垂直于直线(滑块读数 0°)。这时影子的距离有什么特别?
斜边永远比直角边长,所以垂直光线下的影子,就是直线上离 \(\mathbf b\) 最近的点。这个点叫 \(\mathbf b\) 在直线上的投影,记作 \(\mathbf p\)。从 \(\mathbf p\) 指向 \(\mathbf b\) 的那段叫残差 (residual) \(\mathbf e = \mathbf b - \mathbf p\),它和直线成直角。于是 \(\mathbf b\) 被拆成了两份:
投影 = 最近点 = 残差垂直。这三句话说的是同一件事。"最近"是一个要比较距离的优化问题,"垂直"是一个能用点积写出来的方程。把"最近"换成"垂直",我们就能直接算出答案,不用去试。这个想法会一直用到最小二乘。
3动手玩:投影实验室
拖动青色箭头 u 的尖端来转动那条过原点的直线,拖动 b 的尖端移动目标点。直线上那个空心的候选点 c 也能拖动,但它只能在直线上滑动。右下方的小图画出 \(|\mathbf b-\mathbf c|\) 随 c 的位置的变化。
- 把候选点 c 放到直线上离 b 最近的位置。小图里有什么标记告诉你对了?
- 在 \(\mathbf b\ne\mathbf 0\) 的前提下让 p = 0。u 和 b 此时是什么关系?
- 让 p 指向 u 的反方向。提示:看 \(\mathbf u\cdot\mathbf b\) 的符号。
- 让残差的长度正好是 b 的一半:\(|\mathbf e| = |\mathbf b|/2\)。这时 u 与 b 的夹角是多少度?
注意 \(\mathbf u\) 只是用来指方向的:把 \(\mathbf u\) 拉长或缩短,直线、投影 \(\mathbf p\)、残差 \(\mathbf e\) 都不变。公式里 \(\mathbf u\) 出现了两次(分子一次、分母一次),长度正好抵消。
4第二种视角:投影是一个矩阵
投影对 \(\mathbf b\) 是线性的:把 \(\mathbf b\) 放大 2 倍,投影也放大 2 倍;两个向量之和的投影,等于两个投影之和。根据 1.3 节,每个线性变换都对应一个矩阵,这个矩阵叫投影矩阵 \(P\)。它对整个平面做同一件事:把每一个点推到直线上最近的位置。
下面用 1.3 节的方式看它。拖动 \(\mathbf u\) 的尖端,点"作用一次",整张网格会被压扁到那条直线上。接着再点一次"再作用一次",什么都没有发生。
- 先"作用一次",再点"再作用一次"。数一数有几个点动了。
- 转动 u 让 \(P = \tfrac12\begin{bmatrix}1&1\\1&1\end{bmatrix}\)(直线 y = x)。u 的方向是什么?
| \(P = \dfrac{\mathbf u\mathbf u^\top}{\mathbf u^\top\mathbf u}\) | \(I - P\) | |
|---|---|---|
| 把平面压到 | u 所在的直线 | 垂直于 u 的直线 |
| 被送到 0 的向量 | 垂直于 u 的所有向量 | u 方向的所有向量 |
| 作用在 b 上得到 | \(\cv{\mathbf p}\) | \(\cw{\mathbf e}\) |
| \(P^2\) | \(P\) | \(I-P\) |
| \(\det\), 秩 | 0, 1 | 0, 1 |
把这些性质连在一起想:\(P\) 把 \(\mathbf b\) 压到直线上之后,信息已经丢掉了垂直方向的那一份,再压一次当然没有新东西可丢。所以 \(P^2=P\)(幂等,idempotent)。\(P\) 还是对称的(\(P^\top=P\)),这一点会在下一步"垂直"里起作用。最后,平面被压成一条线,面积变成 0,所以 \(\det P = 0\),\(P\) 的秩是 1,不可逆(1.5 节、1.6 节):知道了影子,你无法还原出原来的点。
5第三种视角:投影到平面,以及为什么要正交基
在三维里,可以把 \(\mathbf b\) 投影到一张过原点的平面上。想法完全一样:平面上离 \(\mathbf b\) 最近的点是 \(\mathbf p\),残差 \(\mathbf e=\mathbf b-\mathbf p\) 垂直于整张平面,也就是和平面的法向量 \(\mathbf n\) 平行。设 \(\mathbf n\) 是单位向量,残差就是 \(\mathbf b\) 在法向上的那一份 \((\mathbf n\cdot\mathbf b)\,\mathbf n\),所以
另一种写法是用平面里的两个互相垂直的单位向量 \(\mathbf q_1,\mathbf q_2\)(正交基)。此时投影就是把两条"沿线投影"加起来:\(\mathbf p=(\mathbf q_1\cdot\mathbf b)\mathbf q_1+(\mathbf q_2\cdot\mathbf b)\mathbf q_2\)。用滑块倾斜平面、移动 \(\mathbf b\),切换两种写法,看它们给出同一个 \(\mathbf p\)。拖动画面可以转动视角。
- 让 b 正好躺在平面里(\(\mathbf e=\mathbf 0\))。这时 \(\mathbf n\cdot\mathbf b\) 是多少?
- 让投影 p = 0(b 不为零)。提示:最容易的情形是水平的平面。
基向量互相垂直,投影就能一个方向一个方向地分开算。每个 \(\mathbf q_i\) 只管自己那条线,互不干扰,把各个投影加起来就行。如果基向量不互相垂直,一个方向上的分量会"漏"到另一个方向里,这个简单的加法就不对了(第 8 节的误区 3 会让你亲眼看到)。所以我们想要正交基。手里只有一组斜着的基怎么办?用 Gram–Schmidt 把它们掰正。
Gram–Schmidt:把斜基掰成正交基
给你两个不垂直的向量 \(\mathbf v_1,\mathbf v_2\)。做法只有三步,而且每一步都用到本节的投影:
- 保留 \(\mathbf v_1\)(方向不变)。
- 从 \(\mathbf v_2\) 里减去它在 \(\mathbf v_1\) 上的投影。剩下的残差 \(\mathbf w\) 垂直于 \(\mathbf v_1\)。
- 把两个向量单位化:\(\mathbf q_1=\mathbf v_1/|\mathbf v_1|\),\(\mathbf q_2=\mathbf w/|\mathbf w|\)。
用步骤按钮一步步走一遍,拖动 \(\mathbf v_1,\mathbf v_2\) 的尖端换一对向量。
- 走完全部 4 步,得到一对正交单位向量 \(\mathbf q_1,\mathbf q_2\)。
- 让 Gram–Schmidt 失败:把 \(\mathbf v_2\) 拖到和 \(\mathbf v_1\) 共线,使 \(\mathbf w\to\mathbf 0\)。为什么这时没法单位化?
6再看数学
提示:把鼠标悬停在公式中带底色的符号上,FIG 2、FIG 3、FIG 4、FIG 5 中对应的元素会被加粗。
投影到一条直线:从"残差垂直"推出公式
直线上的点都写成 \(t\,\mathbf u\)。投影 \(\mathbf p=t\,\mathbf u\) 的残差 \(\mathbf e=\mathbf b-t\,\mathbf u\) 要垂直于 \(\mathbf u\),也就是点积为零:
分母 \(\mathbf u\cdot\mathbf u=|\mathbf u|^2\) 保证了 \(\mathbf u\) 的长度不影响结果。当 \(\mathbf u=\hat{\mathbf u}\) 是单位向量时,分母为 1,公式简化成 1.7 节熟悉的样子:\(\mathbf p=(\hat{\mathbf u}\cdot\mathbf b)\,\hat{\mathbf u}\),其中 \(\hat{\mathbf u}\cdot\mathbf b\) 是投影的(带符号的)长度。
"最近"的说法可以独立验证:\(|\mathbf b-t\mathbf u|^2=|\mathbf b|^2-2t\,\mathbf u\cdot\mathbf b+t^2|\mathbf u|^2\) 是关于 \(t\) 的开口向上的抛物线,顶点在 \(t=\mathbf u\cdot\mathbf b/|\mathbf u|^2\),和上面一样。这就是 FIG 2 小图里最低点的位置。
投影矩阵
把标量 \(\mathbf u^\top\mathbf b\) 挪到 \(\mathbf u\) 的右边,立刻看出一个作用在 \(\mathbf b\) 上的矩阵:
\(\mathbf u\mathbf u^\top\) 是"列乘行"得到的 \(n\times n\) 矩阵(外积)。\(P^2=P\) 的证明只有一行:\((\mathbf u\mathbf u^\top)(\mathbf u\mathbf u^\top)=\mathbf u(\mathbf u^\top\mathbf u)\mathbf u^\top=(\mathbf u^\top\mathbf u)\,\mathbf u\mathbf u^\top\),除以 \((\mathbf u^\top\mathbf u)^2\) 就得到 \(P\)。一个具体的例子:\(\mathbf u=(2,1)\) 时
检查:\(\mathbf p+\mathbf e=(4,2)+(-1,2)=(3,4)=\mathbf b\),而且 \(\mathbf e\cdot\mathbf u=-2+2=0\)。\(P\) 的特征值是 1(沿 \(\mathbf u\))和 0(垂直于 \(\mathbf u\)),1.11 节会回到这一点。
正交分解与勾股定理
每个 \(\mathbf b\) 都能唯一地写成"直线内的一份 + 垂直于直线的一份"。因为 \(\mathbf p\cdot\mathbf e=0\),两份的平方长度直接相加:
\(|\mathbf e|\) 就是 \(\mathbf b\) 到直线的距离。在二维里还有一种算法:\(|\mathbf e| = |\hat{\mathbf u}\times\mathbf b|\),即 1.8 节里的二维叉积的绝对值(平行四边形面积除以底)。叉积的符号给出 \(\mathbf b\) 在直线左边还是右边,这正是 7 节里"有符号的横向误差"。
投影到子空间
设 \(Q=[\,\mathbf q_1\;\cdots\;\mathbf q_k\,]\) 的列是子空间的一组标准正交基(\(Q^\top Q=I\),1.10 节)。把每条线的投影加起来:
平面还有一种写法:设 \(\hl{n}{\mathbf n}\) 是平面的单位法向量,那么 \(P = I-\mathbf n\mathbf n^\top\),即 \(\mathbf p=\mathbf b-(\mathbf n\cdot\mathbf b)\,\mathbf n\)(FIG 4)。这在机器人里最常用:给一个接触面的法向量,去掉速度或力里"进出表面"的那份。
预告:一般的基。如果子空间的基是矩阵 \(A\) 的列,但它们不垂直,投影矩阵变成
当 \(A\) 只有一列 \(\mathbf u\) 时,\(A^\top A=\mathbf u^\top\mathbf u\),回到 \(\mathbf u\mathbf u^\top/\mathbf u^\top\mathbf u\);当 \(A=Q\) 有标准正交列时,\(A^\top A=I\),回到 \(QQ^\top\)。中间那个 \((A^\top A)^{-1}\) 就是"基不垂直"要付的代价,它会在 1.13 节的最小二乘里成为主角。
Gram–Schmidt
对线性无关的 \(\mathbf v_1,\dots,\mathbf v_k\),依次做:
第 \(k\) 步的意思是:先把 \(\mathbf v_k\) 投影到已经做好的 \(\mathbf q_1,\dots,\mathbf q_{k-1}\) 张成的子空间(正交基,所以逐条相加),再取残差。残差垂直于前面所有的 \(\mathbf q_j\)。如果 \(\mathbf w_k=\mathbf 0\),说明 \(\mathbf v_k\) 本来就在前面的张成空间里,向量线性相关(1.2 节),无法继续。把每一步的系数 \(r_{jk}=\mathbf q_j\cdot\mathbf v_k\) 和 \(r_{kk}=|\mathbf w_k|\) 记下来,就得到 \(A=QR\),其中 \(R\) 是上三角矩阵,这就是 QR 分解。
7机器人中的它:循迹误差与摩擦锥
路径跟踪:最近点、横向误差、沿路进度
路径通常是一条由若干线段连成的折线。要知道机器人 \(\mathbf r\) 在路径上"走到了哪",对每一段 \(\mathbf A\to\mathbf B\)(方向 \(\mathbf d=\mathbf B-\mathbf A\))做投影:
线段不是无限长的直线,所以要把 \(t\) 夹到 \([0,1]\):投影落到线段外面时,最近点就是端点。取所有线段里离 \(\mathbf r\) 最近的那个 \(\mathbf c\),得到最近点。\(e_{\text{ct}}\) 是有符号的横向误差(cross-track error):用 1.8 节的二维叉积,机器人在路径前进方向的左边为正,右边为负。沿路进度(along-track)是前面各段的长度之和,加上 \(t\,|\mathbf d|\)。拖动机器人,看每一段的候选最近点,还有哪一段赢了。
- 把机器人放在最近点从一段切换到下一段的位置:两段的距离几乎相等。这些位置连成什么形状?
- 把机器人拖到离路径至少 0.8 的地方,点"出发",看横向误差收敛到 0.1 以内。
路径跟踪控制器(纯追踪 pure pursuit、Stanley、MPC)的输入几乎都是这两个量:横向误差和航向误差,二者都由"最近点"得到。实现里要注意:最近点需要做"单调前进"(只在上次所在线段附近搜索),否则路径自交或往返时最近点会跳到另一段;在路径端点要夹 \(t\);在拐角的外侧,最近点是顶点本身,此时横向误差通常改用相邻两段方向的平均来定义。Snider (2009) 对这些控制律做了系统比较。
接触力:法向力、切向力与摩擦锥
手指(或一个箱子)压在一个表面上,表面的单位法向量是 \(\mathbf n\)(指向表面外),沿表面的单位方向是 \(\hat{\mathbf t}\)。受力 \(\mathbf F\) 是一个向量,它在两个方向上的投影就是
\(f_n>0\) 表示在压向表面,\(f_t\) 的正负表示沿表面的哪个方向。
库仑摩擦说:只要 \(f_n>0\)(确实在压着)且 \(|f_t|\le\mu f_n\),接触就粘住,否则打滑。把条件翻译成角度:\(\mathbf F\) 和"压进表面"方向 \(-\mathbf n\) 的夹角不超过 \(\arctan\mu\)。这些方向组成一个楔形,也就是二维里的摩擦锥。下面的图让你拖动力的箭头尖端,也可以点"箱子"预设,把力换成重力,用滑块倾斜斜面。
- 找到最陡但不打滑的推力方向:箭头方向正好贴着锥的边缘(偏差不超过 3°)。
- 点"箱子"预设,倾斜斜面,找到箱子刚好不下滑的最大角度(\(\tan\alpha\) 在 \(0.9\mu\) 与 \(\mu\) 之间)。
箱子在斜面上的结论很漂亮:重力 \(mg\) 的法向分量是 \(mg\cos\alpha\),切向分量是 \(mg\sin\alpha\),粘住的条件 \(mg\sin\alpha\le\mu\,mg\cos\alpha\) 化简成 \(\tan\alpha\le\mu\),质量约掉了。
抓取规划把每个接触点的摩擦锥当作约束:手指施加的力必须落在锥里,抓取才稳。三维里锥是圆锥,常被近似成四棱锥,好让条件变成线性不等式(本节的法向分量加上几个线性约束),交给二次规划去解(6.8 节)。Lynch & Park 第 12 章对此有完整讨论。
8常见误区
公式 \(\mathbf p=(\mathbf u\cdot\mathbf b)\,\mathbf u\) 只在 \(|\mathbf u|=1\) 时成立。对 \(\mathbf u=(2,1)\)、\(\mathbf b=(3,4)\),漏掉分母会得到 \((20,10)\),比 \(\mathbf b\) 本身还长,显然不是影子;正确答案是 \((4,2)\)。代码里最稳的做法:要么先 u = u / norm(u),要么直接写 u * dot(u,b) / dot(u,u),并在 \(\mathbf u\approx\mathbf 0\) 时提前返回。
直线无限长,线段有两个端点。点投影到线段所在直线上的位置如果落在线段外,最近点就是端点,距离会比到直线的距离更大。漏掉 clip(t, 0, 1) 是最经典的"点到线段距离"bug,症状是机器人在路径末端之外也"贴着路径",或者折线上两段的最近点判断错误。FIG 6 里把机器人拖到线段两端的外侧就能看到。
在平面里,任意两个不共线的向量 \(\mathbf u_1,\mathbf u_2\) 都张成整个平面,所以 \(\mathbf b\) 在它们张成的空间上的投影就是 \(\mathbf b\) 自己。然而把 \(\mathbf b\) 分别投影到 \(\mathbf u_1\) 和 \(\mathbf u_2\) 再相加,一般得不到 \(\mathbf b\)。只有 \(\mathbf u_1\perp\mathbf u_2\) 时才对。拖动两个基向量试试。
- 让两个基向量垂直,使"和"与 \(\mathbf b\) 重合(误差小于 0.1)。
上面的公式对精确算术是对的,但在浮点数里,当输入向量几乎共线时,相减会抵消掉几乎所有有效数字,剩下的是舍入误差,于是 \(\mathbf q_k\) 不再垂直于前面的向量。取四行三列的矩阵,第一行全是 1,下面是对角线上为 \(\varepsilon=10^{-8}\) 的 \(3\times3\) 矩阵(Läuchli 矩阵):经典 Gram–Schmidt 算出 \(\mathbf q_2\cdot\mathbf q_3=0.5\),完全不垂直;改良版 (modified) Gram–Schmidt 把每次减法立刻用在更新后的向量上,最差的 \(|\mathbf q_i\cdot\mathbf q_j|\)(\(i\ne j\))约为 \(10^{-8}\);Householder QR(numpy.linalg.qr 用的方法)约 \(10^{-16}\)。实际代码请用 QR 库函数,不要手写经典 Gram–Schmidt。
\(P\) 的秩比维数低,\(\det P=0\),所以 \(P^{-1}\) 不存在:直线上每一个点,都是垂直于直线的整条线上所有点的影子,只知道影子,没法判断原来的点在哪。需要"还原"时,要补上被丢掉的那一份 \(\mathbf e\),或者像 1.13 节那样退而求其次,只求"最好的"答案。
9小练习
10延伸阅读
- G. Strang, Introduction to Linear Algebra, §4.2 and §4.4 — "投影"与"标准正交基和 Gram–Schmidt"
- G. Strang, MIT 18.06 Linear Algebra (OCW) — 第 15、16、17 讲:子空间上的投影、投影矩阵、正交矩阵与 Gram–Schmidt
- K. Lynch & F. Park, Modern Robotics, Ch. 12 — 抓取与操作:接触、摩擦锥与力封闭
- J. M. Snider, “Automatic Steering Methods for Autonomous Automobile Path Tracking”, CMU-RI-TR-09-08, 2009 — 横向误差与纯追踪、Stanley 等路径跟踪控制律的比较
- L. N. Trefethen & D. Bau, Numerical Linear Algebra, Lectures 6–10 — 投影矩阵、QR、经典与改良 Gram–Schmidt、Householder