Past exam of the numerical analysis course of the University of Oxford / 2021 / 1

There are $n+2$ distinct interpolation nodes but only $n+1$ free coefficients in a polynomial of polynomial degree at most $n$. Thus polynomial interpolation is possible precisely when the data satisfy one compatibility equation. To identify it, form the Lagrange interpolation polynomial through all the data:This is the unique interpolation polynomial of polynomial degree at most $n+1$. Its leading coefficient, which is also the order-$(n+1)$ divided difference, isConsequently the required condition isNecessity follows because any qualifying $p_n$ must equal $q$ by uniqueness of polynomial interpolation; sufficiency follows because $D=0$ removes the only possible term of polynomial degree $n+1$ from $q$.

When this condition holds, a slightly shorter expression uses only the first $n+1$ interpolation nodes:This polynomial agrees with $q$ at $n+1$ distinct points, so the root bound for a polynomial gives $p_n=q$ and hence $p_n(x_{n+1})=f_{n+1}$ as required. Equivalently, the compatibility condition says that this expression, evaluated at the last interpolation node, gives $f_{n+1}$.

Write ${\mathcal{P}}_n$ for the vector space of polynomials of polynomial degree at most $n$, and put $p_n(x)={\sum }_{j=0}^n{a}_j{x}^j$. As the question calls the weighted integral an inner product, its finiteness is implicit; for example, a positive integrable weight $w$ suffices for all the continuous functions involved here.

For every $q\in {\mathcal{P}}_n$, differentiating the squared weighted norm $\Vert f-p_n-tq{\Vert }_w^2$ at its minimum $t=0$ gives the orthogonality equationsIn particular, the requested linear system isIts Gram matrix $G_{kj}={\int }_{-1}^{1}w(x)x^{k+j}dx$ is a symmetric positive-definite matrix: for any nonzero vector $a$,Indeed a nonzero polynomial is nonzero on some open interval, and the weight is positive. Therefore $G$ is an invertible matrix, proving uniqueness. Conversely, if these equations hold, the Pythagorean theorem in an inner-product space gives, for every $q\in {\mathcal{P}}_n$,so the solution really is the unique best approximation.

Let $r=f-p_n$ be the continuous function describing the error. The preceding orthogonality equations sayIf $r$ vanishes identically, any $n+1$ distinct points work. If $r$ already has at least $n+1$ distinct zeros, the assertion also follows. Suppose instead that it has at most $n$ distinct zeros. Among its interior zeros, list those at which its sign changes as $t_1<\cdots <t_m$, where $m\le n$, and define the polynomialwith $q=1$ if $m=0$. Between consecutive zeros of $r$, its sign is constant by the intermediate value theorem. At each $t_j$, both $r$ and $q$ change sign; at every other zero of $r$, neither sign changes. Hence $rq$ has one fixed sign throughout $[-1,1]$ wherever it is nonzero. Replacing $q$ by $-q$ if necessary makes $rq\ge 0$ everywhere.

Since $r$ is not identically zero and $q$ has only finitely many zeros, $rq$ is strictly positive on some open interval. Positivity of $w$ givescontradicting orthogonality because $q\in {\mathcal{P}}_n$. ThusThis is the interpolation property of weighted least-squares polynomial approximation. It supplies interpolation nodes depending on $f$ and $w$, rather than nodes prescribed in advance.

Let $L_{n+1}$ denote the conventional Legendre polynomial, normalized by $L_{n+1}(1)=1$. The $n+1$ quadrature nodes are its distinct polynomial roots in $(-1,1)$. For these nodes form the Lagrange cardinal polynomialsChoose the quadrature weights by integrating these polynomials:An equivalent standard formula isThe reason for selecting these quadrature nodes is the resulting degree of precision of a quadrature rule. For any polynomial $p$ of polynomial degree at most $2n+1$, polynomial division givesThe orthogonality of the Legendre polynomial makes ${\int }_{-1}^1{L}_{n+1}s=0$, while $p(x_i)=r(x_i)$ at each quadrature node. The definition of the quadrature weights integrates $r$ exactly, soIn particular, ${\sum }_i{w}_i=2$. Applying this exactness to ${\ell }_i^2$ also proves $w_i={\int }_{-1}^1{\ell }_i(x{)}^{2}dx>0$.

Truncate the Chebyshev series at the full degree of precision of a quadrature rule:Since $|T_j(x)|\le 1$ on $[-1,1]$, the geometric series estimate givesThe same bound proves uniform convergence of the original Chebyshev series, so its sum and the tail estimate are justified. Gauss-Legendre quadrature is exact on $s_{2n+1}$. Its positive quadrature weights sum to $2$, henceTherefore one explicit choice proving exponential convergence of Gaussian quadrature isUsing exactness through polynomial degree $2n+1$ doubles the exponent compared with truncating at polynomial degree $n$.

Set $W=\mathrm{diag}(w_0,\dots ,w_n)$. For column indices $j,k\in \{1,\dots ,n+1\}$, the product $P_{j-1}{P}_{k-1}$ has polynomial degree at most $2n$, so exactness of Gauss-Legendre quadrature and orthonormality giveThus $Q=W^{1/2}A$ is a square matrix with $Q^{T}Q=I$, and therefore is an orthogonal matrix: $Q{Q}^T=I$ as well. It follows thatEquivalently, the rows of the generalized Vandermonde matrix are orthogonal andThe normalization matters: here $P_{n+1}=\sqrt{(2n+3)/2}{L}_{n+1}$, where $L_{n+1}$ is the conventional Legendre polynomial used above. Thus a formula containing only the nodes and the question's orthonormal polynomials isThis identity is the discrete orthogonality of Gaussian quadrature.