Introduction to the theory of splines   with an optimal mesh.Linear Chebyshev  splines and applications

Vyacheslav K.  Isaev; Vyacheslav V. Zolotukhin

doi:10.3934/naco.2013.3.471

Article Contents

2013, Volume 3, Issue 3: 471-489. Doi: 10.3934/naco.2013.3.471

This issue Previous Article Partial Newton methods for a system of equations Next Article Deflating irreducible singular M-matrix algebraic Riccati equations

Introduction to the theory of splines with an optimal mesh. Linear Chebyshev splines and applications

Vyacheslav K. Isaev^1, and
Vyacheslav V. Zolotukhin^2,

1.
Prof. N. E. Zhukovsky Central Aerohydrodynamic Institute (TsAGI), Zhukovsky str., 1, Zhukovsky, Moscow region, 140180
2.
Moscow Institute of Physics and Technology (State University) (MIPT), Institutsky Lane 9, Dolgoprudny, Moscow region, 141700

Received: February 2012

Revised: July 2013

Published: July 2013

Abstract / Introduction Related Papers Cited by

Abstract

On June 18, 2008 at the Plenary Meeting of the International Conference ``Differential Equations and Topology" dedicated to the 100-th anniversary of L.S. Pontryagin, the report [15] was submitted by Isaev V.K. and Leitmann G. This report in a summary form included a section dedicated to the research of scientists of TsAGI in the field of automation of full life-cycle (i.e. engineering-design-manufacturing, or CAE/CAD/CAM, or CALS-technologies) of wind tunnel models [21]. Within this framework, methods of geometric modeling [1,11] were intensively developed, new classes of optimal splines have been built, including the Pontryagin splines and the Chebyshev splines [12-13,19,37]. This paper reviews some results on the Chebyshev splines. We also give brief remarks about the new applications of Chebyshev splines (outside the usual scope of CALS-technologies in design and manufacturing), namely to the actual problem of air traffic management (ATM) within the Free Flight concept.

Keywords:

Mathematics Subject Classification: Primary: 41A50, 65D07; Secondary: 91A80.

Citation:

Related Papers

Cited by

References

[1]	G. A. Amir'yants, N. A. Vladimirova, V. M. Gadetskiy, V. K. Isaev and S. V. Skorodumov, The nonlinear problems of integrated aerodynamic modelling, Nonlinear dynamic analysis (NDA2), Second International congress, Theses of lectures, MAI, Moscow, (2002), 269.
[2]	D. L. Barrow, C. K. Chui, P. W. Smith and J. D. Ward, Unicity of best approximation by second order splines with variable knots, Mathematics of Computation, 32 (1978), 11-25.
[3]	P. L. Chebyshev, Questions about the least quantities related to the approximate representation of functions, Full. Works, USSR Academy of Sciences Publ., Moscow-Leningrad, 2 (1948). (In Russian).
[4]	P. L. Chebyshev, The theory of mechanisms known as parallelograms, Full. Works, USSR Academy of Sciences Publ., Moscow-Leningrad, 2 (1948). (In Russian).
[5]	M. G. Cox, An algorithm for approximating convex functions by means of first - degree splines, Computer J., 14 (1971).
[6]	V. K. Dzyadyk, "Introduction to the Theory of Uniform Approximation of Functions by Polynomials," Nauka, Moscow, 1977. (In Russian).
[7]	E. A. Fedosov, The programs of development of systems of air traffic management in Europe and the U. S. SESAR and NextGen (Analytical review of the materials of foreign sources of information), General Editor (O. V. Degtyaryov and I. F. Zubkova compilers), State Scientific Center of Russian Federation State Scientific-Research Institute of Aviation Systems Federal State Unitary Enterprise (FSUE) GosNIIAS, Moscow, (2011), 256. (In Russian).
[8]	V. V. Filatov, On Chebyshev approximation by cubic splines, Computer Systems, (56), Mathem. Institute, Siberian Branch of the USSR AS, Novosibirsk, 1973. (In Russian).
[9]	A. I. Grebennikov, "The Method of Splines and Solving Ill-posed Problems in Approximation Theory," Lomonosov MSU Press, Moscow, 1983. (In Russian).
[10]	K. Ichida and T. Kiuopo, Segmentation of planar curve, Electronics and Communication in Japan, 58-d (1975).
[11]	V. K. Isaev, "Geometrical Fundamentals of the CAE/CAD/CAM-system for Wind Tunnel Models," Doctoral Dissertation, TsAGIMAI, Moscow, 1991. (In Russian).
[12]	V. K. Isaev, Pontryagin maximum principle and controlled processes of Hermitian interpolation, Modern problems of mathematics, mathematical analysis, algebra, topology. Dedicated to academician L. S. Pontryagin to his 75 anniversary, Steklov mathematical institute Proceedings, Science, Moscow, 167 (1985), 156-166. (In Russian).
[13]	V. K. Isaev, To the theory of optimal splines, Applied Mathematics and Computation (Special Issue in Honor of George Leitmann on his 86th Birth year), 217 (2010), 1095-1109.doi: 10.1016/j.amc.2010.05.051.
[14]	V. K. Isaev, B. Kh. Davidson, E. N. Khobotov and V. V. Zolotukhin, On construction of multi-level intellectual air traffic management system, Proceedings of the Third International Conference "Managing the multi-large systems development MLSD'2009," V. A. Trapeznikov Institute of control problems of RAS (October 5-9, 2009, Moscow, Russia), Moscow, I (2009), 290-292. (In Russian).
[15]	V. K. Isaev and G. Leitmann, Brief comments on the half-centennial history (1957-2007), Differential Equations and Topology: International conference dedicated to the Centennial Anniversary of L. S. Pontryagin (1908-1988), Theses of lectures, MAX Press, Moscow, (2008), 255-256.
[16]	V. K. Isaev and S. A. Plotnikov, On approximation of functions by splines of the first degree, Methods of spline functions in numerical analysis (Computer Systems), Mathem. Institute, Siberian Branch of the USSR AS, Novosibirsk, (1983), 27-34. (In Russian).
[17]	V. K. Isaev and S. A. Plotnikov, The algorithm of polygonal approximation to a given accuracy and a minimal number of nodes, Recent advances in the machining of curved surfaces on CNC machines, LDNTP Press, Leningrad, (1983), 42-47. (In Russian).
[18]	V. K. Isaev and S. A. Plotnikov, The inverse problem of optimal Chebyshev approximation of geometric information, Trudy TsAGI, 2344 (1987), 3-40.
[19]	V. K. Isaev and S. A. Plotnikov, The reverse Chebyshev problem and Chebyshev splines, Optimal control and differential equations: To the seventieth anniversary from the day of birth of academician E. F. Mishchenko, Proceed. MIRAN 211, Science, Fizmatlit, Moscow, (1995), 164-185, (In Russian).
[20]	V. K. Isaev, S. A. Plotnikov, V. P. Sitnikov and N. V. Shcherbakov, "Some Problems of Optimization of Trajectories Machining Parts with Complex Technical Forms," Experience and prospects for effective use of technological equipment with CNC, LDNTP Press, Leningrad, 1982. (In Russian).
[21]	V. K. Isaev, V. P. Sitnikov, V. A. Sukhnev, I. G. Karimullin, S. V. Skorodumov, V. V. Sonin, V. V. Lubashevskiy, O. E. Baryshnikov, V. E. Zaytsev, E. N. Khobotov, L. I. Shustova and V. M. Platov, Research on creation of the CAE/CAD/CAM-system for wind tunnel models in TsAGI: ASIM (1970-1980), ASIM+ (1980-1992), Problems of creation of perspective air-space technique, Fizmatlit, Moscow, (2005), 498-502. (In Russian).
[22]	V. K. Isaev and V. V. Zolotukhin, Some problems of 2D-maneuvering to ensure the vortex safety of an aircraft, Aerospace MAI Journal, 16 (2009), 5-10. (In Russian).
[23]	V. K. Isaev and V. V. Zolotukhin, Construction of plane maneuvers the aircrafts to ensure the air traffic safety, Proceedings on the VIII Internatonal conference on nonequilibrium processes in nozzles and jets (NPNJ 2010) (May, 25-31 2010 Alushta), MAI-PRINT Publishing House, Moscow, (2010), 489-490. (In Russian).
[24]	V. K. Isaev and V. V. Zolotukhin, Construction of plane maneuvers the aircrafts to ensure air traffic safety, X All-Russian Congress on the fundamental problems of theoretical and applied mechanics. (Nizhny Novgorod, August, 24-30, 2011) Nizhny Novgorod, IV (2011), 441-442. (In Russian).
[25]	V. K. Isaev and V. V. Zolotukhin, Intellect air traffic management system based on the Free Flight concept, Managing the development of large-scale systems (MLSD'2011): Proceedings of the V International Conference "Managing the multi-large systems development MLSD'2009", Establishment of the RAS V.A. Trapeznikov Institute of control problems (October, 3-5, 2011, Moscow, Russia), Moscow, I (2011), 39-41. (In Russian).
[26]	V. K. Isaev and V. V. Zolotukhin, The basics of construction a multi-level intellectual air traffic management system based on the concept of free flight, Proceedings of the XVII International Conference on Computational Mechanics and Modern Applied Software Syste ms (CMMASS'2011), (Alushta, 25-31 May, 2011), Moscow, MAI-PRINT Publishing House, (2011), 749-751. (In Russian).
[27]	H. M. Johnson and A. A. Uogt, Geometric method for approximating convex arc, SIAM J. Appl. Math., 38 (1980), 317-325.doi: 10.1137/0138027.
[28]	Yu. L. Ketkov, On optimal methods of piecewise linear approximation, Proceedings of the USSR universities, Radiophysics, 9 (1966), 1202-1209. (In Russian).
[29]	A. K. Khmelyov, "The Methods of Approximation of Functions and Curves by Splines with a Minimum Number of Nodes and Applications to the problem of design surface of the wind tunnel models," PhD thesis, TsAGI, 1989. (In Russian).
[30]	Yoshisuke Kirozumi and W. A. Dawis, Poligonal approximation by minimax method, Computer Graphics and Image Proc., 19 (1982), 248-264.
[31]	N. P. Korneichuk, "Splines in Approximation Theory," Nauka, Moscow, 1984. (In Russian).
[32]	U. Montanari, A note on minimal length polygonal approximation to a digitized contour, Comm. ACM, 13 (1970), 41-47.
[33]	T. Pavlidis, Poligonal approximations by Newton's method, IEEE Trans. Comput., C-26 (1977) 801-807.
[34]	T. Pavlidis and S. L. Horowitz, Segmentation of plane curves, IEEE Trans. Comput., C-23 (1974), 860-870.
[35]	G. M. Phillips, Algorithms for piecewise straight line approximations, Computer J., 11 (1968), 110-111.
[36]	S. A. Plotnikov, "Development of Methods for Optimal Approximation of Geometric Information in the CNC Systems," PhD thesis, MIPT, 1986. (In Russian).
[37]	S. A. Plotnikov, On the optimal approximation to a given accuracy of the trajectories of discrete control systems, Depon. VINITI, 3690-82, (In Russian).
[38]	B. A. Popov, The accuracy of approximation by uniform splines (absolute error), PMI UAS, Lviv, (1983), 50. (In Russian).
[39]	B. A. Popov, The accuracy of the approximation by uniform splines (weighted error), PMI UAS, Lviv, (1983), 50. (In Russian).
[40]	B. A. Popov and G. S. Tesler, Approximation of functions for technical applications, Nauk. Thought, Kiev, (1980), 352. (In Russian).
[41]	U. E. Ramer, An iterative procedure for the polygonal approximation of plane curves, Computer Graphics and Image Proc., 1 (1972), 244-256.
[42]	Ey. Ya. Remez, "Fundamentals of Numerical Methods of Chebyshev Approximation," Nauk. Dumka, Kiev, 1969. (In Russian).
[43]	Ey. Ya. Remez, "General Computational Methods of Chebyshev Approximation," UAS Publ., Kiev, 1957. (In Russian).
[44]	Ey. Ya. Remez and Gavrilyuk, Computational design of several approaches to the approximate construction of solutions of Chebyshev problems with nonlinear input parameters, Ukrain Math.J., 12 (1960), (In Russian).
[45]	B. M. Shumilov, On local approximation by splines of first-degree, Methods of Spline Functions (Computing systems), Mathem. Institute, Siberian Branch of the USSR AS, Novosibirsk, 75 (1978), 16-22. (In Russian).
[46]	H. A. Simon, Rational choice and the structure of the environment, Psychological Review, 63 (1956), 129-138.
[47]	J. Sklansky, R. L. Chazin and B. J. Hansen, Minimum perimeter polygons of digitized silhuettes, IEEE Trans. Comput., C.-21 (1972), 445-448.
[48]	J. Sklansky and V. Gonzales, "Fast Polygonal Approximation of Digitized Curves," PRIP Proceed., 1979.
[49]	W. C. Stirling, "Satisficing Games and Decision Making: With Applications to Engineering and Computer Science," Cambridge University Press, Cambridge, 2003.doi: 10.1017/CBO9780511543456.
[50]	I. Tomek, Two algorithms for piecewise liner continuous approximations of functions of one variable, IEEE Trans. Comput., C-23 (1974), 445-448.
[51]	H. Werner, "An Introduction to Nonlinear Splines," Proc. of NATO Advanced Study Institute, Calgary, Dosdrecht, 1979.
[52]	C. M. Williams, An efficient algorithm for the piecewse linear approximation of planar curves, Computer Graphics and Image Proc., 8 (1978), 286-293.
[53]	Yu. S. Zav'yalov, B. I. Kvasov and V. L. Miroshnichenko, "Methods of Spline Functions," Nauka, Moscow, 1980, (In Russian).
[54]	Yu. S. Zav'yalov, V. A. Leus and V. A. Skorospelov, "Splines in Engineering Geometry," Mashinostroenie, 1985, (In Russian).
[55]	V. V. Zolotukhin, Simulation of vortex wakes in the problems of air traffic control, Software and Systems, 1 (2011), 126-129. (In Russian).
[56]	V. V. Zolotukhin, V. K. Isaev and B. Kh. Davidson, Some relevant problems of air traffic management, Proceedings of MIPT, 1 (2009), 94-114. (In Russian).
[57]	V. V. Zolotukhin and V. K. Isaev, Application of the satisficing game theory to construct a system to ensure air traffic safety, Proceedings of the Russian scientific-technical seminar "State and prospects of development of automated systems for planning the using airspace in the Russian Federation (PUAS-2011)", November, 22-24, FSUE "GosNIIAS", GosNIIAS Press, Moscow, (2011), 237-244. (In Russian).
[58]	V. V. Zolotukhin and V. K. Isaev, Methods and models of air traffic management, Problems of Mechanical Engineering, Proceedings of the conference, A. A. Blagonravov Institute of machine sciences of RAS, Moscow, (2008), 231-235. (In Russian).
[59]	V. V. Zolotukhin and V. K. Isaev, Using the theory of coalitional games to avoid conflicts between aircrafts, Proceedings of the 53rd MIPT conference "Modern Problems of Fundamental and Applied Sciences", Part III, Aerophysics and space research, Moscow, MIPT, 2 (2010), 78-79. (In Russian).