UDC 519.6+004.02
1 V.M. Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine, Kyiv, Ukraine
lara.vakal@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
- Stechkin S.B., Subbotin Yu.N. Splines in computational mathematics (in Russian). Moscow: Nauka, 1976. 248 p.
- Berdyshev V.I., Petrak L.V. Approximation of functions, compression of numerical information, applications (in Russian). Ekaterinburg: Ural Branch of RAS, 1999. 297 p.
- 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.
- Popov B.A. Uniform approximation by splines (in Russian). Kiev: Nauk. Dumka, 1989. 272 p.
- Malachivsky P.S., Skopetsky V.V. Continuous and smooth minimax spline approximation (in Ukrainian). Kyiv: Nauk. Dumka, 2013. 270 p.
- Korneichuk N.P. Exact constants in the approximation theory (in Russian). Moscow: Nauka, 1987. 424 p.
- Barrodale J., Young A. A note on numerical procedures for approximation by spline functions. Comput. J. 1966. Vol. 9. P. 318–320.
- 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.
- Vakal L.P. Construction of the best Chebishov approximations by splines. Shtuchnyy intelekt. 2017. № 2. P. 94–100.
- 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.
- Nurnberger G., Sommer M. A Remez type algorithm for spline functions. Numer. Math. 1983. Vol. 41, N 1. P. 117–146.
- Remez E.Ya. Fundamentals of numerical methods of the Chebyshev approximation (in Russian).. Kiev: Nauk. Dumka, 1969. 623 p.
- 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.
- Nurnberger G. Bivariate segment approximation and free knot splines; research problems 96-4. Constructive Approximation. 1996. Vol. 12, N 4. P. 555–558.
- 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.
- 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.
- Vakal L.P. Seeking optimal knots for segment approximation. Journal of Automation and Information Sciences. 2016. Vol. 48, N 11. P. 68–75.
- 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.
- 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.
- Vakal L.P. Genetic algorithms for Chebyshev approximation. Komp'yuterni zasoby, merezhi ta systemy. 2013. No. 12. P. 20–26.
- 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.
- 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.