Past exam of the approximation of functions course of the University of Oxford

Original solutions to all three questions of the Approximation of Functions paper sat on 16 June 2011. Source: released Mathematics papers, Part C 2007 11.pdf. Question 3 includes a counterexample to the unqualified printed endpoint exchange rule and the corrected rule. Statements are not reproduced.

The Lagrange interpolation polynomial isThe interpolation nodes are distinct, so these weights are well defined. Applying the same Lagrange interpolation to the constant polynomial one gives $1={\sum }_r{w}_r{\pi }_{n,r}(x)$. Dividing this identity and the formula for $p$ by ${\pi }_n(x)$ gives the barycentric interpolation formulaThis displayed quotient is used away from the interpolation nodes; at $x=x_r$ its removable singularity is evaluated by setting $p(x_r)=u_r$. Multiplying every weight by the same nonzero constant leaves the quotient unchanged.

Chebyshev points are generally more reliable at high degree. The Chebyshev-Lobatto nodes, or the affine images of the roots of a Chebyshev polynomial, cluster near the interval endpoints and control the amplification measured by the Lebesgue constant of interpolation. Equally spaced interpolation nodes can produce large endpoint oscillations and the Runge phenomenon. This is a comparison of numerical robustness and general approximation behaviour, not a claim that one set minimizes the error for every individual function.

Assume $h>0$. The functional is the third forward difference: each forward difference lowers the polynomial degree by one, so it annihilates every polynomial of degree at most two. Directly, $X[1]=-1+3-3+1=0$, $X[x]=3h-6h+3h=0$, and $X[x^2]=3h^2-12h^2+9h^2=0$.

The Peano kernel theorem now gives $X[u]={\int }_0^{3h}K(t)u^{(3)}(t)dt$, where the Peano kernel of the third forward difference isHere $s_{+}=\max (s,0)$ is the positive-part truncated power function. The normalized quadratic cardinal B-spline isIts three polynomial pieces agree with the displayed kernel after rescaling, giving $\boxed{K(t)=h^2{B}_2(t/h)}$. Its knots are $0,h,2h,3h$ in the physical variable, and $K$ is positive throughout $(0,3h)$.

The kernel mass can be evaluated without integrating each piece: apply its representation to $u(x)=x^3/6$, whose third derivative is one. This gives ${\int }_0^{3h}K(t)dt=X[x^3/6]=h^3$. The weighted mean value theorem for integrals with a nonnegative weight therefore yieldsContinuity of $u^{(3)}$ and strict positivity of the weight in the interior place an attained weighted-average value in that open interval, including the constant-derivative case.

Take $n\ge 1$, as intended by the stated normalization. The Chebyshev polynomial recurrence $T_{r+1}=2x{T}_r-T_{r-1}$, with $T_0=1$ and $T_1=x$, shows by mathematical induction that $T_n$ has polynomial degree $n$ and leading coefficient $2^{n-1}$. Consequently $f_n=2^{1-n}{T}_n$ is a monic polynomial. At the ordered Chebyshev extreme points $t_j=-\cos (j\pi /n)$,and $\Vert f_n{\Vert }_{\infty }=2^{1-n}$.

Suppose a monic polynomial $q$ of the same polynomial degree had $\Vert q{\Vert }_{\infty }<2^{1-n}$. The difference $f_n-q$ has degree at most $n-1$ because its leading coefficients cancel. Its signs at the $n+1$ ordered extreme points strictly alternate. The intermediate value theorem supplies a distinct root of a polynomial between each consecutive pair, giving at least $n$ roots. This contradicts its degree bound. Hence the monic Chebyshev extremal polynomial satisfiesAt $n=0$ the printed formula instead gives $f_0=2$, which is not monic; the degree-zero minimizer is the constant one. This endpoint case requires the separate normalization $f_0=1$.

Put $x=\cos \theta$ in the weighted inner product. Since $T_r(\cos \theta )=\cos (r\theta )$,The last equality follows by the product-to-sum trigonometric identity and integration. Thus these are nonzero mutually orthogonal polynomials. The first $n+1$ are linearly independent, and the vector space $P_n$ has dimension $n+1$; therefore $\boxed{P_n=\mathrm{span}(T_0,\dots ,T_n)}$.

For any $q\in P_n$, the function of the real parameter $t$has a minimum at $t=0$. Its derivative there vanishes, proving $\boxed{(u-p_n,q)=0}$. This is precisely the defining orthogonality of an orthogonal projection, or a least-squares polynomial in an orthogonal-polynomial basis. Conversely, this condition and the Pythagorean theorem for inner product spaces give $\Vert u-q{\Vert }_2^2=\Vert u-p_n{\Vert }_2^2+\Vert p_n-q{\Vert }_2^2$, proving the minimum and its uniqueness.

Expand $p_n={\sum }_{r=0}^n{a}_r{T}_r$ in the basis already established and take the inner product with $T_s$. Orthogonality leaves $a_s(T_s,T_s)=(u,T_s)$, soIn particular $a_0={\pi }^{-1}{\int }_0^{\pi }u(\cos \theta )d\theta$ and $a_r=2{\pi }^{-1}{\int }_0^{\pi }u(\cos \theta )\cos (r\theta )d\theta$ for $r\ge 1$. These are the corresponding Chebyshev series coefficients with the constant coefficient convention used in this question.

The equioscillation theorem says that $p_n\in P_n$ is the unique best uniform approximation to a real continuous function $u$ on $[-1,1]$ exactly when its error attains alternating values $\pm E_n$ at $n+2$ ordered distinct points. If $E_n=0$, the error vanishes everywhere and the conclusion is immediate.

For the exponential function, write the candidate line as $p_1(x)=ax+b$. Its error $r(x)=e^x-ax-b$ is strictly convex. Equal endpoint errors require $a=(e-e^{-1})/2=\sinh 1$, and the interior minimum is at $c=\log a$, because $r^{\prime }(c)=e^c-a=0$. Equating the endpoint error to the negative interior error givesIndeed $r(-1)=r(1)=E_1$ and $r(c)=-E_1$; convexity puts every other error value between these extremes. The equioscillation theorem proves optimality.

For the reference-point assertions, put $M=\Vert u-q_a{\Vert }_{\infty }$. The alternating-reference error bound gives $|h_a|\le E_n$. In fact this inequality is strict here. To see the equality obstruction explicitly, let $p_n$ be optimal, $d=p_n-q_a$, andSince $d$ has polynomial degree at most $n$, its order-$(n+1)$ divided difference vanishes: ${\sum }_r{\omega }_{r}d(x_r)=0$. If $E_n=|h_a|>0$, change the overall sign to take $h_a>0$. The error bound for $p_n$ implies $(-1{)}^{r}d(x_r)\ge 0$. The signs of the weights are $(-1{)}^{n+1-r}$, so every term in this sum has the same weak sign. Every term must vanish; $d$ then has $n+2$ distinct zeros, forcing $d=0$. This contradicts $M>E_n$. If $h_a=E_n=0$, $u=p_n$ and the same zero-count argument again forces $q_a=p_n$, also a contradiction. ThusAt every old reference point the absolute error is only $|h_a|$, so a maximizer $\eta$ cannot be one of those points. The printed same-sign choice of $k$ additionally presumes $h_a\ne 0$; when $h_a=0$, none of the reference errors has the nonzero sign of the maximal error.

The printed replacement rule needs an endpoint qualification. For an interior $\eta \in (x_0,x_{n+1})$ and nonzero $h_a$, replacing the adjacent endpoint of its containing reference interval with the same error sign preserves spatial order and alternating signs. The single-point exchange in polynomial minimax approximation then gives the requested strict increase. On an irregular grid, the globally nearest same-sign reference point need not be that adjacent endpoint, so adjacency must be specified. More generally, for any correctly ordered replacement set $z_0<\cdots <z_{n+1}$ on which the old error alternates in sign, let $w_r={\prod }_{s\ne r}(z_r-z_s{)}^{-1}$. The vanished divided difference of $q_a$ and the new alternation equations showThis is a strict weighted average because all the weights are positive in absolute value and $M>|h_a|$.

For an exterior $\eta$ whose error sign is opposite that at the nearest endpoint, merely replacing the nearest same-sign point, as printed, need not preserve alternation. A concrete counterexample uses $n=2$, $q_a=0$, $h_a=1$, and reference pointsLet $u$ be the piecewise linear function through $(-1,-2),(0,1),(1/5,-1),(2/5,1),(3/5,-1),(1,-1)$. Then $M=2$ at $\eta =-1$, and $1<E_2\le 3/2<2$: the upper bound is achieved by the trial constant $-1/2$, while equality at the lower bound is excluded by the preceding zero-count argument. The printed rule selects $k=1$ and hence $z=(0,-1,2/5,3/5)$. Neverthelesssatisfy every printed new alternation equation, with $\boxed{|h_b|=61/64<1=|h_a|}$. Direct substitution at the four points checks this failure; reordering those points would destroy their assigned alternating signs.

The corrected exterior rule inserts $\eta$ as the new extreme reference point and drops the farthest endpoint when its sign is opposite the nearest endpoint. If its sign agrees with the nearest endpoint, replace that endpoint. Interior exchanges replace the adjacent reference point with the same sign. These rules preserve an ordered alternating set, so the strict-increase formula applies in every case.

The resulting Remez algorithm solves the $n+2$ linear alternation equations for the polynomial coefficients and reference height, locates a global maximum of the error, and performs a valid exchange unless $M=|h_a|$. The interval $|h_a|\le E_n\le M$ is an explicit optimality certificate; a small gap $M-|h_a|$ gives a stopping test. Strict increase of bounded reference heights alone does not prove convergence, so that stronger conclusion needs the additional analysis of the chosen exchange algorithm.