Algorithms for nonlinear piecewise polynomial approximation: Theoretical aspects
Authors:
Borislav Karaivanov, Pencho Petrushev and Robert C. Sharpley
Journal:
Trans. Amer. Math. Soc. 355 (2003), 25852631
MSC (2000):
Primary 41A17, 41A25, 65D18; Secondary 65D07, 42B35
Published electronically:
March 19, 2003
MathSciNet review:
1975391
Fulltext 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 JacksonBernstein 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
(89e:46001)
 [2]
Jöran
Bergh and Jörgen
Löfström, Interpolation spaces. An introduction,
SpringerVerlag, Berlin, 1976. Grundlehren der Mathematischen
Wissenschaften, No. 223. MR 0482275
(58 #2349)
 [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
(2002g:42048), http://dx.doi.org/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
(93i:65029), http://dx.doi.org/10.1016/01678396(92)90019L
 [6]
Ronald
A. DeVore and George
G. Lorentz, Constructive approximation, Grundlehren der
Mathematischen Wissenschaften [Fundamental Principles of Mathematical
Sciences], vol. 303, SpringerVerlag, Berlin, 1993. MR 1261635
(95f:41001)
 [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
(94h:41070), http://dx.doi.org/10.1007/9781461229667_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 (89h:46044), http://dx.doi.org/10.1090/S00029947198809201663
 [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
(89d:41035), http://dx.doi.org/10.1007/BFb0078875
 [10]
M.A. Duchaineau, M. Wolinsky, D.E. Sigeti, M.C. Miller, C. Aldrich, and M.B. MineevWeinstein, ROAMing Terrain: Realtime Optimally Adapting Meshes, Proc. IEEE Visualization `97, October 1997, pp. 8188.
 [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
(89d:41027), http://dx.doi.org/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
(89i:41022)
 [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. SpringerVerlag, BerlinNew 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), 192226. MR 2002g:42048
 [5]
 R.A. DeVore, B. Jawerth, and B. Lucier, Surface compression, Computer Aided Geometric Design 9 (1992), 219239. MR 93i:65029
 [6]
 R.A. DeVore and G.G. Lorentz, Constructive Approximation, Grundlehren der Mathemati schen Wissenschaften, Vol. 303, SpringerVerlag, 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.), SpringerVerlag, New York, 1992, pp. 261283. MR 94h:41070
 [8]
 R.A. DeVore and V. Popov, Interpolation of Besov spaces, Trans. Amer. Math. Soc. 305(1988), 397414. MR 89h:46044
 [9]
 R.A. DeVore and V. Popov, Interpolation spaces and nonlinear approximation, in Function Spaces and Applications, M. Cwikel, J. Peetre, Y. Sagher, and H. Wallin (eds.), Springer Lecture Notes in Math. 1302, SpringerVerlag, Berlin, 1988, 191205. MR 89d:41035
 [10]
 M.A. Duchaineau, M. Wolinsky, D.E. Sigeti, M.C. Miller, C. Aldrich, and M.B. MineevWeinstein, ROAMing Terrain: Realtime Optimally Adapting Meshes, Proc. IEEE Visualization `97, October 1997, pp. 8188.
 [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. 363377. 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
Similar Articles
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/S0002994703031416
PII:
S 00029947(03)031416
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 #DMS0079549 and ONR N000140110515.
All three authors were supported in part by ONR grant N000140010470.
Article copyright:
© Copyright 2003 American Mathematical Society
