Lebesgue constants of the classical interpolation node families

edit · history · discussion · files · long url · analysis algebraic

Numbers

$X_n$

$n$

$\Lambda_n(X_n)$

equally spaced nodes including the endpoints

5/4

equally spaced nodes including the endpoints

1.631130309440898824704541501887023924442356613450159352783580830696850500934221140320203718912726317

equally spaced nodes including the endpoints

2.207824397325842998291108864446305774234274567799470245566833288732312260412173069676924205814665708

Chebyshev points of the first kind

1.414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641573

Chebyshev points of the first kind

5/3

Chebyshev points of the first kind

1.847759065022573512256366378793576573644833251727284972230195462561070015002204717429679869700689192

Chebyshev points of the first kind

1.988854381999831757127338934985020988352494687689220579416717796328416740510243919531531526703025820

Chebyshev–Lobatto points

5/4

Chebyshev–Lobatto points

5/3

Chebyshev–Lobatto points

1.798761803322554850762684141827908418424249391062539717614633092562537334065546723334659893260069350

stretched Chebyshev points

5/4

stretched Chebyshev points

1.429872717139877985293875618662785234253018709710226589579708722227491354967790854453805596509561220

stretched Chebyshev points

1.570167488417154209061287536755426611300515144937079443715744104690364783546673282625440284278610491

Gauss–Legendre points

1.732050807568877293527446341505872366942805253810380628055806979451933016908800037081146186757248576

Gauss–Legendre points

7/3

Gauss–Legendre points

2.855099291537834383569220110501426012286905815342097738203087538717520360780725966256320554862224607

Gauss–Legendre points

3.322200088446918493260573419283958297976051230995573999370638476934729241981056699436049039883171787

Gauss–Lobatto points

5/4

Gauss–Lobatto points

3/2

Gauss–Lobatto points

1.635881637422433746209944628138593994433910386351697841677802479401197498920573759310348829968958051

Definition

For a named family $X_n=\{x_0,\ldots,x_n\}$ of interpolation nodes in $[-1,1]$, this table gives the Lebesgue constant $\Lambda_n(X_n)$ [1], where $n$ is the interpolation degree.

Parameters

$X_n$

— node family (equally spaced, Chebyshev first kind, Chebyshev–Lobatto, stretched Chebyshev, Gauss–Legendre, or Gauss–Lobatto)

$n$

— interpolation degree ($n\geq 1$)

Formulas

(1)

$\lambda_n(x;X_n)=\sum_{j=0}^n |\ell_j(x)|$, where $\ell_j(x)=\prod_{m\neq j}(x-x_m)/(x_j-x_m)$. Then $\Lambda_n(X_n)=\max_{-1\leq x\leq1}\lambda_n(x;X_n)$.

Comments

(2)

The nodes are written on $[-1,1]$. The equally spaced family is $x_j=-1+2j/n$. The Chebyshev points of the first kind [2] are $x_j=\cos((2j+1)\pi/(2n+2))$, the roots of $T_{n+1}$. The Chebyshev–Lobatto points are $x_j=\cos(j\pi/n)$, the extrema of the Chebyshev polynomial $T_n$. The cosines in these two Chebyshev families are entries of $\cos(\pi x)$ for rational $x$. The stretched Chebyshev points divide the Chebyshev points of the first kind by $\cos(\pi/(2n+2))$. Here $0\leq j\leq n$.

(3)

The Gauss–Legendre family uses the nodes of the $n+1$ point Nodes and weights of Gauss–Legendre quadrature rule. The Gauss–Lobatto family uses the nodes of the $n+1$ point Nodes and weights of Gauss–Lobatto quadrature rule, namely the endpoints $-1,1$ and the roots of the derivative of the Legendre polynomial $P_n$ when $n>1$.

(4)

The parameter $n$ is the interpolation degree, so each row uses $n+1$ nodes. Some sources index the same constants by the number of nodes.

(5)

This table gives constants for named node families. It does not give the minimal Lebesgue constant obtained by optimising over all node sets of a fixed size.

(6)

At $n=1$, the equally spaced, Chebyshev–Lobatto, stretched Chebyshev, and Gauss–Lobatto families all have nodes $\{-1,1\}$. At $n=2$, the same four families all have nodes $\{-1,0,1\}$, so their Lebesgue constants agree in those rows.

Programs

(P1)

Sage

# In the directory containing the attached generate.py:
from generate import LebesgueConstantsInterpolationNodes

generator = LebesgueConstantsInterpolationNodes()
generator.value({'family': 'equally-spaced', 'n': '5'}, 100)

Links

[1]

Wikipedia: Lebesgue constant

[2]

Wikipedia: Chebyshev nodes

Similar tables

Lagrange basis polynomials for equally spaced nodes — the equally spaced rows use nodes affinely equivalent to these, and the Lebesgue constant is the uniform norm of the corresponding interpolation operator

Chebyshev polynomials of the first kind — the first-kind Chebyshev node families are built from the roots and extrema of these polynomials

Nodes and weights of Gauss–Legendre quadrature — the Gauss–Legendre rows use the same nodes and omit the quadrature weights

Nodes and weights of Gauss–Lobatto quadrature — the Gauss–Lobatto rows use the same nodes and omit the quadrature weights

Newton–Cotes weights — the closed Newton–Cotes rules use equally spaced endpoint nodes affinely equivalent to the equally spaced rows here

Data properties

Entries are of type: real number

How well the digits are known: proven

Table is complete: no (it holds all six listed node families for interpolation degrees $1\leq n\leq4$, as a rectangular range for comparing the families; the next Gauss–Legendre row is already a multi-minute exact computation with the maximisation method used here)

How they were obtained:

The generator builds the node polynomials over $\mathbb{Q}$ and isolates their roots in Sage's algebraic real field. It forms the Lagrange basis exactly, splits $[-1,1]$ at the nodes, and on each interval uses the constant sign pattern of the basis polynomials to replace the Lebesgue function by one algebraic polynomial. The maximum is checked at every interval endpoint and at every real root of that polynomial's derivative; the algebraic maximum is then returned as a real ball with 192 guard bits beyond the 100 digits written, except when it is proved rational and is returned exactly.

As independent checks, the small-degree closed forms $\Lambda_1=1$ for the endpoint node families, $\Lambda_2=5/4$ for the four families with nodes $\{-1,0,1\}$, $\Lambda_1=\sqrt2$ for Chebyshev points of the first kind, and $\Lambda_1=\sqrt3$ for Gauss–Legendre nodes were derived directly from the node sets.