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
78
79
|
<!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>Linear Least Squares Problems</TITLE>
<META NAME="description" CONTENT="Linear Least Squares Problems">
<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="tex2html2709" HREF="node46.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html2707" HREF="node43.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html2701" HREF="node44.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html2711" 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="tex2html2712" 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="tex2html2710" HREF="node46.html">Standard Eigenvalue and Singular </A>
<B>Up:</B> <A NAME="tex2html2708" HREF="node43.html">Driver Routines</A>
<B> Previous:</B> <A NAME="tex2html2702" HREF="node44.html">Linear Equations</A>
<BR> <P>
<H2><A NAME="SECTION04322000000000000000">Linear Least Squares Problems</A></H2>
<A NAME="subsecdrivellsq"> </A>
<A NAME="985"> </A>
<P>
The <B>linear least squares (LLS) problem</B><A NAME="987"> </A> is:
<BR><A NAME="llsq"> </A><IMG WIDTH=500 HEIGHT=23 ALIGN=BOTTOM ALT="equation988" SRC="img57.gif"><BR>
where <I>A</I> is an <I>m</I>-by-<I>n</I> matrix, <I>b</I> is a given <I>m</I> element vector
and <I>x</I> is the <I>n</I> element solution vector.
<P>
In the most usual case, <IMG WIDTH=48 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline12690" SRC="img58.gif"> and <IMG WIDTH=94 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline12692" SRC="img59.gif">.
In this case the
solution to problem (<A HREF="node45.html#llsq">3.1</A>) is unique.
The problem is also
referred to as finding a <B>least squares solution</B> to an
<B>overdetermined</B><A NAME="998"> </A> system of linear equations.
<P>
When <I>m</I> < <I>n</I> and <IMG WIDTH=99 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline12696" SRC="img60.gif">, there are an infinite number
of solutions <I>x</I>
that exactly satisfy <I>b</I>-<I>Ax</I>=0. In this case it is often useful to find
the unique solution <I>x</I> that minimizes <IMG WIDTH=31 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline12704" SRC="img61.gif">,
and the problem
is referred to as finding a <B>minimum norm solution</B><A NAME="1001"> </A> to an
<B>underdetermined</B><A NAME="1003"> </A> system of linear equations.
<P>
The driver routine PxGELS<A NAME="1004"> </A>
solves problem (<A HREF="node45.html#llsq">3.1</A>) on the assumption that
<IMG WIDTH=158 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline12706" SRC="img62.gif"> -- in other words, <I>A</I> has <B>full rank</B> --
finding a least squares solution of an overdetermined<A NAME="1008"> </A><A NAME="1009"> </A> system
when <I>m</I> > <I>n</I>, and a minimum norm solution of an underdetermined<A NAME="1010"> </A> system
when <I>m</I> < <I>n</I>.
PxGELS<A NAME="1011"> </A><A NAME="1012"> </A><A NAME="1013"> </A><A NAME="1014"> </A> uses a <I>QR</I> or <I>LQ</I>
factorization<A NAME="1015"> </A><A NAME="1016"> </A> of <I>A</I> and also allows <I>A</I> to be
replaced by <IMG WIDTH=23 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline12722" SRC="img63.gif"> in the statement of the problem (or by <IMG WIDTH=25 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline12724" SRC="img64.gif"> if <I>A</I> is
complex).
<P>
In the general case when we may have
<IMG WIDTH=158 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline12728" SRC="img65.gif"> -- in other words,
<I>A</I> may be <B>rank-deficient</B><A NAME="1019"> </A> --
we seek the <B>minimum norm least squares</B> solution<A NAME="1021"> </A> <I>x</I>
that minimizes both <IMG WIDTH=31 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline12704" SRC="img61.gif"> and <IMG WIDTH=73 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline12736" SRC="img66.gif">.
<P>
The LLS<A NAME="1023"> </A> driver routines are listed in table <A HREF="node45.html#tabdrivellsq">3.3</A>.
<P>
All routines allow several right-hand-side vectors <I>b</I> and corresponding
solutions <I>x</I> to be handled in a single call, storing these vectors as columns
of matrices <I>B</I> and <I>X</I>, respectively.
Note, however, that equation <A HREF="node45.html#llsq">3.1</A> is solved for
each right-hand-side vector independently; this is <I>not</I> the same as
finding a matrix <I>X</I> that minimizes <IMG WIDTH=85 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline12748" SRC="img67.gif">.
<P>
<P><A NAME="1028"> </A><A NAME="tabdrivellsq"> </A><IMG WIDTH=688 HEIGHT=67 ALIGN=BOTTOM ALT="table1027" SRC="img68.gif"><BR>
<STRONG>Table 3.3:</STRONG> Driver routines for linear least squares problems<BR>
<P><HR><A NAME="tex2html2709" HREF="node46.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html2707" HREF="node43.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html2701" HREF="node44.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html2711" 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="tex2html2712" 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="tex2html2710" HREF="node46.html">Standard Eigenvalue and Singular </A>
<B>Up:</B> <A NAME="tex2html2708" HREF="node43.html">Driver Routines</A>
<B> Previous:</B> <A NAME="tex2html2702" HREF="node44.html">Linear Equations</A>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
