The QR factorisation of a matrix is its decomposition as the product where the matrix is orthogonal and the matrix is upper triangular. Notice that the QR factorisation of a given matrix is not unique.
QR factorisation is often used to solve Linear Least Squares (LLS) problems, and it forms the basis for the QR Algorithm (see Part II), an iterative algorithm used to compute the eigenvalues and eigenvectors of a matrix.
There are several ways in which the QR factorisation can be carried out. In what follows, we will mainly focus on two such ways, namely the method involving Householder reflections, and the method involving Givens rotations.
A Householder reflection is a transformation of the form
where . Each such matrix is symmetric and orthogonal, and it can be shown that is the reflection of in the hyperplane orthogonal to . Hence, , and so .
A Givens rotation is an orthogonal transformation of determinant 1 (hence it's in ) which coincides with the unit matrix, except at the four entries:
for some .
When implementing the Householder reflections method, we have been careful not to execute explicit matrix multiplication when computing
which is an operation, but, as suggested in the notes, we have first evaluated
and then we have formed
(also in operations).
When implementing the Givens rotations method, we have made use of MATLAB's inbuilt command givens, which essentially returns the values of the required that differ from the identity. See get_givens.m
Moreover, the Givens rotation matrix has 'few' nonzero entries and so is sparse; this allows us to avoid doing a full matrix multiplication - we can get away with changing two rows. See do_givens.m
Running the downloadable MATLAB® code on this page opens a GUI which demonstrates the QR algorithm.
You can enter any square matrix you like, or use one of the preset matrices available. If you choose to use one of the preset matrices, you have a choice between sparse and dense matrices.
If you only want to see the structure of the matrices (represented by black for non-zero entries, white for zero entries, and grey for entries that differ from the previous matrix), you can click on the 'Structure only' radio button. By default the GUI shows both the structure and the values. Note that if your matrix or the values in it are large, it is advisable to switch to the 'structure only' mode because of overlap. As soon as you enter a matrix, it will appear on the far left. At the same time, the current matrix for and the current matrix for will appear.
You can also select whether to use Householder reflections or Givens rotations to perform the QR algorithm. Notice that once you choose a method, you cannot change it during the iterations! The default method is Householder.
Once you have input the matrix (and chosen the method), you can start the QR algorithm by clicking on the 'Next' push button. You will see the new (in grey, you can see which rows have changed from the previous ), and the new . To keep track of the number of iterations, there is a display on the right of the 'Next' push button. Keep going until the algorithm terminates (when the string 'Finished!' appears). To start a new iteration, input (or select) another matrix.
To close the GUI, click on the 'Close' push button.
All files as zip archive: qr_fac_all.zip