ІНТЕРПОЛЯЦІЯ ТАБЛИЧНИХ ФУНКЦІЙ ВІД ОДНІЄЇ НЕЗАЛЕЖНОЇ ЗМІННОЇ З ВИКОРИСТАННЯМ МНОГОЧЛЕНА ТЕЙЛОРА

https://doi.org/https://doi.org/10.23939/ujit2022.02.001
Надіслано: Жовтень 08, 2022
Прийнято: Жовтень 17, 2022

Цитування за ДСТУ: Грицюк Ю І., Тушницький Р Б. Інтерполяція табличних функцій від однієї незалежної змінної з використанням многочлена Тейлора. Український журнал інформаційних технологій. 2022, т. 4, № 2. С. 01-17.

Citation APA: Hrytsiuk, Yu. I., & Tushnytskyy, R. B. (2022). Interpolation of tabular functions from one independent variable using the Taylor polynomial. Ukrainian Journal of Information Technology, 4(2), 01-17. https://doi.ora/10.23939/uiH2022.02.001

1
Національний університет «Львівська політехніка»
2
Національний університет "Львівська політехніка", м. Львів, Україна

Розроблено методологію локальної інтерполяції табличних функцій від однієї незалежної змінної з використанням многочлена Тейлора n-го степеня в довільно розташованих вузлах інтерполяції, що дає можливість обчислювати їх проміжні значення між вузлами інтерполяції. Проведений аналіз останніх досліджень та публікацій у сфері інтерполяції табличних функцій показав, що основна їх частина – строга теорія інтерполяції, тобто уточнення фундаментальних її математичних положень. Розглянуто деякі особливості інтерполяції табличних функцій від однієї незалежної змінної з використанням многочлена Тейлора n-го степеня, а саме: наведено алгоритм розв'язання та математичне формулювання задачі інтерполяції; наведено її формалізований запис, а також матричний запис процедур інтерполяції для певних значень аргумента. Наведено скалярний алгоритм розв'язання задачі інтерполяції табличних функцій від однієї незалежної змінної з використанням многочлена Тейлора 2-го, 3-го і 4-го степенів, простота й наочність якого є однією з його переваг, але алгоритм незручний для програмної реалізації. Наведено математичне формулювання задачі інтерполяції табличних функцій у термінах матричної алгебри, яке зводиться до виконання таких дій: за відомими з таблиці значеннями вузлових точок потрібно обчислити матрицю Тейлора n-го степеня; за вказаними у таблиці значеннями функції потрібно сформувати вектор-стовпець вузлів інтерполяції; розв'язати лінійну систему алгебричних рівнянь, коренем якої є числові коефіцієнти многочлена Тейлора n-го степеня.

Розроблено метод розрахунку коефіцієнтів інтерполянт, заданих многочленом Тейлора n-го степеня для однієї незалежної змінної, сутність якого зводиться до добутку матриці, оберненої до матриці Тейлора, яку визначають за вузловими точками табличної функції, на вектор-стовпець, який містить значення вузлів інтерполяції. На конкретних прикладах для табличних функцій від однієї незалежної змінної продемонстровано особливості розрахунку коефіцієнтів інтерполянт 2-го, 3-го і 4-го степенів, а також для кожної з них за допомогою матричного методу обчислено інтерпольовані значення функції у заданих точках. Розрахунки виконано в середовищі Excel, які за аналогією можна успішно реалізувати й в будь-якому іншому обчислювальному середовищі.

[1]     Alain Le Méhauté. (1993). On Multivariate Hermite Polynomial Interpolation. Series in Approximations and Decompositions. Multivariate Approximation: From CAGD to Wavelets, 179–192. https://doi.org/10.1142/9789814503754_0010

[2]     Andrunyk, V. A., Vysotska, V. A., & Pasichnyk V. V. (Ed.), et al. (2018). Numerical methods in computer science: textbook. Issue 2. Lviv: Novy svit-2000, 536 p. [In Ukrainian].

[3]     Boyko, L. T. (2009). Fundamentals of numerical methods: textbook. Dnipropetrovsk: DNU Publishing House, 244 p. [In Ukrainian].

[4]     Bruno Després, & Maxime Herda. (2020). Computation of Sum of Squares Polynomials from Data Points. SIAM Journal on Numerical Analysis, 58(3). https://doi.org/10.1137/19M1273955

[5]     Chapter 1: Computer Arithmetic. (2019). An Introduction to Numerical Computation, 1–19. https://doi.org/10.1142/9789811204425_0001

[6]     Chapter 1: Fundamentals: Taylor Series. (2022). Numerical Methods for Engineers, 1–16. https://doi.org/10.1142/9789811255267_0001

[7]     Chapter 2: Polynomial Interpolation. (2019). An Introduction to Numerical Computation, 21–54. https://doi.org/10.1142/9789811204425_0002

[8]     Chapter 3: Newton–Raphson Algorithms and Interpolation. (2017). Computational Physics, 23–29. https://doi.org/10.1142/9789813200227_0003

[9]     Chapter 6: Applications of Power Series. (2015). Foundations in Applied Nuclear Engineering Analysis, 153–169. https://doi.org/10.1142/9789814630948_0006

[10]  Chui, C. K., & Schumaker, L. L. (1995). Approximation and Interpolation. Wavelets and Multilevel Approximation (Vol. 1). Series in Approximations and Decompositions. Approximation Theory VIII, 1–606. https://doi.org/10.1142/9789814532594

[11]  DAzevedo, E. F., & Simpson, R. B. (1989). On Optimal Interpolation Triangle Incidences. SIAM Journal on Scientific and Statistical Computing, 10(6). https://doi.org/10.1137/0910064

[12]  Duan, Qi, Zhang, Yunfeng, & Twizell, E. H. (2005). A new C2 rational interpolation based on function values and constrained control of the interpolant curves. Applied Mathematics and Computation, 161(1), 311 p. https://doi.org/10.1016/j.amc.2003.12.030

[13]  Duan, Qi, Zhang, Yunfeng, & Twizell, E. H. (2005). A new weighted rational cubic interpolation and its approximation. Applied Mathematics and Computation, 168(2), 990 p. https://doi.org/10.1016/j.amc.2004.09.041

[14]  Duan, Qi, Zhang, Yunfeng, & Twizell, E. H. (2006). A bivariate rational interpolation and the properties. Applied Mathematics and Computation, 179(1), 190 p. https://doi.org/10.1016/j.amc.2005.11.094

[15]  Duan, Qi, Zhang, Yunfeng, & Twizell, E. H. (2008). Hermite interpolation by piecewise rational surface. Applied Mathematics and Computation, 198(1), 59 p. https://doi.org/10.1016/j.amc.2007.08.050

[16]  Fan Zhang, Jinjiang Li, Peiqiang Liu, & Hui Fan. (2020). Computing knots by quadratic and cubic polynomial curves. Computational Visual Media, 6(4), 417–430. https://doi.org/10.1007/s41095-020-0186-4

[17]  Faul, A. C., Goodsell, G., & Powell, M. J. D. (2005). A Krylov subspace algorithm for multiquadric interpolation in many dimensions. IMA Journal of Numerical Analysis, 25(1), 1–24. https://doi.org/10.1093/imanum/drh021

[18]  Filts, R. V. (1994). Calculation of Taylor and Fourier polynomials and their derivatives. Synopsis of lectures on the subject "Mathematical problems of electromechanics" for students. special 1801 "Electromechanics". Lviv: State University "Lviv Polytechnic", 24 p. [In Ukrainian].

[19]  Filts, R. V., & Kotsyuba, M. V. (1988). The program of natural power interpolation and differentiation of a tabular function of several independent variables. Kyiv, Deposited with RFAP. INB.NAn0223. [In Russian].

[20]  Filts, R. V., & Kotsyuba, M. V. (1989). Calculation of two-dimensional magnetic fields by the collocation method using the theory of natural interpolation. Izvestiya vuzov. Electromechanics, 3, 5–12. [In Russian].

[21]  Filts, R. V., Kotsyuba, M. V., & Grytsyuk, Yu. I. (1991). Algorithm for computing the Taylor polynomial and its derivatives on a computer. Izvestia of universities. Electromechanics, 5, 5–10. [In Russian].

[22]  Giampietro Allasia, & CesareBracco. (2011). Two interpolation operators on irregularly distributed data in inner product spaces. Journal of Computational and Applied Mathematics, 235(4), 1763 p. https://doi.org/10.1016/j.cam.2010.04.025

[23]  Goodman, T. N. T., & Meek, D. S. (2007). Planar interpolation with a pair of rational spirals. Journal of Computational and Applied Mathematics, 201(1), 112 p. https://doi.org/10.1016/j.cam.2006.02.003

[24]  Harim, N. A., & Abdul Karim, S. A. (2021). Positivity Preserving Using C2 Rational Quartic Spline Interpolation. In: Abdul Karim, S. A., Abd Shukur, M. F., Fai Kait, C., Soleimani, H., Sakidin, H. (Eds). Proceedings of the 6th International Conference on Fundamental and Applied Sciences. Springer Proceedings in Complexity. Springer, Singapore. https://doi.org/10.1007/978-981-16-4513-6_46

[25]  Hashemi, B., & Trefethen, L. N. (2017). Chebfun in three dimensions. SIAM Journal on Scientific Computing, 39, 341–363. Retrieved from: https://drive.google.com/file/d/1Iv2eukbtCIPc8R7HN1mEbzmELaD1tu9T/view

[26]  Hrytsiuk, Yu. I. (2014). Computational methods and models in scientific research: monograph. Lviv: LSU BZD Publishing House. 288 p. [In Ukrainian].

[27]  Hrytsiuk, Yu. I., & Havrysh, V. I. (2022). Interpolation of table-given functions by Fourier polynomial. Scientific Bulletin of UNFU, 32(4), 88–102. https://doi.org/10.36930/40320414

[28]  Hussain, Malik Zawwar, & Muhammad Sarfraz. (2008). Positivity-preserving interpolation of positive data by rational cubics. Journal of Computational and Applied Mathematics, 218(2), 446 p. https://doi.org/10.1016/j.cam.2007.05.023

[29]  Jared L. Aurentz, Anthony P. Austin, Michele Benzi, & Vassilis Kalantzis. (2019). Stable Computation of Generalized Matrix Functions via Polynomial Interpolation. SIAM Journal on Matrix Analysis and Applications, 40(1). https://doi.org/10.1137/18M1191786

[30]  Jin Xie, & Xiaoyan Liu. (2021). Adjustable Piecewise Quartic Hermite Spline Curve with Parameters. Mathematical Problems in Engineering, 2021, Article ID 2264871, 6 p. https://doi.org/10.1155/2021/2264871

[31]  Kolesnytskyi, O. K., Arsenyuk, I. R., & Mesyura, V. I. (2017). Numerical methods: tutorial. Vinnytsia: VNTU, 130 p. [In Ukrainian].

[32]  Krylyk, L. V., Bogach, I. V., & Lisovenko, A. I. (2019). Numerical Methods. Numerical integration of functions: tutorial. Vinnytsia: VNTU, 74 p. [In Ukrainian].

[33]  Krylyk, L. V., Bogach, I. V., & Prokopova, M. O. (2013). Computational mathematics. Interpolation and approximation of tabular data: tutorial. Vinnytsia: VNTU, 111 p. [In Ukrainian].

[34]  Krystyna STYš, & Tadeusz STYš. (2014). Natural and Generalized Interpolating Polynomials, 27–62 (32). https://doi.org/10.2174/9781608059423114010005

[35]  Kvetny, R. N., Dementiev, V. Yu., Mashnytskyi, M. O., & Yudin, O. O. (2009). Difference methods and splines in multidimensional interpolation problems: monograph. Vinnytsia: Universum-Vinnytsia, 92 p. [In Ukrainian].

[36]  Kvyetny, R. N., & Bogach, I. V. (2003). Interpolation of a function of two variables by the Lagrange method. Bulletin of the Vinnytsia Polytechnic Institute, 6, 365–368. [In Ukrainian].

[37]  Kvyetny, R. N., Kostrova, K. Yu., & Bogach, I. V. (2005). Interpolation by self-similar sets: monograph. Vinnytsia: Universum-Vinnytsia, 100 p. [In Ukrainian].

[38]  Malik Zawwar Hussain, & Muhammad Sarfraz. (2008). Positivity-preserving interpolation of positive data by rational cubics. Journal of Computational and Applied Mathematics, 218(2), 446–458. https://doi.org/10.1016/j.cam.2007.05.023

[39]  Mamchuk, V. I. (2015). Numerical methods: tutorial. Kyiv: National Aviation University, 388 p. [In Ukrainian].

[40]  Martin Berzins. (2000). A Data-Bounded Quadratic Interpolant on Triangles and Tetrahedra. SIAM Journal on Scientific Computing, 22(1). https://doi.org/10.1137/S1064827597317636

[41]  Mikhailets, V. A., & Murach, A. A. (2010). Hörmander spaces, interpolation and elliptic problems. With a preface by Yu. M. Berezansky. Kyiv: IM NAS of Ukraine, 370 p. [In Russian].

[42]  Min Hu, & Jieqing Tan. (2006). Adaptive osculatory rational interpolation for image processing. Journal of Computational and Applied Mathematics, 195(1-2), 46 p. https://doi.org/10.1016/j.cam.2005.07.011

[43]  Moskalets, O. F., & Shutko, V. M. (2010). The method of least squares for splines of odd powers. Bulletin of Engineering Academy of Ukraine, 2, 224. [In Ukrainian].

[44]  Nail A. Gumerov, & Ramani Duraiswami. (2007). Fast Radial Basis Function Interpolation via Preconditioned Krylov Iteration. SIAM Journal on Scientific Computing, 29(5). https://doi.org/10.1137/060662083

[45]  Nekrasov, O. N., & Mirmovich, E. G. (2010). Interpolation and approximation of data by polynomials of power, exponential and trigonometric types. Scientific and educational problems of civil protection, 4, 23–27. [In Russian].

[46]  Pahirya, M. M. (1994). Interpolation of functions by a chained fraction and a branched chained fraction of a special type. Scientific Bulletin of Uzhhorod University. Ser. Mathematical, 1, 72–79. [In Ukrainian].

[47]  Petukh, A. M., Obidnyk, D. T., & Romanyuk, O. N. (2007). Interpolation in problems of contour formation: monograph. Vinnytsia: VNTU, 104 p. [In Ukrainian].

[48]  Philip J. Rasch, & David L. Williamson. (1990). On Shape-Preserving Interpolation and Semi-Lagrangian Transport. SIAM Journal on Scientific and Statistical Computing, 11(4). https://doi.org/10.1137/0911039

[49]  Qinghua Sun, Fangxun Bao, Yunfeng Zhang, & Qi Duan. (2013). A bivariate rational interpolation based on scattered data on parallel lines. Journal of Visual Communication and Image Representation, 24(1), 75–80. https://doi.org/10.1016/j.jvcir.2012.11.003

[50]  Qiyuan Pang, Kenneth L. Ho, & Haizhao Yang. (2020). Interpolative Decomposition Butterfly Factorization. SIAM Journal on Scientific Computing, 42(2). https://doi.org/10.1137/19M1294873

[51]  Romanyuk, O. N., Romanyuk, O. V., & Velychko M. O. (2020). Analysis of circular interpolation methods. The 12 th International scientific and practical conference "Impact of Modernity on Science and Practice" (12-13 April, 2020), 572–574. Edmonton, Canada 2020.

[52]  Sarfraza, M., Hussain, & Malik Zawwar. (2006). Data visualization using rational spline interpolation. Journal of Computational and Applied Mathematics, 189(1-2), 513 p. https://doi.org/10.1016/j.cam.2005.04.039

[53]  Sergey Dolgov, Daniel Kressner, & Christoph Strössner. (2021). Functional Tucker Approximation Using Chebyshev Interpolation. SIAM Journal on Scientific Computing, 43(3). https://doi.org/10.1137/20M1356944

[54]  Sheehan Olver, & Yuan Xu. (2021). Orthogonal structure on a quadratic curve. IMA Journal of Numerical Analysis, 41(1), 206–246. https://doi.org/10.1093/imanum/draa001

[55]  Stefan Jakobsson, Bjorn Andersson, & Fredrik Edelvik. (2009). Rational radial basis function interpolation with applications to antenna design. Journal of Computational and Applied Mathematics, 233(4), 889 p. https://doi.org/10.1016/j.cam.2009.08.058

[56]  Stephen M. Robinson. (1979). Quadratic Interpolation is Risky. SIAM Journal on Numerical Analysis, 16(3). https://doi.org/10.1137/0716030

[57]  Taylor Series and Power Series. (2008). Applications and Computation Complex Analysis, 63–71. https://doi.org/10.1142/9789812811080_0011

[58]  Tsegelyk, H. G. (2004). Numerical methods: textbook for university students. Lviv National University named after Ivan Franko. Lviv, 407 p. [In Ukrainian].

[59]  Tyada, K. R., Chand, A. K. B., & Sajid, M. (2021). Shape preserving rational cubic trigonometric fractal interpolation functions. Mathematics and Computers in Simulation, 190, 866–891. https://doi.org/10.1016/j.matcom.2021.06.015

[60]  Volontyr, L. O., Zelinska, O. V., Potapova, N. A., & Chikov, I. A. (2020). Numerical methods: tutorial. Vinnytsia NAU. Vinnytsia: VNAU, 322 p. [In Ukrainian].

[61]  Winfield, D. (1973). Function Minimization by Interpolation in a Data Table. IMA Journal of Applied Mathematics, 12(3), 339–347. https://doi.org/10.1093/imamat/12.3.339

[62]  Yang Jing, & Han Xu-li. (2019). Robust Uniform B-Spline Models for Interpolating Interval Data. Journal of Graphics, 40(3), 429–434. http://www.txxb.com.cn/EN/10.11996/JG.j.2095-302X.2019030429

[63]  Yaroshenko, O. I., & Grihorkiv, M. V. (2018). Numerical methods: tutorial. Chernivtsi: Chernivtsi National University, 172 p. [In Ukrainian].

[64]  Youtian Tao, & Dongyin Wang. (2015). A bivariate rational cubic interpolating spline with biquadratic denominator. Applied Mathematics and Computation, 264(1), 366–377. https://doi.org/10.1016/j.amc.2015.04.100

[65]  Zhu, Y., & Wang, M. (2020). A class of C1 rational interpolation splines in one and two dimensions with region control. Journal of Computational and Applied Mathematics, 39, 69. https://doi.org/10.1007/s40314-020-1067-2

[66]  Zhuo Liu, Shengjun Liu & Yuanpeng Zhu. (2021). C2 Rational Interpolation Splines with Region Control and Image Interpolation Application. Journal of Mathematical Imaging and Vision, 63, 394–416. https://doi.org/10.1007/s10851-020-01005-z