Lebesgue Constants (Lagrange Interpolation)

N.B. A detailed on-line essay by S. Finch was the starting point for this entry.

Define the $n$th Lebesgue constant for the Lagrange Interpolating Polynomial by

$$\Lambda_n(X)\equiv \max_{-1\leq x\leq 1} \sum_{k=1}^n \left\vert{\,\prod_{j\not=k} {x-x_j\over x_k-x_j}}\right\vert.$$ (1)

It is true that

$$\Lambda_n>{4\over\pi^2}\ln n-1.$$ (2)

The efficiency of a Lagrange interpolation is related to the rate at which $\Lambda_n$ increases. Erdös (1961) proved that there exists a Positive constant such that

$$\Lambda_n>{2\over\pi}\ln n-C$$ (3)

for all $n$. Erdös (1961) further showed that

$$\Lambda_n<{2\over\pi}\ln n+4,$$ (4)

so (3) cannot be improved upon.

References

Erdös, P. ``Problems and Results on the Theory of Interpolation, II.'' Acta Math. Acad. Sci. Hungary 12, 235-244, 1961.

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/lbsg/lbsg.html