Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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 $n$-term Courant element approximation of functions in $L_p$ ( $0 < p \le \infty$) on bounded polygonal domains in $\mathbb{R} ^2$. 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 $f$ to optimally high asymptotic rates which are determined and automatically achieved by the inherent smoothness of $f$. The algorithms provide direct approximation estimates and permit utilization of the general Jackson-Bernstein machinery to characterize $n$-term Courant element approximation in terms of a scale of smoothness spaces ($B$-spaces) which govern the approximation rates.


References [Enhancements On Off] (What's this?)

  • [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 $C(R^d)$, 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 $n$-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: 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

American Mathematical Society