Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Analysis of an algorithm for generating locally optimal meshes for $L_2$ approximation by discontinuous piecewise polynomials

Authors: Y. Tourigny and M. J. Baines
Journal: Math. Comp. 66 (1997), 623-650
MSC (1991): Primary 41A30; Secondary 65D15
MathSciNet review: 1397447
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper discusses the problem of constructing a locally optimal mesh for the best $L_2$ approximation of a given function by discontinuous piecewise polynomials. In the one-dimensional case, it is shown that, under certain assumptions on the approximated function, Baines' algorithm [M.J. Baines, Math. Comp., 62 (1994), pp. 645-669] for piecewise linear or piecewise constant polynomials produces a mesh sequence which converges to an optimal mesh. The rate of convergence is investigated. A two-dimensional modification of this algorithm is proposed in which both the nodes and the connection between the nodes are self-adjusting. Numerical results in one and two dimensions are presented.

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

  • 1. T. Apel and B. Heinrich, Mesh refinement and windowing near edges for some elliptic problem, SIAM J. Numer. Anal. 31 (1994), 695-709. MR 95j:65132
  • 2. M.J. Baines, Algorithms for optimal discontinuous piecewise linear and constant $L_2$ fits to continuous functions with adjustable nodes in one and two dimensions, Math. Comput. 62 (1994), 645-669. MR 94g:65015
  • 3. D.L. Barrow, C.K. Chui, P.W. Smith and J.D. Ward, Unicity of best mean approximation by second order splines with variable knots, Math. Comput. 32 (1978), 1131-1143. MR 58:1853
  • 4. A. Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comput. 31 (1977), 333-390. MR 55:4714
  • 5. H. Burchard, On the degree of convergence of piecewise polynomial approximation on optimal meshes, Trans. Am. Math. Soc. 234 (1977), 531-559. MR 58:1857
  • 6. D. Catherall, The adaption of structured grids to numerical solutions for transonic flow, Internat. J. Numer. Meths. Engrg. 32 (1991), 921-937.
  • 7. K. Chen, Error equidistribution and mesh adaption, SIAM J. Sci. Comput. 15 (1994), 798-818. MR 95a:65156
  • 8. P.G. Ciarlet, Introduction à l'Analyse Numérique Matricielle et à l'Optimisation, Masson, Paris, 1982. MR 84c:65002a
  • 9. E.F. D'Azevedo, Optimal triangular mesh generation by coordinate transformation, SIAM J. Sci. Stat. Comput. 12 (1991), 755-786. MR 92a:65041
  • 10. E.F. D'Azevedo and R.B. Simpson, On optimal triangular meshes for minimizing the gradient error, Numer. Math. 59 (1991), 321-348. MR 92c:65095
  • 11. C. de Boor, A Practical Guide to Splines, Springer-Verlag, New York, 1978. MR 80a:65027
  • 12. M. Delfour, G. Payre and J.P. Zolésio, An optimal triangulation for second-order elliptic problems, Comput. Meths. Appl. Mech. Engrg. 50 (1985), 231-261. MR 86j:65151
  • 13. R.A. DeVore and B.J. Lucier, High order regularity for solutions of the inviscid Burgers equation, in Lecture Notes in Mathematics, vol. 1402, Springer-Verlag, New York, 1989, 147-154. MR 90k:35164
  • 14. R.A. DeVore and V.A. Popov, Interpolation spaces and non-linear approximation, in Function Spaces and Applications, M. Cwikel, J. Peetre, Y. Sagher and H. Wallin, eds., Springer Lecture Notes in Mathematics, vol. 1302, Springer-Verlag, New York, 1988, 191-205. MR 89d:41035
  • 15. N. Dyn, D. Levin and S. Rippa, Data dependent triangulations for piecewise linear interpolation, IMA J. Numer. Anal. 10 (1990), 137-154. MR 91a:65022
  • 16. N. Dyn, D. Levin and S. Rippa, Algorithms for the construction of data dependent triangulations, in Algorithms for Approximation, J.C. Mason and M.G. Cox, eds., Chapman and Hall, London, 1990, 185-192. CMP 91:01
  • 17. W. Huang, Y. Ren and R.D. Russell, Moving mesh PDEs based on the equidistribution principle, SIAM J. Numer. Anal. 31 (1994), 709-730. MR 94m:65149
  • 18. W. Huang and D.M. Sloan, A simple adaptive grid method in two dimensions, SIAM J. Sci. Comput. 15 (1994), 776-797. MR 95a:65155
  • 19. D. McGlure, Nonlinear segmented function approximation and analysis of line patterns, Quart. Appl. Math. 33 (1975), 1-37. MR 57:3709
  • 20. E. Nadler, Piecewise linear best $L_2$ approximation on triangulations, in Approximation Theory V, C.K. Chui, L.L. Schumaker, J.D. Ward, eds., Academic Press, Boston, 1986.
  • 21. R.B. Simpson, Anisotropic mesh transformations and optimal error control, Appl. Numer. Math. 14 (1994), 183-198. CMP 94:11
  • 22. J.H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965. MR 32:1894

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 41A30, 65D15

Retrieve articles in all journals with MSC (1991): 41A30, 65D15

Additional Information

Y. Tourigny
Affiliation: School of Mathematics, University of Bristol, Bristol BS8 1TW, United Kingdom

M. J. Baines
Affiliation: Department of Mathematics, University of Reading, P.O. Box 220, Reading RG6 6AF, United Kingdom

Keywords: $L_2$ approximation, discontinuous piecewise polynomials, adjustable nodes, grid generation, triangulation
Received by editor(s): July 27, 1995
Received by editor(s) in revised form: March 13, 1996
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society