Binev, P., W. Dahmen, R. DeVore, P. Petrushev.
Approximation classes for adaptive methods
(pp. 391-416)
A B S T R A C T S
GENERALIZATION OF A CONJECTURE IN THE GEOMETRY OF
POLYNOMIALS
Bl. Sendov
bsendov@argo.bas.bg
2000 Mathematics Subject Classification: 30C10.
Key words:
Geometry of polynomials, Gauss-Lucas Theorem,
zeros
of polynomials, critical points, Ilieff-Sendov Conjecture.
In this paper we survey work on and around
the following conjecture, which was first stated about 45 years
ago: If all the zeros of an algebraic polynomial p
(of degree n ³
2) lie in a disk with radius r, then, for each
zero z_{1} of p, the disk with center z_{1} and radius r
contains at least one zero of
the derivative p¢.
Until now, this conjecture has been proved
for n £ 8 only.
We also put the conjecture in a more general
framework
involving higher order derivatives and sets defined by
the zeros of the polynomials.
GREEDY APPROXIMATION WITH REGARD TO
BASES AND GENERAL MINIMAL SYSTEMS
S. V. Konyagin
konyagin@ok.ru,
V. N. Temlyakovz
temlyak@math.sc.edu
2000 Mathematics Subject Classification: 41A25, 41A46, 41A58, 46A35.
Key words:
greedy bases, quasi-greedy bases,
almost greedy bases, $m$-term approximation, weak greedy algorithms,
thresholding approximation, minimal systems, A-convergence.
This paper
is a survey which also contains some new results on the nonlinear
approximation with regard to a basis or, more generally, with
regard to a minimal system. Approximation takes place in a Banach
or in a quasi-Banach space. The last decade was very successful in
studying nonlinear approximation. This was motivated by numerous
applications. Nonlinear approximation is important in applications
because of its increased efficiency. Two types of nonlinear
approximation are employed frequently in applications. Adaptive
methods are used in PDE solvers. The m-term approximation
considered here is used in image and signal processing as well as
the design of neural networks. The basic idea behind nonlinear
approximation is that the elements used in the approximation do
not come from a fixed linear space but are allowed to depend on
the function being approximated. The fundamental question of
nonlinear approximation is how to construct good methods
(algorithms) of nonlinear approximation. In this paper we discuss
greedy type and thresholding type algorithms.
PENALIZED LEAST SQUARES FITTING
Manfred von Golitschek
goli@mathematik.uni-wuerzburg.de,
Larry L. Schumaker
s@mars.cas.vanderbilt.edu
2000 Mathematics Subject Classification: Primary 41A15; Secondary 41A25.
Key words:
Penalized least squares,
Tikhonov regularization, Spline approximation.
Bounds
on the error of certain penalized least squares data fitting
methods are derived. In addition to general results in a fairly
abstract setting, more detailed results are included for several
particularly interesting special cases, including splines in both
one and several variables.
SPLINE SUBDIVISION SCHEMES FOR COMPACT SETS. A SURVEY
Nira Dyn
niradyn@post.tau.ac.il,
Elza Farkhi
elza@math.tau.ac.il
2000 Mathematics Subject Classification:
26E25, 28B20, 41A15, 41A36.
Key words:
compact sets, spline
subdivision schemes, metric average, Minkowski sum.
Attempts at extending spline subdivision schemes to operate on compact sets are
reviewed. The aim is to develop a procedure for approximating
a set-valued function with compact images from a finite set of its samples.
This is motivated by the problem of reconstructing a 3D object from a finite set
of its parallel cross sections. The first attempt is limited to the case of convex
sets, where the Minkowski sum of sets is successfully applied to replace addition
of scalars. Since for nonconvex sets the Minkowski sum is too big and there is no
approximation result as in the case of convex sets, a binary operation, called
metric average,
is used instead. With the metric average, spline
subdivision schemes constitute approximating operators for set-valued functions
which are Lipschitz continuous in the Hausdorff metric.
Yet this result is not completely satisfactory, since 3D
objects are not continuous in the Hausdorff metric near points of change of
topology, and a special treatment near such points has yet to be designed.
NEARLY COCONVEX APPROXIMATION
D. Leviatan
leviatan@math.tau.ac.il,
I. A. Shevchuk
shevchuk@univ.kiev.ua
2000 Mathematics Subject Classification:
41A10, 41A17, 41A25, 41A29.
Key words:
Nearly coconvex
approximation, polynomial approximation,
piecewise polynomial approximation, Jackson estimates.
Let f Î C[-1,1] change its convexity finitely many times, in
the interval. We are interested in estimating the degree of
approximation of f by polynomials, and by piecewise polynomials,
which are nearly coconvex with it, namely, polynomials and
piecewise polynomials that preserve the convexity of f except
perhaps in some small neighborhoods of the points where f
changes its convexity. We obtain Jackson type estimates and
summarize the positive and negative results in a truth-table as we
have previously done for nearly comonotone approximation.
ON REPRESENTATIONS OF ALGEBRAIC POLYNOMIALS BY SUPERPOSITIONS
OF PLANE WAVES
K. I. Oskolkov
oskolkov@math.sc.edu
2000 Mathematics Subject Classification:
41-XX, 42-XX.
Key words:
Non-linear approximation, polynomials, plane
waves, ridge functions, Chebyshev - Fourier analysis.
Let P be a bi-variate algebraic polynomial of degree n with
the real senior part, and Y = {y_{j}}_{1}^{n} an n-element
collection of pairwise non-colinear unit vectors on the real
plane. It is proved that there exists a rigid rotation
Y^{j} of Y by an angle
j = j(P,Y)
Î [0,p/n] such that P equals
the sum of n plane wave polynomials, that propagate in the
directions Î Y^{j}.
THE AUTOMORPHISM GROUP OF THE FREE ALGEBRA OF RANK TWO
Peter Binev
binev@math.sc.edu,
Wolfgang Dahmen
dahmen@igpm.rwth-aachen.de,
Ronald DeVore
devore@math.sc.edu,
Pencho Petrushev
pencho@math.sc.edu
2000 Mathematics Subject Classification:
42C40, 46B70, 26B35, 42B25.
Key words:
adaptive finite element methods,
adaptive approximation, $n$-term approximation, degree of approximation,
approximation classes, Besov spaces.
Adaptive Finite Element Methods (AFEM) are numerical procedures
that approximate the solution to a partial differential equation
(PDE) by piecewise polynomials on adaptively generated
triangulations. Only recently has any analysis of
the convergence of these methods [10, 13] or their rates of
convergence [2] become available. In the latter paper it is
shown that a certain AFEM for solving Laplace's equation on a polygonal
domain
W Ì R^{2} based on newest vertex bisection has an
optimal rate of convergence in the following sense. If, for
some s > 0 and for each n = 1,2,..., the solution u can be
approximated in the energy norm to order O(n^{-s}) by piecewise
linear functions on a partition P obtained from n newest
vertex bisections, then the adaptively generated solution will
also use O(n) subdivisions (and floating point computations) and
have the same rate of convergence. The question arises whether
the class of functions A^{s} with this approximation rate can
be described by classical measures of smoothness. The purpose of
the present paper is to describe such approximation classes
A^{s} by Besov smoothness.
Back