276
A. Yu. Morozov and D. L. Reviznikov
m = 20 the number of nodes in the grid will be about one hundred trillion (≈ 10
14 ).
In particular, a large number of interval parameters appears in such applied problem
as modeling chemical transformations in the presence of uncertainties in the rate
constants of reactions. If we consider the complete kinetic mechanisms in which the
reactions are in the thousands, then we have to deal with the thousand-dimensional
regions of parameter uncertainty, and the use of the adaptive interpolation algorithm,
in this case, becomes impossible.
This situation can be improved by making an assumption that is fully consistent
with reality. In practice, there is rarely a situation where absolutely all parameters individually or in combination have a significant impact on the solution. When
constructing an interpolation polynomial, for example, for a function of two variables:
P(x, y) = a 0,0 + a 1,0 x + a 0,1 y + a 1,1 x y + · · · =
p
i=0
p
j=0
a i, j x
i y
j
.
This means that most of the members a i, j x
i y
j will not make a significant contribution to the result and, therefore, they can be ignored. Therefore, to construct an
interpolation polynomial, it is sufficient to use not all ( p + 1)
2 nodes. There appear a
few questions. Which terms need to be considered? How are the grid nodes selected?
A priori, one cannot answer these questions unequivocally.
19.5 Cross Approximation
Let us consider the Lagrange interpolation polynomial on a regular grid for two
variables. The calculation of the value at a certain point reduces to the elementwise
multiplication of two matrices and the summation of all elements:
P(x, y) = L(x, y) ⊗ F =
p
i=0
p
j=0
l i, j (x, y) f i, j ,
where l i, j (x, y) are the basic Lagrange polynomials, f i, j = f (x i , y j ) are values of
the desired function in grid nodes x i , y j . The main goal is to reduce the number of
calculations of function f .
The assumption made in the previous section essentially means that the rank of
the matrix F may be less than ( p + 1). Assume that the function f has the following
structure:
f (x, y) = u 1 (x)v 1 (y) + u 2 (x)v 2 (y) + · · · + u r (x)v r (y),
then the value matrix F =
f i, j
can be represented as the following decomposition:
A. Yu. Morozov and D. L. Reviznikov
m = 20 the number of nodes in the grid will be about one hundred trillion (≈ 10
14 ).
In particular, a large number of interval parameters appears in such applied problem
as modeling chemical transformations in the presence of uncertainties in the rate
constants of reactions. If we consider the complete kinetic mechanisms in which the
reactions are in the thousands, then we have to deal with the thousand-dimensional
regions of parameter uncertainty, and the use of the adaptive interpolation algorithm,
in this case, becomes impossible.
This situation can be improved by making an assumption that is fully consistent
with reality. In practice, there is rarely a situation where absolutely all parameters individually or in combination have a significant impact on the solution. When
constructing an interpolation polynomial, for example, for a function of two variables:
P(x, y) = a 0,0 + a 1,0 x + a 0,1 y + a 1,1 x y + · · · =
p
i=0
p
j=0
a i, j x
i y
j
.
This means that most of the members a i, j x
i y
j will not make a significant contribution to the result and, therefore, they can be ignored. Therefore, to construct an
interpolation polynomial, it is sufficient to use not all ( p + 1)
2 nodes. There appear a
few questions. Which terms need to be considered? How are the grid nodes selected?
A priori, one cannot answer these questions unequivocally.
19.5 Cross Approximation
Let us consider the Lagrange interpolation polynomial on a regular grid for two
variables. The calculation of the value at a certain point reduces to the elementwise
multiplication of two matrices and the summation of all elements:
P(x, y) = L(x, y) ⊗ F =
p
i=0
p
j=0
l i, j (x, y) f i, j ,
where l i, j (x, y) are the basic Lagrange polynomials, f i, j = f (x i , y j ) are values of
the desired function in grid nodes x i , y j . The main goal is to reduce the number of
calculations of function f .
The assumption made in the previous section essentially means that the rank of
the matrix F may be less than ( p + 1). Assume that the function f has the following
structure:
f (x, y) = u 1 (x)v 1 (y) + u 2 (x)v 2 (y) + · · · + u r (x)v r (y),
then the value matrix F =
f i, j
can be represented as the following decomposition: