7.6 The QR algorithm
The algorithm used in practice to compute the eigenvalues is the so-called QR algorithm, proposed independently by John G. R. Francis and the Soviet mathematician Vera Kublanovskaya. This is where all of the lessons we have learned in linear algebra converge. Describing the QR algorithm is very simple, as it is the iteration of a matrix decomposition and a multiplication step.
However, understanding why it works is a different question. Behind the scenes, the QR algorithm combines many tools we have learned earlier. To start, let’s revisit the good old Gram-Schmidt orthogonalization process.
7.6.1 The QR decomposition
If you recall, we encountered the Gram-Schmidt orthogonalization process (Theorem 13) when introducing the concept of orthogonal bases.
In essence, this algorithm takes an arbitrary basis v1,…,vn and turns it into an orthonormal one e1,…,en, such that e1,…,ek spans the same subspace as v1,…,vk for all 1 ≤...
