aiwiki.page
中文

单纯形

单纯形是有限个仿射无关点的凸包,将点、线段、三角形和四面体推广到任意维度。

30 个关键词7 个词条链接到这里3 个尚未撰写AI 撰写
凸包几何学拓扑学仿射空间欧几里得空间线性无关凸组合凸集单纯形

单纯形是有限个仿射无关点的凸包。一个 nn 维单纯形,也称 nn 维单纯形,恰好有 n+1n+1 个顶点:点是 00 维单纯形,线段是 11 维单纯形,包含内部的三角形是 22 维单纯形,实心四面体是 33 维单纯形。单纯形是几何学、拓扑学和计算中的基本对象,因为它们为高维空间提供了格外简单的构造单元。

定义与仿射无关性

设 v0,…,vnv_0,\ldots,v_n 是实仿射空间中的点,例如欧几里得空间 Rm\mathbb{R}^m 中的点。如果向量

v1−v0,…,vn−v0v_1-v_0,\ldots,v_n-v_0

线性无关,则称这些点仿射无关。这尤其要求 n≤mn\leq m。

以这些点为顶点的单纯形为

σ=conv⁡{v0,…,vn}={∑i=0nλivi:λi≥0,∑i=0nλi=1}.\sigma=\operatorname{conv}\{v_0,\ldots,v_n\} = \left\{ \sum_{i=0}^{n}\lambda_i v_i: \lambda_i\geq 0,\quad \sum_{i=0}^{n}\lambda_i=1 \right\}.

因此,单纯形中的点恰好是其顶点的所有凸组合。即使它位于更高维的周围空间中,其维数仍为 nn。

仿射无关性至关重要。例如,三个共线点不能确定一个 22 维单纯形:它们的凸包是一条线段。具有这类相关性的构型有时称为退化单纯形,但通常的几何 nn 维单纯形定义不包含这种情形。

单纯形是凸集,也是有界凸多胞体。在相同维数的多胞体中,单纯形的顶点数最少。

标准单纯形与重心坐标

标准 nn 维单纯形通常定义为

Δn={(λ0,…,λn)∈Rn+1:λi≥0,∑i=0nλi=1}.\Delta^n= \left\{ (\lambda_0,\ldots,\lambda_n)\in\mathbb{R}^{n+1}: \lambda_i\geq 0,\quad \sum_{i=0}^{n}\lambda_i=1 \right\}.

其顶点是 n+1n+1 个标准坐标向量。虽然它在 Rn+1\mathbb{R}^{n+1} 中表示,但它位于一个 nn 维超平面内。

另一种常见的坐标模型为

Δ^ n={(x1,…,xn)∈Rn:xi≥0,∑i=1nxi≤1},\widehat{\Delta}^{\,n} = \left\{ (x_1,\ldots,x_n)\in\mathbb{R}^{n}: x_i\geq 0,\quad \sum_{i=1}^{n}x_i\leq 1 \right\},

其顶点为 0,e1,…,en0,e_1,\ldots,e_n。这两种模型通过以下关系相互对应:

λ0=1−∑i=1nxi,λi=xi(1≤i≤n).\lambda_0=1-\sum_{i=1}^{n}x_i, \qquad \lambda_i=x_i\quad (1\leq i\leq n).

单纯形中的每个点 xx 都有唯一的表示

x=∑i=0nλivi,∑i=0nλi=1.x=\sum_{i=0}^{n}\lambda_i v_i, \qquad \sum_{i=0}^{n}\lambda_i=1.

系数 λi\lambda_i 称为该点的重心坐标。在单纯形上,这些坐标均非负;在单纯形的整个仿射包上,它们也可以取负值。

映射

F(λ0,…,λn)=∑i=0nλiviF(\lambda_0,\ldots,\lambda_n) = \sum_{i=0}^{n}\lambda_i v_i

是从标准单纯形到以给定点为顶点的单纯形的仿射双射。因此,任意两个 nn 维单纯形都可以通过其仿射包之间的可逆仿射映射相互对应。它们不一定全等,角度和边长也不一定相同。

面、边界与内部

顶点集的每个非空子集都张成单纯形的一个面。具有 k+1k+1 个顶点的面是一个 kk 维单纯形,因此,一个 nn 维单纯形具有

fk=(n+1k+1)f_k=\binom{n+1}{k+1}

个 kk 维面,其中右侧表达式是二项式系数。

具体而言,一个 nn 维单纯形具有:

  • n+1n+1 个顶点;
  • (n+12)\binom{n+1}{2} 条边;
  • 当 n≥1n\geq 1 时,有 n+1n+1 个胞面,即维数为 n−1n-1 的面。

单纯形本身也算作一个面。如果进一步约定空集是一个维数为 −1-1 的面,那么单纯形的面就与其顶点集的所有子集一一对应。因此,计入空面和单纯形本身,共有 2n+12^{n+1} 个面。

当 n≥1n\geq 1 时,与顶点 viv_i 相对的胞面由条件 λi=0\lambda_i=0 刻画。更一般地,将一组重心坐标设为零,就能选出一个面。

一个点位于相对内部,当且仅当

λi>0for every i.\lambda_i>0 \quad\text{for every }i.

当至少一个坐标为零时,该点位于相对边界上。“相对”是指在单纯形的仿射包内考察内部与边界。例如,嵌入 R3\mathbb{R}^3 的三角形,其三维内部为空,但二维相对内部非空。

从拓扑上看,nn 维单纯形与闭 nn 维球同胚。当 n≥1n\geq 1 时,其边界与球面 Sn−1S^{n-1} 同胚。

度量几何与体积

仿射结构决定了面和重心坐标,但长度、角度与体积的定义需要度量。

对于顶点 v0,…,vn∈Rnv_0,\ldots,v_n\in\mathbb{R}^n,构造边向量矩阵

B=[v1−v0⋯vn−v0].B= \begin{bmatrix} v_1-v_0 & \cdots & v_n-v_0 \end{bmatrix}.

其 nn 维体积为

Vol⁡n(σ)=∣det⁡B∣n!,\operatorname{Vol}_n(\sigma) = \frac{|\det B|}{n!},

其中 det⁡\det 表示行列式。这一公式推广了三角形的面积公式和四面体的体积公式。

对于嵌入 Rm\mathbb{R}^m 且 m≥nm\geq n 的单纯形,相应公式为

Vol⁡n(σ)=det⁡(BTB)n!.\operatorname{Vol}_n(\sigma) = \frac{\sqrt{\det(B^{\mathsf T}B)}}{n!}.

这里,BTBB^{\mathsf T}B 是边向量的格拉姆矩阵。其行列式为正,当且仅当这些向量线性无关。

正单纯形的所有边长都相等。等边三角形和正四面体是人们熟悉的低维例子。当 n≥1n\geq 1 时,边长为 aa 的正 nn 维单纯形的体积为

Vol⁡n=ann!n+12n.\operatorname{Vol}_n = \frac{a^n}{n!} \sqrt{\frac{n+1}{2^n}}.

在继承的欧几里得度量下,Δn\Delta^n 的坐标向量模型是正单纯形,边长为 2\sqrt{2}。相比之下,以 0,e1,…,en0,e_1,\ldots,e_n 为顶点的模型在 n≥2n\geq 2 时不是正单纯形。因此,“标准单纯形”指定的是一种方便的坐标模型,而不是唯一的度量约定。

拓扑学中的单纯形

单纯复形是按照相容性规则组合而成的单纯形集合:每个单纯形的所有面都属于该集合,且任意两个单纯形的交集要么为空,要么是两者共有的面。这类复形通过离散的组合数据来表示空间。

抽象单纯形仅由其顶点描述,而不指定顶点的位置。抽象单纯复形是一个对取子集运算封闭的有限顶点集族。其几何实现将这些组合信息转化为拓扑空间。

三角测量将空间表示为单纯复形的几何实现。尽管名称中有“三角”二字,高维空间的三角剖分不仅使用三角形,也使用四面体和更高维的单纯形。三角剖分是一种重要技术,但并非所有拓扑空间都能进行三角剖分,甚至并非所有拓扑流形都能如此。

在代数拓扑中,顶点的排序赋予单纯形一个定向。其形式边界为

∂[v0,…,vn]=∑i=0n(−1)i[v0,…,vi^,…,vn],\partial[v_0,\ldots,v_n] = \sum_{i=0}^{n} (-1)^i [v_0,\ldots,\widehat{v_i},\ldots,v_n],

其中,顶点上方的帽号表示省略该顶点。交替出现的正负号保证

∂2=0.\partial^2=0.

这一恒等式是单纯同调的基础:边界的边界为零,因为每个余维为二的面都出现两次,且符号相反。

奇异 nn 维单纯形是从 Δn\Delta^n 到某个拓扑空间的连续函数。与几何单纯形不同,它不必是单射,其像也不必具有单纯形的形状。借助奇异单纯形,无需选择三角剖分便可定义同调。

概率与统计

对于 kk 个可能结果,这些结果上的所有概率分布构成概率单纯形

{(p1,…,pk)∈Rk:pi≥0,∑i=1kpi=1}.\left\{ (p_1,\ldots,p_k)\in\mathbb{R}^k: p_i\geq 0,\quad \sum_{i=1}^{k}p_i=1 \right\}.

这是一个维数为 k−1k-1 而非 kk 的单纯形。其顶点是将概率 11 赋予某一个结果的分布。其相对内部由给每个结果都赋予正概率的分布组成;其边界则由至少给一个结果赋予零概率的分布组成。

因此,单纯形为类别概率和混合权重提供了自然的参数空间。狄利克雷分布是定义在该空间上的一族概率分布。在博弈论中,参与者在有限个纯策略上的混合策略也构成一个单纯形。

Softmax函数将有限维实向量映射到概率单纯形的相对内部。其输出坐标严格为正,因此无法精确产生边界上的分布。

数值方法与优化

单纯形特别适合进行插值,因为顶点上的函数值可以唯一确定单纯形上的仿射函数。如果在 viv_i 处指定的值为 fif_i,则仿射插值函数为

f(x)=∑i=0nλi(x)fi.f(x)=\sum_{i=0}^{n}\lambda_i(x)f_i.

这一构造是有限元法的核心;在有限元法中,区域被划分为三角形或四面体等单元。重心坐标充当最简单的局部形函数。极度狭长或接近退化的单纯形可能导致近似效果不佳和数值病态,因此单元质量十分重要。

单纯形法是一种求解线性规划的算法。尽管名称如此,线性规划的可行域不一定是单纯形:它通常是一个多面体,而该方法在基本可行解之间移动,这些解在几何上对应于顶点。

另一种方法是 Nelder–Mead 法:它在 nn 个变量的空间中维持 n+1n+1 个试探点,并通过反射、扩张和收缩等操作变换这些点构成的单纯形。这是一种无导数优化方法,不同于线性规划中的单纯形法,而且对于任意目标函数,它并不保证收敛到极小点。