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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
<!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>Standard Error Analysis</TITLE>
<META NAME="description" CONTENT="Standard Error Analysis">
<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="tex2html3928" HREF="node138.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3926" HREF="node136.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html3920" HREF="node136.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3930" 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="tex2html3931" 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="tex2html3929" HREF="node138.html">Improved Error Bounds</A>
<B>Up:</B> <A NAME="tex2html3927" HREF="node136.html">Further Details: How Error </A>
<B> Previous:</B> <A NAME="tex2html3921" HREF="node136.html">Further Details: How Error </A>
<BR> <P>
<H2><A NAME="SECTION04641000000000000000">Standard Error Analysis</A></H2>
<A NAME="secbackwarderror"> </A>
<P>
<A NAME="5005"> </A>
We illustrate standard error analysis with the simple example of
evaluating the scalar function <I>y</I>=<I>f</I>(<I>z</I>). Let the output of the
subroutine that implements <I>f</I>(<I>z</I>) be denoted <IMG WIDTH=43 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline18005" SRC="img530.gif">; this includes
the effects of roundoff. If <IMG WIDTH=129 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline18007" SRC="img531.gif">,
where <IMG WIDTH=7 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline18009" SRC="img532.gif"> is small,
we say that <IMG WIDTH=22 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline18011" SRC="img533.gif"> is a <B>backward stable</B>
<A NAME="5007"> </A>
<A NAME="5008"> </A>
algorithm for <I>f</I>,
or that the <B>backward error</B> <IMG WIDTH=7 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline18009" SRC="img532.gif"> is small.
<A NAME="5010"> </A>
<A NAME="5011"> </A>
In other words, <IMG WIDTH=43 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline18005" SRC="img530.gif"> is the
exact value of <I>f</I> at a slightly perturbed input <IMG WIDTH=37 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline18021" SRC="img534.gif">.<A NAME="tex2html1232" HREF="footnode.html#5012"><IMG ALIGN=BOTTOM ALT="gif" SRC="http://www.netlib.org/utk/icons/foot_motif.gif"></A>
<P>
Suppose now that <I>f</I> is a smooth function, so that
we may approximate it near <I>z</I> by a straight line:
<IMG WIDTH=196 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline18033" SRC="img537.gif">.
Then we have the simple error estimate
<BR><IMG WIDTH=412 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath17997" SRC="img538.gif"><BR>
Thus, if <IMG WIDTH=7 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline18009" SRC="img532.gif"> is small and the derivative <I>f</I>'(<I>z</I>) is
moderate, the error <IMG WIDTH=97 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline18039" SRC="img539.gif"> will be small.<A NAME="tex2html1233" HREF="footnode.html#5013"><IMG ALIGN=BOTTOM ALT="gif" SRC="http://www.netlib.org/utk/icons/foot_motif.gif"></A>
This is often written
in the similar form
<BR><IMG WIDTH=430 HEIGHT=41 ALIGN=BOTTOM ALT="displaymath17998" SRC="img540.gif"><BR>
This approximately bounds the <B>relative error</B>
<A NAME="5023"> </A><A NAME="5024"> </A>
<IMG WIDTH=80 HEIGHT=40 ALIGN=MIDDLE ALT="tex2html_wrap_inline18045" SRC="img541.gif"> by the product of
the <B>condition number of</B>
<I>f</I> <B>at</B> <I>z</I>, <IMG WIDTH=46 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline18051" SRC="img542.gif">, and the
<B>relative backward error</B> <IMG WIDTH=16 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline18053" SRC="img543.gif">.
<A NAME="5032"> </A>
<A NAME="5033"> </A>
Thus we get an error bound by multiplying a
condition<A NAME="5034"> </A> number and
a backward error (or bounds for these quantities). We call a problem
<B>ill-conditioned</B><A NAME="5036"> </A> if its condition number is large,
and <B>ill-posed</B><A NAME="5038"> </A>
if its condition number is infinite (or does not exist).<A NAME="tex2html1241" HREF="footnode.html#5039"><IMG ALIGN=BOTTOM ALT="gif" SRC="http://www.netlib.org/utk/icons/foot_motif.gif"></A>
<P>
If <I>f</I> and <I>z</I> are vector quantities, then <I>f</I>'(<I>z</I>) is a matrix
(the Jacobian). Hence, instead of using absolute values as before,
we now measure <IMG WIDTH=7 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline18009" SRC="img532.gif"> by a vector norm <IMG WIDTH=22 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline18065" SRC="img544.gif"> and <I>f</I>'(<I>z</I>)
by a matrix norm <IMG WIDTH=51 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline18069" SRC="img545.gif">. The conventional (and coarsest) error analysis
uses a norm such as the infinity norm. We therefore call
this <B>normwise backward stability</B>.
<A NAME="5041"> </A>
<A NAME="5042"> </A>
For example, a normwise stable
method for solving a system of linear equations <I>Ax</I>=<I>b</I> will
produce a solution <IMG WIDTH=9 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17482" SRC="img449.gif"> satisfying <IMG WIDTH=132 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline18075" SRC="img546.gif">, where
<IMG WIDTH=95 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline18077" SRC="img547.gif"> and
<IMG WIDTH=86 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline18079" SRC="img548.gif"> are both small (close to machine epsilon).
In this case the condition number is
<IMG WIDTH=192 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline18081" SRC="img549.gif">
(see section <A HREF="node139.html#secAxb">6.5</A>).
<A NAME="5045"> </A>
<P>
Almost all of the algorithms in ScaLAPACK (as well as LAPACK)
are stable in the sense just described<A NAME="tex2html1245" HREF="footnode.html#8055"><IMG ALIGN=BOTTOM ALT="gif" SRC="http://www.netlib.org/utk/icons/foot_motif.gif"></A>:
when applied to a matrix <I>A</I>
they produce the exact result for a slightly different matrix <I>A</I>+<I>E</I>,
where <IMG WIDTH=95 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline18077" SRC="img547.gif"> is of order <IMG WIDTH=6 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline17202" SRC="img429.gif">.
<P>
Condition numbers may be expensive to compute
exactly.
For example, it costs about <IMG WIDTH=25 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline18115" SRC="img554.gif"> operations to solve <I>Ax</I>=<I>b</I>
for a general matrix <I>A</I>, and computing <IMG WIDTH=48 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline18121" SRC="img555.gif"> <EM>exactly</EM> costs
an additional <IMG WIDTH=25 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline18123" SRC="img556.gif"> operations, or twice as much.
But <IMG WIDTH=48 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline18121" SRC="img555.gif"> can be <EM>estimated</EM> in only <IMG WIDTH=42 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline18127" SRC="img557.gif">
operations beyond those <IMG WIDTH=25 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline18115" SRC="img554.gif"> necessary for solution,
a tiny extra cost. Therefore, most of ScaLAPACK's condition numbers
and error bounds are based on estimated condition
numbers<A NAME="5062"> </A>, using the method
of [<A HREF="node189.html#hager">72</A>, <A HREF="node189.html#higham1">80</A>, <A HREF="node189.html#nick2">81</A>].
<P>
The price one pays for using an estimated rather than an
exact condition number is occasional
(but very rare) underestimates of the true error; years of experience
attest to the reliability of our estimators, although examples
where they badly underestimate the error can be constructed [<A HREF="node189.html#higham90">82</A>].
Note that once a condition estimate is large enough
(usually <IMG WIDTH=49 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline18131" SRC="img558.gif">), it confirms that the computed
answer may be completely inaccurate, and so the exact magnitude
of the condition estimate conveys little information.
<P>
<HR><A NAME="tex2html3928" HREF="node138.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3926" HREF="node136.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html3920" HREF="node136.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3930" 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="tex2html3931" 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="tex2html3929" HREF="node138.html">Improved Error Bounds</A>
<B>Up:</B> <A NAME="tex2html3927" HREF="node136.html">Further Details: How Error </A>
<B> Previous:</B> <A NAME="tex2html3921" HREF="node136.html">Further Details: How Error </A>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
