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

For a complex $n\times n$ matrix $B=(b_{ij})$, putThe Gershgorin circle theorem states thatTo prove it, let $Bv=\lambda v$ with $v\ne 0$, and choose $i$ for which $|v_i|={\max }_j|v_j|>0$. The $i$th coordinate of the eigenvalue equation givesThe triangle inequality, followed by division by $|v_i|$, givesThus $\lambda \in D_i$, proving the assertion for every eigenvalue.

The second theorem, Gershgorin eigenvalue counting, says that if a union of $k$ indexed Gershgorin discs is disjoint from the remaining $n-k$ Gershgorin discs, that union contains exactly $k$ eigenvalues, counted with algebraic multiplicity. In particular,Discs that touch are not disjoint; overlapping Gershgorin discs cannot individually be assigned one eigenvalue each.

The power iteration starts from $v_0\ne 0$, normally scaled to unit Euclidean norm, and repeatsNormalization prevents the rapidly growing or decaying magnitudes of $A^k{v}_0$ from obscuring its direction. The iteration requires $w_{k+1}\ne 0$.

Because $A$ is a diagonalizable matrix, choose an eigenbasis $u_1,\dots ,u_n$, with corresponding eigenvalues ${\lambda }_1=\lambda ,{\lambda }_2,\dots ,{\lambda }_n$, and expand $v_0={\sum }_j{c}_j{u}_j$. First suppose the dominant eigenvalue is simple and $c_1\ne 0$. ThenForthe sum in parentheses after $u_1$ is $O(q^k)$ in Big O notation. Consequently the power iteration direction error is $O(q^k)$: the iterates approach the line spanned by $u_1$. For a real matrix, a uniquely dominant eigenvalue is real, since otherwise its complex conjugate would have the same modulus. If $\lambda >0$, $v_k$ approaches one unit eigenvector; if $\lambda <0$, successive $v_k$ alternate signs. In either case,This is the sign and phase in power iteration qualification. Also, the necessary assumption is a nonzero coefficient $c_1$ in the eigenbasis, rather than merely a nonzero ordinary inner product with $u_1$: those tests can differ for a nonsymmetric matrix. If $c_1=0$, the method cannot generate the missing component.

If the dominant value $\lambda$ has a higher-dimensional eigenspace, the same argument replaces $c_1{u}_1$ by the nonzero sum of all starting components in that eigenspace. The limiting direction is then that of this sum, which is still an eigenvector for $\lambda$. The usual algorithm assumes $\lambda \ne 0$; a strict dominance gap guarantees this whenever another eigenvalue is present.

An estimate retaining the sign of $\lambda$ is the Rayleigh quotientContinuity of this quotient at a nonzero eigenvector proves the limit even when $A$ is a nonsymmetric matrix. Alternatively, $(A{v}_k{)}_i/(v_k{)}_i\to \lambda$ for a coordinate whose limiting eigenvector component is nonzero. The scaling factor $\Vert A{v}_k{\Vert }_2$ alone tends only to $|\lambda |$.

Choose a shift $\mu$ which is not an eigenvalue. Inverse iteration applies power iteration to $B=(A-\mu I{)}^{-1}$, implemented by a linear system solve rather than by forming an explicit matrix inverse:A single LU decomposition of $A-\mu I$ can be reused for all the solves at this fixed shift. An eigenpair $A{u}_j={\lambda }_j{u}_j$ transforms intoThus an eigenvalue ${\lambda }_{\ast }$ uniquely closest to $\mu$ becomes the dominant eigenvalue of $B$. For a diagonalizable matrix, the argument in the preceding subpart gives convergence of diagonalizable fixed-shift inverse iteration, provided the starting coefficient in the target eigenspace is nonzero, with power iteration direction error $O(q_{\mu }^k)$, whereFor any prescribed simple eigenvalue, taking a sufficiently close but unequal shift makes the numerator small while the denominator stays close to its positive separation from the remaining eigenvalues. This makes $q_{\mu }$ small and gives very fast convergence per iteration. The Rayleigh quotient of $v_k$ estimates ${\lambda }_{\ast }$ directly. If ${\beta }_k$ estimates the associated eigenvalue of $B$, the corresponding estimate is $\mu +{\beta }_k^{-1}$.

The selection principle also applies when the other eigenvalues have nontrivial blocks in the Jordan normal form: their contributions acquire powers of $k$, multiplying strictly smaller geometric factors. A simple uniquely closest eigenvalue still attracts the direction when the Riesz projection of $v_0$ onto its generalized eigenspace is nonzero. For nonreal target eigenvalues, allow complex shifts and arithmetic; a real shift cannot distinguish a conjugate pair of equal distances. Setting $\mu ={\lambda }_{\ast }$ makes the solve singular, and an exactly zero starting target component prevents convergence to that target in exact arithmetic. When ${\lambda }_{\ast }<\mu$ is real, account for the sign behavior of fixed-shift inverse iteration.

The four row Gershgorin discs have centres $9,3,-4,-5$ and radii $1,2,2,1$, respectively. Their real-axis intersections areNone of the Gershgorin discs contains zero, so the Gershgorin circle theorem givesThe discs centred at $9$ and $3$ are each isolated. By Gershgorin eigenvalue counting, they contain exactly one eigenvalue apiece, and both eigenvalues are simple. Each must be real: the characteristic polynomial is real, so a nonreal root would bring a distinct conjugate root into the same disc. Denote these eigenvalues by $\beta \in [8,10]$ and $\alpha \in [1,5]$. The remaining two eigenvalues lie in the union of the negative-centred discs.

For the shift $4$, the distances satisfyfor either of the other eigenvalues $\gamma$, since its real part is at most $-2$. Thus $\alpha$ is uniquely closest to $4$. Once $4$ is checked not to be an eigenvalue, the natural full target-disc interval enclosure and a conservative asymptotic direction factor areAs always, inverse iteration requires a nonzero initial target component. The following calculation verifies the shift and gives sharper information.

For the tridiagonal matrix, let $p_j(t)$ be the determinant of the leading $j\times j$ block of $tI-A$. Expansion along the last row givesIn particular, $\det A=577$, $p_4(4)=-239$ and $p_4(5)=-583$. Both shifted linear systems are nonsingular. Further exact evaluations areThe intermediate value theorem gives a real root in each of $(-6,-5)$, $(-4,-3)$, $(3,4)$ and $(8,9)$. As $p_4$ has polynomial degree four, these are all its roots and each is simple. In particular, $A$ is a diagonalizable matrix, $\alpha \in (3,4)$ and $\beta \in (8,9)$. The closest competitor to $\alpha$ at the shift $4$ is $\beta$, so this refinement yieldsFor the shift $5$, the original Gershgorin discs only give $|\alpha -5|\le 4$ and $|\beta -5|\ge 3$; those bounds do not decide which is closer. The refined interval enclosures do:for the negative eigenvalues. Therefore the answer for this particular matrix is yes:Both shifts select the same eigenvector line and alternate signs because $\alpha <\mu$. The factor bounds concern asymptotic directional convergence, rather than a universal error reduction from the first iterate for a nonsymmetric matrix. The wider interval $[1,5]$ remains a valid full-disc enclosure for both shifts; $[3,4]$ records the stronger information obtained from the characteristic polynomial.