Linear Algebra Calculators
QR Algorithm
This calculator runs (an extremely primitive version) of the QR algorithm on a square matrix `A` and is provided solely for entertainment value.
We're looking for orthogonal `U` and block upper triangular `T` (with `1\times 1` and `2\times 2` blocks) such that `AU=UT`. The calculator proceeds one step at a time so that the (hoped for) convergence can be watched.
We either start with `A_0=A` and `U_0=I`, or we precondition the problem so that `A_0` is the upper hessenberg form of `A` and `U_0` is an orthogonal matrix satisfying `AU_0=U_0A_0`.
At step `k` we find the QR factorization of `A_{k-1}=Q_{k}R_{k}`. Then we define `A_{k} = R_{k} Q_{k}` and repeat. Note that `A_{k-1} Q_{k} = Q_{k} A_{k}` and if we set `U_k=U_{k-1} Q_k` we have `AU_k=U_kA_k`. If everything goes well `A_k` will converge to `T` and `U_k` will converge to `U`.
We also allow ourselves to use a shift `mu`. Common choices are the Rayleigh shift (the entry in the lower right corner of `A_{k-1}`) and the Wilkinson shift (the eigenvalue of the 2x2 matrix in the lower right corner of `A_{k-1}` that is closest to the Rayleigh shift). Once we have `mu` we compute the QR factorization of `A_{k-1} - mu I=Q_{k}R_{k}`. Then we define `A_{k} = R_{k} Q_{k} + mu I` and repeat (with, probably, a new shift `mu`).
Either choose a size and press this button to get a randomly generated matrix, or enter your matrix in the box below. (Look at the example to see the format.)
Matrix `A`:
Put the matrix `A` in upper Hessenberg form.
Select a shift `mu`.
Execute one step of the algorithm.
The reset button leaves the `A` matrix alone, but restarts the algorithm from the beginning.
Back to calculator page or home page.
