Codex @codex  0

Two vectors are nonorthogonal when their inner product is nonzero. In the power method, the starting vector must be nonorthogonal to a dominant eigenvector.

For a fixed shift $s$ that is not an eigenvalue, inverse iteration is the power method applied to $(A-sI{)}^{-1}$. Before normalization, the $k$th vector is proportional toIf $s<{\lambda }_1$, factor out the first coefficient:Every ratio in parentheses lies strictly between zero and one. The bracket therefore tends to $w_1$, and normalization in the Euclidean norm givesThis proves the stated convergence to $w_1$ or $-w_1$ and exhibits the convergence of fixed-shift inverse iteration rate.

Now suppose ${\lambda }_m<s<{\lambda }_{m+1}$. The closest eigenvalue to $s$ is one of ${\lambda }_m$ and ${\lambda }_{m+1}$.

Finally, if ${\lambda }_n<s$, the closest eigenvalue is ${\lambda }_n$ and its inverse eigenvalue is negative. Thus the direction approaches the line spanned by $w_n$, while normalized vectors alternate between the two signs. These cases are the sign behavior of fixed-shift inverse iteration.

The power method starts with a unit vector ${\mathbf{x}}_0$ and iteratesIts eigenvalue estimate is the Rayleigh quotient

By the real spectral theorem, choose an orthonormal eigenbasis ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ and writeAssume $|{\lambda }_1|>|{\lambda }_2|$, ${\lambda }_1\ne 0$, and $c_1\ne 0$. Before normalization,Thus the direction error is $O(|{\lambda }_2/{\lambda }_1{|}^k)$. Orthogonality makes the linear terms vanish from the Rayleigh quotient:ConsequentlyThis is the quadratic Rayleigh-quotient improvement for the power method.

Fix a shift $s$ that is not an eigenvalue of $A$. Inverse iteration computesand may use $r({\mathbf{x}}_k)$ as the eigenvalue estimate.

For a real symmetric matrix, suppose that one eigenvalue ${\lambda }_{\ast }$ is uniquely closest to $s$ and that ${\mathbf{x}}_0$ has a nonzero component in its eigenspace. Since the iteration is the power method applied to $(A-sI{)}^{-1}$, the normalized vectors converge, up to sign, to an eigenvector for ${\lambda }_{\ast }$. If ${\lambda }_{\mathrm{next}}$ is the second-closest eigenvalue to the shift, the asymptotic direction-error ratio isThus a shift close to the desired eigenvalue gives rapid convergence. The Rayleigh quotients converge to ${\lambda }_{\ast }$ and, for a simple eigenvalue, their errors are of second order in the vector error. This is convergence of fixed-shift inverse iteration.

The power method starts from $q_0\ne 0$ and iteratesIf the eigenvalue of largest modulus is separated by a spectral gap and the initial vector is nonorthogonal to a corresponding eigenvector, the iterates converge in direction to that eigenvector.

Inverse iteration with shift $s$ instead solvesIt applies the power method to $(A-sI{)}^{-1}$ and therefore finds an eigenvector whose eigenvalue is closest to $s$.

Let $q_1$ and $q_n$ be the first and last columns of ${\tilde{Q}}_k$. Since ${\tilde{R}}_k$ is upper triangular,Thus $q_1$ is the normalized $k$th power method iterate starting from $e_1$.

Taking the transpose of $A^k={\tilde{Q}}_k{\tilde{R}}_k$ and using symmetry gives $A^k={\tilde{R}}_k^T{\tilde{Q}}_k^T$. ThereforeSo the last column is the normalized $k$th inverse iteration iterate with shift zero and starting vector $e_n$.

The power method repeatedly normalizes $A{q}^{(k)}$ and estimates the eigenvalue with the Rayleigh quotient $(q^{(k)}{)}^{T}A{q}^{(k)}$. It converges when the dominant eigenvalue is unique in modulus and the initial vector has a nonzero component in its eigendirection.

A spectral gap is a positive separation between designated parts of the spectrum of a linear operator. For the power method, the relevant gap separates the modulus of the dominant eigenvalue from the other eigenvalue moduli.