Mathematics of Computation

Analysis of an algorithm for generating locally optimal meshes for $L_2$

approximation by discontinuous piecewise polynomials

Author(s): Y. Tourigny; M. J. Baines.
Journal: Math. Comp. 66 (1997), 623-650.
MSC (1991): Primary 41A30; Secondary 65D15
Retrieve article in: PDF
This article is available free of charge

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.

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 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 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

Y. Tourigny
Affiliation: School of Mathematics, University of Bristol, Bristol BS8 1TW, United Kingdom
Email: y.tourigny@bristol.ac.uk

M. J. Baines
Affiliation: Department of Mathematics, University of Reading, P.O. Box 220, Reading RG6 6AF, United Kingdom
Email: m.baines@reading.ac.uk

DOI: 10.1090/S0025-5718-97-00823-5
PII: S 0025-5718(97)00823-5
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
Copyright of article: Copyright 1997, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS