Analysis of an algorithm for generating locally optimal meshes for 𝐿₂ approximation by discontinuous piecewise polynomials

Tourigny, Y.; Baines, M.

doi:10.1090/S0025-5718-97-00823-5

Analysis of an algorithm for generating locally optimal meshes for $L_2$ approximation by discontinuous piecewise polynomials
HTML articles powered by AMS MathViewer

by Y. Tourigny and M. J. Baines PDF

Math. Comp. 66 (1997), 623-650 Request permission

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

Th. Apel and B. Heinrich, Mesh refinement and windowing near edges for some elliptic problem, SIAM J. Numer. Anal. 31 (1994), no. 3, 695–708. MR 1275108, DOI 10.1137/0731037
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. Comp. 62 (1994), no. 206, 645–669. MR 1223231, DOI 10.1090/S0025-5718-1994-1223231-5
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. Comp. 32 (1978), no. 144, 1131–1143. MR 481754, DOI 10.1090/S0025-5718-1978-0481754-1
Achi Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp. 31 (1977), no. 138, 333–390. MR 431719, DOI 10.1090/S0025-5718-1977-0431719-X
H. G. Burchard, On the degree of convergence of piecewise polynomial approximation on optimal meshes, Trans. Amer. Math. Soc. 234 (1977), no. 2, 531–559. MR 481758, DOI 10.1090/S0002-9947-1977-0481758-4
D. Catherall, The adaption of structured grids to numerical solutions for transonic flow, Internat. J. Numer. Meths. Engrg. 32 (1991), 921–937.
Ke Chen, Error equidistribution and mesh adaptation, SIAM J. Sci. Comput. 15 (1994), no. 4, 798–818. MR 1278002, DOI 10.1137/0915050
Philippe G. Ciarlet, Introduction à l’analyse numérique matricielle et à l’optimisation, Masson, Paris, 1982 (French). Collection Mathématiques Appliquées pour la Maîtrise. [Collection of Applied Mathematics for the Master’s Degree]. MR 680778
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 triangular meshes for minimizing the gradient error, Numer. Math. 59 (1991), no. 4, 321–348. MR 1113194, DOI 10.1007/BF01385784
Carl de Boor, A practical guide to splines, Applied Mathematical Sciences, vol. 27, Springer-Verlag, New York-Berlin, 1978. MR 507062, DOI 10.1007/978-1-4612-6333-3
M. Delfour, G. Payre, and J.-P. Zolésio, An optimal triangulation for second-order elliptic problems, Comput. Methods Appl. Mech. Engrg. 50 (1985), no. 3, 231–261. MR 800331, DOI 10.1016/0045-7825(85)90095-7
Ronald A. DeVore and Bradley J. Lucier, High order regularity for solutions of the inviscid Burgers equation, Nonlinear hyperbolic problems (Bordeaux, 1988) Lecture Notes in Math., vol. 1402, Springer, Berlin, 1989, pp. 147–154. MR 1033281, DOI 10.1007/BFb0083873
R. A. DeVore and V. A. Popov, Interpolation spaces and nonlinear approximation, Function spaces and applications (Lund, 1986) Lecture Notes in Math., vol. 1302, Springer, Berlin, 1988, pp. 191–205. MR 942269, DOI 10.1007/BFb0078875
Nira Dyn, David Levin, and Samuel Rippa, Data dependent triangulations for piecewise linear interpolation, IMA J. Numer. Anal. 10 (1990), no. 1, 137–154. MR 1036653, DOI 10.1093/imanum/10.1.137
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.
Weizhang Huang, Yuhe Ren, and Robert D. Russell, Moving mesh partial differential equations (MMPDES) based on the equidistribution principle, SIAM J. Numer. Anal. 31 (1994), no. 3, 709–730. MR 1275109, DOI 10.1137/0731038
Wei Zhang Huang and David M. Sloan, A simple adaptive grid method in two dimensions, SIAM J. Sci. Comput. 15 (1994), no. 4, 776–797. MR 1278001, DOI 10.1137/0915049
Donald E. McClure, Nonlinear segmented function approximation and analysis of line patterns, Quart. Appl. Math. 33 (1975/76), 1–37. MR 463769, DOI 10.1090/S0033-569X-1975-0463769-X
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.
R. B. Simpson, Anisotropic mesh transformations and optimal error control, Appl. Numer. Math. 14 (1994), 183–198.
J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422