单纯形

定义

单纯形是若干仿射无关的点所构成集合的凸包。设 x₀, x₁, …, x_k 是某个欧氏空间中一组仿射无关的点，则称它们张成的 k 维单纯形为满足下列条件的点 x 的集合：$x=\sum_{i=0}^{k}\lambda_i x_i$，其中 $\sum_{i=0}^{k}\lambda_i=1$ 且每个 $\lambda_i\geq 0$^[2]。这些点称为该单纯形的顶点，k 称为它的维数^[3]。

所谓仿射无关，是指这些点不全部落在任何一张低维平面上，例如平面上 3 个点不能共线，空间中 4 个点不能共面^[4]。按维数递增，单纯形依次为点、线段、三角形、四面体等；一个 k 维单纯形恰好有 k+1 个顶点^[1]。如果所有棱长相等，则称之为正单纯形^[1]。

顶点集的任意非空子集都张成原单纯形的一个低维子单纯形，称为这个单纯形的面^[5]。一个 n 维单纯形中维数为 i 的面共有 $\binom{n+1}{i+1}$ 个，全部真面的总数则为 $2^{n+1}-1$^[6]。只含一个顶点的面即顶点本身，顶点集去掉某一点所得的面称为该顶点对面的面^[5]。整个单纯形有时也被视为它自身的面^[3]。

原理

单纯形内部每一点的坐标可以用重心坐标唯一刻画。对顶点 $x_0,\dots,x_k$，系数 $\lambda_0,\dots,\lambda_k$ 之和恒为 1，因此它们只由点本身决定，与坐标系原点的选取无关^[7]。重心坐标的正负可以判断位置：全部为正的点在单纯形内部，出现负值说明该点落在单纯形之外^[7]。当各顶点权重相等、均取 $1/(k+1)$ 时，对应的点就是单纯形的重心。

重心坐标在低维下有直观的比式解释：一维时它是长度之比，二维时是面积之比，三维时是体积之比，更高维时对应超体积之比^[7]。例如平面上三角形内一点 P 关于顶点 V₁ 的坐标，等于三角形 (P, V₂, V₃) 的面积与整个三角形面积之比^[8]。这组系数之和恒等于 1，因此也常被称为单位分解^[7]。

单纯形内每一点都恰好落在某一个面的内部，面的相交与包含关系与顶点集合的集合运算完全对应^[4]。把许多单纯形按规则粘合起来，就得到单纯复形：其中一个单纯形的所有面也必须属于该复形，且任意两个单纯形的交集要么为空，要么是它们共同的面^[9]。这种粘合规则保证构件既不缺面，也不相互穿插^[10]。

发展历程

三角形的重心坐标概念由德国数学家莫比乌斯于 1827 年引入，为把点表示成顶点凸组合提供了工具^[8]。此后重心坐标被推广到任意维数的单纯形，成为研究高维几何的通用语言^[7]。

20 世纪，单纯形被系统地用于代数拓扑。把拓扑对象剖分成若干小单纯形，要求相邻两块相交的部分仍是单纯形，这种做法称为单纯剖分，曲面情形即三角剖分。剖分是构造欧拉示性数等同调论不变量、研究同调群的基础手段，单纯形由此从图形概念发展为拓扑学的基本构件。

同一时期，单纯形的“顶点寻优”思路被引入线性规划的求解。由于线性规划若存在最优解，必定可以从可行域的凸多面体顶点中找到，于是产生了沿顶点迭代的算法，并因此得名为单纯形法^[11]。20 世纪后半叶，单纯形又成为有限元分析赖以建立的基础单元之一^[12]。

应用

在代数拓扑中，单纯形用于对空间作剖分，把连续对象转化为有限组合结构，从而计算欧拉示性数、同调群等不变量。欧拉示性数可写成各维单纯形数目的交错和，即由各维单纯形个数带正负号相加得到，其结果与剖分方式无关。

在有限元分析中，若求解区域被剖分为 d 维单纯形，相应的单元称为单纯形单元，二维为三角形单元，三维为四面体单元^[12]。单元上的插值函数通常用重心坐标表达，其形函数本身即为重心坐标函数，满足值在顶点处为 1 或 0 的条件^[7]。用一次多项式时自由度取在顶点上，所得近似函数在整个区域上连续^[12]。

在计算几何与计算机图形学中，单纯形是多面体建模与插值的载体。Delaunay 三角剖分把点集的凸包分解为单纯的四面体复合形，它与 Voronoi 图互为对偶，用于空间分区和点定位^[9]。三角形也是目前可由计算机硬件直接绘制的表面图形，许多表面模型因此采用三角网格表示^[9]。重心坐标的插值公式还被用于色彩空间转换等需要在一小块区域内混合多个顶点值的场合^[13]。

在线性规划中，单纯形与算法同名的几何背景在于可行域为凸多面体，最优解可在顶点处达到^[11]。非线性规划的单纯形法则借用顶点寻优的思路：先构造一个含 n+1 个顶点的单纯形，比较各顶点函数值，去掉最坏点并代以新点，逐步构成新的单纯形以逼近最优点^[11]。

局限

单纯形的定义依赖顶点仿射无关，一旦顶点退化，重心坐标就不再唯一。平面上 3 点共线时，定义矩阵奇异、三角形面积为零，直线之外的任何点都无法获得唯一坐标^[7]。因此单纯形只适用于非退化构型。

以单纯形为单元的剖分要求较严。用单纯形拼接时必须遵守向下闭合与整洁相交两条规则，否则得到的集合不是单纯复形，无法进行组合分析^[10]。在有边曲面的剖分中，一条边至多属于两个三角形，顶点附近的三角形须按顺序排成链或圈；不满足这些条件的复形不构成曲面^[14]。用单纯形逼近光滑曲面时，逼近精度受单元尺寸限制，网格越粗描述越失真。

在数值计算方面，单纯形法的迭代次数在最坏情况下可能随问题规模指数增长，因此它虽然是历史上求解线性规划最常用的算法，其理论复杂度并不理想^[15]。此外，单纯形只有顶点与面这类线性结构，本身不能直接表达曲率等光滑性质，超出其对简单多面体的适用范围。

参见

• 单纯复形 —— 由若干单纯形按公共面粘合而成的组合结构。

• 重心坐标 —— 用顶点权重之和为 1 的方式描述单纯形内点的位置。

• 单纯形法 —— 借用凸多面体顶点寻优思路求解线性规划的算法。

• 三角剖分 —— 把曲面分解为三角形单纯形的做法。

• 有限元分析 —— 以单纯形作为基本单元求解偏微分方程的数值方法。

• 欧拉示性数 —— 由各维单纯形数目交错求和得到的拓扑不变量。