单纯形是有限个仿射无关点的凸包。一个 n 维单纯形,也称 n 维单纯形,恰好有 n+1 个顶点:点是 0 维单纯形,线段是 1 维单纯形,包含内部的三角形是 2 维单纯形,实心四面体是 3 维单纯形。单纯形是几何学、拓扑学和计算中的基本对象,因为它们为高维空间提供了格外简单的构造单元。
定义与仿射无关性
设 v0,…,vn 是实仿射空间中的点,例如欧几里得空间 Rm 中的点。如果向量
v1−v0,…,vn−v0
线性无关,则称这些点仿射无关。这尤其要求 n≤m。
以这些点为顶点的单纯形为
σ=conv{v0,…,vn}={i=0∑nλivi:λi≥0,i=0∑nλi=1}.
因此,单纯形中的点恰好是其顶点的所有凸组合。即使它位于更高维的周围空间中,其维数仍为 n。
仿射无关性至关重要。例如,三个共线点不能确定一个 2 维单纯形:它们的凸包是一条线段。具有这类相关性的构型有时称为退化单纯形,但通常的几何 n 维单纯形定义不包含这种情形。
单纯形是凸集,也是有界凸多胞体。在相同维数的多胞体中,单纯形的顶点数最少。
标准单纯形与重心坐标
标准 n 维单纯形通常定义为
Δn={(λ0,…,λn)∈Rn+1:λi≥0,i=0∑nλi=1}.
其顶点是 n+1 个标准坐标向量。虽然它在 Rn+1 中表示,但它位于一个 n 维超平面内。
另一种常见的坐标模型为
Δn={(x1,…,xn)∈Rn:xi≥0,i=1∑nxi≤1},
其顶点为 0,e1,…,en。这两种模型通过以下关系相互对应:
λ0=1−i=1∑nxi,λi=xi(1≤i≤n).
单纯形中的每个点 x 都有唯一的表示
x=i=0∑nλivi,i=0∑nλi=1.
系数 λi 称为该点的重心坐标。在单纯形上,这些坐标均非负;在单纯形的整个仿射包上,它们也可以取负值。
映射
F(λ0,…,λn)=i=0∑nλivi
是从标准单纯形到以给定点为顶点的单纯形的仿射双射。因此,任意两个 n 维单纯形都可以通过其仿射包之间的可逆仿射映射相互对应。它们不一定全等,角度和边长也不一定相同。
面、边界与内部
顶点集的每个非空子集都张成单纯形的一个面。具有 k+1 个顶点的面是一个 k 维单纯形,因此,一个 n 维单纯形具有
fk=(k+1n+1)
个 k 维面,其中右侧表达式是二项式系数。
具体而言,一个 n 维单纯形具有:
- n+1 个顶点;
- (2n+1) 条边;
- 当 n≥1 时,有 n+1 个胞面,即维数为 n−1 的面。
单纯形本身也算作一个面。如果进一步约定空集是一个维数为 −1 的面,那么单纯形的面就与其顶点集的所有子集一一对应。因此,计入空面和单纯形本身,共有 2n+1 个面。
当 n≥1 时,与顶点 vi 相对的胞面由条件 λi=0 刻画。更一般地,将一组重心坐标设为零,就能选出一个面。
一个点位于相对内部,当且仅当
λi>0for every i.
当至少一个坐标为零时,该点位于相对边界上。“相对”是指在单纯形的仿射包内考察内部与边界。例如,嵌入 R3 的三角形,其三维内部为空,但二维相对内部非空。
从拓扑上看,n 维单纯形与闭 n 维球同胚。当 n≥1 时,其边界与球面 Sn−1 同胚。
度量几何与体积
仿射结构决定了面和重心坐标,但长度、角度与体积的定义需要度量。
对于顶点 v0,…,vn∈Rn,构造边向量矩阵
B=[v1−v0⋯vn−v0].
其 n 维体积为
Voln(σ)=n!∣detB∣,
其中 det 表示行列式。这一公式推广了三角形的面积公式和四面体的体积公式。
对于嵌入 Rm 且 m≥n 的单纯形,相应公式为
Voln(σ)=n!det(BTB).
这里,BTB 是边向量的格拉姆矩阵。其行列式为正,当且仅当这些向量线性无关。
正单纯形的所有边长都相等。等边三角形和正四面体是人们熟悉的低维例子。当 n≥1 时,边长为 a 的正 n 维单纯形的体积为
Voln=n!an2nn+1.
在继承的欧几里得度量下,Δn 的坐标向量模型是正单纯形,边长为 2。相比之下,以 0,e1,…,en 为顶点的模型在 n≥2 时不是正单纯形。因此,“标准单纯形”指定的是一种方便的坐标模型,而不是唯一的度量约定。
拓扑学中的单纯形
单纯复形是按照相容性规则组合而成的单纯形集合:每个单纯形的所有面都属于该集合,且任意两个单纯形的交集要么为空,要么是两者共有的面。这类复形通过离散的组合数据来表示空间。
抽象单纯形仅由其顶点描述,而不指定顶点的位置。抽象单纯复形是一个对取子集运算封闭的有限顶点集族。其几何实现将这些组合信息转化为拓扑空间。
三角测量将空间表示为单纯复形的几何实现。尽管名称中有“三角”二字,高维空间的三角剖分不仅使用三角形,也使用四面体和更高维的单纯形。三角剖分是一种重要技术,但并非所有拓扑空间都能进行三角剖分,甚至并非所有拓扑流形都能如此。
在代数拓扑中,顶点的排序赋予单纯形一个定向。其形式边界为
∂[v0,…,vn]=i=0∑n(−1)i[v0,…,vi,…,vn],
其中,顶点上方的帽号表示省略该顶点。交替出现的正负号保证
这一恒等式是单纯同调的基础:边界的边界为零,因为每个余维为二的面都出现两次,且符号相反。
奇异 n 维单纯形是从 Δn 到某个拓扑空间的连续函数。与几何单纯形不同,它不必是单射,其像也不必具有单纯形的形状。借助奇异单纯形,无需选择三角剖分便可定义同调。
概率与统计
对于 k 个可能结果,这些结果上的所有概率分布构成概率单纯形
{(p1,…,pk)∈Rk:pi≥0,i=1∑kpi=1}.
这是一个维数为 k−1 而非 k 的单纯形。其顶点是将概率 1 赋予某一个结果的分布。其相对内部由给每个结果都赋予正概率的分布组成;其边界则由至少给一个结果赋予零概率的分布组成。
因此,单纯形为类别概率和混合权重提供了自然的参数空间。狄利克雷分布是定义在该空间上的一族概率分布。在博弈论中,参与者在有限个纯策略上的混合策略也构成一个单纯形。
Softmax函数将有限维实向量映射到概率单纯形的相对内部。其输出坐标严格为正,因此无法精确产生边界上的分布。
数值方法与优化
单纯形特别适合进行插值,因为顶点上的函数值可以唯一确定单纯形上的仿射函数。如果在 vi 处指定的值为 fi,则仿射插值函数为
f(x)=i=0∑nλi(x)fi.
这一构造是有限元法的核心;在有限元法中,区域被划分为三角形或四面体等单元。重心坐标充当最简单的局部形函数。极度狭长或接近退化的单纯形可能导致近似效果不佳和数值病态,因此单元质量十分重要。
单纯形法是一种求解线性规划的算法。尽管名称如此,线性规划的可行域不一定是单纯形:它通常是一个多面体,而该方法在基本可行解之间移动,这些解在几何上对应于顶点。
另一种方法是 Nelder–Mead 法:它在 n 个变量的空间中维持 n+1 个试探点,并通过反射、扩张和收缩等操作变换这些点构成的单纯形。这是一种无导数优化方法,不同于线性规划中的单纯形法,而且对于任意目标函数,它并不保证收敛到极小点。