Notebook 4

Number Representation and Error Propagation

Acknowledgements

Parts of the material in this section was taken from a number of sources, which are listed below

S. Wolfram.Mathematica 4.0, 
R.D. Skeeler and J.B. Keiper, Elementary numerical computing with Mathematica, McGraw-Hill, Inc.

Introduction

This notebook will give an introduction to number representation and error propagation.

This notebook contains material covering representation of numbers and propagation of errors in computations using Mathematica. The first chapter deals with number representation, and chapter two with error propagation. In the text you will find a number of exercises that will help to understand the material.

Important  instructions  for  all students:
Each notebook  contains several questions that must be handed in. Theses questions are labeled accordingly:

Required: These questions must be done by all students.

Advanced:  These questions are considered to be more difficult and may be assigned by the instructor.

Optional:   These questions are optional  to all students  and will be counted towards   extra  marks.

IV.1 Number Representation

Introduction

In everyday life referring to a number means referring to a decimal number, built up from units (digits) in the range from 0 up to 9. Most computers do not have a decimal look on numbers and rather use a different base for number representation. In particular, the binary number representation with base 2, where units are in the range from 0 up to 1, is widely used in computers.

The problem is that numbers, which can be represented exactly in one number system, are in general not exactly representable in another system. A binary computer cannot represent most decimal numbers exactly. To illustrate this, consider the following example. In a decimal system the output will be 1.0, 0.9, ..., 0.1. But what does a computer make of it? Try it! (Note: make sure you know how to stop an evaluation in Mathematica: use 'Alt ,' or 'Alt .')

x = 1.0;
While [x  !=  0.0,  Print[x]; x = x - 0.1]

The problem in this example is that 0.1, and therefore all intermediate results, could not be represented exactly and the stopping criterion was never satisfied.

The example above can be rewritten such that the stopping criterion can be satisfied. Verify that the code below works as expected.

x  =  10.0;
While [x  !=  0.0,  Print[x / 10];  
      x  =  x  -  1]

As human beings and computers have a different number representation, conversion is required when going from one system to the other.  Results from a calculation by a computer need to be converted from binary or octal representation (nice for a computer) to a decimal representation (nice for a human being). For example

(Subscript[1010.11, 2]) = (2^3) + (2^1) + 
            (2^(-1)) + (2^(-2)) = 8  +  4  +  (1/2) +  (1/4) =  
            10.75 and (Subscript[147.2, 8]) = (8^2) + 
            4 × (8^1) + 7 × (8^0) + 
            2 × (8^(-1)) = 64  +  32  +  7 + (2/8) =  
            103.25.

On the other hand, if one wants to provide input to a computer program, the input first has to be conversed from decimal to the number system of the computer before the data can be processed. A binary computer will make the following conversion when the decimal number 5.2 is fed into it (decimal numbers in magenta)

5.2  = (Subscript[100, 2])+ 1.2
	       = (Subscript[101, 2])+ 0.2
         = (Subscript[101.001, 2])+ 0.075
         = (Subscript[101.0011, 2])+ 0.0125
etc .  ad infinitum

The erroneous expansion of decimal numbers can have a great impact. In the Gulf war of 1991 an Iraqi Scud slipped through the Patriot defence shield and hit an army camp in Dhahran due to an incorrect expansion of the number 0.1!

REQUIRED
IV.1a The Patriot missile defence system kept time in unites of 1/10th of a second. When the fatal Scud that hit Dhahran, was detected, the Patriot clock had been running for 100 hours. How many bits in base 2 are required to represent 100 hours in units of 1/10th of a second?

REQUIRED
IV.1b How many bits are required to represent 1-(2^(-53)) exactly in binary? How many decimal places are required to represent the same number exactly in base 10?

Positional System

The way in which numbers are represented, both in normal life and in a computer, is by combining a sequence of units or digits with the positions at which these units occur in the number. For example, the decimal number 792 means seven hundreds (or ten times ten), nine tens and two units, or 792 = 
        7× (10^2) + 9 × (10^1) + 2× (10^0). This positional system was invented 4000 years ago by the Babylonian who did not use a decimal system as we do, but a hexadecimal with base 60.

The positional system is certainly not the only system. Take for example the Romans who used a completely other way for dealing with numbers. Their system had no such a thing as a base 2 or 10. Instead they used a fixed number of symbols I, V, X, L, C, D and M, for 1, 5, 10, 50, 100, 500 and 1000 respectively and numbers were formed by a sequence of symbols in decreasing order of magnitude. (Note: when too many instances of a symbol would be needed, the order would change such that lower value symbols would precede higher value symbols.) So, the number 68 would have been written by the Romans as LXVIII.

The positional system is determined by the choice for the base or radix β, a positive integer number, and the 'digits' {0,  
        1,  ⋯,  β  -  1}. Besides the well-known decimal system with base 10 the following systems are familiar in computer environments

Integer Number Representation

An arbitrary integer number g will have the following form in a positional system with base β

g  =  σ (Subscript[a, t - 1]) (Subscript[a, t - 
                2]) ⋯ (Subscript[a, 2]) (Subscript[a, 1]) (Subscript[a, 0]),

where σ is the sign that can be ±1, and each of the t digits is in the range from 0 to β - 1. If we define \(TraditionalForm\`g\_β = ∑\+\(i = 0\)\%\(t - 1\)\(a\_i\) β\^i\),  the value of g is given by

\(TraditionalForm\`g = \(σ\ g\_β = σ \(∑\+\(i = 0\)\%\(t - 1\)\(a\_i\) β\^i\)\)\).

The decimal number -(Subscript[235, 10]) has according to this notation the value:

-(5×(10^0) +  3 ×(10^1)  +  
              2 ×(10^2))  =  -235.

Fractional Number Representation

The above-described representation for integer numbers can be modified to include fractional numbers. An arbitrary fractional number f will have the following form in a positional system with base β

f  =  σ .  
            (Subscript[a, 1])  (Subscript[a, 2]) ⋯  (Subscript[a, t - 1]) (Subscript[a, t]),

where the sign σ (±1) is followed by a point, and each of the t digits is in the range from 0 to β - 1. If we define (Subscript[f, β]) = (∑_(i = 1)^t) 
                (Subscript[a, i]) (β^(-i)),  the value of f is given by

\(TraditionalForm\`f = \(σ\ f\_β = σ \(∑\+\(i = 1\)\%t\( a\_i\) β\^\(-i\)\)\)\).

In this notation the decimal number - .(Subscript[41, 10]) has the value - (4 ×(10^(-1))  +  
              1×(10^(-2)))  = -0.41. Similarly, the binary number  .(Subscript[1101, 2]) has the value 1 ×(2^(-1)) +  
          1 × (2^(-2))  + 
          1 ×(2^(-4))=(1/2) +  (1/4)  +  
            (1/16) =  0.8125.

Notice the use of the dot notation that is common to the Anglo-Saxon world, whereas the rest of the world uses a comma to denote fractional numbers.

Floating Point Number Representation

Fractional number representation becomes awkward as soon as the numbers become very large or small. The floating point number representation introduces an exponent part that is adequate especially when dealing with large or small numbers. The general form for the floating point representation of a number x  ≠  0 is

x  =  σ m (β^e),

where σ is the by now well-known sign, m is the mantissa with (β^(-1)) ≤  m  <  1, and e is the exponent which can be a positive or negative integer number. In the special case where x  =  0 the mantissa is zero, but the value of the exponent is undefined and is system dependent. In the floating point notation the decimal number -0.000001234 would be written as - .1234 (10^(-5)).

Finite Number Representation

A computer does not have an infinite length for the mantissa or exponent. Instead it uses a fixed length for both the mantissa and the exponent. This implies that the numbers that can be represented by a computer are bounded by a maximum (and of course a minimum). The largest possible value for the exponent is denoted by (Subscript[e, max]) and the smallest (negative) value for the exponent is denoted by (Subscript[e, min]). All numbers represented by a computer thus lie in a fixed range, mainly depending on (Subscript[e, min]) and (Subscript[e, max]).

The fixed length of the mantissa imposes a restriction on the accuracy with which numbers can be represented.

By selecting a combination of a particular β, mantissa length t, the minimum value for the exponent (Subscript[e, min]) and the maximum value for the exponent (Subscript[e, max]), the numbers that can be represented are completely determined. A finite floating point number system is dependent on this combination and is denoted as \(ℝ\&^\)(β, t, (Subscript[e, min]), (Subscript[e, max])).

To enforce unambiguous representation of floating point numbers we use normalised floating point numbers, where the mantissa starts with a non-zero digit for floating point numbers not equal to zero.

As an example all normalised numbers in the floating point system \(TraditionalForm\`\(ℝ\&^\)(10, \ 3, \ \(-4\), \ 
        5)\) are listed, and also the total of the numbers that can be represented in this system.

({{ .(Subscript[999, (10^5)]),  .(Subscript[998, (10^5)]),  .(Subscript[997, (10^5)]), ⋯,  .(Subscript[100, (10^5)])}, { .(Subscript[999, (10^4)]),  .(Subscript[998, (10^4)]),  .(Subscript[997, (10^4)]), ⋯,  .(Subscript[100, (10^4)])}, {⋮, ⋮, ⋮, ⋮, ⋮}, { .(Subscript[999, (10^1)]),  .(Subscript[998, (10^1)]),  .(Subscript[997, (10^1)]), ⋯,  .(Subscript[100, (10^1)])}, { .(Subscript[999, (10^0)]),  .(Subscript[998, (10^0)]),  .(Subscript[997, (10^0)]), ⋯,  .(Subscript[100, (10^0)])}, { .(Subscript[999, (10^(-1))]),  .(Subscript[998, (10^(-1))]), \( .997\_\(10\^\(-1\)\)\), ⋯,  .(Subscript[100, (10^(-1))])}, {⋮, ⋮, ⋮, ⋮, ⋮}, { .(Subscript[999, (10^(-4))]),  .(Subscript[998, (10^(-4))]), \( .997\_\(10\^\(-4\)\)\), ⋯,  .(Subscript[100, (10^(-4))])}, {0,  ,  ,  ,  }, {- .(Subscript[100, (10^(-4))]), - .(Subscript[101, (10^(-4))]), \(- .102\_\(10\^\(-4\)\)\), ⋯, - .(Subscript[999, (10^(-4))])}, {⋮, ⋮, ⋮, ⋮, ⋮}, {- .(Subscript[100, (10^5)]), - .(Subscript[101, (10^5)]), \(- .102\_\(10\^5\)\), ⋯, - .(Subscript[999, (10^5)])}})

Each row contains 900 numbers. Looking at the positive numbers there are five rows with a positive exponent, four rows with a negative exponent and one row with exponent zero. This gives ten rows for the positive numbers.  This is also true for the negative numbers, giving a total of twenty rows with 900 elements each. Finally there is a row containing only the number zero. The total numbers to be represented in this system is therefore 20 × 900  +  1  =  18 001. The largest number that can be represented in this system is  .999 (10^5) and the smallest number is - .999 (10^5). The smallest positive number is given by  .1 (10^(-4)) =  (10^(-5)).

The largest number that can be represented in a floating point number system \(ℝ\&^\)(β, t, (Subscript[e, min]), (Subscript[e, max])) is called maxreal or overflow threshold or giant and its value is given by maxreal = (1  -  (β^(-t))) × (β^(Subscript[e, max])).

The smallest positive number that can be represented in a floating point number system \(ℝ\&^\)(β, t, (Subscript[e, min]), (Subscript[e, max])) is called minreal or underflow threshold or dwarf and its value is given by minreal =(β^(((Subscript[e, min])-1))).

All representable numbers in a system \(ℝ\&^\)(β, t, (Subscript[e, min]), (Subscript[e, max])) are called the machine numbers. For any machine number u other than the giant, there exists a smallest larger machine number \(TraditionalForm\`\(u\^+\)\), called the upper neighbour. Also, for any machine number u other than the dwarf, there exists a largest smaller machine number \(TraditionalForm\`\(u\^-\)\), called the lower neighbour.

The relative dispersion is defined for any non-zero machine number other than the giant as

\(TraditionalForm\`ρ\  := \(\(|\)\(\(\(\(u\^+\) - \ u\)\/u\)\(|\)\)\)\).

For u  =  m × (β^e), i.e. with mantissa m and exponent e, the relative dispersion can be expressed as

ρ := ((β^(-t))/m),

with (β^(-1)) ≤ m  <  1.

From this an interval for the relative dispersion can be derived:

(β^(-t))<ρ ≤(β^(1 - t)).

The maximum value for the relative dispersion is called the machine precision or the system resolution and is usually denoted with η. It can be shown that the following equality holds

\(TraditionalForm\`η\( = \&\(p . 
              d . \)\)\(max\+u\(\(|\)\(\(\(\(u\^+\) - 
                      u\)\/u\)\(|\)\)\)\  = β\^\(1 - t\)\)\).

If we take the same floating point system as in the previous example the relative dispersion is given by \(TraditionalForm\`\(\(ρ\)\(\ \)\(=\)\(\(\(|\)\(\(\(\(u\^+\) - \ 
                    u\)\/u\)\(|\)\)\)\(\ \)\(=\)\)\(\ \)\)\)((β^(-1))/m)  = ((10^(-1))/m), with (10^(-1))  ≤  m  <  1. 
The machine precision (or equivalent: maximal dispersion) in this system is given by  \(TraditionalForm\`η\  = \(β\^\(1 - t\)\  = \(10\^\(1 - 3\)\  = \ 10\^\(-2\)\)\)\).

A real number x in the range of the machine numbers, i.e. x  =  0 or dwarf ≤ |x| ≤ giant, will be approximated in a computer by a machine number u. This machine number u will be chosen such that in a way it approximates x best among all machine numbers. The notation for this is u  =  fl(x). In a system using rounding fl(x) will be the machine number closest to x (and closer to zero in case x lies exactly between two machine numbers). For a system with truncation fl(x) will be the largest machine number less or equal to x for positive numbers, while for negative numbers the equivalence fl(x)  =  -fl(-x) is used.

The unknown ϵ is called the representation error.

For example, take the system \(TraditionalForm\`ℝ\&^\)(2, 3, -1, 2). The machine precision in this system is given by \(TraditionalForm\`η\  = \(β\^\(1 - t\)\  = \ \(2\^\(1 - 3\)\  = \ 1\/4\)\)\). The representation error is then given by \(TraditionalForm\`\(\(|\)\(\ \)\(ϵ\)\(|\)\(\(≤\)\(1\/8\)\)\)\) in case of rounding and \(TraditionalForm\`\(\(|\)\(\ \)\(ϵ\)\(|\)\(\(≤\)\(1\/4\)\)\)\) in case of truncation.

\(TextForm\`In\ the\ table\ below\ all\ machine\ numbers\ are\ given\ for\ a  normalised\ mantissa\)

({{, mantissa, ±(1/2), ±(5/8), ±(3/4), ±(7/8)}, {exponent, , , , , }, {-1, , ±(1/4), ±(5/16), \(±\(3\/8\)\), ±(7/16)}, {0, , ±(1/2), ±(5/8), \(±\(3\/4\)\), ±(7/8)}, {1, , ±1, ±(5/4), ±(3/2), ±(7/4)}, {2, , ±2, ±(5/2), ±3, ±(7/2)}})

REQUIRED
IV.1c What other numbers can be represented if we drop the restriction of a normalised mantissa?

The numbers in the floating point system can also be drawn graphically. In the picture below the numbers are depicted on a one-dimensional axis.

REQUIRED 
IV.1d 
a) Use the function Table[] to  form a list  of all the positive  normalized  machine numbers on a three-didgit, base 4 computer, that has exponents in the range -2 to 2, inlcuding 0 and sign bits. 
b) How many numbers are there in the list?
c) What are the smallest  and largest numbers on the list?
d) ListPLot the Log of the Sorted, Flattened list of numbers. Why do the points tend to lie in a straight line?
e) Why is the line scalloped? (hightly  irregular) 
f) Would  the scallops be more or less pronounced in base 16?
 (You might want to use the function  BaseForm[])

Machine Arithmetic and Errors

The arithmetic operators +, -, × and / all have a machine implementation denoted by \(TraditionalForm\`+\&^\), \(TraditionalForm\`-\&^\), \(TraditionalForm\`\(×\&^\)\) and \(TraditionalForm\`\(/\&^\)\) respectively. For any two machine numbers \(TraditionalForm\`u, v\  ∈ \ ℝ\&^\) the relation between these operators and their machine counterparts is given by

({{u \(+\&^\) v, =, (u + v)(1 + (Subscript[ε, 1])) , \(\(with\  | \(ε\_1 | \(\(≤\)\(\ \)\(η\)\)\)\)\(,\)\)}, {u \(-\&^\) v, =, (u - v)(1 + (Subscript[ε, 2])), \(\(with\  | \(ε\_2 | \(\(≤\)\(\ \)\(η\)\)\)\)\(,\)\)}, {u \(×\&^\) v, =, (u × v)(1 + (Subscript[ε, 3])), \(\(with\  | \(ε\_3 | \(\(≤\)\(\ \)\(η\)\)\)\)\(,\)\)}, {u \(/\&^\) v, =, (u / v)(1 + (Subscript[ε, 4])), \(with\  | \(ε\_4 | \(\(≤\)\(\ \)\(\(η\)\(.\)\)\)\)\)}})

More generally:

\(TraditionalForm\`u\ \(\(\(ω\)\(\ \)\)\&^\) 
          v\  = \((u\ ω\ v)\)\ \((1\  + \ ε)\), 
      for\  | \(ε | \(\(≤\)\(\ \)\(η\)\)\), ω\  ∈ \ {\(+\(\(,\)\(\ \)\(-\(\(,\)\(\ \)\(\(×\)\(\(,\)\(\ \)\(/\)\)\)\)\)\)\)}\ and\ u, 
      v\  ∈ \ ℝ\&\(\(^\)\(\ \)\)\).

Note: instead of the ^ notation to emphasize the finite precision of the calculation there is another notation for this purpose: fl (). Thus u \(+\&^\) v is equivalent to fl(u + v).

For example consider the floating point system \(TraditionalForm\`\(\(\(ℝ\&^\)\((\)\(\(10\)\(,\)\(3\)\(,\)\(\ \)\(\(*\)\(,\)\)\(\ \)\)\)\(*)\)\)\), where the minimum and maximum values for the exponent may be anything, since these are not relevant in this example. The machine precision for this system is given by η  =  (β^(1 - t))  =  
          (10^(-3)). Further, take \(TraditionalForm\`u\  = \ \( .3536\ \ 10\^\(-1\)\ and\ v\  = \  .2646\ \ 10\^0\)\). What is u \(×\&^\) v?

In exact arithmetic:
 \(TraditionalForm\`u\ ×\ 
          v\  = \( .09356256\ \ 10\^\(-1\)\  = \  .9356256\ \ 10\^\(-2\)\)\) 
For the floating point system with a four digits mantissa this gives u \(×\&^\) v = .9356  (10^(-2)). The absolute error due to round-off in this case is  .3  (10^(-6)), whereas the relative error is  .3  (10^(-4)).

The big question now is what the 'computer result' will be of an operation x ω y , where x and y are real numbers. In general the numbers x and y will not be machine numbers, so there will be an error in representing these numbers. Moreover, as we have seen above, also the operations will introduce errors due to limited mantissa length. It appears that a distinction has to be made between the operators × and / on the one hand, and + and - on the other hand when we want to compute |\(x\&^\) \(ω\&^\) \(y\&^\) - x ω y| .

Absolute error for × and /

In the following the error in the computation with the × operator is discussed. By replacing the × operator by the / operator the error in the division operation is derived. If the relative errors in representing x and y are given by (Subscript[ε, 1]) and (Subscript[ε, 2]) respectively, the machine numbers \(TraditionalForm\`x\&^\) and \(TraditionalForm\`y\&^\) are given by \(TraditionalForm\`x\&^\  = \ x\ \((1\  + ε\_1)\)\) and \(TraditionalForm\`y\&^\  = \ y\ \((1\  + ε\_2)\)\). For \(x\&^\) \(×\&^\) \(y\&^\) we then find

\(x\&^\) \(×\&^\) \(y\&^\) = \(\((x\&^\ ×\ 
                  y\&^)\)\ \((1\  + \ ε\_3)\) = \ \((x\ \((1\  + \ ε\_1)\)\ ×\ \ \(y(
                    1\  + \ ε\_2)\))\) \((1\  + \ ε\_3)\)\),

for some  (Subscript[ε, 3]) in the order of the machine precision. From this it follows that

|\(x\&^\) \(×\&^\) \(y\&^\) - x × y | =\(\(\(|\)\(\(\((x\ \((1\  + \ ε\_1)\)\ ×\ \ \(y(
                      1\  + \ ε\_2)\))\) \((1\  + \ ε\_3)\)\  - \ x\ ×\ y\)\(|\)\)\)

        				\(\(=\)\(\(\(|\)\(x\ ×\ 
                  y\ \ \((1\  + \ ε\_1)\)\ \((1\  + \ ε\_2)\)\ \((1\  + \ ε\_3)\)\  - \ \ x\ ×\ 
                  y\)\(|\)\(
\)\(	\)\(\(\((1)\)\(	\)\(≤\)\)\  | \(\(x\ ×\ 
                      y\ \ \((1\  + \ ε)\)\^3\  - \ \ x\ ×\ 
                      y\)\(|\)\)\)\)\ \  = \(\(|\)\(x\ ×\ 
                y\ \((1 + 3\ ε\  + \ 
                    3\ ε\^2\  + ε\^3)\)\)\(|\)\(\ \)\(
\)\(	\)\(\((2)\)	 ≤ \ 
                3.03\ ε\)\(|\)\(x\ ×\ 
                y\)\(|\)\(\(≤\)\(\ \)\(3.03  η\)\)\(|\)\(x\ ×\ 
                y\)\(|\)\(.\)\)\)\)\)

In this derivation we have assumed (1) \(TraditionalForm\`ε\  = 
        max {ε\_1, \ ε\_2, ε\_3}\) and ignored (2) the higher order terms in ε (see Wikinson in:IMA Bull. 22 (11/12) p.192-200, 1986). The relative error for the multiplication easily follows from the result

|((\(x\&^\) \(×\&^\) \(y\&^\) - x × y)/(x × 
                  y))| ≤ \(\(\(\ \)\(3  η\  | \(\(x\ ×\ 
                        y\)\(|\)\)\)\)\/\(\(|\)\(\(x\ ×\ y\)\(|\)\)\)\) = 3 η.

Absolute error for + and -

The error bounds for the + and - operators are less severe than for the × and / operators. Like in the previous subsection we will only discuss the error bound for one of the operators, the + operator. The error bound for the subtraction can be derived in a similar way. Again, let the relative errors in representing x and y be given by (Subscript[ε, 1]) and (Subscript[ε, 2]) respectively. The machine numbers \(TraditionalForm\`x\&^\) and \(TraditionalForm\`y\&^\) are given by \(TraditionalForm\`x\&^\  = \ x\ \((1\  + ε\_1)\)\) and \(TraditionalForm\`y\&^\  = \ y\ \((1\  + ε\_2)\)\). For \(x\&^\) \(+\&^\) \(y\&^\) we then find

\(x\&^\) \(+\&^\) \(y\&^\) = \(\((x\&^\  + \ 
                  y\&^)\)\ \((1\  + \ ε\_3)\)\  = \((x\ \((1\  + \ ε\_1)\)\  + \ 
                  y\ \((1\  + \ ε\_2)\))\) \((1\  + \ ε\_3)\)\),

for some  (Subscript[ε, 3]) in the order of the machine precision. From this it follows that

|(\(x\&^\) \(+\&^\) \(y\&^\)) - (x  +  y)| =\(\(\(|\)\(\((x\ \((1\  + \ ε\_1)\)\  + \ 
                  y\ \((1\  + \ ε\_2)\))\) \((1\  + \ ε\_3)\)\  - \ \((x\  + \ y)\)\)\(|\)\)

        				\(\(=\)\(\(\(|\)\(\((x\ \((1\  + \ ε\_1)\) \((1\  + \ ε\_3)\)\  + 
                    y\ \ \((1\  + \ ε\_2)\)\ \((1\  + \ ε\_3)\)\ )\) - \ \((x\  + \ 
                    y)\)\)\(|\)\(
\)\(	\)\(\(\((1)\)\(	\)\(≤\)\)\  | \(\(\((x\ \ \((1\  + \ ε)\)\^2 + 
                        y\ \ \((1\  + \ ε)\)\^2)\)\ \  - \((x\  + \ y)\)\)\(|\)\)\)\)\ \  = \(\(|\)\(\((x\  + \ 
                    y)\)\ \((2\ ε\  + ε\^2)\)\)\(|\)\(\ \)\(
\)\(	\)\(\((2)\)	 ≤ \ 
                  2\ ε | \(x\  + \ 
                    y | \(\(≤\)\(\ \)\(2\ \(ε(\(|\)\(x\)\(\ \)\(|\)\(+\(\(|\)\(\(y\)\(|\)\)\)\)\ )\)\)\) ≤ 
                    2 \(\( η(\(|\)\(x\)\(\ \)\(|\)\(+\ \(\(|\)\(\(y\)\(|\)\)\)\)\ )\)\(.\)\)\)\)\)\)\)\)

In this derivation it has been assumed (1) \(TraditionalForm\`ε\  = 
        max {ε\_1, \ ε\_2, ε\_3}\) and ignored (2) the higher order terms in ε. The relative error for the addition easily follows from the result

|((\((x\&^\ \(+\&^\ y\&^\))\) - (x  +  y))/(x  +  y))| \(\(≤\)\(2\ η\ \ \(\(\ \)\(\(|\)\(x\)\(|\)\(+\ \(\(|\)\(\(y\)\(|\)\)\)\)\)\)\/\(\(|\)\(\(x\  + \ y\)\(|\)\)\)\)\).

The above implies that for addition and subtraction the absolute error in the result is proportional to the sum of the absolute values of the operands. Adding two operands with the same sign or subtracting operands with opposite sign also gives a small relative error compared to the exact result. But it can be seen immediately that when adding two operands with opposite sign or subtracting operands with equal sign the relative error may explode due to cancellation of numbers.

ADVANCED
IV.1e Take the floating point system \(TraditionalForm\`\(\(\(ℝ\&^\)\((\)\(\(10\)\(,\)\(\ \)\(4\)\(,\)\(\ \)\(\(*\)\(,\)\)\(\ \)\)\)\(*)\)\)\). The machine precision is η  =  (10^(-3)). If x  =   .10046 and y  =   .99634  (10^(-1)) what is x  -  y? What is the absolute error? What is the relative error? Use machine implementation of  "-" with arguments having the same exponent.

IV.2 Error Propagation

In the previous section it was shown that errors are inherent to numerical calculations. Unlike symbolic calculations, where the focus is on symbol manipulation, errors play an important role in numerical calculations. Errors may come from several sources:

Modelling errors occur when assumptions on the model are not correct. For example, a classical approach is taken in a situation where a quantum approach is required, or a viscous component is left out of consideration.
Data errors occur due to inaccuracies in the input data. The input data can be the result of (inaccurate) measurements or be the result of previous calculations.
Computational errors occur due to inaccuracies in the computational procedure.  Round-off due to finite precision is an example of a computational error. Other examples are truncation in which an infinite process is approximated by a finite process, like \(TraditionalForm\`e\^x\  ≈ \ ∑\+\(n = 0\)\%100 x\^n\/\(n!\)\) or (f^′)(
          a)  ≈ ((f(a  +  h)  -  f(a))/(2 h)). Also, bugs in the software or hardware errors fall in this category, but these will not be discussed here further.

The type of error that is of most interest to us is the last category: the computational error. This type of error is a necessary evil, responsible for almost never resulting in the exact answer. On the other hand, a high accuracy is feasible when desired, albeit at the expense of a large computational effort. In the previous section the definition was given for the absolute error as the difference of the exact value minus the approximated value, and for the relative error as the quotient of the absolute error and the exact value. From these definitions it follows immediately that the approximated value \(TraditionalForm\`x\&~\) of an exact value x can be written as \(TraditionalForm\`\(\(x\)\(\ \)\)\&~ = \ 
        x\ \((1\  + ε)\)\), where ε is the relative error.
It is important to distinguish data errors from computational errors. Let a be some exact value, \(TraditionalForm\`a\&~\) its machine representation (value with data error) and let f(x) be some computational procedure, which maps an input value to an output value. While f(a) would be the desired output value, the best result that can be obtained is \(TraditionalForm\`f(a\&~)\). This is caused by data errors. The propagated data error is defined as

propagated data error= \(f(a\&~)\  - \ f(a)\).

Just as the input value a could not be represented exactly, the output value will suffer the same problem. Thus, even if the input value is exact, say x, the output value will in general not be f(x) but \(TraditionalForm\`\(f\&^\)(x)\). Instead of ending up with the result f(a) for the input value a, the final result will be \(TraditionalForm\`\(f\&^\)(a\&~)\).
The accumulated absolute error now becomes

\(TraditionalForm\`\(\(|\)\(\(\(f\&^\)(a\&~)\  - \ 
              f(a)\)\(|\)\)\)\  = \(\(|\)\(\(f\&^\)(a\&~)\  - \ f(a\&~)\  + \ f(a\&~)\  - 
            f(a)\)\(|\)\(\(≤\)\(\(|\)\(\(f\&^\)(a\&~)\  - \ 
                f(a\&~)\)\(|\)\(\ \)\(+\ \(\(|\)\(f(a\&~)\  - \ 
                    f(a)\)\(|\)\(\ \)\)\)\)\)\)\).

The first term on the right hand side is called the computational error (computational error =\(\(f\&^\)(a\&~)\  - \ f(a\&~)\)). This type of error depends on the implementation. The second term on the right hand side is the propagated data error that depends on the condition of the problem. The condition will be discussed later in this section.
The relation between these errors is shown in the picture below. The picture shows both the exact curve f(x) and the curve \(TraditionalForm\`\(f\&^\)(x)\) of computed values. The green dot indicates the intended (exact) function value, but due to different types of errors the result obtained is the one indicated by the red dot.

Conditioning

Even when calculations are performed exactly, there are situations for which it can be difficult or impossible to obtain a correct answer. Chaotic systems are extremely sensitive to small changes in the start conditions. A well-known example of such a system is weather forecasting. The chaotic nature of the system imposes a limit on the period at which the weather can be forecasted with some degree of confidentiality (this period is about 15 days!).
The sensitivity of a system to changes in the start conditions is expressed in terms of the condition number, which is defined as

sensitivity := condition number := \(\(\(|\)\(\(relative\ error\ in\ result\)\(|\)\)\)\/\(\(|\)\(\(relative\ error\ in\ data\)\(|\)\)\)\).

The condition number determines whether a system is sensitive to changes in the start conditions. A large condition number makes a system ill-conditioned and sensitive to small changes. A small condition number on the other hand defines a well-conditioned system where the system behaves well to small changes.

Condition number of linear functions

Assume that the approximated result for f(a) follows from using the approximated value of a, for some linear function f. (Whenever f is not a linear function take the first order Taylor expansion.) It was shown in the previous section that for any number the computed or approximated value can be written as

approximated value  = 
        exact value × (1  +  relative error).

Applying this to f(a) gives

\(TraditionalForm\`f\&~\ \((a)\)\  = \(f(
            a)\)\ \((1\  + \ ε\_\(f(a)\))\)\), 			(1)

where \(TraditionalForm\`\(f\&~\)(a)\) is the approximated value to f(a). The assumption that \(TraditionalForm\`\(f\&~\)(a)\) follows from the approximated value for a can be written as

\(TraditionalForm\`f\&~\ \((a)\)\  = \ 
        f(a\ \((1\  + \ ε\_a)\))\). 			(2)

Combining (1) and (2) leads to

({{ , f(a) (1  +  (Subscript[ε, f(a)])), =, f(a (1  +  (Subscript[ε, a]))) }, {=>,  f(
                    a) (Subscript[ε, f(a) ]), =, f(a +  a (Subscript[ε, a]))  -  f(a)}, {=>, \(ε\_\(f(a)\)\/ε\_a\), =, (( f(a +  a (Subscript[ε, a]))  - 
                      f(a))/(f(
                        a) (Subscript[ε, a]).))}})  (3)

The fraction \(TraditionalForm\`ε\_\(f(a)\)\ /\ ε\_a\) is a measure for the sensitivity of this system. If the derivative of f(x) exists in a the following is true

\(TraditionalForm\`lim\+\(ε\_a → 0\)\(f(a + \ a\ ε\_a)\  - \ f(a)\)\/\(a  ε\_a\) = \ \(f\^′\)(a)\).

Together with (3) this gives

\(TraditionalForm\`ε\_\(f(a)\)\/ε\_a → a\ \(\(f\^′\)(a)\)\/\(f(a)\)\),

as (Subscript[ε, a]) → 0. This result gives us a measure for the relative sensitivity of f(a) for small variations in a. By taking the absolute value the condition number of f(x) for x  =  a is obtained:

\(TraditionalForm\`\(\(|\)\(\(ε\_\(f(a)\)\/ε\_a\)\(|\)\)\)\).

Take for example the function f(x)  =  (e^x). The relative derivative is given by \(TraditionalForm\`x\ \(\(f\^′\)(x)\)\/\(f(x)\)\  = \(x\ e\^x\/e\^x\  = \ x\)\). The condition number is therefore \(TraditionalForm\`\(\(|\)\(\(x\)\(|\)\)\)\). This implies that for  x  ≫  1 the function is sensitive to small changes in its arguments. For x  ≪  1, on the other hand, small variations in the arguments will have only small effects.

REQUIRED
IV.2a Give the condition number for an argument x for the function f(x)  =  ln (x). Also discuss when the function is sensitive to small changes in its arguments.