On Adaptive Grid Approximations in the Weight Norm
YURI K.DEM'YANOVICH
Parallel Algorithm Department,
Saint Petersburg State University,
Universitetskaya nab.,7/9, Saint Petersburg,
RUSSIA
Abstract: - The purpose of this paper is to develop an algorithm construction of adaptive variation-grid methods
for classes of one-dimensional boundary value problems of the second order. Classes of non-degenerate
problems are considered, as well as classes of problems with weak and strong degeneracy. The results obtained
are suitable for learning computer systems designed to solve problems of the aforementioned classes. To
achieve the set goals, the corresponding approximation theorems are established with degeneration. Ways of
adaptive choice approximation space at a variation-grid method in a one-dimensional boundary value problem
are considered. The locality of the approximation is substantially used. The considerations are reduced to an
iterative process, while building an adaptive grid. Numerical examples illustrating the effectiveness of the
proposed approach are given.
Key-Words: - adaptive approximation, artificial intelligence, mathematical physics, numerical calculations
Received: September 29, 2022. Revised: October 31, 2022. Accepted: November 11, 2022. Published: December 12, 2022.
1 Introduction
Research in the field of artificial intelligence is
widespread and covers many areas of the
development of science and practice. These studies
make it possible, to a certain extent, to optimize
efforts aimed at the effective solution of urgent and
difficult problems that require the resources of
powerful computer systems. Let us give an example
of some studies in the mentioned area.
The authors in [1] predict the future of
excitation energy transfer with artificial
intelligence-based quantum dynamics.
In [2], the authors propose a distributed
approximate Newton-type algorithm with a fast
convergence rate for communication-efficient
federated edge learning.
The authors of [3] show that pool-based active
classification can be improved.
The technological troubles with the design of
Processing-in-Memory are discussed in [4].
In [5], the authors propose a new algorithm of
machine learning techniques. The mentioned
algorithm has less complexity than known machine
learning algorithms.
Based on the recent advancements in music
structure analysis, the authors of [6] automate the
evaluation process by introducing a collection of
metrics that can objectively describe structural
properties of the music signal.
The development of a disagreement-based
online learning algorithm is given in [7].
In [8], the authors first construct a graph-based
network model as well as a Poisson process-based
traffic model in the context of 5G mobile
networks.
In [9], the authors develop a deep learning-based
approach to model and predict the designers'
sequential decisions in the systems design context.
Everyone knows the computational difficulties of
solving problems of mathematical physics. These
difficulties are overcome with the sophisticated
use of additional information about the tasks under
consideration.
Let us mention some works in which it is
possible to effectively use learning systems and
the means of artificial intelligence.
The article [10] is devoted to the solution of the
nonstationary integro-differential equation with a
degenerate elliptic differential operator. The
Galerkin method with cubic spline wavelets is
employed for spatial discretization combined with
the Crank-Nicolson scheme and Richardson
extrapolation for time discretization.
It seems that adaptive methods developed
with the help of artificial intelligence greatly
simplify the solution of problems of mathematical
physics. Such problems are considered in a large
number of papers.
The authors in [11] investigate the approximate
solution to a nonlinear Volterra integro-differential
equation in the complex plane by applying the
iterative method in each iteration.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.92
Yuri K. Dem'yanovich
E-ISSN: 2224-2880
801
Volume 21, 2022
In [12], the authors proposed a highly efficient
and accurate collocation method based on the Haar
wavelet for the parameter identification in
multidimensional hyperbolic partial differential
equations. It can also be assumed that the
mentioned means would be useful in solving the
problems considered in the works, [13] and [14].
Computational stability issues are investigated in
[15]. A comprehensive study of the approximation
in variational grid methods in the case of uniform
grids, is given in the monograph, [16]. A
generation to irregular grids is available, [17].
As can be seen from the previous discussion,
the problem of building an adaptive algorithm in
classes of boundary value problems is very
relevant. The relevance of this approach is
determined by two circumstances. On the one hand,
the properties of the solutions to the boundary value
problems are investigated in many problems. On
the other hand, trainable computer systems
(artificial intelligence) have been developed.
These achievements give hope for a significant
increase in the efficiency of the numerical solution
of boundary value problems.
The purpose of this paper is to develop an
algorithm construction of adaptive - variation grid
methods for classes of one-dimensional boundary
value problems of the second order. Classes of non-
degenerate problems are considered, as well as
classes of problems with weak and strong
degeneracy. The results obtained are suitable for
learning computer systems designed to solve the
problems of the mentioned classes.
Thus this work is aimed at developing
adaptive approximations suitable for teaching
intelligent computer systems. In this paper, the
adaptive approximations are applied to variation-
grid methods in a one-dimensional boundary
problem. The basis of this study is the works of S.G.
Mikhlin which are related to the variation-grid
method for an one-dimensional boundary problem
with degeneration (see [16]). In this study, we
consider an adaptive choice of the approximation
space when certain information of the behavior of
the solution of the mentioned problem is available.
The results of this work are adaptive
numerical methods suitable for the teaching of
intellectual computer systems using representatives
of the class of the mentioned problems. This work
makes it possible to train a computer system using
a set of problems with a known exact or
approximate solution. Numerical examples
illustrating the effectiveness of the proposed
approaches are given at the end of this paper.
2 Background
This paragraph provides the necessary information
about a boundary value problem with degeneracy
for an ordinary differential equation. Here are the
results obtained by Professor S.G. Mikhlin, [16].
Consider the differential equation
where , , and the function
is measurable and limited. Suppose
for .
When setting the boundary value problem for
equation (1), we will distinguish the following
cases.
1. The function at point is nonzero,,
2. The function at the point is equal to
zero,
In the second case, one has to consider (see [16])
three subcases.
2a. Integral over interval of the function
converges at point ,
2b. The integral of function diverges,
but the integral of function x
converges. In other words, the relations
2c. Integral over interval of the function
x diverges at point ,
In cases 1. and 2a. (see formulas (2) -- (4))
we add the boundary conditions
to equation (1).
In cases 2b. and 2c. (see formulas (5) -- (6)) we
will assume that . In these
cases, we add the boundary condition
(8)
to equation (1).
Under these conditions, we can assume that
the problems under consideration have the form
, where , operator acts in the space
and it is extended to a positive-definite
self-adjoint operator. Hence it follows that the
solution of the problem lies in the space
. The approximate solution of the problem
is the solution of the problem to a minimum of
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.92
Yuri K. Dem'yanovich
E-ISSN: 2224-2880
802
Volume 21, 2022
energy functional on a suitable subspace
of the energy space :
where
The inequality
follows from (9) - (10). Relation (11) is usually
used to obtain estimates of the convergence rate
for the method (see, for example, [17]).
In this paper, inequality (11) is used for the
adaptive approximation. The last one reduces to a
suitable choice of subspaces . Here the simplest
variants of subspaces, namely, spaces of
piecewise linear continuous functions are
considered.
For what follows, we need the estimates’
approximations in the spaces with a weighted norm.
3 Approximation Estimates
Let be an element of the space . Let's put
.
Lemma 1. The following statements are true.
1. For the function , ,
a representation
is true. For the function , , the
formula
is valid.
Proof. 1. Writing the left side of formula (12),
using the Leibniz formula, we have
To prove formula (12), it remains to take out the
multiplier from the brackets and combine
the difference of the derivatives using the double
integral indicated on the right side formulas (12).
2. Formula (13) is obtained from formula (12) by
applying the Leibniz formula for the difference
,.
This concludes the proof.
Lemma 2. For , , ,
the inequality
|
2
d (14)
is correct.
Proof. The following chain of relations is obvious
This concludes the proof.
Lemma 3. If , , and
, then we have the estimate
Proof. Under the assumptions of the lemma, the
function is continuous. We use relation (12)
and inequality (14). As a result, we arrive at
estimate (15). This completes the proof.
Corollary 1. Under the conditions of Lemma 3
-estimate
||u - |
is valid.
The proof is obtained by squaring the relation
(15) and integrating the result over the interval
.
4 Approximation Estimates
Theorem 1. If
(c,d) then the inequality
||qu-
(16)
is correct.
Proof. We introduce the notation
I= ||qu-
. (17)
In accordance with formula (13), for (17) we have
Using the Cauchy-Bunyakovsky inequality, we
obtain
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.92
Yuri K. Dem'yanovich
E-ISSN: 2224-2880
803
Volume 21, 2022
Simple calculations give
For from (19) - (20) we have
Now from (18) with the help of (21) we obtain
This concludes the proof.
Theorem 2. If
then the inequality
is fulfilled.
Proof. It is easy to see that the relation
(x)=(d-c
holds.
Let's put
Because the
then for from (24) we have
So
From formulas (23) - (25) we obtain
Relation (26) is equivalent to inequality (22).
This concludes the proof.
5 Approximation Estimates without
Degeneracy
Consider problem (1), (7), assuming that
condition (2) is fulfilled.
Here we confine ourselves to the case =0.
In the future, the solution of the problems under
consideration will be denoted with .
Let's introduce a grid
Let be the space of the splines of the
first degree, whose coordinate splines are the
continuous functions ,
for
for
for (28)
where In this way
Theorem 3. Let be an element of the space
, and is an interpolant for
function given by the formula
Then the inequality
is right.
Proof. Consider . Taking into account
the ratio
we have
. (32)
Using relations (22) in formula (32), we obtain inequality
(31). This concludes the proof.
6 Approximation Estimate in a
Problem with Weak Degeneracy
Consider the solution of problem (1), (7) under
conditions (3) -- (4). Here we use the
approximation defined by formulas (27) - (29).
The difference from the previous point is that in
this case the solution belongs to spaces
. In view of this,
the estimate changes on the interval .
Lemma 4. An inequality
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.92
Yuri K. Dem'yanovich
E-ISSN: 2224-2880
804
Volume 21, 2022
is correct.
Proof. Introduce the notation
The inequalities are obvious
Using the ratio
from inequality (37) we have
Taking into account formulas (34) - (38) and the
obvious inequality we obtain
relation (33). This completes the proof.
Theorem 4. Let be the solution to problem
(1), (7) under conditions (3) -- (4). Let be an
interpolant for the function , given by formula
(30). Then the inequality
Iu-
is correct.
The proof of this theorem differs from the
proof of Theorem 3 only by the summand
corresponding to the index . For the above
term, estimate (33) should be applied, and found in
Lemma 4. As a result, we obtain inequality (39).
7 Approximation Estimate in a
Problem with Strong Degeneracy
In the case of strong degeneracy, consider problem
(1), (8) under conditions (3), (5), assuming that
. Because of this
assumption the operator of the problem under
consideration is a positive definite operator. The
difference from the previous point is that in this
case, the solution of the problem under
consideration belongs to spaces
(a+,b)
, where
is
the subspace of space
consisting of
functions which equal to zero for . In view
of this, as an approximation, S.G. Mikhlin proposed
(see [16]) to take a piecewise linear approximation,
which is equal to a constant on the interval .
Theorem 5. Let be the solution problem (1),
(7) under conditions (3), (5). If
for
for
then the inequality
Iu-
is fulfilled.
Proof. Consider I u-. We have
Iu-
For the first term in (41) we use the obvious
inequality
So
The second term in (41) is estimated in the same
way as in Theorems 3 and 4,
Finally, when estimating the third term on the
right side of formula (41), we use inequality (16).
As a result we get
1
Adding relations (43) and (44), we find
1
Adding inequality (42) to inequality (45), we
arrive at relation (40).
This concludes the proof.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.92
Yuri K. Dem'yanovich
E-ISSN: 2224-2880
805
Volume 21, 2022
8 Choosing an Adaptive Grid
For the fixed a and M N, M >1, consider the
set K= K() of grids of the form
On set K, consider the function y of the
form
y
where the functions are defined and
differentiable on the set
.
Let us discuss the conditions
(B)
and for a fixed the functions
,are continuous in the set of variables ,
and for fixed are strictly monotone
decreasing if , .
In addition, it is assumed that
Consider the conditions under which the
mentioned derivatives are equal to zero. So we
are interested in the situation when the relations
are right.
Theorem 6. If conditions (B) are fulfilled (see
formulas (46) -- (49)), then the following
properties hold.
1. For any there are numbers
,
such that for
the relations
(50) turn into true equalities. Numbers
are
determined uniquely by the given and can
be treated as functions of the argument ,
, j=2,3,… ,M. Wherein
2. The functions
depend
continuously on .
3. As the functions
tend to , keeping relations (51).
4. For the functions
tend to , keeping relation (51).
Proof. 1. Let us fix . In view of the
(B) conditions, we have
We suppose increase from to .
Due to the same conditions, the value
increases monotonically from 0 to . Therefore,
there is a value
that satisfies the relation
Similarly, we conclude that there is
such that
for
formula (50), written for
, turns into the correct equality.
Continuing this process, successive enumeration
of relations (50) uniquely define the values
,
Thus,
can be considered as
single-valued argument functions of
,
, , so relation (50) holds.
Item 1 of the lemma to be proved is established.
It remains to note that the continuity of the
functions
follows from the implicit
function theorem, and points 3, 4 are obvious
consequences of conditions (B).
Lemma 5. Whatever the number a
unique point of the form
exists in set with
properties
Proof. Of the above properties 1 - 4 it follows
that the monotonic increase of from to +
leads to a monotonic increase in within the same
limits.
Thus, there is a unique value
, where
. In this case, we set
,
,
, so relation (52) is fulfilled.
This concludes the proof.
Consider the set of vectors
satisfying ratios
Obviously, is an open set in the Euclidean
space .
The right-hand sides of estimates (31), (39), and
(40) are functions of the form
satisfying the (B) condition.
Taking into account their dependence on and
, we introduce a common designation
=
Note the following obvious property of the function
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.92
Yuri K. Dem'yanovich
E-ISSN: 2224-2880
806
Volume 21, 2022
Theorem 7. The functionis positive
on set , it has a unique critical point in this set,
and at this point the function reaches
its minimum.
The proof follows from Lemma 5 for
Theorem 8. For the right-hand side of each of the
estimates (31), (39) and (40) for a fixed
(>, is fixed) there is a unique set of nodes
, for which the right side
takes the minimum value. This set of nodes is the
only critical point on the right side.
The proof is a direct consequence of Theorem 7.
9 On the Choice of Grid in the Case of
Strong Degeneracy
We use estimate (40). Let's put
+
()
(57)
(58)
Without loss of generality, we will assume that the
integrands functions in relations (57) - (58) are
extended to positive constants, so that
the conditions (B) are satisfied.
An example of problem (1), (8) is the problem
(see [16])
,
where .
The solution to problem (59) -- (60) is function
(61)
Taking into account (61) we have (58) in the
form
+
(62)
Consider the case =1. Formula (62) takes the
form
. (63)
We introduce the notation , ,
. By (63) equations (50) can be represented in
the form
where and are known values, <y, and is
the desired unknown, . The obvious root of
the equation is , but this solution should be
excluded, since the condition is not satisfied.
Using elementary transformations, we eliminate
the factor and from equation (64) we pass to
the cubic equation
+
Setting the numbers x and y and solving
equation (65), we find the solution . Then
we solve equation (65) for x and y . As a
result, we find . The process can be stopped
when the end of the interval is reached . The
resulting number of nodes on the mentioned
interval may not satisfy the user. In this case
calculations should be repeated with the changed
value of the number ,
10 Numerical Experiment Results
For a numerical experiment, the problem was
considered with strong degeneracy, namely,
problem (59) - (60) for , :
.
The problem was solved with the variation-grid
method described above.
To determine the grid, we set in equation
(65) and use it in the recurrent process mentioned
above.
The initial data for this process are ,
. The results are shown in
Table 1.
The problem represented by an illustrative
example of the previous point, was solved on an HP
27 p251ur computer using the system Maple
2017.0 with .
For values the accuracy
achieved was of the order of , ,
respectively. On a uniform grid with the same
number of nodes, known calculations (see [16]) in
some cases gave less accurate results (see Table 1).
Although the comparison seems difficult
because of the differences in the types of
computers used to (calculations presented in [16]
carried out at BESM-6). Control calculations using
the same program Maple 2021.1 systems gave the
same result.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.92
Yuri K. Dem'yanovich
E-ISSN: 2224-2880
807
Volume 21, 2022
The computation time using the proposed
algorithm was 92 seconds.
Table 1. Calculation Error
No.
Value of
argument
Error
at BESM-6
Error
Maple-2021
1.
0.0
0.20
2.94
2.
0.1
0.18
2.01
3.
0.2
0.13
1.41
4.
0.3
0.87
1.13
5.
0.4
0.65
1.03
6.
0.5
0.48
9.33
7.
0.6
0.34
7.67
8.
0.7
0.23
7.67
9.
0.8
0.14
7.05
10.
0.9
0.67
7.30
11 Conclusion
It is widely known that the numerical solutions of
problems of mathematical physics have many
difficulties. These difficulties are associated with
the constant expansion of the set of such tasks. In
addition, the requirements to the accuracy of the
numerical solutions increase constantly. Using priori
information on such problems, we divide their
set into classes of tasks. Its circumstance allows
the use of trained computer systems for the
effective solution of problems. As you know, the
training of a computer system is carried out on
several problems of this class with a known
solution. The result of learning is determination of
the parameters of the adaptive method. Since the
solution of problems of mathematical physics is
often carried out at various grid methods (FEM,
finite difference method), the natural parameters of
these methods are grid knots. The adaptive choice
of knots seems to be very important in the case of
problems with particular features of the solution.
Mortgaged into the system, the method uses a priori
information about solution properties for adaptive
positioning of grid knots.
Note that in most complex computational
problems the desired function has regions of fast
and slow changes (in tasks related to earthquakes,
tsunamis, weapons tests, etc.) The approximation
of the desired function using a grid method on an
adaptive non-uniform grid wins significantly when
compared to its approximation on a uniform grid
(see, for example, Table 1).
In areas of rapid change function, the grid
should be dense, and in areas of slow change, a
sparse mesh can be used. Training a computer
system based on available information about the
decision makes it possible to indicate the mentioned
areas. For this, goals require approximation
estimates with known constants (see, for example,
the theorems of this paper). In practice, we have to
solve many similar problems. In this case, the
training of the computer system is carried out on
several problems of this type with a known
decision. The result is an averaged adaptive mesh,
which can be used in the future for other tasks of
the mentioned type.
In this work, this approach is implemented in
the case of the variation-grid method for a boundary
value problem in the one-dimensional differential
equation of the second order. Numerical results of
computer implementation of such an approach are
done.
In the future, it is planned to use this approach
for more complex boundary problems. The
perceived difficulties are of a technical nature. One
of these difficulties is that the process of learning
a computer system requires significant time
resources. However, this should not stop research
of this kind, because the power of the emerging
computing systems are growing exponentially.
Acknowledgment:
The author is highly grateful and indebted to St.
Petersburg University for financial supporting the
preparation of this paper (Pure ID 93852135,
92424538).
References:
[1] Ullah, A., Dral, P.O. ``Predicting the future of
excitation energy transfer in light-harvesting
complex with artificial intelligence-based
quantum dynamics'', Nature
Communications 13(1),pp.1930, 2022.
[2] Dinh, C.T., Tran, N.H., Nguyen, T.D., (...),
Zhou, B.B., Zomaya, A.Y.``DONE:
Distributed Approximate Newton-type
Method for Federated Edge Learning'',
IEEE Transactions on Parallel and Distributed
Systems 33(11), pp. 2648-2660, 2022.
[3] Puchkin, N., Zhivotovskiy, N. ``Exponential
Savings in Agnostic Active Learning
Through Abstention'', IEEE Transactions on
Information Theory 68(7), pp. 4651-4665,
2022.
[4] Han, W., Heo, J., Kim, J., Lim, S., Kim, J.-Y.
`Design of Processing-in-Memory With Triple
Computational Path and Sparsity Handling for
Energy-Efficient DNN Training'', IEEE
Journal on Emerging and Selected Topics in
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.92
Yuri K. Dem'yanovich
E-ISSN: 2224-2880
808
Volume 21, 2022
Circuits and Systems 12(2), pp. 354-366,
2022.
[5] Jiao, Y., Gu, Y. ``Communication-Efficient
Decentralized Subspace Estimation'', IEEE
Journal on Selected Topics in Signal
Processing 16(3), pp. 516-531, 2022.
[6] De Berardinis, J., Cangelosi, A., Coutinho, E.
`Measuring the Structural Complexity of
Music: From Structural Segmentations to
the Automatic Evaluation of Models for
Music Generation'', IEEE/ACM
Transactions on Audio Speech and
Language Processing 30, pp. 1963-1976,
2022.
[7] Huang,B., Salgia,S., Zhao,Q. `Disagree-
ment-Based Active Learning in Online
Settings'',IEEE Transactions on Signal
Processing 70, pp. 1947-1958, 2022.
[8] Yuan, X., Yao, H., Wang, J., Mai, T.,
Guizani, M.Artificial. ``Intelligence
Empowered QoS-Oriented Network
Association for Next-Generation Mobile
Networks'', IEEE Transactions on Cognitive
Communications and Networking 7(3), pp.
856-870, 2021.
[9] Rahman, M.H., Xie, C., Sha, Z.
``Predicting sequential design decisions using
the function-behavior-structure design
process model and recurrent neural networks'',
Journal of Mechanical Design, Transactions
of the ASME 143(8),081706, 2022.
[10] Cern, D. Wavelet Method for Sensitivity
Analysis of European Options under Merton
Jump-Diffusion Model AIP Conference
Proceedings 2425,110004, 2022.
[11] Erfanian, M., Zeidabadi, H. Solving of
Nonlinear Volterra Integro-Differential
Equations in the Complex Plane with Periodic
Quasi-wavelets, International Journal of
Applied and Computational Mathematics
7(6),221, 2021.
[12] Priyadarshi, G., Rathish Kumar, B.V.
Parameter identification in multidimensional
hyperbolic partial differential equations using
wavelet collocation method Mathematical
Methods in the Applied Sciences 44(11),
9079-9095, 2021.
[13] I. G. Burova, "Application Local Polynomial
and Non-polynomial Splines of the Third
Order of Approximation for the Construction
of the Numerical Solution of the Volterra
Integral Equation of the Second Kind,"
WSEAS Transactions on Mathematics, vol.
20, pp. 9-23, 2021.
[14] E. N. Menshov, "Approximation of Families
of Characteristics of Energy Objects in the
Class of Linear Differential
Equations,"WSEAS Transactions on
Computers, vol. 20, pp. 239-246, 2021.
[15] Michlin S.G. Some Theorems on the Stability
of Numerical Processes, Atti d. Lincei.
Classe fis., mat. e nat., fasc.2, 1982, pp. 1-32.
[16] Michlin S.G. Approximation auf dem
Kubischen Gitter. Berlin, 1976.
[17] Dem'yanovich Yu.K. ``Approximation on
Manifold'', WSEAS Transactionson
Mathematics, 20, pp. 62-73, 2021.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en
_US
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2022.21.92
Yuri K. Dem'yanovich
E-ISSN: 2224-2880
809
Volume 21, 2022
