This thesis discusses several topics related to interpolation and how it is used in numerical analysis. It begins with an overview of the aspects of interpolation theory that are relevant to the discussion at hand before presenting three new contributions to the field. The first new result is a detailed error analysis of the barycentric formula for trigonometric interpolation in equally-spaced points. We show that, unlike the barycentric formula for polynomial interpolation in Chebyshev points (and contrary to the main view in the literature), this formula is not always stable. We demonstrate how to correct this instability via a rewriting of the formula and establish the forward stability of the resulting algorithm. Second, we consider the problem of trigonometric interpolation in grids that are perturbations of equally-spaced grids in which each point is allowed to move by at most a fixed fraction of the grid spacing. We prove that the Lebesgue constant for these grids grows at a rate that is at most algebraic in the number of points, thus answering questions put forth by Trefethen and Weideman about the robustness of numerical methods based on trigonometric interpolation in points that are uniformly distributed but not equally-spaced. We use this bound to derive theorems about the convergence rate of trigonometric interpolation in these grids and also discuss the related question of quadrature. Specifically, we prove that if a function has V ≥ 1 derivatives, the Vth of which is Hölder continuous (with a Hölder exponent that depends on the size of the maximum allowable perturbation), then the interpolants converge uniformly to the function at an algebraic rate; larger values of V lead to more rapid convergence. A similar statement holds for the corresponding quadrature rule. We also consider what analogue, if any, there is for trigonometric interpolation of the famous 1/4 theorem of Kadec from sampling theory that restricts the size of the perturbations one can make to the integers and still be guaranteed to have a set of stable sampling for the Paley-Wiener space. We present numerical evidence suggesting that in the discrete case, the 1/4 threshold takes the form of a threshold for the boundedness of a "2-norm Lebesgue constant" and does not appear to have much significance in practice. We believe that these are the first results regarding this problem to appear in the literature. While we do not believe the results we establish are the best possible quantitatively, they do (rigorously) capture the main features of trigonometric interpolation in perturbations of equally-spaced grids. We make several conjectures as to what the optimal results may be, backed by extensive numerical results. Finally, we consider a new application of interpolation to numerical linear algebra. We show that recently developed methods for computing the eigenvalues of a matrix by dis- cretizing contour integrals of its resolvent are equivalent to computing a rational interpolant to the resolvent and finding its poles. Using this observation as the foundation, we develop a method for computing the eigenvalues of real symmetric matrices that enjoys the same advantages as contour integral methods with respect to parallelism but employs only real arithmetic, thereby cutting the computational cost and storage requirements in half.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:730413 |
| Date | January 2016 |
| Creators | Austin, Anthony P. |
| Contributors | Trefethen, Lloyd N. |
| Publisher | University of Oxford |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | https://ora.ox.ac.uk/objects/uuid:11c16937-4a59-494d-a06f-6d27b634e2f3 |
Page generated in 0.002 seconds