Elements of the General Theory of Optimal Algorithms

verfasst von: Ivan V. Sergienko, Valeriy K. Zadiraka, Oleg M. Lytvyn

Verlag: Springer International Publishing

Buchreihe : Springer Optimization and Its Applications

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

In this monograph, the authors develop a methodology that allows one to construct and substantiate optimal and suboptimal algorithms to solve problems in computational and applied mathematics. Throughout the book, the authors explore well-known and proposed algorithms with a view toward analyzing their quality and the range of their efficiency. The concept of the approach taken is based on several theories (of computations, of optimal algorithms, of interpolation, interlination, and interflatation of functions, to name several). Theoretical principles and practical aspects of testing the quality of algorithms and applied software, are a major component of the exposition. The computer technology in construction of T-efficient algorithms for computing ε-solutions to problems of computational and applied mathematics, is also explored. The readership for this monograph is aimed at scientists, postgraduate students, advanced students, and specialists dealing with issues of developing algorithmic and software support for the solution of problems of computational and applied mathematics.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Elements of the Computing Theory

Abstract

This chapter is devoted to the further development of the theory of computational errors, namely, the work proposes a combined approach to assessing the quality of the solution of the problem. This takes into account the various sources of error that accompany the real computational process. These are first of all method errors, irreversible error, and rounding error. With regard to rounding error, it should be noted that due to the complexity of the tasks to be solved, the number of operations increases significantly, and in some cases, the assessment of rounding error becomes the main one. Ignoring rounding errors means that computer models may have nothing to do with physical ones. Ways to reduce rounding errors are to select the parameter S. The meaning of this parameter is that S memory cells are allocated to one number. Thanks to the parameter S you can adjust the accumulation of rounding errors.

This combined approach to assessing the quality of the solution of the problem is a guarantee of the quality of its solution. Failure to take into account at least one component of the error does not provide such a guarantee.

Ivan V. Sergienko, Valeriy K. Zadiraka, Oleg M. Lytvyn

Chapter 2. Theories of Computational Complexity

Abstract

This chapter is devoted to the issues of algebraic and analytical computational complexity of problem solving. The main focus is on computer technology for computational processes, which is covered for various computational models.

An important reserve for computational optimization is the construction and use of optimal in accuracy and speed computational algorithms. This allows you to solve the problem with the least error and can transfer the problem from the class of unsolvable problems to the class of solvable ones.

The choice of information solution operator is also a reserve for computational optimization. Successful choice of the information operator makes it possible to reduce the Chebyshev radius of the uncertainty region of the approximate solution of the problem.

These approaches are illustrated by the problem of approximate calculation of integrals from fast-oscillating functions in both one-dimensional and multidimensional cases.

Ivan V. Sergienko, Valeriy K. Zadiraka, Oleg M. Lytvyn

Chapter 3. Interlineation of Functions

This chapter is devoted to the construction and study of interlineation operators of functions of two or more variables with and without preservation of the class of differentiation. When constructing interlineation operators of functions, new information operators are used: traces of an approximate function and traces of some differential operators with partial derivatives up to the specified order on a system of parallel or intersecting lines. If information operators use only traces of functions, then we have an interlineation of the Lagrangian type. If the interlineation of functions uses traces of the approximate function and traces of some system of differential operators from the approximate function, then we have a Hermitian-type interlineation. If the approximate function has continuous derivatives only up to a certain order, then Hermitian interlineation operators with given traces on the system of lines give functions that do not have the same class of differentiation as the approximate function. For this case, the work presents a generalized D'Alembert formula (the classical D'Alembert formula is its partial case), which automatically preserves the same class of differentiation to which the approximate function belongs. The work presents examples of Hermitian interlineation operators with and without preservation of the class of differentiation on the system of parallel, mutually perpendicular, and intersecting lines.

Here give integral representations of the residual terms of the approximation of differentiation functions of two variables with and without preservation of the class of differentiation. An example of Lagrangian interlineation on a system of mutually perpendicular lines with the optimal choice of these interlineation lines is given.

Ivan V. Sergienko, Valeriy K. Zadiraka, Oleg M. Lytvyn

Chapter 4. Interflatation of Functions

Abstract

This chapter presents the operators of interflatation of functions of three variables on a system of mutually perpendicular planes using rational, polynomial, trigonometric auxiliary functions, and auxiliary functions in the form of splines. These operators use traces of the approximate function of three variables and traces of its normal derivatives on some system of planes. Note that the operators of interlineation and interflatation of functions are a natural generalization of the interpolation of functions of many variables.

This chapter also presents possible applications of interlineation of functions in solving boundary value problems with partial derivatives within the framework of V.L. Rvachev’s structural method. This method is based on the use of R-functions that are positive in given domains, equal to zero at the boundary of domains that are negative outside these domains. The monograph presents three problems that can improve the computational properties of the structures of approximate solutions of boundary value problems, if to construct them use the interlineation operators of functions with automatic preservation of the class of differentiation.

Here give integral representations of the residual terms of the approximation of differentiation functions of three variables.

Ivan V. Sergienko, Valeriy K. Zadiraka, Oleg M. Lytvyn

Chapter 5. Cubature Formulae Using Interlineation of Functions

Abstract

This chapter presents the cubature formulas for calculating the integrals of the functions of two variables, which are obtained by replacing the subintegral function by spline interlineation operators. The cubature formulas for calculating the integrals of fast-oscillating functions are also given, in which the non-oscillating factor is replaced by the corresponding spline interlineation formula.

Here using integral representations of the residual terms of the approximation of differentiation functions of two and three variables with and without preservation of the class of differentiation. Creating application software sometimes costs more than the cost of the computer itself. Therefore, testing the quality of software is a very important task.

Ivan V. Sergienko, Valeriy K. Zadiraka, Oleg M. Lytvyn

Chapter 6. Testing the Quality of Algorithm Programs

Abstract

This chapter outlines both the theoretical foundations of testing algorithms and programs, and practical (programs differ from algorithms by the presence of rounding errors). In particular, the subject and purposes of testing and the method of testing are covered. An important issue is the assembly of test kits and the implementation of the experiment.

Examples of testing in the calculation of integrals from fast-oscillating functions are also given.

One of the main problems of computational mathematics is search ε-solution of the problem for a given processor time. The connection of such characteristics of the computational algorithm as accuracy, memory, and speed is important.

Ivan V. Sergienko, Valeriy K. Zadiraka, Oleg M. Lytvyn

Chapter 7. Computer Technologies of Solving Problems of Computational and Applied Mathematics with Fixed Values of Quality Characteristics

Abstract

This chapter describes computer technologies for solving problems of computational and applied mathematics with given values of quality characteristics in accuracy and speed. This technology is suitable for any problem of computational and applied mathematics. This computer technology is essentially based on the use of all possible reserves of computational optimization, including the theory of errors, optimal for the accuracy and speed of computational algorithms, detection and refinement of a priori information about the problem, the choice of computational model, and more.

This computer technology is illustrated by the task of integrating fast-oscillating functions. Problems of computational and applied mathematics related to the integration of fast-oscillating functions are also given.

Ivan V. Sergienko, Valeriy K. Zadiraka, Oleg M. Lytvyn

Backmatter

Titel: Elements of the General Theory of Optimal Algorithms
verfasst von: Ivan V. Sergienko
Valeriy K. Zadiraka
Oleg M. Lytvyn
Verlag: Springer International Publishing
Electronic ISBN: 978-3-030-90908-6
Print ISBN: 978-3-030-90906-2
DOI: https://doi.org/10.1007/978-3-030-90908-6