Optimization of computational methods in functional spaces is one of the main problems of computational mathematics. In the present work algebraic and functional statements for the problem of difference formulas. For optimization of difference formulas, i.e., for construction of optimal difference formulas in functional spaces the important role plays the extremal function of the given difference formula. In this work, in the Sobolev space, the extremal function of the difference formula is explicitly found and the norm of the error functional of the difference formula is calculated. Furthermore, existence and uniqueness of the optimal difference formula are proved.
Shadimetov Kh.M. , Mirzakabilov R.N.
Sun Jun 26 12:14:38 2022
Contents
1 Introduction…………………………………………………………………………… ??
2 The problem on construction of difference formulas………………….. ??
3 The functional statement of the problem. The extremal function of the difference formulas……………………………………………………………………………… ??
4 Square of the norm of the error functional……………………………….. ??
1 Introduction
Suppose it is required to find a solution of a differential equation
(1.1)
with the initial condition in the interval . We divide this interval by pieces with length and we will search approximate values of the solution at nodes , The classical example of such type of methods is the Euler method which consists of the following: an approximate value of the solution at the point is obtained from the approximate value of the solution at the point by the formula
(1.2)
where . Therefore is a linear combination of values of the function and its derivatives at the point . We consider only discrete methods, i.e. methods which define a solution for discrete values of independent variable. A characteristic feature of discrete methods for solution of equation (1.1) is the process of solution consists of repetition of algorithm for obtaining of searching solution by using known, previously calculated values and
The problem of construction of a numerical algorithm can be separated into three groups:
- Local properties of the algorithm.
The problem consists of choosing such a algorithm for calculating of that the difference will be minimal. Here is an approximate value of the exact solution and are known. Asymptotic estimation of the algorithm’s accuracy for
is defined by two numbers and , if
It is supposed that the solution is sufficiently smooth, and parameter characterize the algebraic degree of exactness. An example of a such algorithm is Euler methods (1.2) for which and .
- Global properties of the algorithm.
The main problem is choosing such an algorithm that does not lead to the accumulation of errors, i.e.
as
- Stability of the algorithm as numerical process.
Some convergent algorithms may be accompanied by numerical instability. Therefore we consider conditions which are guarantee the stability of algorithms.
2 The problem on construction of difference formulas
The problem on construction of difference formulas exact for polynomials of degree , we also consider first in algebraic statement. Further as difference formula we mean the following approximate equality
(2.1)
Here
and are coefficients of the difference formula.
The difference formula of order is called
an implicit if and
an explicit if . The following difference we call
the error of the formula
(2.2)
In the class of differentiable functions defined on the interval , the equality (2.2) defines additive and homogeneous functional which we call
the error functional of the difference formula (2.1). We say that the difference formula is exact for a function if the difference (2.2) is equal to zero. By another words, functions for which the difference formula is exact form the kernel of the error functional . The problem on construction of difference formulas in algebraic statement for the interval is as follows:
Find coefficients and of the difference formula such that the formula becomes exact for all polynomials from the space for possible large , where is the space of polynomials of degree .
Therefore, the quality of the difference formula will be higher when the dimension of the space of polynomials is larger
Substituting a polynomial
for in (2.2) we get
Thus, our requirement for , which is equivalent to the following system of conditions
(2.3)
is fulfilled in that case when the vectors
are the solution of the system
System (2.3) has a solution if .
Now we give known difference formulas constructed by algebraic way.
We denote then the Adams-Bashforth formula has the form
and the Adams-Moulton formula has the form
There are other known formulas, for example, the Nystrom and the Mali-Simpson formulas and others.
3 The functional statement of the problem. The extremal function of the difference formulas
Now we go to the functional statement of our problem. We consider functions which are belong to the Sobolev space is a Hilbert space of real functions which are differ for polynomials of degree and square integrable with derivative of order on the interval . The inner product in this space is defined as
(3.1)
Since the space embedded to the space of continuous functions, the error functional of the difference formula is a linear functional
(3.2)
The problem of construction of the difference formula
in the functional statement is to find such a functional (3.2) which has minimal norm in the space . For finding the explicit form of the error functional we use an extremal function of the given functional, i.e. we use the function satisfying the equality
It is known that in the work of I. Babuska et al [1] finding of the extremal function was reduced to the differential equation of order . However, there was not given the solution of the differential equation. Our method of finding is differ from the method of I.Babuska and allows to find the extremal function explicitly.
Problems for construction of cubature and difference formulas in functional statement were considered, for example, in the works [2]-[10],[13],[15].
The norm of a function in the space is defined as
(3.3)
Since the functional of the form
is defined on the space then we have
(3.4)
Since is the Hilbert space equipped with the inner product (3.1) and corresponding norm (3.3) then applying the Riesz theorem for any linear functional, in particular for the error functional, we find an explicit form of the norm of the functional using a function which is the Riesz element. By the Riesz theorem for any the following equalities hold
(3.5)
By virtue of (3.1) and (3.5) we obtain the following identity which is true for any function of the space of infinitely differentiable finite functions
(3.6)
By Integrating by parts times the left hand side of the (3.6) we get
where is the characteristic function of the interval .
Thus, in the space of generalized functions we have the following equation
(3.7)
The general solution of equation (3.7) is written in the form
(3.8)
And in the formula (3.8) the sum
is a polynomial of degree with overdetermined coefficients corresponding to the following term
The function is a fundamental solution of the equation
and it has the form
We consider equation (13) out of the interval . By virtue of (2.3) out of the interval the expression is a polynomial of degree , because this function is from after times differentiation it becomes zero. For fulfilling the condition for it should be
where is a polynomial of degree
So, for any difference formula of the form (2.1) in the space its extremal function, i.e. its Riesz element is given by the formula
where is a polynomial of degree . Thus we have proved the following theorem.
Теорема 1 The extremal function of the differential formula (2.1) in the space is defined by the formula
(3.9)
4 Square of the norm of the error functional
We know that by Riesz theorem and definition of the extremal function it follows
Hence we get the following theorem.
Теорема 2 Square of the norm of the error functional of the difference formula (2.1) is defined by the formula
On the strength of Theorem 2, using the extremal function and orthogonality conditions (3.4) of the error functional to polynomials of degree , after some calculations we get
where
It is known that the stability of a difference formula in the sense of Dahlquits, as the strong stability, is only defined by coefficients
By this reason our search of the optimal formula is only connected by variation of coefficients
The difference formula with the error functional in the space can be characterized by two methods. On the one hand it is defined by coefficients with conditions (3.4), on the other hand by the extremal function .
Now we go to minimization of square of the norm for the error functional of the difference formula for the given by coefficients with conditions (3.4).
We apply the indefinite multipliers method of Lagrange. For this we consider the function
Partial derivatives of the function by and equating to zero
This gives the following system of equations
(4.1)
(4.2)
where
and
The solution of the system (4.1), (4.2) which we denote as , is a critical point for the function . From Lagrange method it follows that are the searching values of the coefficients of the optimal difference formula. They give the conditional minimum to the norm under the conditions (9).
Now we consider the formula (3.9). Taking into account arbitrariness of coefficients of the polynomial , we choose them such that the derivative coincides with the polynomial from (4.1). In such a choice for values of the derivative of the extremal function at points we get which follows from the formula (4.1). Therefore, we have proved Babuska’s theorem by algebraic way.
Теорема 3 Difference formulas
are optimal if and only if when the function , defined by the formula (3.9), can be selected such that
and
for implicit and explicit formulas, respectively.
As a results for construction of implicit optimal difference formulas it is necessary to solve the following system of linear equations
where are defined from the stability conditions of the difference formula in the sense of Dahlquits and
Определение 1 The difference formula (2.1) is stable in the sense of Dahlquits if all roots of the characteristic polynomial satisfy and roots, for which , are simple [11], [12], [14].
For example,
for
Similarly, for the explicit difference formula we have
where are defined from stability of the difference formula and from the equality
Here we suppose that the system (4.1), (4.2) is solvable. Its solvability follows from the general theory of Lagrange multipliers. However one can verify solvability directly by algebraic way.
From the theory of conditional extremum it is known the sufficient condition in which the solution gives local minimum to the function on the monifold (3.4). It consists of positive definiteness of the quadratic form
(4.3)
on the set of vectors under the condition
(4.4)
Here the matrix has the form
We show that in the considered case the quadratic form is strongly positive.
Теорема 4 For any nonzero vector
lying in the subspace , the function is strictly positive.
Proof. From the definition of the Lagrange function and from equality (4.3) we obtain
Consider the linear functional of the form
If we take into account the condition (4.4) then this functional belongs to the space . Thus, it has the extremal function which is a solution of the equation
Clearly, that as a one can get the following linear combination of the shifts of the fundamental solution
Here is a solution of the equation
Square of the norm of the function in the space coincides with the form :
Hence clear that for non zero the function is strictly positive. It is known that for the system (4.4) always has a solution, i.e. the matrix has the right inverse, then the system (4.1), (4.2) has a unique solution.
Теорема 5 If the matrix has the right inverse then the matrix of the system (4.1), (4.2) is nonsingular.
Proof. We denote the matrix of the quadratic form (4.3). We write homogeneous system corresponding to the system (4.1), (4.2) in the following form:
(4.5)
We show that a unique solution of (4.5) is identical zero.
Let be a solution of (4.5). We consider the following functional for the vector :
It is clear that this functional belongs to the space . As a extremal function for we take the following
This is possible, because, the function belongs to the space and is the solution of the equation
The first equations of the system (4.5) mean that the function vanishes at all nodes of the difference formula, i.e. for Then with respect to the norm of the functional in we have
that is possible only for Taking this into account, from first equations of the system (4.5) we obtain
(4.6)
By assertion of the theorem the matrix has the right inverse, then has the left inverse matrix. Hence and from (4.6) it follows that that the solution also is zero. Theorem is proved.
Thus, the system (4.1), (4.2) has unique solution.
References
[1] Babuska I., Vitasek E., Prager M.
Numerical processes for solution of differential equations: – Mir, Moscow, 1969, 369 p.
[2] Babuska I., Sobolev S.
Optimization of numerical methods.: – Apl. Mat., 10, 9-170, 1965
[3] Соболев С.
Введение а теорию кубатурных формул.: – М., 1974, 808 с
[4] Sobolev S., Vaskevich L.
Cubature fromulas.: – Novosibirsk, 1996, 484 p.
[5] Shadimetov Kh. Weighted optimal cubature formulas in the Sobolev periodic space: –
Siberian journal of computational mathematics. Novosibirsk, 1999, v.2, pp. 185-195.
[6] Shadimetov Kh. On optimal lattice quadrature and cubature formulas.:-
Dokl. Russian Academy of Sciences. Moscow, 2001, v.376, no. 5, pp. 597-599.
[7] Shadimetov Kh. Functioanal statement of the problem of optimal difference formulas: –
Uzbek mathematical Journal, 2015, no. 4, pp.179-183.
[8] Shadimetov Kh., Mirzakabilov R.N. The problem on construction of difference formulas: –
Problems of Computational and Applied Mathematics.– 2018, no. 5 (17). pp. 95-101.
[9] Akhmedov D.M., Hayotov A.R., Shadimetov Kh.M. Optimal quadrature formulas with derivatives for Cauchy type singular integrals:-
Applied Mathematics and Computation. 2018, N317. P.150-159.
[10] Boltaev N.D., Hayotov A.R., Shadimetov Kh.M. Construction of Optimal Quadrature Formula for Numerical Calculation of Fourier Coefficients in Sobolev space : –
American Journal of Numerical Analysis, 2016, v. 4, no. 1, pp. 1-7.
[11] Dahlquits G. Convergence and stability in the numerical integration of ordinary differential equations:-
Math. Scand., 1956, v. 4, pp. 33-52.
[12] Dahlquits G. Stability and error bounds in the numerical integration of ordinary differential equations:-
Trans. Roy. Inst. Technol. Stockholm, 1959.
[13] Shadimetov Kh.M., Hayotov A.R. Optimal quadrature formulas in the sense of Sard in space: –
Calcolo (2014) 51:211-243.
[14] Henrici P.,
Discrete variable methods in ordinary differential equations:- J.Wihey Sons, Ins., New York, London.
[15] Shadimetov Kh.M., Hayotov A.R., Akhmedov D.M. Optimal quadrature formulas for Cauchy type singular integrals in Sobolev space:-
Applied Mathematics and Computation. 2015, v. 263, pp. 302-314.
