稀疏网格

稀疏网格是表示、积分或插值高维函数的数值计算技术。最初是由俄罗斯数学家Sergey A. Smolyak （Lazar Lyusternik的学生）基于稀疏张量积构造发展。高效实现此类网格的计算机算法后来由Michael Griebel和Christoph Zenger 开发。

维度诅咒

表示多维函数的标准方式是采用张量或完全网格。故用于存储、运算的基函数或节点的数量与维数指数增加。即使以今天的计算能力，也不可能处理超过 4 或 5 维的函数。Template:来源请求

维度诅咒可以表示为使用 $N_{l}$ 个格点进行 $l$ 阶积分积分误差。若函数的正则性为 $r$ ，即 $r$ 次可微，维数为 $d$ ，则

$| E_{l} | = O (N_{l}^{- \frac{r}{d}})$

Smolyak 发现了基于单变量求积规则 $Q^{(1)}$ 的计算上更为高效的多维函数积分方法。对 $d$ 维函数 $f$ ，Smolyak积分 $Q^{(d)}$ 一个函数的可以写成具有张量积的递归公式：

$Q_{l}^{(d)} f = (\sum_{i = 1}^{l} (Q_{i}^{(1)} - Q_{i - 1}^{(1)}) \otimes Q_{l - i + 1}^{(d - 1)}) f$

$Q$ 的下标是离散化的水平，我们不妨令一维 $i$ 阶的积分要对 $O (2^{i})$ 个点求值。^[1]正则性为 $r$ 的函数的误差估计是：

$| E_{l} | = O (N_{l}^{- r} {(\log N_{l})}^{(d - 1) (r + 1)})$