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
80
81
82
83
84
85
86
87
88
|
<!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>Error Bounds for the Singular Value Decomposition</TITLE>
<META NAME="description" CONTENT="Error Bounds for the Singular Value Decomposition">
<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="tex2html3986" HREF="node143.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3984" HREF="node132.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html3978" HREF="node141.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3988" 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="tex2html3989" 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="tex2html3987" HREF="node143.html">Further Details: Error Bounds </A>
<B>Up:</B> <A NAME="tex2html3985" HREF="node132.html">Accuracy and Stability</A>
<B> Previous:</B> <A NAME="tex2html3979" HREF="node141.html">Error Bounds for the </A>
<BR> <P>
<H1><A NAME="SECTION04680000000000000000">Error Bounds for the Singular Value Decomposition</A></H1>
<A NAME="secsvd"> </A>
<P>
The singular<A NAME="5879"> </A> value
decomposition (SVD) of a real <I>m</I>-by-<I>n</I> matrix <I>A</I> is defined as
follows. Let <IMG WIDTH=106 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline14127" SRC="img197.gif">. The SVD of <I>A</I> is <IMG WIDTH=86 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline14119" SRC="img195.gif">
(<IMG WIDTH=88 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline14133" SRC="img199.gif"> in the complex case), where
<I>U</I> and <I>V</I> are orthogonal (unitary) matrices and
<IMG WIDTH=152 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline18852" SRC="img671.gif"> is diagonal,
with <IMG WIDTH=172 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline18854" SRC="img672.gif">.
The <IMG WIDTH=13 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline12826" SRC="img77.gif"> are the <B>singular values</B> of <I>A</I> and the leading
<I>r</I> columns <IMG WIDTH=14 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline12840" SRC="img80.gif"> of <I>U</I> and <IMG WIDTH=12 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline12842" SRC="img81.gif"> of <I>V</I> the
<B>left and right singular vectors,</B> respectively.
The SVD of a general matrix is computed by PxGESVD
<A NAME="5884"> </A><A NAME="5885"> </A><A NAME="5886"> </A><A NAME="5887"> </A>
(see subsection <A HREF="node46.html#subsecdriveeig">3.2.3</A>).
<P>
The approximate error
bounds
for the computed singular values
<IMG WIDTH=99 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline18870" SRC="img673.gif"> are
<BR><IMG WIDTH=326 HEIGHT=18 ALIGN=BOTTOM ALT="displaymath18830" SRC="img674.gif"><BR>
The approximate error bounds for the computed singular vectors
<IMG WIDTH=12 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline18872" SRC="img675.gif"> and <IMG WIDTH=14 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline18874" SRC="img676.gif">,
which bound the acute angles between the computed singular vectors
and true singular vectors <IMG WIDTH=12 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline12842" SRC="img81.gif"> and <IMG WIDTH=14 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline12840" SRC="img80.gif">, are
<A NAME="5897"> </A>
<A NAME="5898"> </A>
<BR><IMG WIDTH=500 HEIGHT=43 ALIGN=BOTTOM ALT="eqnarray5899" SRC="img677.gif"><BR>
These bounds can be computing by the following code fragment:
<A NAME="5905"> </A>
<A NAME="5906"> </A>
<P>
<PRE> EPSMCH = PSLAMCH( ICTXT, 'E' )
* Compute singular value decomposition of A
* The singular values are returned in S
* The left singular vectors are returned in U
* The transposed right singular vectors are returned in VT
CALL PSGESVD( 'V', 'V', M, N, A, IA, JA, DESCA, S, U, IU, JU,
$ DESCU, VT, IVT, JVT, DESCVT, WORK, LWORK, INFO )
IF( INFO.GT.0 ) THEN
PRINT *,'PSGESVD did not converge'
ELSE IF( MIN( M, N ).GT.0 ) THEN
SERRBD = EPSMCH * S( 1 )
* Compute reciprocal condition numbers for singular vectors
CALL SDISNA( 'Left', M, N, S, RCONDU, INFO )
CALL SDISNA( 'Right', M, N, S, RCONDV, INFO )
DO 10 I = 1, MIN( M, N )
VERRBD( I ) = EPSMCH*( S( 1 ) / RCONDV( I ) )
UERRBD( I ) = EPSMCH*( S( 1 ) / RCONDU( I ) )
10 CONTINUE
END IF</PRE>
<P>
For example, if
<IMG WIDTH=315 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline18242" SRC="img571.gif">
and
<BR><IMG WIDTH=329 HEIGHT=87 ALIGN=BOTTOM ALT="displaymath18831" SRC="img678.gif"><BR>
then the singular values, approximate error bounds, and true errors are given below.
<P>
<BR><IMG WIDTH=728 HEIGHT=88 ALIGN=BOTTOM ALT="tabular5913" SRC="img679.gif"><BR>
<BR> <HR>
<UL><A NAME="CHILD_LINKS"> </A>
<LI> <A NAME="tex2html3990" HREF="node143.html#SECTION04681000000000000000">Further Details: Error Bounds for the Singular Value Decomposition</A>
</UL>
<BR> <HR>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
