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

A polynomial least-squares approximation $p_n\in {\Pi }_n$ minimizes the weighted residual norm:Equivalently it minimizes ${\int }_{-1}^1{x}^2(u(x)-q(x){)}^{2}dx$. This is a best approximation within a finite-dimensional polynomial space, without an interpolation requirement.

If $p$ is a minimizer, then for each $q\in {\Pi }_n$ the quadratichas a minimum at $t=0$, so $(u-p,q)=0$. Conversely, if this orthogonality holds, then for every $q\in {\Pi }_n$ the Pythagorean theorem in the inner product space givesThus the minimizers are exactly the orthogonal projections characterized byFor existence, write $p={\sum }_{j=0}^n{c}_j{x}^j$. The conditions form the normal equations $Gc=b$, with Gram matrix $G_{ij}=(x^i,x^j)$ and $b_i=(u,x^i)$. For every nonzero coefficient vector $v$,Indeed a nonzero polynomial is nonzero on some open interval away from $0$, where the weight is positive. Hence $G$ is a positive-definite matrix and is invertible, proving existence and uniqueness of $c$. Uniqueness also follows from the preceding Pythagorean theorem identity. The zero of the weight at one point therefore causes no degeneracy on continuous functions or polynomials.

Define the reflected polynomial $\tilde{p}(x)=-p(-x)$. It belongs to ${\Pi }_n$. Since $u$ is odd, a change of variable and the evenness of the weight giveThus $\tilde{p}$ is another polynomial least-squares approximation. By uniqueness, $\tilde{p}=p$, soThe conclusion includes the zero polynomial, which is both odd and even.

By part (c), the best polynomial of degree at most $2$ is odd, hence has the form $p_2(x)=cx$. The orthogonal projection condition with $q=x$ givesThe residual is odd, so its weighted inner products with the even polynomials $1$ and $x^2$ vanish automatically. Thus all three normal equations hold and

For $w\ne 0$, the Householder transformation isLet $P=w{w}^T/(w^{T}w)$. Then $P^T=P$ and $P^2=P$, since $P$ is the orthogonal projection matrix onto the span of $w$. Hence $H^T=H$ andThus $H$ is a symmetric matrix and an orthogonal matrix. Geometrically it reverses the component parallel to $w$ and fixes the perpendicular hyperplane.

Let $r=\Vert u{\Vert }_2>0$, and choose $s=1$ if $u_1\ge 0$ and $s=-1$ otherwise. SetThis vector is nonzero, because $w_1$ has magnitude $|u_1|+r$. Direct computation givesso the Householder transformation satisfiesThe first entry is nonzero and every other entry is zero. The sign choice also avoids cancellation when forming the first entry of $w$, which is useful in numerical computation.

Apply part (b) to the first column of $A$, using the identity if it is already the zero vector. This gives an orthogonal matrix $H_1$ for which $H_{1}A$ has zeros below its first diagonal entry. At stage $j$, apply a Householder transformation to rows $j,\dots ,n$ of column $j$, and extend it by the identity on the first $j-1$ coordinates. If that trailing column is zero, again use the identity. The transformation preserves zeros in earlier columns, since their trailing entries already vanish.

After at most $n-1$ stages,is an upper triangular matrix. Each $H_j$ is symmetric and orthogonal, so withwe have $Q^{T}Q=I$ andNo invertibility assumption was used, so the Householder QR decomposition also exists for singular matrices.

Multiply $Ax=b$ by $Q^T$ to get the equivalent triangular systemFor nonsingular $A$, compute $c=Q^{T}b$ and use back substitution:Orthogonal transformations preserve the Euclidean norm, making this a numerically stable reduction. The factors can be applied as stored Householder transformations without explicitly forming $Q$.

Since $Q$ is invertible, $A$ is singular exactly when $R$ is singular. For an upper triangular matrix,Thus a singular $A$ forces at least one zero diagonal entry in $R$. In that case, ordinary division-based back substitution must be replaced by a consistency/rank analysis: the system may have no solution or infinitely many solutions, and a rank-revealing factorization can identify the free parameters.