Method of Searching Optimal Nodes Arrangement of Continuous Function Approximation with Consideration of Space Nonlinearity

Konopatskiy, E.V.; Kislitsyn, D.I.; Stepura, A.V.; Kotova, O.V.

doi:10.26583/sv.17.3.01

Scientific Visualization, 2025, volume 17, number 3, pages 1 - 8, DOI: 10.26583/sv.17.3.01

Method of Searching Optimal Nodes Arrangement of Continuous Function Approximation with Consideration of Space Nonlinearity

Authors: E.V. Konopatskiy^1,A, D.I. Kislitsyn^2,A, A.V. Stepura^3,B, O.V. Kotova^4,С

^A Nizhny Novgorod State University of Architecture and Civil Engineering

^B Moscow State University of Civil Engineering (National Research University)

^C Donbas National Academy of Civil Engineering and Architecture

¹ ORCID: 0000-0003-4798-7458, e.v.konopatskiy@mail.ru

² ORCID: 0000-0002-0232-9593, kislitsynd@yandex.ru

³ ORCID: 0000-0003-4099-329X, stepuraAV@mgsu.ru

⁴ ORCID: 0009-0004-6292-1080, o.v.kotova@donnasa.ru

Abstract

A method of searching optimal nodes of approximation realized on the example of Runge function is proposed. The method is based on the use of interpolation algebraic curves in point calculus and is reduced to minimization of the target function of many variables, which provides minimum deviations of the approximating function from the original one. Traditionally, in the process of interpolation, the coefficients of the interpolating function are determined on the basis of the initial points, which does not make it possible to ensure the search for the optimal location of interpolation nodes, since the coordinates of the node points are necessary to determine the coefficients of the interpolating function. The peculiarity of interpolation curves realized in point calculation is that they are obtained by uniform distribution of the parameter along the numerical axis and keep the coordinates of interpolation nodes in the point equation, which makes it possible to set and solve the problem of their optimal location by minimizing the target function. After the realization of the coordinate calculation of the point equation of the interpolation curve, the final result of the approximation of the original function is an algebraic curve given in parametric form, which allows us to use the nonlinearity of space to significantly reduce the degree of the approximating polynomial function. For example, when using Chebyshev nodes, which are considered optimal for approximating the Runge function, at least 20 nodes are needed to achieve a high-quality approximation, which leads to the need to use a polynomial of degree 19. In this case, the MSE is 0.000111. Whereas for the Runge function approximation based on the optimized arrangement of approximation nodes, even when using 6 node points, the MSE is only 0.0000284, which is an order of magnitude lower compared to Chebyshev nodes and allows using two polynomials of degree 5 on each of the coordinate axes instead of one polynomial of degree 19.

Keywords: approximation, continuous function, approximation nodes, interpolation, interpolation curve, minimum of function, point calculus, nonlinear space, Runge function.

1. Introduction

One of the main tools for solving problems of scientific image visualization and visual analytics is interpolation and approximation. Interpolation is used for visualization of fields of various origins [1, 2], for fast visualization of scenes using 3D gas pedals [3], for implementation of texture compression technologies used in modern personal computers, tablets and smartphones [4], for visualization of results of parametric calculations in computational aerogasodynamics problems [5] and others. Approximation is traditionally used for numerical solution of differential equations [7, 8, 9]. In addition, it is widely used in engineering geometry and computer graphics [10], is used for 3D modeling of equilibrium capillary surfaces and visualization of various effects related to their stability or instability [11], for processing the results of parametric calculations in computational aerogasodynamics [5, 12] and other tasks.

Among the variety of multivariate approximation problems [13, 14], it is necessary to single out a class of problems related to the approximation of continuous functions [15, 16]. Such problems are usually solved on a segment of functions with interpolation on uniform meshes [17]. The choice of uniform meshes is related to the necessity to determine in advance the interpolation nodes, since they are necessary for determining the coefficients of interpolation functions. At the same time, in [13, 18], a method of defining interpolation curves in the point calculus was proposed, which preserved the possibility of choosing any interpolation nodes. The use of such interpolation curves opens new possibilities in approximation of continuous curves and allows us to formulate in a new way the problem of approximation of continuous functions related to the search for optimal approximation nodes by minimizing the target function, which previously simply could not be posed due to the limited capabilities of existing mathematical apparatuses of interpolation.

2. Method of searching optimal nodes of approximation

The method of searching optimal nodes of approximation is based on the use of interpolation curves implemented in the point calculus [13, 18]. The main idea of defining such curves is that instead of specific values of polynomial coefficients, the coordinate vectors A_k are used, which control the shape of the algebraic curve:

where M − is the current point of the curve arc;

t − is the current parameter, which varies from 0 to 1;

n − is the number of interpolation nodes.

Let us replace the coordinate vectors A_k by the nodes of the interpolation curve M_k. For this purpose, we assume the following condition:M=M_k+1 under uniform distribution of the current parameter t=k/n. It should be taken into account that the first and the last interpola-tion nodes are already defined by the initial and final points of the curve. That is A₁=M₁ at t=0, and A_n=M_n at t=1. As a result, instead of the parameter t at each point (interpolation node) we get its specific value. Next, we make a system of linear equations, which is solved by the Cramer method with respect to unknown coordinate vectors A_k, replacing them by the nodes of the interpolation curve M_k. The A_k expressions defined in this way are substituted into the original point equation of the algebraic curve. As a result, we obtain the point equation of the interpolation curve, which is defined by the nodes of M_k and the current parameter t:

where − polynomial functions of degree n, obtained by replacing the coordinate vectors A_k by the nodes of the interpolation curve M_k.

Thus, the interpolation curve equation retains the possibility of controlling the interpolation nodes M_k. Passing to the system of parametric equations, for two-dimensional space we obtain:

where x_k+1 and y_k+1 − are the interpolation node coordinates M_k+1.

The resulting system of equations describes the space nonlinear along the abscissa and ordinate axes using two independent polynomial functions.

Now, having the equation of curves preserving coordinates of interpolation nodes, we can set the problem of optimal location of interpolation nodes along the abscissa axis for approximation of continuous functions. For this purpose, the interpolation curve must be discretized - represented as a discrete set of points, the number of which m must be greater than the number of interpolation nodes n. As a result, for two-dimensional space we obtain two separate arrays of functions x_i and y_i from the interpolation nodes and the current parameter with a uniform distribution of values t_i=i/m. Thus, for each particular value of t_i we obtain the values of functions x_i and y_i, which depend only on the interpolation nodes M_k.

The target function is the sum of squares of the difference of coordinates , where is the function to be approximated as a variable for which an array of values derived from the approximating function is used.

Having determined the minimum of the target function, we obtain the coordinate values of the interpolation curve nodes optimized along the abscissa axis and the final equation of the interpolation curve in vector form or as a system of parametric equations.

In fact, the proposed method is based on minimizing the standard deviation of two functions. In this case, the approximating polynomial function is "trained" on the basis of the approximated function. The quality of such "training" depends on the number of points obtained by discretization of the interpolation curve. Thus, the higher the value of the number of discretized points of the interpolation curve m, the higher the quality of approximation and, at the same time, the higher the computational load. As computational experiments have shown, this dependence is not linear and even at small values of m it is possible to obtain high-quality approximation results at low computational costs.

3. Results of computational experiments

For computational experiments, the Runge function is chosen to be defined on the segment [-1,1]:

To approximate the Runge function, an interpolation curve in nonlinear two-dimensional space passing through 6 interpolation nodes M_k is used, which is defined by the following point equation and reduced to a system of two homogeneous parametric equations:

where x_j and y_j − are the coordinates of 6 interpolation nodes ();

;

− parameter of the interpolation curve, which varies from 0 to 1;

− addition of parameter t to 1.

The values are calculated from the original Runge function:

Then we compose and determine the minimum of the target function: . To conduct computational experiments, the value of m=100.

Of the 6 interpolation nodes, the first and the last one has already been determined based on the conditions: , . It remains to calculate the coordinates of the 4 nodes: so that the deviation of the approximated polynomial function from the approximating function is minimized.

The calculations were performed in the Maple computer algebra system. The NLPSolve command from the Optimization package was used to minimize the target function. As a result, the optimal coordinates of the nodes of the Runge function approximation on the abscissa axis were determined:

The final equations of the approximating function in nonlinear two-dimensional space are represented as the following system of parametric equations:

As can be seen from the obtained system of equations, two polynomials of degree 5 on each of the coordinate axes were used to approximate the Runge function. Let us perform a visual comparison of the graph of the approximated Runge function and the approximating algebraic curve of the 5th order in nonlinear space (Fig. 1).

Fig. 1. Visualization of the graph of the Runge function (red) approximated by a 5th order algebraic curve in nonlinear space (blue)

For visual comparison of the obtained results, let us present the graph of Runge function approximated by Lagrange polynomial with uniform distribution of interpolation nodes (Fig. 2) and using Chebyshev nodes (Fig. 3), which are considered optimal for approximation of Runge function. As can be seen from comparing Figure 1 with Figures 2 and 3, existing methods of approximating the Runge function are significantly inferior in accuracy to the proposed method of searching optimal nodes of approximation.

Fig. 2. Visualization of the graph of Runge function (red) approximated by Lagrange polynomial with uniform distribution of interpolation nodes (blue)

Fig. 3. Visualization of the graph of Runge function (red) approximated by Lagrange polynomial using Chebyshev knots (blue)

According to the calculation results, the mean square error of approximation (MSE) was only 0.0000284, which is confirmed by comparing the graphs of the functions shown in Figure 1. For comparison, the MSE of the 5th order interpolation curve based on 6 Chebyshev nodes is. To achieve MSE=0.0000253 of the curve based on Chebyshev nodes, comparable to the mean square error based on the method of determining the optimal location of the approximation nodes, it is necessary at least 23 nodes, which leads to the need to use a polynomial of degree 22 and significantly increases the complexity of calculations, requirements for rounding polynomial coefficients and complicates the possibilities of their practical use. Such a high quality of approximation at a minimum value of nodal points is ensured by the fact that the approximating curve is defined in a nonlinear space, preserving nonlinearity both along the abscissa and ordinate axes. This suggests that even more efficient approximation can be achieved for spatial interpolation curves in multidimensional space.

We also conducted computational experiments to determine the optimal approximation nodes for various interpolants in the form of algebraic curves passing through predetermined points. As a result, we can analyze the trend of the MSE of the method of searching optimal nodes of approximation of continuous functions taking into account the nonlinearity of space depending on the number of approximation nodes (Table 1).

Table 1. Dependence of MSE on the number of approximation nodes

Number

of nodes

MSE

0,000963

2,84E-05

5,14E-07

1,01E-08

8,15E-10

2,67E-08

4E-09

As can be seen from Table 1, up to 9 nodes there is a stable growth of approximation accuracy and its insignificant decrease when using 10 and 11 approximation nodes. This is due to the limitation of the used numerical method of minimizing the target function by the number of iterations. Nevertheless, the MSE values remain at the level of 10^-8 and below, which indicates a very high quality of approximation and efficiency of the proposed method.

Let us compare the proposed method with the research results of other authors. In [19], a special algorithm based on the wavelet transform was implemented, which provided quasi-interpolation of the Runge function by the singular wavelet method with a uniform arrangement of interpolation nodes on the interval [-1, 1]. To achieve a qualitative result, 13 points were needed, which is also inferior to the proposed method in terms of the number of approximation nodes. In [20], adaptive radial basis functions were used to approximate the Runge function on the interval [-1, 1]. To achieve MSE=0.000017 comparable in accuracy with the proposed method, 47 interpolation nodes were needed instead of 6. At the same time, 83 nodes were needed for accurate approximation with MSE at the level of 2.6E-6.

In [21] the possibility of using neural networks for approximation of Runge function on the interval [-2.5,2.5] was investigated. Let us apply the method of searching optimal nodes of approximation of continuous functions taking into account the nonlinearity of space to approximate Runge function with new boundary conditions.

Fig. 4. Visualization of the graph of the Runge function (red) on the segment [-2.5,2.5] approximated by an algebraic curve in nonlinear space (blue):

a) 5th order curve passing through 6 interpolation nodes;

b) 6th order curve passing through 7 interpolation nodes

When approximating the Runge function on the segment [-2.5,2.5] by a 5th order algebraic curve passing through 6 interpolation nodes, the mean square error was 0.0005587. And when using the 6th order curve passing through 7 interpolation nodes, MSE=0.00001936. As can be seen from the obtained results (Fig. 4a and 4b), the efficiency of the proposed method is higher when the number of approximation nodes is much smaller. In [21], 500 points were used to approximate the Runge function by a neural network with 1 neuron on the input layer, 3 neurons on the hidden layer and 1 neuron on the output layer trained on 25 epochs. While for the realization of the proposed method of searching optimal nodes of approximation in nonlinear space only 6 and 7 nodes were needed, respectively (Fig. 4a and 4b).

4. Conclusions

The advantages of the proposed method for optimizing the location of approximation nodes, in addition to low values of the MSE, include the fact that the method is stable to an increase in the number of nodes. This is explained by the specificity of the method itself, which each time optimizes the location of approximation nodes, adapting to the function being approximated. In this case, there is no undesirable effect of oscillations of the polynomial function, which is confirmed by the Runge example. Another advantage is a significant reduction in the degree of approximating polynomials compared to other approximation methods without the need to use piecewise functions for approximation.

The disadvantages of the proposed method include the fact that it is implemented using numerical methods to find the minimum of the target function, which largely depend on the quality of the choice of the initial approximation. More research is required to ensure the robustness of the proposed method to the minimization of the target function. At the same time, the proposed method has shown high stability with respect to the increase of approximation nodes. It is sufficiently universal and can be an effective tool for approximating any continuous functions, as well as experimental data sets of any origin.

Since the curve is the main form-forming tool of geometric modeling, the proposed method of searching optimal nodes of approximation of continuous functions taking into account the nonlinearity of space has great prospects for increasing the number of variables of the approximating function to approximate geometric objects, processes and phenomena with complex geometric shape using continuous functions without the need to use piecewise functions. Such curves can become an effective tool for describing the internal structure of space for modeling isotropic and anisotropic geometric bodies as a distinguished part of space [22]. The search for effective methods for minimizing the target function of many variables and computational experiments on approximation of various continuous and piecewise functions are also a prospect for further research.

5. Acknowledgements

The study was supported by the Russian Science Foundation Grant No. 25-21-00003: https://rscf.ru/en/project/25-21-00003/.

References

1. Boyarchuk M.A., Zhurkin I.G., Nepoklonov V.B. Concept of a visualization method for Earth’s gravity field on plain maps. Scientific Visualization. 2019. Vol. 11. No. 1. pp. 70-79. DOI 10.26583/sv.11.1.06.

2. Modyaev A.D., Leonova N.M., Filatov A.S., Shabynin A.A. Methodology of gamma-rays visualization in indoor space. Scientific Visualization. 2014. Vol. 6. No. 3. pp. 87-95.

3. Andreev S., Valiev I. OpenGL visualization in Inspirer2 with quality of ray tracing method. Scientific Visualization. 2012. Vol. 4. No. 3. pp. 26-34.

4. Paltashev T., Perminov I. Texture Compression Techniques. Scientific Visualization. 2014. Vol. 6. No. 1. pp. 106-146.

5. Alekseev A.K., Bondarev A.E., Pyatakova Yu.S. On the Visualization of Multidimensional Functions using Canonical Decomposition. Scientific Visualization. 2022. Vol. 14. No. 3. pp. 73-91. DOI 10.26583/sv.14.3.06.

6. Alekseev A.K., Bondarev A.E., Pyatakova Yu.S. On Application of Canonical Decomposition for the Visualization of Results of Multiparameter Computations. Scientific Visualization. 2023. Vol. 15. No. 4. pp. 12-23. DOI 10.26583/sv.15.4.02.

7. Tolok A.V., Tolok N.B. Functional-Voxel Modeling of The Cauchy Problem. Scientific Visualization. 2024. Vol. 16. No. 1. pp. 105-111. DOI 10.26583/sv.16.1.09.

8. Vasilyev A.N., Lazovskaya T.V., Tarkhov D.A. Approximation of Bessel functions by the method of constructing multilayer solutions of differential equations. Modern information technologies and IT education. 2020. Vol. 16. No. 2. pp. 273-284. DOI 10.25559/SITITO.16.202002.273-284.

9. Konopatskiy E.V., Voronova O.S., Shevchuk O.A., Bezditnyi A.A. About one method of numeral decision of differential equalizations in partials using geometric interpolants. CEUR Workshop Proceedings, 2020. Vol. 2763. pp. 213-219. DOI 10.30987/conferencearticle_5fce27708eb353.92843700.

10. Korotkiy V.A. Irregular Curves in Engineering Geometry and Computer Graphics. Sci-entific Visualization. 2022. Vol. 14. No. 1. pp. 1-17. DOI 10.26583/sv.14.1.01.

11. Klyachin A.A., Klyachin V.A., Grigorieva E.G. Visualization of Stability and Calculation of the Shape of the Equilibrium capillary surface. Scientific Visualization. 2016. Vol. 8. No. 2. pp. 37-52.

12. 6. Alekseev A.K., Bondarev A.E., Pyatakova Yu.S. On Application of Canonical De-composition for the Visualization of Results of Multiparameter Computations. Scientific Vis-ualization. 2023. Vol. 15. No. 4. pp. 12-23. DOI 10.26583/sv.15.4.02.

13. Konopatskiy E.V. Approximation of geometric objects using arcs of curves passing through to advance given points. Information technologies. 2019. VOL. 25. No. 1. pp. 46-52. DOI 10.17587/it.25.46-51.

14. Konopatskiy E.V., Bezditnyi A.A., Shevchuk O.A. Modeling geometric varieties with given differential characteristics and its application. CEUR Workshop Proceedings, 2020. Vol. 2744. DOI 10.51130/graphicon-2020-2-4-31.

15. Ta Y.T., Ngo H.H., Nguyen V.H. A new computational method for determining parame-ters representing fundamental frequency contours of speech words. Journal of Information Hiding and Multimedia Signal Processing. 2020. Vol. 11. No. 1. pp. 1-13.

16. Motoki M., Shintani H., Matsuo K., Martin T. Mcginnity Utilization of SAM-based net-work for developing function approximation. Journal of Digital Information Management. 2022. Vol. 20. No. 4. pp. 148-155. DOI 10.6025/jdim/2022/20/4/148-155.

17. Ramazanov A.R.K., Magomedova V.G., Ibragimova B.M. Rational approximation of con-tinuous functions with interpolation on uniform node grids. Bulletin of Dagestan State Uni-versity. 2012. No. 1. pp. 106-111.

18. Konopatskiy E.V., Bezdytniy A.A. Modeling and Visualization of Complex Shaped Sur-faces Using Interpolation Curves. Scientific Visualization. 2024. Vol. 16. No. 4. pp. 1-10. DOI 10.26583/sv.16.4.01.

19. Romanchak V.M. Approximation by singular wavelets. System analysis and applied in-formatics. 2018. No. 2. pp. 23-28.

20. Zhang Qi., Zhao Ya., Levesley J. Adaptive radial basis function interpolation using an error indicator. Numerical Algorithms. 2017. Vol. 76. No. 2. pp. 441-471. DOI 10.1007/s11075-017-0265-5.

21. Galkin V.A., Gavrilenko T.V., Smorodinov A.D. Some aspects of approximation and in-terpolation of functions artificial neural networks. Bulletin KRAUNTS. Physical and Mathe-matical Sciences. 2022. Vol. 38. No. 1. pp. 54-73. DOI 10.26117/2079-6641-2022-38-1-54-73.

22. Konopatskiy E.V., Bezditnyi A.A., Lagunova M.V., Naidysh A.V. Principles of solid mod-elling in point calculus. IoP conference series: Journal of Physics: Conf. Series 1901 (2021) 012063. DOI 10.1088/1742-6596/1901/1/012063.

Scientific Visualization