稀疏网格
稀疏网格是表示、积分或插值高维函数的数值计算技术。最初是由俄罗斯数学家Sergey A. Smolyak (Lazar Lyusternik的学生)基于稀疏张量积构造发展。高效实现此类网格的计算机算法后来由Michael Griebel和Christoph Zenger 开发。
维度诅咒
表示多维函数的标准方式是采用张量或完全网格。故用于存储、运算的基函数或节点的数量与维数指数增加。即使以今天的计算能力,也不可能处理超过 4 或 5 维的函数。[来源请求]
维度诅咒可以表示为使用 个格点进行 阶积分积分误差。若函数的正则性为 ,即 次可微,维数为 ,则
Smolyak求积法则
Smolyak 发现了基于单变量求积规则 的计算上更为高效的多维函数积分方法。对 维函数 ,Smolyak积分 一个函数的可以写成具有张量积的递归公式:
的下标是离散化的水平,我们不妨令一维 阶的积分要对 个点求值。[1]正则性为 的函数的误差估计是:
延伸阅读
- Brumm, J.; Scheidegger, S. Using Adaptive Sparse Grids to Solve High-Dimensional Dynamic Models. Econometrica. 2017, 85 (5): 1575–1612. doi:10.3982/ECTA12216.
- Garcke, Jochen. Garcke, Jochen; Griebel, Michael , 编. Sparse Grids and Applications (PDF). Springer. 2012: 57–80 [2022-01-07]. ISBN 978-3-642-31702-6. (原始内容 (PDF)存档于2022-01-07).
- Zenger, Christoph. Hackbusch, Wolfgang , 编. Parallel Algorithms for Partial Differential Equations (PDF). Vieweg. 1991: 241–251 [2022-01-07]. ISBN 3-528-07631-3. (原始内容 (PDF)存档于2022-01-22).
外部链接
- 一种用于常规稀疏网格的高效内存数据结构 (页面存档备份,存于互联网档案馆)
- 稀疏网格上的有限差分格式 (页面存档备份,存于互联网档案馆)
- 稀疏网格上的可视化
- 稀疏网格上的数据挖掘,J.Garcke、M.Griebel (pdf) (页面存档备份,存于互联网档案馆)
- ^ Sparse Grid Basics. sparsegrids.org. [2022-01-10]. (原始内容存档于2022-01-10).