Numerical Errors - Revision history

GethinWilliams: /* Total Error */

2011-02-22T12:21:33Z

Total Error

GethinWilliams: /* Truncation Errors */

2011-02-22T12:15:09Z

Truncation Errors

GethinWilliams: /* Truncation Errors */

2011-02-22T12:05:27Z

Truncation Errors

GethinWilliams: /* Truncation Errors */

2011-02-22T11:56:32Z

Truncation Errors

GethinWilliams: /* Algorithms Matter */

2011-02-22T11:51:35Z

Algorithms Matter

GethinWilliams at 11:45, 22 February 2011

2011-02-22T11:45:01Z

GethinWilliams: /* I didn't expect that! A tale of surprising Rounding Errors */

2011-02-22T11:42:52Z

I didn't expect that! A tale of surprising Rounding Errors

GethinWilliams: /* I didn't expect that! */

2011-02-22T11:41:57Z

I didn't expect that!

GethinWilliams: /* Introduction */

2011-02-22T11:36:27Z

Introduction

GethinWilliams: moved Numerics to Numerical Errors

2011-02-22T11:30:06Z

moved Numerics to Numerical Errors

← Older revision		Revision as of 12:21, 22 February 2011
Line 72:		Line 72:

	=Total Error=		=Total Error=
		+
		+	For an iterative scheme, the truncation error per step is not the whole story, An estimate for <math>y^j</math> will inevitably depend upon the truncation errors accumulated over any previous steps. For the Euler method above, it can be shown that the total solution error due to cumulative truncation errors is <math>O(\Delta t)</math>. Euler's method is hence ''first order''.
		+
		+	Other methods, such as a [http://en.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods Runge-Kutta] approach, may have different error characteristics.

	=Algorithms Matter: A Case of Catastrophic Cancellation=		=Algorithms Matter: A Case of Catastrophic Cancellation=

@@ Line 51: / Line 51: @@
 =Truncation Errors=
-Roundoff errors aren't the only source of approximations in our programs, however.  Consider solving a differential equation using the finite difference method.  In case, it is common to approximate the value of a function using a truncated Taylor series.  Discarding the higher order terms will introduce an error in our estimate of the function's value.
+Roundoff errors aren't the only source of approximation in our programs, however.  Consider solving a differential equation using the finite difference method.  In case, it is common to approximate the value of a function using a ''truncated'' Taylor series.  Discarding the higher order terms will introduce an error in our estimate of the function's value.
-As an example, Euler's method for solving Ordinary Differential Equations ().
+As an example, consider Euler's method for solving the Ordinary Differential Equation:
 =Total Error=

← Older revision		Revision as of 12:05, 22 February 2011
Line 52:		Line 52:

	Roundoff errors aren't the only source of approximations in our programs, however. Consider solving a differential equation using the finite difference method. In case, it is common to approximate the value of a function using a truncated Taylor series. Discarding the higher order terms will introduce an error in our estimate of the function's value.		Roundoff errors aren't the only source of approximations in our programs, however. Consider solving a differential equation using the finite difference method. In case, it is common to approximate the value of a function using a truncated Taylor series. Discarding the higher order terms will introduce an error in our estimate of the function's value.
		+
		+	As an example, Euler's method for solving Ordinary Differential Equations ().

	=Total Error=		=Total Error=

← Older revision		Revision as of 11:56, 22 February 2011
Line 50:		Line 50:

	=Truncation Errors=		=Truncation Errors=
		+
		+	Roundoff errors aren't the only source of approximations in our programs, however. Consider solving a differential equation using the finite difference method. In case, it is common to approximate the value of a function using a truncated Taylor series. Discarding the higher order terms will introduce an error in our estimate of the function's value.

	=Total Error=		=Total Error=

@@ Line 53: / Line 53: @@
 =Total Error=
-=Algorithms Matter=
+=Algorithms Matter: A Case of Catastrophic Cancellation=
 In this example, we're going to compare two iterative routines:

← Older revision		Revision as of 11:45, 22 February 2011
Line 48:		Line 48:

	Run the Fortran program ('''./surprising_f.exe''') for completeness and note that while the tan function may be better behaved, floating-point arithmetic is still not associative, as a rule.		Run the Fortran program ('''./surprising_f.exe''') for completeness and note that while the tan function may be better behaved, floating-point arithmetic is still not associative, as a rule.
		+
		+	=Truncation Errors=
		+
		+	=Total Error=

	=Algorithms Matter=		=Algorithms Matter=

@@ Line 47: / Line 47: @@
 The plain simplicity of these examples, coupled with their jarring results should warn us right away that there are many, many surprises waiting for us in programs involving floating-point numbers.  Forewarned is forearmed.
-Run the Fortran program (./surprising_f.exe) for completeness and note that while the tan function may be better behaved, floating-point arithmetic is still not associative, as a rule.
+Run the Fortran program ('''./surprising_f.exe''') for completeness and note that while the tan function may be better behaved, floating-point arithmetic is still not associative, as a rule.
 =Algorithms Matter=

@@ Line 10: / Line 10: @@
 Given the limited resources available to digital computers they must '''approximate''' the ''real line'' using a finite number of discrete points.  It is this approximation which is the source of many of our surprises.  Given the huge capacity of modern computers, it is easy to forget that this approximation exists.  It's my goal in the sections below, to draw your attention to the areas in which ignoring this approximation will come back to bite you!
-=I didn't expect that!=
+=I didn't expect that!  A tale of surprising Rounding Errors=
 Let's dive into our first example:
@@ Line 26: / Line 26: @@
 </pre>
-This program does some very simple arithmetic and yet we start to see odd things happening already!  For example the trigonometric function '''tan''' can give us hugely different values depending upon whether we give it a single precision- (typically stored using 4 bytes) or a double precision- (8 byte) number.  To be fair <math>\tan(\pi/2)</math> (radians) is undefined, and so it's hard to say what the right output should be.  However, is does highlight that you need to be vigilant when using floating-point numbers and not to expect that your program's behaviour will always be benign.
+This program does some very simple arithmetic and yet we start to see odd things happening already!  For example the trigonometric function '''tan''' can give us hugely different values depending upon whether we give it a single precision- (typically stored using 4 bytes) or a double precision- (8 byte) number.  To be fair <math>\tan(\pi/2)</math> (radians) is undefined, and so it's hard to say what the right output should be.  However, is does highlight that you need to be vigilant when using floating-point numbers and not to expect that your program's behaviour will always be predictable or benign.
 Less dramatic, but perhaps more alarming is the next section of the program.  This time, we take three double-precision numbers, initialise them to some values and then add them together.  So simple, what could go wrong?  Lots! it turns out..
@@ Line 39: / Line 39: @@
 </pre>
-In this part of the program, we clearly see those approximations mentioned in the introduction.  For example, we see that 0.43 is in fact stored as the approximation, 0.42999999999999999334.  Then, when we factor in other approximations made in the intermediate steps of summing up these numbers, we begin to understand that xx + (yy + zz) will indeed give us a different value to (xx + yy) + zz.  Shocking!  We definitely wouldn't want to write a test of the form:
+In this part of the program, we clearly see those approximations mentioned in the introduction.  For example, we see that 0.43 is in fact stored as the approximation, 0.42999999999999999334.  Then, when we accumulate other approximations made in the intermediate steps of the summation, we begin to understand that xx + (yy + zz) will indeed give us a different value to (xx + yy) + zz.  Shocking!  We definitely wouldn't want to write a test of the form:
-<pre>
+<source lang="c">
 if (total == 1.47) ...
-</pre>
+</source>
 The plain simplicity of these examples, coupled with their jarring results should warn us right away that there are many, many surprises waiting for us in programs involving floating-point numbers.  Forewarned is forearmed.
-Run the Fortran program (./surprising_f.exe) for completeness and note that while the tan function may be better behaved, arithmetic is still not associative as a rule.
+Run the Fortran program (./surprising_f.exe) for completeness and note that while the tan function may be better behaved, floating-point arithmetic is still not associative, as a rule.
 =Algorithms Matter=

@@ Line 4: / Line 4: @@
 =Introduction=
-Sooner or later, you're going to want to include '''real''', aka '''floating-point''', numbers in your programs.  Beit for measured quantities, or parameterisations, but integers don't always cut it.  Now this is all fine and as it should be.  A word of warning, however.  Programs containing floating point numbers can do very odd things indeed!  Use them with care.
+Sooner or later, you're going to want to include '''real''', aka '''floating-point''', numbers in your programs.  Beit for measured quantities, or parameterisations, but integers don't always cut it.  This is all fine and as it should be.  A word of warning, however.  Programs containing floating point numbers can do very odd things indeed!  Use them with care.
-At core the reason that unexpected things happen is because you are sat in front of a '''digital''' computer, which is capable to storing and manipulating a '''finite''' number of '''discrete''' entities.  This is contrasted against the '''infinite''' nature of real numbers.  There are an inifinity of real numbers between o and 1, say, or indeed between 0.000001 and 0.0000011.  Also there is no theoretical limit to the number of digits in a decimal fraction.
+A key reason why unexpected things happen is because you are sat in front of a digital computer, which is capable to storing and manipulating a '''finite''' number of discrete entities.  This is contrasted against the '''infinite''' nature of real numbers.  There are an infinity of real numbers between 0 and 1, say, or indeed between 0.000001 and 0.0000011.  Also there is no theoretical limit to the number of digits in a decimal fraction.
-Digital computers must then '''approximate''' real numbers using a finite number of discrete ones, and it is this approximation which is the source of our surprises.  Given the huge capacity of modern computers, it is easy to forget that this approximation.  It's my goal in the sections below, to draw your attention to the areas in which ignoring this approximation will come back to bite you!
+Given the limited resources available to digital computers they must '''approximate''' the ''real line'' using a finite number of discrete points.  It is this approximation which is the source of many of our surprises.  Given the huge capacity of modern computers, it is easy to forget that this approximation exists.  It's my goal in the sections below, to draw your attention to the areas in which ignoring this approximation will come back to bite you!
 =I didn't expect that!=

← Older revision	Revision as of 11:30, 22 February 2011
(No difference)