مروری بر روش‌های درون‌یابی و تقریب‌سازی

نوع مقاله : مقاله مروری

نویسنده

دانشکده مهندسی عمران، دانشگاه آزاد اسلامی واحد اصفهان (خوراسگان)، اصفهان، ایران

چکیده

در فرایند حل عددی معادلات دیفرانسیل، درون‌یابی توابع هدف حساس‌ترین بخش محاسبات است که بر سرعت و دقت محاسبات تأثیرگذار است. این مقاله با هدف نگرش جامع بر انواع الگوریتم‌های درون‌یابی و بررسی سیر تاریخی ابداع و تکامل آن‌ها به رشته تحریر در آمده است. در این تحقیق روش‌های درون‌یابی بر حسب نوع نمایش جبری آن‌ها دسته‌بندی شده‌اند و الگوریتم‌های زیر مجموعه هر دسته به طور مجزا مورد کنکاش قرار گرفته‌اند. فرایند اجرایی و نحوه انجام محاسبات هر کدام از روش‌ها به اختصار بیان شده است و خواننده جهت مطالعات مفصل و تکمیلی درباره هر کدام از روش‌ها به منابع مرتبط با آن رهنمون شده است. سابقه استفاده از هر روش در علوم کاربردی هم مورد توجه و بررسی قرار گرفته است و قدرت محاسباتی، پایداری عددی و نرخ همگرایی روش‌ها بر اساس همین سوابق کاربردی بیان شده‌اند

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

A Brief Overview of Interpolation Methods

نویسنده [English]

  • Mohamad Najar
Department of Civil Engineering, Isfahan (Khorasgan) Branch, Islamic Azad University, Isfahan, Iran
چکیده [English]

Interpolation and approximation are the most important parts of partial differential equation solution procedures, which significantly affect the cost and the accuracy of the results. This paper is aimed to exhaustively investigate the interpolation algorithms and trace their chronologically developments. The interpolation methods are classified based on their mathematical representation, and then surveyed separately. An abridgement of calculation steps of methods are presented and for details, the reader is referred by the main references. The usage records in applied science and engineering are included and their numerical dominance, stability and convergence rate are discussed

کلیدواژه‌ها [English]

  • numerical methods
  • interpolation
  • approximation
  • meshless methods
  1. Liu G. R., “Moving Beyound the Finite Element Method”, Mesh Free Methods, CRC PRESS, Florida, 2000.
  2. Liu M. B., and Liu G. R., “Smoothed Particle Hydrodynamics (SPH): An Overview and Recent Developments”, Archives of Computational Methods in Engineering, Vol. 17, pp.25-76, 2000.
  3. Lucy L. B., “A Numerical Approach to The Testing of The Fission Hypothesis”, Astronomical Journal, 82(12), pp.1013-1024, 1977.
  4. Gingold R. A. and Monaghan J.J., “Smoothed Particle Hydrodynamics, Theory and Application to Non-Spherical Stars”, Monthly Notices of the Royal Astronomical Society, 181, pp. 375-389, 1977.
  5. Monaghan J. J., “Smoothed Particle Hydrodynamics”, Annual Review of Astronomy and Astrophysics, Vol. 30, pp. 543-574, 1992.
  6. Fulk D.A., and Quinn D.W., “An Analysis of 1-D Smoothed Particle Hydrodynamics Kernels”, Journal of Computational Physics, Vol. 126(1), pp.165–180, 1996.
  7. Liu M.B., Liu G.R., and Lam K.Y., “Constructing Smoothing Functions in Smoothed Particle Hydrodynamics with Applications”, Journal of Computational and Applied Mathematics, Vol. 155(2), pp. 263–284, 2003.
  8. Monaghan J.J., “Why Particle Methods Work”, SIAM (Society for Industrial and Applied Mechanics), 3(4), pp. 422-433, 1982.

9.     Liu W.K., Adee J., Jun S., and Belytschko T., “Reproducing Kernel Particle Methods for Elastic and Plastic Problems”, Advanced Computational Methods for Material Modeling, pp. 175-190, 1993.

  1. Morris J.P., “A Study of the Stability Properties of Smooth Particle Hydrodynamics”, Publication of Astronomical Society of the Australia, Vol. 13(1), pp. 97–102, 1996.
  2. Omang M., Borve S., and Trulsen J., “Alternative Kernel Functions for Smoothed Particle Hydrodynamics in Cylindrical Symmetry”, Shock Waves, 14(4), pp. 293–298, 2005.
  3. Jin H.B., and Ding X., “On Criterions for Smoothed Particle Hydrodynamics Kernels in Stable Field”, Journal of Computational Physics, Vol. 202(2), 699– 709, 2005.
  4. Swegle, J.W., Hicks D.L., and Attaway S.W., “Smoothed Particle Hydrodynamics Stability Analysis”, Journal of Computational Physics, Vol. 116(1), 123– 134, 1995.
  5. Capuzzo-Dolcetta, R., and Di Lisio R., “A Criterion for the Choice of the Interpolation Kernel in Smoothed Particle Hydrodynamics”, Applied Numerical Mathematics, Vol. 34(4), 363–371, 2000.
  6. Monaghan J.J., and Lattanzio J.C., “A Refined Particle Method for Astrophysical Problems”, Astronomy and Astrophysics, Vol. 149(1), 135–143, 1985.
  7. Morris J.P., “Analysis of Smoothed Particle Hydrodynamics with Applications”, Monash University, 1996.
  8. Libersky L. and Petschek A.G., “Smooth Particle Hydrodynamics with Strength of Materials”, Proceedings of Advances in the Free-Lagrange Method (lecture notes in physics), Jackson Lake Lodge, Moran, Wyoming, 248-257, 1990.
  9. Johnson G.R., Peterson E.H. and Stryrk R. A., “Incorporation of an SPH Option into the EPIC Code for a Wide Range of High Velocity Impact Computations”, International Journal of Impact Engineering, Vol. 14, 385-394, 1993.
  10. Randles P.W., and Libersky L.D., “Smoothed Particle Hydrodynamics: Some Recent Improvements and Applications”, Applied Mechanical Engineering, Vol. 139: 1-4, 1996.
  11. Liu W.K., Cgen Y., Jun S., Chen J. S., Belytschko T., Pan C., Uras R. A. and Chang C.T., “Overview and Applications of the Reproducing Kernel Particle Methods”, Archives of Computational Methods in Engineering, 3(1): pp. 3-80, 1996.
  12. Haar, A., “Zur Theorie dr orthogonalen Funktionsysteme”, Mathematische Annelen, 69, pp. 331–371, 1910.
  13. Glowinski, R., Lawton, W.M., Ravachol, M. and Tenenbaum, E., “Wavelets Solution of Linearand Nonlinear Elliptic, Parabolic and Hyperbolic Problems in One Space Dimension”, Computing Methods in Applied Sciences and Engineering, SIAM, Philadelphia, 55–120, 1990.
  14. Liu W.K., Jun S., and Zhang Y.F., “Reproducing Kernel Particle Methods”, International Journal for Numerical Methods in Fluids, 20(8,9), pp. 1081-1106, 1995.
  15. Liu W.K., Chen Y., Chang C.T., and Belytschko T., “Advances in Multiple Scale Kernel Particle Methods”, Computational Mechanics, 18, pp. 73-111, 1996.

25. Liu W.K., Jun S., Sihling D.T., Chen Y., and Hao W., “Multiresolution Reproducing Kernel Particle Method for Computational Fluid Dynamics”, International Journal for Numerical Methods in Fluids, Vol. 24, pp.1391-1415, 1997.

26. Chen J.S., Pan C., Wu C.T., and Liu W.K., “Reproducing Kernel Particle Methods for Large Deformation Analysis of Nonlinear Structures”, Computational Methods in Applied Mechanics and Engineering, Vol. 139, pp. 195-228, 1996.

27. Mosava V., “Reproducing Kernel Particle Method and its Modification”, Mathematica Bohemica, Vol. 4, pp. 383-392, 2009.

28. Babuska I., Banerjee U., and Osborn J.E., “Survey of Meshless and Generalized Finite Element Methods: A Unified Aapproach”, Acta Numerica, Vol. 12, pp. 1–125, 2003.

29. Chen J.S., Pan C., and Wu C.T., “Large Deformation Analysis of Rubber Based on a Reproducing Kernel Particle Methods”, Computational Mechanics, Vol. 19, pp. 211–227, 1997.

30. Li S., and Liu W.K., “Reproducing Kernel Hierarchical Partition of Unity”, International Journal for Numerical Methods in Engineering, Vol. 45, pp. 251–317, 1999.

31. Joyot P., Trunzierb J., and Chinesta F., “Enriched Reproducing Kernel Approximation: Reproducing Functions with Discontinuous Derivatives”, Meshfree Methods for Partial Differential Equation II, Springer, Berlin: pp. 93–107, 2004.

32. Uras R.A., Chang C.T., Chen Y., and Liu W.K., “Multiresolution Reproducing Kernel Particle Methods in Acoustics”, Journal of Computational Acoustics, Vol. 5(1), pp. 71-94, 1997.

33. Walsh J.L., “Some Interpolation Series”, The American Mathematical Monthly, Vol. 41(5), pp. 300-308, 1934.

34. Stigler S.M., “The History of Statistics: The Measurement of Uncertainty Before 1900”, Harvard University Press, ISBN 978-0-674-40340-6., 1986.

35. Jeffrey M.S., “Galton, Pearson, and the Peas: A Brief History of Linear Regression for Statistics Instructors”, Journal of Statistics Education, Vol. 9(3), 2001.

36. Golub G.H., and Loan F.V., “Matrix Computations”, The John Hopkins University Press, Baltimore and London, 1996.

37. Nay R.A., and Uktu S., “An Alternative for the Finite Element Method”, Variational Methods in Engineering, Vol. 1, 1972.

38. Batina J., “A Gridless Euler/Navier-Stokes Solution Algorithm for Complex Aircraft Applications”, American Institute of Aeronautics and Astronautics, 93-0333, Reno NV, Januvary, pp. 11-14, 1993.

39. Cohen A., Davenport M.A., and Leviatan D., “On the Stability and Accuracy of Least Squares Approximations”, Foundations of Computational Mathematics, Vol. 13, pp. 819-834, 2013.

40. Migliorati G., Nobile F., and Tempone R., “Convergence Estimates in Probability and in Expectation for Discrete Least Squares with Noisy Evaluations at Random Points”, Journal of Multivariate Analysis, Vol. 142, pp. 167–182, 2015.

41. Cohen A., and Migliorati G., “Optimal Weighted Least-Squares Methods”, SMAI Journal of Computational Mathematics, Vol. 3, pp. 181-203, 2017.

42. Doostan A., and Hampton j., “Coherence Motivated Sampling and Convergence Analysis of Least Squares Polynomial Chaos Regression”, Computational Methods in Applied Mechanics Engineering, Vol. 290, pp. 73–97, 2015.

43. Jakeman J.D., Narayan A., and Zhou T., “A Christoffel Function Weighted Least Squares Algorithm for Collocation Approximations”, Mathematics of Computation, Vol. 86, pp. 1913–1947, 2017.

44. Solaimon O.M., “Application of Weighted Least Squares Regression in Forecasting”, International Journal of Recent Research in Interdisciplinary Sciences (IJRRIS), Vol. 2(3), pp. 45-54, 2015.

45. Chatterjee S., and Hadi A.S., “Regrassion Analysis by Example”, John Wiley and Sons, 2006

46. Nayroles B., Touzot G., and Villon P., “Generalizing the Finite Element Method: Diffuse Approximation and Diffuse Elements”, Computational Mechanics, Vol. 10, pp. 307-318, 1992.

47. Belytschko T., Lu Y., and Gu L., “Element Free Galerkin Methods”, International Journal for Numerical Methods in Engineering, Vol. 37, pp. 229-256, 1994.

48. Atluri S.N., and Zhu T., “A New Meshless Local Petrov-Galerkin (MLPG) Approach in Computational Mechanics”, Computational Mechanics, Vol. 22, pp. 117-127, 1998.

49. De S., and Bathe K. J., “The Method of Finite Spheres”, Computational Mechanics, Vol. 25, pp. 329-345, 2000.

50. Onate E., Idelson S., Zienkiewicz O.C., and Taylor R.L., “A Finite Point Method in Computational Mechanics Applications to Convective Transport and Fluid Flow”, International Journal for Numerical Methods in Engineering, Vol. 39, pp. 3839-3866, 1996.

51. Onate E., Idelson S., Zienkiewicz O.C., and Taylor R.L., “A Stabilized Finite Point Method for Analysis of Fluid Mechanics Problems”, Computer Methods for Applied Mechanics and Engineering, Vol. 139(1-4), pp. 315-347, 1996.

52. Onate E., Perazzo F., and Miquel J., “A Finite Point Method for Elasticity Problems”, Computers and Structures, Vol. 79, pp. 2151-2163, 2001.

53. Onate E., “Derivation of Stabilized Equations for Advective-Diffusive Transport and Fluid Flow Problems”, Computer Methods in Applied Mechanics and Engineering, Vol. 151(1-2), pp. 233-267, 1998.

54. Lancaster P., and Salkauskas K., “Surfaces Generated by Moving Least Squares Methods”, Mathematics of Computation, Vol. 37(155), pp. 141-158

55. Cleveland W.S., “Visualizing Data, AT & T Bell Laboratories”, Murray Hill, NJ, 1993.

56. Dolbow J., and Belytschko T., “An Introduction to Programming the Meshless Element Free Galerkin Method”, Archives of Computational Methods in Engineering (State of the art reviews), Vol. 5(3), pp. 207-241, 1998.

57. Krongauz Y., and BelytSchko T., “Enforcement of Essential Boundary Conditions in Meshless Approximations Using Finite Elements”, Computer Methods in Applied Mechanics and Engineering, Vol. 131(1-2), pp. 133-145, 1996.

58. BelytSchko T., Krongauz Y., Organ D., Fleming M., and Krysl P., “Meshless Method: An Overview and Recent Developments”, Computer Methods in Applied Mechanics and Engineering, Vol. 139, pp. 3-47, 1996.

  1. Liu G.R., and Gu Y.T., “A Point Interpolation Method for Two Dimensional Solids”, International Journal for Numerical Methods in Engineering, Vol. 50, 937-951, 2001.

60. Liu G.R., and Gu Y.T., “A Matrix Triangularization Algorithm for the Polynomial Point Interpolation Method”, Computer Methods in Applied Mechanics and Engineering, Vol. 192(19), pp. 2269-2295, 2003.

  1. Wang J.G., and Liu G.R., “Radial Point Interpolation Method for Elastoplastic Problems”, Proceeding of 1st International Conference on Structural Stability and Dynamics, December 7-9, Taipei, Taiwan, 703-708, 2000.
  2. Hardy R.L., “Multiquadric Equations of Topography and Other Irregular Surfaces”, Journal of Geophysical Research, Vol. 76(8), 1905-1915, 1971.
  3. Hardy R.L., “Theory and Applications of the Multiquadric-Biharmonic Method 20 Years of Discovery 1968-1988”, Computers and Mathematics with Applications, Vol.19(8,9), 163-208, 1990.
  4. Kansa E.J., “Multiquadrics-A Scattered Data Approximation Scheme with Applications to Computational Fluid Dynamics-I Surface Approximations and Partial Derivative Estimates”, Computers and Mathematics with Applications, Vol. 19(8,9), 127-145, 1990.
  5. Kansa E.J., “Multiquadrics-A scattered Data Approximation Scheme with Applications to Computational Fluid Dynamics-II”, Computers and Mathematics with Applications, Vol. 19(8,9), 147-161, 1990.
  6. Coleman C.J., “On the Use of Radial Basis Functions in the Solution of Elliptic Boundary Value Problems”, Computational Mechanics, Vol. 17, 418-422, 1996.
  7. Sharan M., Kansa E.J., and Gupta S., “Application of the Multiquadric Method for Numerical Solution of Elliptic Partial Differential Equations”, Applied Mathematics and computation, Vol. 84, 275-302, 1997.
  8. Wendland H., “Error Estimates for Interpolation by Compactly Supported Radial Basis Functions of Minimal Degree”, Journal of Approximation Theory, Vol. 93, 258-396, 1998.
  9. Franke C., and Schaback R., “Convergence Order Estimates of Meshless Collocation Methods Using Radial Basis Functions”, Advances in Computational Mathematics, Vol. 8(4), 381–399, 1998.
  10. Cheng A.H.D., Goldberg M.A., Kansa E.J., and Zammito G., “Exponential Convergence and h-c Multiquadric Collocation Method for Partial Differential Equations”, Numerical Methods for Partial Differential Equations, Vol.19(5), 571–694, 1971.
  11. Felipe M.A.A., “Radial Basis Functions and Related Models”, Signal Processing, Vol. 45, 37-58, 1995.
  12. Wang J.G., and Liu G.R., “A Point Interpolation Meshless Method Based on Radial Basis Functions”, International Journal for Numerical Methods in Engineering, Vol. 54(11), 1623-1648, 2002.
  13. Shepard D., “A Two-Dimensional Interpolation Function for Irregularly-Spaced Data”, Proceedings of the 23rd National Conference ACM, 517-523, 1968.
  14. Wendland H., “Scattered Data Approximation”, Cambridge University Press, Cambridge, 2005.
  15. Cavoretto R., “Two and Three Dimensional Partition of Unity Interpolation by Product-Type Functions”, Applied Mathematics and Information Science, Vol. 9(1), 1-8, 2015.
  16. Melenk J.M., and Babuska I., “The Partition of Unity Finite Element Method: Basic Theory and Applications”, Computer Methods in Applied Mechanics and Engineering, Vol. 139, 289-314, 1996.
  17. Babuska I., and Melenk J.M., “The Partition of Unity Method”, International Journal for Numerical Methods in Engineering, Vol. 40, 727-758, 1997.
  18. Cavoretto R., “Adaptive Radial Basis Function Partition of Unity Interpolation: A Bivariate Algorithm for Unstructured Data”, Journal of Scientific Computing, Vol. 87(41), 2021.
  19. Junk M., “Do Finite Volume Methods Need a Mesh?”, Meshfree Methods for Partial Differential Equations, 223-238, 2003.
  20. Heryudono A., and Raessi M., “Adaptive Partition of Unity Interpolation Method with Moving Patches”, Mathematics and Computers in Simulation, Vol. 210, 49-65, 2023.
  21. Cavoretto R., DeMarchi S., DeRossi A., Perracchione E., and Santin G., “Partition of Unity Interpolation Using Stable Kernel-Based Techniques”, Applied Numerical Mathematics, Vol. 116, 95-107, 2017.
  22. Piegl L., and Tiller W., “The NURBS Book”, Springer, New York, 1997.
  23. Faux I.D., and Pratt M.J., “Computational Geometry for Design and Manufacture”, Ellis Horwood Ltd., Chichester, 1982.
  24. Mortenson M.E., “Geometric Modeling”, John Wiley, New York, 1985.
  25. Beach R.C., “An Introduction to the Curves and Surfaces of Computer Aided Design”, Van Nostrand Reinhold, New York, 1991.
  26. Su B., and Liu D., “Computational Geometry- Curves and Surface Modeling”, Academic Press, Boston, 1989.
  27. Rogers D.F., and Adams J.A., “Mathematical Elements for Computer Graphics”, McGraw-Hill, New York, 1990.
  28. Gordon W.J., and Riesenfeld R.F., “Bernstein-Bezier Methods for the Computer-Aided Design of Free-Form Curves and Surfaces”, Journal of the Association for Computing Machinery, Vol. 21(2), pp. 293-310, 1974.
  29. Forrest A.R., “Interactive Interpolation and Approximation by Bezier Polynomials”, The Computer Journal, Vol. 15(1), pp. 71-79, 1972.
  30. Farin G.E., “Curves and Surfaces for Computer Aided Geometric Design- A Practical Guide”, Academic Press, Boston, 1993.
  31. Daniel M., and Daubisse J.C., “The Numerical Problem of Using Bezier Curves and Surfaces in the Power Basis”, Computer Aided Geometric Design, Vol. 6, pp. 121-128, 1989.
  32. Lorentz G. G., “Bernstein Polynomials”, Chelsea Publishing Co., New York, 1986.
  33. Schoenberg I.J., “Contributions to the Problem of Approximation of Equidistant Data by Analytic Functions”, Quarterly of Applied Mathematics, Vol. 4, pp. 45-99, 1946.
  34. Ramshaw L., “Blossoming: A Connect-the-Dots Approach to Splines”, Report 19, Digital, System Research Center, Palo Alto, CA, 1987.
  35. Cox M.G., “The Numerical Evaluation of B-Splines”, Journal of the Institute of Mathematics and Its Applications, Vol.10, pp. 134-149, 1972.
  36. De Boor C., “On Calculating with B-Splines”, Journal of Approximation Theory, Vol. 6, pp. 50-62, 1972.

ارتقاء امنیت وب با وف ایرانی