Past exam of the options II course of the University of Oxford / 2010 / P (Numerical Analysis)

A best approximation to $x$ from $U_n$ is a vector $u_{\ast }\in U_n$ such thatThe definition requires attainment of the infimum. This finite-dimensional subspace does have such an approximation, as the explicit projection below shows; completeness of the whole inner-product space is unnecessary.

Expand both squared norms using the inner product:Adding cancels the cross terms, giving the parallelogram lawThe real part may be omitted in a real inner-product space.

Suppose $u,v\in U_n$ both minimize the distance, with common value $d$. Apply the parallelogram identity to $x-u$ and $x-v$:The midpoint belongs to the linear subspace $U_n$, so its distance from $x$ is at least $d$. It follows that $\Vert u-v{\Vert }^2\le 0$, hence $u=v$. Thus the best approximation is unique.

Let $v={\sum }_{k=1}^n⟨x,e_k⟩e_k$, using the convention that the inner product is linear in its first argument. Orthonormality givesfor every $j$. Hence $x-v$ is orthogonal to $U_n$. For any $u\in U_n$, the Pythagorean identity gives $\Vert x-u{\Vert }^2=\Vert x-v{\Vert }^2+\Vert v-u{\Vert }^2$, so $v$ is the unique best approximation. Therefore

Expand the norm of the orthonormal-basis expression. All cross terms vanish and $\Vert e_k\Vert =1$, so

The residual $x-P_{n}x$ is orthogonal to $P_{n}x\in U_n$. Thus the Pythagorean theorem gives $\Vert x{\Vert }^2=\Vert x-P_{n}x{\Vert }^2+\Vert P_{n}x{\Vert }^2$. Substitute part (ii) and rearrange:Nonnegativity of the left-hand side also gives the finite form of Bessel's inequality.

Assume the usual nondegenerate interval $a<b$. The integral is bilinear and symmetric because the functions and weight are real. It is nonnegative on $(f,f)$. If $f$ is nonzero at a point, continuity makes $|f|$ bounded below by a positive number on a nontrivial relative interval nearby, and the positive continuous weight is also bounded below there. Hence ${\int }_a^b{f}^{2}w>0$. Thus the formula is positive definite and defines an inner product.

The functions are orthogonal precisely whenA singleton interval would make this integral zero for every function, so the condition $a<b$ is necessary.

The intended orthogonal-polynomial convention is $\mathrm{deg}{p}_k=k$. An arbitrary orthonormal basis without this degree ordering does not satisfy the claim: permuting a standard basis can place the nonzero constant polynomial last, where it has no roots rather than $n+1$. The following proof uses the required degree ordering.

It makes $p_k$ orthogonal to every polynomial of degree less than $k$, since $p_0,\dots ,p_{k-1}$ form a basis of that lower-degree space. Let $c_1,\dots ,c_r$ be the distinct roots in $(a,b)$ at which $p_k$ changes sign, and put $q(x)={\prod }_{j=1}^r(x-c_j)$, with $q=1$ if $r=0$. The product $p_{k}q$ has constant sign on $(a,b)$ except at its finitely many zeros: each sign change of $p_k$ is canceled by that of $q$.

If $r<k$, then $q$ has degree below $k$, so orthogonality gives ${\int }_a^b{p}_{k}qw=0$. But a nonzero constant-sign continuous product against the positive weight has a nonzero integral, a contradiction. Thus $r\ge k$. Since $\mathrm{deg}{p}_k=k$, there are exactly $k$ such roots, all simple, with no additional endpoint roots. In particularThis also includes $k=0$, where the polynomial is nonzero constant and has no roots.

Use the intended degree ordering from part (b). Let ${\ell }_j$ be the degree-$n$ Lagrange cardinal polynomial at the distinct roots $x_0,\dots ,x_n$ of $p_{n+1}$:For any $f\in {\Pi }_{2n+1}$, polynomial division gives $f=s{p}_{n+1}+r$ with $\mathrm{deg}s\le n$ and $\mathrm{deg}r\le n$. Orthogonality of $p_{n+1}$ to ${\Pi }_n$ makes the integral of $s{p}_{n+1}$ zero, and that product also vanishes at every quadrature node. Meanwhile $r={\sum }_{j}r(x_j){\ell }_j$ by interpolation. ConsequentlyThus the rule is exact up to degree $2n+1$. To determine the sign of a weight, apply exactness to ${\ell }_j^2$, of degree $2n$:The inequality is strict because ${\ell }_j$ is a nonzero polynomial and the weight is positive. This is the Gaussian quadrature construction; the source asks only for nonnegative weights, and the proof gives positivity.