CSC 180
Notes for Tutorial #12 -- last tutorial !

Monday 2  December  

Wednesday 4 December

===============

 1. A few catastrophic cancellation examples.
 ============================================

In calculus next term, you will learn to use series expansions to 
approximate functions.   For example, you will learn that you can write:

  e^x  = 1 + x + (x^2)/(2!) + (x^3)/(3!) + ... + (x^i)/(i!) + ...

          infinity
       =    sum  (x^i)/(i!) .
            i=0

This series is called the Maclaurin series for f(x) = e^x.
(In these text notes ^ means "to the power". So e^x = e to the power x.)
This Maclaurin series approximation is quite beautiful because it
will converge to e^x for any real value of x.

A C program implementation of this algorithm for computing e^x has
one obvious trouble -- we can't compute to i=infinity!  One solution
to this trouble is to stop summing the series when the partial sums
have converged to some number of decimal places.
                         j
(The jth partial sum is sum  (x^i)/(i!).)
                        i=0

This algorithm works well for *positive* values of x.  But unfortunately,
it is not good for *negative* values of x.  It would produce, for example:

  e^(-30) = -1.5 x 10^(-4)      ( wrong, because e^x > 0 for all x)
and
  e^(-40) = 3.7                 ( wrong, because e^x < 1 for all x < 0)

when you stopped summing the series after the partial sums agree to 8 places.

What went wrong with the algorithm?
===================================

Let's look into this in more detail and attempt to calculate 
e^(-5.5) which is really equal to 0.0040868 ...

Using the Maclaurin series, and 5 decimal digit arithmetic, we get the 
following:  
 (5 decimal digits are chosen to avoid the tedium of too many digits.
  We will consider the series to have converged when the partial sums
  agree to 5 places.)

                terms           partial sums      (it is instructive to line 
                                                   up on the decimal point)
 e^(-5.5) =     1.0000             1.0000
               -5.5000            -4.5000
              +15.125            +10.625
              -27.730            -17.105
              +38.129            +21.024
              -41.942            -20.918
              +38.446            +17.528
              -30.208            -12.680    (note that the terms are now 
                  .                  .       decreasing, which is a necessary
                  .                  .       condition for the series to 
                  .                  .       converge.)

                                 =======
       "converged" partial sum --> 0.0026363   
                           which is not a good approximation to 0.0040868.


Why did the sum give such a poor approximation to the true result?
==================================================================

Observe:  The neglected digits in the calculated term 
            +38.446   
          (which are due to roundoff to 5 places) look like
              0.000xxxxx...   
          (the x's represent some of the neglected digits.)
          The value of the neglected part is almost as large as the final
          exact result (0.0040868...).  They would have made a significant
          contribution to the final result.  But we don't know them since
          we only carry five digits.
  
          In fact, 8 of the terms in the summation are of the form
               XX.XXX
          and our final result is of the form 
                0.00XXXXX. 
          So the four most significant digits in these 8 terms are 
          cancelled out and contribute nothing to the final result!

The cancellation of the significant digits makes the unknown rounded-off
digits relevant to the final result.  We get a lousy final approximation 
because we don't know the lost digits.  For this reason, the cancellation 
of significant digits is called catastrophic.


How to avoid the cancellation?
=============================

Note that your calculator can accurately calculate e^(-5.5), so there must 
be a way to evaluate e^(-5.5) accurately.  What does your calculator do?

First note that e^(-x) = 1 / e^x.

This suggests the following algorithm for evaluating e^(-5.5):

   use the series to calculate e^(5.5).  All of the terms in the
   series will be positive, so there can be no catastrophic cancellation of
   information.  We get:  e^(5.5) = 244.69  

   and then write e^(-5.5) = 1 / 244.69
                           = 0.0040868   which is accurate!

=============================================================================

Another example:

  Sometimes it seems inevitable that you will get a catastrophic
  cancellation, but sometimes you can use ingenuity to avoid it.

example:  
  Consider the problem of evaluating the function  g(x) = 1 - cos(x).

Question: For what values of x would you expect the straightforward 
          evaluation of g(x) to suffer from a cancellation of digits
          due to the use of a finite-precision floating point arithmetic?

Answer:  For any x near 0, +/- 2pi, +/- 4 pi, etc, because then 
         cos(x) is near 1 and the calculation of 1 - cos(x) will involve
         the subtraction of nearly equal numbers and the loss of significant
         digits.

A better algorithm can be derived.  

Recall that cos( 2*theta ) = 1 - 2 sin^2( theta ).

Therefore,  1 - cos( 2*theta ) = 2 sin^2( theta )
and then g(x) = 2 sin^2( theta/2 ),
a formula and algorithm that avoids the loss of significant digits.


=============================================================================

 2. Questions about Assignment Four.
 ===================================

Please ask for questions about Assignment Four and try to answer them.

=============================================================================

End of tutorials for the term -- phew!