Optimal anisotropic meshes for minimizing interpolation errors in 𝐿^{𝑝}-norm

Chen, Long; Sun, Pengtao; Xu, Jinchao

doi:10.1090/S0025-5718-06-01896-5

Optimal anisotropic meshes for minimizing interpolation errors in $L^p$-norm
HTML articles powered by AMS MathViewer

by Long Chen, Pengtao Sun and Jinchao Xu PDF

Math. Comp. 76 (2007), 179-204 Request permission

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

Slimane Adjerid and Joseph E. Flaherty, A moving-mesh finite element method with local refinement for parabolic partial differential equations, Comput. Methods Appl. Mech. Engrg. 55 (1986), no. 1-2, 3–26. MR 845411, DOI 10.1016/0045-7825(86)90083-6
A. Agouzal, K. Lipnikov, and Yu. Vassilevski, Adaptive generation of quasi-optimal tetrahedral meshes, East-West J. Numer. Math. 7 (1999), no. 4, 223–244. MR 1738437
A. Agouzal and Yu. Vassilevski, On a discrete Hessian recovery for $P_1$ finite elements, J. Numer. Math. 10 (2002), no. 1, 1–12. MR 1905846, DOI 10.1515/JNMA.2002.1
Thomas Apel, Anisotropic finite elements: local estimates and applications, Advances in Numerical Mathematics, B. G. Teubner, Stuttgart, 1999. MR 1716824
Th. Apel, M. Berzins, P. K. Jimack, G. Kunert, A. Plaks, I. Tsukerman, and M. Walkley, Mesh shape and anisotropic elements: theory and practice, The mathematics of finite elements and applications, X, MAFELAP 1999 (Uxbridge), Elsevier, Oxford, 2000, pp. 367–376. MR 1801989, DOI 10.1016/B978-008043568-8/50024-9
Thomas Apel, Sergei Grosman, Peter K. Jimack, and Arnd Meyer, A new methodology for anisotropic mesh refinement based upon error gradients, Appl. Numer. Math. 50 (2004), no. 3-4, 329–341. MR 2074008, DOI 10.1016/j.apnum.2004.01.006
Thomas Apel and Joachim Schöberl, Multigrid methods for anisotropic edge refinement, SIAM J. Numer. Anal. 40 (2002), no. 5, 1993–2006. MR 1950630, DOI 10.1137/S0036142900375414
David C. Arney and Joseph E. Flaherty, An adaptive mesh-moving and local refinement method for time-dependent partial differential equations, ACM Trans. Math. Software 16 (1990), no. 1, 48–71. MR 1073410, DOI 10.1145/77626.77631
I. Babuška and W. C. Rheinboldt, Error estimates for adaptive finite element computations, SIAM J. Numer. Anal. 15 (1978), no. 4, 736–754. MR 483395, DOI 10.1137/0715049
Ivo Babuška and Theofanis Strouboulis, The finite element method and its reliability, Numerical Mathematics and Scientific Computation, The Clarendon Press, Oxford University Press, New York, 2001. MR 1857191
R. E. Bank and A. H. Sherman, An adaptive, multilevel method for elliptic boundary value problems, Computing 26 (1981), no. 2, 91–105 (English, with German summary). MR 619932, DOI 10.1007/BF02241777
Randolph E. Bank, Andrew H. Sherman, and Alan Weiser, Refinement algorithms and data structures for regular local mesh refinement, Scientific computing (Montreal, Que., 1982) IMACS Trans. Sci. Comput., I, IMACS, New Brunswick, NJ, 1983, pp. 3–17. MR 751598
Randolph E. Bank and Jinchao Xu, Asymptotically exact a posteriori error estimators. I. Grids with superconvergence, SIAM J. Numer. Anal. 41 (2003), no. 6, 2294–2312. MR 2034616, DOI 10.1137/S003614290139874X
Randolph E. Bank and Jinchao Xu, Asymptotically exact a posteriori error estimators. II. General unstructured grids, SIAM J. Numer. Anal. 41 (2003), no. 6, 2313–2332. MR 2034617, DOI 10.1137/S0036142901398751
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 (2002), no. 2, 478–495. MR 1941849, DOI 10.1006/jcph.2002.7179
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.
Houman Borouchaki, Paul Louis George, Frédéric Hecht, Patrick Laug, and Eric Saltel, Delaunay mesh generation governed by metric specifications. I. Algorithms, Finite Elem. Anal. Des. 25 (1997), no. 1-2, 61–83. Adaptive meshing, Part 1. MR 1442300, DOI 10.1016/S0168-874X(96)00057-1
Houman Borouchaki, Paul Louis George, and Bijan Mohammadi, Delaunay mesh generation governed by metric specifications. II. Applications, Finite Elem. Anal. Des. 25 (1997), no. 1-2, 85–109. Adaptive meshing, Part 1. MR 1442301, DOI 10.1016/S0168-874X(96)00065-0
J. U. Brackbill and J. S. Saltzman, Adaptive zoning for singular problems in two dimensions, J. Comput. Phys. 46 (1982), no. 3, 342–368. MR 673707, DOI 10.1016/0021-9991(82)90020-1
Weiming Cao, Weizhang Huang, and Robert D. Russell, A study of monitor functions for two-dimensional adaptive mesh generation, SIAM J. Sci. Comput. 20 (1999), no. 6, 1978–1994. MR 1694650, DOI 10.1137/S1064827597327656
Jens Lang, Weiming Cao, Weizhang Huang, and Robert D. Russell, A two-dimensional moving finite element method with local refinement based on a posteriori error estimates, Appl. Numer. Math. 46 (2003), no. 1, 75–94. MR 1986348, DOI 10.1016/S0168-9274(03)00013-8
Graham F. Carey and Hung T. Dinh, Grading functions and mesh redistribution, SIAM J. Numer. Anal. 22 (1985), no. 5, 1028–1040. MR 799126, DOI 10.1137/0722061
H. D. Ceniceros and T. Y. Hou. An efficient dynamically adaptive mesh for potentially singular solutions. Journal of Computational Physics, 172:609–639, 2001.
L. Chen. Mesh smoothing schemes based on optimal Delaunay triangulations. In 13th International Meshing Roundtable, pages 109–120, Williamsburg, VA, 2004. Sandia National Laboratories.
Long Chen, New analysis of the sphere covering problems and optimal polytope approximation of convex bodies, J. Approx. Theory 133 (2005), no. 1, 134–145. MR 2122271, DOI 10.1016/j.jat.2004.12.009
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.
L. Chen, J. Z. Wang, and J. Xu. Asymptotically optimal and linear-time algorithm for polygonal curve simplification. Submitted to IEEE, 2005.
Long Chen and Jin-chao Xu, Optimal Delaunay triangulations, J. Comput. Math. 22 (2004), no. 2, 299–308. Special issue dedicated to the 70th birthday of Professor Zhong-Ci Shi. MR 2058939
Long Chen and Jinchao Xu, An optimal streamline diffusion finite element method for a singularly perturbed problem, Recent advances in adaptive computation, Contemp. Math., vol. 383, Amer. Math. Soc., Providence, RI, 2005, pp. 191–201. MR 2195801, DOI 10.1090/conm/383/07164
L. Chen and J. Xu. Stability and accuracy of adapted finite element methods for singularly perturbed problems. Submitted to Numer. Math., 2005.
E. F. D’Azevedo, Optimal triangular mesh generation by coordinate transformation, SIAM J. Sci. Statist. Comput. 12 (1991), no. 4, 755–786. MR 1102406, DOI 10.1137/0912040
E. F. D’Azevedo and R. B. Simpson, On optimal interpolation triangle incidences, SIAM J. Sci. Statist. Comput. 10 (1989), no. 6, 1063–1075. MR 1025475, DOI 10.1137/0910064
Carl de Boor, Good approximation by splines with variable knots, Spline functions and approximation theory (Proc. Sympos., Univ. Alberta, Edmonton, Alta., 1972) Internat. Ser. Numer. Math., Vol. 21, Birkhäuser, Basel, 1973, pp. 57–72. MR 0403169
Carl de Boor, Good approximation by splines with variable knots. II, Conference on the Numerical Solution of Differential Equations (Univ. Dundee, Dundee, 1973) Lecture Notes in Math., Vol. 363, Springer, Berlin, 1974, pp. 12–20. MR 0431606
Yana Di, Ruo Li, Tao Tang, and Pingwen Zhang, Moving mesh finite element methods for the incompressible Navier-Stokes equations, SIAM J. Sci. Comput. 26 (2005), no. 3, 1036–1056. MR 2126125, DOI 10.1137/030600643
V. Dolejsi. Anisotropic mesh adaptation for finite volume and finite element methods on triangular meshes. Computing and Visualization in Science, 1:165–178, 1998.
V. Dolejší, Anisotropic mesh adaptation technique for viscous flow simulation, East-West J. Numer. Math. 9 (2001), no. 1, 1–24. MR 1839196
Todd F. Dupont and Yingjie Liu, Symmetric error estimates for moving mesh Galerkin methods for advection-diffusion equations, SIAM J. Numer. Anal. 40 (2002), no. 3, 914–927. MR 1949398, DOI 10.1137/S0036142900380431
Arkady S. Dvinsky, Adaptive grid generation from harmonic maps on Riemannian manifolds, J. Comput. Phys. 95 (1991), no. 2, 450–476. MR 1117849, DOI 10.1016/0021-9991(91)90285-S
L. Formaggia and S. Perotto, New anisotropic a priori error estimates, Numer. Math. 89 (2001), no. 4, 641–667. MR 1865506, DOI 10.1007/s002110100273
L. Formaggia and S. Perotto, Anisotropic error estimates for elliptic problems, Numer. Math. 94 (2003), no. 1, 67–92. MR 1971213, DOI 10.1007/s00211-002-0415-z
William D. Gropp, Local uniform mesh refinement with moving grids, SIAM J. Sci. Statist. Comput. 8 (1987), no. 3, 292–304. MR 883772, DOI 10.1137/0908036
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.
Richard S. Hamilton, Harmonic maps of manifolds with boundary, Lecture Notes in Mathematics, Vol. 471, Springer-Verlag, Berlin-New York, 1975. MR 0482822
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, Math. Comp. 70 (2001), no. 235, 897–909. MR 1826572, DOI 10.1090/S0025-5718-01-01286-8
Weizhang Huang, Practical aspects of formulation and solution of moving mesh partial differential equations, J. Comput. Phys. 171 (2001), no. 2, 753–775. MR 1848733, DOI 10.1006/jcph.2001.6809
Weizhang Huang, Variational mesh adaptation: isotropy and equidistribution, J. Comput. Phys. 174 (2001), no. 2, 903–924. MR 1868106, DOI 10.1006/jcph.2001.6945
Weizhang Huang and Robert D. Russell, Moving mesh strategy based on a gradient flow equation for two-dimensional problems, SIAM J. Sci. Comput. 20 (1999), no. 3, 998–1015. MR 1665654, DOI 10.1137/S1064827596315242
Weizhang Huang and Weiwei Sun, Variational mesh adaptation. II. Error estimates and monitor functions, J. Comput. Phys. 184 (2003), no. 2, 619–648. MR 1959407, DOI 10.1016/S0021-9991(02)00040-2
P. Knupp, Mesh generation using vector-fields, J. Comput. Phys. 119 (1995), no. 1, 142–148. MR 1336033, DOI 10.1006/jcph.1995.1122
G. Kunert. A posteriori error estimation for anisotropic tetrahedral and triangular finite element meshes. Ph. D. Thesis, 1999.
Gerd Kunert, An a posteriori residual error estimator for the finite element method on anisotropic tetrahedral meshes, Numer. Math. 86 (2000), no. 3, 471–490. MR 1785418, DOI 10.1007/s002110000170
Gerd Kunert, A local problem error estimator for anisotropic tetrahedral finite element meshes, SIAM J. Numer. Anal. 39 (2001), no. 2, 668–689. MR 1860258, DOI 10.1137/S003614299935615X
Gerd Kunert, A posteriori $L_2$ error estimation on anisotropic tetrahedral finite element meshes, IMA J. Numer. Anal. 21 (2001), no. 2, 503–523. MR 1825834, DOI 10.1093/imanum/21.2.503
Gerd Kunert, Toward anisotropic mesh construction and error estimation in the finite element method, Numer. Methods Partial Differential Equations 18 (2002), no. 5, 625–648. MR 1919601, DOI 10.1002/num.10023
Gerd Kunert, A posteriori error estimation for convection dominated problems on anisotropic meshes, Math. Methods Appl. Sci. 26 (2003), no. 7, 589–617. MR 1967323, DOI 10.1002/mma.368
Gerd Kunert and Serge Nicaise, Zienkiewicz-Zhu error estimators on anisotropic tetrahedral and triangular finite element meshes, M2AN Math. Model. Numer. Anal. 37 (2003), no. 6, 1013–1043. MR 2026406, DOI 10.1051/m2an:2003065
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 (2000), no. 2, 283–303. MR 1777490, DOI 10.1007/PL00005407
Ruo Li, Tao Tang, and Pingwen Zhang, Moving mesh methods in multiple dimensions based on harmonic maps, J. Comput. Phys. 170 (2001), no. 2, 562–588. MR 1844903, DOI 10.1006/jcph.2001.6749
Ruo Li, Tao Tang, and Pingwen Zhang, A moving mesh finite element algorithm for singular problems in two and three space dimensions, J. Comput. Phys. 177 (2002), no. 2, 365–393. MR 1897293, DOI 10.1006/jcph.2002.7002
Yu. V. Vasilevskiĭ and K. N. Lipnikov, Optimal triangulations: existence, approximations and double differentiation of $P_1$ finite element functions, Zh. Vychisl. Mat. Mat. Fiz. 43 (2003), no. 6, 866–874 (Russian, with Russian summary); English transl., Comput. Math. Math. Phys. 43 (2003), no. 6, 827–835. MR 1994415
Konstantin Lipnikov and Yuri Vassilevski, Parallel adaptive solution of 3D boundary value problems by Hessian recovery, Comput. Methods Appl. Mech. Engrg. 192 (2003), no. 11-12, 1495–1513. MR 1963061, DOI 10.1016/S0045-7825(02)00654-0
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.
Vladimir D. Liseikin, Grid generation methods, Scientific Computation, Springer-Verlag, Berlin, 1999. MR 1707310, DOI 10.1007/978-3-662-03949-6
Yingjie Liu, Randolph E. Bank, Todd F. Dupont, Sonia Garcia, and Rafael F. Santos, Symmetric error estimates for moving mesh mixed methods for advection-diffusion equations, SIAM J. Numer. Anal. 40 (2002), no. 6, 2270–2291 (2003). MR 1974185, DOI 10.1137/S003614290038073X
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 (2002), no. 2, 526–544. MR 1927400, DOI 10.1006/jcph.2002.7140
Stefano Micheletti, Simona Perotto, and Marco Picasso, Stabilized finite elements on anisotropic meshes: a priori error estimates for the advection-diffusion and the Stokes problems, SIAM J. Numer. Anal. 41 (2003), no. 3, 1131–1162. MR 2005198, DOI 10.1137/S0036142902403759
J. J. H. Miller, E. O’Riordan, and G. I. Shishkin, Fitted numerical methods for singular perturbation problems, World Scientific Publishing Co., Inc., River Edge, NJ, 1996. Error estimates in the maximum norm for linear problems in one and two dimensions. MR 1439750, DOI 10.1142/2933
D. S. Mitrinović, J. E. Pečarić, and V. Volenec, Recent advances in geometric inequalities, Mathematics and its Applications (East European Series), vol. 28, Kluwer Academic Publishers Group, Dordrecht, 1989. MR 1022443, DOI 10.1007/978-94-015-7842-4
C. K. Chui, L. L. Schumaker, and J. D. Ward (eds.), Approximation theory. V, Academic Press, Inc., Boston, MA, 1986. MR 903679
M. Picasso, An anisotropic error indicator based on Zienkiewicz-Zhu error estimator: application to elliptic and parabolic problems, SIAM J. Sci. Comput. 24 (2003), no. 4, 1328–1355. MR 1976219, DOI 10.1137/S1064827501398578
M. Picasso, Numerical study of the effectivity index for an anisotropic error indicator based on Zienkiewicz-Zhu error estimator, Comm. Numer. Methods Engrg. 19 (2003), no. 1, 13–23. MR 1952014, DOI 10.1002/cnm.546
Helmut Pottmann, Rimvydas Krasauskas, Bernd Hamann, Kenneth Joy, and Wolfgang Seibold, On piecewise linear approximation of quadratic functions, J. Geom. Graph. 4 (2000), no. 1, 31–53. MR 1789628
Weiqing Ren and Xiao-Ping Wang, An iterative grid redistribution method for singular problems in multiple dimensions, J. Comput. Phys. 159 (2000), no. 2, 246–273. MR 1752617, DOI 10.1006/jcph.2000.6435
María-Cecilia Rivara, Design and data structure of fully adaptive, multigrid, finite-element software, ACM Trans. Math. Software 10 (1984), no. 3, 242–264. MR 791990, DOI 10.1145/1271.1274
María-Cecilia Rivara, Mesh refinement processes based on the generalized bisection of simplices, SIAM J. Numer. Anal. 21 (1984), no. 3, 604–613. MR 744176, DOI 10.1137/0721042
H.-G. Roos, M. Stynes, and L. Tobiska, Numerical methods for singularly perturbed differential equations, Springer Series in Computational Mathematics, vol. 24, Springer-Verlag, Berlin, 1996. Convection-diffusion and flow problems. MR 1477665, DOI 10.1007/978-3-662-03206-0
Richard Schoen and Shing Tung Yau, On univalent harmonic maps between surfaces, Invent. Math. 44 (1978), no. 3, 265–278. MR 478219, DOI 10.1007/BF01403164
E. G. Sewell. Automatic generation of triangulations for piecewise polynomial approximation. In Ph. D. dissertation. Purdue Univ., West Lafayette, Ind., 1972.
R. B. Simpson, Anisotropic mesh transformations and optimal error control, Proceedings of the Third ARO Workshop on Adaptive Methods for Partial Differential Equations (Troy, NY, 1992), 1994, pp. 183–198. MR 1273824, DOI 10.1016/0168-9274(94)90025-6
J. H. Smith and A. M. Stuart. Analysis of continuous moving mesh equations. SIAM J. Sci. Statist. Comput, 13:1265–1286, 1992.
Jinchao Xu and Zhimin Zhang, Analysis of recovery type a posteriori error estimators for mildly structured grids, Math. Comp. 73 (2004), no. 247, 1139–1152. MR 2047081, DOI 10.1090/S0025-5718-03-01600-4
Paul A. Zegeling, $r$-refinement for evolutionary PDEs with finite elements or finite differences, Proceedings of the International Centre for Mathematical Sciences Conference on Grid Adaptation in Computational PDEs: Theory and Applications (Edinburgh, 1996), 1998, pp. 97–104. MR 1602836, DOI 10.1016/S0168-9274(97)00086-X
Joe F. Thompson, Bharat K. Soni, and Nigel P. Weatherill (eds.), Handbook of grid generation, CRC Press, Boca Raton, FL, 1999. MR 1848160
Zhimin Zhang and Ahmed Naga, A new finite element gradient recovery method: superconvergence property, SIAM J. Sci. Comput. 26 (2005), no. 4, 1192–1213. MR 2143481, DOI 10.1137/S1064827503402837
O. C. Zienkiewicz and J. Z. Zhu, The superconvergent patch recovery and a posteriori error estimates. I. The recovery technique, Internat. J. Numer. Methods Engrg. 33 (1992), no. 7, 1331–1364. MR 1161557, DOI 10.1002/nme.1620330702
O. C. Zienkiewicz and J. Z. Zhu, The superconvergent patch recovery and a posteriori error estimates. II. Error estimates and adaptivity, Internat. J. Numer. Methods Engrg. 33 (1992), no. 7, 1365–1382. MR 1161558, DOI 10.1002/nme.1620330703