Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
UDC 519.6+004.02
L.P. Vakal1, E.S. Vakal2


1 V.M. Glushkov Institute of Cybernetics of the National Academy
of Sciences of Ukraine, Kyiv, Ukraine

lara.vakal@gmail.com

2 Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

jvakal@gmail.com

ALGORITHM FOR BEST UNIFORM SPLINE APPROXIMATION WITH FREE KNOTS

Abstract. An algorithm for best uniform spline approximation with free knots is presented in this paper. A differential evolution is used for finding the optimal knots. It is one of the best evolutionary algorithms which finds function’s global optimum in minimum time. Spline coefficients are computed as a solution of a spline-approximation problem with fixed knots. Results of the numerical experiment are given.

Keywords: best uniform approximation, spline, optimal knots, differential evolution.



FULL TEXT

REFERENCES

  1. Stechkin S.B., Subbotin Yu.N. Splines in computational mathematics (in Russian). Moscow: Nauka, 1976. 248 p.

  2. Berdyshev V.I., Petrak L.V. Approximation of functions, compression of numerical information, applications (in Russian). Ekaterinburg: Ural Branch of RAS, 1999. 297 p.

  3. Vakal E.S., Kivva S.L., Mistetskii G.E., Stelya O.B. Solution method for nonlinear parabolic equations. Journal of Mathematical Sciences. 1991. Vol. 54, N 2. P. 781–786.

  4. Popov B.A. Uniform approximation by splines (in Russian). Kiev: Nauk. Dumka, 1989. 272 p.

  5. Malachivsky P.S., Skopetsky V.V. Continuous and smooth minimax spline approximation (in Ukrainian). Kyiv: Nauk. Dumka, 2013. 270 p.

  6. Korneichuk N.P. Exact constants in the approximation theory (in Russian). Moscow: Nauka, 1987. 424 p.

  7. Barrodale J., Young A. A note on numerical procedures for approximation by spline functions. Comput. J. 1966. Vol. 9. P. 318–320.

  8. Esch R.E., Eastman W.L. Computational methods for best spline function approximation. Journal of Approximation Theory. 1969. Vol. 2, N 1. P. 85–96.

  9. Vakal L.P. Construction of the best Chebishov approximations by splines. Shtuchnyy intelekt. 2017. № 2. P. 94–100.

  10. Schumaker L.L. Some algorithms for the computation of interpolating and approximating spline functions. Theory and applications of spline functions. New York: Academic Press, 1969. P. 87–102.

  11. Nurnberger G., Sommer M. A Remez type algorithm for spline functions. Numer. Math. 1983. Vol. 41, N 1. P. 117–146.

  12. Remez E.Ya. Fundamentals of numerical methods of the Chebyshev approximation (in Russian).. Kiev: Nauk. Dumka, 1969. 623 p.

  13. Schumaker L.L. Uniform approximation by chebyshev spline functions. II. Free knots. SIAM Journal of Numerical Analysis. 1968. Vol. 5, N 4. P. 647–656.

  14. Nurnberger G. Bivariate segment approximation and free knot splines; research problems 96-4. Constructive Approximation. 1996. Vol. 12, N 4. P. 555–558.

  15. Crouzeix J.P., Sukhorukova N., Ugon J. Characterization theorem for best polynomial spline approximation with free knots, variable degree and fixed tails. Journal of Optimization Theory and Applications. 2017. Vol. 172, N 3. P. 950–964.

  16. Meinardus G., rnberger G., Sommer M., Strauss H. Algorithm for piecewise polynomials and splines with free knots. Math. of Computation. 1989. Vol. 53, N 187. P. 235–247.

  17. Vakal L.P. Seeking optimal knots for segment approximation. Journal of Automation and Information Sciences. 2016. Vol. 48, N 11. P. 68–75.

  18. Vakal L.P., Kalenchuk-Porkhanova A.A., Vakal E.S. Increasing the efficiency of Chebyshev segment fractional rational approximation. Cybernetics and Systems Analysis. 2017. Vol. 53, N 5. P. 759–765.

  19. Storn R., Price K. Differential evolution — a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization. 1997. Vol. 11. P. 341–359.

  20. Vakal L.P. Genetic algorithms for Chebyshev approximation. Komp'yuterni zasoby, merezhi ta systemy. 2013. No. 12. P. 20–26.

  21. Vakal L.P. Solving uniform nonlinear approximation problem using continuous genetic algorithm. Journal of Automation and Information Sciences. 2016. Vol. 48, N 6. P. 49–59.

  22. Vakal L.P. Approximation of functions of many variables using an algorithm for differential evolution. Matematychni mashyny i systemy. 2017. No. 1. P. 90–96.
© 2019 Kibernetika.org. All rights reserved.