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

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

Published electronically:
March 19, 2003

MathSciNet review:
1975391

Full-text PDF

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]**C. Bennett and R. Sharpley,*Interpolation of operators*, Pure and Applied Mathematics Vol.**129**, Academic Press, Inc., Boston, MA, 1988. MR**89e:46001****[2]**J. Bergh and J. Löfström,*Interpolation spaces: An introduction*, Grundlehren der Mathematischen Wissenschaften, No. 223. Springer-Verlag, Berlin-New York, 1976. MR**58:2349****[3]**O. Davydov and P. Petrushev, Nonlinear approximation from differentiable piecewise polynomials, 2002, preprint.**[4]**R. DeVore, I. Daubechies, A. Cohen, and W. Dahmen, Tree approximation and optimal encoding, Appl. Comput. Harmon. Anal. II (2001), 192-226. MR**2002g:42048****[5]**R.A. DeVore, B. Jawerth, and B. Lucier, Surface compression, Computer Aided Geometric Design**9**(1992), 219-239. MR**93i:65029****[6]**R.A. DeVore and G.G. Lorentz,*Constructive Approximation*, Grundlehren der Mathemati- schen Wissenschaften, Vol.**303**, Springer-Verlag, Heidelberg, 1993. MR**95f:41001****[7]**R.A. DeVore, P. Petrushev, and X. Yu, Nonlinear wavelet approximation in the space ,*Progress in Approximation Theory*(A. A. Gonchar, E. B. Saff, eds.), Springer-Verlag, New York, 1992, pp. 261-283. MR**94h:41070****[8]**R.A. DeVore and V. Popov, Interpolation of Besov spaces, Trans. Amer. Math. Soc.**305**(1988), 397-414. MR**89h:46044****[9]**R.A. DeVore and V. 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 Math.**1302**, Springer-Verlag, Berlin, 1988, 191-205. MR**89d:41035****[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]**P. Petrushev, Direct and converse theorems for spline and rational approximation and Besov spaces, in*Function Spaces and Applications*, M. Cwikel et. al. (eds), Vol. 1302 of Lecture Notes in Mathematics, Springer, Berlin, 1988, pp. 363-377. MR**89d:41027****[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. Petrushev and V. Popov,*Rational approximation of real functions*, Cambridge University Press, 1987. MR**89i:41022**

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:
https://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