{'fraction_non_alphanumeric': 0.07098571926158133, 'fraction_numerical': 0.025148032044583768, 'mean_word_length': 4.067419696434874, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Interpolation Approximation: Convergence rates for polynomial interpolation for functions of limited regularity

The convergence rates on polynomial interpolation in most cases are estimated by Lebesgue constants. These estimates may be overestimated for some special points of sets for functions of limited regularities. In this paper, by applying the Peano kernel theorem and Wainerman's lemma, new formulas on the convergence rates are considered. Based upon these new estimates, it shows that the interpolation at strongly normal pointsystems can achieve the optimal convergence rate, the same as the best polynomial approximation. Furthermore, by using the asymptotics on Jacobi polynomials, the convergence rates are established for Gauss-Jacobi, Jacobi-Gauss-Lobatto or Jacobi-Gauss-Radau pointsystems. From these results, we see that the interpolations at the Gauss-Legendre, Legendre-Gauss-Lobatto pointsystem, or at strongly normal pointsystems, has essentially the same approximation accuracy compared with those at the two Chebyshev piontsystems, which also illustrates the equally accuracy of the Gauss and Clenshaw-Curtis quadrature. In addition, numerical examples illustrate the perfect coincidence with the estimates, which means the convergence rates are optimal.

1. Introduction. Numerical analysis is built on a strong foundation of approximation theory. In almost every area of numerical analysis it is a fact that, sooner or later, the discussion comes down to approximation theory (Trefethen [57]).
A central problem in approximation theory is to construct accurate and efficient approximation to the targeting function by simple functions. The most useful class of simple functions are polynomials. There exist many investigations for the behavior of continuous functions approximated by polynomials. Weierstrass [73] in 1885 proved the well known result that every continuous function f (x) in [−1, 1] can be uniformly approximated as closely as desired by a polynomial function. This result has both practical and theoretical relevance, especially in polynomial interpolation.
Polynomial interpolation is a fundamental tool in many areas of scientific computing. Lagrange interpolation is a classical technique for approximation of continuous functions. Let us denote by There is a well developed theory that quantifies the convergence or divergence of the Lagrange interpolation polynomials (Trefethen [59]). Two key notions for interpolation in a given set of points are that of the Lebesgue function λ n (x), (1.4) which are of fundamental importance (Cheney [9], Davis [12] and Szegö [54]). The Lebesgue constant can also be interpreted as the ∞-norm of the projection operator L n : C([−1, 1]) → P n−1 where P n−1 is the set of polynomials of degree less than or equal to n − 1.
Nevertheless, it is worth noting that if f (x) has an absolutely continuous (k − 1)st derivative f (k−1) on [−1, 1] for some k ≥ 1 and its k-th derivative f (k) is of bounded variation Var(f (k) ) < ∞, Mastroianni and Szabados [41], Trefethen [59] and Xiang et al. [76] proved that (1.10) where L n [f ] is at the n Chebyshev points of first or second kind, which has the same asymptotic order as for the best approximation p * n−1 ; see de la Vallée Poussin [62]. In particular, for f (x) = |x|, the error on the L n [f ] at the above two Chebyshev point systems satisfies [59,76]), while (see Bernstein [3] and Varga and Capenter [63]). Thus, the error estimate (1.5) may be overestimated for functions of limited regularity with some sets of special points. Moreover, it has been observed, by Clenshaw-Curtis [10] and O'Hara and Smith [29], that n-point Gauss quadrature and n-point Clenshaw-Curtis quadrature have essentially the same accuracy, which has been showed recently by Trefethen [58,59], Brass and Petras [6] and Xiang and Bornemann [75]. These two quadratures are derived from the interpolating polynomial based on the n Gauss-Legender and Clenshaw-Curtis points, respectively. This motivates us to conjecture that the interpolating polynomials based on the two point systems above have the same convergence rate. However, it can not be derived from (1.5).
In this paper, we present new and sharper convergence estimates of the interpolation error for functions of limited regularity. The key idea is to derive a Peano-type estimate for the interpolation error by the famous Peano kernel theorem [44]; on the other hand, application of Wainerman's lemma [72] allows us to bound the Peano-kernels whereby proving the ultimate estimate. Suppose f (x) has an absolutely continuous (r − 1)st derivative f (r−1) on [−1, 1], and its r-th derivative f (r) is of bounded variation Var(f (r) ) < ∞. We will show that Comparing (1.11) with (1.5), we see that in some sense. Particularly, from (1.12), it directly follows that the interpolation L n [f ] at the strongly normal point system (see Fejér [19,21]) can achieve the optimal convergence rate O Furthermore, ℓ (n) j ∞ can be explicitly estimated for Gauss-Jacobi or Jacobi-Gauss-Lobatto point systems, by using the asymptotics on Jacobi polynomials given by Szegö [54] and Sun [53] as follows • For the n Gauss-Jacobi points: • For the n Jacobi-Gauss-Lobatto points (the roots of (1 − x 2 )P (α,β) n−2 (x) = 0): From the above estimates, we see that the interpolation at the Gauss-Legendre or at the Legendre-Gauss-Lobatto point system, has essentially the same approximation accuracy compared with those at the two Chebyshev point systems. All of them satisfy that L n = O(1). In addition, the convergence rate is attainable, which is illustrated by some functions of limited regularity.
The paper is organized as follows: In section 2, we present the error of f (x) − L n [f ](x) for each fixed x ∈ [0, 1] by using the Peano representation and the bounded variation. In section 3, we introduce the interesting Wainerman's lemma and deduce the error bound on f − L n [f ] ∞ by L n . We consider, in section 4, the estimates of ℓ (n) j ∞ and derive convergence rates for the interpolating polynomials based on strongly normal point systems, Gauss-Jacobi and Jacobi-Gauss-Lobatto point systems sequentially. Numerical experiments also demonstrates the optimality of these theoretical convergence rates.
Throughout this paper, A ∼ B means that there exist positive constants C 1 and C 2 such that For simplicity, in the following we abbreviate x  k (x) as ℓ k (x). 2. The Peano kernel theorem. There are two general methods for deriving strict error bounds (Dahlquist and Björck [11]). One applies the norms and distance formula together with the Lebesgue constants, which often overestimates the error. The other is due to the Peano kernel theorem.
Let L be a continuous linear functional on the continuous function space 1]) and L(αf ) = αL(f ) for any scalar α. In addition, we assume L[P r−1 ] = {0} for some r ∈ {1, 2, . . .}, where P r−1 denotes the set of polynomials with degree less than or equal to r − 1.
The Peano kernel theorem (Peano [44], see also Kowalewski [35], Schmidt [50] and Mises [43]) is the identity For each fixed x ∈ [−1, 1], we consider the special functional , and then by the Peano theorem [44] Similar to the Peano kernel for quadrature [6], the kernel for interpolation satisfies the following properties.
In the following, we consider functions of limited regularity as Suppose that f (t) has an absolutely continuous  [55, pp. 143-145], we see that a function G : [−1, 1] → R is absolutely continuous if and only if it takes the form G(t) = t −1 g(y)dy + C for some absolutely integrable g : [−1, 1] → R and a constant C. It is obvious that such g is not unique. Then in this paper, we suppose f (t) satisfies (2.9) and define dy for all t ∈ [−1, 1] with g being absolutely integrable and of bounded variation . [58,59]. If f (r) is of bounded variation, then f (r+1) exists almost everywhere and f (r+1) ∈ L 1 ([−1, 1]) (see Lang [38] and Rudin [47]). Whereas, f (r) in [58,59] denotes an equivalent representation in the sense of almost everywhere. An example for f (x) = |t| is given in [58,59], where f (t) is not differentiable at t = 0, but f ′ can be chosen as Using the new condition, we see that |t| can be represented as |t| = 1 + t −1 g(y)dy with Then, following Brass and Petras [6] and integrating by parts, it yields Since g can be written as g = g 1 − g 2 with g 1 and g 2 are monotonically increasing, and Var(g) = Var(g 1 ) + Var(g 2 ) (see Lang [38, pp. 280-281]). Without loss of generality, let us assume g is monotonically increasing. Then by the second mean value theorem of integral calculus, it Then, for every positive integer ℓ and every u ∈ [−1, 1], there is a q u ∈ P ℓ satisfying and noting that E n [P n−1 ] = 0, by Theorem 2.2 we have Consequently, by Lemma 2.3 we get that From Theorem 2.2 and Lemma 2.4 we obtain that Theorem 2.5. Suppose f (t) satisfies (2.9), then for n ≥ r + 1 3. Wainerman's lemma. In the following, we shall focus on the estimate of K 1 ∞ . Notice that n j=1 ℓ j (t) ≡ 1 for t ∈ [−1, 1] and Thus, in these cases we obtain Suppose that x m+1 < u ≤ x m for some positive integer m, then for u ≤ x we get In particular, if x 1 = 1 or x n = −1, K 1 (u) can be estimated by (3.3), (3.4) or K 1 (−1) = 0. Lemma 3.1. (Wainerman's lemma [72]) Suppose x m+1 < u ≤ x m for some positive integer m, and let where sgn denotes the sign function.
Proof. The interesting result and its proof is published in Russian in [72]. For convenience and completeness, we present the proof here.
For x m+1 < u < x m , from the definition of ℓ k (t) we see that which directly leads to the desired result (3.5) for sgn(ℓ k (u)) based on k ≤ m or k > m, respectively.
In the following, we will show that sgn(a k (u)) also satisfies (3.5).
In the case k ≤ m: Since then by the Rolle's theorem it follows Note that a k (t) is a polynomial of degree n − 1, then a ′ k (t) is a polynomial of degree n − 2, which implies that y j are the exact zeros of a ′ k (t) and a ′ k (t) has the form of for some non-zero constant C. In addition, from (3.7) a ′ k (t) has alternative sign between these roots. Then, by a k (x k+1 ) = 0 and a k (x k ) = 1, it yields By the alternative property of a ′ k (t) between these roots, it deduces that sgn(a ′ k (t)) = (−1) j−k for t ∈ (y j+1 , y j ) and j > k, particularly, which, together with a k (x k+1 ) = a k (x k+2 ) = 0, derives sgn(a k (t)) = −1 for t ∈ (x k+2 , x k+1 ). Similarly, applying In the case k > m: By applying similar arguments, we derive a k (u) = (−1) k−m−1 for k > m. Furthermore, from (3.5) and the definition of a k (t), we see that immediately: for k ≤ m and x m+1 < u < x m , The special case of (3.6) when u = x m directly follows from |a k (x m )| = |ℓ k (x m )| by the definitions of a k (u) and ℓ k (u).
In the next section, we shall focus on estimates of L n for special points of sets.   Krylov [36,Theorem 7,p. 263]); that is, the clustering will be asymptotically the same: on [−1, 1], n points will be distributed with density (per unit length) as n tends to infinity (see Hale and Trefethen [27] and Trefethen [56]). Moreover, optimal point systems for polynomial interpolation often appears to be clustering near endpoints ±1 (see Z. Ditzian and V. Totik [13] and [58]). (The Gauss-Jacobi type point systems have this proposition.) The density of the zeros of orthogonal polynomials has been extensively studied in Erdös and Turán [16,17], Gatteschi [22] and Szegö [54].
4.1. Strongly normal point systems. One of the proofs of Weierstrass approximation theorem using interpolation polynomials was first presented by Fejér [19] in 1916 based on the This polynomial is known as the Hermite-Fejér interpolation polynomial.
It is worth noticing that if the point system is strongly normal, then v i (t) ≥ c > 0 for all i = 1, 2, . . . , n and t ∈ [−1, 1], and (see [20]) and then Theorem 4.1. Suppose f (t) satisfies (2.9) and {x j } n j=1 is a strongly normal point system, then for n ≥ r + 1 Following de la Vallée Poussin [62], the error bound indicates f − L n [f ] ∞ = O( f − p * n−1 ∞ ) for the interpolant at a strongly normal point system for a functions of limited regularity with V r < ∞ for some r ≥ 1.
Additionally, we implement the interpolation by the barycentric algorithms from [77] with m = 1 for Gauss-Jacobi point systems under α > −1 and β > −1, while for Jacobi-Gauss-Lobatto point systems under α > 0 and β > 0. In other cases, we used the barycentric algorithms together with for the Jacobi-Gauss-Lobatto point systems with α · β ≤ 0 at the N nodes, and for the Gauss-Jacobi-Radau point systems at the N nodes, respectively, where P N −2 (x) and P N −1 (x), calculated by the barycentric algorithms in [77], are the interpolant of f at the N − 2 and N − 1 Gauss-Jacobi points of P
Proof. In [53], the proof of Lemma 4.2 is given only for 0 ≤ θ k ≤ π 2 or k = m. That proof can be readily extended to 0 ≤ θ k ≤ 2π 3 due to (4.18). We complement the proof for 2π 3 < θ k < π and k = m next.
Remark 2. Theorem 4.3 implies at the roots of the Jacobi polynomial P Then the interpolations at the n-point Gauss-Legendre points and at the n-point Chebyshev points of first kind or second kind have essentially the same accuracy. All of them can achieve the optimal convergence rate O( f − p * n−1 ∞ ). Consequently, the corresponding quadrature Gauss, Clenshaw-Curtis and Fejér first rule have equally the same performance [74].
Here, we used Figs. 4.7-4.8 to illustrate the convergence rates for general Gauss-Jacobi point systems, where (α, β) are obtained by rand(1, 2) (1st row) and mrand(1, 2) with mrand(1, 2) ∞ > m − 1 for m = 2, 3, 4 (2nd row), respectively. From these figures, we see that the convergence rates are attainable too, which are in accordance with the estimates. Then the convergence rates at the Gauss-Jacobi point systems are optimal.
It is interesting to note that numerical experiments also show that the same occurs for analytic or smooth functions at these point systems. Here we illustrate the phenomenons by entire function f (x) = e x , i.e., analytic throughout the complex plane, f (x) = 1/(1 + 25x 2 ), which is analytic in a neighborhood of [−1, 1] but not throughout the complex plane, and f (x) = e −1/x 2 , which is not analytic in a neighborhood of [−1, 1] but is infinitely differentiable in [−1, 1].