Academic literature on the topic 'Lebesgue constants'

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.

Dans certains phénomènes physiques modélisés par des EDP, les coefficients intervenant dans les équations ne sont pas des fonctions déterministes fixées, et dépendent de paramètres qui peuvent varier. Ceci se produit par exemple dans le cadre de la modélisation des écoulements en milieu poreux lorsqu’on décrit le champ de perméabilité par un processus stochastique pour tenir compte de l’incertitude sur ce champs. Dans d’autres cadres, il peut s’agir de paramètres déterministes que l’on cherche à ajuster, par exemple pour optimiser un certain critère sur la solution. La solution u dépend donc non seulement de la variable x d’espace/temps mais aussi d’un vecteur y = (yj) de paramètres potentiellement nombreux, voire en nombre infinis. L’approximation numérique en y de l’application (x,y)-&gt; u(x, y) est donc impossible par les méthodes classiques de type éléments finis, et il faut envisager des approches adaptées aux grandes dimensions. Cette thèse est consacrée à l’étude théorique et l’approximation numérique des EDP paramétriques en grandes dimensions. Pour une large classe d’EDP avec une certaine dépendance anisotrope en les paramètres yj, on étudie de la régularité en y de l’application u et on propose des méthodes d’approximation numérique dont les performances ne subissent pas les détériorations classiquement observées en grande dimension. On cherche en particulier à évaluer la complexité de la classe des solutions {u(y)}, par exemple au sens des épaisseurs de Kolmogorov, afin de comprendre les limites inhérentes des méthodes numériques. On analyse en pratique les propriétés de convergences de diverses méthodes d’approximation avec des polynômes creux<br>For certain physical phenomenon that are modelled by PDE, the coefficients intervening in the equations are not fixed deterministic functions, but depend on parameters that may vary

Cette thèse traite de l'interpolation polynomiale des fonctions d'une ou plusieurs variables. Nous nous intéresserons principalement à l'interpolation de Lagrange mais un de nos travaux concerne les interpolations de Kergin et d'Hakopian. Nous dénotons par K le corps de base qui sera toujours R ou C, Pd(KN) l'espace des polynômes de N variables et de degré au plus d à coefficients dans K. Un ensemble A dans KN contenant autant de points que la dimension de Pd(KN) est dit unisolvent s'il n'est pas contenu dans l'ensemble des zéros d'un polynôme de degré d. Pour toute fonction f définie sur A, il existe un unique L[A;f] dans Pd(KN) tel que L[A;f]=f sur A, appelé le polynôme d'interpolation de Lagrange de f en A. Les polynômes d'interpolation de Kergin et d'Hakopian sont deux généralisations naturelles en plusieurs variables de l'interpolation de Lagrange à une variable. La construction de ces polynômes nécessite le choix de points à partir desquels on construit certaines formes linéaires qui sont des moyennes intégrales et qui fournissent les conditions d'interpolation. La qualité des approximations fournies par les polynômes d'interpolation dépend pour une large mesure du choix des points d'interpolation. Cette qualité est mesurée par la croissance de la norme de l'opérateur linéaire qui à toute fonction continue associe son polynôme d'interpolation. Cette norme est appelée la constante de Lebesgue (associée au compact et aux points d'interpolation considérés). La majeure partie de cette thèse est consacrée à l'étude de cette constante. Nous donnons par exemples le premier exemple général explicite de familles de points possédant une constante de Lebesgue qui croit comme un polynôme. C'est une avancée significative dans ce domaine de recherche<br>This thesis deals with polynomial interpolation of functions in one and several variables. We shall be mostly concerned with Lagrange interpolation but one of our work deals with Kergin and Hakopian interpolants. We denote by K the field that may be either R or C, and Pd(KN) the vector space of all polynomials of N variables of degree at most d. The set A of KN is said to be an unisolvent set of degree d if it is not included in the zero set of a polynomial of degree not greater than d. For every function f defined on A, there exists a unique L[A; f ] in Pd(KN) such that L[A; f ] = f on A, which is called the Lagrange interpolation polynomial of a function f at A. Kergin and Hakopian interpolants are natural multivariate generalizations of univariate Lagrange interpolation. The construction of these interpolation polynomials requires the use of points with which one obtains a number of natural mean value linear forms which provide the interpolation conditions. The quality of approximation furnished by interpolation polynomials much depends on the choice of the interpolation points. In turn, the quality of the interpolation points is best measured by the growth of the norm of the linear linear operator that associates to a continuous function its interpolation polynomial. This norm is called the Lebesgue constant. Most of this thesis is dedicated to the study of such constant. We provide for instances the first general examples of multivariate points having a Lebesgue constant that grows like a polynomial. This is an important advance in the field

abstract: I focus on algorithms that generate good sampling points for function approximation. In 1D, it is well known that polynomial interpolation using equispaced points is unstable. On the other hand, using Chebyshev nodes provides both stable and highly accurate points for polynomial interpolation. In higher dimensional complex regions, optimal sampling points are not known explicitly. This work presents robust algorithms that find good sampling points in complex regions for polynomial interpolation, least-squares, and radial basis function (RBF) methods. The quality of these nodes is measured using the Lebesgue constant. I will also consider optimal sampling for constrained optimization, used to solve PDEs, where boundary conditions must be imposed. Furthermore, I extend the scope of the problem to include finding near-optimal sampling points for high-order finite difference methods. These high-order finite difference methods can be implemented using either piecewise polynomials or RBFs.<br>Dissertation/Thesis<br>Doctoral Dissertation Mathematics 2019