Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Optimal anisotropic meshes for minimizing interpolation errors in $ L^p$-norm


Authors: Long Chen, Pengtao Sun and Jinchao Xu
Journal: Math. Comp. 76 (2007), 179-204
MSC (2000): Primary 41A25, 41A50, 65M15, 65M50, 65M60, 65N15, 65M30, 65M50
DOI: https://doi.org/10.1090/S0025-5718-06-01896-5
Published electronically: September 15, 2006
MathSciNet review: 2261017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we present a new optimal interpolation error estimate in $ L^p$ norm ( $ 1\leq p\leq \infty$) for finite element simplicial meshes in any spatial dimension. A sufficient condition for a mesh to be nearly optimal is that it is quasi-uniform under a new metric defined by a modified Hessian matrix of the function to be interpolated. We also give new functionals for the global moving mesh method and obtain optimal monitor functions from the viewpoint of minimizing interpolation error in the $ L^p$ norm. Some numerical examples are also given to support the theoretical estimates.


References [Enhancements On Off] (What's this?)

  • 1. S. Adjerid and J. E. Flaherty.
    A moving-mesh finite element method with local refinement for parabolic partial differential equations.
    Comp. Meht. Appl. Mech. Engry., 55:3-26, 1986. MR 0845411 (87h:65187)
  • 2. A. Agouzal, K. Lipnikov, and Y. Vassilevski.
    Adaptive generation of quasi-optimal tetrahedral meshes.
    East-West J. Numer. Math., 7:223-244, 1999. MR 1738437 (2000i:65204)
  • 3. A. Agouzal and Y. Vassilevski.
    On a discrete Hessian recovery for $ {P}_1$ finite elements.
    J. Numer. Math., 10:1-12, 2002. MR 1905846 (2003c:65137)
  • 4. T. Apel.
    Anisotropic finite elements: Local estimates and applications.
    Book Series: Advances in Numerical Mathematics. Stuttgart: Teubner, 1999.MR 1716824 (2000k:65002)
  • 5. T. Apel, M. Berzins, P. K. Jimack, G. Kunert, A. Plake, I. Tsukerman, and M. Walkley.
    Mesh shape and anisotropic elements: Theory and practice.
    In J. R. Whiteman (ed. ): The Mathematics of Finite Elements and Applications X, Elsevier, Amsterdam,, pages 367-376, 2000. MR 1801989 (2001j:65180)
  • 6. T. Apel, S. Grosman, P. K. Jimack, and A. Meyer.
    A new methodology for anisotropic mesh refinement based upon error gradients. Appl. Numer. Math., 50(3-4):329-341, 2004.MR 2074008
  • 7. T. Apel and J. Schoberl.
    Multigrid methods for anisotropic edge refinement.
    SIAM Journal on Numerical Analysis, 40(5):1993-2006, 2000. MR 1950630 (2003m:65225)
  • 8. D. C. Arney and J. E. Flaherty.
    An adaptive mesh-moving and local refinement method for time-dependentt partial differential equatioins.
    ACM Trans. Math. Software, 16:48-71, 1990. MR 1073410 (91f:65154)
  • 9. I. Babuška and W. C. Rheinboldt.
    Error estimates for adaptive finite element computations.
    SIAM Journal on Numerical Analysis, 15:736-754, 1978. MR 0483395 (58:3400)
  • 10. I. Babuška and T. Strouboulis.
    The Finite Element Method and Its Reliability.
    Numerical Mathematics and Scientific Computation, Oxford Science Publications, 2001.MR 1857191 (2002k:65001)
  • 11. R. E. Bank and A. H. Sherman.
    An adaptive multilevel method for elliptic boundary value problems.
    Computing, 26:91-105, 1981.MR 0619932 (83c:65229)
  • 12. R. E. Bank, A. H. Sherman, and A. Weiser.
    Refinement algorithms and data structures for regular local mesh refinement.
    In R. S. et al., editor, Scientific Computing, pages 3-17. IMACS/North-Holland Publishing Company, Amsterdam, 1983. MR 0751598
  • 13. R. E. Bank and J. Xu.
    Asymptotically exact a posteriori error estimators, Part I: Grids with superconvergence.
    SIAM Journal on Numerical Analysis, 41(6):2294-2312, 2003. MR 2034616 (2004k:65194)
  • 14. R. E. Bank and J. Xu.
    Asymptotically exact a posteriori error estimators, Part II: General unstructured grids.
    SIAM Journal on Numerical Analysis, 41(6):2313-2332, 2003. MR 2034617 (2004m:65212)
  • 15. G. Beckett, J. A. Mackenzie, A. Ramage, and D. M. Sloan.
    Computational solution of two-dimensional unsteady PDEs using moving mesh methods.
    J. Comput. Phys., 182(2):478-495, November 2002. MR 1941849 (2003m:65169)
  • 16. H. Borouchaki, M. J. Castro-Diaz, P. L. George, F. Hecht, and B. Mohammadi.
    Anisotropic adaptive mesh generation in two dimensions for CFD.
    In 5th International Conference On Numerical Grid Generation in Computational Field Simulations, volume 3, pages 197-206. Mississppi State University, 1996.
  • 17. H. Borouchaki, P. L. George, F. Hecht, P. Laug, and E. Saltel.
    Delaunay mesh generation governed by metric specifications. I. algorithms.
    Finite Elem. Anal. Des., 25(1-2):61-83, 1997. MR 1442300 (98c:65163)
  • 18. H. Borouchaki, P. L. George, and B. Mohammadi.
    Delaunay mesh generation governed by metric specifications. II. applications.
    Finite Elem. Anal. Des., 25(1-2):85-109, 1997. MR 1442301 (98c:65164)
  • 19. J. U. Brackbill and J. S. Saltzman.
    Adaptive zoning for singular problems in two dimensions.
    J. Comput. Phys., 46:342-368, 1982. MR 0673707 (84c:65140)
  • 20. W. Cao, W. Huang, and R. D. Russell.
    A study of monitor functions for two dimensional adaptive mesh generation.
    SIAM J. Sci. Comput., 20:1978-1994, 1999. MR 1694650 (2000c:65113)
  • 21. W. Cao, J. Lang, W. Huang, and R. D. Russell.
    A two-dimensional moving finite element method with local refinement based on a posteriori error estimates.
    Appl. Numer. Math., 46:75-94, 2003. MR 1986348 (2004d:65113)
  • 22. G. F. Carey and H. T. Dinh.
    Grading functions and mesh redistribution.
    SIAM Journal on Numerical Analysis, 22(5):1028-1040, 1985. MR 0799126 (86h:65123)
  • 23. H. D. Ceniceros and T. Y. Hou.
    An efficient dynamically adaptive mesh for potentially singular solutions.
    Journal of Computational Physics, 172:609-639, 2001.
  • 24. L. Chen.
    Mesh smoothing schemes based on optimal Delaunay triangulations.
    In 13th International Meshing Roundtable, pages 109-120, Williamsburg, VA, 2004. Sandia National Laboratories.
  • 25. L. Chen.
    New analysis of the sphere covering problems and optimal polytope approximation of convex bodies.
    Journal of Approximation Theory, 133(1):134-145, March 2005. MR 2122271 (2005k:41097)
  • 26. L. Chen, P. Sun, and J. Xu.
    Multilevel homotopic adaptive finite element methods for convection dominated problems.
    In The Proceedings for 15th Conferences for Domain Decomposition Methods, Lecture Notes in Computational Science and Engineering 40, pages 459-468. Springer, 2004.
  • 27. L. Chen, J. Z. Wang, and J. Xu.
    Asymptotically optimal and linear-time algorithm for polygonal curve simplification.
    Submitted to IEEE, 2005.
  • 28. L. Chen and J. Xu.
    Optimal Delaunay triangulations.
    Journal of Computational Mathematics, 22(2):299-308, 2004. MR 2058939 (2005c:41042)
  • 29. L. Chen and J. Xu.
    An optimal streamline diffusion finite element method for a singularly perturbed problem.
    In AMS Contemporary Mathematics Series: Recent Advances in Adaptive Computation, volume 383, pages 236-246, Hangzhou, 2005. MR 2195801
  • 30. L. Chen and J. Xu.
    Stability and accuracy of adapted finite element methods for singularly perturbed problems.
    Submitted to Numer. Math., 2005.
  • 31. E. F. D'Azevedo.
    Optimal triangular mesh generation by coordinate transformation.
    SIAM J. Sci. Statist. Comput., 12:755-786, 1991. MR 1102406 (92a:65041)
  • 32. E. F. D'Azevedo and R. B. Simpson.
    On optimal interpolation triangle incidences.
    SIAM J. Sci. Statist. Comput., 6:1063-1075, 1989. MR 1025475 (91a:65019)
  • 33. C. de Boor.
    Good approximation by splines with variable knots.
    Int. Seines Numer. Math, Birkhauser Verlag, Basel, 21:57-72, 1973.MR 0403169 (53:6982)
  • 34. C. de Boor.
    Good approximation by splines with variables knots II.
    In G. A. Watson, editor, Proceedings of the Eleventh International Conference on Numerical Methods in Fluid Dynamics, volume 363, pages 12-20. Springer-Verlag, Dundee, Scotland, 1974. MR 0431606 (55:4603)
  • 35. Y. Di, R. Li, T. Tang, and P. Zhang.
    Moving mesh finite element methods for the incompressible Navier-Stokes equations.
    SIAM J. Sci. Comput., 26(3):1036-1056, 2005. MR 2126125 (2005j:65107)
  • 36. V. Dolejsi.
    Anisotropic mesh adaptation for finite volume and finite element methods on triangular meshes.
    Computing and Visualization in Science, 1:165-178, 1998.
  • 37. V. Dolejsi.
    Anisotropic mesh adaptation technique for viscous flow simulation.
    East-West Journal of Numerical Mathematics, 1-24,2001, 9(1):1-24, 2001. MR 1839196 (2002c:65164)
  • 38. T. Dupont and Y. Liu.
    Symmetric error estimates for moving mesh galerkin methods for advection-diffusion equations.
    SIAM Journal on Numerical Analysis, 40(3):914-927, 2002. MR 1949398 (2004b:65147)
  • 39. A. S. Dvinsky.
    Adaptive grid generation from harmonic maps on Riemannian manifolds.
    J. Comput. Phys., 95(2):450-476, 1991. MR 1117849 (92e:65162)
  • 40. L. Formaggia and S. Perotto.
    New anisotropic a priori error estimates.
    Numer. Math., 89(4):641-667, 2001. MR 1865506 (2002j:65110)
  • 41. L. Formaggia and S. Perotto.
    Anisotropic error estimates for elliptic problems.
    Numer. Math., pages 67-92, 2003. MR 1971213 (2004c:65127)
  • 42. W. D. Gropp.
    Local uniform mesh refinement with moving grids.
    SIAM J. Sci. Statist. Comput., 8:292-304, 1987. MR 0883772 (88f:65161)
  • 43. W. G. Habashi, M. Fortin, J. Dompierre, M. G. Vallet, D. Ait-Ali-Yahia, Y. Bourgault, M. P. Robichaud, A. Tam, and S. Boivin.
    Anisotropic mesh optimization for structured and unstructured meshes.
    In 28th Computational Fluid Dynamics Lecture Series. von Karman Institute, March 1997.
  • 44. R. Hamilton.
    Harmonic Maps of Manifolds with Boundary, volume 471 of Lecture Notes in Math.
    American Mathematical Society, Springer-Verlag, New York, 1975. MR 0482822 (58:2872)
  • 45. W. Hoffmann, A. H. Schatz, L. B. Wahlbin, and G. Wittum.
    Asymptotically exact a posteriori estimators for the pointwise gradient error on each element in irregular meshes I: A smooth problem and globally quasi-uniform meshes.
    Mathematics of Computation, 70:897-909, 2001. MR 1826572 (2002a:65178)
  • 46. W. Huang.
    Practical aspects of formulation and solution of moving mesh partial differential equations.
    J. Comput. Phys., 171:753-775, 2001. MR 1848733 (2002e:65132)
  • 47. W. Huang.
    Variational mesh adaptation: isotropy and equidistribution.
    J. Comput. Phys., 174:903-924, 2001. MR 1868106
  • 48. W. Huang and R. D. Russell.
    Moving mesh strategy based on a gradient flow equation for two-dimensional problems.
    SIAM J. Sci. Comput., 20:998-1015, 1999. MR 1665654 (99m:65179)
  • 49. W. Huang and W. Sun.
    Variational mesh adaptation II: Error estimates and monitor functions.
    J. Comput. Phys., 184:619-648, 2003. MR 1959407
  • 50. P. Knupp.
    Mesh generation using vector-fields.
    J. Comput. Phys., 119:142-148, 1995. MR 1336033 (96b:65119)
  • 51. G. Kunert.
    A posteriori error estimation for anisotropic tetrahedral and triangular finite element meshes.
    Ph. D. Thesis, 1999.
  • 52. G. Kunert.
    An a posteriori residual error estimator for the finite element method on anisotropic tetrahedral meshes.
    Numer. Math., 86(3):471-490, 2000. MR 1785418 (2001g:65141)
  • 53. G. Kunert.
    A local problem error estimator for anisotropic tetrahedral finite element meshes.
    SIAM Journal on Numerical Analysis, 39(2):668-689, 2001. MR 1860258 (2002g:65145)
  • 54. G. Kunert.
    A posteriori $ l^2$ error estimation on anisotropic tetrahedral finite element meshes.
    IMA Journal of Numerical Analysis, 21(2):503-523, 2001. MR 1825834 (2002a:65162)
  • 55. G. Kunert.
    Toward anisotropic mesh construction and error estimation in the finite element method.
    Numerical Methods for Partial Differential Equations, 18(5):625-648, 2002.MR 1919601 (2003g:65153)
  • 56. G. Kunert.
    A posteriori error estimation for convection dominated problems on anisotropic meshes.
    Math. Meth. Appl. Sci., 26(7):589-617, 2003. MR 1967323 (2004e:65123)
  • 57. G. Kunert and S. Nicaise.
    Zienkiewicz-zhu error estimators on anisotropic tetrahedral and triangular finite element meshes.
    M2AN Math. Model. Numer. Anal., 37(6):1013-1043, 2003. MR 2026406 (2004k:65196)
  • 58. G. Kunert and R. Verfürth.
    Edge residuals dominate a posteriori error estimates for linear finite element methods on anisotropic triangular and tetrahedral meshes.
    Numer. Math., 86(2):283-303, 2000. MR 1777490 (2001i:65127)
  • 59. R. Li, T. Tang, and P. Zhang.
    Moving mesh methods in multiple dimensions based on harmonic maps.
    J. Comput. Phys., 170(2):562-588, July 2001. MR 1844903 (2002e:65139)
  • 60. R. Li, T. Tang, and P. Zhang.
    A moving mesh finite element algorithm for singular problems in two and three space dimensions.
    J. Comput. Phys., 177(2):365-393, April 2002. MR 1897293 (2003c:65093)
  • 61. K. Lipnikov and Y. Vassilevski.
    Optimal triangulations: Existence, approximation and double differentiation of $ {P}_1$ finite element functions.
    Comput. Math. Math. Phys., 43(6):827-835, 2003. MR 1994415 (2004f:65205)
  • 62. K. Lipnikov and Y. Vassilevski.
    Parallel adaptive solution of 3d boundary value problems by hessian recovery.
    Comput. Methods Appl. Mech. Engrg., 192:1495-1513, 2003. MR 1963061
  • 63. K. Lipnikov and Y. Vassilevski.
    Error estimates for Hessian-based mesh adaptation algorithms with control of adaptivity.
    In 13th International Meshing Roundtable, pages 345-351. Sandia National Laboratories, 2004.
  • 64. V. D. Liseikin.
    Grid Generation Methods.
    Springer Verlag, Berlin, 1999. MR 1707310 (2000d:65001)
  • 65. Y. Liu, R. E. Bank, T. F. Dupont, S. Garcia, and R. F. Santos.
    Symmetric error estimates for moving mesh mixed methods for advection-diffusion equations.
    SIAM Journal on Numerical Analysis, 40(6):2270-2291, 2003. MR 1974185 (2004f:65141)
  • 66. J. A. Mackenzie and M. L. Robertson.
    A moving mesh method for the solution of the one-dimensional phase-field equations.
    J. Comput. Phys., 181(2):526-544, Sept. 2002. MR 1927400 (2003h:65111)
  • 67. S. Micheletti, S. Perotto, and M. Picasso.
    Stabilized finite elements on anisotropic meshes :a priori error estimates for the advantion-diffusion and the stokes problem.
    SIAM Journal on Numerical Analysis, 41(3):1131-1162, 2003. MR 2005198 (2004g:65157)
  • 68. J. J. H. Miller, E. O'Riordan, and G. I. Shishkin.
    Fitted Numerical Methods For Singular Perturbation Problems.
    World Scientific, 1996. MR 1439750 (98c:65002)
  • 69. D. S. Mitrinovic, J. E. Pecaric, and V. Volenec.
    Recent Advances in Geometric Inequalities.
    Mathematics and its applications: East European Series 28, 1989. MR 1022443 (91k:52014)
  • 70. E. Nadler.
    Piecewise linear best $ {L}_2$ approximation on triangulations.
    In C. K. Chui, L. L. Schumaker, and J. D. Ward, editors, Approximation Theory, volume V, pages 499-502. Academic Press, 1986. MR 0903679 (88e:41003)
  • 71. M. Picasso.
    An anisotropic error indicator based on zienkiewicz-zhu error estimator:application to elliptic and parabolic problems.
    SIAM J. SCI. COMPUT., 24(4):1328-1355, 2003. MR 1976219 (2004e:65124)
  • 72. M. Picasso.
    Numerical study of the effectivity index for an anisotropic error indicator based on zienkiewicz-zhu error estimator.
    COMMUNICATION IN NUMERICAL METHODS IN ENGINEERING, 19:13-23, 2003.MR 1952014 (2004c:65131)
  • 73. H. Pottmann, R. Krasauskas, B. Hamann, K. Joy, and W. Seibold.
    On piecewise linear approximation of quadratic functions.
    J. Geometry and Graphics, 4(1):31-53, 2000. MR 1789628 (2001i:65022)
  • 74. W. Ren and X. Wang.
    An iterative grid redistribution method for singular problems in multiple dimensions.
    J. Comput. Phys., 159:246-273, 2000. MR 1752617
  • 75. M. C. Rivara.
    Design and data structure for fully adaptive, multigrid finite element software.
    ACM Trans. Math. Soft., 10:242-264, 1984. MR 0791990 (86f:65207)
  • 76. M. C. Rivara.
    Mesh refinement processes based on the generalized bisection of simplices.
    SIAM Journal on Numerical Analysis, 21:604-613, 1984. MR 0744176 (85i:65159)
  • 77. H. G. Roos, M. Stynes, and L. Tobiska.
    Numerical Methods for Singularly Perturbed Differential Equations, volume 24 of Springer series in Computational Mathematics.
    Springer Verlag, 1996. MR 1477665 (99a:65134)
  • 78. R. Schoen and S. Y. Yau.
    On univalent harmonic maps between surfaces.
    Invent. Math., 44:265-278, 1978. MR 0478219 (57:17706)
  • 79. E. G. Sewell.
    Automatic generation of triangulations for piecewise polynomial approximation.
    In Ph. D. dissertation. Purdue Univ., West Lafayette, Ind., 1972.
  • 80. R. B. Simpson.
    Anisotropic mesh transformations and optimal error control.
    Applied Numerical Mathematics, 14:183-198, 1994. MR 1273824
  • 81. J. H. Smith and A. M. Stuart.
    Analysis of continuous moving mesh equations.
    SIAM J. Sci. Statist. Comput, 13:1265-1286, 1992.
  • 82. J. Xu and Z. M. Zhang.
    Analysis of recovery type a posteriori error estimators for mildly structured grids.
    Mathematics of Computation, pages 781-801, 2003. MR 2047081 (2005f:65141)
  • 83. P. A. Zegeling.
    $ r$-refinement for evolutionary PDEs with finite elements or finite differences.
    Appl. Numer. Math., 26B:97-104, January 1998. MR 1602836
  • 84. P. A. Zegeling.
    Moving grid techniques.
    In B. K. S. F. Thompson and N. P. Weatherill, editors, Handbook of Grid Generation, pages 37-1 - 37-18. CRC Press LLC, 1999. MR 1848160 (2002f:65001)
  • 85. Z. M. Zhang and A. Naga.
    A new finite element gradient recovery method: Superconvergence property.
    SIAM J. Sci. Comput., 26(4):1192-1213, 2005. MR 2143481 (2006d:65137)
  • 86. O. C. Zienkiewicz and J. Z. Zhu.
    The superconvergence patch recovery and a posteriori error estimates. Part 1: The recovery techniques.
    International Journal for Numerical Methods in Engineering, 33:1331-1364, 1992.MR 1161557 (93c:73098)
  • 87. O. C. Zienkiewicz and J. Z. Zhu.
    The superconvergence patch recovery and a posteriori error estimates. Part 2: Error estimates and adaptivity.
    International Journal for Numerical Methods in Engineering, 33:1365-1382, 1992.MR 1161558 (93c:73099)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 41A25, 41A50, 65M15, 65M50, 65M60, 65N15, 65M30, 65M50

Retrieve articles in all journals with MSC (2000): 41A25, 41A50, 65M15, 65M50, 65M60, 65N15, 65M30, 65M50


Additional Information

Long Chen
Affiliation: Department of Mathematics, Pennsylvania State University, University Park, Pennsylvania 16802

Pengtao Sun
Affiliation: Department of Mathematics, Pennsylvania State University, University Park, Pennsylvania 16802
Email: sun@math.psu.edu

Jinchao Xu
Affiliation: The School of Mathematical Science, Peking University, Beijing, People’s Republic of China; and Department of Mathematics, Pennsylvania State University, University Park, Pennsylvania 16802
Email: xu@math.psu.edu

DOI: https://doi.org/10.1090/S0025-5718-06-01896-5
Received by editor(s): October 13, 2003
Received by editor(s) in revised form: November 23, 2005
Published electronically: September 15, 2006
Additional Notes: The authors were supported in part by NSF Grant #DMS-0074299 and Center for Computational Mathematics and Applications, Penn State University.
The third author was also supported in part by NSF DMS-0209497 and NSF DMS-0215392 and the Changjiang Professorship through Peking University
Article copyright: © Copyright 2006 American Mathematical Society

American Mathematical Society