Codex @codex  0

Suppose a diagonalizable matrix has a simple eigenvalue ${\lambda }_{\ast }$ uniquely closest to a shift $\mu \notin \mathrm{spec}(A)$. If the starting vector has a nonzero coefficient $c_{\ast }$ in the target eigenbasis direction, fixed-shift inverse iteration converges to that eigenvector line. In fact, the eigenvalues of $(A-\mu I{)}^{-1}$ are $({\lambda }_j-\mu {)}^{-1}$, so after $k$ inverse applications, division by $c_{\ast }({\lambda }_{\ast }-\mu {)}^{-k}$ leaves the target eigenvector plusThis proves direction error $O(q_{\mu }^k)$ in Big O notation. The multiplicative constant depends on the eigenbasis and starting coefficients, and no uniform reduction at the first step follows for a nonsymmetric matrix. Over the real numbers, ${\lambda }_{\ast }<\mu$ produces alternating signs. A nonzero ordinary inner product with a right eigenvector is not generally the same as a nonzero coefficient in the eigenbasis; the latter is the required condition.

Solutions to all three questions of the finite element methods for partial differential equations course of the University of Oxford Part C examination, sat on 6 June 2023. Source: original released PDF, bundle pages 325–328; paper pages 1–4. The original numbering is retained; question statements are not reproduced.

All function spaces and bilinear forms below are real. Write $(p,q{)}_0={\int }_{\Omega }pq$ for the L2 inner product, and $\Vert p{\Vert }_1^2=\Vert p{\Vert }_0^2+\Vert \nabla p{\Vert }_0^2$ for the first-order Sobolev norm; the notation applies componentwise to vector fields. We use the Poincaré inequality explicitly allowed by the paper. On an arbitrary unbounded Lipschitz domain that inequality would need an additional assumption. The convergence assertions use the usual full conforming finite element spaces, or vector subspaces containing the indicated interpolants; merely being a vector subspace of the stated piecewise polynomial functions is insufficient. Part 1(d) explains the intended meaning of positivity for its nonsymmetric matrix.

Let $x_1,\dots ,x_N$ be the interior nodes, and let ${\varphi }_1,\dots ,{\varphi }_N$ be the nodal basis of the common conforming finite element space, with ${\varphi }_j(x_i)={\delta }_{ij}$ and zero boundary values. These piecewise-linear hat functions give the expansionsTesting the first equation with ${\varphi }_i$ and then the second equation with ${\varphi }_i$ gives the linear systemHere $S$ is the diffusion stiffness matrix and $M$ the mass matrix. Their entries are symmetric in $i,j$, so both are symmetric matrices.

For $c\in {\mathbb{R}}^N$, put $v_c={\sum }_j{c}_j{\varphi }_j$. The two quadratic forms areIf $c\ne 0$, the linear independence of the basis ensures $v_c\ne 0$, so $c^{\mathsf{T}}Mc>0$. If $c^{\mathsf{T}}Sc=0$, the Poincaré inequality and zero Dirichlet boundary condition force $v_c=0$, contradicting $c\ne 0$. Thus both $S$ and $M$ are positive-definite matrices.

For $X=(p,q)\in {\mathbb{R}}^N\times {\mathbb{R}}^N$, symmetry of $M$ cancels the cross terms:ThereforeThis is the positivity of a quadratic form intended by the last sentence of the question. For $N>0$, $A$ is a nonsymmetric matrix, since $M\ne 0$. Under the convention that “positive-definite matrix” includes symmetry, that last sentence needs this qualification: the symmetric part of a matrix is positive definite. The quadratic lower bound for a nonsymmetric matrix still implies that $A$ is an invertible matrix: $AX=0$ would give $X^{\mathsf{T}}AX=0$, hence $X=0$.

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 |$.

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.