next up previous contents index
Next: Complete Orthogonal Factorization Up: Orthogonal Factorizations and Linear Previous: LQ Factorization

QR Factorization with Column Pivoting

To solve a linear least squares problem (3.1)   when A is not of full rank, or the rank of A is in doubt, we can perform either a QR factorization with column pivoting     or a singular value decomposition (see subsection 3.3.6).

The QR factorization with column pivoting is given by
where Q and R are as before and P is a permutation matrix, chosen (in general) so that
and moreover, for each k,
In exact arithmetic, if tex2html_wrap_inline13482, then the whole of the submatrix tex2html_wrap_inline13484 in rows and columns k+1 to n would be zero. In numerical computation, the aim must be to determine an index k such that the leading submatrix tex2html_wrap_inline13492 in the first k rows and columns is well conditioned and tex2html_wrap_inline13484 is negligible:
Then k is the effective rank of A. See Golub and Van Loan [71] for a further discussion of numerical rank determination.   

The so-called basic solution to the linear least squares problem (3.1)  can be obtained from this factorization as
where tex2html_wrap_inline13502 consists of just the first k elements of tex2html_wrap_inline13506.

The routine PxGEQPF     computes the QR factorization with column pivoting  but does not attempt to determine the rank of A. The matrix Q is represented in exactly the same way as after a call of PxGEQRF    , and so the routines PxORGQR and PxORMQR can be used to work with Q (PxUNGQR and PxUNMQR if Q is complex).          

Susan Blackford
Tue May 13 09:21:01 EDT 1997