查看“︁稀疏网格”︁的源代码

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

== 维度诅咒 ==
表示多维函数的标准方式是采用张量或完全网格。故用于存储、运算的基函数或节点的数量与维数[[指数 (统计学)|指数]]增加。即使以今天的计算能力，也不可能处理超过 4 或 5 维的函数。{{来源请求||time=2022-01-07}}

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

<math>|E_l| = O(N_l^{-\frac{r}{d}})</math>

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

<math>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</math>

<math>Q</math>的下标是离散化的水平，我们不妨令一维<math>i</math>阶的积分要对<math>O(2^{i})</math>个点求值。<ref>{{cite web |title=Sparse Grid Basics |url=https://sparsegrids.org/basics/ |website=sparsegrids.org |accessdate=2022-01-10 |archive-date=2022-01-10 |archive-url=https://web.archive.org/web/20220110175321/https://sparsegrids.org/basics/ }}</ref>正则性为<math>r</math>的函数的误差估计是：

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

== 延伸阅读 ==

* {{Cite journal|title=Using Adaptive Sparse Grids to Solve High-Dimensional Dynamic Models|last=Brumm|first=J.|last2=Scheidegger|first2=S.|journal=[[Econometrica]]|issue=5|doi=10.3982/ECTA12216|year=2017|volume=85|pages=1575–1612}}
* {{Cite book|url=https://ins.uni-bonn.de/media/public/publication-media/sparse_grids_nutshell_code.pdf|first=Jochen|last=Garcke|title=Sparse Grids and Applications|editor-last=Garcke|editor-first=Jochen|editor2-last=Griebel|editor2-first=Michael|editor2-link=Michael Griebel|publisher=Springer|isbn=978-3-642-31702-6|year=2012|pages=57–80|access-date=2022-01-07|archive-date=2022-01-07|archive-url=https://web.archive.org/web/20220107061700/https://ins.uni-bonn.de/media/public/publication-media/sparse_grids_nutshell_code.pdf}}
* {{Cite book|url=https://www5.in.tum.de/pub/zenger91sg.pdf|first=Christoph|last=Zenger|title=Parallel Algorithms for Partial Differential Equations|editor-first=Wolfgang|editor-last=Hackbusch|location=|publisher=Vieweg|year=1991|pages=241–251|isbn=3-528-07631-3|access-date=2022-01-07|archive-date=2022-01-22|archive-url=https://web.archive.org/web/20220122112208/https://www5.in.tum.de/pub/zenger91sg.pdf}}

== 外部链接 ==

* [http://www.lrr.in.tum.de/~murarasu/ppopp027s-murarasu.pdf 一种用于常规稀疏网格的高效内存数据结构] {{Wayback|url=http://www.lrr.in.tum.de/~murarasu/ppopp027s-murarasu.pdf |date=20110719100339 }}
* [http://wissrech.iam.uni-bonn.de/research/projects/zumbusch/fd.html 稀疏网格上的有限差分格式] {{Wayback|url=http://wissrech.iam.uni-bonn.de/research/projects/zumbusch/fd.html |date=20170612142454 }}
* [https://web.archive.org/web/20120219044130/http://cumbia.informatik.uni-stuttgart.de/ger/research/fields/recent/sparse/ 稀疏网格上的可视化]
* [http://wissrech.iam.uni-bonn.de/research/pub/garcke/kdd.pdf 稀疏网格上的数据挖掘，J.Garcke、M.Griebel (pdf)] {{Wayback|url=http://wissrech.iam.uni-bonn.de/research/pub/garcke/kdd.pdf |date=20170808140438 }}
[[Category:数值分析]]