An Example of Optimal Nodes for Interpolation Revisited

Abstract

A famous unsolved problem in the theory of polynomial interpolation is that of explicitly determining a set of nodes which is optimal in the sense that it leads to minimal Lebesgue constants. In [11] a solution to this problem was presented for the first non-trivial case of cubic interpolation. We add here that the quantities that characterize optimal cubic interpolation (in particular: the minimal Lebesgue constant) can be compactly expressed as real roots of certain cubic polynomials with integral coefficients. This facilitates the presentation and impartation of the subject matter and may guide extensions to optimal higher-degree interpolation.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

7.1 Introduction

The Bernstein conjecture of 1931 and Kilgore’s theorem of 1977 [6] characterize, by means of the equioscillation property of the Lebesgue function, the optimal nodes which minimize the Lebesgue constant for n-th degree Lagrange polynomial interpolation. The Bernstein conjecture has been settled to the affirmative in 1978 [2, 7].

However, as put in [3]: In spite of this nice characterization, the optimal nodes as well as the optimal Lebesgue constants are not known explicitly.

Although the knowledge of these quantities may be of little practical importance, since they can be computed numerically for the first few values of n (see [1, 3, 9, 15]), and near-optimal nodes are explicitly known (see [3]), … the problem of analytical description of the optimal matrix of nodes is considered by pure mathematicians as a great challenge [3]. In [8] (p. xlvii) it is put more dramatically: The nature of the optimal set X* remains a mystery.

But at least the first non-trivial case of cubic interpolation has been demystified so that for n = 3 the desired analytical solution to the problem of explicitly determining the optimal nodes and the minimal Lebesgue constant is known [11]. To facilitate the presentation and impartation of this instructive example we add here alternative expositions of the minimal cubic Lebesgue constant and of the (positive) extremum point at which the local maximum of the optimal cubic Lebesgue function occurs: we identify them as roots of certain intrinsic cubic polynomials with integral coefficients. The third determining quantity, the (positive) optimal node for cubic interpolation, has already been described in this concise way [11].

Such a description is in the spirit of the open question raised in [4] (p. 21): Is there a set of relatively simple functionsf _n such that the roots off _n are the optimal nodes for Lagrange interpolation?

We will provide as simple functions f ₃ three cubic polynomials with integral coefficients whose roots yield the solution to the optimal cubic interpolation problem.

7.2 Three Cubic Polynomials with Integral Coefficients Whose Roots Yield the Solution to the Optimal Cubic Interpolation Problem

The situation is as follows (n = 3): It suffices to consider (algebraic) Lagrange interpolation on the zero-symmetric partition

$$-1 = x_{0} < x_{1} = -x_{2} < x_{2} < x_{3} = 1$$

(7.1)

of the canonical interval [ − 1, 1], so that only the placement of the positive node x ₂ remains critical. The sampled values y _i  = f(x _i ), 0 ≤ i ≤ 3, of some (continuous) function f which is to be interpolated on (7.1) by a cubic polynomial, do not enter into the discussion. We know from [11] that the following holds:

The square of the optimal node x ₂ = x ₂ ^∗ is given as the unique real root of a cubic polynomial with integral coefficients:

$$P_{3}(z) = -1 + 2z + 17{z}^{2} + 25{z}^{3}.$$

(7.2)

Proposition 7.1.

We add here that the analytic expression for x ₂ ^∗ as given in ([11],(22)) can alternatively be restated as

$$\begin{array}{lcl} x_{2}^{{\ast}}& =& \dfrac{1} {5\sqrt{3}}\sqrt{-17 +{ \left (\dfrac{14699 + 1725\sqrt{69} } {2} \right )}^{\frac{1} {3} } +{ \left (\dfrac{14699 - 1725\sqrt{69}} {2} \right )}^{\frac{1} {3} }} \\ & \; & \\ & =&0.4177913013\ldots \end{array}$$

(7.3)

Proof.

The verification that the expression (7.3) equals the expression (22) given in [11] is straightforward and is left to the reader.

Proposition 7.2.

L ₃ ^∗ , the sought-for minimal value of the cubic Lebesgue constant

$$L_{3}(x_{2}) =\max \limits _{\vert x\vert \leq 1}F_{3}(x,x_{2})\;\mbox{ with}\;F_{3}(x,x_{2}) =\displaystyle\sum \limits _{ i=0}^{3}\vert l_{ i,3}(x)\vert \;\mbox{ and}\;l_{i,3}(x) =\displaystyle\prod \limits _{ j=0,j\neq i}^{3} \dfrac{x - x_{j}} {x_{i} - x_{j}},$$

(7.4)

can likewise be identified with the unique real root of a cubic polynomial with integral coefficients:

$$Q_{3}(z) = -11 + 53z - 93{z}^{2} + 43{z}^{3}.$$

(7.5)

The analytic expression for L ₃ ^∗ as deduced in ([11](23)) can alternatively be restated as

$$\displaystyle\begin{array}{rcl} L_{3}^{{\ast}}& =& \dfrac{1} {129}\left (93 +{ \left (125172 + 11868\sqrt{69}\right )}^{\frac{1} {3} } +{ \left (125172 - 11868\sqrt{69}\right )}^{\frac{1} {3} }\right ) \\ & =& 1.4229195732\ldots \end{array}$$

(7.6)

Proof.

The verification that L ₃ ^∗ in its identical forms ([11], (23)) or (7.6) coincides with the real root of Q ₃ is by straightforward insertion and is left to the reader.

Proposition 7.3.

The square of the maximum point $x = \overline{x} \in [x_{2}^{{\ast}},1]$ , at which the first derivative of the optimal cubic Lebesgue function F ₃ (x,x ₂ ^∗ ) vanishes, can likewise be identified with the unique real root of a cubic polynomial with integral coefficients:

$$R_{3}(z) = -1 + 7z - 23{z}^{2} + 25{z}^{3}.$$

(7.7)

The analytic expression for $\overline{x}$ as given in ([11],(14)), after insertion of x ₂ = x ₂ ^∗ , reads as

$$\begin{array}{lcl} \overline{x}& =& \dfrac{1} {5\sqrt{3}}\sqrt{23 + 2{\left (\dfrac{623 + 75\sqrt{69} } {2} \right )}^{\frac{1} {3} } + 2{\left (\dfrac{623 - 75\sqrt{69}} {2} \right )}^{\frac{1} {3} }} \\ & \; & \\ & =&0.7331726239\ldots \end{array}$$

(7.8)

Proof.

The verification that the square of $\overline{x}$, where $\overline{x}$ is given by (7.8), coincides with the real root of R ₃ is again by straightforward insertion. □ 

By symmetry, the first derivative of F ₃(x, x ₂ ^∗) also vanishes at $-\overline{x} \in [-1,-x_{2}^{{\ast}}]$ and at $x = 0 \in [-x_{2}^{{\ast}},x_{2}^{{\ast}}]$ which gives the three equal local maxima $F_{3}(-\overline{x},x_{2}^{{\ast}}) = F_{3}(0,x_{2}^{{\ast}}) = F_{3}(\overline{x},x_{2}^{{\ast}})$ of the optimal cubic Lebesgue function (equioscillation property). These maxima are identical with the value $\min \limits _{0<x_{2}<1}L_{3}(x_{2}) = L_{3}(x_{2}^{{\ast}}) = L_{3}^{{\ast}}$.

The three polynomials P ₃, Q ₃, and R ₃, respectively their unique real roots, thus completely describe the solution to the problem of optimal cubic interpolation on [ − 1, 1].

7.3 Concluding Remarks

We point out that already in 1968 the polynomial P ₃ (in the variable z = t ²) has appeared as part of a posed problem in the not easily accessible source [14] (p. 89, Problem 6.43).

However, no analytic expressions for x ₂ ^∗ or L ₃ ^∗ or $\overline{x}$ are given there. At the time of writing [11] the source [14], which we had learned from [7], was not available to us.

We believe that the polynomials Q ₃ and R ₃ appear here for the first time in connection with optimal cubic polynomial interpolation and we hope that they may guide, together with P ₃, the finding of extensions to optimal n-th degree polynomial interpolation, n ≥ 4.

Additional recommended reading is [5, 9, 10] (especially Example 2.5.3), [12, 13].