Kowalski, M
1994
Selected Topics in Approximation and Computation
Sikorski, K.; Kowalski, M. and Stenger, F.
Oxford University Press, Oxford, England, 1995. Funded partially by IBM and ACERC.
This text covers classical basic results of approximation theory. It also obtains new developments in the theory of moments and Sinc approximation, as well as n-widths, s-numbers, and the relationship of these concepts to computational complexity. In addition, the text also contains several computational algorithms.
Chapter 1 covers basic concepts of classical approximation.
In Section 1.1, the classical and basic concepts of approximation theory are couched in the language of functional analysis. It is thus convenient to cover the concepts of existence and uniqueness of best approximation in a normed space setting.
A very important normed space from the point of both theory and application, in which to study best approximation is that of an inner product space. In this space it is convenient to study approximation in various polynomial settings, such as, via classical orthogonal polynomials, and via Cardinal, or sinc approximation. These concepts are covered in Section 1.2 of the text.
Concepts of approximation in the uniform norm are covered in Section 1.3. These concepts are also conveniently presented in a Banach space setting. Important examples from a classical standpoint include polynomial approximation with respect to the uniform norm.
Chapter 2 deals with spline methods of approximation.
Polynomials. Are historically the most popular tools of approximation, since they are easy to compute. However, a polynomial of high degree does not do a good job of approximating arbitrary given data, since it is then nearly always the case that the polynomial also has large over and undershoots between data points. On the other hand, splines, which are piecewise polynomials discussed in Chapter 2, are very convenient for approximating data, particularly data that is contaminated with noise. This is especially true of the practically important B-spines, which have variation-diminshing properties when used to approximate data, i.e., the total variation of the spline approximant is not more than that of the data. Thus splines provide particularly useful methods of approximation in the important areas of computer aided geometric design and for representing computer graphics displays.
Sinc methods discussed in Chapter 3 are ideal for approximating functions that may have singularities at end-points of an interval. Sline methods are ideal for approximation of data, and polynomial methods are ideal for approximating analytic functions that have no singularities on the interval of approximation. For example, if a function is analytic in a region containing an interval I, then we can achieve an O(exp{-b n}) error in a degree n polynomial approximation of the function in I, where b is some positive constant. This rapid exponential rate of decrease of the error reduces to a drastically slow O(n-b') rate in the case when the function has a singularity on I. Also, it turns out that Sinc methods provide simple to use accurate approximation tools for every operation of calculus, including the approximation of Hilbert transform, the approximation of derivatives, the approximation of definite and indefinite integration, the approximation and inversion of Laplace transforms, and the approximation of indefinite convolution integrals. While an O(exp{-b' n1/2}) error is also possible via spline approximation, by suitable choice of both the mesh and the degree of the spline on each subinterval, the constant b' in this exponential rate of convergence is usually not as large as the corresponding constant b for sinc approximation.
In Chapter 4 we present a family of simple rational functions, which make possible the explicit and arbitrarily accurate rational approximation of the filter, the step, and impulse functions.
Moment problems are conveniently discussed in the setting of approximation theory in Chapter 5. Included among the well known moment problems are the discrete and continuous moment problems named after Hausdorff, Stieltjes, and Hamburger, as well as the discrete and continuous trigonometric moment problems. We also include the Sinc moment problem, whose solution in the appropriate Sinc space is relatively easy, and devoid of the difficulties that one encounters using the usual monomial bases.
Chapter 6 deals with some rather "deep" concepts of approximation, namely, of n-widths and s-numbers. A historically first and practically important problem of approximation theory is to achieve a practically accurate approximation to a function f by e.g., a polynomial of a certain degree. Next, one might want to know the error of best approximation of the function f by polynomials of degree n. Following this, we could identify a class of functions F to which the function f to be approximated belongs, and we could then determine the maximum error of best approximation, as f is varied throughout F. Finally, we could vary out tools of approximation, i.e., the classes of n-dimensional subspaces, (e.g., not just polynomials) and so deduce the best method of approximation of functions in F. We are thus able to explore limits of approximability, a knowledge of which is both practically and theoretically worth while.
Chapter 7 discusses optimal methods of approximation, and optimal algorithms for general, nonlinear approximation problems. It relates approximability with the amount of work required to achieve a certain accuracy. These concepts are discussed in the general setting of normed spaces, and later, they are connected with splines, and also with the concepts of n-widths and s-numbers discussed in the previous chapter.
Chapter 8 illustrates applications of the approximation theory of the previous chapters. We discuss here the solution of Burgers' equation, the approximation of band-limited signals, and a nonlinear zero finding problem.
Each section of the text ends with a set of exercises. Each chapter closes with annotations including historical remarks that indicate the source of the material. The references follow afterwards.
Exercises are numbered from 1 to 180 globally throughout the text. Theorems, lemmas, corollaries, examples, and figures are numbered consecutively within each page. Therefore the notation Theorem 265.1 and Example 265.1 means first theorem and first example on page 265. There are no references to the literature inside of the text. All references are discussed in annotations to each chapter. Numbered formulas are almost eliminated to provide more structured text. In a few cases left they are numbered again according to the page system described above, i.e., formula 15.1 means first formula on page 15. We believe that the special format chosen will best serve the reader by providing more structured and self contained text.
Kowalski, M
1994
Selected Topics in Approximation and Computation
Sikorski, K.; Kowalski, M. and Stenger, F.
Oxford University Press, Oxford, England, 1995. Funded partially by IBM and ACERC.
This text covers classical basic results of approximation theory. It also obtains new developments in the theory of moments and Sinc approximation, as well as n-widths, s-numbers, and the relationship of these concepts to computational complexity. In addition, the text also contains several computational algorithms.
Chapter 1 covers basic concepts of classical approximation.
In Section 1.1, the classical and basic concepts of approximation theory are couched in the language of functional analysis. It is thus convenient to cover the concepts of existence and uniqueness of best approximation in a normed space setting.
A very important normed space from the point of both theory and application, in which to study best approximation is that of an inner product space. In this space it is convenient to study approximation in various polynomial settings, such as, via classical orthogonal polynomials, and via Cardinal, or sinc approximation. These concepts are covered in Section 1.2 of the text.
Concepts of approximation in the uniform norm are covered in Section 1.3. These concepts are also conveniently presented in a Banach space setting. Important examples from a classical standpoint include polynomial approximation with respect to the uniform norm.
Chapter 2 deals with spline methods of approximation.
Polynomials. Are historically the most popular tools of approximation, since they are easy to compute. However, a polynomial of high degree does not do a good job of approximating arbitrary given data, since it is then nearly always the case that the polynomial also has large over and undershoots between data points. On the other hand, splines, which are piecewise polynomials discussed in Chapter 2, are very convenient for approximating data, particularly data that is contaminated with noise. This is especially true of the practically important B-spines, which have variation-diminshing properties when used to approximate data, i.e., the total variation of the spline approximant is not more than that of the data. Thus splines provide particularly useful methods of approximation in the important areas of computer aided geometric design and for representing computer graphics displays.
Sinc methods discussed in Chapter 3 are ideal for approximating functions that may have singularities at end-points of an interval. Sline methods are ideal for approximation of data, and polynomial methods are ideal for approximating analytic functions that have no singularities on the interval of approximation. For example, if a function is analytic in a region containing an interval I, then we can achieve an O(exp{-b n}) error in a degree n polynomial approximation of the function in I, where b is some positive constant. This rapid exponential rate of decrease of the error reduces to a drastically slow O(n-b') rate in the case when the function has a singularity on I. Also, it turns out that Sinc methods provide simple to use accurate approximation tools for every operation of calculus, including the approximation of Hilbert transform, the approximation of derivatives, the approximation of definite and indefinite integration, the approximation and inversion of Laplace transforms, and the approximation of indefinite convolution integrals. While an O(exp{-b' n1/2}) error is also possible via spline approximation, by suitable choice of both the mesh and the degree of the spline on each subinterval, the constant b' in this exponential rate of convergence is usually not as large as the corresponding constant b for sinc approximation.
In Chapter 4 we present a family of simple rational functions, which make possible the explicit and arbitrarily accurate rational approximation of the filter, the step, and impulse functions.
Moment problems are conveniently discussed in the setting of approximation theory in Chapter 5. Included among the well known moment problems are the discrete and continuous moment problems named after Hausdorff, Stieltjes, and Hamburger, as well as the discrete and continuous trigonometric moment problems. We also include the Sinc moment problem, whose solution in the appropriate Sinc space is relatively easy, and devoid of the difficulties that one encounters using the usual monomial bases.
Chapter 6 deals with some rather "deep" concepts of approximation, namely, of n-widths and s-numbers. A historically first and practically important problem of approximation theory is to achieve a practically accurate approximation to a function f by e.g., a polynomial of a certain degree. Next, one might want to know the error of best approximation of the function f by polynomials of degree n. Following this, we could identify a class of functions F to which the function f to be approximated belongs, and we could then determine the maximum error of best approximation, as f is varied throughout F. Finally, we could vary out tools of approximation, i.e., the classes of n-dimensional subspaces, (e.g., not just polynomials) and so deduce the best method of approximation of functions in F. We are thus able to explore limits of approximability, a knowledge of which is both practically and theoretically worth while.
Chapter 7 discusses optimal methods of approximation, and optimal algorithms for general, nonlinear approximation problems. It relates approximability with the amount of work required to achieve a certain accuracy. These concepts are discussed in the general setting of normed spaces, and later, they are connected with splines, and also with the concepts of n-widths and s-numbers discussed in the previous chapter.
Chapter 8 illustrates applications of the approximation theory of the previous chapters. We discuss here the solution of Burgers' equation, the approximation of band-limited signals, and a nonlinear zero finding problem.
Each section of the text ends with a set of exercises. Each chapter closes with annotations including historical remarks that indicate the source of the material. The references follow afterwards.
Exercises are numbered from 1 to 180 globally throughout the text. Theorems, lemmas, corollaries, examples, and figures are numbered consecutively within each page. Therefore the notation Theorem 265.1 and Example 265.1 means first theorem and first example on page 265. There are no references to the literature inside of the text. All references are discussed in annotations to each chapter. Numbered formulas are almost eliminated to provide more structured text. In a few cases left they are numbered again according to the page system described above, i.e., formula 15.1 means first formula on page 15. We believe that the special format chosen will best serve the reader by providing more structured and self contained text.