稀疏网格

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

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

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

|E_l| = O(N_l^{-\frac{r}{d}})

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

Q_l^{(d)} f = \left(\sum_{i=1}^l \left(Q_i^{(1)}-Q_{i-1}^{(1)}\right)\otimes Q_{l-i+1}^{(d-1)}\right)f

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

|E_l| = O\left(N_l^{-r}\left(\log N_l\right)^{(d-1)(r+1)}\right)