1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<!--Converted with LaTeX2HTML 96.1-h (September 30, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds -->
<HTML>
<HEAD>
<TITLE>QR Factorization with Column Pivoting</TITLE>
<META NAME="description" CONTENT="QR Factorization with Column Pivoting">
<META NAME="keywords" CONTENT="slug">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<LINK REL=STYLESHEET HREF="slug.css">
</HEAD>
<BODY LANG="EN" >
<A NAME="tex2html2847" HREF="node56.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html2845" HREF="node52.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html2839" HREF="node54.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html2849" HREF="node1.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="http://www.netlib.org/utk/icons/contents_motif.gif"></A> <A NAME="tex2html2850" HREF="node190.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="http://www.netlib.org/utk/icons/index_motif.gif"></A> <BR>
<B> Next:</B> <A NAME="tex2html2848" HREF="node56.html">Complete Orthogonal Factorization</A>
<B>Up:</B> <A NAME="tex2html2846" HREF="node52.html">Orthogonal Factorizations and Linear </A>
<B> Previous:</B> <A NAME="tex2html2840" HREF="node54.html">LQ Factorization</A>
<BR> <P>
<H3><A NAME="SECTION04332300000000000000"><I>QR</I> Factorization with Column Pivoting</A></H3>
<P>
To solve a linear least squares problem (<A HREF="node45.html#llsq">3.1</A>)<A NAME="1612"> </A><A NAME="1613"> </A>
when <I>A</I> is not of full rank, or the rank of <I>A</I> is in doubt, we can
perform either a <I>QR</I> factorization with column pivoting<A NAME="1614"> </A><A NAME="1615"> </A>
<A NAME="1616"> </A> or a singular value
decomposition (see subsection <A HREF="node64.html#subseccompsvd">3.3.6</A>).
<P>
The <B><I>QR</I></B> <B>factorization with column pivoting</B> is given by
<BR><IMG WIDTH=356 HEIGHT=48 ALIGN=BOTTOM ALT="displaymath13452" SRC="img135.gif"><BR>
where <I>Q</I> and <I>R</I> are as before and <I>P</I> is a permutation matrix, chosen
(in general) so that
<BR><IMG WIDTH=342 HEIGHT=18 ALIGN=BOTTOM ALT="displaymath13453" SRC="img136.gif"><BR>
and moreover, for each <I>k</I>,
<BR><IMG WIDTH=394 HEIGHT=18 ALIGN=BOTTOM ALT="displaymath13454" SRC="img137.gif"><BR>
In exact arithmetic, if <IMG WIDTH=93 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline13482" SRC="img138.gif">, then the whole of the submatrix
<IMG WIDTH=26 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline13484" SRC="img139.gif"> in rows and columns <I>k</I>+1 to <I>n</I>
would be zero. In numerical computation, the aim must be to
determine an index <I>k</I> such that the leading submatrix <IMG WIDTH=26 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline13492" SRC="img140.gif"> in the first
<I>k</I> rows and columns is well conditioned and <IMG WIDTH=26 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline13484" SRC="img139.gif"> is negligible:
<BR><IMG WIDTH=395 HEIGHT=48 ALIGN=BOTTOM ALT="displaymath13455" SRC="img141.gif"><BR>
Then <I>k</I> is the effective rank of <I>A</I>.
See Golub and Van Loan [<A HREF="node189.html#GVL2">71</A>]
for a further discussion of numerical rank determination.
<A NAME="1645"> </A><A NAME="1646"> </A>
<P>
The so-called basic solution to the linear least squares
problem (<A HREF="node45.html#llsq">3.1</A>)<A NAME="1648"> </A> can be obtained from this factorization as
<BR><IMG WIDTH=322 HEIGHT=48 ALIGN=BOTTOM ALT="displaymath13456" SRC="img142.gif"><BR>
where <IMG WIDTH=12 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline13502" SRC="img143.gif"> consists of just the first <I>k</I> elements of <IMG WIDTH=61 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline13506" SRC="img144.gif">.
<P>
The routine PxGEQPF<A NAME="1656"> </A><A NAME="1657"> </A><A NAME="1658"> </A><A NAME="1659"> </A>
computes the <I>QR</I> factorization with column pivoting<A NAME="1660"> </A>
but does not attempt to determine the rank of <I>A</I>.
The matrix <I>Q</I> is represented in exactly the same way as after a call of
PxGEQRF<A NAME="1661"> </A><A NAME="1662"> </A><A NAME="1663"> </A><A NAME="1664"> </A>, and so the routines PxORGQR and PxORMQR can be used to work with <I>Q</I>
(PxUNGQR and PxUNMQR if <I>Q</I> is complex).
<A NAME="1665"> </A><A NAME="1666"> </A><A NAME="1667"> </A><A NAME="1668"> </A>
<A NAME="1669"> </A><A NAME="1670"> </A><A NAME="1671"> </A><A NAME="1672"> </A>
<P>
<BR> <HR>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
