Editing Sparse grid (section)

== Smolyak's quadrature rule ==
Smolyak found a computationally more efficient method of integrating multidimensional functions based on a [[univariate]] quadrature rule <math>Q^{(1)}</math>. The <math>d</math>-dimensional Smolyak integral <math>Q^{(d)}</math> of a function <math>f</math> can be written as a recursion formula with the [[tensor product]].

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

The index to <math>Q</math> is the level of the [[discretization]]. If a 1-dimension integration on level <math>i</math> is computed by the evaluation of <math>O(2^{i})</math> points, the error estimate for a function of regularity <math>r</math> will be
<math>|E_l| = O\left(N_l^{-r}\left(\log N_l\right)^{(d-1)(r+1)}\right)</math>