Modernization adaptive piecewise linear approximation of difficult-to-compute functions
Keywords:
approximation, interpolation, piecewise linear approximation, difficult-to-compute function, efficiency indexAbstract
The solution of many theoretical and applied problems requires that some functional dependencies be substituted into others, which are more convenient for the implementation of a specific mathematical problem. At the same time, information about the character of the original function can be insufficient, and the function itself can be considered to be difficult to compute. The accuracy of such an approximation depends on the methods used, the character of the original function, as well as the number and choice of grid points. The easiest way of building such an approximation is doing it on a uniform grid of points, which does not always provide an acceptable result. The purpose of this paper is to develop effective adaptive methods of approximating functions for the problems aimed at searching for the lengths of curves and calculating integrals under conditions of limited information about the character of the original function and the presence of its derivatives. An adaptive approach to the approximation of a wide class of one-dimensional functions is proposed in the paper. For this approximation a piecewise linear approximation with a simple mechanism of exponential adaptive feedback step process control is used. The possibilities of this approach are considered, using the problems of calculating the lengths of curves and values of definite integrals. The specifics of the application of the suggested approach are detailed for each case. The approach does not require an initial allocation of grid points. The method ensures the required accuracy in automatic mode. The result is realized in a single pass without any preliminary transformations. The reliability of the obtained results is confirmed by solving the known test examples. The results of calculating a number of definite integrals with different nature of integrand are presented. The calculation results by the proposed method are compared with the data obtained by the usual trapezoid method. A high efficiency of the proposed approach is established. The proposed method opens the way for creating effective means for solving numerical integration and differentiation problems, as well as integral and differential equations and so on.References
Ostrovskiy, A. M. (1966). Solutions of Equations and Systems of Equations, 2nd ed.New York: Academic Press.
Krylov, A. N. (1954). Lektsii o priblizhennykh vychisleniyakh [Lectures on Approximate Calculations].Moscow: Gostekhizdat (in Russian).
Weiershtrass, K. (1885). Über die analytische Darstellbarkeit sogenannter willkürlicher Funktionen einer reelen Veränderlichn. Sitzungsberichte der Berliner Akademie der Wissenschaften, pp. 633–639.
Mhaskar, H. N., Pai, D. V. (2000). Fundamentals of Approximation Theory.New Delhi: Narosa Publishing House.
Trefethen, L. N. (2013). Approximation Theory and Approximation Practice.Oxford:OxfordUniversity.
Richardson, L. F. (1911). The Approximate Arithmetical Solution by Finite Differences of Physical Problems Involving Differential Equations, with an Application to the Stresses in a Masonry Dam. Philosophical Transactions of the Royal Society of London. Ser. A, Vol. 210, pp. 307–357.
Runge, C. (1901). Über empirische funktionen und die interpolation zwischen äquidistanten en ordinaten. Zeitschrift für Mathematik und Physik, Vol. 46, pp. 224–243.
Chebyshev, P. L. (1881). O funktsiyakh, malo uklonyayushchikhsya ot nulya pri nekotorykh velichinakh peremennykh. Sobranie sochineniy, [On Functions Deviating Least from Zero at Some Values of Variables. Col.works]. Vol. 3, pp. 108–127 (in Russian).
Faber, G. (1914) Über die interpolatiorische darstellung stetiger funktionen. Deutsche Mathematiker-Vereinigung Jahresbeucht, Vol. 23, pp. 192–210.
Marcinkiewicz, J. (1939).Sur interpolation d`operations. Comptes rendus de l'Académie des Sciences, Vol. 208, pp. 1272–1273.
Bernshteyn, S. N. (1937). O mnogochlenakh ortogonalnykh v konechnom intervale [On Orthogonal Polynomials in a Finite Interval].Kharkov: Gos. nauch.-tekhn. izd-vo Ukrainy (in Russian).
Ahlberg, J. H., Nilson, E. N., Walsh, J. L. (1967). The Theory of Splines and Their Applications.New York andLondon: Academic Press.
Popov, B. A., Tesler, G. S. (1984). Priblizhenie funktsiy splaynami [Approximation of Functions by Splines]Kiev: Nauk. dumka (in Russian).
Rvachev, V. L., Rvachev, V. A. (1975). Atomarnye funktsii v matematicheskoy fizike. Matematizatsiya znaniy i nauch.-tekhn. Progress [Atomic Functions in Mathematical Physics. Knowledge Mathematization, and Scientific and Technical Progress].Kiev: Nauk. dumka, pp. 188–199 (in Russian).
Ryabenkiy, V. S. (1974). Lokalnye formuly gladkogo vospolneniya i gladkoy interpolyatsii po ikh znacheniyam v uzlakh neravnomernoy pryamougolnoy setki [Local Formulae for Smooth Replacement and Interpolation by Their Values in Non-Uniform Rectangular Grid Nodes].Moscow: In-t problem matematiki Akademiyi nauk SSSR, 1974. 42 p. (Preprint. Akademiya nauk SSSR. In-t problem matematiki; 21) (in Russian).
Bos, L., De Marchi, S., Hormann, K., Klein, G. (2012). On the Lebesgue Constant of Barycentric Rational Interpolation at Equidistant Nodes. Numerische Mathematik, Vol. 121, Iss. 3, pp. 461–471.
Bellman, R. E. (2016). Adaptive Control Processes. A Guided Tour.Princeton Legacy Library.
Bahvalov, N. S. (1966). Obalgoritmakh vybora shaga integrirovaniya. Vychisl. metody i programmirovanie [On Algorithms for Selecting Integration Steps. Computational Methods and Programming], Iss. 5, pp. 3–8 (in Russian).
Pukk, R. A. (1970). Algoritm integrirovaniya, uchityvayushchiy stepen gladkosti funktsiy. Izv. AN ESSR. Fizika. Matematika [Integration Algorithm Taking into Account Degree of Function Smoothness. Proceedings of AS of ESSR. Physics. Mathematics], Vol. 19, No. 3, pp. 368–370 (in Russian).
Sheludko, G. A. Adaptivnoe integrirovanie. AN Ukrainy In-t problem mashinostroeniya. [Adaptive Integration. AS ofUSSR. IMEP].Kharkov, 1973. 12 p. Dep. VINITI 26.07.73, No. 7753 (in Russian).
Sheludko, H.A., Ugrimov, S. V. (1997). Adaptivnyie resheniya nekotorykh zadach vyichislitelnoy matematiki. Akademiya nauk Ukrainyi. In-t problem mashinostroeniya. [Adaptive Solutions to Some Problems of Computational Mathematics . AS ofUSSR. IMEP].Kharkov(in Russian).
Gander, W., Gautschi, W. (2000). Adaptive Quadrature – Revisited. BIT Numerical Mathematics, Vol. 40. Iss. 1, pp. 84–101.
Forsythe, G.E., Malcolm, M.A., Moler, C.B. (1977). Computer Methods for Mathematical Computations.EnglewoodCliffs,New Jersey: Prentice-Hall.
Mathews, J., Fink, K. (2004). Numerical Methods Using Matlab. 4nd ed.New Jersey: Prentice-Hall.
Sheludko, H.A., Ugrimov, S. V. (2011). Adaptivnaya gibridizatsiya [Adaptive Hybridisation].Kharkov: Miskdruk (in Russian).
Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (1972). Edited by M. Abramowitz andI. A. Stegun. 9th ed.New York:Dover Publication.
Downloads
Published
Issue
Section
License
Copyright (c) 2018 G. A. Sheludko, S. V. Ugrimov
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.
All authors agree with the following conditions:
- The authors reserve the right to claim authorship of their work and transfer to the journal the right of first publication of the work under the license agreement (the agreement).
- Authors have a right to conclude independently additional agreement on non-exclusive spreading the work in the form in which it was published by the jpurnal (for example, to place the work in institution repository or to publish as a part of a monograph), providing a link to the first publication of the work in this journal.
- Journal policy allows authors to place the manuscript in the Internet (for example, in the institution repository or on a personal web sites) both before its submission to the editorial board and during its editorial processing, as this ensures the productive scientific discussion and impact positively on the efficiency and dynamics of citation of published work (see The Effect of Open Access).
