274
A. Yu. Morozov and D. L. Reviznikov
System of Eqs. 19.2 can be considered as a function, the input of which is
G
k
0 [i 1 , i 2 , . . . , i m ] and the output is G
k+1
0 [i 1 , i 2 , . . . , i m ].
With G
k+1
0
an interpolation, polynomial P
k+1
x
0
is constructed, for example, in
the form of a Lagrange:
P
k+1
j
x
0
=
p
i 1 ,i 2 ,...,i m =0
L
x
0
[i 1 , i 2 , . . . , i m ] · G
k+1
0 [i 1 , i 2 , . . . , i m , j], j = 1, n,
where L
x
0
is m-dimensional array that consists of the values of the basic Lagrange
polynomials:
L
x
0
[i 1 , i 2 , . . . , i m ] =
p
j=0
m
k=0
i k = j
p
x
0
k − x
0
k
x
0
k − x
0
k
− j
i k − j
.
If the posterior error of interpolation
error = max
x 0 ∈
x 0 , x 0
x
k+1
(x
0
) − P
k+1
(x
0
)
(19.3)
is greater than some given value ε, than G
k
0 is split into two grids G
k
1 and G
k
2 so that
their estimate of the interpolation error is less than error. All the same actions are
performed for them as for the grid G
k
0 , and, if necessary, they are also broken.
As a result, at the time of t k+1 a kd-tree and the corresponding piecewise polynomial function that interpolates the solution with a given accuracy will be obtained.
The process of constructing a kd-tree is illustrated in Fig. 19.1. There is no need to
build a kd-tree from scratch at each step, instead, the tree obtained in the previous
step is used, and depending on the estimate of the interpolation error, it is rebuilt.
The process of crushing vertices always occurs at the previous step (dashed lines),
because, when creating new vertices, the values associated with their nodes are
interpolated, which must be performed at a time when the error is still valid. If the
interpolation error becomes acceptable for the vertex and all its descendants, then
the descendants are deleted, and the vertex itself becomes a leaf.
Assessment in the form of Eq. 19.3 in practice is not performed for all points from
the region of uncertainty, but only for some points. When creating a vertex G
k
0 , a test
set of points is randomly created:
X
k
0 =
x
k
(ˆ x
0
)
ˆ x
0
= rand
x
0
, x 0
.
By analogy with the construction of G
k+1
0 , X
k+1
0
is constructed using X
k
0 by
solving non-interval Cauchy problems similar to Eq. 19.2. The posterior estimate of
the interpolation error takes the following form:
A. Yu. Morozov and D. L. Reviznikov
System of Eqs. 19.2 can be considered as a function, the input of which is
G
k
0 [i 1 , i 2 , . . . , i m ] and the output is G
k+1
0 [i 1 , i 2 , . . . , i m ].
With G
k+1
0
an interpolation, polynomial P
k+1
x
0
is constructed, for example, in
the form of a Lagrange:
P
k+1
j
x
0
=
p
i 1 ,i 2 ,...,i m =0
L
x
0
[i 1 , i 2 , . . . , i m ] · G
k+1
0 [i 1 , i 2 , . . . , i m , j], j = 1, n,
where L
x
0
is m-dimensional array that consists of the values of the basic Lagrange
polynomials:
L
x
0
[i 1 , i 2 , . . . , i m ] =
p
j=0
m
k=0
i k = j
p
x
0
k − x
0
k
x
0
k − x
0
k
− j
i k − j
.
If the posterior error of interpolation
error = max
x 0 ∈
x 0 , x 0
x
k+1
(x
0
) − P
k+1
(x
0
)
(19.3)
is greater than some given value ε, than G
k
0 is split into two grids G
k
1 and G
k
2 so that
their estimate of the interpolation error is less than error. All the same actions are
performed for them as for the grid G
k
0 , and, if necessary, they are also broken.
As a result, at the time of t k+1 a kd-tree and the corresponding piecewise polynomial function that interpolates the solution with a given accuracy will be obtained.
The process of constructing a kd-tree is illustrated in Fig. 19.1. There is no need to
build a kd-tree from scratch at each step, instead, the tree obtained in the previous
step is used, and depending on the estimate of the interpolation error, it is rebuilt.
The process of crushing vertices always occurs at the previous step (dashed lines),
because, when creating new vertices, the values associated with their nodes are
interpolated, which must be performed at a time when the error is still valid. If the
interpolation error becomes acceptable for the vertex and all its descendants, then
the descendants are deleted, and the vertex itself becomes a leaf.
Assessment in the form of Eq. 19.3 in practice is not performed for all points from
the region of uncertainty, but only for some points. When creating a vertex G
k
0 , a test
set of points is randomly created:
X
k
0 =
x
k
(ˆ x
0
)
ˆ x
0
= rand
x
0
, x 0
.
By analogy with the construction of G
k+1
0 , X
k+1
0
is constructed using X
k
0 by
solving non-interval Cauchy problems similar to Eq. 19.2. The posterior estimate of
the interpolation error takes the following form: