Lagmental Vicfred

QR Iteration Reveals Eigenvalues without Forming a Polynomial by Vicfred

Last updated: Sun 14 August 2011

tags: mathematics, matrix factorizations, least squares, positive matrices

Repeated QR factorizations produce similar matrices that tend toward triangular form. Keeping the exact identity in view prevents the geometric or probabilistic intuition from drifting.

Notation

Matrix factorizations expose different geometry: \(A=QR\) separates an orthonormal frame, while \(A=U\Sigma V^\ast\) separates rotations from axis scaling.

$$ A_k=Q_kR_k,\qquad A_{k+1}=R_kQ_k $$

The typography mirrors the proof: first declare \(\mathsf D\), then state \(\mathsf C\). The symbol \(\Longrightarrow\) below is a logical dependency, not extra mathematical structure.

$$ A_{k+1}=Q_k^\ast A_kQ_k $$

Stress the formula

A worked instance is useful here because it exposes every index that the compressed statement hides.

$$ A_k=(Q_0\cdots Q_{k-1})^\ast A_0(Q_0\cdots Q_{k-1})\longrightarrow\begin{pmatrix}\lambda_1&\ast&\cdots\\0&\lambda_2&\ast\\\vdots&\ddots&\ddots\end{pmatrix} $$

Interpretation

What survives the example is not its particular numbers but the relation encoded by the two rows below. That relation is the part worth transporting to a new setting.

$$ \begin{aligned} \mathsf{D}\;&:\quad A_k=Q_kR_k,\qquad A_{k+1}=R_kQ_k,\\[5pt] \mathsf{C}\;&:\quad A_{k+1}=Q_k^\ast A_kQ_k. \end{aligned} $$

Limit of the argument

Conditioning matters numerically. An exact algebraic identity can be a poor computational method when it squares the condition number.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] A_{k+1}=Q_k^\ast A_kQ_k \end{gathered}} $$

The result is compact enough to reuse without pretending that the caveat has disappeared. The worked line remains the quickest consistency check.

This article was posted on Tue 25 May 2010. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.