19 Adaptive Interpolation, TT-Decomposition and Sparse …
283
Families of basis functions ϕ l, i (x) are generated from the obtained sets of points
using the stretching and shift of the hat function ϕ(x):
ϕ l, i (x) = ϕ
(x − i · h l )
h l
.
For each value l, the functions ϕ l, i (x) form a nodal basis (or Lagrange basis). It
is obvious that
span
ϕ l, i : 1 ≤ i ≤ 2
l
− 1
= ⊕
k≤l
span
ϕ k, i : 1 ≤ i ≤ 2
k
− 1, i odd
.
In the case of a sparse grid (Fig. 19.6b, c), the d-dimensional basis of the level n
is defined as
ϕ l 1 l 2 ...l d ,i 1 i 2 ...i d (x 1 , x 2 , . . . , x d ) =
d
j=1
ϕ l j , i j (x j ),
d
j=1
l j ≤ n + d − 1, 1 ≤ i j ≤ 2
l j − 1, i j odd.
Compared to the full grid (max
l j
≤ n), the sparse grid has a significantly smaller
number of nodes, but at the same time, asymptotically, the interpolation error rises
n
d−1 times.
There is an adaptive version of these grids, where a binary tree is used for structuring. In the classical version, if the investigated function has a non-zero value at
the boundary of the region, then all faces of smaller dimensions are considered. The
adaptive grid is built for each face. It is easy to calculate that for an n-dimensional
region the number of faces of smaller dimension will be 3
n
−1. Given the duplication
of nodes in different grids, in the best case, the number of nodes will be equaled 3
n ,
which indicates the exponential complexity of this approach. An important property
of sparse grids is the flexibility of adaptation: for a small increase in accuracy in
each particular case, there is no need to immediately double the number of nodes, as
would be necessary for the adaptive interpolation algorithm.
Consider examples. Figure 19.7 shows several functions R
2
→ R and the resulting
adaptive grid, and Fig. 19.8 shows the grids for functions R
3
→ R. These figures
show that this approach defines the combinations of parameters that play a significant
role, while the construction of grid does not occur on the entire set, but only on the
subsets corresponding to these combinations.
The calculation of the approximate value of the function at a given point is reduced
to the summation of the basic functions with certain weight coefficients, which
are determined in accordance with the interpolated function. The values of these
weights can be considered as the adaptation criterion, according to which the grid is
compressed.
283
Families of basis functions ϕ l, i (x) are generated from the obtained sets of points
using the stretching and shift of the hat function ϕ(x):
ϕ l, i (x) = ϕ
(x − i · h l )
h l
.
For each value l, the functions ϕ l, i (x) form a nodal basis (or Lagrange basis). It
is obvious that
span
ϕ l, i : 1 ≤ i ≤ 2
l
− 1
= ⊕
k≤l
span
ϕ k, i : 1 ≤ i ≤ 2
k
− 1, i odd
.
In the case of a sparse grid (Fig. 19.6b, c), the d-dimensional basis of the level n
is defined as
ϕ l 1 l 2 ...l d ,i 1 i 2 ...i d (x 1 , x 2 , . . . , x d ) =
d
j=1
ϕ l j , i j (x j ),
d
j=1
l j ≤ n + d − 1, 1 ≤ i j ≤ 2
l j − 1, i j odd.
Compared to the full grid (max
l j
≤ n), the sparse grid has a significantly smaller
number of nodes, but at the same time, asymptotically, the interpolation error rises
n
d−1 times.
There is an adaptive version of these grids, where a binary tree is used for structuring. In the classical version, if the investigated function has a non-zero value at
the boundary of the region, then all faces of smaller dimensions are considered. The
adaptive grid is built for each face. It is easy to calculate that for an n-dimensional
region the number of faces of smaller dimension will be 3
n
−1. Given the duplication
of nodes in different grids, in the best case, the number of nodes will be equaled 3
n ,
which indicates the exponential complexity of this approach. An important property
of sparse grids is the flexibility of adaptation: for a small increase in accuracy in
each particular case, there is no need to immediately double the number of nodes, as
would be necessary for the adaptive interpolation algorithm.
Consider examples. Figure 19.7 shows several functions R
2
→ R and the resulting
adaptive grid, and Fig. 19.8 shows the grids for functions R
3
→ R. These figures
show that this approach defines the combinations of parameters that play a significant
role, while the construction of grid does not occur on the entire set, but only on the
subsets corresponding to these combinations.
The calculation of the approximate value of the function at a given point is reduced
to the summation of the basic functions with certain weight coefficients, which
are determined in accordance with the interpolated function. The values of these
weights can be considered as the adaptation criterion, according to which the grid is
compressed.