QR DecompositionThe QR decomposition of a rectangular matrix  with linearly independent columns involves the computation of matrices  and  such that where the columns of  form an orthonormal basis for the columns of  and  is upper triangular. It can be computed in Mathematica with the function QRDecomposition. This computes the QR decomposition of a sample matrix. The result is a list of the two matrices. In[1]:=  |
Out[2]=
|
In fact the first argument that is returned is a list of the orthonormal columns. To generate the  matrix it is necessary to compute the transpose, as shown below. In[3]:=  |
Out[4]=
|
This is a matrix factorization, so  is equal to  . In[5]:=  |
Out[5]=
|
In addition, the columns of  are orthonormal. Because the result of QRDecomposition returns the list of columns, they can be extracted with one part index. The following two examples demonstrate the orthonormal properties of the columns. In[6]:=  |
Out[6]=
|
In[7]:=  |
Out[7]=
|
The QR decomposition is also defined for rectangular matrices. In this case  . In[8]:=  |
Out[10]=
|
For an input matrix where  , the result of QRDecomposition are two matrices: an  matrix  and an  matrix  . When the matrix represents an overdetermined system of equations, that is,  , QRDecomposition returns an  matrix  and an  matrix  . (Note that to generate the matrix  , it is necessary to transpose the result from QRDecomposition.) This is demonstrated in the following example. In[11]:=  |
Out[13]=
|
This is often referred to as the thin QR decomposition, see for example Golub and van Loan. If you wish to compute the full QR decomposition, it is possible to pad out  with extra rows of zeros and  with extra orthonormal columns. This can be done with the following function. In[14]:=  |
The  and  computed by this function are  and  , respectively. In[15]:=  |
Out[17]=
|
In[18]:=  |
Out[18]=
|
Solving Systems of EquationsFor a square non-singular matrix  the QR decomposition can be used to solve the matrix equation  , as is also the case for the LU decomposition. However, when the matrix is rectangular, the QR decomposition is also useful for solving the matrix equation. One particular application of the QR decomposition is to find least squares solutions to overdetermined systems, by solving the system of normal equations because  , this can be simplified as Thus the normal equations simplify to and because  is non-singular this simplifies to Because  is triangular this is a particularly easy system to solve; sample code to implement this technique is given in the section Examples: Least Squares QR.
| 
