Algorithms for nonlinear piecewise polynomial approximation: Theoretical aspects

Authors:
Borislav Karaivanov, Pencho Petrushev and Robert C. Sharpley

Journal:
Trans. Amer. Math. Soc. **355** (2003), 2585-2631

MSC (2000):
Primary 41A17, 41A25, 65D18; Secondary 65D07, 42B35

Published electronically:
March 19, 2003

MathSciNet review:
1975391

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this article algorithms are developed for nonlinear -term Courant element approximation of functions in ( ) on bounded polygonal domains in . Redundant collections of Courant elements, which are generated by multilevel nested triangulations allowing arbitrarily sharp angles, are investigated. Scalable algorithms are derived for nonlinear approximation which both capture the rate of the best approximation and provide the basis for numerical implementation. Simple thresholding criteria enable approximation of a target function to optimally high asymptotic rates which are determined and automatically achieved by the inherent smoothness of . The algorithms provide direct approximation estimates and permit utilization of the general Jackson-Bernstein machinery to characterize -term Courant element approximation in terms of a scale of smoothness spaces (-spaces) which govern the approximation rates.

**[1]**Colin Bennett and Robert Sharpley,*Interpolation of operators*, Pure and Applied Mathematics, vol. 129, Academic Press, Inc., Boston, MA, 1988. MR**928802****[2]**Jöran Bergh and Jörgen Löfström,*Interpolation spaces. An introduction*, Springer-Verlag, Berlin-New York, 1976. Grundlehren der Mathematischen Wissenschaften, No. 223. MR**0482275****[3]**O. Davydov and P. Petrushev, Nonlinear approximation from differentiable piecewise polynomials, 2002, preprint.**[4]**Albert Cohen, Wolfgang Dahmen, Ingrid Daubechies, and Ronald DeVore,*Tree approximation and optimal encoding*, Appl. Comput. Harmon. Anal.**11**(2001), no. 2, 192–226. MR**1848303**, 10.1006/acha.2001.0336**[5]**Ronald A. DeVore, Björn Jawerth, and Bradley J. Lucier,*Surface compression*, Comput. Aided Geom. Design**9**(1992), no. 3, 219–239. MR**1175287**, 10.1016/0167-8396(92)90019-L**[6]**Ronald A. DeVore and George G. Lorentz,*Constructive approximation*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 303, Springer-Verlag, Berlin, 1993. MR**1261635****[7]**R. A. DeVore, P. Petrushev, and X. M. Yu,*Nonlinear wavelet approximation in the space 𝐶(𝑅^{𝑑})*, Progress in approximation theory (Tampa, FL, 1990) Springer Ser. Comput. Math., vol. 19, Springer, New York, 1992, pp. 261–283. MR**1240786**, 10.1007/978-1-4612-2966-7_11**[8]**Ronald A. DeVore and Vasil A. Popov,*Interpolation of Besov spaces*, Trans. Amer. Math. Soc.**305**(1988), no. 1, 397–414. MR**920166**, 10.1090/S0002-9947-1988-0920166-3**[9]**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**, 10.1007/BFb0078875**[10]**M.A. Duchaineau, M. Wolinsky, D.E. Sigeti, M.C. Miller, C. Aldrich, and M.B. Mineev-Weinstein, ROAMing Terrain: Real-time Optimally Adapting Meshes, Proc. IEEE Visualization `97, October 1997, pp. 81-88.**[11]**B. Karaivanov and P. Petrushev, Nonlinear piecewise polynomial approximation beyond Besov spaces, 2001, preprint. (http://www.math.sc.edu/~imip/01.html).**[12]**B. Karaivanov, P. Petrushev and R.C. Sharpley, Algorithms for nonlinear piecewise polynomial approximation, 2002, preprint.**[13]**Pencho P. Petrushev,*Direct and converse theorems for spline and rational approximation and Besov spaces*, Function spaces and applications (Lund, 1986) Lecture Notes in Math., vol. 1302, Springer, Berlin, 1988, pp. 363–377. MR**942281**, 10.1007/BFb0078887**[14]**P. Petrushev, Multivariate -term rational and piecewise polynomial approximation, J. Approx. Theory (2003), to appear. (http://www.math.sc.edu/~imip/01.html)**[15]**P. P. Petrushev and V. A. Popov,*Rational approximation of real functions*, Encyclopedia of Mathematics and its Applications, vol. 28, Cambridge University Press, Cambridge, 1987. MR**940242**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2000):
41A17,
41A25,
65D18,
65D07,
42B35

Retrieve articles in all journals with MSC (2000): 41A17, 41A25, 65D18, 65D07, 42B35

Additional Information

**Borislav Karaivanov**

Affiliation:
Department of Mathematics, University of South Carolina, Columbia, South Carolina 29208

Email:
karaivan@math.sc.edu

**Pencho Petrushev**

Affiliation:
Department of Mathematics, University of South Carolina, Columbia, South Carolina 29208

Email:
pencho@math.sc.edu

**Robert C. Sharpley**

Affiliation:
Department of Mathematics, University of South Carolina, Columbia, South Carolina 29208

Email:
sharpley@math.sc.edu

DOI:
http://dx.doi.org/10.1090/S0002-9947-03-03141-6

Keywords:
Nested irregular triangulations,
redundant representations,
nonlinear $n$-term approximation,
Courant elements,
Jackson and Bernstein estimates.

Received by editor(s):
May 2, 2002

Published electronically:
March 19, 2003

Additional Notes:
The second and third authors were supported in part by Grant NSF #DMS-0079549 and ONR N00014-01-1-0515.

All three authors were supported in part by ONR grant N00014-00-1-0470.

Article copyright:
© Copyright 2003
American Mathematical Society