NLA MT25, QR algorithm

• [[Course - Numerical Linear Algebra MT25]]^U
  • [[Notes - NLA MT25, QR factorisation]]^U

When I took this course, this section was non-examinable. My previous notes on the QR algorithm can be found here:

• [[Notes - Numerical Analysis HT24, QR factorisation]]^U
• [[Notes - Numerical Analysis HT24, QR algorithm]]^U

Notes

• If $A$ is symmetric:
  • The reduction to Hessenberg form also makes $A$ tridiagonal (although in my previous notes, we only analyse the QR algorithm under the assumption $A$ is symmetric)
  • The QR steps for a tridiagonal matrix require only $O(n)$ steps rather than $O(n^2)$ steps.
  • There are efficient algorithms for tridiagonal eigenvalue problems.
  • Another possibility is using the Nakatsukasa-Freund-Higham algorithm
• Connections to computing the SVD:
  • The SVD decomposition is closely related to the eigenvalue decomposition of symmetric matrices (since the singular values are the eigenvalues of $A^\top A$)
  • However in the SVD algorithm, $U$ and $V$ are allowed to be different so you can modify the algorithm to save some of the work that was used to make sure the matrices pre- and post- multiplying the eigenvalue matrix were the same
  • One popular algorithm for SVD inspired by the QR algorithm is Golub-Kahan
• Generalised [[Notes - NLA MT25, Eigenvalue problems]]^U
  • These can be solved via a variant of the QR algorithm called the QZ algorithm.