File: node135.html

package info (click to toggle)
scalapack-doc 1.5-11
links: PTS
area: main
in suites: bullseye, buster, stretch
size: 10,336 kB
ctags: 4,931
sloc: makefile: 47; sh: 18
file content (322 lines) | stat: -rw-r--r-- 28,811 bytes
parent folder | download | duplicates (4)
<!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>How to Measure Errors</TITLE>
<META NAME="description" CONTENT="How to Measure Errors">
<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="tex2html3902" HREF="node136.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3900" 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="tex2html3894" HREF="node134.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3904" 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="tex2html3905" 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="tex2html3903" HREF="node136.html">Further Details:  How Error </A>
<B>Up:</B> <A NAME="tex2html3901" HREF="node132.html">Accuracy and Stability</A>
<B> Previous:</B> <A NAME="tex2html3895" HREF="node134.html">New Sources of Error </A>
<BR> <P>
<H1><A NAME="SECTION04630000000000000000">How to Measure Errors</A></H1>
<A NAME="secnormnotation">&#160;</A>
<P>
<A NAME="4588">&#160;</A>
ScaLAPACK routines return four types of floating-point output arguments:
<UL><A NAME="4590">&#160;</A>
<LI> <EM>Scalar</EM>, such as an eigenvalue of a matrix,
<A NAME="4592">&#160;</A>
<LI> <EM>Vector</EM>, such as the solution <I>x</I> of a linear system <I>Ax</I>=<I>b</I>,
<A NAME="4594">&#160;</A>
<LI> <EM>Matrix</EM>, such as a matrix inverse <IMG WIDTH=29 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline13063" SRC="img110.gif">, and
<A NAME="4597">&#160;</A>
<LI> <EM>Subspace</EM>, such as the space spanned by one or more eigenvectors of a matrix.
</UL>
This section provides measures for errors in these quantities, which we
need in order to express error bounds.
<P>
<A NAME="4600">&#160;</A>
First, consider <EM>scalars</EM>. Let the scalar <IMG WIDTH=10 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17436" SRC="img441.gif"> be an approximation of 
the true answer <IMG WIDTH=10 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline16235" SRC="img369.gif">. We can measure the difference between <IMG WIDTH=10 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline16235" SRC="img369.gif">
and <IMG WIDTH=10 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17436" SRC="img441.gif"> either by the <B>absolute error</B>
<IMG WIDTH=49 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17444" SRC="img442.gif">, or, if <IMG WIDTH=10 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline16235" SRC="img369.gif"> is nonzero, by the <B>relative error</B>
<IMG WIDTH=79 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17448" SRC="img443.gif">. Alternatively, it is sometimes more convenient 
to use <IMG WIDTH=79 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17450" SRC="img444.gif"> instead of the standard expression
for relative error.
If the relative error of <IMG WIDTH=10 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17436" SRC="img441.gif"> is, say, <IMG WIDTH=33 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17454" SRC="img445.gif">, we say that 
<IMG WIDTH=10 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17436" SRC="img441.gif"> is <EM>accurate to 5 decimal digits</EM>.
<A NAME="4614">&#160;</A><A NAME="4615">&#160;</A>
<A NAME="4616">&#160;</A><A NAME="4617">&#160;</A>
<P>
<A NAME="4618">&#160;</A>
To measure the error in <EM>vectors</EM>, we need to measure the <EM>size</EM>
or <EM>norm</EM> of a vector <I>x</I><A NAME="4622">&#160;</A>. A popular norm
is the magnitude of the largest component, <IMG WIDTH=100 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17460" SRC="img446.gif">, 
which we denote by
<IMG WIDTH=38 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline17462" SRC="img447.gif">. This is read <EM>the infinity norm of</EM> <I>x</I>. 
See Table&nbsp;<A HREF="node135.html#tabnorms">6.2</A> for a summary of norms.
<P>
<P><A NAME="4628">&#160;</A><A NAME="tabnorms">&#160;</A><IMG WIDTH=549 HEIGHT=113 ALIGN=BOTTOM ALT="table4627" SRC="img448.gif"><BR>
<STRONG>Table 6.2:</STRONG> Vector and matrix norms<BR>
<P>
<P>
If <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17482" SRC="img449.gif"> is an approximation to the
exact vector <I>x</I>, we will refer to <IMG WIDTH=63 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17486" SRC="img450.gif"> as the
absolute error in <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17482" SRC="img449.gif"> (where <I>p</I> is one of the values in Table&nbsp;<A HREF="node135.html#tabnorms">6.2</A>) 
<A NAME="4658">&#160;</A><A NAME="4659">&#160;</A>
<A NAME="4660">&#160;</A><A NAME="4661">&#160;</A>
and refer to <IMG WIDTH=107 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17492" SRC="img451.gif"> as the relative error
in <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17482" SRC="img449.gif"> (assuming <IMG WIDTH=64 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17496" SRC="img452.gif">). As with scalars,
we will sometimes use <IMG WIDTH=107 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17498" SRC="img453.gif">
for the relative error. 
As above, if the relative error of <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17482" SRC="img449.gif"> is, say <IMG WIDTH=33 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17454" SRC="img445.gif">, we say 
that <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17482" SRC="img449.gif"> is accurate to 5 decimal digits.
The following example illustrates these ideas.
<P>
<BR><IMG WIDTH=364 HEIGHT=67 ALIGN=BOTTOM ALT="displaymath17410" SRC="img454.gif"><BR>
<BR><IMG WIDTH=500 HEIGHT=136 ALIGN=BOTTOM ALT="eqnarray4677" SRC="img455.gif"><BR>
Thus, we would say that <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17482" SRC="img449.gif"> approximates <I>x</I> to 2
decimal digits.
<P>
<A NAME="4707">&#160;</A>
Errors in <EM>matrices</EM> may also be measured with norms<A NAME="4709">&#160;</A>. 
The most obvious
generalization of <IMG WIDTH=38 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline17462" SRC="img447.gif"> to matrices would appear to be
<IMG WIDTH=131 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17512" SRC="img456.gif">, but this does not have certain
important mathematical properties that make deriving error bounds
convenient.
Instead, we will use 
<IMG WIDTH=219 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17514" SRC="img457.gif">,
where <I>A</I> is an <I>m</I>-by-<I>n</I> matrix, or
<IMG WIDTH=208 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17522" SRC="img458.gif">;
see Table&nbsp;<A HREF="node135.html#tabnorms">6.2</A> for other matrix norms.
As before, <IMG WIDTH=70 HEIGHT=34 ALIGN=MIDDLE ALT="tex2html_wrap_inline17524" SRC="img459.gif"> is the absolute 
error<A NAME="4724">&#160;</A><A NAME="4725">&#160;</A>
in <IMG WIDTH=13 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17526" SRC="img460.gif">, <IMG WIDTH=116 HEIGHT=34 ALIGN=MIDDLE ALT="tex2html_wrap_inline17528" SRC="img461.gif">
is the relative error<A NAME="4730">&#160;</A><A NAME="4731">&#160;</A>
in <IMG WIDTH=13 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17526" SRC="img460.gif">, and a relative error in <IMG WIDTH=13 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17526" SRC="img460.gif"> of
<IMG WIDTH=33 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17454" SRC="img445.gif"> means <IMG WIDTH=13 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17526" SRC="img460.gif"> is accurate to 5 decimal digits. 
The following example illustrates these ideas.
<BR><IMG WIDTH=438 HEIGHT=67 ALIGN=BOTTOM ALT="displaymath17411" SRC="img462.gif"><BR>
<BR><IMG WIDTH=500 HEIGHT=206 ALIGN=BOTTOM ALT="eqnarray4739" SRC="img463.gif"><BR>
so <IMG WIDTH=13 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17526" SRC="img460.gif"> is accurate to 1 decimal digit.
<P>
We now introduce some related notation we will use in our error bounds.
The <B>condition number of a matrix</B> <I>A</I> is defined as
<A NAME="4779">&#160;</A>
<IMG WIDTH=172 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline17542" SRC="img464.gif">, where <I>A</I>
is square and invertible, and <I>p</I> is <IMG WIDTH=16 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline17548" SRC="img465.gif"> or one of the other
possibilities in Table&nbsp;<A HREF="node135.html#tabnorms">6.2</A>. The condition number 
measures how sensitive <IMG WIDTH=29 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline13063" SRC="img110.gif"> is to changes in <I>A</I>; the larger
the condition number, the more sensitive is <IMG WIDTH=29 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline13063" SRC="img110.gif">. For example,
for the same <I>A</I> as in the last example,
<BR><IMG WIDTH=468 HEIGHT=67 ALIGN=BOTTOM ALT="displaymath17412" SRC="img466.gif"><BR>
ScaLAPACK
error estimation routines typically compute a variable called 
<TT>RCOND</TT><A NAME="4789">&#160;</A>, which is the reciprocal of the condition number (or an
approximation of the reciprocal). The reciprocal of the condition
number is used instead of the condition number itself in order
to avoid the possibility of overflow when the condition number is very large.
<A NAME="4790">&#160;</A>
<A NAME="4791">&#160;</A>
Also, some of our error bounds will use the vector of absolute values
of <I>x</I>, |<I>x</I>| (<IMG WIDTH=69 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17562" SRC="img467.gif">), or similarly |<I>A</I>|
(<IMG WIDTH=84 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17566" SRC="img468.gif">).
<P>
<A NAME="4794">&#160;</A>
Now we consider errors in <EM>subspaces</EM>. Subspaces are the
outputs of routines that compute eigenvectors and invariant
subspaces of matrices.  We need a careful definition
of error in these cases for the following reason. The nonzero vector <I>x</I> is called a 
<EM>(right) eigenvector</EM> of the matrix <I>A</I> with <EM>eigenvalue</EM>
<IMG WIDTH=8 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline12778" SRC="img69.gif"> if <IMG WIDTH=65 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17574" SRC="img469.gif">. From this definition, we see that
-<I>x</I>, 2<I>x</I>, or any other nonzero multiple <IMG WIDTH=19 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline17580" SRC="img470.gif"> of <I>x</I> is also an
eigenvector. In other words, eigenvectors are not unique. This
means we cannot measure the difference between two supposed eigenvectors 
<IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17482" SRC="img449.gif"> and <I>x</I> by computing <IMG WIDTH=62 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline17588" SRC="img471.gif">, because this may
be large while <IMG WIDTH=73 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline17590" SRC="img472.gif"> is small or even zero for
some <IMG WIDTH=41 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline17592" SRC="img473.gif">. This is true
even if we normalize <I>x</I> so that <IMG WIDTH=63 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline17596" SRC="img474.gif">, since both
<I>x</I> and -<I>x</I> can be normalized simultaneously. Hence, to define
error in a useful way, we need instead to consider the set <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17602" SRC="img475.gif"> of
all scalar multiples <IMG WIDTH=128 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17604" SRC="img476.gif"> of 
<I>x</I>. The set <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17602" SRC="img475.gif"> is 
called the <EM>subspace spanned by <I>x</I></EM> and is uniquely determined 
by any nonzero member of <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17602" SRC="img475.gif">. We will measure the difference
between two such sets by the <EM>acute angle</EM> between them.
Suppose <IMG WIDTH=11 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17614" SRC="img477.gif"> is spanned by <IMG WIDTH=25 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17616" SRC="img478.gif"> and
<IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17602" SRC="img475.gif"> is spanned by <IMG WIDTH=25 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17620" SRC="img479.gif">. Then the acute angle between
<IMG WIDTH=11 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17614" SRC="img477.gif"> and <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17602" SRC="img475.gif"> is defined as
<A NAME="4806">&#160;</A>
<A NAME="4807">&#160;</A>
<BR><IMG WIDTH=399 HEIGHT=43 ALIGN=BOTTOM ALT="displaymath17413" SRC="img480.gif"><BR>
One can show that <IMG WIDTH=47 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline17626" SRC="img481.gif"> does not change when either
<IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17482" SRC="img449.gif"> or <I>x</I> is multiplied by any nonzero scalar. For example, if
<BR><IMG WIDTH=374 HEIGHT=67 ALIGN=BOTTOM ALT="displaymath17414" SRC="img482.gif"><BR>
as above, then <IMG WIDTH=131 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline17632" SRC="img483.gif"> for any
nonzero scalars <IMG WIDTH=11 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline14473" SRC="img243.gif"> and <IMG WIDTH=9 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline17636" SRC="img484.gif">.
<P>
Let us consider another way to interpret the angle <IMG WIDTH=7 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17638" SRC="img485.gif"> between <IMG WIDTH=11 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17614" SRC="img477.gif"> and
<IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17602" SRC="img475.gif">.  
<A NAME="4821">&#160;</A>
<A NAME="4822">&#160;</A>
Suppose <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17482" SRC="img449.gif"> is a unit vector (<IMG WIDTH=63 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline17646" SRC="img486.gif">).
Then there is a scalar <IMG WIDTH=11 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline14473" SRC="img243.gif"> such that
<BR><IMG WIDTH=361 HEIGHT=43 ALIGN=BOTTOM ALT="displaymath17415" SRC="img487.gif"><BR>
The approximation <IMG WIDTH=25 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17650" SRC="img488.gif"> holds when <IMG WIDTH=7 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17638" SRC="img485.gif"> is much less than 1
(less than .1 will do nicely).  If <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17482" SRC="img449.gif"> is an approximate
eigenvector with error bound <IMG WIDTH=115 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline17656" SRC="img489.gif">,
where <I>x</I> is a true eigenvector, there is another true eigenvector
<IMG WIDTH=19 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline17580" SRC="img470.gif"> satisfying <IMG WIDTH=107 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17662" SRC="img490.gif">.
For example, if
<BR><IMG WIDTH=518 HEIGHT=67 ALIGN=BOTTOM ALT="displaymath17416" SRC="img491.gif"><BR>
then <IMG WIDTH=137 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline17664" SRC="img492.gif"> for 
<IMG WIDTH=54 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline17666" SRC="img493.gif">.
<P>
Finally, many of our error bounds will contain a factor <I>p</I>(<I>n</I>) (or <I>p</I>(<I>m</I>,<I>n</I>)),
which grows as a function of matrix dimension <I>n</I> (or dimensions <I>m</I> and <I>n</I>).
It represents a potentially different function for each problem.
In practice, the true errors usually grow at most linearly; using
<I>p</I>(<I>n</I>)=1 in the error bound formulas will often give a 
reasonable estimate; <I>p</I>(<I>n</I>)=<I>n</I> is more conservative.
Therefore, we will refer to <I>p</I>(<I>n</I>) as a ``modestly growing'' 
function of <I>n</I>;
however. it can occasionally be much larger.
For simplicity, the error bounds computed by the code fragments
in the following sections will use <I>p</I>(<I>n</I>)=1. 
This means these computed error bounds may occasionally
slightly underestimate the true error. For this reason we refer
to these computed error bounds as ``approximate error bounds.''
<P>
<B>Further Details:  How to Measure Errors</B><A NAME="secbackgroundnormnotation">&#160;</A>
<P>
<A NAME="4843">&#160;</A><A NAME="4844">&#160;</A>
The relative error <IMG WIDTH=79 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17448" SRC="img443.gif"> in the approximation
<IMG WIDTH=10 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17436" SRC="img441.gif"> of the true solution <IMG WIDTH=10 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline16235" SRC="img369.gif"> has a drawback: it often cannot 
be computed directly, because it depends on the unknown quantity
<IMG WIDTH=17 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17694" SRC="img494.gif">. However, we can often instead estimate
<IMG WIDTH=79 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17450" SRC="img444.gif">, since <IMG WIDTH=10 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17436" SRC="img441.gif"> is
known (it is the output of our algorithm). Fortunately, these two
quantities are necessarily close together, provided either one is small,
which is the only time they provide a useful bound anyway. For example,
<IMG WIDTH=116 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17700" SRC="img495.gif"> implies
<BR><IMG WIDTH=383 HEIGHT=42 ALIGN=BOTTOM ALT="displaymath17417" SRC="img496.gif"><BR>
so they can be used interchangeably.
<P>
Table&nbsp;<A HREF="node135.html#tabnorms">6.2</A> contains a variety of norms we will use to 
measure errors.
These norms have the properties that 
<IMG WIDTH=154 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17702" SRC="img497.gif">, and 
<IMG WIDTH=162 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17704" SRC="img498.gif">, where <I>p</I> is one of
1, 2, <IMG WIDTH=16 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline17548" SRC="img465.gif">, and <I>F</I>. These properties are useful for deriving
error bounds.
<P>
An error bound that uses a given norm may be changed into an error bound
that uses another norm. This is accomplished by multiplying the first
error bound by an appropriate function of the problem dimension.
Table&nbsp;<A HREF="node135.html#tableVectorNormFpq">6.3</A> gives the
factors <IMG WIDTH=44 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17716" SRC="img499.gif"> such that <IMG WIDTH=136 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17718" SRC="img500.gif">, where
<I>n</I> is the dimension of <I>x</I>.
<P>
<P><A NAME="4863">&#160;</A><A NAME="tableVectorNormFpq">&#160;</A><IMG WIDTH=525 HEIGHT=130 ALIGN=BOTTOM ALT="table4862" SRC="img501.gif"><BR>
<STRONG>Table 6.3:</STRONG> Bounding one vector norm in terms of another<BR>
<P>
<P>
Table&nbsp;<A HREF="node135.html#tableMatrixNormFpq">6.4</A> gives the
factors <IMG WIDTH=67 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17746" SRC="img502.gif"> such that <IMG WIDTH=165 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17748" SRC="img503.gif">, where
<I>A</I> is <I>m</I>-by-<I>n</I>.
<P>
<P><A NAME="4893">&#160;</A><A NAME="tableMatrixNormFpq">&#160;</A><IMG WIDTH=549 HEIGHT=151 ALIGN=BOTTOM ALT="table4892" SRC="img504.gif"><BR>
<STRONG>Table 6.4:</STRONG> Bounding one matrix norm in terms of another<BR>
<P>
<P>
The two-norm of <I>A</I>, <IMG WIDTH=34 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline17802" SRC="img505.gif">, is also called the <B>spectral
norm</B> of <I>A</I> and is equal to the <B>largest singular value</B>
<IMG WIDTH=59 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline17806" SRC="img506.gif"> of <I>A</I>.
We shall also need to refer to the <B>smallest singular value</B>
<IMG WIDTH=57 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline17810" SRC="img507.gif"> of <I>A</I>; its value can be defined in a similar way to
the definition of the two-norm in Table&nbsp;<A HREF="node135.html#tabnorms">6.2</A>, namely, as
<IMG WIDTH=147 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline17814" SRC="img508.gif"> when <I>A</I> 
has at least as many rows as columns, and defined as
<IMG WIDTH=158 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline17818" SRC="img509.gif"> when <I>A</I> has more
columns than rows.  The two-norm, 
Frobenius norm<A NAME="4938">&#160;</A><A NAME="4939">&#160;</A>, 
and singular values of a matrix do not change
if the matrix is multiplied by a real orthogonal (or complex unitary) matrix.
<P>
Now we define <EM>subspaces</EM> spanned by more than one vector,
and <EM>angles between subspaces</EM>.
<A NAME="4942">&#160;</A>
<A NAME="4943">&#160;</A>
Given a set of <I>k</I>
<I>n</I>-dimensional vectors <IMG WIDTH=81 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17826" SRC="img510.gif">, they determine
a subspace <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17602" SRC="img475.gif"> consisting of all their possible linear combinations
<IMG WIDTH=79 HEIGHT=33 ALIGN=MIDDLE ALT="tex2html_wrap_inline17830" SRC="img511.gif">, <IMG WIDTH=14 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline17832" SRC="img512.gif"> scalars <IMG WIDTH=7 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17834" SRC="img513.gif">. We also
say that <IMG WIDTH=81 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17826" SRC="img510.gif"> <EM>spans</EM> <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17602" SRC="img475.gif">.
The difficulty in measuring the difference between subspaces is that
the sets of vectors spanning them are not unique.
For example, <IMG WIDTH=25 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17620" SRC="img479.gif">, <IMG WIDTH=39 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17842" SRC="img514.gif"> and <IMG WIDTH=34 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17844" SRC="img515.gif"> all determine the 
same subspace. 
Therefore, we cannot simply compare the subspaces spanned by
<IMG WIDTH=81 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17846" SRC="img516.gif"> and <IMG WIDTH=81 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17826" SRC="img510.gif"> by
comparing each <IMG WIDTH=14 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline17850" SRC="img517.gif"> to <IMG WIDTH=14 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline17852" SRC="img518.gif">. Instead, we will measure the <EM>angle</EM>
between the subspaces, which is independent of the spanning set
of vectors. Suppose subspace <IMG WIDTH=11 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17614" SRC="img477.gif"> is spanned by
<IMG WIDTH=81 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17846" SRC="img516.gif"> and that subspace <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17602" SRC="img475.gif">
is spanned by <IMG WIDTH=81 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17826" SRC="img510.gif">. If <I>k</I>=1, we instead write more
simply <IMG WIDTH=25 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17616" SRC="img478.gif"> and <IMG WIDTH=25 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17620" SRC="img479.gif">.
When <I>k</I>=1, we define
the angle <IMG WIDTH=51 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline17870" SRC="img519.gif"> between
<IMG WIDTH=11 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17614" SRC="img477.gif"> and <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17602" SRC="img475.gif"> as the acute angle
between <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17482" SRC="img449.gif"> and <I>x</I>.
When <I>k</I>&gt;1, we define the acute angle between <IMG WIDTH=11 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17614" SRC="img477.gif"> and 
<IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17602" SRC="img475.gif"> as the largest acute angle between any vector <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17482" SRC="img449.gif"> in
<IMG WIDTH=11 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17614" SRC="img477.gif"> and the closest vector <I>x</I> in <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17602" SRC="img475.gif"> to <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17482" SRC="img449.gif">:
<P>
<BR><IMG WIDTH=500 HEIGHT=41 ALIGN=BOTTOM ALT="eqnarray4963" SRC="img520.gif"><BR>
ScaLAPACK routines that compute subspaces return 
vectors <IMG WIDTH=81 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17846" SRC="img516.gif"> spanning a subspace
<IMG WIDTH=11 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17614" SRC="img477.gif"> that are <EM>orthonormal</EM>. This means the
<I>n</I>-by-<I>k</I> matrix <IMG WIDTH=112 HEIGHT=34 ALIGN=MIDDLE ALT="tex2html_wrap_inline17904" SRC="img521.gif"> 
satisfies <IMG WIDTH=76 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17906" SRC="img522.gif">. Suppose also that
the vectors <IMG WIDTH=81 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17826" SRC="img510.gif"> spanning <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17602" SRC="img475.gif">
are orthonormal, so <IMG WIDTH=112 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline17912" SRC="img523.gif"> also
satisfies <IMG WIDTH=76 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline17914" SRC="img524.gif">.
Then there is a simple expression for the angle between
<IMG WIDTH=11 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17614" SRC="img477.gif"> and <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17602" SRC="img475.gif">:
<A NAME="4982">&#160;</A>
<A NAME="4983">&#160;</A>
<BR><IMG WIDTH=365 HEIGHT=21 ALIGN=BOTTOM ALT="displaymath17418" SRC="img525.gif"><BR>
For example, if
<BR><IMG WIDTH=442 HEIGHT=67 ALIGN=BOTTOM ALT="displaymath17419" SRC="img526.gif"><BR>
then <IMG WIDTH=123 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline17920" SRC="img527.gif">.
<P>
As stated above, all our bounds will contain a factor 
<I>p</I>(<I>n</I>) (or <I>p</I>(<I>m</I>,<I>n</I>)), which measures how roundoff errors can grow
as a function of matrix dimension <I>n</I> (or <I>m</I> and <I>m</I>).
In practice, the true error usually grows just linearly with <I>n</I>, 
or even slower,
but we can generally prove only much weaker bounds of the form <IMG WIDTH=100 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline17934" SRC="img528.gif">.
This is because we cannot rule out the extremely unlikely possibility of rounding
errors all adding together instead of canceling on average. Using
<IMG WIDTH=100 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline17934" SRC="img528.gif"> would give pessimistic and unrealistic bounds, especially
for large <I>n</I>, so we content ourselves with describing <I>p</I>(<I>n</I>) as a
``modestly growing'' polynomial function of <I>n</I>. Using <I>p</I>(<I>n</I>)=1 in
the error bound formulas will often give a reasonable error estimate.
For detailed derivations of various
<I>p</I>(<I>n</I>), see [<A HREF="node189.html#GVL2">71</A>, <A HREF="node189.html#wilkinson1">114</A>, <A HREF="node189.html#higham96">84</A>, <A HREF="node189.html#demmelMA221">38</A>].
<P>
There is also one situation where <I>p</I>(<I>n</I>) can grow as large as <IMG WIDTH=32 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline17950" SRC="img529.gif">:
Gaussian elimination. This typically  occurs only on specially constructed
matrices presented in numerical analysis courses [<A HREF="node189.html#wilkinson1">114</A>, p. 212,].
However, the expert driver for solving linear systems, PxGESVX<A NAME="4997">&#160;</A><A NAME="4998">&#160;</A><A NAME="4999">&#160;</A><A NAME="5000">&#160;</A>,
provides error bounds incorporating <I>p</I>(<I>n</I>), and so this rare possibility
can be detected.
<P>
<HR><A NAME="tex2html3902" HREF="node136.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3900" 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="tex2html3894" HREF="node134.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3904" 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="tex2html3905" 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="tex2html3903" HREF="node136.html">Further Details:  How Error </A>
<B>Up:</B> <A NAME="tex2html3901" HREF="node132.html">Accuracy and Stability</A>
<B> Previous:</B> <A NAME="tex2html3895" HREF="node134.html">New Sources of Error </A>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>