Past exam of the numerical analysis course of the University of Oxford / 2014 (A7, 4326)

A Givens rotation acts as the identity matrix outside two selected coordinates $i,j$, and has the following block on those coordinates:The convention with the opposite signs of the sines is equivalent after replacing $\theta$ by $-\theta$. A Householder reflection with nonzero normal vector $w\in {\mathbb{R}}^n$ isIt reverses the component parallel to $w$ and fixes the perpendicular hyperplane. Both are orthogonal matrices, so their transposes are their inverses and they preserve the Euclidean norm.

If $u=0$, any nonzero $w$, for instance the first Cartesian basis vector $e_1$, gives $H(w)u=0$ and $\alpha =0$. Suppose $u\ne 0$. Choosewhere ${\mathrm{sgn}}_{+}(r)=1$ for $r\ge 0$ and $-1$ otherwise. This choice ensures $w\ne 0$, including when $u$ is already on the first coordinate axis. Since ${\alpha }^2=u^{T}u$,Therefore the Householder reflection satisfiesThe orthogonality of $H(w)$, used here to check length preservation, gives $|\alpha |=\Vert H(w)u{\Vert }_2=\Vert u{\Vert }_2$. The chosen sign also avoids catastrophic cancellation in $w_1=u_1-\alpha$. This is a Householder reflection sending a vector to a coordinate axis with no zero-normal exception.

Set $A^{(0)}=A$. At step $k=1,\dots ,n-2$, let $u=A_{k+1:n,k}^{(k-1)}$ be the column below the diagonal. Choose a Householder reflection ${\hat{H}}_k$ sending $u$ onto its first coordinate axis, and embed it asIf $u=0$, use $P_k=I$. Left multiplication annihilates entries $k+2,\dots ,n$ in column $k$. Right multiplication performs the matching operation on row $k$, because the matrix remains symmetric. The first $k$ coordinates are fixed, so zeros already created in earlier columns and rows are preserved.

Here the orthogonality of each $P_k$ is used explicitly: $P_k^{-1}=P_k^T$, so each update is a similarity transformation and preserves eigenvalues. After $n-2$ steps,where $Q$ is orthogonal and $T$ is a real symmetric tridiagonal matrix. This is Householder tridiagonalization.

A QR factorization of a real $n\times n$ matrix isThus $Q$ is an orthogonal matrix and $R$ is an upper triangular matrix. It exists even if $A$ is singular; requiring positive diagonal entries of $R$ is a convenient uniqueness convention for nonsingular $A$, rather than part of the general existence statement. Over the complex numbers, replace orthogonal by unitary and transpose by conjugate transpose.

For an efficient QR algorithm, first reduce a general real matrix to upper Hessenberg matrix by orthogonal similarities. For a real symmetric matrix, use Householder tridiagonalization; the resulting symmetric tridiagonal matrix is the usual input in this setting. These structures are preserved by suitable QR algorithm implementations and greatly reduce the work per iteration.

The output is the eigenvalues, together with an orthogonal reduction when the factors are accumulated. In the symmetric case the target is a diagonal matrix, whose diagonal entries are the real eigenvalues; the accumulated orthogonal columns are eigenvectors. For a general real matrix, the target is the real form in a Schur decomposition: an upper block triangular matrix with diagonal blocks of size one or two. The two-by-two blocks represent complex conjugate eigenvalue pairs. An arbitrary unshifted iteration need not converge, so these describe the intended converged output, with appropriate shifts and block deflation in the QR algorithm.

With $A_0=A$, repeat the shifted QR algorithm:The QR shift ${\mu }_k$ is chosen from $A_k$, for example its bottom-right entry or an eigenvalue of a trailing two-by-two block. Explicitly using the orthogonality of $Q_k$ givesThus each update is a matrix similarity preserving eigenvalues. Accumulate $Q_0{Q}_1\cdots Q_k$ if eigenvectors or the full reduction are wanted. Once a subdiagonal entry is negligible, block deflation in the QR algorithm separates the corresponding blocks and iteration continues on the active block.

The initial bottom-right entry is zero, so the chosen QR shift is ${\mu }_0=0$. One valid QR factorization is $Q_0=A$, $R_0=I$, using explicitly that $A^{T}A=I$. The update isIt repeats forever and never approaches a diagonal matrix. With the standard positive-diagonal convention for $R$, this factorization is unique, so the Rayleigh-shift iteration is stationary and fails to diagonalize $A$.

The failure is independent of harmless sign conventions. The columns of $A$ are already orthonormal, so another QR factorization can only replace $Q_0$ by $AD$ and $R_0$ by $D$, where $D$ is diagonal with entries $\pm 1$. Then $A_1=DAD$ still has zero diagonal and off-diagonal magnitudes one. Subsequent bottom-right shifts remain zero and the off-diagonal magnitude never decreases. The eigenvalues are $+1,-1$, with equal absolute values, explaining the lack of separation in the unshifted QR algorithm.

Let the real QR shift be $\mu$ and put $r=\sqrt{1+{\mu }^2}$. A valid QR factorization, including the singular cases $\mu =\pm 1$, isHere $Q^{T}Q=I$, and multiplying verifies $QR=A-\mu I$. Using this orthogonality in the shifted update givesIt is diagonal exactly when ${\mu }^2-1=0$. Therefore all real shifts giving the eigenvalues in one iteration areThe resulting diagonal is $(-1,1)$ or $(1,-1)$, respectively. Both QR shifts are exact eigenvalues. Sign changes in the QR factorization conjugate $A_1$ by a diagonal sign matrix and do not alter its zero pattern. This is Exact-shift diagonalization of a two-state swap matrix.

The norm induced by the specified inner product is the L2 normA polynomial $p_n\in {\Pi }_n$ is a best polynomial least-squares approximation whenMinimizing this norm is equivalent to minimizing its square, the integrated squared error. Continuity ensures that a function with zero squared norm is identically zero: a nonzero value would give a neighbourhood on which the square has a positive integral.

Write $p_n(x)={\sum }_{j=0}^n{c}_j{x}^j$. The allowed orthogonal projection characterization, applied to the basis $1,x,\dots ,x^n$, gives the normal equationsExplicitly $G_{ij}=0$ if $i+j$ is odd and $G_{ij}=2/(i+j+1)$ if it is even. These equations can also be derived by differentiating $\int (u-\sum c_j{x}^j{)}^{2}dx$ with respect to each coefficient.

The Gram matrix $G$ is a symmetric positive-definite matrix. For any nonzero real coefficient vector $z$,The polynomial inside the square is nonzero, so its square is positive on some interval. Hence $G$ has zero kernel and is invertible. Thus the normal equations have exactly one solution, giving exactly one best least-squares polynomial. This proves both existence and uniqueness. For completeness, if the residual is orthogonal to ${\Pi }_n$, then for every $q\in {\Pi }_n$ the Pythagorean theorem gives $\Vert u-q{\Vert }^2=\Vert u-p_n{\Vert }^2+\Vert p_n-q{\Vert }^2$, directly verifying minimality and uniqueness.

Split the best polynomial into its even and odd parts, $p_n=p_e+p_o$. Both parts belong to ${\Pi }_n$. Since $u$ is odd, $u-p_o$ is odd and $p_e$ is even. Their product is odd, so its integral on the symmetric interval vanishes. The orthogonality givesThe candidate $p_o$ cannot have a strictly smaller error than a minimizer. Consequently $\Vert p_e{\Vert }^2=0$, and continuity gives $p_e=0$. Thus $\boxed{p_n(-x)=-p_n(x)}$. For $n=0$ this means $p_0=0$, which is indeed an odd function. More generally this is parity preservation by polynomial least-squares projection.

By parity preservation by polynomial least-squares projection, $p_2(x)=\beta x$: the constant and quadratic coefficients vanish. The remaining normal equation isThereforeThe residual is automatically orthogonal to $1$ and $x^2$ by parity and to $x$ by construction, so it is orthogonal to every element of ${\Pi }_2$. This checks the full linear least squares condition, rather than only a necessary coefficient equation.

Projection onto the constant polynomials requires the residual to be orthogonal to $1$. For the original inner product,For the weighted inner product the corresponding normal equation isHenceIt increases monotonically towards one. Although the weight vanishes at zero, it is positive elsewhere, and a nonzero continuous function is nonzero on an interval of positive weight. Thus the weighted expression really is an inner product and the constant minimizer is unique.

The normalized weight $(2n+1)x^{2n}/2$ has total mass one and assigns mass $r^{2n+1}$ to $[-r,r]$ for each $0<r<1$. Its mass therefore concentrates near $-1$ and $1$, where $x^2=1$. This explains why the weighted best constant tends to one rather than to the unweighted spatial average. It is endpoint concentration in weighted constant approximation.

The Gershgorin circle theorem states that every eigenvalue of $A=(a_{ij})\in {\mathbb{R}}^{n\times n}$ belongs to at least one of the closed Gershgorin discsThe eigenvalue may be complex even though the matrix is real. To prove the theorem, choose a nonzero complex eigenvector $v$ with $Av=\lambda v$ and an index $i$ at which $|v_i|$ is maximal. Then $|v_i|>0$, and the $i$th row givesThe triangle inequality yieldsThus $\lambda \in D_i$, proving the assertion without any symmetry assumption.

The second theorem, or Gershgorin eigenvalue counting, states: if a union of $k$ indexed Gershgorin discs is disjoint from all remaining discs, it contains exactly $k$ eigenvalues, counted with algebraic multiplicity. In particular, an isolated Gershgorin disc contains exactly one simple eigenvalue. The separation condition is essential; merely drawing overlapping discs does not assign one eigenvalue to each.

The determinant is invariant under transpose. Therefore the characteristic polynomials coincide:Their polynomial roots, including their algebraic multiplicities, are the same, so $A$ and $A^T$ have the same eigenvalues. This allows column sums as well as row sums to supply Gershgorin discs for the same spectrum.

The first row has off-diagonal sum $a_{12}<1/4$. Rows $2,\dots ,n-1$ have sums less than $1/2$, and the last row has sum $c+a_{n,n-1}<5/4$, since $0<c<1$. Every row except the second therefore has its Gershgorin disc strictly away from zero: its centre is at least one in the first row and at least three in the remaining rows.

For the second row, an exact sufficient condition is $|b|>a_{21}+a_{23}$. Since the sum is strictly below $1/2$, the coefficient-independent boundsguarantee that zero is outside every Gershgorin disc. Consequently zero is not an eigenvalue and $A$ is an invertible matrix. Equality at $\pm 1/2$ is allowed because the off-diagonal entry bounds are strict. These are sufficient strict diagonal dominance bounds; values of $b$ between them can also give invertible matrices.

Put $n=2m$. With $b=2$, the row Gershgorin discs have centres $1,2,\dots ,n$ and radiiApplying the theorem to the transpose gives column Gershgorin discs with radiiThe enlarged disc moves from the last centre to the first centre. All small discs in either family are mutually disjoint, because adjacent centres are one unit apart and their radii have sum strictly below one.

For the row family, the small disc at any $i\le m$ is also disjoint from the enlarged disc at $n$ ifFor the column family, every small disc at $i\ge m+1$ is disjoint from the enlarged disc at $1$ by the same estimate, since $i-1\ge m$. Thus the Gershgorin eigenvalue counting theorem certifies one simple eigenvalue near each of $1,\dots ,m$ from rows, and near each of $m+1,\dots ,n$ from columns. The certified small discs from the two families are themselves disjoint, so these are $n$ different eigenvalues.

The largest nonnegative $c$ certified by these uniform row-and-column separation bounds isMore generally the argument works for $|c|\le c_{\mathrm{G}}$. The endpoint is included because all actual entry bounds, and hence all actual radius estimates above, are strict. For $n=8$, $c_{\mathrm{G}}=13/4$: row discs isolate centres $1,2,3,4$, and column discs isolate centres $5,6,7,8$.

For $c>c_{\mathrm{G}}$, taking the adjacent entries sufficiently close to $1/4$ makes the enlarged row disc meet the small disc at $m$, and the enlarged column disc meet the small disc at $m+1$. Hence this particular uniform disc-separation certificate stops there. This is a Gershgorin guarantee, not a necessary spectral threshold: failure of disc separation does not prove repeated or nonreal eigenvalues for the actual matrix.

Finally, a real matrix has nonreal eigenvalues in complex conjugate pairs. Every certified small disc has a real centre and is invariant under conjugation. A nonreal eigenvalue in it would bring its distinct conjugate into the same disc, contradicting its count of exactly one. Therefore all the certified eigenvalues are real and simple. The two-family argument is Complementary row and column Gershgorin isolation.

Strict diagonal dominance givesThus every $b_{ii}\ne 0$, and the diagonal matrix $D$ has inverse $D^{-1}=\mathrm{diag}(1/b_{11},\dots ,1/b_{nn})$. The iteration matrix has entriesEach row Gershgorin disc for $T$ is centred at zero and has radiusTherefore every eigenvalue of $T$ satisfiesEquivalently, the induced matrix norm satisfies $\Vert T{\Vert }_{\infty }<1$, bounding the spectral radius. This is the usual Jacobi convergence from strict diagonal dominance; the Jacobi error matrix is $-T$, with the same eigenvalue magnitudes.