High dimensional polynomial interpolation on sparse grids

We study polynomial interpolation on a d-dimensional cube, where d is large. We suggest to use the least solution at sparse grids with the extrema of the Chebyshev polynomials. The polynomial exactness of this method is almost optimal. Our error bounds show that the method is universal, i.e., almost optimal for many different function spaces. We report on numerical experiments for d = 10 using up to 652 065 interpolation points. This revised version was published online in June 2006 with corrections to the Cover Date.     

The use of the stochastic arithmetic to estimate the value of interpolation polynomial with optimal degree

One of the considerable discussions in data interpolation is to find the optimal number of data which minimizes the error of the interpolation polynomial. In this paper, first the theorems corresponding to the equidistant nodes and the roots of the Chebyshev polynomials are proved in order to estimate the accuracy of the interpolation polynomial, when the number of data increases. Based on these theorems, then we show that by using a perturbation method based on the CESTAC method, it is possible to find the optimal degree of the interpolation polynomial. The results of numerical experiments are presented.     

The error norm of Gauss-Lobatto quadrature formulae for weight functions of Bernstein-Szegö type

Summary In certain spaces of analytic functions the error term of the Gauss-Lobatto quadrature formula relative to a (nonnegative) weight function is a continuous linear functional. Here we compute the norm of the error functional for the Bernstein-Szegö weight functions consisting of any of the four Chebyshev weights divided by an arbitrary quadratic polynomial that remains positive on [–1, 1]. The norm can subsequently be used to derive bounds for the error functional. The efficiency of these bounds is illustrated with some numerical examples.Work supported in part by a grant from the Research Council of the Graduate School, University of Missouri-Columbia.     

Exact order of Hoffman’s error bounds for elliptic quadratic inequalities derived from vector-valued Chebyshev approximation

In this paper, we introduce the exact order of Hoffman’s error bounds for approximate solutions of elliptic quadratic inequalities. Elliptic quadratic inequalities are closely related to Chebyshev approximation of vector-valued functions (including complex-valued functions). The set of Chebyshev approximations of a vector-valued function defined on a finite set is shown to be Hausdorff strongly unique of order exactly 2 ^s for some nonnegative integer s. As a consequence, the exact order of Hoffman’s error bounds for approximate solutions of elliptic quadratic inequalities is exactly 2 ^-s for some nonnegative integer s. The integer s, called the order of deficiency (which is computable), quantifies how much the Abadie constraint qualification is violated by the elliptic quadratic inequalities. Received: April 15, 1999 / Accepted: February 21, 2000?Published online July 20, 2000     

On a Steffensen-Hermite method of order three

In this paper we study a third order Steffensen type method obtained by controlling the interpolation nodes in the Hermite inverse interpolation polynomial of degree 2. We study the convergence of the iterative method and we provide new convergence conditions which lead to bilateral approximations for the solution; it is known that the bilateral approximations have the advantage of offering a posteriori bounds of the errors. The numerical examples confirm the advantage of considering these error bounds.     

The error norm of Gaussian quadrature formulae for weight functions of Bernstein-Szegö type

Summary We consider the Gaussian quadrature formulae for the Bernstein-Szegö weight functions consisting of any one of the four Chebyshev weights divided by an arbitrary quadratic polynomial that remains positive on [–1, 1]. Using the method in Akrivis (1985), we compute the norm of the error functional of these quadrature formulae. The quality of the bounds for the error functional, that can be obtained in this way, is demonstrated by two numerical examples.     

Fourier and barycentric formulae for equidistant Hermite trigonometric interpolation

We consider the Hermite trigonometric interpolation problem of order 1 for equidistant nodes, i.e., the problem of finding a trigonometric polynomial t that interpolates the values of a function and of its derivative at equidistant points. We give a formula for the Fourier coefficients of t in terms of those of the two classical trigonometric polynomials interpolating the values and those of the derivative separately. This formula yields the coefficients with a single FFT. It also gives an aliasing formula for the error in the coefficients which, on its turn, yields error bounds and convergence results for differentiable as well as analytic functions. We then consider the Lagrangian formula and eliminate the unstable factor by switching to the barycentric formula. We also give simplified formulae for even and odd functions, as well as consequent formulae for Hermite interpolation between Chebyshev points.     

Error estimates and condition numbers for radial basis function interpolation

For interpolation of scattered multivariate data by radial basis functions, an “uncertainty relation” between the attainable error and the condition of the interpolation matrices is proven. It states that the error and the condition number cannot both be kept small. Bounds on the Lebesgue constants are obtained as a byproduct. A variation of the Narcowich-Ward theory of upper bounds on the norm of the inverse of the interpolation matrix is presented in order to handle the whole set of radial basis functions that are currently in use.     

Multipoint Taylor formulæ

Summary. The main result of this paper is an abstract version of the Kowalewski–Ciarlet–Wagschal multipoint Taylor formula for representing the pointwise error in multivariate Lagrange interpolation. Several applications of this result are given in the paper. The most important of these is the construction of a multipoint Taylor error formula for a general finite element, together with the corresponding –error bounds. Another application is the construction of a family of error formul? for linear interpolation (indexed by real measures of unit mass) which includes some recently obtained formul?. It is also shown how the problem of constructing an error formula for Lagrange interpolation from a D–invariant space of polynomials with the property that it involves only derivatives which annihilate the interpolating space can be reduced to the problem of finding such a formula for a ‘simpler’ one–point interpolation map. Received March 29, 1996 / Revised version received November 22, 1996     

Convergence of CG and GMRES on a tridiagonal Toeplitz linear system

The Conjugate Gradient method (CG), the Minimal Residual method (MINRES), or more generally, the Generalized Minimal Residual method (GMRES) are widely used to solve a linear system Ax=b. The choice of a method depends on A’s symmetry property and/or definiteness), and MINRES is really just a special case of GMRES. This paper establishes error bounds on and sometimes exact expressions for residuals of CG, MINRES, and GMRES on solving a tridiagonal Toeplitz linear system, where A is Hermitian or just normal. These expressions and bounds are in terms of the three parameters that define A and Chebyshev polynomials of the first or second kind. AMS subject classification (2000)  65F10, 65N22     

一类单位圆上的Chebyshev权的Cauchy型求积公式

在本文中,我们首先给出一些基本的结果和一些概念,然后给出单位圆上带Cheby shev权的一些Cauchy主值积分的求积公式,最后给出了它们的误差估计.     

The rate of convergence of GMRES on a tridiagonal Toeplitz linear system

The Generalized Minimal Residual method (GMRES) is often used to solve a nonsymmetric linear system Ax = b. But its convergence analysis is a rather difficult task in general. A commonly used approach is to diagonalize A = XΛ X ⁻¹ and then separate the study of GMRES convergence behavior into optimizing the condition number of X and a polynomial minimization problem over A’s spectrum. This artificial separation could greatly overestimate GMRES residuals and likely yields error bounds that are too far from the actual ones. On the other hand, considering the effects of both A’s spectrum and the conditioning of X at the same time poses a difficult challenge, perhaps impossible to deal with in general but only possible for certain particular linear systems. This paper will do so for a (nonsymmetric) tridiagonal Toeplitz system. Sharp error bounds on and sometimes exact expressions for residuals are obtained. These expressions and/or bounds are in terms of the three parameters that define A and Chebyshev polynomials of the first kind.     

Global Error Estimation with Runge--Kutta Methods

An analysis of global error estimation for Runge—Kuttasolutions of ordinary differential equations is presented. Thebasic technique is that of Zadunaisky in which the global erroris computed from a numerical solution of a neighbouring problemrelated to the main problem by some method of interpolation.It is shown that Runge—Kutta formulae which permit validglobal error estimation using low-degree interpolation can bedeveloped, thus leading to more accurate and computationallyconvenient algorithms than was hitherto expected. Some specialRunge—Kutta processes up to order 4 are presented togetherwith numerical results.     

On the Smolyak cubature error for analytic functions

We consider Smolyak's construction for the numerical integration over the d‐dimensional unit cube. The underlying class of integrands is a tensor product space consisting of functions that are analytic in the Cartesian product of ellipses. The Kronrod–Patterson quadrature formulae are proposed as the corresponding basic sequence and this choice is compared with Clenshaw–Curtis quadrature formulae. First, error bounds are derived for the one‐dimensional case, which lead by a recursion formula to error bounds for higher dimensional integration. The applicability of these bounds is shown by examples from frequently used test packages. Finally, numerical experiments are reported. This revised version was published online in June 2006 with corrections to the Cover Date.     

Local uniform error estimates for spherical basis functions interpolation

This paper discusses local uniform error estimates for spherical basis functions (SBFs) interpolation, where error bounds for target functions are restricted on spherical cap. The discussion is first carried out in the native space associated with the smooth SBFs, which is generated by a strictly positive definite zonal kernel. Then, the smooth SBFs are embedded in a larger space that is generated by a less smooth kernel, and for the target functions outside the original native space, the local uniform error estimates are established. Finally, some numerical experiments are given to illustrate the theoretical results. Copyright © 2013 John Wiley & Sons, Ltd.     

有限元近似可计算的误差界

本文研究了有限元近似可计算的误差界，利用“二次插值过渡”方法，获得二维线性、双线性有限元和三维三线性有限元的新的插值常数估计值．理论分析和数值实验表明该结果是有效的，发展了P．Arbenz等人的工作．     

On convergence rates of prolate interpolation and differentiation

Prolate spheroidal wave functions of order zero (PSWFs) are widely used in scientific computation. There are few results about the error bounds of the prolate interpolation and differentiation. In this paper, based on the Cauchy’s residue theorem and asymptotics of PSWFs, the convergence rates are derived. To get stable approximation, the first barycentric formula is applied. These theoretical results and high accuracy are illustrated by numerical examples.     

Convergence of a continuation method under Lipschitz continuous derivative in Banach spaces

The aim of this paper is to use recurrence relations instead of majorizing sequences to establish the semilocal convergence of a continuation method combining Chebyshev method and Convex acceleration of Newton??s method for solving nonlinear equations in Banach spaces under the assumption that the first Fréchet derivative satisfies the Lipschitz continuity condition. An existence-uniqueness theorem is given. Also, a closed form of error bounds is derived in terms of a real parameter ????[0,1]. Two numerical examples are worked out to demonstrate the efficacy of our convergence analysis. On comparing the existence and uniqueness regions for the solution obtained by our analysis with those obtained by using majorizing sequences, it is found that our analysis gives better results in both the examples. Further, we observed that for particular values of ??, our analysis reduces to those for Chebyshev method (??=0) and Convex acceleration of Newton??s method (??=1) respectively with improved results.     

L p -Error Bounds for Hermite Interpolation and the Associated Wirtinger Inequalities

The B-spline representation for divided differences is used, for the first time, to provide L _p -bounds for the error in Hermite interpolation, and its derivatives, thereby simplifying and improving the results to be found in the extensive literature on the problem. These bounds are equivalent to certain Wirtinger inequalities. The major result is the inequality where H_Θ f is the Hermite interpolant to f at the multiset of n points Θ, and is the diameter of . This inequality significantly improves upon Beesack's inequality, on which almost all the bounds given over the last 30 years have been based. Date received: June 24, 1994 Date revised: February 4, 1996.     

改进Lagrange插值多项式误差上界的系数

当用Lagrange插值多项式逼近函数时,重要的是要了解误差项的性态.本文研究具有等距节点的Lagrange插值多项式,估计了Lagrange插值多项式逼近函数误差项的上界,改进了小于5次Lagrange插值多项式逼近函数误差界的系数.