Chapter 03

Hard

Polynomial Interpolation

00 · Symbol Glossary

$\mathcal{P}_n$P sub n — polynomial space

The vector space of polynomials of degree at most $n$ , including the zero polynomial. It is the function class in which an interpolant through $n+1$ nodes is sought. Read "P sub n."

$\ell_i(x)$ell sub i of x — Lagrange basis polynomial

The unique element of $\mathcal{P}_n$ that equals $1$ at the node $x_i$ and equals $0$ at every other node. The Lagrange form of the interpolant is the combination $\sum_i y_i\,\ell_i(x)$ .

$f[x_0,\ldots,x_k]$f bracket x-zero through x-k — divided difference

The coefficient of the degree- $k$ product in the Newton form, computed recursively from values by successive difference quotients. Read "f of the nodes x-zero through x-k." Symmetric in the nodes, and equal to $f^{(k)}(\xi)/k!$ for some $\xi$ when $f$ is smooth.

$\omega(x)$omega of x — nodal polynomial

The monic product $\prod_{i=0}^{n}(x-x_i)$ . It vanishes at every node, and it is the geometric factor in the interpolation error. Read "omega of x."

$\xi$xi — intermediate point

A point, depending on the evaluation site and on $f$ , that lies in the smallest interval containing that site and the nodes. The error formula evaluates $f^{(n+1)}$ there. Its exact location is unknown; bounds replace it by a maximum.

$\Lambda_n$Lambda sub n — Lebesgue constant

The maximum of $\sum_{i=0}^{n}\lvert\ell_i(x)\rvert$ on the interval of interest. It measures how much larger the interpolant can be, in the uniform norm, than a good comparison polynomial from the same $\mathcal{P}_n$ .

$T_m(x)$T sub m of x — Chebyshev polynomial

The degree- $m$ polynomial defined by $T_m(\cos\theta)=\cos(m\theta)$ , with leading coefficient $2^{m-1}$ for $m\ge 1$ . Its zeros are the Chebyshev nodes that keep $\omega$ as small as a monic polynomial of that degree can be.

01 · Existence and Uniqueness

A desk is handed pillar dates and values — discount factors at $1$ year and $2$ years, or a function sampled at laboratory nodes — and must pass a curve through every pillar. Before any formula, the question is which class of curves makes that demand determine exactly one function. The class in this chapter is $\mathcal{P}_n$ .

Definition — The interpolation problem

Let $x_0,\ldots,x_n$ be nodes and let $y_0,\ldots,y_n$ be corresponding values. A polynomial $p$ interpolates the data when

p(x_i)=y_i \qquad\text{for each } i=0,\ldots,n.

The nodes are distinct when $x_i\neq x_j$ for $i\neq j$ . Throughout this chapter, $n$ is the upper bound on the degree: $n+1$ conditions, polynomials drawn from $\mathcal{P}_n$ .

Plain language: the interpolant is the unique curve of degree at most $n$ through the dots. There are $n+1$ dots, sitting at distinct horizontal positions, and the curve that threads them is one polynomial from $\mathcal{P}_n$ . The degree may land strictly below $n$ when the dots happen to lie on a simpler polynomial; the class that makes the curve unique is still degree at most $n$ .

One algebraic fact carries uniqueness. If $r\in\mathcal{P}_n$ has $n+1$ distinct roots, then each root contributes a linear factor, so $r(x)=c\prod_{i=0}^{n}(x-x_i)$ would have degree $n+1$ unless the constant $c$ is $0$ . Hence $r$ is the zero polynomial.

Proof — Uniqueness for distinct nodes

Write a candidate as $p(x)=\sum_{k=0}^{n} a_k x^k$ . The interpolation conditions are the square linear system $V\mathbf{a}=\mathbf{y}$ with entries $V_{ik}=x_i^{k}$ , rows and columns indexed from $0$ . The coefficient matrix $V$ is the Vandermonde matrix of the nodes. If $p$ and $q$ both interpolate the same data, the coefficient vector of $p-q$ lies in the kernel of $V$ . That difference is an element of $\mathcal{P}_n$ with $n+1$ distinct roots, so it is the zero polynomial. The kernel is trivial, and there is at most one interpolant in $\mathcal{P}_n$ .

Existence is the explicit Lagrange polynomial in Section 02, which meets every value and therefore shows that $V\mathbf{a}=\mathbf{y}$ has a solution. Together the two halves say $V$ is invertible. Every later formula in the chapter returns that same polynomial: a second expression is a rearrangement of the one solution.

❌ Repeated nodes

Take $n=1$ , so the class is $\mathcal{P}_1$ , and set $x_0=x_1=0$ with values $y_0=1$ , $y_1=2$ .

What is attempted: a polynomial $p(x)=ax+b$ with $p(0)=1$ and $p(0)=2$ .

Where it breaks: the two conditions assign two different numbers to the same input. The root argument never starts, because there are not two distinct roots to give to $p-q$ . The Lagrange denominator $x_0-x_1$ in Section 02 is the same collision, written as division by zero.

Consequence: no function at all, polynomial or otherwise, interpolates contradictory values at one point. If instead $y_0=y_1$ , the two conditions collapse to one condition on a two-dimensional space, and infinitely many elements of $\mathcal{P}_1$ pass through that single point. Distinct nodes are the hypothesis that makes "exactly one" true.

Degree at most n

The interpolant lives in $\mathcal{P}_n$ , so its degree may come out strictly below $n$ . Three collinear samples have a unique interpolant in $\mathcal{P}_2$ , and that interpolant is a polynomial of degree $1$ . Dropping to a smaller degree is a successful interpolation. Demanding degree exactly $n$ is a different problem, and it need not have a solution.

02 · The Lagrange Form

Uniqueness says the interpolant is a single polynomial. Lagrange's formula names it by building, at each node, a polynomial that is $1$ there and $0$ at the others, then weighting those pieces by the prescribed values.

Definition — Lagrange basis and Lagrange form

For distinct nodes $x_0,\ldots,x_n$ and values $y_0,\ldots,y_n$ , the Lagrange basis polynomials and the Lagrange interpolant are

\ell_i(x)=\prod_{j\neq i}\frac{x-x_j}{x_i-x_j}, \qquad p(x)=\sum_{i=0}^{n} y_i\,\ell_i(x).

The product for $\ell_i$ runs over the $n$ indices $j\in\{0,\ldots,n\}$ with $j\neq i$ . Each denominator is a nonzero constant. The numerator is monic of degree $n$ after it is expanded, so $\ell_i\in\mathcal{P}_n$ and therefore $p\in\mathcal{P}_n$ .

Plain language: the Lagrange form is a blend of spikes that are $1$ at one node and $0$ at the others. Each spike $\ell_i$ belongs to node $x_i$ , the interpolant weights that spike by the height $y_i$ , and the weighted spikes are added. At a sample node every spike but one is $0$ , so the blend equals the height prescribed there; between the nodes the spikes overlap.

At a node $x_k$ with $k\neq i$ , the factor $x-x_k$ in the numerator of $\ell_i$ is zero, so $\ell_i(x_k)=0$ . At $x_i$ , every factor equals $1$ , so $\ell_i(x_i)=1$ . Hence $p(x_k)=\sum_i y_i\,\ell_i(x_k)=y_k$ . This polynomial is a solution of the Vandermonde system in Section 01, and the kernel argument there says it is the only one. The coefficients never require the matrix $V$ to be formed.

Step-by-step — Lagrange interpolant of $(0,1)$, $(1,2)$, $(2,4)$

Write the three basis polynomials. The denominators are $(0-1)(0-2)=2$ , $(1-0)(1-2)=-1$ , and $(2-0)(2-1)=2$ .

\ell_0(x)=\frac{(x-1)(x-2)}{2},\quad \ell_1(x)=-x(x-2),\quad \ell_2(x)=\frac{x(x-1)}{2}.

Weight by the values $1$ , $2$ , and $4$ and combine. The factor $4\cdot(1/2)$ on the third basis polynomial simplifies to $2$ before expansion:

p(x)=\frac{(x-1)(x-2)}{2}-2x(x-2)+2x(x-1).

Expand. $(x-1)(x-2)=x^2-3x+2$ , so the first term is $\tfrac12 x^2-\tfrac32 x+1$ . The second term is $-2x^2+4x$ . The third is $2x^2-2x$ . The $x^2$ coefficients are $\tfrac12-2+2=\tfrac12$ . The $x$ coefficients are $-\tfrac32+4-2=\tfrac12$ . The constant is $1$ .

p(x)=\frac12 x^2+\frac12 x+1.

Check the nodes. $p(0)=1$ . $p(1)=\tfrac12+\tfrac12+1=2$ . $p(2)=\tfrac12\cdot 4+\tfrac12\cdot 2+1=2+1+1=4$ . Each value is the prescribed $y_i$ . Section 01 then says this quadratic is the only element of $\mathcal{P}_2$ with that property.

✓ Example — The samples $1,2,4$ are not themselves a quadratic rule

The values $1,2,4$ at $0,1,2$ are $2^0,2^1,2^2$ . The interpolant $\tfrac12 x^2+\tfrac12 x+1$ agrees with $2^x$ at those three nodes and nowhere else is required to. At $x=3$ , the polynomial returns $\tfrac12\cdot 9+\tfrac12\cdot 3+1=\tfrac{9}{2}+\tfrac{3}{2}+1=7$ , while $2^3=8$ . The gap of $1$ is legal: interpolation fixes values at the nodes and is silent between them until the error formula of Section 04.

❌ Forcing degree exactly n

The data $(0,0)$ , $(1,1)$ , $(2,2)$ ask for an element of $\mathcal{P}_2$ .

What is attempted: a quadratic $ax^2+bx+c$ with $a\neq 0$ required in advance, on the grounds that three points "determine a parabola."

Where it breaks: $p(x)=x$ already lies in $\mathcal{P}_2$ and meets all three values. Uniqueness forbids a second interpolant, so there is no solution with $a\neq 0$ . The Lagrange sum produces $p(x)=x$ ; the $x^2$ coefficients cancel.

Consequence: "degree at most $n$ " is the class in the theorem. "Degree exactly $n$ " can be empty for the same data.

03 · The Newton Form

Lagrange's basis depends on every node at once. Adding a pillar changes every $\ell_i$ . Newton's form is the same polynomial written so that the old coefficients stay put and the new node appends one term.

Definition — Divided differences and the Newton form

Set $f[x_i]=y_i$ . For $k\ge 1$ and any window of $k+1$ distinct nodes,

f[x_i,\ldots,x_{i+k}]=\frac{f[x_{i+1},\ldots,x_{i+k}]-f[x_i,\ldots,x_{i+k-1}]}{x_{i+k}-x_i}.

The Newton form of the interpolant is

p(x)=a_0+\sum_{k=1}^{n} a_k\prod_{j=0}^{k-1}(x-x_j), \qquad a_k=f[x_0,\ldots,x_k].

The $k=0$ term is the constant $a_0=y_0$ . The sum in the display starts at $k=1$ , where the product first has a factor.

Plain language: a divided difference is the coefficient that records how much new bending the next dot demands. Newton's form writes the same interpolant as a constant plus terms that each vanish at the nodes already accounted for, so a newly arrived pillar appends one product and the earlier coefficients stay put. The polynomial is the one from Section 02; this arrangement is the one that updates when another date arrives.

The product that multiplies $a_k$ vanishes at $x_0,\ldots,x_{k-1}$ . Consequently the partial sum that stops at $a_m$ already interpolates the first $m+1$ data points, and later terms do not disturb those values. Evaluating at $x_m$ solves for $a_m$ and recovers the divided-difference recurrence. By Section 01 this $p$ equals the Lagrange interpolant: same nodes, same values, same space.

The leading term of the degree- $k$ product is $a_k x^k$ . So $a_k=f[x_0,\ldots,x_k]$ is the leading coefficient of the unique interpolant through those $k+1$ points. Leading coefficients do not depend on the order in which points were fed to the recurrence. Divided differences are therefore symmetric in their arguments: $f[x_0,x_1]=f[x_1,x_0]$ , and likewise for longer brackets.

Step-by-step — Newton form of the same data $(0,1)$, $(1,2)$, $(2,4)$

Fill the value column. $f[0]=1$ , $f[1]=2$ , $f[2]=4$ .

Compute first differences. $f[0,1]=(2-1)/(1-0)=1$ . $f[1,2]=(4-2)/(2-1)=2$ . Each numerator is a difference of values; each denominator is the corresponding node gap.

Compute the second difference. The numerator is the difference of the two first differences just obtained, and the denominator is the span from the first node in the bracket to the last:

f[0,1,2]=\frac{2-1}{2-0}=\frac12.

Assemble and expand. $p(x)=1+1\cdot(x-0)+\tfrac12(x-0)(x-1)=1+x+\tfrac12 x^2-\tfrac12 x$ .

p(x)=\frac12 x^2+\frac12 x+1.

This is the polynomial Section 02 produced with Lagrange. The agreement is the uniqueness theorem, checked by hand.

✓ Example — A three-pillar discount factor

Discount factors $1$ , $\tfrac{97}{100}$ , $\tfrac{93}{100}$ at maturities $0$ , $1$ , $2$ determine an element of $\mathcal{P}_2$ .

The first differences are $(\tfrac{97}{100}-1)/(1-0)=-\tfrac{3}{100}$ and $(\tfrac{93}{100}-\tfrac{97}{100})/(2-1)=-\tfrac{4}{100}$ . The second difference uses the gap $2-0=2$ :

f[0,1,2]=\frac{-\tfrac{4}{100}-\left(-\tfrac{3}{100}\right)}{2}=\frac{-\tfrac{1}{100}}{2}=-\frac{1}{200}.

p(t)=1-\frac{3}{100}\,t-\frac{1}{200}\,t(t-1).

At $t=\tfrac32$ , which sits between the pillars, $t(t-1)=\tfrac32\cdot\tfrac12=\tfrac34$ , so the last term is $-\tfrac{1}{200}\cdot\tfrac34=-\tfrac{3}{800}$ . The linear term is $-\tfrac{3}{100}\cdot\tfrac32=-\tfrac{9}{200}=-\tfrac{36}{800}$ . Hence $p(\tfrac32)=1-\tfrac{36}{800}-\tfrac{3}{800}=\tfrac{761}{800}$ . The curve value $0.95125$ lies between the neighboring pillar values $\tfrac{97}{100}$ and $\tfrac{93}{100}$ . Differentiating the expanded form $p(t)=1-\tfrac{1}{40}t-\tfrac{1}{200}t^2$ gives $p'(t)=-\tfrac{1}{40}-\tfrac{1}{100}t=-(2t+5)/200$ , which is negative for every $t\ge 0$ . On the hull of these three pillars the interpolant is still a decreasing discount factor.

❌ Extrapolating a pillar polynomial past the last node

The same quadratic, evaluated at maturity $20$ .

What is attempted: $p(20)=1-\tfrac{3}{100}\cdot 20-\tfrac{1}{200}\cdot 20\cdot 19=1-\tfrac{3}{5}-\tfrac{19}{10}$ .

Where it breaks: $\tfrac{3}{5}+\tfrac{19}{10}=\tfrac{6}{10}+\tfrac{19}{10}=\tfrac{25}{10}=\tfrac52$ , so $p(20)=1-\tfrac52=-\tfrac32$ . Nothing in the interpolation conditions speaks about $t=20$ . The nodal factor $\omega(20)=20\cdot 19\cdot 18=6840$ is the size Section 04 multiplies into the unknown second derivative; three pillars on $[0,2]$ do not bound that derivative out at $20$ .

Consequence: $-\tfrac32$ is the polynomial's value, and it is not a discount factor. The identity $p(t_i)=y_i$ holds at $0,1,2$ . Outside the hull of the nodes the formula is an extrapolation, and the error factor $\omega$ grows like the product of the distances to every pillar.

04 · The Error Formula

Matching $n+1$ values leaves a definite gap at every other $x$ . The gap factors into a derivative of $f$ , which the nodes do not control, and the nodal polynomial $\omega$ , which they do.

Definition — Interpolation error

Let $x_0,\ldots,x_n$ be distinct nodes in an interval, and let $f$ have a continuous derivative of order $n+1$ on an open interval containing the nodes and the evaluation point $x$ . Let $p\in\mathcal{P}_n$ interpolate $f$ at the nodes, and write $\omega(x)=\prod_{i=0}^{n}(x-x_i)$ . Then there exists a point $\xi$ , strictly inside the smallest interval that contains $x$ and all the nodes, such that

f(x)-p(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\,\omega(x).

If $x$ itself is a node, both sides are $0$ . If $\lvert f^{(n+1)}\rvert\le M$ on the interval that contains $\xi$ , then

\lvert f(x)-p(x)\rvert\le\frac{M}{(n+1)!}\,\lvert\omega(x)\rvert.

Plain language: the error formula is the Taylor remainder, with the sample nodes in place of one expansion point. The degree- $n$ Taylor gap at a single center carries $f^{(n+1)}$ and a factorial $(n+1)!$ , times a pure power of the distance to that center. The same derivative and the same factorial appear here, and the pure power is replaced by $\omega(x)$ , the product of the distances from the evaluation site to each sample node.

The Newton form supplies the same gap with a divided difference in place of the derivative. Extend the node list by the evaluation point $x$ , using the value $f(x)$ . The enlarged Newton polynomial interpolates the original data, because the added term contains the product $\omega$ , and it interpolates $(x,f(x))$ by construction of the last coefficient. Evaluating there yields the identity

f(x)-p(x)=f[x_0,\ldots,x_n,x]\,\omega(x).

The next proof identifies the divided difference with $f^{(n+1)}(\xi)/(n+1)!$ . In particular, for any distinct $z_0,\ldots,z_m$ in the interval of smoothness,

f[z_0,\ldots,z_m]=\frac{f^{(m)}(\xi)}{m!}

for some $\xi$ in the interval they span: apply the error formula to the first $m$ points and read the last Newton coefficient at $z_m$ . When $f^{(n+1)}$ vanishes identically, $f\in\mathcal{P}_n$ , every divided difference of order $n+1$ vanishes, and $p=f$ .

Proof — The derivative form of the error

If $x$ equals some node, both sides of the claimed formula are zero. Now fix $x$ distinct from every $x_i$ , and define

\lambda=\frac{f(x)-p(x)}{\omega(x)}, \qquad g(t)=f(t)-p(t)-\lambda\,\omega(t).

Then $g(x_i)=y_i-y_i-\lambda\cdot 0=0$ , and $g(x)=0$ by the choice of $\lambda$ . So $g$ has at least $n+2$ distinct zeros.

Rolle's theorem: a function that is continuous on a closed interval, differentiable on the interior, and equal at the two endpoints has derivative equal to zero at some point strictly between them. Apply it once on each interval between consecutive zeros of $g$ . The derivative $g'$ has at least $n+1$ distinct zeros. Repeat. After $n+1$ applications, $g^{(n+1)}$ has at least one zero; call it $\xi$ . The point $\xi$ lies in the open interval spanned by $x$ and the nodes.

The derivative of order $n+1$ kills $p$ , since $\deg p\le n$ . The nodal polynomial is monic of degree $n+1$ , so $\omega^{(n+1)}(t)=(n+1)!$ . Therefore

g^{(n+1)}(\xi)=f^{(n+1)}(\xi)-\lambda\,(n+1)!=0.

Solve for $\lambda$ and substitute the definition of $\lambda$ . The error formula follows.

Sibling of the Taylor remainder

Calculus Chapter 11 writes the gap between $f$ and its degree- $n$ Taylor polynomial at a single center $a$ as $f^{(n+1)}(c)\,(x-a)^{n+1}/(n+1)!$ . The derivative order and the factorial match the formula above. The geometric factor $(x-a)^{n+1}$ is what $\omega(x)$ becomes when every interpolation condition has coalesced at the single point $a$ . The nodes in this chapter stay distinct. The two remainders share an engine and differ in the polynomial that multiplies $f^{(n+1)}(\xi)/(n+1)!$ .

Step-by-step — Bound the gap for $e^x$ at $x=\tfrac12$, nodes $0$ and $1$

Name the interpolant. Here $n=1$ , $f(0)=1$ , $f(1)=e$ . The unique element of $\mathcal{P}_1$ through those points is the chord $p(x)=1+(e-1)x$ . At the test point, $p(\tfrac12)=(1+e)/2$ .

Evaluate $\omega$ . $\omega(x)=x(x-1)$ , so $\omega(\tfrac12)=\tfrac12\cdot(-\tfrac12)=-\tfrac14$ and $\lvert\omega(\tfrac12)\rvert=\tfrac14$ . The factor $(n+1)!$ is $2!=2$ .

Bound the derivative on the whole interval that may contain $\xi$ . The nodes and the test point all lie in $[0,1]$ , and $f''(t)=e^t$ is increasing, so $1\le e^t\le e$ on that interval. The legal ceiling is $M=e$ , attained as the value at the right endpoint, not as a value we may choose.

Apply the bound. $\lvert f(\tfrac12)-p(\tfrac12)\rvert\le (e/2)\cdot(1/4)=e/8$ . The unknown $\xi$ has been removed. The bound does not require a numerical value of $e^{1/2}$ .

❌ Bounding the derivative only at a convenient point

On the same data, replace $M=e$ by $f''(0)=e^0=1$ , then quote the number $(1/2)\cdot(1/4)=1/8$ as an error bound.

Where it breaks: the theorem requires $\lvert f^{(n+1)}(t)\rvert\le M$ at every $t$ in the interval that contains $\xi$ , and $\xi$ is only known to lie somewhere in $(0,1)$ . On that interval $e^t>1$ for every $t>0$ , so $M=1$ fails at the point the formula actually uses.

Consequence: $1/8$ is smaller than the expression the theorem permits. It is not a bound. The legal ceiling on $[0,1]$ is $e$ , and the legal numerical bound is $e/8$ .

Two later chapters quote this display directly. Chapter 04 cuts the domain into subintervals and applies the formula on each piece, with a local degree and a local $\omega$ whose size is a power of the local spacing. Chapter 06 integrates it. A Newton–Cotes rule is $\int p$ , and the quadrature error is

\int_a^b\frac{f^{(n+1)}(\xi_x)}{(n+1)!}\,\omega(x)\,dx,

with $\xi_x$ depending on the dummy variable of integration. The derivative factor and the nodal polynomial are the ones proved here; Chapter 06 evaluates the integral of that product for equispaced quadrature nodes.

05 · The Runge Phenomenon

The bound in Section 04 shrinks when $M/(n+1)!$ shrinks faster than $\lvert\omega\rvert$ grows. Raising $n$ changes both factors, and it changes $\omega$ through the placement of the nodes. Equispaced nodes, the default when a table is printed at a constant step, make $\lvert\omega\rvert$ worst near the ends of the interval.

Definition — Lebesgue function and Lebesgue constant

On an interval $I$ containing the nodes, the Lebesgue function and the Lebesgue constant of those nodes are

\lambda(x)=\sum_{i=0}^{n}\lvert\ell_i(x)\rvert, \qquad \Lambda_n=\max_{x\in I}\lambda(x).

For every comparison polynomial $q\in\mathcal{P}_n$ and every continuous $f$ , if $p$ interpolates $f$ at the nodes, then

\|f-p\|_\infty\le(1+\Lambda_n)\,\|f-q\|_\infty,

where $\|\,\cdot\,\|_\infty$ is the maximum of the absolute value on $I$ .

Plain language: the Lebesgue function adds the absolute values of the Lagrange spikes at a point, and the Lebesgue constant $\Lambda_n$ is the largest value that sum attains on the interval. It is the inflation allowed against any other polynomial from the same $\mathcal{P}_n$ : on the whole interval, the interpolant's uniform error is at most $1+\Lambda_n$ times the uniform error of that comparison. A large constant means the spikes, measured in absolute value, can pile up and swing the curve well beyond the size of the samples.

The comparison is arbitrary, so it applies in particular to any $q$ that approximates $f$ well. The interpolant is then at most a factor $1+\Lambda_n$ worse than that comparison. The short proof is linearity. The interpolant of $q$ is $q$ itself, by uniqueness. Hence $p-q$ interpolates the sampled values of $f-q$ , and

p(x)-q(x)=\sum_{i=0}^{n}\bigl(f(x_i)-q(x_i)\bigr)\,\ell_i(x).

Each $\lvert f(x_i)-q(x_i)\rvert$ is at most $\|f-q\|_\infty$ , so $\lvert p(x)-q(x)\rvert\le\|f-q\|_\infty\,\lambda(x)\le\Lambda_n\|f-q\|_\infty$ . The triangle inequality $\|f-p\|_\infty\le\|f-q\|_\infty+\|p-q\|_\infty$ produces the factor $1+\Lambda_n$ .

For equispaced nodes the constant is hostile. As the degree $n$ tends to infinity,

\Lambda_n\sim\frac{2^{n+1}}{\mathrm{e}\, n\ln n},

with $\ln$ the natural logarithm and $\mathrm{e}$ its base. The right-hand side grows exponentially. A family of comparison polynomials $q_n$ may converge to $f$ rapidly while $(1+\Lambda_n)\|f-q_n\|_\infty$ still diverges. The equispaced element of $\mathcal{P}_n$ is the source of that divergence.

Definition — Runge's example

Let $f(x)=1/(1+25x^2)$ on $[-1,1]$ , and let $p_n\in\mathcal{P}_n$ interpolate $f$ at the $n+1$ equispaced nodes $x_i=-1+2i/n$ for $i=0,\ldots,n$ , with $n\ge 1$ . Then $\|f-p_n\|_\infty$ is unbounded as $n\to\infty$ . The blow-up concentrates near the endpoints $\pm 1$ . This is Runge's classical example: a function with derivatives of every order whose equispaced interpolants diverge uniformly.

Plain language: Runge's example is the high-degree wiggle at the ends on equal spacing. The function $1/(1+25x^2)$ is smooth and stays positive and at most $1$ , and the nodes are spaced evenly across $[-1,1]$ . Raising the degree rebuilds an equispaced interpolant whose oscillations near $\pm 1$ grow, and the largest gap on the interval is unbounded as the degree tends to infinity. Further equally spaced dots leave that end wiggle in place.

The poles of $f$ sit at $x=\pm i/5$ , because $1+25x^2=0$ forces $x^2=-1/25$ . They lie at a fixed complex distance $1/5$ from the origin, so high derivatives of $f$ on $[-1,1]$ are large. The error formula multiplies that derivative factor by $\omega(x)/(n+1)!$ . Equispaced nodes make $\lvert\omega\rvert$ much larger near $\pm 1$ than near the middle, and for this $f$ the product does not tend to $0$ uniformly. The full divergence proof uses that complex-analytic setup; the hand calculation below already shows the endpoint disease at degree $4$ , where every arithmetic step is rational.

Step-by-step — Equispaced interpolant of $1/(1+25x^2)$ at degree $4$

Record the samples. Nodes $-1,-\tfrac12,0,\tfrac12,1$ . The function is even, and $f(0)=1$ , $f(1)=1/26$ , $f(\tfrac12)=1/(1+25\cdot\tfrac14)=1/(29/4)=4/29$ . The same values recur at the negative nodes.

Use symmetry and uniqueness. If $p$ interpolates these data, so does $t\mapsto p(-t)$ , because the data are even. Section 01 forces $p(-t)=p(t)$ . A general even element of $\mathcal{P}_4$ is $p(x)=a+bx^2+cx^4$ .

Read the three coefficients off three nodes. $p(0)=1$ gives $a=1$ . Then $b+c=1/26-1=-25/26$ , and $b/4+c/16=4/29-1=-25/29$ .

Clear the second equation. Multiply $b/4+c/16=-25/29$ by $16$ : $4b+c=-400/29$ , where $-400=16\cdot(-25)$ . Subtract $b+c=-25/26$ :

3b=-\frac{400}{29}+\frac{25}{26}=\frac{-10400+725}{754}=-\frac{9675}{754},

using the common denominator

29\cdot 26=754

. Hence

b=-9675/(3\cdot 754)=-3225/754

. Then

c=-25/26-b=-725/754+3225/754=2500/754=1250/377

Evaluate at $x=4/5$ , between the nodes $1/2$ and $1$ . Here $(4/5)^2=16/25$ and $(4/5)^4=256/625$ . The quadratic contribution is $(-3225/754)\cdot(16/25)=-1032/377$ , after cancelling $3225/25=129$ and dividing $-129\cdot 16$ and $754$ by $2$ . The degree- $4$ contribution, using $1250/377=2500/754$ and $2500/625=4$ , is $4\cdot 256/754=1024/754=512/377$ .

Add. $p(4/5)=1-1032/377+512/377=1-520/377=(377-520)/377=-143/377$ . Since $377=13\cdot 29$ and $143=11\cdot 13$ ,

p\!\left(\frac45\right)=-\frac{11}{29}.

Meanwhile

f(4/5)=1/(1+25\cdot 16/25)=1/(1+16)=1/17>0

. The interpolant at a point inside

[-1,1]

is already negative, while

f

on the whole real line takes values in

(0,1]

❌ Treating a finer equispaced table as a safer uniform approximation

Degree $4$ on this $f$ has already produced $p(4/5)=-11/29$ , about $-0.379$ , against $f(4/5)=1/17$ , about $0.059$ .

What is attempted: the inference that moving to degree $6$ , $8$ , or $10$ with the same equispaced pattern must reduce the uniform error, because more interpolation conditions are being enforced.

Where it breaks: each new degree rebuilds $\omega$ and replaces $f^{(n+1)}$ . Runge's theorem says the uniform norm of the error on $[-1,1]$ is unbounded along this sequence. The Lebesgue constant of the equispaced nodes grows like $2^{n+1}/(e\, n\ln n)$ , so the inequality of this section allows the interpolant to depart from a good comparison polynomial by an exponential factor. Matching more equispaced samples does not purchase a smaller $\Lambda_n$ .

Consequence: pointwise agreement at more and more equispaced nodes coexists with a uniform error that refuses to tend to $0$ . The sign error $-11/29$ is the same phenomenon, visible before the asymptotic regime.

06 · Chebyshev Nodes

The error formula isolates one factor the node-setter controls: the size of the monic polynomial $\omega$ . Among all choices of $n+1$ distinct nodes in $[-1,1]$ , the smallest possible value of $\max\lvert\omega\rvert$ is attained by clustering nodes toward the endpoints. Those nodes are the zeros of a Chebyshev polynomial.

Definition — Chebyshev polynomials and Chebyshev nodes

The Chebyshev polynomials are $T_0(x)=1$ , $T_1(x)=x$ , and

T_{m}(x)=2x\,T_{m-1}(x)-T_{m-2}(x) \qquad (m\ge 2).

They satisfy $T_m(\cos\theta)=\cos(m\theta)$ . The Chebyshev nodes for interpolation in $\mathcal{P}_n$ are the $n+1$ zeros of $T_{n+1}$ ,

x_k=\cos\!\left(\frac{(2k+1)\pi}{2(n+1)}\right), \qquad k=0,\ldots,n.

Plain language: Chebyshev nodes are denser samples near the ends, placed there to tame that wiggle. They are the zeros of $T_{n+1}$ , and the cosine relation puts them on equal steps of angle, which crowd toward $x=\pm 1$ and leave wider gaps near the middle. The resulting monic nodal polynomial $\omega$ has the smallest possible maximum on $[-1,1]$ among monic polynomials of degree $n+1$ , so the geometric factor in the error formula is as small as the node placement can make it.

The cosine identity follows from the recurrence. It holds for $m=0$ and $m=1$ . The addition formula $\cos((m+1)\theta)+\cos((m-1)\theta)=2\cos\theta\cos(m\theta)$ is the same three-term relation the polynomials obey, so the two sequences agree for every $m$ . In particular $\lvert T_m(x)\rvert\le 1$ for every $x\in[-1,1]$ , since it equals $\lvert\cos(m\theta)\rvert$ at $x=\cos\theta$ .

The zeros are the angles where $\cos((n+1)\theta)=0$ , that is $(n+1)\theta=(2k+1)\pi/2$ , so $\theta=(2k+1)\pi/(2n+2)$ , and $k=0,\ldots,n$ produces $n+1$ distinct cosines in $(-1,1)$ .

The leading coefficient of $T_m$ is $2^{m-1}$ for $m\ge 1$ : true for $T_1$ , and the recurrence multiplies the leading term by $2x$ while the subtracted polynomial $T_{m-2}$ has lower degree. Thus $T_{n+1}$ has leading coefficient $2^n$ , and $2^{-n}T_{n+1}$ is monic of degree $n+1$ . Its roots are the Chebyshev nodes, so it is their nodal polynomial:

\omega(x)=2^{-n}T_{n+1}(x), \qquad \max_{[-1,1]}\lvert\omega(x)\rvert=2^{-n}.

The maximum is $2^{-n}$ because $\lvert T_{n+1}\rvert\le 1$ and $T_{n+1}$ attains $\pm 1$ .

Clustering is the cosine map, read off the derivative. Equal steps in the angle $\theta$ produce horizontal steps $\Delta x\approx -\sin\theta\,\Delta\theta$ , and $\sin\theta=\sqrt{1-x^2}$ when $x=\cos\theta$ . The gaps are therefore proportional to $\sqrt{1-x^2}$ : large near $x=0$ , where the sine is near $1$ , and small near $x=\pm 1$ , where the sine vanishes. The nodes crowd the endpoints.

Proof — No monic polynomial is smaller on the interval

Let $q$ be monic of degree $m=n+1$ , and write $\delta=2^{1-m}=2^{-n}$ . Suppose, for a contradiction, that $\lvert q(x)\rvert<\delta$ at every $x\in[-1,1]$ . Let $\hat T=2^{-n}T_{n+1}$ , which is monic, and set $r=\hat T-q$ . The degree- $m$ terms cancel, so $\deg r\le m-1$ .

At the $m+1$ points $t_j=\cos(j\pi/m)$ for $j=0,\ldots,m$ , the identity $T_m(\cos\phi)=\cos(m\phi)$ with $m$ replaced by $n+1$ gives $T_{n+1}(t_j)=\cos(j\pi)=(-1)^j$ . Hence $\hat T(t_j)=(-1)^j\delta$ . Because $\lvert q(t_j)\rvert<\delta$ , the difference $r(t_j)$ is nonzero and has the sign of $(-1)^j$ . Along the ordered points $t_0>t_1>\cdots>t_m$ , the values of $r$ therefore change sign on each of the $m$ consecutive gaps. A continuous function with a sign change on an interval has a root in that interval, so $r$ has at least $m$ distinct roots. A nonzero polynomial of degree at most $m-1$ has at most $m-1$ roots. This contradiction forces the supposition to fail.

Every monic polynomial of degree $n+1$ therefore satisfies $\max_{[-1,1]}\lvert q\rvert\ge 2^{-n}$ . The Chebyshev choice attains $2^{-n}$ , so it is optimal for the uniform size of $\omega$ .

✓ Example — Degree $1$ on $[-1,1]$, Chebyshev against the endpoints

For $n=1$ the relevant polynomial is $T_2(x)=2x^2-1$ , with zeros $x=\pm\sqrt{2}/2$ . The monic nodal polynomial is $\omega_C(x)=x^2-\tfrac12=2^{-1}T_2(x)$ . On $[-1,1]$ its absolute value is at most $\tfrac12$ , and it equals $\tfrac12$ at $x=-1$ , $x=0$ , and $x=1$ , with signs $+,-,+$ .

The equispaced choice for two nodes is the pair of endpoints, with $\omega_E(x)=(x+1)(x-1)=x^2-1$ . Then $\lvert\omega_E(0)\rvert=1$ , which is twice $2^{-1}$ . The derivative factor $f''(\xi)/2!$ in the error formula is unchanged by this comparison; the entire improvement available from moving the nodes is the drop in $\lvert\omega\rvert$ , here from $1$ down to $\tfrac12$ at the midpoint.

When the nodes are not yours to move

Chebyshev nodes minimize $\max\lvert\omega\rvert$ on $[-1,1]$ among monic polynomials of degree $n+1$ . That minimization is available when the nodes are a choice, as they are for a quadrature rule in Chapter 06. Pillar dates on a discount curve are market data, not free parameters. Moving them to $\cos((2k+1)\pi/(2n+2))$ is not a trade one can book. Chapter 04 answers that constraint by abandoning a single global element of $\mathcal{P}_n$ : the same error formula is applied on each subinterval, where the local nodal polynomial is a power of the local spacing and the degree stays fixed while the mesh is refined.

For orientation, the Lebesgue constant of the Chebyshev nodes grows only logarithmically, $\Lambda_n\sim(2/\pi)\ln(n+1)$ . A comparison error that decays geometrically dominates a logarithm, so the node choice that minimizes $\max\lvert\omega\rvert$ keeps $1+\Lambda_n$ from swallowing the approximation. Applied to Runge's function, the Chebyshev interpolants converge to $f$ uniformly at a geometric rate in $n$ . That rate is the counterpart of the divergence theorem in Section 05; its proof tracks a Bernstein ellipse out to the poles at $\pm i/5$ , and it is recorded here as a classical fact. The equispaced asymptotic of Section 05 grows exponentially. Both Lebesgue asymptotics are classical. The inequality they plug into was proved from the Lagrange basis above.

07 · Practice Exercises

EXERCISE 3.1

Write the three Lagrange basis polynomials for the nodes $-1$ , $0$ , and $2$ before multiplying by the values. Each denominator is a product of two nonzero node gaps.

The basis polynomials are $\ell_0(x)=x(x-2)/3$ , because the denominator is $(-1-0)(-1-2)=3$ ; $\ell_1(x)=-(x+1)(x-2)/2$ , because the denominator is $(0+1)(0-2)=-2$ ; and $\ell_2(x)=x(x+1)/6$ , because the denominator is $(2+1)(2-0)=6$ .

Weight by $2$ , $-1$ , and $1$ . Then $2\ell_0=(2/3)x^2-(4/3)x$ . The middle contribution is $(-1)\cdot\ell_1=(1/2)(x+1)(x-2)=(1/2)x^2-(1/2)x-1$ . The last is $(1/6)x^2+(1/6)x$ .

The $x^2$ coefficients add as $2/3+1/2+1/6=4/6+3/6+1/6=8/6=4/3$ . The $x$ coefficients add as $-4/3-1/2+1/6=-8/6-3/6+1/6=-10/6=-5/3$ . The constant term is $-1$ . Therefore $p(x)=\tfrac43 x^2-\tfrac53 x-1$ .

Checks: $p(-1)=4/3+5/3-1=3-1=2$ , $p(0)=-1$ , and $p(2)=(4/3)\cdot 4-(5/3)\cdot 2-1=16/3-10/3-1=2-1=1$ .

The Newton route returns the same polynomial, as Section 01 requires. The divided differences are $f[-1,0]=(-1-2)/(0-(-1))=-3$ and $f[0,2]=(1-(-1))/(2-0)=1$ , so $f[-1,0,2]=(1-(-3))/(2-(-1))=4/3$ . Then $p(x)=2-3(x+1)+(4/3)x(x+1)=(4/3)x^2+(-3+4/3)x+(2-3)=(4/3)x^2-(5/3)x-1$ .

The nodes $-1$ , $0$ , $2$ carry the values $2$ , $-1$ , $1$ . Build the Lagrange interpolant in $\mathcal{P}_2$ , expand it into $ax^2+bx+c$ , and check all three nodes.

EXERCISE 3.2

The Newton coefficient of order $3$ is a difference of two second differences, divided by the span from the first node to the last. A quadratic that already passes through the four points must be the interpolant in $\mathcal{P}_3$ .

The value column is $f[0]=1$ , $f[1]=4$ , $f[2]=9$ , $f[3]=16$ .

First differences, each over a gap of $1$ : $f[0,1]=3$ , $f[1,2]=5$ , $f[2,3]=7$ .

Second differences, each over a span of $2$ : $f[0,1,2]=(5-3)/2=1$ and $f[1,2,3]=(7-5)/2=1$ .

Third difference: $f[0,1,2,3]=(1-1)/(3-0)=0$ .

The Newton form is $p(x)=1+3x+1\cdot x(x-1)+0=1+3x+x^2-x=x^2+2x+1=(x+1)^2$ .

The polynomial $(x+1)^2$ lies in $\mathcal{P}_3$ and matches all four values, since its samples are $1,4,9,16$ . By uniqueness it is the interpolant, so the degree- $3$ coefficient is $0$ for any ordering of these nodes. Equivalently, Section 04 says every third divided difference of a polynomial of degree $2$ vanishes, because the third derivative is identically $0$ .

The nodes $0,1,2,3$ carry the values $1,4,9,16$ . Compute the divided-difference table through order $3$ , write the Newton form, and explain why the coefficient of the cubic product is $0$ .

EXERCISE 3.3

The interpolant in $\mathcal{P}_1$ is the chord between $(0,0)$ and $(\pi/2, 1)$ . On $[0,\pi/2]$ the second derivative of $\sin x$ is $-\sin x$ , whose absolute value is at most $1$ . The point $\xi$ lies in the open interval spanned by the nodes and the test point.

Here $n=1$ , $f(x)=\sin x$ , $f(0)=0$ , $f(\pi/2)=1$ . The chord is $p(x)=(2/\pi)\,x$ , because the slope is $1/(\pi/2)=2/\pi$ . At the test point, $p(\pi/4)=(2/\pi)\cdot(\pi/4)=1/2$ .

The nodal polynomial is $\omega(x)=x(x-\pi/2)$ , so $\omega(\pi/4)=(\pi/4)(\pi/4-\pi/2)=(\pi/4)(-\pi/4)=-\pi^2/16$ and $\lvert\omega(\pi/4)\rvert=\pi^2/16$ . Also $(n+1)! = 2$ , and $\lvert f''(t)\rvert=\lvert-\sin t\rvert\le 1$ for every real $t$ , in particular on $[0,\pi/2]$ , which contains every candidate $\xi$ . Section 04 gives

\left\lvert\sin\frac{\pi}{4}-p\!\left(\frac{\pi}{4}\right)\right\rvert\le\frac{1}{2}\cdot\frac{\pi^2}{16}=\frac{\pi^2}{32}.

The point $\xi$ lies in $(0,\pi/2)$ .

The exact gap is available for a check and is not required to use the bound: $\sin(\pi/4)=\sqrt{2}/2$ , so the absolute error is $(\sqrt{2}-1)/2$ . It sits under the bound by elementary comparisons. $\sqrt{2}<3/2$ because $(3/2)^2=9/4>2$ , hence $(\sqrt{2}-1)/2<(1/2)/2=1/4$ . And $\pi>3$ gives $\pi^2/32>9/32>8/32=1/4$ . Therefore $(\sqrt{2}-1)/2<\pi^2/32$ .

Let $f(x)=\sin x$ , with nodes $0$ and $\pi/2$ . Write the interpolant in $\mathcal{P}_1$ , and bound $\lvert f(\pi/4)-p(\pi/4)\rvert$ by the formula in Section 04. State an interval that contains $\xi$ .

EXERCISE 3.4

For interpolation in $\mathcal{P}_2$ the nodal polynomial has degree $3$ , so the Chebyshev polynomial in the formula is $T_3$ . Its monic multiple is $T_3/4$ . For the equispaced nodes $-1,0,1$ , differentiate $x^3-x$ to locate the maximum of the absolute value on $[-1,1]$ .

The recurrence gives $T_2(x)=2x^2-1$ and $T_3(x)=2x(2x^2-1)-x=4x^3-3x$ . The zeros solve $x(4x^2-3)=0$ , so the Chebyshev nodes are $x=0$ and $x=\pm\sqrt{3}/2$ . The leading coefficient of $T_3$ is $4=2^2$ , and the monic nodal polynomial is $\omega_C(x)=2^{-2}T_3(x)=x^3-(3/4)x$ . Section 06 gives $\max_{[-1,1]}\lvert\omega_C\rvert=2^{-2}=1/4$ . The same number is visible at the critical points: $\omega_C'(x)=3x^2-3/4$ vanishes at $x=\pm 1/2$ , and $\omega_C(1/2)=(1/2)(1/4-3/4)=-1/4$ , while $\omega_C(\pm 1)=\pm(1-3/4)=\pm 1/4$ .

For nodes $-1,0,1$ , $\omega_E(x)=x(x-1)(x+1)=x^3-x$ . The derivative $3x^2-1$ vanishes at $x=\pm 1/\sqrt{3}$ . Then $\omega_E(1/\sqrt{3})=(1/\sqrt{3})^3-1/\sqrt{3}=1/(3\sqrt{3})-3/(3\sqrt{3})=-2/(3\sqrt{3})=-2\sqrt{3}/9$ after multiplying numerator and denominator by $\sqrt{3}$ . The value at $-1/\sqrt{3}$ is the negative of this, because $\omega_E$ is odd, and both endpoints give $\omega_E(\pm 1)=0$ . The maximum of $\lvert\omega_E\rvert$ on $[-1,1]$ is therefore $2\sqrt{3}/9$ .

Compare the squares, both positive: $(2\sqrt{3}/9)^2=12/81=4/27$ and $(1/4)^2=1/16$ . Cross-multiplication gives $4\cdot 16=64>27=27\cdot 1$ , so $4/27>1/16$ , hence $2\sqrt{3}/9>1/4$ . The equispaced nodal polynomial is larger in uniform norm by the factor $(2\sqrt{3}/9)/(1/4)=8\sqrt{3}/9$ . In the error formula the derivative factor is independent of this choice; the ratio $8\sqrt{3}/9$ is a ratio of geometric factors $\lvert\omega\rvert$ .

On $[-1,1]$ , for interpolation in $\mathcal{P}_2$ , write the Chebyshev nodes and their monic nodal polynomial, and the monic nodal polynomial of the equispaced nodes $-1,0,1$ . Show that the equispaced polynomial has the larger maximum absolute value, and give the exact ratio of the two maxima.

08 · Summary

Object	Statement
Interpolant in $\mathcal{P}_n$	Through $n+1$ distinct nodes there is exactly one polynomial of degree at most $n$
Lagrange form	$p(x)=\sum_i y_i\ell_i(x)$ , with $\ell_i(x_k)=1$ if $i=k$ and $0$ otherwise
Newton form	Coefficients $a_k=f[x_0,\ldots,x_k]$ multiply the running products $(x-x_0)\cdots(x-x_{k-1})$
Error formula	$f(x)-p(x)=f^{(n+1)}(\xi)\,\omega(x)/(n+1)!$ , with $\omega(x)=\prod(x-x_i)$
Lebesgue comparison	$\\|f-p\\|_\infty\le(1+\Lambda_n)\\|f-q\\|_\infty$ for every $q\in\mathcal{P}_n$
Equispaced nodes	$\Lambda_n$ grows like $2^{n+1}/(e\, n\ln n)$ ; Runge's $1/(1+25x^2)$ diverges uniformly
Chebyshev nodes	Zeros of $T_{n+1}$ ; the monic $\omega$ has uniform norm $2^{-n}$ , the minimum possible on $[-1,1]$
Hand warning	The degree- $4$ equispaced interpolant of Runge's function equals $-11/29$ at $x=4/5$

The error display is the engine the next chapters quote. Chapter 04 applies it on each piece of a spline, with the degree held fixed and $\omega$ local. Chapter 06 integrates it and reads off the error of a quadrature rule.

Next: Piecewise Polynomials and Splines — Chapter 04 keeps the demand that the curve hit prescribed values, and it breaks the single polynomial at the nodes so that one global $\omega$ no longer multiplies a single high derivative across the whole interval.