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
65
66
67
68
69
70
71
72
73
74
75
76
77
|
<!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</TITLE>
<META NAME="description" CONTENT="QR Factorization">
<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="tex2html2823" HREF="node54.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html2821" 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="tex2html2815" HREF="node52.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html2825" 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="tex2html2826" 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="tex2html2824" HREF="node54.html">LQ Factorization</A>
<B>Up:</B> <A NAME="tex2html2822" HREF="node52.html">Orthogonal Factorizations and Linear </A>
<B> Previous:</B> <A NAME="tex2html2816" HREF="node52.html">Orthogonal Factorizations and Linear </A>
<BR> <P>
<H3><A NAME="SECTION04332100000000000000"><I>QR</I> Factorization</A></H3>
<A NAME="1500"> </A>
<P>
The most
common, and best known, of the factorizations
is the <B><I>QR</I></B> <B>factorization</B><A NAME="1503"> </A>
given by
<BR><IMG WIDTH=352 HEIGHT=48 ALIGN=BOTTOM ALT="displaymath13230" SRC="img115.gif"><BR>
where <I>R</I> is an <I>n</I>-by-<I>n</I> upper triangular matrix and <I>Q</I> is an <I>m</I>-by-<I>m</I>
orthogonal (or unitary) matrix. If <I>A</I> is of full rank <I>n</I>, then <I>R</I> is
nonsingular.
It is sometimes convenient to write the factorization as
<BR><IMG WIDTH=347 HEIGHT=48 ALIGN=BOTTOM ALT="displaymath13231" SRC="img116.gif"><BR>
which reduces to
<BR><IMG WIDTH=287 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath13232" SRC="img117.gif"><BR>
where <IMG WIDTH=19 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline13270" SRC="img118.gif"> consists of the first <I>n</I> columns of <I>Q</I>, and <IMG WIDTH=19 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline13276" SRC="img119.gif"> the
remaining <I>m</I>-<I>n</I> columns.
<P>
If <I>m</I> < <I>n</I>, <I>R</I> is trapezoidal, and the factorization can be written
<BR><IMG WIDTH=371 HEIGHT=29 ALIGN=BOTTOM ALT="displaymath13233" SRC="img120.gif"><BR>
where <IMG WIDTH=19 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline13286" SRC="img121.gif"> is upper triangular and <IMG WIDTH=19 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline13288" SRC="img122.gif"> is rectangular.
<P>
The routine PxGEQRF<A NAME="1518"> </A><A NAME="1519"> </A><A NAME="1520"> </A><A NAME="1521"> </A>
computes the <I>QR</I> factorization<A NAME="1522"> </A><A NAME="1523"> </A>. The matrix <I>Q</I> is not
formed explicitly, but is represented as a product of elementary reflectors,
<A NAME="1524"> </A>
<A NAME="1525"> </A>
as described in section <A HREF="node66.html#secorthog">3.4</A>.
Users need not be aware of the details of this representation,
because associated routines are provided to work with <I>Q</I>:
PxORGQR<A NAME="1527"> </A><A NAME="1528"> </A> (or PxUNGQR<A NAME="1529"> </A><A NAME="1530"> </A>
in the complex case) can generate all or part of <I>Q</I>,
while PxORMQR<A NAME="1531"> </A><A NAME="1532"> </A> (or PxUNMQR)<A NAME="1533"> </A><A NAME="1534"> </A> can pre- or post-multiply
a given matrix by <I>Q</I> or <IMG WIDTH=23 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline13300" SRC="img123.gif">
(<IMG WIDTH=25 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline13302" SRC="img124.gif"> if complex).
<P>
The <I>QR</I> factorization can be used to solve the linear least squares
problem (<A HREF="node45.html#llsq">3.1</A>)<A NAME="1536"> </A><A NAME="1537"> </A> when <IMG WIDTH=48 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline13306" SRC="img125.gif"> and
<I>A</I> is of full rank, since
<BR><IMG WIDTH=668 HEIGHT=50 ALIGN=BOTTOM ALT="displaymath13234" SRC="img126.gif"><BR>
<I>c</I> can be computed by PxORMQR<A NAME="1548"> </A><A NAME="1549"> </A> (or PxUNMQR<A NAME="1550"> </A><A NAME="1551"> </A>), and <IMG WIDTH=12 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline13312" SRC="img127.gif"> consists of its first
<I>n</I> elements. Then
<I>x</I> is the solution of the upper triangular system
<BR><IMG WIDTH=283 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath13235" SRC="img128.gif"><BR>
which can be computed by PxTRTRS<A NAME="1552"> </A><A NAME="1553"> </A><A NAME="1554"> </A><A NAME="1555"> </A>.
The residual vector <I>r</I> is given by
<BR><IMG WIDTH=338 HEIGHT=48 ALIGN=BOTTOM ALT="displaymath13236" SRC="img129.gif"><BR>
and may be computed using PxORMQR<A NAME="1559"> </A><A NAME="1560"> </A> (or PxUNMQR<A NAME="1561"> </A><A NAME="1562"> </A>).
The residual sum of squares <IMG WIDTH=29 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline13320" SRC="img130.gif"> may be computed without forming <I>r</I>
explicitly, since
<BR><IMG WIDTH=349 HEIGHT=17 ALIGN=BOTTOM ALT="displaymath13237" SRC="img131.gif"><BR><HR><A NAME="tex2html2823" HREF="node54.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html2821" 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="tex2html2815" HREF="node52.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html2825" 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="tex2html2826" 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="tex2html2824" HREF="node54.html">LQ Factorization</A>
<B>Up:</B> <A NAME="tex2html2822" HREF="node52.html">Orthogonal Factorizations and Linear </A>
<B> Previous:</B> <A NAME="tex2html2816" HREF="node52.html">Orthogonal Factorizations and Linear </A>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
