📘 第 8 章：向量空间的几何

本篇在干嘛

前面各章我们主要在”代数”地使用向量：求线性组合、解方程组、做正交化。第 8 章换一个视角——把向量看作点，把某些向量集合看作线段、多边形、立体等几何对象。核心手段是对线性组合的”权重”逐步加限制：

• 8.1 仿射组合：权重之和为 $1$；
• 8.2 仿射无关与重心坐标：权重唯一，用于计算机图形学插值；
• 8.3 凸组合：权重之和为 $1$ 且全部非负，得到凸集与凸包；
• 8.4 超平面：用一个线性方程 $\mathbf{n}\cdot \mathbf{x}=d$ 隐式描述，用于”分隔”两个集合；
• 8.5 多面体：凸包与顶点、面、支撑超平面，以及欧拉公式；
• 8.6 曲线与曲面：贝塞尔曲线，字体、CAD 和计算机图形学的数学基础。

全部内容对应 Lay《Linear Algebra and its Applications》第 5 版第 8 章，例题与练习题讲解完整保留。虽然画图都在 ${\mathbb{R}}^2,{\mathbb{R}}^3$，但所有概念对 ${\mathbb{R}}^n$ 乃至一般向量空间都成立。

开篇引入：柏拉图立体

公元前 387 年，柏拉图在雅典创立学园，门口刻着”不懂几何者不得入内”。希腊人痴迷于正多面体：所有面都是全等的正多边形、所有顶点处角度都相等。毕达哥拉斯学派早已知道四面体（4 个三角形面）、正方体（6 个正方形面）、八面体（8 个三角形面），它们以矿物晶体的形式自然存在。这类正多面体总共只有五种，剩下两种是十二面体（12 个五边形面）和二十面体（20 个三角形面），柏拉图在《蒂迈欧篇》中讨论了它们的理论，因此合称柏拉图立体。

图 8-1：自然界中以正多面体形状出现的矿物晶体

图 8-2：五种柏拉图立体

几个世纪里人们不需要想象三维以上的几何对象，但今天的数学家经常处理四维、五维甚至上百维向量空间中的对象。哪些二维、三维的几何性质可以推广到高维？本章给出部分答案：8.1 和 8.4 节刻画”直线”与”平面”的高维推广（超平面，第 9 章线性规划的基础）；8.5 节用投影的方式”看”四维的”立方体”与”单纯形”；8.2 和 8.6 节包含计算机图形学应用；8.5 节习题还给出了 ${\mathbb{R}}^3$ 中正多面体只有五种的一个证明思路。

8.1 仿射组合

什么是仿射组合

给定 ${\mathbb{R}}^n$ 中的向量（点）${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_p$ 与标量 $c_1,\dots ,c_p$，若线性组合

$$c_1{\mathbf{v}}_1+\cdots +c_p{\mathbf{v}}_p$$

的权重满足 $c_1+\cdots +c_p=1$，就称它为 ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_p$ 的一个仿射组合。

定义（仿射包）：集合 $S$ 中各点的全部仿射组合构成的集合，称为 $S$ 的仿射包（或仿射张成），记作 $\mathrm{aff}S$。

直观理解：普通线性组合允许权重任意，因此永远包含原点、可以”张满”整个子空间；仿射组合把权重总和锁定为 $1$，等于砍掉了”缩放原点”的自由度，得到的不再是一个过原点的子空间，而是一个平移过的几何对象。

单个点 ${\mathbf{v}}_1$ 的仿射包就是 $\{{\mathbf{v}}_1\}$（权重只能取 $c_1=1$）。两个不同点的仿射包有特别的形式：设 $\mathbf{y}=c_1{\mathbf{v}}_1+c_2{\mathbf{v}}_2$，$c_1+c_2=1$，令 $t=c_2$，则 $c_1=1-t$，于是

$$\mathbf{y}=(1-t){\mathbf{v}}_1+t{\mathbf{v}}_2,t\in \mathbb{R}$$

当 $t=0$ 时得 ${\mathbf{v}}_1$，$t=1$ 时得 ${\mathbf{v}}_2$。把它改写成

$$\mathbf{y}={\mathbf{v}}_1+t({\mathbf{v}}_2-{\mathbf{v}}_1)=\mathbf{p}+t\mathbf{u}$$

其中 $\mathbf{p}={\mathbf{v}}_1$，$\mathbf{u}={\mathbf{v}}_2-{\mathbf{v}}_1$。这就是第 1.5 节见过的直线参数方程：过原点的直线 $\mathrm{Span}\{\mathbf{u}\}$ 整体平移 $\mathbf{p}$ 之后，就得到过 ${\mathbf{v}}_1,{\mathbf{v}}_2$ 的直线。

图 8-3：$\mathbf{y}=\mathbf{p}+t\mathbf{u}$ 是把 $\mathrm{Span}\{\mathbf{u}\}$ 平移 $\mathbf{p}$ 得到的直线

图 8-4：$\mathrm{aff}\{{\mathbf{v}}_1,{\mathbf{v}}_2\}$ 就是过 ${\mathbf{v}}_1,{\mathbf{v}}_2$ 的整条直线

注意图中 $\mathbf{y}$ 是 ${\mathbf{v}}_1,{\mathbf{v}}_2$ 的仿射组合，而 $\mathbf{y}-{\mathbf{v}}_1=t({\mathbf{v}}_2-{\mathbf{v}}_1)$ 是平移后向量的线性组合。这个”减掉一个基准点就把仿射问题变成线性问题”的想法，正是下面定理的内容。

定理 1：仿射组合 ⟺ 平移后的线性组合

${\mathbb{R}}^n$ 中的点 $\mathbf{y}$ 是 ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_p$ 的仿射组合，当且仅当 $\mathbf{y}-{\mathbf{v}}_1$ 是平移向量 ${\mathbf{v}}_2-{\mathbf{v}}_1,\dots ,{\mathbf{v}}_p-{\mathbf{v}}_1$ 的线性组合。

证明思路：若 $\mathbf{y}-{\mathbf{v}}_1=c_2({\mathbf{v}}_2-{\mathbf{v}}_1)+\cdots +c_p({\mathbf{v}}_p-{\mathbf{v}}_1)$，展开整理得

$$\mathbf{y}=(1-c_2-\cdots -c_p){\mathbf{v}}_1+c_2{\mathbf{v}}_2+\cdots +c_p{\mathbf{v}}_p$$

各权重之和恰为 $1$，故 $\mathbf{y}$ 是仿射组合。反过来，从 $\mathbf{y}=c_1{\mathbf{v}}_1+\cdots +c_p{\mathbf{v}}_p$（权重和为 $1$）出发，用 $c_1=1-c_2-\cdots -c_p$ 移项即得前一式。∎

定理中的基准点 ${\mathbf{v}}_1$ 可以换成列表中的任何一个点，只是记号变化。这是判断”某点是否在仿射包里”的标准算法：全部减去 ${\mathbf{v}}_1$，然后做普通的行化简判线性组合。

例 1

设 ${\mathbf{v}}_1=\left[\begin{array}{c}1\\ 2\end{array}\right],{\mathbf{v}}_2=\left[\begin{array}{c}2\\ 5\end{array}\right],{\mathbf{v}}_3=\left[\begin{array}{c}1\\ 3\end{array}\right],{\mathbf{v}}_4=\left[\begin{array}{c}-2\\ 2\end{array}\right],\mathbf{y}=\left[\begin{array}{c}4\\ 1\end{array}\right]$。若可能，把 $\mathbf{y}$ 写成 ${\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3,{\mathbf{v}}_4$ 的仿射组合。

解 先算平移点：

$${\mathbf{v}}_2-{\mathbf{v}}_1=\left[\begin{array}{c}1\\ 3\end{array}\right],{\mathbf{v}}_3-{\mathbf{v}}_1=\left[\begin{array}{c}0\\ 1\end{array}\right],{\mathbf{v}}_4-{\mathbf{v}}_1=\left[\begin{array}{c}-3\\ 0\end{array}\right],\mathbf{y}-{\mathbf{v}}_1=\left[\begin{array}{c}3\\ -1\end{array}\right]$$

求标量 $c_2,c_3,c_4$ 使 $c_2({\mathbf{v}}_2-{\mathbf{v}}_1)+c_3({\mathbf{v}}_3-{\mathbf{v}}_1)+c_4({\mathbf{v}}_4-{\mathbf{v}}_1)=\mathbf{y}-{\mathbf{v}}_1$，对增广矩阵行化简：

$$\left[\begin{array}{cccc}1& 0& -3& 3\\ 3& 1& 0& -1\end{array}\right]\sim \left[\begin{array}{cccc}1& 0& -3& 3\\ 0& 1& 9& -10\end{array}\right]$$

方程组相容，通解为 $c_2=3c_4+3,c_3=-9c_4-10$，$c_4$ 为自由变量。取 $c_4=0$：

$$\mathbf{y}-{\mathbf{v}}_1=3({\mathbf{v}}_2-{\mathbf{v}}_1)-10({\mathbf{v}}_3-{\mathbf{v}}_1)+0({\mathbf{v}}_4-{\mathbf{v}}_1)$$

从而

$$\mathbf{y}=8{\mathbf{v}}_1+3{\mathbf{v}}_2-10{\mathbf{v}}_3$$

（验证权重和：$8+3-10=1$ ✓。）再取 $c_4=1$，得 $c_2=6,c_3=-19$，于是

$$\mathbf{y}=13{\mathbf{v}}_1+6{\mathbf{v}}_2-19{\mathbf{v}}_3+{\mathbf{v}}_4$$

这说明表示不唯一——自由变量提供了无穷多种写法。

常见坑

“能不能表示成仿射组合”判断的是相容性；解不唯一是常态，不要被”答案不唯一”吓到。另外权重可以是负数、可以大于 1——只要总和为 1 就行，这是仿射与后面”凸”的关键区别。

若所选点恰好是 ${\mathbb{R}}^n$ 的一组基 $B=\{{\mathbf{b}}_1,\dots ,{\mathbf{b}}_n\}$，问题更直接：任何 $\mathbf{y}$ 都有唯一的线性组合 $\mathbf{y}=c_1{\mathbf{b}}_1+\cdots +c_n{\mathbf{b}}_n$，而这个组合是仿射组合当且仅当权重之和为 $1$（这些权重就是 $\mathbf{y}$ 的 $B$-坐标，见 4.4 节）。

例 2

设 ${\mathbf{b}}_1=\left[\begin{array}{c}4\\ 0\\ 3\end{array}\right],{\mathbf{b}}_2=\left[\begin{array}{c}0\\ 4\\ 2\end{array}\right],{\mathbf{b}}_3=\left[\begin{array}{c}5\\ 2\\ 4\end{array}\right],{\mathbf{p}}_1=\left[\begin{array}{c}2\\ 0\\ 0\end{array}\right],{\mathbf{p}}_2=\left[\begin{array}{c}1\\ 2\\ 2\end{array}\right]$。已知 $B=\{{\mathbf{b}}_1,{\mathbf{b}}_2,{\mathbf{b}}_3\}$ 是 ${\mathbb{R}}^3$ 的基，判断 ${\mathbf{p}}_1,{\mathbf{p}}_2$ 是否为 $B$ 中点的仿射组合。

解 两个判断合并做：对 $[{\mathbf{b}}_1{\mathbf{b}}_2{\mathbf{b}}_3{\mathbf{p}}_1{\mathbf{p}}_2]$ 行化简（两个增广列）：

$$\left[\begin{array}{ccccc}4& 0& 5& 2& 1\\ 0& 4& 2& 0& 2\\ 3& 2& 4& 0& 2\end{array}\right]\sim \left[\begin{array}{ccccc}1& 0& 0& -2& \frac{2}{3}\\ 0& 1& 0& -1& \frac{2}{3}\\ 0& 0& 1& 2& -\frac{1}{3}\end{array}\right]$$

读第 4 列得 ${\mathbf{p}}_1=-2{\mathbf{b}}_1-{\mathbf{b}}_2+2{\mathbf{b}}_3$，权重和 $-2-1+2=-1\ne 1$，故 ${\mathbf{p}}_1$ 不是仿射组合；读第 5 列得 ${\mathbf{p}}_2=\frac{2}{3}{\mathbf{b}}_1+\frac{2}{3}{\mathbf{b}}_2-\frac{1}{3}{\mathbf{b}}_3$，权重和 $1$，故 ${\mathbf{p}}_2$ 是仿射组合。

仿射集与”平集”（flat）

定义：集合 $S$ 称为仿射的，若 $\mathbf{p},\mathbf{q}\in S$ 蕴含 $(1-t)\mathbf{p}+t\mathbf{q}\in S$ 对每个实数 $t$ 成立。

几何上：只要两点在集合里，过这两点的整条直线就在集合里。代数上：定义只要求”两点的仿射组合仍在集合内”，但下面的定理说明这等价于”任意多个点的仿射组合仍在集合内”。

定理 2

集合 $S$ 是仿射的，当且仅当 $S$ 中点的每一个仿射组合都属于 $S$，即 $S=\mathrm{aff}S$。

证明思路：对组合中点的个数 $m$ 作数学归纳。$m=1,2$ 时由定义成立。设 $k$ 个点的情形成立，考虑 $k+1$ 个点：$\mathbf{y}=c_1{\mathbf{v}}_1+\cdots +c_k{\mathbf{v}}_k+c_{k+1}{\mathbf{v}}_{k+1}$，权重和为 1。必有某个权重 $\ne 1$，不妨设 $c_{k+1}\ne 1$，令 $t=c_1+\cdots +c_k=1-c_{k+1}\ne 0$，改写为

$$\mathbf{y}=(1-c_{k+1})\underset{\text{系数和为 1，由归纳假设其在 }S}{\underbrace{\left(\frac{c_1}{t}{\mathbf{v}}_1+\cdots +\frac{c_k}{t}{\mathbf{v}}_k\right)}}+c_{k+1}{\mathbf{v}}_{k+1}$$

这成为 $S$ 中两点的仿射组合，故 $\mathbf{y}\in S$。∎

接下来是与子空间对应的一套术语：

定义：用向量 $\mathbf{p}$ 平移集合 $S$ 得到的集合是 $S+\mathbf{p}=\{\mathbf{s}+\mathbf{p}:\mathbf{s}\in S\}$。${\mathbb{R}}^n$ 的一个子空间的平移称为一个 flat（平集）。两个平集若互为平移则称平行。平集的维数就是对应平行子空间的维数。集合 $S$ 的维数 $\dim S$ 定义为包含 $S$ 的最小平集的维数。维数为 1 的平集叫直线，维数为 $n-1$ 的平集叫超平面。

在 ${\mathbb{R}}^3$ 中，真子空间只有原点、过原点的直线、过原点的平面；所以 ${\mathbb{R}}^3$ 中的真平集就是点（0 维）、直线（1 维）、平面（2 维），可以过原点也可以不过。

定理 3

非空集合 $S$ 是仿射的，当且仅当 $S$ 是一个平集。

证明思路：（⇒）取定 $\mathbf{p}\in S$，令 $W=S+(-\mathbf{p})$，即 $S=W+\mathbf{p}$，只需证 $W$ 是子空间。$0\in W$ 显然。对 ${\mathbf{u}}_1={\mathbf{s}}_1-\mathbf{p},{\mathbf{u}}_2={\mathbf{s}}_2-\mathbf{p}\in W$ 与任意实数 $t$：

$${\mathbf{u}}_1+t{\mathbf{u}}_2=({\mathbf{s}}_1-\mathbf{p})+t({\mathbf{s}}_2-\mathbf{p})=(1-t){\mathbf{s}}_1+t\underset{\text{是 }S\text{ 中点的仿射组合，故在 }S}{\underbrace{({\mathbf{s}}_1+{\mathbf{s}}_2-\mathbf{p})}}-\mathbf{p}$$

由定理 2 知 $\mathbf{y}={\mathbf{s}}_1+{\mathbf{s}}_2-\mathbf{p}\in S$，于是 $(1-t){\mathbf{s}}_1+t\mathbf{y}\in S$，故 ${\mathbf{u}}_1+t{\mathbf{u}}_2\in W$，$W$ 对加法与数乘封闭，是子空间。（⇐）若 $S=W+\mathbf{p}$，对 ${\mathbf{s}}_1={\mathbf{u}}_1+\mathbf{p},{\mathbf{s}}_2={\mathbf{u}}_2+\mathbf{p}$ 有 $(1-t){\mathbf{s}}_1+t{\mathbf{s}}_2=(1-t){\mathbf{u}}_1+t{\mathbf{u}}_2+\mathbf{p}\in W+\mathbf{p}=S$，故 $S$ 仿射。∎

定理 3 给出了仿射包的几何看法：$\mathrm{aff}S$ 就是把 $S$ 中所有点做仿射组合得到的那个”平集”。

图 8-5：例 2 中的点。${\mathbf{b}}_1,{\mathbf{b}}_2,{\mathbf{b}}_3$ 的全部线性组合是整个 ${\mathbb{R}}^3$，但全部仿射组合只是过这三点的平面；${\mathbf{p}}_2$ 在平面上而 ${\mathbf{p}}_1$ 不在

仿射包与方程组的解集

例 3

设方程 $A\mathbf{x}=\mathbf{b}$ 的解都具有形式 $\mathbf{x}=x_3\mathbf{u}+\mathbf{p}$，其中 $\mathbf{u}=\left[\begin{array}{c}2\\ -3\\ 1\end{array}\right],\mathbf{p}=\left[\begin{array}{c}4\\ 0\\ -3\end{array}\right]$。求两点 ${\mathbf{v}}_1,{\mathbf{v}}_2$，使解集等于 $\mathrm{aff}\{{\mathbf{v}}_1,{\mathbf{v}}_2\}$。

解 解集是一条过 $\mathbf{p}$、方向为 $\mathbf{u}$ 的直线，而 $\mathrm{aff}\{{\mathbf{v}}_1,{\mathbf{v}}_2\}$ 是过 ${\mathbf{v}}_1,{\mathbf{v}}_2$ 的直线，所以只需在解集直线上任取两点。取 $x_3=0,1$ 对应的点：

$${\mathbf{v}}_1=\mathbf{p}=\left[\begin{array}{c}4\\ 0\\ -3\end{array}\right],{\mathbf{v}}_2=\mathbf{u}+\mathbf{p}=\left[\begin{array}{c}2\\ -3\\ 1\end{array}\right]+\left[\begin{array}{c}4\\ 0\\ -3\end{array}\right]=\left[\begin{array}{c}6\\ -3\\ -2\end{array}\right]$$

于是解集可写成

$$\mathbf{x}=(1-x_3)\left[\begin{array}{c}4\\ 0\\ -3\end{array}\right]+x_3\left[\begin{array}{c}6\\ -3\\ -2\end{array}\right]$$

这个例子印证了 1.5 节的结论：$A\mathbf{x}=\mathbf{b}$ 的解集是 $A\mathbf{x}=0$ 解集（子空间）的平移——用新语言说就是”解集是仿射集”。

齐次形式：把仿射问题变回线性问题的另一招

对 $\mathbf{v}\in {\mathbb{R}}^n$，把末尾添一个 1 得到 $\tilde{\mathbf{v}}=\left[\begin{array}{c}\mathbf{v}\\ 1\end{array}\right]\in {\mathbb{R}}^{n+1}$，称为 $\mathbf{v}$ 的标准齐次形式。

定理 4

${\mathbb{R}}^n$ 中的点 $\mathbf{y}$ 是 ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_p$ 的仿射组合，当且仅当 $\mathbf{y}$ 的齐次形式属于 $\mathrm{Span}\{{\tilde{\mathbf{v}}}_1,\dots ,{\tilde{\mathbf{v}}}_p\}$。事实上，$\mathbf{y}=c_1{\mathbf{v}}_1+\cdots +c_p{\mathbf{v}}_p$ 且 $c_1+\cdots +c_p=1$，当且仅当 $\tilde{\mathbf{y}}=c_1{\tilde{\mathbf{v}}}_1+\cdots +c_p{\tilde{\mathbf{v}}}_p$。

证明：比较等式 $\left[\begin{array}{c}\mathbf{y}\\ 1\end{array}\right]=c_1\left[\begin{array}{c}{\mathbf{v}}_1\\ 1\end{array}\right]+\cdots +c_p\left[\begin{array}{c}{\mathbf{v}}_p\\ 1\end{array}\right]$ 的前 $n$ 行与最后一行：前 $n$ 行给出线性组合式，最后一行恰好强制 $c_1+\cdots +c_p=1$。∎

为什么好用？ 因为”权重和为 1”这个约束被自动编码进了向量的最后一行，判断仿射组合只需对 $[{\tilde{\mathbf{v}}}_1\cdots {\tilde{\mathbf{v}}}_p\tilde{\mathbf{p}}]$ 做一次普通的行化简。

例 4

设 ${\mathbf{v}}_1=\left[\begin{array}{c}3\\ 1\\ 1\end{array}\right],{\mathbf{v}}_2=\left[\begin{array}{c}1\\ 2\\ 2\end{array}\right],{\mathbf{v}}_3=\left[\begin{array}{c}1\\ 7\\ 1\end{array}\right],\mathbf{p}=\left[\begin{array}{c}4\\ 3\\ 0\end{array}\right]$。用定理 4 把 $\mathbf{p}$ 写成 ${\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3$ 的仿射组合（若可能）。

解 对方程 $x_1{\tilde{\mathbf{v}}}_1+x_2{\tilde{\mathbf{v}}}_2+x_3{\tilde{\mathbf{v}}}_3=\tilde{\mathbf{p}}$ 的增广矩阵行化简。为简化计算，把最后一行 1 移到最上面：

$$\left[\begin{array}{cccc}1& 1& 1& 1\\ 3& 1& 1& 4\\ 1& 2& 7& 3\\ 1& 2& 1& 0\end{array}\right]\sim \left[\begin{array}{cccc}1& 1& 1& 1\\ 0& -2& -2& 1\\ 0& 1& 6& 2\\ 0& 1& 0& -1\end{array}\right]\sim \cdots \sim \left[\begin{array}{cccc}1& 0& 0& 1.5\\ 0& 1& 0& -1\\ 0& 0& 1& 0.5\\ 0& 0& 0& 0\end{array}\right]$$

由定理 4，$\mathbf{p}=1.5{\mathbf{v}}_1-{\mathbf{v}}_2+0.5{\mathbf{v}}_3$（权重和 $1.5-1+0.5=1$ ✓）。图 8-6 展示了包含这四个点的平面。

图 8-6：${\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3,\mathbf{p}$ 共同所在的平面

8.1 练习题（Practice Problem）

题目：在坐标纸上画出 ${\mathbf{v}}_1=\left[\begin{array}{c}1\\ 0\end{array}\right],{\mathbf{v}}_2=\left[\begin{array}{c}-1\\ 2\end{array}\right],{\mathbf{v}}_3=\left[\begin{array}{c}3\\ 1\end{array}\right],\mathbf{p}=\left[\begin{array}{c}4\\ 3\end{array}\right]$，解释为什么 $\mathbf{p}$ 必是 ${\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3$ 的仿射组合，并求出该组合。

解答：三点不共线，故 $\mathrm{aff}\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3\}$ 不可能是一维的；${\mathbb{R}}^2$ 中非一维的平集只能是整个 ${\mathbb{R}}^2$，所以 $\mathbf{p}$ 一定在仿射包里。为求权重，先算

$${\mathbf{v}}_2-{\mathbf{v}}_1=\left[\begin{array}{c}-2\\ 2\end{array}\right],{\mathbf{v}}_3-{\mathbf{v}}_1=\left[\begin{array}{c}2\\ 1\end{array}\right],\mathbf{p}-{\mathbf{v}}_1=\left[\begin{array}{c}3\\ 3\end{array}\right]$$

行化简：

$$\left[\begin{array}{ccc}-2& 2& 3\\ 2& 1& 3\end{array}\right]\sim \left[\begin{array}{ccc}1& 0& \frac{1}{2}\\ 0& 1& 2\end{array}\right]$$

故 $\mathbf{p}-{\mathbf{v}}_1=\frac{1}{2}({\mathbf{v}}_2-{\mathbf{v}}_1)+2({\mathbf{v}}_3-{\mathbf{v}}_1)$，即

$$\mathbf{p}=\left(1-\frac{1}{2}-2\right){\mathbf{v}}_1+\frac{1}{2}{\mathbf{v}}_2+2{\mathbf{v}}_3=-\frac{3}{2}{\mathbf{v}}_1+\frac{1}{2}{\mathbf{v}}_2+2{\mathbf{v}}_3$$

系数和为 $1$，确实是仿射组合。也可以用例 4 的齐次形式方法行化简，得到同样的结果。

图 8-7：练习题各点作图示意——${\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3$ 不共线，仿射包为全平面

通关标准

• 会用”减去基准点 + 行化简”或”齐次形式 + 行化简”两种方法判断并求仿射组合；
• 说得出仿射集 = 平集 = 子空间的平移，直线是 1 维平集、超平面是 $n-1$ 维平集；
• 知道 $A\mathbf{x}=\mathbf{b}$ 的解集为什么是仿射集。

本节习题（判断仿射组合、找点张成指定平面、证明线性变换保持仿射性等）见原书 8.1 节。

8.2 仿射无关

仿射相关的定义

在 ${\mathbb{R}}^3$ 中考虑三个向量 $\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3\}$。若 ${\mathbf{v}}_3=(1-t){\mathbf{v}}_1+t{\mathbf{v}}_2$（${\mathbf{v}}_3$ 是前两个的仿射组合），则

$$(1-t){\mathbf{v}}_1+t{\mathbf{v}}_2-{\mathbf{v}}_3=0$$

这是一个线性相关关系，而且有一个额外的漂亮性质：权重之和为 0：$(1-t)+t+(-1)=0$。这就引出：

定义：${\mathbb{R}}^n$ 中的指标集 $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_p\}$ 称为仿射相关的，若存在不全为零的实数 $c_1,\dots ,c_p$ 使

$$c_1+\cdots +c_p=0\text{且}{c}_1{\mathbf{v}}_1+\cdots +c_p{\mathbf{v}}_p=0$$

否则称为仿射无关的。

仿射组合是特殊的线性组合，所以仿射相关是”受限版”的线性相关——每个仿射相关的集合自动线性相关，反之不成立。只含一个点的集合（哪怕 $\{0\}$）总是仿射无关的，因为单个系数既要非零又要等于零，矛盾。两个点仿射相关当且仅当两点重合。

定理 5：仿射相关的四个等价刻画

设 $S=\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_p\}$ 是 ${\mathbb{R}}^n$ 中的指标集，$p\ge 2$。下列命题逻辑等价（同真同假）：

• a. $S$ 仿射相关；
• b. $S$ 中某点是其余点的仿射组合；
• c. 平移后的集合 $\{{\mathbf{v}}_2-{\mathbf{v}}_1,\dots ,{\mathbf{v}}_p-{\mathbf{v}}_1\}$ 线性相关；
• d. 齐次形式集合 $\{{\tilde{\mathbf{v}}}_1,\dots ,{\tilde{\mathbf{v}}}_p\}\subset {\mathbb{R}}^{n+1}$ 线性相关。

证明思路：(a)⇒(b)：把权重关系除以 $c_1$ 解出 ${\mathbf{v}}_1$，右端系数和为 1。(b)⇒(c)：由 ${\mathbf{v}}_1=c_2{\mathbf{v}}_2+\cdots +c_p{\mathbf{v}}_p$（$c_2+\cdots +c_p=1$）移项得 $c_2({\mathbf{v}}_2-{\mathbf{v}}_1)+\cdots +c_p({\mathbf{v}}_p-{\mathbf{v}}_1)=0$，且 $c_2,\dots ,c_p$ 不全为零。(c)⇒(a)：反向重排并令 $c_1=-(c_2+\cdots +c_p)$。(d) 与 (a) 的等价来自齐次形式把”权重和为零”与”组合为零”合并成一个方程。∎

常见坑

(c) 中的基准点 ${\mathbf{v}}_1$ 可换成任意一点，但必须同一个点减到底——一部分减 ${\mathbf{v}}_1$、另一部分减 ${\mathbf{v}}_2$，得到的集合就不再对应仿射相关性了。

例 1

两个不同点 $\mathbf{p},\mathbf{q}$ 的仿射包是一条直线。若第三个点 $\mathbf{r}$ 在这条直线上，则 $\{\mathbf{p},\mathbf{q},\mathbf{r}\}$ 仿射相关；若点 $\mathbf{s}$ 不在过 $\mathbf{p},\mathbf{q}$ 的直线上，则三点不共线，$\{\mathbf{p},\mathbf{q},\mathbf{s}\}$ 仿射无关。

图 8-8：$\mathbf{p},\mathbf{q},\mathbf{r}$ 共线，仿射相关；不在直线上的 $\mathbf{s}$ 使三点仿射无关

例 2

设 ${\mathbf{v}}_1=\left[\begin{array}{c}1\\ 3\\ 7\end{array}\right],{\mathbf{v}}_2=\left[\begin{array}{c}2\\ 7\\ 6.5\end{array}\right],{\mathbf{v}}_3=\left[\begin{array}{c}0\\ 4\\ 7\end{array}\right]$，$S=\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3\}$。判断 $S$ 是否仿射无关。

解 计算 ${\mathbf{v}}_2-{\mathbf{v}}_1=\left[\begin{array}{c}1\\ 4\\ -0.5\end{array}\right]$，${\mathbf{v}}_3-{\mathbf{v}}_1=\left[\begin{array}{c}-1\\ 1\\ 0\end{array}\right]$。这两个向量不成倍数，线性无关，故定理 5 各条全不成立，$S$ 仿射无关。图 8-9 中 $\mathrm{Span}{S}^{\prime }$ 是过原点的平面，$\mathrm{aff}S$ 是过 ${\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3$ 的平行平面。

图 8-9：仿射无关集 $\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3\}$ 与平移后的线性无关集 $S^{\prime }$

例 3

在例 2 中加入 ${\mathbf{v}}_4=\left[\begin{array}{c}0\\ 14\\ 6\end{array}\right]$，$S=\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_4\}$ 是否仿射相关？

解 计算 ${\mathbf{v}}_4-{\mathbf{v}}_1=\left[\begin{array}{c}-1\\ 11\\ -1\end{array}\right]$，对平移点组成的矩阵行化简：

$$\left[\begin{array}{rrr}1& -1& -1\\ 4& 1& 11\\ -0.5& 0& -1\end{array}\right]\sim \left[\begin{array}{rrr}1& -1& -1\\ 0& 5& 15\\ 0& -0.5& -1.5\end{array}\right]\sim \left[\begin{array}{rrr}1& -1& -1\\ 0& 5& 15\\ 0& 0& 0\end{array}\right]$$

不是每列都是主元列，平移点线性相关，由定理 5(c)，$S$ 仿射相关。完整行化简还可得

$${\mathbf{v}}_4-{\mathbf{v}}_1=2({\mathbf{v}}_2-{\mathbf{v}}_1)+3({\mathbf{v}}_3-{\mathbf{v}}_1)⟺{\mathbf{v}}_4=-4{\mathbf{v}}_1+2{\mathbf{v}}_2+3{\mathbf{v}}_3$$

即 ${\mathbf{v}}_4$ 落在平面 $\mathrm{aff}\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3\}$ 内（图 8-10）。第二个式子中系数 $-4,2,3$（和为 1）就是 ${\mathbf{v}}_4$ 相对于 $\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3\}$ 的仿射坐标（重心坐标）。

图 8-10：${\mathbf{v}}_4$ 落在平面 $\mathrm{aff}\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3\}$ 内，两套网格对应两种坐标表示

重心坐标（Barycentric Coordinates）

定理 6（唯一表示定理的仿射版）

设 $S=\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\}$ 是 ${\mathbb{R}}^n$ 中的仿射无关集，则 $\mathrm{aff}S$ 中每个点 $\mathbf{p}$ 都有唯一的仿射组合表示：

$$\mathbf{p}=c_1{\mathbf{v}}_1+\cdots +c_k{\mathbf{v}}_k,c_1+\cdots +c_k=1$$

这组唯一的系数 $c_1,\dots ,c_k$ 称为 $\mathbf{p}$ 的重心坐标（也称仿射坐标）。

注意到上式等价于关于齐次形式的单个方程

$$\left[\begin{array}{c}\mathbf{p}\\ 1\end{array}\right]=c_1\left[\begin{array}{c}{\mathbf{v}}_1\\ 1\end{array}\right]+\cdots +c_k\left[\begin{array}{c}{\mathbf{v}}_k\\ 1\end{array}\right]$$

所以对增广矩阵 $[{\tilde{\mathbf{v}}}_1\cdots {\tilde{\mathbf{v}}}_k\tilde{\mathbf{p}}]$ 行化简即可求出重心坐标。

例 4

设 $\mathbf{a}=\left[\begin{array}{c}1\\ 7\end{array}\right],\mathbf{b}=\left[\begin{array}{c}3\\ 0\end{array}\right],\mathbf{c}=\left[\begin{array}{c}9\\ 3\end{array}\right],\mathbf{p}=\left[\begin{array}{c}5\\ 3\end{array}\right]$。求 $\mathbf{p}$ 关于仿射无关集 $\{\mathbf{a},\mathbf{b},\mathbf{c}\}$ 的重心坐标。

解 对齐次形式增广矩阵行化简（把 1 行移到最上）：

$$[\tilde{\mathbf{a}}\tilde{\mathbf{b}}\tilde{\mathbf{c}}\tilde{\mathbf{p}}]=\left[\begin{array}{cccc}1& 3& 9& 5\\ 7& 0& 3& 3\\ 1& 1& 1& 1\end{array}\right]\sim \left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 3& 9& 5\\ 7& 0& 3& 3\end{array}\right]\sim \left[\begin{array}{cccc}1& 0& 0& \frac{1}{4}\\ 0& 1& 0& \frac{1}{3}\\ 0& 0& 1& \frac{5}{12}\end{array}\right]$$

重心坐标为 $\frac{1}{4},\frac{1}{3},\frac{5}{12}$，即 $\mathbf{p}=\frac{1}{4}\mathbf{a}+\frac{1}{3}\mathbf{b}+\frac{5}{12}\mathbf{c}$。

重心坐标由 Möbius 于 1827 年提出，有物理与几何两重解释。物理上：若在三角形顶点 $\mathbf{a},\mathbf{b},\mathbf{c}$ 处分别放置质量 $m_{\mathbf{a}},m_{\mathbf{b}},m_{\mathbf{c}}$（总和为 1），则 $\mathbf{p}$ 就是这个质点系的质心（重心）。几何上：$\mathbf{p}$ 把三角形 $△\mathbf{abc}$ 分成三个小三角形 $△\mathbf{pbc}$、$△\mathbf{apc}$、$△\mathbf{abp}$，三个小三角形与大三角形的面积比恰好等于三个重心坐标。一般地，若 $\mathbf{p}=r\mathbf{a}+s\mathbf{b}+t\mathbf{c}$，则

$$\mathrm{area}(\Delta \mathbf{pbc})=r\cdot \mathrm{area}(\Delta \mathbf{abc}),\mathrm{area}(\Delta \mathbf{apc})=s\cdot \mathrm{area}(\Delta \mathbf{abc}),\mathrm{area}(\Delta \mathbf{abp})=t\cdot \mathrm{area}(\Delta \mathbf{abc})$$

在例 4 中即面积比 $\frac{1}{4},\frac{1}{3},\frac{5}{12}$（公式在原书习题 21–23 中验证；三维中四面体体积有类似结论）。当 $\mathbf{p}$ 落在三角形外时，某些重心坐标为负：过 $\mathbf{b},\mathbf{c}$ 的直线上的点满足 $r=0$（它们只是 $\mathbf{b},\mathbf{c}$ 的仿射组合），而过 $\mathbf{a}$ 的平行线上的点满足 $r=1$。

图 8-11：$\mathrm{aff}\{\mathbf{a},\mathbf{b},\mathbf{c}\}$ 中点的重心坐标取值区域——三角形内部坐标全正，越出某条边则对应坐标变负

常见坑

重心坐标唯一的前提是 $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\}$ 仿射无关。点在”三角形内”对应全正的坐标，“在边上”对应某个坐标为 0，“在三角形外”对应某个坐标为负——判断点与三角形的位置关系时不用算具体数值，看正负号即可。

重心坐标在计算机图形学中的应用

图形程序常用”线框”近似物体：物体表面由许多小三角形片组成，程序只需在顶点处知道颜色、光照等信息，再把这些信息光滑地插值到三角形内部——插值公式就是用重心坐标作为权重对顶点值做线性组合。

屏幕颜色常用 RGB 坐标 $(r,g,b)$ 描述，每个分量取 0 到 1：纯红 $(1,0,0)$、白 $(1,1,1)$、黑 $(0,0,0)$。

例 5

设 ${\mathbf{v}}_1=\left[\begin{array}{c}3\\ 1\\ 5\end{array}\right],{\mathbf{v}}_2=\left[\begin{array}{c}4\\ 3\\ 4\end{array}\right],{\mathbf{v}}_3=\left[\begin{array}{c}1\\ 5\\ 1\end{array}\right],\mathbf{p}=\left[\begin{array}{c}3\\ 3\\ 3.5\end{array}\right]$。三角形三个顶点处的颜色分别为品红 $(1,0,1)$、浅品红 $(1,0.4,1)$、紫 $(0.6,0,1)$，求 $\mathbf{p}$ 处的插值颜色。

图 8-12：用重心坐标对顶点颜色做插值

解 先求 $\mathbf{p}$ 的重心坐标（齐次形式行化简，第 4 行移到第 1 行）：

$$[{\tilde{\mathbf{v}}}_1{\tilde{\mathbf{v}}}_2{\tilde{\mathbf{v}}}_3\tilde{\mathbf{p}}]\sim \left[\begin{array}{cccc}1& 1& 1& 1\\ 3& 4& 1& 3\\ 1& 3& 5& 3\\ 5& 4& 1& 3.5\end{array}\right]\sim \left[\begin{array}{cccc}1& 0& 0& 0.25\\ 0& 1& 0& 0.50\\ 0& 0& 1& 0.25\\ 0& 0& 0& 0\end{array}\right]$$

所以 $\mathbf{p}=0.25{\mathbf{v}}_1+0.5{\mathbf{v}}_2+0.25{\mathbf{v}}_3$。用同样的权重组合颜色数据：

$$0.25\left[\begin{array}{c}1\\ 0\\ 1\end{array}\right]+0.50\left[\begin{array}{c}1\\ 0.4\\ 1\end{array}\right]+0.25\left[\begin{array}{c}0.6\\ 0\\ 1\end{array}\right]=\left[\begin{array}{c}0.9\\ 0.2\\ 1\end{array}\right]\begin{array}{c}\leftarrow \text{红}\\ \leftarrow \text{绿}\\ \leftarrow \text{蓝}\end{array}$$

图形场景渲染前要去除”隐藏面”：想象从观察者眼睛出发、穿过屏幕某个像素进入场景的一条射线，屏幕像素应显示射线最先碰到的物体的颜色（图 8-13）。当物体用三角形片线框近似时，求射线与三角形交点恰好可以用重心坐标完成；这套射线-三角形求交的数学还能实现极为逼真的光影着色（光线追踪），目前实时渲染还嫌慢，但硬件进步可能改变这一点。

图 8-13：从眼睛穿过屏幕到达最近物体的射线

例 6

设 ${\mathbf{v}}_1=\left[\begin{array}{c}1\\ 1\\ -6\end{array}\right],{\mathbf{v}}_2=\left[\begin{array}{c}8\\ 1\\ -4\end{array}\right],{\mathbf{v}}_3=\left[\begin{array}{c}5\\ 11\\ -2\end{array}\right],\mathbf{a}=\left[\begin{array}{c}0\\ 0\\ 10\end{array}\right],\mathbf{b}=\left[\begin{array}{c}0.7\\ 0.4\\ -3\end{array}\right]$，射线 $\mathbf{x}(t)=\mathbf{a}+t\mathbf{b}$（$t\ge 0$）。求射线与三角形 ${\mathbf{v}}_1{\mathbf{v}}_2{\mathbf{v}}_3$ 所在平面的交点，并判断交点是否在三角形内。

解 平面即 $\mathrm{aff}\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3\}$，其上典型点可写成 $(1-c_2-c_3){\mathbf{v}}_1+c_2{\mathbf{v}}_2+c_3{\mathbf{v}}_3$。交点满足

$$(1-c_2-c_3){\mathbf{v}}_1+c_2{\mathbf{v}}_2+c_3{\mathbf{v}}_3=\mathbf{a}+t\mathbf{b}$$

整理成 $c_2({\mathbf{v}}_2-{\mathbf{v}}_1)+c_3({\mathbf{v}}_3-{\mathbf{v}}_1)+t(-\mathbf{b})=\mathbf{a}-{\mathbf{v}}_1$，矩阵形式：

$$\left[\begin{array}{ccc}{\mathbf{v}}_2-{\mathbf{v}}_1& {\mathbf{v}}_3-{\mathbf{v}}_1& -\mathbf{b}\end{array}\right]\left[\begin{array}{c}{c}_2\\ c_3\\ t\end{array}\right]=\mathbf{a}-{\mathbf{v}}_1$$

代入数据（${\mathbf{v}}_2-{\mathbf{v}}_1=\left[\begin{array}{c}7\\ 0\\ 2\end{array}\right],{\mathbf{v}}_3-{\mathbf{v}}_1=\left[\begin{array}{c}4\\ 10\\ 4\end{array}\right],\mathbf{a}-{\mathbf{v}}_1=\left[\begin{array}{c}-1\\ -1\\ 16\end{array}\right]$）并行化简：

$$\left[\begin{array}{cccc}7& 4& -0.7& -1\\ 0& 10& -0.4& -1\\ 2& 4& 3& 16\end{array}\right]\sim \left[\begin{array}{cccc}1& 0& 0& 0.3\\ 0& 1& 0& 0.1\\ 0& 0& 1& 5\end{array}\right]$$

得 $c_2=0.3,c_3=0.1,t=5$。交点为

$$\mathbf{x}(5)=\mathbf{a}+5\mathbf{b}=\left[\begin{array}{c}0\\ 0\\ 10\end{array}\right]+5\left[\begin{array}{c}0.7\\ 0.4\\ -3\end{array}\right]=\left[\begin{array}{c}3.5\\ 2.0\\ -5.0\end{array}\right]$$

同时 $\mathbf{x}(5)=0.6{\mathbf{v}}_1+0.3{\mathbf{v}}_2+0.1{\mathbf{v}}_3$。三个重心权重全为正，故交点在三角形内部。

8.2 练习题（Practice Problems）

题 1：如何快速判断三点共线？

解答：三点共线等价于集合仿射相关（例 1）。仿照例 2 的方法：用一个点减去另外两个点，若得到的两个新向量成倍数（线性相关），则原三点共线。

题 2：${\mathbf{v}}_1=\left[\begin{array}{c}4\\ 1\end{array}\right],{\mathbf{v}}_2=\left[\begin{array}{c}1\\ 0\end{array}\right],{\mathbf{v}}_3=\left[\begin{array}{c}5\\ 4\end{array}\right],{\mathbf{v}}_4=\left[\begin{array}{c}1\\ 2\end{array}\right]$ 仿射相关，求一组权重 $c_1,\dots ,c_4$ 使 $c_1{\mathbf{v}}_1+\cdots +c_4{\mathbf{v}}_4=0$ 且 $c_1+\cdots +c_4=0$、不全为零。

解答：定理 5 指出：各点齐次形式之间的线性相关关系（用同一组权重）就给出仿射相关关系。对 $[{\tilde{\mathbf{v}}}_1{\tilde{\mathbf{v}}}_2{\tilde{\mathbf{v}}}_3{\tilde{\mathbf{v}}}_4]$ 行化简：

$$\left[\begin{array}{cccc}4& 1& 5& 1\\ 1& 0& 4& 2\\ 1& 1& 1& 1\end{array}\right]\sim \left[\begin{array}{cccc}1& 1& 1& 1\\ 4& 1& 5& 1\\ 1& 0& 4& 2\end{array}\right]\sim \left[\begin{array}{cccc}1& 0& 0& -1\\ 0& 1& 0& 1.25\\ 0& 0& 1& 0.75\end{array}\right]$$

把它看成四个未知数的 $A\mathbf{x}=0$：$x_4$ 自由，$x_1=x_4,x_2=-1.25x_4,x_3=-0.75x_4$。取 $x_4=4$ 得整数解 $x_1=4,x_2=-5,x_3=-3$，于是

$$4{\tilde{\mathbf{v}}}_1-5{\tilde{\mathbf{v}}}_2-3{\tilde{\mathbf{v}}}_3+4{\tilde{\mathbf{v}}}_4=0⟹4{\mathbf{v}}_1-5{\mathbf{v}}_2-3{\mathbf{v}}_3+4{\mathbf{v}}_4=0$$

（权重和 $4-5-3+4=0$ ✓。另一种方法：把所有点平移到原点（都减 ${\mathbf{v}}_1$），求线性相关后再还原，计算量差不多。）

图 8-14：原书习题 15 的配图——三角形三条边延长后把平面分成七个区域，各区域中重心坐标的正负号模式不同（如 ${\mathbf{p}}_1$ 是 $(-,+,+)$，${\mathbf{p}}_2$ 在边上是 $(0,+,+)$）

通关标准

• 能用定理 5 的 (c) 或 (d) 判断仿射相关性（行化简一次搞定）；
• 会用齐次形式求重心坐标，并能根据坐标正负判断点相对三角形的位置；
• 理解图形学插值与射线求交这两大应用的基本思路。

本节习题（判断仿射相关、求重心坐标、符号分析、证明 $p\ge n+2$ 时必仿射相关等）见原书 8.2 节。

8.3 凸组合

凸组合与凸包

8.1 节限制权重之和为 1，本节再加一条：权重非负。

定义：点 ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\in {\mathbb{R}}^n$ 的凸组合是形如

$$c_1{\mathbf{v}}_1+c_2{\mathbf{v}}_2+\cdots +c_k{\mathbf{v}}_k$$

的线性组合，其中 $c_1+c_2+\cdots +c_k=1$ 且 $c_i\ge 0$ 对所有 $i$ 成立。集合 $S$ 中各点的全部凸组合构成的集合称为 $S$ 的凸包，记作 $\mathrm{conv}S$。

单点的凸包与仿射包相同，都是 $\{{\mathbf{v}}_1\}$；其他情形下凸包都真包含于仿射包。回忆两个不同点的仿射包是整条直线 $\mathbf{y}=(1-t){\mathbf{v}}_1+t{\mathbf{v}}_2$（$t\in \mathbb{R}$）；而凸组合要求 $0\le t\le 1$，所以

$$\mathrm{conv}\{{\mathbf{v}}_1,{\mathbf{v}}_2\}=\overline{{\mathbf{v}}_1{\mathbf{v}}_2}$$

就是连接 ${\mathbf{v}}_1,{\mathbf{v}}_2$ 的线段。

若 $S$ 仿射无关且 $\mathbf{p}\in \mathrm{aff}S$，则 $\mathbf{p}\in \mathrm{conv}S$ 当且仅当 $\mathbf{p}$ 的重心坐标全部非负——这正是”点在三角形（四面体）内部”这一几何直觉的代数表达。

例 1

设 ${\mathbf{v}}_1=\left[\begin{array}{c}3\\ 0\\ 6\\ -3\end{array}\right],{\mathbf{v}}_2=\left[\begin{array}{c}-6\\ 3\\ 3\\ 0\end{array}\right],{\mathbf{v}}_3=\left[\begin{array}{c}3\\ 6\\ 0\\ 3\end{array}\right],{\mathbf{p}}_1=\left[\begin{array}{c}0\\ 3\\ 3\\ 0\end{array}\right],{\mathbf{p}}_2=\left[\begin{array}{c}-10\\ 5\\ 11\\ -4\end{array}\right]$，$S=\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3\}$ 是正交集。判断 ${\mathbf{p}}_1,{\mathbf{p}}_2$ 是否属于 $\mathrm{Span}S$、$\mathrm{aff}S$、$\mathrm{conv}S$。

解 $S$ 正交，线性组合的权重可以用 6.3 节的正交投影公式直接算。令 $W=\mathrm{Span}S$，计算 ${\mathbf{p}}_1$ 在 $W$ 上的正交投影：

$${\mathrm{proj}}_W{\mathbf{p}}_1=\frac{{\mathbf{p}}_1\cdot {\mathbf{v}}_1}{{\mathbf{v}}_1\cdot {\mathbf{v}}_1}{\mathbf{v}}_1+\frac{{\mathbf{p}}_1\cdot {\mathbf{v}}_2}{{\mathbf{v}}_2\cdot {\mathbf{v}}_2}{\mathbf{v}}_2+\frac{{\mathbf{p}}_1\cdot {\mathbf{v}}_3}{{\mathbf{v}}_3\cdot {\mathbf{v}}_3}{\mathbf{v}}_3=\frac{18}{54}{\mathbf{v}}_1+\frac{18}{54}{\mathbf{v}}_2+\frac{18}{54}{\mathbf{v}}_3=\frac{1}{3}\left({\mathbf{v}}_1+{\mathbf{v}}_2+{\mathbf{v}}_3\right)={\mathbf{p}}_1$$

投影等于自身，说明 ${\mathbf{p}}_1\in \mathrm{Span}S$；三个权重 $\frac{1}{3}$ 之和为 1，故 ${\mathbf{p}}_1\in \mathrm{aff}S$；权重还全为正，故 ${\mathbf{p}}_1\in \mathrm{conv}S$。

对 ${\mathbf{p}}_2$ 做同样的计算得 ${\mathrm{proj}}_W{\mathbf{p}}_2\ne {\mathbf{p}}_2$。正交投影是 $\mathrm{Span}S$ 中离 ${\mathbf{p}}_2$ 最近的点，两者不等说明 ${\mathbf{p}}_2\notin \mathrm{Span}S$，当然更不在 $\mathrm{aff}S$ 与 $\mathrm{conv}S$ 中。

层级关系

$\mathrm{conv}S\subseteq \mathrm{aff}S\subseteq \mathrm{Span}S$。判断时逐级收紧权重条件即可：线性组合 ⟶ 权重和为 1 ⟶ 权重非负且和为 1。

凸集

定义：集合 $S$ 称为凸的，若对任意 $\mathbf{p},\mathbf{q}\in S$，线段 $\overline{\mathbf{pq}}$ 包含于 $S$。

直观上：集合中任意两点都能互相”看见”，视线不穿出集合。

图 8-15：凸集——任意两点间的线段都在集合内

图 8-16：又一个凸集

图 8-17：非凸集——存在两点连线穿出集合

与仿射情形完全平行地，有如下三个定理。

定理 7

集合 $S$ 是凸的，当且仅当 $S$ 中点的每个凸组合都属于 $S$，即 $S=\mathrm{conv}S$。

证明：与定理 2 的归纳证明相同，只是归纳步里系数 $0\le c_i\le 1$ 保证 $t=c_1+\cdots +c_k=1-c_{k+1}>0$，且 $z=\frac{c_1}{t}{\mathbf{v}}_1+\cdots +\frac{c_k}{t}{\mathbf{v}}_k$ 的系数非负、和为 1，是凸组合，由归纳假设 $z\in S$。∎

定理 8

任意一族凸集 $\{S_{\alpha }\}$ 的交 ${\bigcap }_{\alpha }{S}_{\alpha }$ 是凸的；任意一族仿射集 $\{T_{\beta }\}$ 的交是仿射的。

证明：若 $\mathbf{p},\mathbf{q}\in {\bigcap }_{\alpha }{S}_{\alpha }$，则线段 $\overline{\mathbf{pq}}$ 落在每个 $S_{\alpha }$ 中，故落在交集中。仿射情形类似。∎

定理 9

对任意集合 $S$，$\mathrm{conv}S$ 等于所有包含 $S$ 的凸集的交。

证明：令 $T$ 为所有包含 $S$ 的凸集之交。$\mathrm{conv}S$ 本身是包含 $S$ 的凸集，故 $T\subseteq \mathrm{conv}S$。反之，任取包含 $S$ 的凸集 $C$，由定理 7 它包含 $C$ 中点的一切凸组合，特别地包含 $S$ 中点的一切凸组合，即 $\mathrm{conv}S\subseteq C$；对所有这样的 $C$ 取交即得 $\mathrm{conv}S\subseteq T$。∎

定理 9 说明 $\mathrm{conv}S$ 是包含 $S$ 的最小凸集。形象地说：在 $S$ 外围套一根橡皮筋，收缩后橡皮筋的轮廓就是凸包的边界；凸包”填平”了 $S$ 内部的洞和外部的凹陷。

图 8-18：平面点集 $S$

图 8-19：$\mathrm{conv}S$——橡皮筋收缩出的多边形

图 8-20：集合 $T$ 的凸包 $\mathrm{conv}T$

图 8-21：例 2(b)——$S=\{{\mathbf{e}}_1,{\mathbf{e}}_2,{\mathbf{e}}_3\}$ 的凸包是 ${\mathbb{R}}^3$ 中以三个标准基向量为顶点的三角形面片

例 2

a. 图 8-18 至 8-20 展示了 ${\mathbb{R}}^2$ 中集合 $S,T$ 的凸包——不规则点集的凸包是把外缘点连起来的多边形。

b. 设 $S$ 是 ${\mathbb{R}}^3$ 的标准基 $\{{\mathbf{e}}_1,{\mathbf{e}}_2,{\mathbf{e}}_3\}$，则 $\mathrm{conv}S$ 是以 ${\mathbf{e}}_1,{\mathbf{e}}_2,{\mathbf{e}}_3$ 为顶点的三角形面片（图 8-21）。

例 3

设 $S=\left\{\left[\begin{array}{c}x\\ y\end{array}\right]:x\ge 0,y=x^2\right\}$（抛物线右支）。证明 $\mathrm{conv}S$ 是原点与 $\left\{\left[\begin{array}{c}x\\ y\end{array}\right]:x>0,y\ge x^2\right\}$ 的并。

图 8-22：抛物线及其凸包（阴影区域，含原点）

论证：$\mathrm{conv}S$ 中每点都在连接 $S$ 中两点的线段上。图 8-22 中虚线示意除原点外正 $y$ 轴不在 $\mathrm{conv}S$ 中，因为 $y$ 轴上属于 $S$ 的点只有原点。但”看起来如此”不等于证明：比如 $(10^{-2},10^4)$ 真的在某条从原点到曲线上一点的线段上吗？

具体验证：取阴影区域中任一点 $\mathbf{p}=\left[\begin{array}{c}a\\ b\end{array}\right]$（$a>0,b\ge a^2$）。过 $0$ 与 $\mathbf{p}$ 的直线方程为 $y=(b/a)t$，与曲线 $y=t^2$ 的交点满足 $t=b/a$，即交点为 $\left[\begin{array}{c}b/a\\ b^2/a^2\end{array}\right]\in S$。由于 $b/a\ge a>0$，$\mathbf{p}$ 恰在这条从 $0$ 到该交点的线段上。所以阴影区域的确是 $\mathrm{conv}S$。∎

卡拉西奥多里定理（Caratheodory）

凸组合的定义没有限制使用多少个点。下面的定理说：在 $n$ 维空间里，最多 $n+1$ 个点就永远够了。这是 1907 年 Constantin Caratheodory 证明的结果。

定理 10（Caratheodory 定理）

若 $S$ 是 ${\mathbb{R}}^n$ 的非空子集，则 $\mathrm{conv}S$ 中每一点都可表示为 $S$ 中至多 $n+1$ 个点的凸组合。

证明思路：设 $\mathbf{p}=c_1{\mathbf{v}}_1+\cdots +c_k{\mathbf{v}}_k$（${\mathbf{v}}_i\in S$，$c_i\ge 0$，权和 1）。若 $k>n+1$，则由 8.2 节习题 12，$\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\}$ 仿射相关，故存在不全为零的 $d_1,\dots ,d_k$ 使 $\sum d_i{\mathbf{v}}_i=0$ 且 $\sum d_i=0$。适当选 $d_k>0$ 并使比值 $\frac{c_k}{d_k}$ 在所有 $d_i>0$ 的组中最小，令 $b_i=c_i-\frac{c_k}{d_k}{d}_i$，则 $b_k=0$、$\sum b_i=1$、各 $b_i\ge 0$（$d_i\le 0$ 时 $b_i\ge c_i\ge 0$；$d_i>0$ 时 $b_i=d_i\left(\frac{c_i}{d_i}-\frac{c_k}{d_k}\right)\ge 0$），并且

$$\sum _{i=1}^k{b}_i{\mathbf{v}}_i=\sum _{i=1}^k{c}_i{\mathbf{v}}_i-\frac{c_k}{d_k}\sum _{i=1}^k{d}_i{\mathbf{v}}_i=\mathbf{p}$$

即用 $k-1$ 个点重新表达了 $\mathbf{p}$。重复此过程直到点数不超过 $n+1$。∎

例 4

设 ${\mathbf{v}}_1=\left[\begin{array}{c}1\\ 0\end{array}\right],{\mathbf{v}}_2=\left[\begin{array}{c}2\\ 3\end{array}\right],{\mathbf{v}}_3=\left[\begin{array}{c}5\\ 4\end{array}\right],{\mathbf{v}}_4=\left[\begin{array}{c}3\\ 0\end{array}\right],\mathbf{p}=\left[\begin{array}{c}\frac{10}{3}\\ \frac{5}{2}\end{array}\right]$，$S=\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3,{\mathbf{v}}_4\}$，且

$$\frac{1}{4}{\mathbf{v}}_1+\frac{1}{6}{\mathbf{v}}_2+\frac{1}{2}{\mathbf{v}}_3+\frac{1}{12}{\mathbf{v}}_4=\mathbf{p}\text{\hspace{1em}(2)}$$

用卡拉西奥多里定理证明中的步骤把 $\mathbf{p}$ 改写为 $S$ 中三个点的凸组合。

解 $S$ 仿射相关。用 8.2 节的方法求仿射相关关系：

$$-5{\mathbf{v}}_1+4{\mathbf{v}}_2-3{\mathbf{v}}_3+4{\mathbf{v}}_4=0\text{\hspace{1em}(3)}$$

(3) 中系数为正的点是 ${\mathbf{v}}_2$ 和 ${\mathbf{v}}_4$，分别计算 (2) 与 (3) 中系数之比：${\mathbf{v}}_2$ 的比值 $\frac{1}{6}÷4=\frac{1}{24}$，${\mathbf{v}}_4$ 的比值 $\frac{1}{12}÷4=\frac{1}{48}$。取更小者，从 (2) 减去 $\frac{1}{48}$ 倍的 (3) 以消去 ${\mathbf{v}}_4$：

$$\left(\frac{1}{4}+\frac{5}{48}\right){\mathbf{v}}_1+\left(\frac{1}{6}-\frac{4}{48}\right){\mathbf{v}}_2+\left(\frac{1}{2}+\frac{3}{48}\right){\mathbf{v}}_3+\left(\frac{1}{12}-\frac{4}{48}\right){\mathbf{v}}_4=\mathbf{p}$$ $$⟹\frac{17}{48}{\mathbf{v}}_1+\frac{4}{48}{\mathbf{v}}_2+\frac{27}{48}{\mathbf{v}}_3=\mathbf{p}$$

三个系数非负、和为 $\frac{48}{48}=1$，正是所需的三点凸组合。（一般地这个点数不能再降：${\mathbb{R}}^2$ 中任意三个不共线点的重心在三点的凸包内，却不在任何两点的凸包内。）

8.3 练习题（Practice Problems）

题 1：${\mathbf{v}}_1=\left[\begin{array}{c}6\\ 2\\ 2\end{array}\right],{\mathbf{v}}_2=\left[\begin{array}{c}7\\ 1\\ 5\end{array}\right],{\mathbf{v}}_3=\left[\begin{array}{c}-2\\ 4\\ -1\end{array}\right],{\mathbf{p}}_1=\left[\begin{array}{c}1\\ 3\\ 1\end{array}\right],{\mathbf{p}}_2=\left[\begin{array}{c}3\\ 2\\ 1\end{array}\right]$，判断 ${\mathbf{p}}_1,{\mathbf{p}}_2$ 是否属于 $\mathrm{conv}S$（$S=\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3\}$）。

解答：先平移到 ${\mathbf{v}}_1$：

$${\mathbf{v}}_2-{\mathbf{v}}_1=\left[\begin{array}{c}1\\ -1\\ 3\end{array}\right],{\mathbf{v}}_3-{\mathbf{v}}_1=\left[\begin{array}{c}-8\\ 2\\ -3\end{array}\right],{\mathbf{p}}_1-{\mathbf{v}}_1=\left[\begin{array}{c}-5\\ 1\\ -1\end{array}\right],{\mathbf{p}}_2-{\mathbf{v}}_1=\left[\begin{array}{c}-3\\ 0\\ -1\end{array}\right]$$

把矩阵 $[{\mathbf{v}}_2-{\mathbf{v}}_1{\mathbf{v}}_3-{\mathbf{v}}_1]$ 增广上 ${\mathbf{p}}_1-{\mathbf{v}}_1,{\mathbf{p}}_2-{\mathbf{v}}_1$ 两列后行化简：

$$\left[\begin{array}{rrrr}1& -8& -5& -3\\ -1& 2& 1& 0\\ 3& -3& -1& -1\end{array}\right]\sim \left[\begin{array}{rrrr}1& 0& \frac{1}{3}& 1\\ 0& 1& \frac{2}{3}& \frac{1}{2}\\ 0& 0& 0& -\frac{5}{2}\end{array}\right]$$

第 3 列说明 ${\mathbf{p}}_1-{\mathbf{v}}_1=\frac{1}{3}({\mathbf{v}}_2-{\mathbf{v}}_1)+\frac{2}{3}({\mathbf{v}}_3-{\mathbf{v}}_1)$，即 ${\mathbf{p}}_1=0\cdot {\mathbf{v}}_1+\frac{1}{3}{\mathbf{v}}_2+\frac{2}{3}{\mathbf{v}}_3$——系数非负、和为 1，故 ${\mathbf{p}}_1\in \mathrm{conv}S$（实际上 ${\mathbf{p}}_1\in \mathrm{conv}\{{\mathbf{v}}_2,{\mathbf{v}}_3\}$，在线段上）。最后一列出现矛盾行，${\mathbf{p}}_2-{\mathbf{v}}_1$ 不是平移向量的线性组合，即 ${\mathbf{p}}_2$ 连仿射组合都不是，自然不在 $\mathrm{conv}S$ 中。

（也可以对齐次形式 $[{\tilde{\mathbf{v}}}_1{\tilde{\mathbf{v}}}_2{\tilde{\mathbf{v}}}_3{\tilde{\mathbf{p}}}_1{\tilde{\mathbf{p}}}_2]$ 一次行化简完成同样判断。）

题 2：设 $S$ 是曲线 $y=1/x$（$x>0$）上的点集，解释为什么 $\mathrm{conv}S$ 由曲线上及曲线上方的所有点组成。

解答：几何上，若 $\mathbf{p}$ 是 $S$ 上方的点，则过 $\mathbf{p}$、斜率为 1 的直线会在碰到正 $x$ 轴与正 $y$ 轴之前与曲线 $S$ 交于两点，$\mathbf{p}$ 落在这两点的线段上，故属于 $\mathrm{conv}S$；而曲线下方的任何点都不可能落在两端都在曲线上的线段内。

图 8-23：原书习题 21 配图——二次贝塞尔曲线构造中 ${\mathbf{f}}_0(\frac{1}{2})$、${\mathbf{f}}_1(\frac{1}{2})$、$\mathbf{g}(\frac{1}{2})$ 的位置（详见 8.6 节）

通关标准

• 能说出三者的嵌套关系：凸包 ⊆ 仿射包 ⊆ 张成，并知道权重条件的差别（非负且和 1 / 和 1 / 任意）；
• 会判断点是否在凸包中（平移 + 行化简，看权重非负与否）；
• 知道卡拉西奥多里定理”最多 $n+1$ 个点”的结论及消除多余点的基本操作。

本节习题（判断点在哪个集合、凸包描述、贝塞尔曲线与控制点的凸包关系等）见原书 8.3 节。

8.4 超平面

超平面在 ${\mathbb{R}}^n$ 的几何中地位特殊：它把空间切成互不相交的两块——正如平面把 ${\mathbb{R}}^3$ 分成两部分、直线切过 ${\mathbb{R}}^2$。处理超平面的关键在于使用隐式描述（一个方程），而不是前面用过的显式/参数描述。

${\mathbb{R}}^2$ 中直线的隐式方程是 $ax+by=d$；${\mathbb{R}}^3$ 中平面的是 $ax+by+cz=d$。两者都是”令某个线性表达式取定值 $d$“。这个”线性表达式”叫线性泛函。

定义：${\mathbb{R}}^n$ 上的线性泛函是从 ${\mathbb{R}}^n$ 到 $\mathbb{R}$ 的线性变换 $f$。对每个实数 $d$，记

$$[f:d]=\{\mathbf{x}\in {\mathbb{R}}^n:f(\mathbf{x})=d\}$$

即 $f$ 取值为 $d$ 的所有点。处处为零的称为零泛函，其余为非零泛函。

例 1

${\mathbb{R}}^2$ 中直线 $x-4y=13$ 是一个超平面，它是线性泛函 $f(x,y)=x-4y$ 取值 13 的点集，即 $[f:13]$。

例 2

${\mathbb{R}}^3$ 中平面 $5x-2y+3z=21$ 是超平面 $[g:21]$，其中 $g(x,y,z)=5x-2y+3z$。

隐式描述的代数结构

设线性泛函 $f$ 的标准矩阵是 $1\times n$ 矩阵 $A=[a_1{a}_2\cdots a_n]$。则：

1. $[f:0]=\{\mathbf{x}:A\mathbf{x}=0\}=\mathrm{Nul}A$。若 $f$ 非零，由秩定理 $\dim \mathrm{Nul}A=n-1$，所以 $[f:0]$ 本身就是一个过原点的超平面；
2. $[f:d]=[f:0]+\mathbf{p}$，其中 $\mathbf{p}$ 是 $A\mathbf{x}=d$ 的任一特解——这正是 1.5 节定理 6 的”解集 = 零空间 + 特解”。所以各 $[f:d]$ 是彼此平行的超平面。

图 8-24：一族平行超平面，$\mathbf{p}$ 所在的那张满足 $f(\mathbf{p})=d$

把 $A\mathbf{x}=d$ 写成内积形式：取 $\mathbf{n}\in {\mathbb{R}}^n$ 与 $A$ 各分量相同，则

$$[f:d]=\{\mathbf{x}\in {\mathbb{R}}^n:\mathbf{n}\cdot \mathbf{x}=d\}$$

特别地 $[f:0]=\{\mathbf{x}:\mathbf{n}\cdot \mathbf{x}=0\}$ 是 $\mathrm{Span}\{\mathbf{n}\}$ 的正交补。沿用 ${\mathbb{R}}^3$ 的说法，$\mathbf{n}$ 称为这些超平面的法向量（不要求单位长度）；$[f:d]$ 也叫 $f$ 的水平集，$\mathbf{n}$ 称为 $f$ 的梯度。

例 3

设 $\mathbf{n}=\left[\begin{array}{c}3\\ 4\end{array}\right],\mathbf{v}=\left[\begin{array}{c}1\\ -6\end{array}\right]$，$H=\{\mathbf{x}:\mathbf{n}\cdot \mathbf{x}=12\}$（即直线 $3x+4y=12$）。求平行超平面 $H_1=H+\mathbf{v}$ 的隐式描述。

解 先在 $H_1$ 中找一个点：取 $H$ 中一点 $\left[\begin{array}{c}0\\ 3\end{array}\right]$，加 $\mathbf{v}$ 得

$$\mathbf{p}=\left[\begin{array}{c}1\\ -6\end{array}\right]+\left[\begin{array}{c}0\\ 3\end{array}\right]=\left[\begin{array}{c}1\\ -3\end{array}\right]$$

算 $\mathbf{n}\cdot \mathbf{p}=3(1)+4(-3)=-9$，所以 $H_1=[f:-9]$，其中 $f(x,y)=3x+4y$。图 8-25 同时画出了子空间 $H_0=\{\mathbf{x}:\mathbf{n}\cdot \mathbf{x}=0\}$。

图 8-25：过原点的超平面 $H_0$ 与平移后的 $H_1=H+\mathbf{v}$

隐式 ⟷ 显式互化

例 4（隐式 → 显式）

把 ${\mathbb{R}}^2$ 中的直线 $x-4y=13$ 写成参数向量形式。

解 这就是解非齐次方程 $A\mathbf{x}=\mathbf{b}$，$A=\left[\begin{array}{cc}1& -4\end{array}\right]$，$\mathbf{b}=13$。令 $y$ 为自由变量：$x=13+4y$，

$$\mathbf{x}=\left[\begin{array}{c}13+4y\\ y\end{array}\right]=\left[\begin{array}{c}13\\ 0\end{array}\right]+y\left[\begin{array}{c}4\\ 1\end{array}\right]=\mathbf{p}+y\mathbf{q},y\in \mathbb{R}$$

例 5（显式 → 隐式，两点定直线）

设 ${\mathbf{v}}_1=\left[\begin{array}{c}1\\ 2\end{array}\right],{\mathbf{v}}_2=\left[\begin{array}{c}6\\ 0\end{array}\right]$，$L_1$ 为过这两点的直线。求线性泛函 $f$ 与常数 $d$ 使 $L_1=[f:d]$。

解 $L_1$ 平行于过原点和 ${\mathbf{v}}_2-{\mathbf{v}}_1$ 的直线 $L_0$。设 $L_0$ 的方程为 $\mathbf{n}\cdot \mathbf{x}=0$，$\mathbf{n}$ 必须与 ${\mathbf{v}}_2-{\mathbf{v}}_1=\left[\begin{array}{c}5\\ -2\end{array}\right]$ 正交。解 $[ab]\left[\begin{array}{c}5\\ -2\end{array}\right]=0$，目测一组解 $\mathbf{n}=\left[\begin{array}{c}2\\ 5\end{array}\right]$（因为 $2\cdot 5+5\cdot (-2)=0$），令 $f(x,y)=2x+5y$。再算 $d=f({\mathbf{v}}_1)=2(1)+5(2)=12$，得 $L_1:2x+5y=12$。验证：$f({\mathbf{v}}_2)=2(6)+5(0)=12$ ✓。

例 6（显式 → 隐式，三点定平面）

设 ${\mathbf{v}}_1=\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right],{\mathbf{v}}_2=\left[\begin{array}{c}2\\ -1\\ 4\end{array}\right],{\mathbf{v}}_3=\left[\begin{array}{c}3\\ 1\\ 2\end{array}\right]$。求过这三点的平面 $H_1$ 的隐式描述 $[f:d]$。

解 $H_1$ 平行于过原点、包含平移点 ${\mathbf{v}}_2-{\mathbf{v}}_1=\left[\begin{array}{c}1\\ -2\\ 3\end{array}\right]$ 与 ${\mathbf{v}}_3-{\mathbf{v}}_1=\left[\begin{array}{c}2\\ 0\\ 1\end{array}\right]$ 的平面 $H_0$（两平移向量线性无关，故 $H_0=\mathrm{Span}\{{\mathbf{v}}_2-{\mathbf{v}}_1,{\mathbf{v}}_3-{\mathbf{v}}_1\}$）。法向量 $\mathbf{n}=\left[\begin{array}{c}a\\ b\\ c\end{array}\right]$ 需与两个平移向量都正交：

$$\left[\begin{array}{cccc}1& -2& 3& 0\\ 2& 0& 1& 0\end{array}\right]⟹a=-\frac{2}{4}c,b=\frac{5}{4}c$$

取 $c=4$ 得 $\mathbf{n}=\left[\begin{array}{c}-2\\ 5\\ 4\end{array}\right]$，$f(\mathbf{x})=-2x_1+5x_2+4x_3$，$H_0=[f:0]$。再用 ${\mathbf{v}}_1$ 求 $d=f({\mathbf{v}}_1)=-2(1)+5(1)+4(1)=7$。验证：$f({\mathbf{v}}_2)=-4-5+16=7$ ✓，$f({\mathbf{v}}_3)=7$ ✓。

${\mathbb{R}}^3$ 中还可用叉积公式求 $\mathbf{n}=({\mathbf{v}}_2-{\mathbf{v}}_1)\times ({\mathbf{v}}_3-{\mathbf{v}}_1)$，用符号行列式助记：

$$\mathbf{n}=\left|\begin{array}{ccc}1& 2& \mathbf{i}\\ -2& 0& \mathbf{j}\\ 3& 1& \mathbf{k}\end{array}\right|=\left|\begin{array}{cc}-2& 0\\ 3& 1\end{array}\right|\mathbf{i}-\left|\begin{array}{cc}1& 2\\ 3& 1\end{array}\right|\mathbf{j}+\left|\begin{array}{cc}1& 2\\ -2& 0\end{array}\right|\mathbf{k}=-2\mathbf{i}+5\mathbf{j}+4\mathbf{k}=\left[\begin{array}{c}-2\\ 5\\ 4\end{array}\right]$$

把第三列换成 $x_1,x_2,x_3$ 做普通行列式，就直接给出 $f$ 的表达式：$f(x_1,x_2,x_3)=-2x_1+5x_2+4x_3$。

定理 11（超平面的刻画）

${\mathbb{R}}^n$ 的子集 $H$ 是超平面，当且仅当 $H=[f:d]$，其中 $f$ 是某非零线性泛函、$d\in \mathbb{R}$。等价地：$H$ 是超平面当且仅当存在非零向量 $\mathbf{n}$ 与实数 $d$ 使 $H=\{\mathbf{x}:\mathbf{n}\cdot \mathbf{x}=d\}$。

证明思路：（⇒）取 $\mathbf{p}\in H$，则 $H_0=H-\mathbf{p}$ 是 $n-1$ 维子空间。取 $\mathbf{y}\notin H_0$，由 6.3 节正交分解定理 $\mathbf{y}={\mathbf{y}}_1+\mathbf{n}$，其中 $\mathbf{n}$ 与 $H_0$ 中所有向量正交。令 $f(\mathbf{x})=\mathbf{n}\cdot \mathbf{x}$（由内积性质它是线性泛函），则 $[f:0]$ 是包含 $H_0$ 的 $n-1$ 维子空间，由基定理 $H_0=[f:0]$。令 $d=f(\mathbf{p})=\mathbf{n}\cdot \mathbf{p}$，则 $[f:d]=[f:0]+\mathbf{p}=H$。（⇐）由前面的 (1)(3) 两式即得。∎

分离超平面：${\mathbb{R}}^n$ 中的拓扑词汇

许多重要应用依赖”用一个超平面把两个集合分开”的想法：一个集合在超平面一侧、另一个在另一侧。先把术语说清楚：

• 开球：$B(\mathbf{p},\delta )=\{\mathbf{x}:\Vert \mathbf{x}-\mathbf{p}\Vert <\delta \}$（中心 $\mathbf{p}$、半径 $\delta$）；
• 内点：$\mathbf{p}$ 是 $S$ 的内点，若存在 $\delta >0$ 使 $B(\mathbf{p},\delta )\subset S$；
• 边界点：以 $\mathbf{p}$ 为中心的每个开球都同时与 $S$ 及其补集相交；
• 开集：不含自己的任何边界点（所有点都是内点）；闭集：包含自己的全部边界点（含一部分但不含全部边界点的集合既不开也不闭）；
• 有界集：存在 $\delta >0$ 使 $S\subset B(0,\delta )$；紧集：既闭又有界。

定理：开集的凸包是开的，紧集的凸包是紧的。（闭集的凸包未必闭，见原书习题 27。）

图 8-26：闭且有界的集合 $S$——内部点与边界点的对比

例 7

设 $S=\mathrm{conv}\left\{\left[\begin{array}{c}-2\\ 2\end{array}\right],\left[\begin{array}{c}-2\\ -2\end{array}\right],\left[\begin{array}{c}2\\ -2\end{array}\right],\left[\begin{array}{c}2\\ 2\end{array}\right]\right\}$（以 $(\pm 2,\pm 2)$ 为顶点的正方形），${\mathbf{p}}_1=\left[\begin{array}{c}-1\\ 0\end{array}\right]$，${\mathbf{p}}_2=\left[\begin{array}{c}2\\ 1\end{array}\right]$。则 ${\mathbf{p}}_1$ 是内点（$B({\mathbf{p}}_1,\frac{3}{4})\subset S$）；${\mathbf{p}}_2$ 是边界点（无论球多小都同时碰到 $S$ 内外）。$S$ 包含全部边界点故为闭集，$S\subset B(0,3)$ 故有界，因此 $S$ 是紧集。

记号：$f(A)\le d$ 表示对每个 $\mathbf{x}\in A$ 都有 $f(\mathbf{x})\le d$；反向或严格不等式类似。

定义：超平面 $H=[f:d]$ 分隔集合 $A,B$，若下列之一成立：

• (i) $f(A)\le d$ 且 $f(B)\ge d$，或
• (ii) $f(A)\ge d$ 且 $f(B)\le d$。

把弱不等号全换成严格不等号则称 $H$ 严格分隔 $A,B$。

严格分隔要求两集合不相交；普通分隔不要求——例如平面上两个外切的圆，公切线分隔它们但不能严格分隔。反过来，不相交也不保证能严格分隔：设

$$A=\left\{\left[\begin{array}{c}x\\ y\end{array}\right]:x\ge \frac{1}{2},\frac{1}{x}\le y\le 2\right\},B=\left\{\left[\begin{array}{c}x\\ y\end{array}\right]:x\ge 0,y=0\right\}$$

$A,B$ 是不相交的闭凸集，但 $A$ 沿 $x$ 轴方向无限贴近 $B$，任何直线（${\mathbb{R}}^2$ 的超平面）都无法严格分隔它们（图 8-27）。可见分隔问题比直觉复杂，好在有下面两个充分条件。

图 8-27：不相交的两个闭凸集，却无法被严格分隔——$A$ 渐近贴近 $x$ 轴上的 $B$

定理 12

设 $A,B$ 是非空凸集，$A$ 紧、$B$ 闭。则存在严格分隔 $A,B$ 的超平面，当且仅当 $A\cap B=\varnothing$。

定理 13

设 $A,B$ 是非空紧集。则存在严格分隔 $A,B$ 的超平面，当且仅当 $(\mathrm{conv}A)\cap (\mathrm{conv}B)=\varnothing$。

证明：（⇐）紧集的凸包是紧的，由定理 12 存在超平面严格分隔 $\mathrm{conv}A$ 与 $\mathrm{conv}B$，当然也严格分隔更小的集合 $A,B$。（⇒）设 $H=[f:d]$ 严格分隔，不妨 $f(A)<d<f(B)$。对 $A$ 中点的任意凸组合 $\mathbf{x}=c_1{\mathbf{x}}_1+\cdots +c_k{\mathbf{x}}_k$：

$$f(\mathbf{x})=c_{1}f({\mathbf{x}}_1)+\cdots +c_{k}f({\mathbf{x}}_k)<c_{1}d+\cdots +c_{k}d=d$$

（用到 $c_1+\cdots +c_k=1$。）故 $f(\mathrm{conv}A)<d$，同理 $f(\mathrm{conv}B)>d$，$H$ 严格分隔两个凸包，由定理 12 它们必不相交。∎

例 8

设 ${\mathbf{a}}_1=\left[\begin{array}{c}2\\ 1\\ 1\end{array}\right],{\mathbf{a}}_2=\left[\begin{array}{c}-3\\ 2\\ 1\end{array}\right],{\mathbf{a}}_3=\left[\begin{array}{c}3\\ 4\\ 0\end{array}\right],{\mathbf{b}}_1=\left[\begin{array}{c}1\\ 0\\ 2\end{array}\right],{\mathbf{b}}_2=\left[\begin{array}{c}2\\ -1\\ 5\end{array}\right]$，$A=\{{\mathbf{a}}_1,{\mathbf{a}}_2,{\mathbf{a}}_3\}$，$B=\{{\mathbf{b}}_1,{\mathbf{b}}_2\}$。证明超平面 $H=[f:5]$（$f(x_1,x_2,x_3)=2x_1-3x_2+x_3$）不能分隔 $A,B$。是否存在与 $H$ 平行、能分隔 $A,B$ 的超平面？$\mathrm{conv}A$ 与 $\mathrm{conv}B$ 相交吗？

解 逐点计算 $f$ 值：

$$f({\mathbf{a}}_1)=2,f({\mathbf{a}}_2)=-11,f({\mathbf{a}}_3)=-6,f({\mathbf{b}}_1)=4,f({\mathbf{b}}_2)=12$$

$f({\mathbf{b}}_1)=4<5<f({\mathbf{b}}_2)=12$：$B$ 的点分布在 $H$ 两侧，所以 $H$ 不能分隔 $A,B$。但 $f(A)\le -6<3<4\le f(B)$，平行的超平面 $[f:3]$ 可以严格分隔 $A,B$。由定理 13，$(\mathrm{conv}A)\cap (\mathrm{conv}B)=\varnothing$。

常见坑

“没有与 $H$ 平行的超平面能严格分隔”并不能推出两个凸包相交——也许某个不平行于 $H$ 的超平面可以分隔它们。逻辑方向别搞反。

8.4 练习题（Practice Problem）

题目：设 ${\mathbf{p}}_1=\left[\begin{array}{c}1\\ 0\\ 2\end{array}\right],{\mathbf{p}}_2=\left[\begin{array}{c}-1\\ 2\\ 1\end{array}\right],{\mathbf{n}}_1=\left[\begin{array}{c}1\\ 1\\ -2\end{array}\right],{\mathbf{n}}_2=\left[\begin{array}{c}-2\\ 1\\ 3\end{array}\right]$；$H_1$ 是过 ${\mathbf{p}}_1$、法向 ${\mathbf{n}}_1$ 的 ${\mathbb{R}}^3$ 平面，$H_2$ 是过 ${\mathbf{p}}_2$、法向 ${\mathbf{n}}_2$ 的平面。给出 $H_1\cap H_2$ 的显式描述（生成其中所有点的公式）。

解答：先算 ${\mathbf{n}}_1\cdot {\mathbf{p}}_1=1+0-4=-3$，${\mathbf{n}}_2\cdot {\mathbf{p}}_2=2+2+3=7$。于是

$$H_1\cap H_2=\{\mathbf{x}:x_1+x_2-2x_3=-3\text{且}-2x_1+x_2+3x_3=7\}$$

行化简求解：

$$\left[\begin{array}{cccc}1& 1& -2& -3\\ -2& 1& 3& 7\end{array}\right]\sim \left[\begin{array}{cccc}1& 0& -\frac{5}{3}& -\frac{10}{3}\\ 0& 1& -\frac{1}{3}& \frac{1}{3}\end{array}\right]$$

通解为 $x_1=-\frac{10}{3}+\frac{5}{3}{x}_3,x_2=\frac{1}{3}+\frac{1}{3}{x}_3,x_3=x_3$，即

$$\mathbf{x}=\mathbf{p}+x_3\mathbf{v},\mathbf{p}=\left[\begin{array}{c}-\frac{10}{3}\\ \frac{1}{3}\\ 0\end{array}\right],\mathbf{v}=\left[\begin{array}{c}\frac{5}{3}\\ \frac{1}{3}\\ 1\end{array}\right]$$

$H_1\cap H_2$ 是过 $\mathbf{p}$、方向 $\mathbf{v}$ 的直线；$\mathbf{v}$ 与 ${\mathbf{n}}_1,{\mathbf{n}}_2$ 都正交，符合”两平面交线垂直于两个法向量”的几何直觉。

通关标准

• 会在”点 + 法向量”与隐式方程 $\mathbf{n}\cdot \mathbf{x}=d$ 之间自由换算，会从两点/三点求出隐式方程；
• 能用 $f$ 在各点取值判断某超平面是否分隔两个集合，并寻找平行的分隔超平面；
• 记住两个分隔定理的条件（紧 + 闭 / 紧 + 紧，凸包不相交）。

本节习题（求隐式描述、判断开闭、找严格分隔超平面等）见原书 8.4 节。

8.5 多面体

本节研究一类重要的紧凸集——多面体（polytope）。它们出现在博弈论（9.1 节）、线性规划（9.2–9.4 节）以及反馈控制设计等优化问题中。

定义：${\mathbb{R}}^n$ 中的多面体是有限点集的凸包。${\mathbb{R}}^2$ 中多面体就是多边形；${\mathbb{R}}^3$ 中称为多面体（polyhedron），重要特征是面、棱、顶点——正方体有 6 个方形面、12 条棱、8 个顶点。多面体是紧凸集：${\mathbb{R}}^n$ 中有限集是紧的，由 8.4 节的定理其凸包也是紧的。

定义（面）：设 $S$ 是 ${\mathbb{R}}^n$ 中的紧凸集。非空子集 $F\subset S$（$F\ne S$）称为 $S$ 的一个**（真）面**，若存在超平面 $H=[f:d]$ 使 $F=S\cap H$ 且 $f(S)\le d$ 或 $f(S)\ge d$。这样的 $H$ 称为 $S$ 的支撑超平面。若 $\dim F=k$，则 $F$ 称为 $S$ 的 k-面。

若多面体 $P$ 的维数为 $k$，则称 $P$ 为 k-多面体。$P$ 的 0-面叫顶点（vertices），1-面叫棱（edge），$(k-1)$ 维面叫侧面（facet）。

例 1

设 $S$ 是 ${\mathbb{R}}^3$ 中的正方体。让平面 $H$ 在 ${\mathbb{R}}^3$ 中平移直到恰好”贴住”（支撑）正方体而不切入内部，按 $H$ 的方向不同，$H\cap S$ 有三种可能：

• $H\cap S$ 可能是 2 维的方形侧面（facet）；
• $H\cap S$ 可能是 1 维的棱；
• $H\cap S$ 可能是 0 维的顶点。

图 8-28：支撑平面切出 2 维面（正方形的面）

图 8-29：支撑平面切出 1 维棱

图 8-30：支撑平面切出 0 维顶点

多面体的应用大多围绕顶点展开，因为顶点有特殊性质：

定义（极点）：设 $S$ 是凸集。点 $\mathbf{p}\in S$ 称为 $S$ 的极点（extreme point），若 $\mathbf{p}$ 不落在任何完全位于 $S$ 内的线段内部。更精确地说：若 $\mathbf{x},\mathbf{y}\in S$ 且 $\mathbf{p}\in \overline{\mathbf{xy}}$，则 $\mathbf{p}=\mathbf{x}$ 或 $\mathbf{p}=\mathbf{y}$。$S$ 的全部极点构成的集合称为 $S$ 的轮廓（profile）。

任何紧凸集的顶点自动是极点（在定理 14 的证明 (b)⇒(c) 中顺便证明）。处理多面体 $P=\mathrm{conv}\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\}$ 时，通常希望 ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_k$ 恰是极点；但给定的点列表可能有多余项——比如某个 ${\mathbf{v}}_i$ 是某条棱的中点，删掉它凸包不变。

定义（最小表示）：$\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\}$ 是多面体 $P$ 的最小表示，若 $P=\mathrm{conv}\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\}$ 且对每个 $i=1,\dots ,k$，${\mathbf{v}}_i\notin \mathrm{conv}\{{\mathbf{v}}_j:j\ne i\}$。

每个多面体都有最小表示：若某个 ${\mathbf{v}}_i$ 是其他点的凸组合就删掉，重复直到不能再删；可以证明最小表示唯一。

定理 14

设 $M=\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\}$ 是多面体 $P$ 的最小表示，则下列三条等价：a. $\mathbf{p}\in M$；b. $\mathbf{p}$ 是 $P$ 的顶点；c. $\mathbf{p}$ 是 $P$ 的极点。

证明思路：(a)⇒(b)：令 $Q=\mathrm{conv}\{\mathbf{v}\in M:\mathbf{v}\ne \mathbf{p}\}$。由最小性 $\mathbf{p}\notin Q$；$Q$ 紧，由定理 13 存在超平面 $H^{\prime }$ 严格分隔 $\{\mathbf{p}\}$ 与 $Q$。过 $\mathbf{p}$ 作平行于 $H^{\prime }$ 的超平面 $H$（图 8-31），则 $Q$ 落在 $H$ 的一侧闭半空间 $H^{+}$ 中，从而 $P\subseteq H^{+}$，即 $H$ 在 $\mathbf{p}$ 处支撑 $P$；且 $\mathbf{p}$ 是 $P$ 中唯一能落在 $H$ 上的点，$H\cap P=\{\mathbf{p}\}$，故 $\mathbf{p}$ 是顶点。(b)⇒(c)：设支撑超平面 $H=[f:d]$ 满足 $H\cap P=\{\mathbf{p}\}$、$f(P)\ge d$。若 $\mathbf{p}=(1-c)\mathbf{x}+c\mathbf{y}$（$0<c<1$，$\mathbf{x},\mathbf{y}\in P$），由 $\mathbf{y}=\frac{1}{c}\mathbf{p}-\left(\frac{1}{c}-1\right)\mathbf{x}$ 推出

$$f(\mathbf{y})=\frac{1}{c}f(\mathbf{p})-\left(\frac{1}{c}-1\right)f(\mathbf{x})\le \frac{1}{c}d-\left(\frac{1}{c}-1\right)d=d$$

而 $\mathbf{y}\in P$ 应有 $f(\mathbf{y})\ge d$，故 $f(\mathbf{y})=d$，$\mathbf{y}\in H\cap P$，与 $H\cap P=\{\mathbf{p}\}$ 矛盾。这一段对任意紧凸集都成立，不必是多面体。(c)⇒(a)：极点显然属于 $M$。∎

图 8-31：过 $\mathbf{p}$ 且平行于 $H^{\prime }$ 的支撑超平面 $H$ 在 $\mathbf{p}$ 处支撑 $P$

例 2

多边形（${\mathbb{R}}^2$ 中的 2-多面体）的轮廓就是顶点集（图 8-32）。闭球的轮廓是其边界（球面上每点都是极点）；开集没有极点，轮廓为空；闭半空间也没有极点。

图 8-32：多边形的轮廓即顶点集——边上的点都落在某条边线段内部，不是极点

原书习题 18 要求证明：$\mathbf{p}$ 是凸集 $S$ 的极点当且仅当从 $S$ 中去掉 $\mathbf{p}$ 后剩下的集合仍是凸集。由此可知，若 $S^{\ast }\subset S$ 且 $\mathrm{conv}{S}^{\ast }=S$，则 $S^{\ast }$ 必须包含 $S$ 的轮廓。但一般 $S^{\ast }$ 可能要比轮廓大；而当 $S$ 紧时，轮廓本身就够了——这就是下面的定理。它说明每个非空紧凸集都有极点，且极点集是凸包等于 $S$ 的最小子集。

定理 15

非空紧凸集 $S$ 是其轮廓（全部极点）的凸包。

证明：对 $S$ 的维数作数学归纳。∎

定理 15 的一个重要应用是下面这一定理——线性规划发展中的关键理论结果之一。线性泛函是连续函数，连续函数在紧集上必取到最大最小值；定理 16 进一步断言：最值一定在极点处取到。

定理 16

设 $f$ 是非空紧凸集 $S$ 上的线性泛函，则存在 $S$ 的极点 $\hat{\mathbf{v}},\hat{\mathbf{w}}$ 使

$$f(\hat{\mathbf{v}})=\underset{\mathbf{v}\in S}{\max }f(\mathbf{v}),f(\hat{\mathbf{w}})=\underset{\mathbf{v}\in S}{\min }f(\mathbf{v})$$

证明思路：设最大值 $m$ 在 ${\mathbf{v}}^{\prime }\in S$ 取到，即 $f({\mathbf{v}}^{\prime })=m$。由定理 15，${\mathbf{v}}^{\prime }=c_1{\mathbf{v}}_1+\cdots +c_k{\mathbf{v}}_k$ 是极点的凸组合（$c_i\ge 0$，权和 1）。若每个极点都满足 $f({\mathbf{v}}_i)<m$，则

$$m=f({\mathbf{v}}^{\prime })=c_{1}f({\mathbf{v}}_1)+\cdots +c_{k}f({\mathbf{v}}_k)<c_{1}m+\cdots +c_{k}m=m(c_1+\cdots +c_k)=m$$

矛盾。故必有某个极点 $\hat{\mathbf{v}}$ 使 $f(\hat{\mathbf{v}})=m$。最小值同理。∎

例 3

设 ${\mathbf{p}}_1=\left[\begin{array}{c}-1\\ 0\end{array}\right],{\mathbf{p}}_2=\left[\begin{array}{c}3\\ 1\end{array}\right],{\mathbf{p}}_3=\left[\begin{array}{c}1\\ 2\end{array}\right]$，$S=\mathrm{conv}\{{\mathbf{p}}_1,{\mathbf{p}}_2,{\mathbf{p}}_3\}$。对下列线性泛函分别求 $f$ 在 $S$ 上的最大值 $m$，并找出所有使 $f(\mathbf{x})=m$ 的点 $\mathbf{x}$：

• a. $f_1(x_1,x_2)=x_1+x_2$
• b. $f_2(x_1,x_2)=-3x_1+x_2$
• c. $f_3(x_1,x_2)=x_1+2x_2$

解 由定理 16，最大值在某个极点取到，所以只需在三个极点处计算取值并选最大。

a. $f_1({\mathbf{p}}_1)=-1,f_1({\mathbf{p}}_2)=4,f_1({\mathbf{p}}_3)=3$，故 $m_1=4$；画出直线 $x_1+x_2=4$ 可见只有 $\mathbf{x}={\mathbf{p}}_2$ 处 $f_1(\mathbf{x})=4$（图 8-33）。

b. $f_2({\mathbf{p}}_1)=3,f_2({\mathbf{p}}_2)=-8,f_2({\mathbf{p}}_3)=-1$，故 $m_2=3$；直线 $-3x_1+x_2=3$ 表明只在 $\mathbf{x}={\mathbf{p}}_1$ 处取到（图 8-34）。

c. $f_3({\mathbf{p}}_1)=-1,f_3({\mathbf{p}}_2)=5,f_3({\mathbf{p}}_3)=5$，故 $m_3=5$；直线 $x_1+2x_2=5$ 表明 $f_3$ 在 ${\mathbf{p}}_2,{\mathbf{p}}_3$ 以及线段 $\overline{{\mathbf{p}}_2{\mathbf{p}}_3}$ 上的每一点取到（图 8-35）——整条边与支撑超平面平行贴合。

图 8-33：(a) $x_1+x_2=4$ 只在顶点 ${\mathbf{p}}_2$ 处支撑三角形

图 8-34：(b) $-3x_1+x_2=3$ 在顶点 ${\mathbf{p}}_1$ 处支撑

图 8-35：(c) $x_1+2x_2=5$ 沿整条边 $\overline{{\mathbf{p}}_2{\mathbf{p}}_3}$ 支撑，最值点有无穷多个

高维情形同理：线性泛函在多面体 $P$ 上的最大值在支撑超平面与 $P$ 的交上取到，这个交要么是单个极点、要么是两个以上极点的凸包（仍是一个多面体，其极点是 $P$ 极点的子集）。

多面体的两种表示

按定义，多面体是有限点集的凸包——这是显式表示（直接列出点）。多面体也可以隐式表示为有限个闭半空间的交。

例 4

设 ${\mathbf{p}}_1=\left[\begin{array}{c}0\\ 1\end{array}\right],{\mathbf{p}}_2=\left[\begin{array}{c}1\\ 0\end{array}\right],{\mathbf{p}}_3=\left[\begin{array}{c}3\\ 2\end{array}\right]$，$S=\mathrm{conv}\{{\mathbf{p}}_1,{\mathbf{p}}_2,{\mathbf{p}}_3\}$。求 $S$ 的隐式表示。

解 简单代数可得三条边所在直线及 $S$ 所在一侧：

• 过 ${\mathbf{p}}_1,{\mathbf{p}}_2$ 的直线：$x_1+x_2=1$，$S$ 在 $x_1+x_2\ge 1$ 一侧，即 $-x_1-x_2\le -1$；
• 过 ${\mathbf{p}}_2,{\mathbf{p}}_3$ 的直线：$x_1-x_2=1$，$S$ 在 $x_1-x_2\le 1$ 一侧；
• 过 ${\mathbf{p}}_3,{\mathbf{p}}_1$ 的直线：$-x_1+3x_2=3$，$S$ 在 $-x_1+3x_2\le 3$ 一侧。

图 8-36：三角形 $S$ 及其三条边界直线

于是 $S$ 可描述为线性不等式组的解集：

$$\{\begin{array}{l}-x_1-x_2\le -1\\ x_1-x_2\le 1\\ -x_1+3x_2\le 3\end{array}\text{即}A\mathbf{x}\le \mathbf{b},A=\left[\begin{array}{cc}-1& -1\\ 1& -1\\ -1& 3\end{array}\right],\mathbf{b}=\left[\begin{array}{c}-1\\ 1\\ 3\end{array}\right]$$

（向量之间的不等号作用于每一对对应分量。）

第 9 章需要把多面体的隐式描述换成最小表示（列出全部极点）。简单情形可以作图；图上看不清时用下面的代数程序：

求出各边界直线两两的交点，把每个交点代入其余不等式检验：全部满足则是多面体的顶点，否则剔除。

例 5

设 $P=\{\mathbf{x}\in {\mathbb{R}}^2:A\mathbf{x}\le \mathbf{b},\mathbf{x}\ge 0\}$，其中

$$A=\left[\begin{array}{cc}1& 3\\ 1& 1\\ 3& 2\end{array}\right],\mathbf{b}=\left[\begin{array}{c}18\\ 8\\ 21\end{array}\right]$$

求 $P$ 的最小表示。

解 $\mathbf{x}\ge 0$ 把 $P$ 限制在第一象限（线性规划的典型约束）。三条边界线：

$$(1)x_1+3x_2=18,(2)x_1+x_2=8,(3)3x_1+2x_2=21$$

三线斜率均为负，草图即可看出 $(0,0),(7,0),(0,6)$ 是顶点。再看直线的交点：

• (1)∩(2)：${\mathbf{p}}_{12}=(3,5)$，坐标非负，代入 (3) 检验：$3(3)+2(5)=19<21$ ✓，${\mathbf{p}}_{12}$ 在 $P$ 内；
• (2)∩(3)：${\mathbf{p}}_{23}=(5,3)$，代入 (1) 检验：$1(5)+3(3)=14<18$ ✓，${\mathbf{p}}_{23}$ 在 $P$ 内；
• (1)∩(3)：${\mathbf{p}}_{13}=(\frac{27}{7},\frac{33}{7})$，代入 (2) 检验：$\frac{27}{7}+\frac{33}{7}=\frac{60}{7}\approx 8.6>8$ ✗，${\mathbf{p}}_{13}$ 不在 $P$ 内。

所以 $P$ 的最小表示为

$$\left\{\left[\begin{array}{c}0\\ 0\end{array}\right],\left[\begin{array}{c}7\\ 0\end{array}\right],\left[\begin{array}{c}3\\ 5\end{array}\right],\left[\begin{array}{c}5\\ 3\end{array}\right],\left[\begin{array}{c}0\\ 6\end{array}\right]\right\}$$

单纯形（Simplex）

单纯形是仿射无关有限向量集的凸包。构造 $k$ 维单纯形（k-单纯形）的递归过程：

• 0-单纯形 $S^0$：单个点 $\{{\mathbf{v}}_1\}$；
• 1-单纯形 $S^1$：$\mathrm{conv}(S^0\cup \{{\mathbf{v}}_2\})$，${\mathbf{v}}_2\notin \mathrm{aff}{S}^0$——线段；
• 2-单纯形 $S^2$：$\mathrm{conv}(S^1\cup \{{\mathbf{v}}_3\})$，${\mathbf{v}}_3\notin \mathrm{aff}{S}^1$——三角形；
• 3-单纯形 $S^3$：$\mathrm{conv}(S^2\cup \{{\mathbf{v}}_4\})$，${\mathbf{v}}_4\notin \mathrm{aff}{S}^2$——四面体；
• 依此类推：$k$-单纯形 $S^k=\mathrm{conv}(S^{k-1}\cup \{{\mathbf{v}}_{k+1}\})$。

图 8-37：从线段到三角形到四面体——单纯形的逐维构造

观察规律：三角形 $S^2$ 的三条棱中，一条是原来的 $S^1$，另外两条是把 $S^1$ 的两个端点”拉伸”到新点 ${\mathbf{v}}_3$ 的线段。四面体 $S^3$ 的四个三角面中，一个是原来的 $S^2$，另外三个是把 $S^2$ 的三条棱拉伸到 ${\mathbf{v}}_4$；顶点则拉伸成棱。这个规律让我们可以”想象”四维的 $S^4$：称为五胞体（pentatope），由 $S^3$ 与一个不在其三维空间中的点 ${\mathbf{v}}_5$ 作凸包得到。完整图形画不出来，但图 8-38 很有启发性：$S^4$ 有 5 个顶点，任意 4 个顶点确定一个四面体形状的侧面（facet），共 5 个；图中标出全部 10 条棱，由此可想象 10 个三角面。

图 8-38：四维单纯形 $S^4$ 投影到 ${\mathbb{R}}^2$，突出显示两个四面体侧面（${\mathbf{v}}_1{\mathbf{v}}_2{\mathbf{v}}_4{\mathbf{v}}_5$ 与 ${\mathbf{v}}_2{\mathbf{v}}_3{\mathbf{v}}_4{\mathbf{v}}_5$）

图 8-39：$S^4$ 的另一种画法——第五个顶点被画在四面体 $S^3$ “内部”，突出显示的四面体侧面看起来也在内部

超立方体（Hypercube）

设 $I_i=\overline{0{\mathbf{e}}_i}$ 是从原点到标准基向量 ${\mathbf{e}}_i$ 的线段。对 $1\le k\le n$，向量和

$$C^k=I_1+I_2+\cdots +I_k$$

称为 k 维超立方体。（两个集合的向量和定义为 $A+B=\{\mathbf{a}+\mathbf{b}:\mathbf{a}\in A,\mathbf{b}\in B\}$。）

构造过程：$C^1$ 就是线段 $I_1$；把 $C^1$ 平移 ${\mathbf{e}}_2$，初、末位置构成的凸包是正方形 $C^2$；把 $C^2$ 平移 ${\mathbf{e}}_3$ 得立方体 $C^3$；把 $C^3$ 平移 ${\mathbf{e}}_4$ 得四维超立方体 $C^4$（图 8-40 至 8-42）。

图 8-40：$C^1$——线段

图 8-41：$C^2$——正方形

图 8-42：$C^3$——立方体

$C^4$ 的二维投影见图 8-43、8-44：$C^3$ 的每条棱被拉伸成一个方形面，每个方形面被拉伸成一个立方形面。图 8-45 至 8-47 突出显示 $C^4$ 的三个立方侧面：分别来自 $C^3$ 的左面、前面和顶面被拉伸成的立方体。

图 8-43：$C^4$ 投影到 ${\mathbb{R}}^2$（一）

图 8-44：$C^4$ 投影到 ${\mathbb{R}}^2$（二）

图 8-45：$C^4$ 的立方侧面 (a)——来自 $C^3$ 的左面

图 8-46：$C^4$ 的立方侧面 (b)——来自 $C^3$ 的前面

图 8-47：$C^4$ 的立方侧面 (c)——来自 $C^3$ 的顶面

图 8-48：$C^4$ 的另一种画法——平移后的 $C^3$ 被”放”在 $C^3$ 内部，畸变更小、更易看清立方侧面

$C^4$ 的计数：立方面共 8 个（原像与像各 1 个，加上 $C^3$ 的 6 个方形面拉伸成的 6 个）；方形面有 $2\times 6+12=24$ 个（原像与像的 $6+6$ 个，加 12 条棱拉伸成的 12 个）；棱有 $2\times 12+8=32$ 条（2 倍棱数加顶点数）；顶点有 $2\times 8=16$ 个（来自 $C^3$ 及其平移像）。

欧拉公式

多面体研究中一个出色的结果是欧拉（1707–1783）首先证明的公式，联系各维面的数目。设 $f_k(P)$ 为 $n$ 维多面体 $P$ 的 k-面个数：

$$\text{欧拉公式：}\sum _{k=0}^{n-1}(-1{)}^k{f}_k(P)=1+(-1{)}^{n-1}$$

特别地 $n=3$ 时 $v-e+f=2$（顶点数 − 棱数 + 面数 = 2）。用正方体验证：$8-12+6=2$ ✓；用四面体验证：$4-6+4=2$ ✓。

8.5 练习题（Practice Problem）

题目：求由 $A\mathbf{x}\le \mathbf{b},\mathbf{x}\ge 0$ 定义的多面体 $P$ 的最小表示，其中 $A=\left[\begin{array}{cc}1& 3\\ 1& 2\\ 2& 1\end{array}\right],\mathbf{b}=\left[\begin{array}{c}12\\ 9\\ 12\end{array}\right]$。

解答：三条不等式为 (a) $x_1+3x_2\le 12$、(b) $x_1+2x_2\le 9$、(c) $2x_1+x_2\le 12$。$\mathbf{x}\ge 0$ 限制在第一象限，$(0,0)$ 是一个顶点。三条线在 $x_1$ 轴上的截距为 12、9、6，取最小者，$(6,0)$ 是顶点；在 $x_2$ 轴上的截距为 4、4.5、12，取最小者，$(0,4)$ 是顶点。

再看三线在正象限的交点：

• (a)∩(b)：${\mathbf{p}}_{ab}=(3,3)$，代入 (c)：$2(3)+1(3)=9<12$ ✓，${\mathbf{p}}_{ab}$ 在 $P$ 内；
• (b)∩(c)：${\mathbf{p}}_{bc}=(5,2)$，代入 (a)：$1(5)+3(2)=11<12$ ✓，${\mathbf{p}}_{bc}$ 在 $P$ 内；
• (a)∩(c)：${\mathbf{p}}_{ac}=(4.8,2.4)$，代入 (b)：$1(4.8)+2(2.4)=9.6>9$ ✗，${\mathbf{p}}_{ac}$ 不在 $P$ 内。

所以 $P$ 的五个顶点为 $(0,0),(6,0),(5,2),(3,3),(0,4)$，构成最小表示（图 8-49）。

图 8-49：练习题的多面体 $P$——五边形区域及其五个顶点

通关标准

• 会从 $A\mathbf{x}\le \mathbf{b},\mathbf{x}\ge 0$ 求多面体的最小表示（截距 + 两两交点回代检验）；
• 分得清顶点 / 极点 / 最小表示三个概念及其联系（定理 14）；
• 记住”线性泛函在紧凸集上的最值在极点取到”（定理 16）——这是第 9 章线性规划的钥匙；
• 知道单纯形与超立方体的递归构造和欧拉公式 $v-e+f=2$。

本节习题（最值问题、最小表示、面数计数、正多面体只有五种的证明等）见原书 8.5 节。

8.6 曲线与曲面

几千年来造船工匠用细长木条弯出船壳；近代设计师用柔性金属长条绘制汽车与飞机的曲面。重物与销钉把金属条压成光滑曲线——自然三次样条。相邻两个控制点（销钉或重物）之间的曲线用三次多项式参数表示。遗憾的是：移动一个控制点会改变整条曲线的形状（销钉与重物对金属条施加的物理力会传遍全长），设计师早想要”局部控制”——动一个点只影响一小段曲线。1962 年，法国汽车工程师 Pierre Bézier 通过增加控制点并用一类以他命名的曲线解决了这个问题。

贝塞尔曲线

贝塞尔曲线在计算机图形学与工程中都极为重要：Adobe Illustrator、Macromedia Freehand、OpenGL 等都在用。它让程序只用少量控制点就能精确存储曲线段与曲面信息，所有图形命令只需对控制点计算，其特殊结构还能加速图形管线中生成最终显示的其他计算。

8.3 节习题介绍过二次贝塞尔曲线以及构造高次曲线的一种方法。这里重点讨论二次与三次贝塞尔曲线，分别由三个或四个控制点确定，记为 ${\mathbf{p}}_0,{\mathbf{p}}_1,{\mathbf{p}}_2$（与 ${\mathbf{p}}_3$）。这些点可以在 ${\mathbb{R}}^2$ 或 ${\mathbb{R}}^3$ 中，也可以用 ${\mathbb{R}}^3$ 或 ${\mathbb{R}}^4$ 中的齐次形式表示。曲线的标准参数描述（$0\le t\le 1$）为：

$$\mathbf{w}(t)=(1-t{)}^2{\mathbf{p}}_0+2t(1-t){\mathbf{p}}_1+t^2{\mathbf{p}}_2\text{\hspace{1em}(1)}$$ $$\mathbf{x}(t)=(1-t{)}^3{\mathbf{p}}_0+3t(1-t{)}^2{\mathbf{p}}_1+3t^2(1-t){\mathbf{p}}_2+t^3{\mathbf{p}}_3\text{\hspace{1em}(2)}$$

图 8-50：典型的二次与三次贝塞尔曲线——通常只通过首末控制点，但整条曲线始终落在控制点的凸包内

贝塞尔曲线在图形学中有用的原因之一：其本质性质在线性变换与平移下保持。若 $A$ 是相应尺寸的矩阵，由矩阵乘法的线性性：

$$A\mathbf{x}(t)=A\left[(1-t{)}^3{\mathbf{p}}_0+3t(1-t{)}^2{\mathbf{p}}_1+3t^2(1-t){\mathbf{p}}_2+t^3{\mathbf{p}}_3\right]=(1-t{)}^{3}A{\mathbf{p}}_0+3t(1-t{)}^{2}A{\mathbf{p}}_1+3t^2(1-t)A{\mathbf{p}}_2+t^{3}A{\mathbf{p}}_3$$

即 $A\mathbf{x}(t)$ 是以 $A{\mathbf{p}}_0,\dots ,A{\mathbf{p}}_3$ 为控制点的贝塞尔曲线（平移情形见原书习题 1）。

曲线的形状还暗示控制点决定了曲线在首末控制点处的切线。回忆微积分：参数曲线 $\mathbf{y}(t)$ 在 $\mathbf{y}(t)$ 处切线的方向由导数 ${\mathbf{y}}^{\prime }(t)$（切向量，逐分量求导）给出。

例 1

确定二次贝塞尔曲线 $\mathbf{w}(t)$ 在 $t=0$ 与 $t=1$ 处的切向量与控制点的关系。

解 把 (1) 中的权重展开成简单多项式：

$$\mathbf{w}(t)=(1-2t+t^2){\mathbf{p}}_0+(2t-2t^2){\mathbf{p}}_1+t^2{\mathbf{p}}_2$$

由于对函数求导是线性变换：

$${\mathbf{w}}^{\prime }(t)=(-2+2t){\mathbf{p}}_0+(2-4t){\mathbf{p}}_1+2t{\mathbf{p}}_2$$

于是

$${\mathbf{w}}^{\prime }(0)=-2{\mathbf{p}}_0+2{\mathbf{p}}_1=2({\mathbf{p}}_1-{\mathbf{p}}_0),{\mathbf{w}}^{\prime }(1)=-2{\mathbf{p}}_1+2{\mathbf{p}}_2=2({\mathbf{p}}_2-{\mathbf{p}}_1)$$

即 ${\mathbf{p}}_0$ 处的切向量指向从 ${\mathbf{p}}_0$ 到 ${\mathbf{p}}_1$ 的方向，长度是该线段的两倍；末端同理指向 ${\mathbf{p}}_2-{\mathbf{p}}_1$。注意当 ${\mathbf{p}}_1={\mathbf{p}}_0$ 时 ${\mathbf{w}}^{\prime }(0)=0$，此时 $\mathbf{w}(t)=(1-t^2){\mathbf{p}}_1+t^2{\mathbf{p}}_2$，图像就是从 ${\mathbf{p}}_1$ 到 ${\mathbf{p}}_2$ 的线段。

连接两条贝塞尔曲线

两条基本贝塞尔曲线可以首尾相接：第一段 $\mathbf{x}(t)$ 的终点是第二段 $\mathbf{y}(t)$ 的起点 ${\mathbf{p}}_2$。合成曲线在 ${\mathbf{p}}_2$ 处称为具有 $G^0$ 几何连续性——两段确实接上了。但如果两段在 ${\mathbf{p}}_2$ 处的切线方向不同，就会出现”尖角”（方向的突变），见图 8-51。

图 8-51：${\mathbf{p}}_2$ 处的 $G^0$ 连续——接上了，但有尖角

为避免急弯，通常只需调整为 $G^1$ 几何连续：两个切向量在 ${\mathbf{p}}_2$ 处指向同一方向（即 ${\mathbf{x}}^{\prime }(1)$ 与 ${\mathbf{y}}^{\prime }(0)$ 平行同向，长度可以不同）。若两个切向量相等，则切向量连续，合成曲线具有 $C^1$ 参数连续性。图 8-52 的 (a) 是 $G^1$、(b) 是 $C^1$。

图 8-52：(a) $G^1$ 连续与 (b) $C^1$ 连续

例 2

设 $\mathbf{x}(t)$ 与 $\mathbf{y}(t)$ 是两条二次贝塞尔曲线，控制点分别为 $\{{\mathbf{p}}_0,{\mathbf{p}}_1,{\mathbf{p}}_2\}$ 与 $\{{\mathbf{p}}_2,{\mathbf{p}}_3,{\mathbf{p}}_4\}$，两段在 ${\mathbf{p}}_2=\mathbf{x}(1)=\mathbf{y}(0)$ 处相接。

a. 若合成曲线在 ${\mathbf{p}}_2$ 处具有 $G^1$ 连续，控制点需满足什么代数条件？几何上如何说？ b. 对 $C^1$ 连续重复 (a)。

解：

a. 由例 1，${\mathbf{x}}^{\prime }(1)=2({\mathbf{p}}_2-{\mathbf{p}}_1)$；把 $\mathbf{y}(t)$ 的控制点代入例 1 公式得 ${\mathbf{y}}^{\prime }(0)=2({\mathbf{p}}_3-{\mathbf{p}}_2)$。$G^1$ 连续即 ${\mathbf{y}}^{\prime }(0)=k{\mathbf{x}}^{\prime }(1)$，$k>0$，等价于

$${\mathbf{p}}_3-{\mathbf{p}}_2=k({\mathbf{p}}_2-{\mathbf{p}}_1),k>0\text{\hspace{1em}(3)}$$

几何上：${\mathbf{p}}_2$ 落在从 ${\mathbf{p}}_1$ 到 ${\mathbf{p}}_3$ 的线段上。证明：令 $t=(k+1{)}^{-1}$，则 $0<t<1$，且 $k=\frac{1-t}{t}$，代回 (3) 整理得 ${\mathbf{p}}_2=(1-t){\mathbf{p}}_1+t{\mathbf{p}}_3$。

b. $C^1$ 连续要求 ${\mathbf{y}}^{\prime }(0)={\mathbf{x}}^{\prime }(1)$，即 $2({\mathbf{p}}_3-{\mathbf{p}}_2)=2({\mathbf{p}}_2-{\mathbf{p}}_1)$，于是 ${\mathbf{p}}_3-{\mathbf{p}}_2={\mathbf{p}}_2-{\mathbf{p}}_1$，即

$${\mathbf{p}}_2=\frac{{\mathbf{p}}_1+{\mathbf{p}}_3}{2}$$

几何上：${\mathbf{p}}_2$ 是从 ${\mathbf{p}}_1$ 到 ${\mathbf{p}}_3$ 线段的中点（图 8-52、8-53）。

图 8-53：两条三次贝塞尔曲线的 $C^1$ 连续——接合点恰在相邻两控制点连线的中点

两条曲线具有 $C^2$（参数）连续是指既有 $C^1$ 连续、又有 ${\mathbf{x}}^{\prime \prime }(1)={\mathbf{y}}^{\prime \prime }(0)$。三次贝塞尔曲线可以做到 $C^2$，但这会严重限制控制点的位置。另一类三次曲线——B 样条（B-splines）——天生具有 $C^2$ 连续，因为每对相邻曲线共享三个控制点而不是一个；代价是控制点更多、计算更多（本节习题会讨论）。

出人意料的是：若 $\mathbf{x}(t)$ 与 $\mathbf{y}(t)$ 在 ${\mathbf{p}}_3$ 处相接，在 ${\mathbf{p}}_3$ 处看起来的光滑程度通常对 $G^1$ 与 $C^1$ 是一样的，因为 ${\mathbf{x}}^{\prime }(t)$ 的大小与曲线的物理形状无关，只反映参数化的方式。比如令 $\mathbf{z}(t)=\mathbf{x}(2t)$，则 $\mathbf{z}(t)$ 走完同一曲线的速度是原来的两倍；由链式法则 ${\mathbf{z}}^{\prime }(t)=2{\mathbf{x}}^{\prime }(2t)$，${\mathbf{p}}_3$ 处的切向量也变成两倍，但曲线形状没变。

实践中常把许多简单贝塞尔曲线拼接起来构成图形对象。排版程序是重要应用：字体中许多字母含曲线段。例如 PostScript® 字体中每个字母存储为一组控制点，加上用线段与贝塞尔曲线构造字母”轮廓”的信息；放大字母基本上就是把每个控制点坐标乘同一个比例因子，再填充实心部分。图 8-54 展示了一个 PostScript 字符及其控制点。

图 8-54：一个 PostScript 字符——可见大量控制点

贝塞尔曲线的矩阵方程

贝塞尔曲线是用多项式作权重的控制点线性组合，$\mathbf{x}(t)$ 可写成

$$\mathbf{x}(t)=\left[\begin{array}{cccc}{\mathbf{p}}_0& {\mathbf{p}}_1& {\mathbf{p}}_2& {\mathbf{p}}_3\end{array}\right]\left[\begin{array}{c}(1-t{)}^3\\ 3t(1-t{)}^2\\ 3t^2(1-t)\\ t^3\end{array}\right]=\left[\begin{array}{cccc}{\mathbf{p}}_0& {\mathbf{p}}_1& {\mathbf{p}}_2& {\mathbf{p}}_3\end{array}\right]\left[\begin{array}{c}1-3t+3t^2-t^3\\ 3t-6t^2+3t^3\\ 3t^2-3t^3\\ t^3\end{array}\right]$$ $$=\left[\begin{array}{cccc}{\mathbf{p}}_0& {\mathbf{p}}_1& {\mathbf{p}}_2& {\mathbf{p}}_3\end{array}\right]\left[\begin{array}{cccc}1& -3& 3& -1\\ 0& 3& -6& 3\\ 0& 0& 3& -3\\ 0& 0& 0& 1\end{array}\right]\left[\begin{array}{c}1\\ t\\ t^2\\ t^3\end{array}\right]$$

以四个控制点为列的矩阵称为几何矩阵 $G$；$4\times 4$ 的多项式系数矩阵是贝塞尔基矩阵 $M_B$。记 $\mathbf{u}(t)$ 为 $t$ 的幂组成的列向量，则贝塞尔曲线为

$$\mathbf{x}(t)=G{M}_B\mathbf{u}(t)\text{\hspace{1em}(4)}$$

图形学中其他参数三次曲线也写成这种形式：把 $M_B$ 的元素换成适当数值就得到 B 样条（比贝塞尔”更光滑”，但不通过任何控制点）；把 $M_B$ 换成 Hermite 基矩阵就得到 Hermite 三次曲线，此时几何矩阵的列由曲线的起点、终点及这两点处的切向量组成。

为讨论贝塞尔曲面，还要把 (4) 用参数 $s$ “换个方向”分解一次：

$$\mathbf{x}(s)=\mathbf{u}(s{)}^T{M}_B^T\left[\begin{array}{c}{\mathbf{p}}_0\\ {\mathbf{p}}_1\\ {\mathbf{p}}_2\\ {\mathbf{p}}_3\end{array}\right]=\left[\begin{array}{cccc}(1-s{)}^3& 3s(1-s{)}^2& 3s^2(1-s)& s^3\end{array}\right]\left[\begin{array}{c}{\mathbf{p}}_0\\ {\mathbf{p}}_1\\ {\mathbf{p}}_2\\ {\mathbf{p}}_3\end{array}\right]\text{\hspace{1em}(5)}$$

这里 $4\times 1$ 的控制点矩阵称为几何向量——应视为分块（partitioned）矩阵，元素是列向量；它左边的矩阵也是分块矩阵，每块是标量。分块矩阵乘法有意义，因为几何向量中的每个（向量）元素既可以左乘标量也可以左乘矩阵。

贝塞尔曲面

三维双三次曲面片可以由四个贝塞尔曲线的几何矩阵构造。考虑 $4\times 4$ 个控制点 ${\mathbf{p}}_{ij}$（$i,j=1,\dots ,4$）组成的分块矩阵 $G$。由 (4)，$G$ 右乘权重向量 $M_B\mathbf{u}(t)={\left[\begin{array}{cccc}(1-t{)}^3& 3t(1-t{)}^2& 3t^2(1-t)& t^3\end{array}\right]}^T$ 得到一个分块 $4\times 1$ 矩阵，每个元素是一条贝塞尔曲线。固定 $t$，这个列向量又可作为 (5) 中另一个变量 $s$ 的几何向量。由此得到贝塞尔双三次曲面：

$$\mathbf{x}(s,t)=\mathbf{u}(s{)}^T{M}_B^{T}G{M}_B\mathbf{u}(t),0\le s,t\le 1\text{\hspace{1em}(6)}$$

$\mathbf{x}(s,t)$ 是 16 个控制点的线性组合。若把控制点排成较均匀的矩形阵列（图 8-55），贝塞尔曲面就像由八条贝塞尔曲线”编织”控制：四条沿 $s$ 方向、四条沿 $t$ 方向；曲面实际通过四个”角”上的控制点。作为大曲面中的一片时，十六点曲面与邻居共享其 12 个边界控制点。

图 8-55：贝塞尔双三次曲面片的 16 个控制点

曲线与曲面的近似

在 CAD 程序和写实游戏中，设计师在工作站上”组装场景”，与几何对象交互；对象的每次微调都需要程序重新计算。贝塞尔曲线与曲面用比多边形近似少得多的控制点描述对象，大幅缩短计算时间、加快设计迭代。

但场景组装完成后，最终图像生成阶段的计算需求不同：渲染需要引入光源、上色、加纹理、模拟反射，这时由平面和直边组成的多面体对象更方便。例如计算表面上点 $\mathbf{p}$ 处的反射光方向，需要入射光方向和表面法向量（垂直于 $\mathbf{p}$ 处切平面的向量）。法向量在”小平面片”表面上容易算：若 ${\mathbf{p}}_1,{\mathbf{p}}_2,{\mathbf{p}}_3$ 是一个小平面多边形的相邻顶点，表面法向量就是 $\pm ({\mathbf{p}}_2-{\mathbf{p}}_1)\times ({\mathbf{p}}_2-{\mathbf{p}}_3)$；多边形足够小时，整个多边形只需一个法向量。而且两个常用的着色算法 Gouraud 着色与 Phong 着色都要求表面由多边形定义。

因此场景组装阶段的贝塞尔曲线与曲面通常被近似成直线段和多面体表面。基本思想是：把曲线或曲面不断分成更小的片段，每段的控制点越来越多。

贝塞尔曲线与曲面的递归细分

图 8-56 显示贝塞尔曲线的四个控制点 ${\mathbf{p}}_0,\dots ,{\mathbf{p}}_3$，以及两条新曲线的控制点，每条新曲线与原曲线的一半重合。“左”曲线从 ${\mathbf{q}}_0={\mathbf{p}}_0$ 开始，到原曲线中点 ${\mathbf{q}}_3$ 结束；“右”曲线从 ${\mathbf{r}}_0={\mathbf{q}}_3$ 开始，到 ${\mathbf{r}}_3={\mathbf{p}}_3$ 结束。

图 8-56：贝塞尔曲线的细分——两条半段曲线各有一套新控制点

图 8-57 显示新控制点围出的区域比原控制点围出的更”细长”。随着控制点间距离缩小，每段曲线的控制点也越来越接近共线——贝塞尔曲线的这种变差缩减性质依赖于”贝塞尔曲线总在控制点的凸包内”这一事实。

图 8-57：原控制点与两半段曲线控制点的凸包对比

新控制点与原控制点之间有简单公式。显然 ${\mathbf{q}}_0={\mathbf{p}}_0$、${\mathbf{r}}_3={\mathbf{p}}_3$。原曲线 $\mathbf{x}(t)$ 的中点在 $\mathbf{x}(0.5)$ 处，把 (2) 展开成多项式形式：

$$\mathbf{x}(t)=(1-3t+3t^2-t^3){\mathbf{p}}_0+(3t-6t^2+3t^3){\mathbf{p}}_1+(3t^2-3t^3){\mathbf{p}}_2+t^3{\mathbf{p}}_3\text{\hspace{1em}(7)}$$

于是

$${\mathbf{q}}_3={\mathbf{r}}_0=\mathbf{x}(0.5)=\frac{1}{8}({\mathbf{p}}_0+3{\mathbf{p}}_1+3{\mathbf{p}}_2+{\mathbf{p}}_3)\text{\hspace{1em}(8)}$$

其余”内部”控制点的公式要用切向量推导。对 (7) 求导：

$${\mathbf{x}}^{\prime }(t)=(-3+6t-3t^2){\mathbf{p}}_0+(3-12t+9t^2){\mathbf{p}}_1+(6t-9t^2){\mathbf{p}}_2+3t^2{\mathbf{p}}_3$$

特别地

$${\mathbf{x}}^{\prime }(0)=3({\mathbf{p}}_1-{\mathbf{p}}_0),{\mathbf{x}}^{\prime }(1)=3({\mathbf{p}}_3-{\mathbf{p}}_2)\text{\hspace{1em}(9)}$$

几何上：${\mathbf{p}}_1$ 在曲线于 ${\mathbf{p}}_0$ 处的切线上，${\mathbf{p}}_2$ 在 ${\mathbf{p}}_3$ 处的切线上（图 8-57）。又由 ${\mathbf{x}}^{\prime }(t)$ 算得

$${\mathbf{x}}^{\prime }(0.5)=\frac{3}{4}(-{\mathbf{p}}_0-{\mathbf{p}}_1+{\mathbf{p}}_2+{\mathbf{p}}_3)\text{\hspace{1em}(10)}$$

设 $\mathbf{y}(t)$、$\mathbf{z}(t)$ 分别是由 ${\mathbf{q}}_0,\dots ,{\mathbf{q}}_3$ 与 ${\mathbf{r}}_0,\dots ,{\mathbf{r}}_3$ 确定的贝塞尔曲线。$\mathbf{y}(t)$ 走的是 $\mathbf{x}(t)$ 的前半段路径，$\mathbf{y}(t)=\mathbf{x}(0.5t)$；$\mathbf{z}(t)$ 从 $\mathbf{x}(0.5)$ 出发，$\mathbf{z}(t)=\mathbf{x}(0.5+0.5t)$。由链式法则：

$${\mathbf{y}}^{\prime }(t)=0.5{\mathbf{x}}^{\prime }(0.5t),{\mathbf{z}}^{\prime }(t)=0.5{\mathbf{x}}^{\prime }(0.5+0.5t)\text{\hspace{1em}(11)}$$

由 (9)（把 $\mathbf{x}$ 换成 $\mathbf{y}$）、(11) 取 $t=0$、再由 (9) 得：

$$3({\mathbf{q}}_1-{\mathbf{q}}_0)={\mathbf{y}}^{\prime }(0)=0.5{\mathbf{x}}^{\prime }(0)=\frac{3}{2}({\mathbf{p}}_1-{\mathbf{p}}_0)\text{\hspace{1em}(12)}$$

由 (9)（${\mathbf{y}}^{\prime }(1)$ 处）、(11) 取 $t=1$、(10) 得：

$$3({\mathbf{q}}_3-{\mathbf{q}}_2)={\mathbf{y}}^{\prime }(1)=0.5{\mathbf{x}}^{\prime }(0.5)=\frac{3}{8}(-{\mathbf{p}}_0-{\mathbf{p}}_1+{\mathbf{p}}_2+{\mathbf{p}}_3)\text{\hspace{1em}(13)}$$

联立 (8)(9)(10)(12)(13) 可解出 ${\mathbf{q}}_0,\dots ,{\mathbf{q}}_3$ 的公式（原书习题 13）。几何上如图 8-58：内部控制点 ${\mathbf{q}}_1$、${\mathbf{r}}_2$ 分别是线段 $\overline{{\mathbf{p}}_0{\mathbf{p}}_1}$ 与 $\overline{{\mathbf{p}}_2{\mathbf{p}}_3}$ 的中点；把 $\overline{{\mathbf{p}}_1{\mathbf{p}}_2}$ 的中点与 ${\mathbf{q}}_1$ 相连，所得线段的中点正是 ${\mathbf{q}}_2$！

图 8-58：细分后新控制点的几何结构——只需”取中点”就能画出来

至此完成一步细分。“递归”开始：两条新曲线继续细分，直到所有曲线段足够直（也可以”自适应”：某段已足够直就不再细分）。细分结束后，把每段的端点用直线段连起来，场景就为最终图像生成的下一步做好了准备。

贝塞尔双三次曲面的每个横截面都是贝塞尔曲线，具有同样的变差缩减性质，所以细分过程可以逐个横截面进行。基本策略：对参数为 $s$ 的四条”平行”贝塞尔曲线分别细分，得到四组各 8 个控制点；当 $t$ 变化时得到 8 条各有 4 个控制点的曲线，再对每组细分，共产生 64 个控制点。自适应递归在这里也可行，但有一些细节需要小心。

8.6 练习题（Practice Problems）

B 样条与贝塞尔不同，通常不通过控制点。单段 B 样条的参数形式为

$$\mathbf{x}(t)=\frac{1}{6}\left[(1-t{)}^3{\mathbf{p}}_0+(3t^3-6t^2+4){\mathbf{p}}_1+(-3t^3+3t^2+3t+1){\mathbf{p}}_2+t^3{\mathbf{p}}_3\right]\text{\hspace{1em}(14)}$$

$0\le t\le 1$，控制点为 ${\mathbf{p}}_0,\dots ,{\mathbf{p}}_3$。当 $t$ 从 0 变到 1，$\mathbf{x}(t)$ 画出一条贴近线段 $\overline{{\mathbf{p}}_1{\mathbf{p}}_2}$ 的短曲线。代数变形后也可写成

$$\mathbf{x}(t)=\frac{1}{6}\left[(1-t{)}^3{\mathbf{p}}_0+(3t(1-t{)}^2-3t+4){\mathbf{p}}_1+(3t^2(1-t)+3t+1){\mathbf{p}}_2+t^3{\mathbf{p}}_3\right]\text{\hspace{1em}(15)}$$

与贝塞尔曲线对比：除开头的 $\frac{1}{6}$ 因子外，${\mathbf{p}}_0,{\mathbf{p}}_3$ 项相同；${\mathbf{p}}_1$ 的分量多了 $-3t+4$，${\mathbf{p}}_2$ 的分量多了 $3t+1$，把曲线往 $\overline{{\mathbf{p}}_1{\mathbf{p}}_2}$ 方向拉近。$\frac{1}{6}$ 因子保证系数之和为 1。图 8-59 比较了同控制点的 B 样条与贝塞尔曲线。

图 8-59：B 样条段与贝塞尔曲线对比——B 样条更贴近 $\overline{{\mathbf{p}}_1{\mathbf{p}}_2}$，且不经过任何控制点

题 1：证明 B 样条不从 ${\mathbf{p}}_0$ 出发，但 $\mathbf{x}(0)$ 属于 $\mathrm{conv}\{{\mathbf{p}}_0,{\mathbf{p}}_1,{\mathbf{p}}_2\}$；并设 ${\mathbf{p}}_0,{\mathbf{p}}_1,{\mathbf{p}}_2$ 仿射无关，求 $\mathbf{x}(0)$ 关于 $\{{\mathbf{p}}_0,{\mathbf{p}}_1,{\mathbf{p}}_2\}$ 的仿射坐标。

解答：在 (14) 中令 $t=0$：

$$\mathbf{x}(0)=\frac{1}{6}\left[{\mathbf{p}}_0+4{\mathbf{p}}_1+{\mathbf{p}}_2\right]=\frac{1}{6}{\mathbf{p}}_0+\frac{2}{3}{\mathbf{p}}_1+\frac{1}{6}{\mathbf{p}}_2\ne {\mathbf{p}}_0$$

系数 $\frac{1}{6},\frac{2}{3},\frac{1}{6}$ 非负且和为 1，故 $\mathbf{x}(0)\in \mathrm{conv}\{{\mathbf{p}}_0,{\mathbf{p}}_1,{\mathbf{p}}_2\}$；仿射坐标为 $\left(\frac{1}{6},\frac{2}{3},\frac{1}{6}\right)$。

题 2：证明 B 样条不终止于 ${\mathbf{p}}_3$，但 $\mathbf{x}(1)$ 属于 $\mathrm{conv}\{{\mathbf{p}}_1,{\mathbf{p}}_2,{\mathbf{p}}_3\}$；并设 ${\mathbf{p}}_1,{\mathbf{p}}_2,{\mathbf{p}}_3$ 仿射无关，求 $\mathbf{x}(1)$ 关于 $\{{\mathbf{p}}_1,{\mathbf{p}}_2,{\mathbf{p}}_3\}$ 的仿射坐标。

解答：在 (14) 中令 $t=1$：

$$\mathbf{x}(1)=\frac{1}{6}\left[{\mathbf{p}}_1+4{\mathbf{p}}_2+{\mathbf{p}}_3\right]=\frac{1}{6}{\mathbf{p}}_1+\frac{2}{3}{\mathbf{p}}_2+\frac{1}{6}{\mathbf{p}}_3\ne {\mathbf{p}}_3$$

系数非负、和为 1，故 $\mathbf{x}(1)\in \mathrm{conv}\{{\mathbf{p}}_1,{\mathbf{p}}_2,{\mathbf{p}}_3\}$；仿射坐标为 $\left(\frac{1}{6},\frac{2}{3},\frac{1}{6}\right)$。

通关标准

• 会写出二次/三次贝塞尔曲线的参数式，并说明曲线总在控制点的凸包内；
• 会算端点切向量（${\mathbf{x}}^{\prime }(0)=3({\mathbf{p}}_1-{\mathbf{p}}_0)$ 等），并据此写出 $G^0/G^1/C^1$ 连续的控制点条件（$G^1$：${\mathbf{p}}_2$ 在 $\overline{{\mathbf{p}}_1{\mathbf{p}}_3}$ 上；$C^1$：${\mathbf{p}}_2$ 是中点）；
• 理解几何矩阵 × 基矩阵 × 幂向量这一通用形式，以及双三次曲面的 $\mathbf{x}(s,t)=\mathbf{u}(s{)}^T{M}_B^{T}G{M}_B\mathbf{u}(t)$；
• 知道递归细分”取中点”的几何结构和 B 样条为何天生 $C^2$。

本节习题（平移与凸包性质、B 样条基矩阵、四分体字体转换、细分控制点公式等）见原书 8.6 节。

自测一下

1. ${\mathbb{R}}^2$ 中三点 ${\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3$ 不共线，点 $\mathbf{p}$ 满足 $\mathbf{p}-{\mathbf{v}}_1=3({\mathbf{v}}_2-{\mathbf{v}}_1)-2({\mathbf{v}}_3-{\mathbf{v}}_1)$。$\mathbf{p}$ 是 ${\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3$ 的仿射组合吗？权重是多少？

是。由定理 1，$\mathbf{y}-{\mathbf{v}}_1$ 是平移点的线性组合当且仅当 $\mathbf{y}$ 是仿射组合，所以 $\mathbf{p}$ 在 $\mathrm{aff}\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3\}$ 中。具体权重：$\mathbf{p}=(1-3+2){\mathbf{v}}_1+3{\mathbf{v}}_2-2{\mathbf{v}}_3=0\cdot {\mathbf{v}}_1+3{\mathbf{v}}_2-2{\mathbf{v}}_3$，权重 $0,3,-2$ 之和为 1。注意权重允许负数，这正是仿射（区别于凸）的特征。

2. 判断 $\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3,{\mathbf{v}}_4\}$（${\mathbf{v}}_i\in {\mathbb{R}}^3$）是否仿射相关，最省事的判据是什么？

由定理 5(c)：任取一个基准点（如 ${\mathbf{v}}_1$），计算 ${\mathbf{v}}_2-{\mathbf{v}}_1,{\mathbf{v}}_3-{\mathbf{v}}_1,{\mathbf{v}}_4-{\mathbf{v}}_1$，对以它们为列的 $3\times 3$ 矩阵行化简——列线性相关当且仅当原四点仿射相关。（等价地也可用定理 5(d) 对 $4\times 4$ 齐次形式矩阵行化简。）由于 ${\mathbb{R}}^3$ 中 4 个点超过 $n+1=4$ 个不多但需真判；若是 5 个或更多点则必仿射相关（8.2 习题 11）。

3. 点 $\mathbf{p}$ 关于三角形 $\{\mathbf{a},\mathbf{b},\mathbf{c}\}$ 的重心坐标是 $(-0.2,0.8,0.4)$。$\mathbf{p}$ 在三角形内部吗？权重和不等于 1 有问题吗？

不在内部——第一个重心坐标为负，说明 $\mathbf{p}$ 落在边 $\overline{\mathbf{bc}}$ 对面的一侧之外；全为正是”内部”的充要条件。权重和 $-0.2+0.8+0.4=1$，没问题：重心坐标本来就要求和为 1，只是其中可以有负值。

4. 线性泛函 $f(x_1,x_2)=2x_1-x_2$ 定义的超平面 $[f:3]$ 的法向量是什么？它和 $[f:0]$ 是什么关系？

法向量 $\mathbf{n}=\left[\begin{array}{c}2\\ -1\end{array}\right]$，超平面即直线 $2x_1-x_2=3$。$[f:0]=\{\mathbf{x}:\mathbf{n}\cdot \mathbf{x}=0\}=\mathrm{Nul}\left[\begin{array}{cc}2& -1\end{array}\right]$ 是过原点的平行直线（$\mathbf{n}$ 的正交补），$[f:3]=[f:0]+\mathbf{p}$，其中 $\mathbf{p}$ 是任一满足 $\mathbf{n}\cdot \mathbf{p}=3$ 的点，例如 $\left[\begin{array}{c}1.5\\ 0\end{array}\right]$。两者平行，距离由 $d/(\pm \Vert \mathbf{n}\Vert )$ 控制。

5. 为什么"线性泛函 $f$ 在紧凸集上的最大值必在极点取到"（定理 16）对线性规划至关重要？

线性规划的可行域通常是 $A\mathbf{x}\le \mathbf{b},\mathbf{x}\ge 0$ 定义的多面体（紧凸集），目标是最大化一个线性泛函。定理 16 保证最优解一定能取在多面体的某个顶点（极点）处，于是只需检查有限个顶点而不必搜索无穷多个可行点——单纯形法的理论根基正来源于此。支撑超平面贴合整条边时（如 8.5 例 3c），最优解有无穷多个，但至少存在一个最优顶点。

6. 两条三次贝塞尔曲线在 ${\mathbf{p}}_3$ 处相接。要达到 $C^1$ 连续，控制点要满足什么条件？与 $G^1$ 的差别在哪？

$C^1$ 要求切向量相等：${\mathbf{y}}^{\prime }(0)={\mathbf{x}}^{\prime }(1)$，由端点切向量公式 $3({\mathbf{p}}_4-{\mathbf{p}}_3)=3({\mathbf{p}}_3-{\mathbf{p}}_2)$，即 ${\mathbf{p}}_3$ 是 $\overline{{\mathbf{p}}_2{\mathbf{p}}_4}$ 的中点。$G^1$ 只要求方向相同：${\mathbf{p}}_4-{\mathbf{p}}_3=k({\mathbf{p}}_3-{\mathbf{p}}_2)$（$k>0$），即 ${\mathbf{p}}_3$ 落在线段 $\overline{{\mathbf{p}}_2{\mathbf{p}}_4}$ 上但不一定是中点。对观察者来说两者的视觉光滑程度通常一样，差别只在切向量的大小（参数化速度）。