The Conditioning of a Linear Barycentric Rational Interpolant

Abstract

We study what a referee has asked us to call the “second Berrut rational interpolant”, introduced thirty years ago, which is linear in the interpolated function values and converges exponentially when the nodes are conformal images of Chebyshev points. We show that the Lebesgue constant for this interpolant grows just logarithmically with the number of nodes under reasonable assumptions, extending results of Bos et al. in 2013 for the corresponding first interpolant.

For Thanos Antoulas, on the occasion of his 70th birthday and in remembrance of our undergraduate years together at the ETH in Zurich.

1 Introduction

Polynomial interpolation has been a standard computational tool in applied mathematics at least since the time of Newton, Waring and Lagrange [12]. In its simplest version, it consists in associating to a vector $\mathbf {x} = [x_0,\ldots ,x_n]^T$ of, say, $n+1$ distinct abscissae, and a vector $\mathbf {f} = [f_0,\ldots ,f_n]^T$ of corresponding ordinates, which may be values of a function f or not, the unique polynomial $p_n[\mathbf {f}]$ of degree at most n that takes on the value $f_j$ at $x_j$, $j=0,\ldots ,n$. The corresponding mapping has several nice properties. It is linear: the polynomial interpolating a linear combination of $\mathbf {f}$-vectors is the linear combination of the corresponding polynomials, i.e., $p_n[\alpha \mathbf {f} + \beta \mathbf {g}] = \alpha p_n[\mathbf {f}] + \beta p_n[\mathbf {g}]$, $\forall \ \alpha ,\beta \in \text {I}\!\text {R}$; moreover, the uniqueness makes it a projection, a property that permits the study of the conditioning by means of the Lebesgue constant.

But it has its drawbacks, the main one being the fact that it is useful for large n only if the nodes are located in particular ways in the interpolation interval $[a,b] \equiv [\min x_j,\max x_j]$ [19, Chap. 5]. Long before the advent of electronic computing, for instance, Runge showed that, for the most important case of equidistant nodes, the interpolant of a meromorphic function converges only if the poles of the latter lie outside a certain region containing [a, b] [12]. And even for functions, such as $e^x$, for which the interpolant converges for equidistant points, it is extremely ill-conditioned for n large [13, Sect. 5.5].

It is therefore appropriate to look for alternative infinitely smooth interpolants which work well for general sets of nodes. In [3], the author took advantage of the observation by Werner [22] that, by modifying the so-called weights $\lambda _j$ in the barycentric formula

(1)

for $p_n$, one obtains a rational function, say $r_n[f]$, of degree $\le n$, i.e., with both numerator and denominator degrees at most n; the new suggestion was to choose weights $\beta _j$ different from the $\lambda _j$ to obtain a good denominator for the given set of nodes, instead of the unique denominator 1 for all sets of nodes in polynomial interpolation. That way the two properties of linearity and projection are preserved [4].

A good choice of the $\beta _j$ requires the ordering of the nodes according to

$$\begin{aligned} a = x_0< x_1< \cdots < x_n = b\,; \end{aligned}$$

(2)

indeed, the weights should alternate in sign, for otherwise the interpolant will not reproduce all linear functions [14]. In view of this, the simplest possible choice of the weights, as proposed in [3], is

$$\begin{aligned} \beta _j = (-1)^j, \end{aligned}$$

(3)

independently of the values of the nodes. We denote the corresponding interpolant by $R_0$; the referee has suggested that this should be called the “first Berrut rational interpolant” (see [14]). It was shown in [3] that $R_0$ has no real poles; moreover, its O(h)-convergence (where $h := \max _{i=0,\ldots ,n-1} (x_{i+1} - x_i)\big )$ and well-conditioning were conjectured. The O(h)-convergence was proved in [11] under a local mesh ratio condition.

For an approximation operator which is a projection, the conditioning is best addressed through its Lebesgue constant $\varLambda _n$ (see Sect. 2). For $R_0$, the latter has been shown to increase only logarithmically for the most frequently used sets of nodes [9], a behaviour as nice as that of polynomial interpolation with the most favourable nodes (see also [21]).

However, by considering the even rational trigonometric interpolant obtained by transferring the polynomial onto the circle with the transform $x = \cos \phi$ [3], one comes to the conclusion that the first and last terms of the sums in both the numerator and the denominator of the interpolant should appear only once and the other terms twice. After simplifying by a factor of two, one sees that the weights [3]

$$\begin{aligned} \beta _j = (-1)^j \delta _j,\qquad \delta _j := {\left\{ \begin{array}{ll} 1/2,&{}j=0 \text { or }j=n,\\ 1,&{}\text {otherwise,}\\ \end{array}\right. } \end{aligned}$$

(4)

should be better than (3). (To be precise, this formula for the weights holds in the present case, where $x_0 = a$ and $x_n = b$, i.e., where the interval $[x_0,x_n]$ covers the whole interval of interpolation: when the interpolant is to be used beyond one or both extremities, slightly more complicated formulae involving trigonometric functions should be used, see [3].) We denote the corresponding interpolant by $R_1$, the “second Berrut rational interpolant”. When the nodes are the Chebyshev points of the second kind, the weights (4) coincide with the $\lambda _j$ [13, p. 252], $R_1 \equiv p_n[\mathbf {f}]$, and exponential convergence is achieved if f is analytic in an ellipse containing [a, b] [20, p. 57]. It was shown in [3] that $R_1$ does not have any poles in [a, b] for any set of nodes, and conjectured in the same work that $R_1$ is well-conditioned. Additionally, it was proved in [2] that $R_1$ retains the exponential convergence when the $x_j$ are conformally shifted Chebyshev nodes, and conjectured that the convergence is $O(h^2)$ in general; conditions guaranteeing the latter are given in [5].

In 2007, Floater and Hormann [11] presented a family of interpolants with a higher order of convergence, which they denote by $d+1$, . For every d and every set of nodes $\mathbf {x}$, these authors give a linear rational interpolant $r_n^{(d)}[\mathbf {f}]$, depending on d, such that $\Vert r_n^{(d)}[\mathbf {f}]-f\Vert = O(h^{d+1})$. After constructing the interpolant as a blend of the $n-d$ interpolating polynomials corresponding to the subvectors of $d+1$ consecutive nodes, they provide the weights of its barycentric representation (which always exists, as shown in [7]). For equidistant nodes, $r_n^{(0)}[\mathbf {f}]$ and $r_n^{(1)}[\mathbf {f}]$ correspond to $R_0$ and $R_1$, respectively; however, this is not the case with other sets of nodes.

In the present paper, we study the Lebesgue constant of $R_1$ for equidistant and well-spaced nodes such as conformally shifted Chebyshev points of the second kind, which are the most important in practice. Our results are extensions of results of Bos et al. [9] for $R_0$.

2 The Conditioning of the Interpolant $R_1$

The conditioning of a problem is the sensitivity of its solution to perturbations of its data. (In many contexts, this is called stability, but in numerical analysis the latter term should be reserved for the stability of an algorithm [13, p. 33].) Here the data are the function values $\mathbf {f}$ and the solution is the interpolant

$$\begin{aligned} R_1(x) = {\sum _{j=0}^n}'' \frac{ (-1)^j f_j}{x-x_j} \Bigg / {\sum _{i=0}^n}'' \frac{ (-1)^j}{x-x_j}, \end{aligned}$$

(5)

where the double prime attached to a sum indicates that its first and last terms are halved.

The fact that $R_1$ is a linear projection operator into a linear space of functions with a Lagrange basis (i.e., a basis $\{b_j(x)\}$ with the Lagrange property $b_j(x_i) = \delta _{ij}$) leads to the fact that the norm of that operator, called its Lebesgue constant, provides a good characterization of the conditioning. Indeed, if one perturbs each $f_j$ by a number $e_j$, i.e., perturbing the vector $\mathbf {f}$ with the vector $\mathbf {e} := (e_j)$, then for a linear interpolant $r_n[\mathbf {f}]$

$$ r_n[\mathbf {f} + \mathbf {e}](x) = \sum _{j=0}^n (f_j + e_j)b_j(x) . $$

The corresponding perturbation of the interpolant amounts to

$$\begin{aligned} r_n[\mathbf {f} + \mathbf {e}](x) - r_n[\mathbf {f}](x)= & {} \sum _{j=0}^n e_jb_j(x)\nonumber \\ \end{aligned}$$

so that

$$\begin{aligned} \big |r_n{[}\mathbf {f} + \mathbf {e}](x) - r_n{[}\mathbf {f}](x)\big |\le & {} \sum _{j=0}^n | e_j|\cdot |b_j(x)|\nonumber \\\le & {} \Vert \mathbf {e}\Vert \sum _{j=0}^n |b_j(x)| \end{aligned}$$

(6)

where $\Vert \ \cdot \ \Vert$ denotes the vector infinity norm.

Equation (6) gives a local bound for the perturbation induced by $\mathbf {e}$. The function

$$\lambda _n(x) := \sum _{j=0}^n |b_j(x)|$$

is called the Lebesgue function of the interpolation operator, its infinity norm

$$\varLambda _n := \Vert \lambda _n\Vert $$

the Lebesgue constant. (It turns out that $\varLambda _n$ is the norm of the interpolation operator on the space of continuous functions.) Equation (6) then yields

$$\Vert r_n[\mathbf {f} + \mathbf {e}] - r_n[\mathbf {f}]\Vert \le \varLambda _n\cdot \Vert \mathbf {e}\Vert ; $$

$r_n$ being linear, this means $\Vert r_n[\mathbf {e}]\Vert /\Vert \mathbf {e}\Vert \le \varLambda _n$; the global relative perturbation of the interpolant is bounded by $\varLambda _n$.

Definition 1

We say that $\varLambda _n$ grows at most logarithmically with n, if

$$\begin{aligned} \varLambda _n \le a + b \ln n \end{aligned}$$

(7)

for some positive constants a and b and every $n>n_0$, .

The rational interpolant $r_n[\mathbf {f}]$ obtained by replacing the weights $\lambda _j$ in (1) by some $\beta _j$ independent of $\mathbf {f}$ can be written as $\sum _{j=0}^n f_jb_j(x)$ with the Lagrange basis functions

$$b_j(x) := \frac{\beta _j}{x-x_j} \Bigg / {\sum _{i=0}^n} \frac{\beta _i}{x-x_i},$$

so that [7]

$$\begin{aligned} \lambda _n(x) = \sum _{j=0}^n\left| \frac{\beta _j}{x-x_j}\right| \Bigg / \left| {\sum _{i=0}^n} \frac{\beta _i}{x-x_i}\right| . \end{aligned}$$

(8)

For $R_1$ this yields

$$ \lambda _n(x) = {\sum _{i=0}^n}'' \frac{1}{|x-x_i|} \Bigg / D(x), $$

where

$$ D(x) := \left| {\sum _{i=0}^n}'' \frac{(-1)^i}{x-x_i} \right| . $$

If x is one of the $x_j$’s, a limit calculation in (8) shows that $\lambda _n(x)=1$. Otherwise, let $x_k$ be the node at the immediate left of x, i.e., $x \in (x_k,x_{k+1})$. If k is odd and $\le n-5$, then

$$ D(x) = \cdots - \frac{\delta _{k-1}}{x-x_{k-1}} + \frac{1}{x-x_k} + \frac{1}{x_{k+1}-x} - \frac{1}{x_{k+2}-x} + \cdots , $$

where $\delta _j$ is defined in (4). Therefore we may write the numerator of $\lambda _n(x)$ as $D(x) + 2N(x)$, where

$$ N(x) = \cdots + \frac{\delta _{k-3}}{x-x_{k-3}} + \frac{\delta _{k-1}}{x-x_{k-1}} + \frac{1}{x_{k+2}-x} + \frac{1}{x_{k+4}-x} + \cdots $$

(setting $\delta _j = 0$ for $j < 0$) to obtain

$$\lambda _n(x) = 1 + 2N(x)/D(x).$$

Note that all terms of N are positive. If k is even, one may multiply all terms in D and N by $-1$ to get the same expression for $\lambda _n$.

At first sight, it seems that, in view of the factors 1/2 arising in the first and last terms, one must study the two extremal intervals $[x_0,x_1]$ and $[x_{n-1},x_n]$ separately from the others. However, a shift by ${x_0+x_n\over 2} =: m$ of the interval $[x_0,x_n]$ together with the abscissae $x_j$, i.e.,

$$\widetilde{x}_j := x_j - m,\qquad \widetilde{x} := x - m$$

(so that m becomes 0) without change of the weights just shifts $\lambda _n(x)$. Moreover, a reflection $\widehat{x}_j := - x_j$ and $\widehat{x} := - x$ reflects $\lambda _n(x)$ as well. Also, $\lambda _n(x)$ is unchanged by a multiplication of all weights by $-1$. Thus, if there are at least two points on each side of m, we may bound $\lambda _n(x)$ only on $[x_0,m]$: bounds for $x\in \ (m,x_n]$ are obtained after a reflection with respect to m and a multiplication of the weights by $-1$, if n is odd. This shows that it suffices to treat just the case $x\in [x_0,x_1]$ separately, and explains why the $\delta _j$’s appear to the left only in D and N above.

Lemma 1

For $x \in (x_k,x_{k+1})$, $1\le k \le \left[ {n\over 2}\right]$,

$$\begin{aligned} D(x) \ge A_1 + A_2, \end{aligned}$$

(9)

where

$$ A_1 = \frac{x_k-x_{k-1}}{(x_{k+1}-x_{k-1})(x_{k+1}-x_k)}, \qquad A_2 = \frac{x_{k+2}-x_{k+1}}{(x_{k+1}-x_k)(x_{k+2}-x_k)}, $$

and

$$\begin{aligned} N(x) \le B_1 + B_2 \end{aligned}$$

(10)

where

$$ B_1 = {\sum _{i \ge 0}}' \frac{1}{x_k-x_{k-1-2i}}, \qquad B_2 = {\sum _{i \ge 0}}' \frac{1}{x_{k+2+2i}-x_{k+1}} $$

and the prime means that, if present, the terms $1/(x_k - x_0)$, resp. $1/(x_n - x_{k+1})$, are to be multiplied by 1/2.

Proof

For the denominator,

$$ D(x) \ge D_1(x) + D_2(x), $$

where

$$ D_1(x) := - \frac{\delta _{k-1}}{x-x_{k-1}} + \frac{1}{x-x_k} \ge \frac{x_k-x_{k-1}}{(x-x_{k-1})(x-x_k)}, $$

and

$$ D_2(x) := \frac{1}{x_{k+1}-x} - \frac{1}{x_{k+2}-x} = \frac{x_{k+2}-x_{k+1}}{(x_{k+1}-x)(x_{k+2}-x)}. $$

(In D, all pairs of terms corresponding to nodes to the left of $x_{k-1}$ are positive, and so is the term corresponding to $x_0$ if k is even; the same holds accordingly to the right of $x_{k+1}$. When $k=1$, the factor $\delta _0$ in front of $1/(x-x_0)$ makes D even larger.) Since $D_1$ and $D_2$ are decreasing, respectively increasing, for $x \in (x_k,x_{k+1})$,

$$ D_1(x) \ge D_1(x_{k+1}) = A_1, \qquad D_2(x) \ge D_2(x_k) = A_2. $$

For the numerator,

$$ N(x) = N_1(x) + N_2(x), $$

where

$$ N_1(x) = \cdots + \frac{\delta _{k-3}}{x-x_{k-3}} + \frac{\delta _{k-1}}{x-x_{k-1}}, $$

and

$$ N_2(x) = \frac{1}{x_{k+2}-x} + \frac{1}{x_{k+4}-x} + \cdots . $$

Since $N_1$ and $N_2$ are decreasing and increasing, respectively, for $x \in (x_k,x_{k+1})$,

$$ N_1(x) \le N_1(x_k) = B_1, \qquad N_2(x) \le N_2(x_{k+1}) = B_2. $$

   $\blacksquare$

One proves in a similar way the following corresponding results for $k=0$.

Lemma 2

For $x \in (x_0,x_{1})$,

$$\begin{aligned} D(x) \ge A_1 + A_2, \end{aligned}$$

(11)

where

$$ A_1 = \frac{1/2}{x_1 - x_0}, \qquad A_2 = \frac{x_{2}-x_{1}}{(x_{1}-x_0)(x_{2}-x_0)}, $$

and

$$\begin{aligned} N(x) \le B_2 \end{aligned}$$

(12)

where

$$ B_2 = {\sum _{i \ge 0}}' \frac{1}{x_{2i+2}-x_{1}}. $$

2.1 Equidistant Nodes

For uniformly spaced points $x_k = a + kh$, $h = (b-a)/n$, the lemmas imply that $D(x) \ge 1/h$ for every $x\in [a,b]$. Moreover,

$$\begin{aligned} B_1&\le {1\over h}\left( 1 + {1\over 3} + {1\over 5} + \cdots + {1\over \ell }\right) ,\qquad \ell = {\left\{ \begin{array}{ll} k-1,&{}k \text { even,}\\ k,&{}k \text { odd,} \end{array}\right. } \end{aligned}$$

and

$$\begin{aligned} B_2&\le {1\over h}\left( 1 + {1\over 3} + {1\over 5} + \cdots + {1\over \ell }\right) ,\qquad \ell = {\left\{ \begin{array}{ll} n-k-1,&{}n-k \text { even,}\\ n-k-2,&{}n - k \text { odd,} \end{array}\right. } \end{aligned}$$

so that $N(x) < \frac{1}{h} L$ with

$$\begin{aligned} L := \left( 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{k-1} + \frac{1}{k}\right) + \left( 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n-k-1}\right) . \end{aligned}$$

(13)

As in similar proofs, we now use the fact that $\ln (2j+1)$ is an upper bound of the jth sum of the harmonic series, so that

$$ L \le \ln (2k+1) + \ln (2(n-k-1)+1), $$

which is maximized over real k in $[0,n-1]$ by $k=(n-1)/2$, implying that

$$\begin{aligned} L \le 2\ln (n), \end{aligned}$$

(14)

and therefore,

$$ \lambda _n(x) \le 1 + 4 \ln (n). $$

Theorem 1

For uniformly spaced nodes, the Lebesgue constant of the interpolant $R_1$ grows at most logarithmically with n.

This result is already known as the case $d=1$ of [8]. However, the above proof of the bound for D does not make use of the original formula for the Floater–Hormann interpolant, merely of the barycentric formula.

We have confirmed this logarithmic growth numerically. The second column of Table 1 displays $\varLambda _n$ for doubling numbers of interpolation nodes. To check the constant b in the logarithmic growth, we have also computed after every pair (n, 2n) an approximation $\widehat{a}$ and $\widehat{b}$ in the logarithmic growth formula by solving the system of equations

$$\begin{aligned} \widehat{a} + \widehat{b} \ln (2n + 2)= & {} \varLambda _{2n + 2}\\ \widehat{a} + \widehat{b} \ln (n + 1)= & {} \varLambda _{n + 1}. \end{aligned}$$

The corresponding values of $\widehat{b}$ are given in the third column of the table. Compared with the number $2/\pi = 0.6366197723675814$, they are in line with the main term of the asymptotic formula for the Lebesgue constant of $R_0$ given in [15, 23]. (All the computations described in this article were performed in MATLAB on MacBook Pro computers.)

Table 1 The Lebesgue constant $\varLambda _n$ for equidistant and shifted equidistant nodes. For each of the two we give the constant itself as well as the empirical value $\widehat{b}$ of the factor of $\ln (n)$

2.2 Well-Spaced Nodes

The article [9] introduces the following property of interpolation points.

Definition 2

For each , let $X_n := \{x_k\}_{k=0}^n$ be a set of interpolation nodes satisfying property (2) and let

$$ h_k := x_{k+1}-x_k,\qquad k=0,\ldots ,n-1. $$

An array of such sets is called well-spaced if there exist two constants K and R, $R\ge 1$, both independent of n, such that the three conditions

$$\begin{aligned} {x_k-x_{k-1}\over x_k - x_j}&\le {K\over k-j},\qquad k=1,\ldots ,n,\quad j = 0,\ldots ,k-1, \end{aligned}$$

(15)

$$\begin{aligned} {x_{k+1}-x_k\over x_j-x_k}&\le {K\over j-k},\qquad k=0,\ldots ,n-1,\quad j = k+1,\ldots ,n,\end{aligned}$$

(16)

$$\begin{aligned} {h_k\over h_{k-1}} \le R,&\quad {h_{k-1}\over h_k}\le R,\qquad k = 1,\ldots ,n-1, \end{aligned}$$

(17)

hold for every set of nodes $X_n$.

We shall indifferently call the array and the nodes well-spaced. Note that the property of well-spacing is invariant with respect to translation or spacing of the nodes.

The authors of [9] established that every such array leads to a logarithmic growth of the Lebesgue constant of $R_0$:

Theorem 2

If is an array of well-spaced nodes, then the Lebesgue constant of the interpolant $R_0$ grows at most logarithmically with n.

We shall now use the above lemmas to show the same for $R_1$. Let first $k\ge 1$. Then, according to (17),

$$\begin{aligned} A_1&= {h_{k-1}\over (x_{k+1}-x_{k-1})h_k} \ge {1\over x_{k+1}-x_{k-1}}\cdot {1\over R}\\ \end{aligned}$$

and

$$\begin{aligned} A_2&= {h_{k+1}\over h_{k}(x_{k+2}-x_k)} \ge {1\over R}\cdot {1\over x_{k+2}-x_{k}} \end{aligned}$$

so that

$$\begin{aligned} A_1 + A_2 \ge {1\over R}\bigg ({1\over x_{k+2}-x_{k}} + {1\over x_{k+1}-x_{k-1}}\bigg ). \end{aligned}$$

(18)

Moreover, $x_{k+2}-x_{k} = h_k + h_{k+1} \le R(h_{k-1} + h_k) = R(x_{k+1}-x_{k-1})$ and $x_{k+1}-x_{k-1} = h_{k-1} + h_k \le (R+1)h_k$, so that

$$\begin{aligned} A_1 + A_2 \ge {1\over R}\Big ({1\over R} + 1\Big ){1\over x_{k+1}-x_{k-1}} \ge {R+1\over R^2}{1\over (R+1)h_{k}} = {1\over R^2h_k}. \end{aligned}$$

(19)

If $k=0$, we have in Lemma 2

$$ A_1 + A_2 \ge A_1 = {1\over 2h_0}.$$

On the whole, we therefore have for $x\in (x_k,x_{k+1})$

$$ D(x) \ge {1\over Sh_k}$$

with

$$ S := {\left\{ \begin{array}{ll} 1,&{}k=0,\\ R^2,&{}k>0. \end{array}\right. } $$

In the upper bound for N, possible factors 1/2 may be ignored. We compute for $k\ne 0$

$$\begin{aligned} B_1&= {1\over x_k - x_{k-1}} + {1\over x_k - x_{k-3}} + {1\over x_k - x_{k-5}} + {1\over x_k - x_{k-7}} + \cdots \\&= {1\over x_k - x_{k-1}}\left( 1 + {x_k - x_{k-1}\over x_k - x_{k-3}} + {x_k - x_{k-1}\over x_k - x_{k-5}} + {x_k - x_{k-1}\over x_k - x_{k-7}} + \cdots \right) . \end{aligned}$$

By (15), this may be bounded as

$$ B_1 \le {1\over h_{k-1}}\left( 1 + {K\over 3} + {K\over 5} + {K\over 7} +\cdots \right) . $$

Similarly for $B_2$:

$$\begin{aligned} B_2&= {1\over 2}{1\over x_{k+2} - x_{k+1}} + {1\over x_{k+4} - x_{k+1}} + {1\over x_{k+6} - x_{k+1}} + {1\over x_{k+8} - x_{k+1}} + \cdots \\&= {1\over x_{k+2} - x_{k+1}}\left( {1\over 2} + {x_{k+2} - x_{k+1}\over x_{k+4} - x_{k+1}} + {x_{k+2} - x_{k+1}\over x_{k+6} - x_{k+1}} + {x_{k+2} - x_{k+1}\over x_{k+8} - x_{k+1}} + \cdots \right) , \end{aligned}$$

which by (16) may be majorized as

$$ B_2 \le {1\over h_{k+1}}\left( 1 + {K\over 3} + {K\over 5} + {K\over 7} +\cdots \right) $$

with the same number of terms as in Sect. 2.1, so that with (13)

$$N(x) \le \left( {1\over h_{k-1}} + {1\over h_{k+1}}\right) KL$$

and thus with (19)

$$\begin{aligned} \lambda _n(x)&\le 1 + 2R^2 \left( {h_k\over h_{k-1}} + {h_k\over h_{k+1}}\right) 2K\ln (n)\\&\le 1 + 8KR^3\ln (n). \end{aligned}$$

If $k=0$, $B_1 = 0$ and $B_2 \le {1\over h_1}\left( 1 + {K\over 3} + {K\over 5} + \cdots \right)$ so that

$$N(x) \le {2\over h_1}K\ln (n)$$

and

$$\lambda _n(x) \le 1 + {h_0\over h_1}4K\ln (n) \le 1 + 4 K R \ln (n).$$

This establishes our first main theorem.

Theorem 3

If is an array of well-spaced nodes, then the Lebesgue constant of the interpolant $R_1$ grows at most logarithmically with n.

2.3 Conformally Shifted Nodes

The complexity of the pseudospectral solution of a boundary value problem can often be drastically reduced by a move of the points, for instance to improve the conditioning of the system of equations to be solved, or to have more points close to a steep gradient (front).

In [16], Kosloff and Tal-Ezer suggested applying such point shifts to loosen the step restriction in the solution of the systems of ordinary differential equations arising from the pseudospectral method of lines applied to time evolution problems. The idea is to introduce, besides the interval I on which the function is to be interpolated, another interval J containing the standard points (such as equidistant or Chebyshev). Then, to obtain a particular set of points in I, a (one-to-one) conformal map of a domain containing J, say g, is used, which applies J onto I, thereby determining the desired shifted points. Since g is infinitely differentiable, the composite function $f\circ g$ inherits the differentiability properties of f.

Recall that $R_1$ coincides with the interpolating polynomial, when the nodes are Chebyshev points of the second kind, so that it converges exponentially to interpolated functions which are analytic. Recall also that $R_1$ retains the exponential convergence for the same class of functions, when the Chebyshev points of the second kind are shifted conformally [2]. This example of use of $R_1$ is likely the most important, as it greatly improves the accuracy of pseudospectral solutions of boundary value ordinary and partial differential equations whose solution displays large gradients: see the applications in explosion modeling [18], fluid infiltration [10] and finance [17]. We shall now see how the results of Bos et al. [9] and the above theorems imply the logarithmic growth of the Lebesgue constant for such nodes.

Bos et al. work on the interval [0, 1]. This is indeed general, as one immediately sees that a shift and a contraction/dilation of the interval of interpolation do not modify the Lebesgue function (8) and the Lebesgue constant is thus unaffected by such operations. These authors give the following definition of a (regular) distribution function of nodes.

Definition 3

A function $F\in C[0,1]$ is a distribution function, if it is a strictly increasing bijection of the interval [0, 1]. F is regular, if $F\in C^1[0,1]$ and $F'$ has a finite number of zeros in [0, 1] with finite multiplicities.

Given a distribution function F and some , the authors define the associated interpolation nodes $X_n = X_n(F)$ as the set of $x_k$ with

$$\begin{aligned} x_k := F(k/n),\qquad k=0,1,\ldots ,n. \end{aligned}$$

(20)

They then prove the following result.

Theorem 4

If F is a regular distribution function and $X_n$ are the associated interpolation nodes from (20) for every , then the array of nodes is well-spaced.

Since a conformal map g cannot have any zero derivative in its domain [1, p. 133], Theorem 2 automatically yields the following results.

Corollary 1

The Lebesgue constants of $R_0$ as well as of $R_1$ with conformally shifted equidistant points grow at most logarithmically with n.

Proof

For $R_0$, the result follows immediately from Theorem 3.5 in [9] and Theorem 2 above, for $R_1$ from Theorem 3.    $\blacksquare$

Among their examples of regular distributions, Bos and al. give the extrema of the Chebyshev polynomials, which are the Chebyshev points of the second kind.

Lemma 3

A composition of regular distribution functions is itself a regular distribution function.

Proof

This follows directly from the chain rule.    $\blacksquare$

Corollary 2

The Lebesgue constant of $R_1$ with conformally shifted Chebyshev points of the second kind grows at most logarithmically with n.

Proof

Let g(y) be the conformal map of the interval containing the Chebyshev points to the interpolation interval. g being conformal, its derivative does not have any zeros, so that g is a regular distribution function on J. Then $g\circ F$ is a composition of regular distribution functions, thus a regular distribution function as well, according to Lemma 3. The corresponding array of nodes is well-spaced according to Theorem 4 and the Lebesgue constant of $R_1$ with a well-spaced array grows at most logarithmically (Theorem 3).    $\blacksquare$

We have numerically verified this logarithmic behavior of the Lebesgue constant with conformally shifted points. To increase the efficiency of methods for solving differential problems, it is natural to move more points toward the location of a front. A simple map for the case where the front lies in the center of the interval $[-1,1]$ is that suggested by Kosloff and Tal-Ezer for another purpose and mentioned above,

$$\begin{aligned} x = g_\alpha (y) = {\arcsin (\alpha y)\over \arcsin (\alpha )},\qquad 0< \alpha < 1. \end{aligned}$$

(21)

See the improvement in accuracy in [6]. In the limit $\alpha \rightarrow 0$, the nodes remain the equidistant ones. In the limit $\alpha \rightarrow 1$, the singularities at $\pm 1/\alpha$ of $g_\alpha$ tend toward the extremities of the interval.

First we have repeated the experiment documented in columns 2 and 3 of Table 1 for equidistant points shifted with the map (21) and $\alpha = 0.9$. The results are in columns 4 and 5: they demonstrate that the constant b in (7) seems quite independent of the shift.

Then we have repeated the experiment of Table 1, but now with Chebyshev points of the second kind and shifted Chebyshev points of the second kind. The results, given in Table 2, seem to show that the main term of the Lebesgue constant does not change much with a conformal shift of Chebyshev nodes, and is very close to the one corresponding to equidistant points.

Table 2 The Lebesgue constant $\varLambda _n$ for Chebyshev points of the second kind, and the same shifted. The values of $\widehat{b}$ have the same meaning as in Table 1

3 Conclusion

This article has been devoted to the study of the behaviour, as the number of nodes increases, of the second “Berrut” interpolant introduced some decades ago. We have shown that, at least in the instances of practical interest, the interpolant enjoys the same perfect condition of its special case of the usual Chebyshev interpolating polynomial, and likewise of its first-order variant $R_0$, with a Lebesgue constant growing at most logarithmically. This is true in particular of the important case of the shifted Chebyshev nodes used in practical applications, and justifies their use with arbitrary large numbers of nodes.