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

The best polynomial minimizes the weighted squared error among all polynomials of degree at most $n$:The given inner product is positive definite on continuous functions despite the weight vanishing at zero: a continuous nonzero function is nonzero on an interval containing nonzero points, so its weighted square integral is strictly positive.

If the error is orthogonal to ${\Pi }_n$, then for any $q\in {\Pi }_n$,proving sufficiency. Conversely, if $p_n$ minimizes, perturb it to $p_n+tq$ for any real $t$. The squared error becomesA minimum at $t=0$ forces the linear coefficient to vanish, proving necessity.

For existence, choose the basis $1,x,\dots ,x^n$. Its Gram matrix $G$ is positive definite because $c^{T}Gc$ is the squared norm of the nonzero polynomial with coefficients $c$. Thus $G$ is invertible, and the normal equations $Gc=((u,x^j){)}_{j=0}^n$ have a solution, giving an orthogonal residual and therefore a minimizer. The Pythagorean identity shows any other minimizer differs by a polynomial of zero norm, so it is equal to the first. Hence the best polynomial exists and is unique.

For odd $u$, define $q(x)=-p_n(-x)$. It is another polynomial in ${\Pi }_n$. Changing variables $x\mapsto -x$, and using evenness of the weight $x^2$, gives $\Vert u-q\Vert =\Vert u-p_n\Vert$. Thus $q$ is also a best polynomial. Uniqueness from part (b) gives $p_n(x)=-p_n(-x)$, provingEquivalently, the even component of a candidate is orthogonal to the odd residual and can only increase the squared error.

By part (c), the best degree-at-most-two polynomial is odd, so it must be $p_2(x)=bx$. Orthogonality to $x$ givesThereforeIts error is automatically orthogonal to the even basis functions $1,x^2$ by parity, and the chosen coefficient makes it orthogonal to $x$, so part (b) verifies optimality.

For nonzero $w$, the Householder transformation isThe rank-one matrix $P=w{w}^T/(w^{T}w)$ is symmetric and satisfies $P^2=P$. Consequently $H^T=H$ and $H^{T}H=(I-2P{)}^2=I-4P+4P^2=I$. Thus the matrix is symmetric and orthogonal; geometrically it reflects the component along $w$ and fixes its perpendicular hyperplane.

Let $r=\Vert u{\Vert }_2>0$ and choose $s=1$ when $u_1\ge 0$, otherwise $s=-1$. Set $w=u+sr{e}_1$, which is nonzero because $r+s{u}_1>0$. ComputeThus the reflecting term in $H(w)u$ is exactly $w$, givingIts first coordinate is nonzero and all remaining coordinates vanish. The choice of sign also avoids subtracting nearly equal vectors when the first component is large.

Apply part (b) to the first column of $A$, using an orthogonal reflection to zero all entries below the first. Next apply a Householder reflection to the trailing subvector of the second column, embedded as $\mathrm{diag}(1,H_2)$ so it leaves the first row and the zeros already created intact. Continue similarly through the columns. If a trailing column subvector is zero, skip that step.

The product of these embedded orthogonal matrices sends $A$ to an upper triangular matrix $R$. Write that product as $Q^T$; its transpose $Q$ is also orthogonal. HenceThe argument uses no inverse of $A$ and therefore includes singular matrices.

Multiplying the system by $Q^T$ turns it into $Rx=Q^{T}b$. For nonsingular $A$, compute the transformed right side and solve the upper triangular system by back substitution. Orthogonal transformations preserve Euclidean lengths and do not amplify errors in that transformation.

If $A$ is singular,Since $\det Q=\pm 1$, at least one diagonal entry of $R$ is zero. The resulting triangular system must then be checked for consistency and any free variables, rather than applying divisions by zero.