高等数学 / 系统课时

高维积分难题

高维积分难题

本课解释积分维度升高后,为什么规则网格会迅速变得不可计算,以及随机采样如何绕开“每一维都要细分”的成本。完成后,你可以根据维度、精度和函数特征判断应使用网格积分还是采样估计。

学习目标

  • 理解网格积分中的维数灾难
  • 掌握蒙特卡洛积分的基本估计公式
  • 能识别随机采样的优势、限制与适用场景

网格数量为何指数增长

在一维区间上,每个方向取 mm 个网格点只需要 mm 次计算;但在 dd 维空间中,每一维都取 mm 个点,总点数会变成:

Ngrid=mdN_{\text{grid}}=m^d

即使每维只取 100100 个点,计算规模也会快速膨胀:

维度 dd 网格点数 100d100^d
1 10210^2
2 10410^4
5 101010^{10}
10 102010^{20}

这就是维数灾难:分辨率只按每维线性提高,总成本却按维度指数增长。存储、函数求值和遍历时间都会成为瓶颈。

规则网格与随机采样的高维成本对比图

随机采样如何估计积分

设要计算区域 DD 上的积分:

I=∫Df(x) dxI=\int_D f(x)\,\mathrm{d}x

若 DD 具有有限的正体积,ff 可积,并能从该区域独立均匀采样 X1,…,XNX_1,\ldots,X_N,则有

I=Vol⁡(D) E[f(X)]I=\operatorname{Vol}(D)\,E[f(X)]

因此可以用样本平均值估计积分:

I^N=Vol⁡(D)1N∑i=1Nf(Xi)\hat I_N=\operatorname{Vol}(D)\frac{1}{N}\sum_{i=1}^{N}f(X_i)

与网格不同,蒙特卡洛方法只计算实际抽到的 NN 个点,不需要在每个维度上铺满网格。若 f(X)f(X) 的方差有限,估计量的标准误差为 Vol⁡(D)Var⁡(f(X))/N\operatorname{Vol}(D)\sqrt{\operatorname{Var}(f(X))/N}。样本数的指数固定为 −1/2-1/2,但方差、区域体积和单次采样或函数求值的成本仍可能随维度改变。

一个可验证的高维例子

考虑单位立方体 [0,1]d[0,1]^d 上的函数:

f(x1,…,xd)=∑j=1dxjf(x_1,\ldots,x_d)=\sum_{j=1}^d x_j

由于每个坐标在 [0,1][0,1] 上均匀分布时均值为 1/21/2,精确积分为:

I=∫[0,1]d∑j=1dxj dx=d2I=\int_{[0,1]^d}\sum_{j=1}^d x_j\,\mathrm{d}x =\frac{d}{2}

随机采样时,只需生成 NN 个 dd 维样本,计算每个样本坐标和,再取平均。估计量无偏,其标准误差为:

SE⁡(I^N)=d12N\operatorname{SE}(\hat I_N)=\sqrt{\frac{d}{12N}}

例如 d=100d=100、N=106N=10^6 时,标准误差约为 0.00290.0029。规则网格若每维取 100100 个点则需要 1020010^{200} 次函数求值,二者的规模差异已经不是工程优化能够弥补的。

可以用标准库先运行较小的算例,比较样本标准误差和理论值。

python
from math import fsum, sqrt
from random import Random
from statistics import stdev

dimension, sample_count = 20, 50_000
rng = Random(42)
values = [sum(rng.random() for _ in range(dimension))
          for _ in range(sample_count)]
estimate = fsum(values) / sample_count
empirical = stdev(values) / sqrt(sample_count)
theory = sqrt(dimension / (12 * sample_count))

print(f"estimate={estimate:.6f} exact={dimension / 2:.6f}")
print(f"estimated SE={empirical:.6f} theoretical SE={theory:.6f}")

预期输出如下。

text
estimate=10.000291 exact=10.000000
estimated SE=0.005769 theoretical SE=0.005774

这个例子用到了各坐标独立,所以坐标和的方差等于各坐标方差之和。理论标准误差衡量重复独立实验的波动,单次误差可以更小,也可以更大。

随机采样也有代价

蒙特卡洛方法避免了网格点数的指数爆炸,但并不意味着高维问题自动变简单。

  • O(N−1/2)O(N^{-1/2}) 的收敛速度较慢,误差缩小到原来一半通常需要约四倍样本
  • 若函数主要在极小区域取大值,均匀采样可能长期抽不到关键区域
  • 对独立样本,维度升高可能增大被积函数的方差;对依赖样本,还要另外分析样本之间的相关性
  • 复杂区域上的均匀采样本身可能很困难

例如在单位立方体中估计所有坐标都小于 1/21/2 的概率,真实值是 2−d2^{-d}。在 d=100d=100、N=106N=10^6 时,命中次数的期望只有 N2−d≈7.9×10−25N2^{-d}\approx7.9\times10^{-25},几乎肯定一个都抽不到。样本全零时,直接算出的样本方差也是零,但这个结果没有捕捉到稀有事件。

重要性采样、分层采样与控制变量可利用问题结构降低方差。马尔可夫链蒙特卡洛主要用于从难以直接抽样的目标分布获取样本,链上样本通常相关。分析此时的误差时,需要检查链的收敛情况和有效样本量。

如何选择积分方法

场景 更合适的方法 原因
低维、函数平滑、精度要求高 高斯求积或自适应网格 收敛快,可利用函数平滑性
中高维、区域规则、可独立采样 蒙特卡洛积分 成本随样本数增长,不铺满网格
低差异序列可用、函数较平滑 准蒙特卡洛 常比纯随机采样更稳定
概率集中在狭小区域 重要性采样或分层采样 把样本集中到贡献最大的区域

一个实用判断是:当 mdm^d 已超出可承受的函数求值次数时,不应继续增加网格密度,而应转向采样方法或利用问题结构做降维。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

高维积分难题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通