Nonlinear Approximation Theory

The first investigations of nonlinear approximation problems were made by P.L. Chebyshev in the last century, and the entire theory of uniform approxima­ tion is strongly connected with his name. By making use of his ideas, the theories of best uniform approximation by rational functions and by polynomials were developed over the years in an almost unified framework. The difference between linear and rational approximation and its implications first became apparent in the 1960's. At roughly the same time other approaches to nonlinear approximation were also developed. The use of new tools, such as nonlinear functional analysis and topological methods, showed that linearization is not sufficient for a complete treatment of nonlinear families. In particular, the application of global analysis and the consideration of flows on the family of approximating functions intro­ duced ideas which were previously unknown in approximation theory. These were and still are important in many branches of analysis. On the other hand, methods developed for nonlinear approximation prob­ lems can often be successfully applied to problems which belong to or arise from linear approximation. An important example is the solution of moment problems via rational approximation. Best quadrature formulae or the search for best linear spaces often leads to the consideration of spline functions with free nodes. The most famous problem of this kind, namely best interpolation by poly­ nomials, is treated in the appendix of this book.

I. Preliminaries.- § 1. Some Notation, Definitions and Basic Facts.- A. Functional Analytic Notation and Terminology.- B. The Approximation Problem. Definitions and Basic Facts.- C. An Invariance Principle.- D. Divided Differences.- § 2. A Review of the Characterization of Nearest Points in Linear and Convex Sets.- A. Characterization via the Hahn-Banach Theorem and the Kolmogorov Criterion.- B. Special Function Spaces.- § 3. Linear and Convex Chebyshev Approximation.- A. Haar’s Uniqueness Theorem. Alternants.- B. Haar Cones.- C. Alternation Theorem for Haar Cones.- §4. L1-Approximation and Gaussian Quadrature Formulas.- A. The Hobby-Rice Theorem.- B. Existence of Generalized Gaussian Quadrature Formulas.- C. Extremal Properties.- II. Nonlinear Approximation: The Functional Analytic Approach.- §1. Approximative Properties of Arbitrary Sets.- A. Existence.- B. Uniqueness from the Generic Viewpoint.- §2. Solar Properties of Sets.- A. Suns. The Kolmogorov Criterion.- B. The Convexity of Suns.- C. Suns and Moons in C(X).- § 3. Properties of Chebyshev Sets.- A. Approximative Compactness.- B. Convexity and Solarity of Chebyshev Sets.- C. An Alternative Proof.- III. Methods of Local Analysis.- §1. Critical Points.- A. Tangent Cones and Critical Points.- B. Parametrizations and C1-Manifolds.- C. Local Strong Uniqueness.- §2. Nonlinear Approximation in Hilbert Spaces.- A. Nonlinear Approximation in Smooth Banach Spaces.- B. A Classification of Critical Points.- C. Continuity.- D. Functions with Many Local Best Approximations.- § 3. Varisolvency.- A. Varisolvent Families.- B. Characterization and Uniqueness of Best Approximations.- C. Regular and Singular Points.- D. The Density Property.- §4. Nonlinear Chebyshev Approximation: The Differentiable Case.- A. The Local Kolmogorov Criterion.- B. The Local Haar Condition.- C. Haar Manifolds.- D. The Local Uniqueness Theorem for C1-Manifolds.- §5. The Gauss-Newton Method.- A. General Convergence Theory.- B. Numerical Stabilization.- IV. Methods of Global Analysis.- §1. Preliminaries. Basic Ideas.- A. Concepts for the Classification of Critical Points.- B. An Example with Many Critical Points.- C. Local Homeomorphisms.- §2. The Uniqueness Theorem for Haar Manifolds.- A. The Deformation Theorem.- B. The Mountain Pass Theorem.- C. Perturbation Theory.- §3. An Example with One Nonlinear Parameter.- A. The Manifold $$E_n^c\backslash E_{n - 1}^c$$.- B. Reduction to One Parameter.- C. Improvement of the Bounds.- V. Rational Approximation.- §1. Existence of Best Rational Approximations.- A. The Existence Problem in C(X).- B. Rational Lp-Approximation. Degeneracy.- §2. Chebyshev Approximation by Rational Functions.- A. Uniqueness and Characterization of Best Approximations.- B. Normal Points.- C. The Lethargy Theorem and the Lip 1 Conjecture.- §3. Rational Interpolation.- A. The Cauchy Interpolation Problem.- B. Rational Functions with Real Poles.- C. Comparison Theorems.- §4. Padé Approximation and Moment Problems.- A. Padé Approximation.- B. The Stieltjes and the Hamburger Moment Problem.- §5. The Degree of Rational Approximation.- A. Approximation of ex on [?1, +1].- B. Approximation of e?x on [0, ?] by Inverses of Polynomials.- C. Rational Approximation of e?x on [0,?).- D. Rational Approximation of ?x.- E. Rational Approximation of ?x?.- §6. The Computation of Best Rational Approximations.- A. The Differential Correction Algorithm.- B. The Remes Algorithm.- VI. Approximation by Exponential Sums.- §1. Basic Facts.- A. Proper and Extended Exponential Sums.- B. The Descartes’ Rule of Signs.- §2. Existence of Best Approximations.- A. A Bound for the Derivatives of Exponential Sums.- B. Existence.- §3. Some Facts on Interpolation and Approximation.- A. Interpolation by Exponential Sums.- B. The Speed of Approximation of Completely Monotone Functions.- VII. Chebyshev Approximation by ?-Polynomials.- §1. Descartes Families.- A. ?-Polynomials.- B. Sign-Regular and Totally Positive Kernels.- C. The Generalized Descartes’ Rule.- D. Further Generalizations.- E. Examples.- §2. Approximation by Proper ?-Polynomials.- A. Varisolvency.- B. Sign Distribution.- C. Positive Sums.- §3. Approximation by Extended ?-Polynomials: Elementary Theory.- A. Non-Uniqueness, Characterization of Best Approximations.- B. ?Polynomials of Order 2.- §4. The Haar Manifold Gn\Gn?1.- A. Simple Parametrizations.- B. The Differentiable Structure.- C. Families with Bounded Spectrum.- §5. Local Best Approximations.- A. Characterization of Local Best Approximations.- B. The Generic Viewpoint.- §6. Maximal Components.- A. Introduction of Maximal Components.- B. The Boundary of Maximal Components.- §7. The Number of Local Best Approximations.- A. The Construction of Local Best Approximations.- B. Completeness of the Standard Construction.- VIII. Approximation by Spline Functions with Free Nodes.- §1. Spline Functions with Fixed Nodes.- A. Chebyshevian Spline Functions.- B. Zeros of Spline Functions.- C. Characterization of Best Uniform Approximations.- §2. Chebyshev Approximation by Spline Functions with Free Nodes.- A. Existence..- B. Continuity and Differentiability Properties.- C. Characterization of Best Approximations.- §3. Monosplines of Least L?-Norm.- A. The Family $$S_{n,k}^ +$$.- B. Monosplines.- C. The Fundamental Theorem of Algebra for Monosplines.- D. Monosplines with Multiple Nodes of Least L?-Norm.- E. Perfect Splines and Generalized Monosplines.- §4. Monosplines of Least L1-Norm.- A. Examples of Nonuniqueness.- B. Duality.- C. The Improvement Operator.- D. Proof of Lemma 4.3.- §5. Monosplines of Least Lp-Norm.- A. The Rodriguez Function for the Lp-Norms.- B. The Degree of the Mapping ?.- C. The Uniqueness Theorem.- Appendix. The Conjectures of Bernstein and Erdös.