Introductory lecture

Numerical methods

Lectures: Doc. Mgr. Jozef Kristek, PhD. F1-207

Exercises: Mgr. David Gregor F1-204
 Introductory lecture

Contents

1. Introduction, syllabus, evaluation

2. Source and types of errors
3. Definition of errors
4. Rounding, propagation of errors
5. Representation of numbers
6. Conditionality of numerical problems and
numerical stability of algorithms
 Introduction

real problem –> mathematical model

mathematical model - solved using computers

Numerical mathematics is a scientific discipline,

which develop and analyze methods
based on manipulations with numbers
 Introduction

Numerical problem

clear and unambiguous description

of functional relation
between the finite number
of input and output data

Algorithm of the numerical problem

clear and unambiguous specification

of finite sequence of operations.
The operations uniquely assign
n-tuple numbers of results
to the m-tuple numbers
from certain set of input data

Pre- a post-processing
 Introductory lecture

Contents

1. Introduction, syllabus, evaluation

2. Source and types of errors
3. Definition of errors
4. Rounding, propagation of errors
5. Representation of numbers
6. Conditionality of numerical problems and
numerical stability of algorithms
 Source and types of errors

Human errors

Errors of mathematical model

difference between solution
of mathematical (idealized) problem
and
solution of real problem

Example: Estimation of the surface of the Earth

using equation S= 4 π r 2

Errors of input data

due to inaccuracy of measurements
 Source and types of errors

Errors of numerical method

comes from taking a numerical problem
instead of mathematical problem
The estimation of this error
is necessary part of solution of numerical problem
 Source and types of errors

Errors of numerical method

comes from taking a numerical problem
instead of mathematical problem
The estimation of this error
is necessary part of solution of numerical problem

Example: Computation of the value of sin x for x=1 using

the summation of the finite number of terms
in Taylor expansion

2 n1
x 3 x5 x 7 x9 x
sin x  x      1 
n
3! 5! 7! 9! 2n  1!
 Source and types of errors

Errors of numerical method

comes from taking a numerical problem
instead of mathematical problem
The estimation of this error
is necessary part of solution of numerical problem

Example: Computation of the value of sin x for x=1 using

the summation of the finite number of terms
in Taylor expansion

2 n1
x 3 x5 x 7 x9 x
sin x  x      1 
n
3! 5! 7! 9! 2n  1!

We know that summation of the first n terms of expansion

gives the error in estimation at most
1/ 2n  1!
 Source and types of errors

Round-off errors
Round-off errors can cumulate but also cancel

Example: The number π, result of 2/3

 Source and types of errors

Round-off errors
Round-off errors can cumulate but also cancel

Example: The number π, result of 2/3

real problem – all kind of errors together


 Introductory lecture

Contents

1. Introduction, syllabus, evaluation

2. Source and types of errors
3. Definition of errors
4. Rounding, propagation of errors
5. Representation of numbers
6. Conditionality of numerical problems and
numerical stability of algorithms
 Definition of errors

Let x is the exact value of some number

and x is its approximation
  x  x  x
we call absolute error of approximation
 Definition of errors

Let x is the exact value of some number

and x is its approximation
  x  x  x
we call absolute error of approximation

Relative error
  x  x  x

x x
 Definition of errors

Estimation of errors

Each non-negative number  , for which

  x  
i.e.
x    x  x  
we call estimation of absolute error
 Definition of errors

Estimation of errors

Each non-negative number  , for which

  x  
i.e.
x    x  x  
we call estimation of absolute error

Each non-negative number  , for which

  x

x
we call estimation of relative error
 Definition of errors

Estimation of errors

Each non-negative number  , for which

  x  
i.e.
x    x  x  
we call estimation of absolute error

Each non-negative number  , for which

  x

x
we call estimation of relative error

Usually we write
x  x   x  x 1   
 Definition of errors

Now evaluate an error

of valuef  x1, x2 ,..., xn  of function f ,
if exact values xi
will be changed by approximate values x i  xi  xi .
 Definition of errors

Now evaluate an error

of valuef  x1, x2 ,..., xn  of function f ,
if exact values xi
will be changed by approximate values x i  xi  xi .

n
f  x  1 n  2 f x 
f  x  f  x    xi   xi x j  .
i1 xi 2 i , j1 xi x j
 Definition of errors

Now evaluate an error

of valuef  x1, x2 ,..., xn  of function f ,
if exact values xi
will be changed by approximate values x i  xi  xi .

n
f  x  1 n  2 f x 
f  x  f  x    xi   xi x j  .
i1 xi 2 i , j1 xi x j

Assuming that xi x j are small

 Definition of errors

Now evaluate an error

of valuef  x1, x2 ,..., xn  of function f ,
if exact values xi
will be changed by approximate values x i  xi  xi .

n f  x 
f  x  f  x    xi
i1 xi

Assuming that xi x j are small

 Definition of errors

Now evaluate an error

of valuef  x1, x2 ,..., xn  of function f ,
if exact values xi
will be changed by approximate values x i  xi  xi .

n f  x 
f  x  f  x    xi
i1 xi

Assuming that xi x j are small, we can define absolute error as

f  x 
n
f  x  : f  x   f  x    xi
i1 xi
 Definition of errors

Now evaluate an error

of valuef  x1, x2 ,..., xn  of function f ,
if exact values xi
will be changed by approximate values x i  xi  xi .

n f  x 
f  x  f  x    xi
i1 xi

Assuming that xi x j are small, we can define absolute error as

f  x 
n n
f  x 
f  x  : f  x   f  x    xi    xi (1)
i1 xi  i1 xi
 Definition of errors

And for relative error

f  x  n
xi f  x  xi
f x
  f  x  xi xi
i1
 Definition of errors

And for relative error

f  x  n
xi f  x  xi n
xi f  x  xi
f x 
  f  x  xi xi 
  f  x  xi

xi
. (2)
i1 i1

In practice the function values and values of derivatives

are evaluated at x.
Error of basic arithmetic operations

Let f  x, y   x  y.
 Error of basic arithmetic operations

Let f  x, y   x  y.
Using eqs. (1) and (2) we obtain
absolute and relative error of addition and subtraction

  x  y x x y y
  x  y   x  y  
x y x y x x y y
 Error of basic arithmetic operations

Let f  x, y   x  y.
Using eqs. (1) and (2) we obtain
absolute and relative error of addition and subtraction

  x  y x x y y
  x  y   x  y  
x y x y x x y y

Relative error of addition or subtraction could be significantly larger

then relative errors of each operand in case when
x y is significantly smaller than x or y .
 Error of basic arithmetic operations

Let f  x, y   xy .
Then absolute and relative error of multiplication

  xy  x y
  xy   y x  x y  
xy x y

Let f  x, y   x / y.
Then absolute and relative error of division

 x 1
  x   x / y x y
    x  2 y  
 y  y y x/ y x y
 Introductory lecture

Contents

1. Introduction, syllabus, evaluation

2. Source and types of errors
3. Definition of errors
4. Rounding, propagation of errors
5. Representation of numbers
6. Conditionality of numerical problems and
numerical stability of algorithms
 Rounding

Let x is approximation of x written in decimal representation

x    d1 10e  d 2 10e1    d k 10e1k   , d1  0.

 
 Rounding

Let x is approximation of x written in decimal representation

x    d1 10e  d 2 10e1    d k 10e1k   , d1  0.

 
We say that k-th decimal digit dk is significant if

x  x  0,5 10e1k (3)

i.e. if x differs from x

at most of 5 units of order of subsequent digit.
 Rounding

Let x is approximation of x written in decimal representation

x    d1 10e  d 2 10e1    d k 10e1k   , d1  0.

 
We say that k-th decimal digit dk is significant if

x  x  0,5 10e1k (3)

i.e. if x differs from x

at most of 5 units of order of subsequent digit.
If inequality (3) holds for k  p , but not for k  p  1,
we say, that x has p significant digits
and is correctly rounded value of the number x
to the p significant digits.
 Rounding

We say that k-th decimal place is significant if

x  x  0,5 10k (4)

i.e. if x differs from x

at most of 5 units of order of subsequent decimal place.
 Rounding

We say that k-th decimal place is significant if

x  x  0,5 10k (4)

i.e. if x differs from x

at most of 5 units of order of subsequent decimal place.
If inequality (4) hold for kp but not for k  p 1 ,
we say that x has p significant decimal places.
 Rounding

Several examples

# of significant # of significant
x x digits decimal places
374 380
-27.6473 -27.598
100.002 99.9973
99.9973 100.002
-0.003728 -0.0041
1.841*10-6 2.5*10-6
 Rounding

Several examples

# of significant # of significant
x x digits decimal places
374 380 1 -
-27.6473 -27.598
100.002 99.9973
99.9973 100.002
-0.003728 -0.0041
1.841*10-6 2.5*10-6
 Rounding

Several examples

# of significant # of significant
x x digits decimal places
374 380 1 -
-27.6473 -27.598 3 1
100.002 99.9973
99.9973 100.002
-0.003728 -0.0041
1.841*10-6 2.5*10-6
 Rounding

Several examples

# of significant # of significant
x x digits decimal places
374 380 1 -
-27.6473 -27.598 3 1
100.002 99.9973 4 2
99.9973 100.002
-0.003728 -0.0041
1.841*10-6 2.5*10-6
 Rounding

Several examples

# of significant # of significant
x x digits decimal places
374 380 1 -
-27.6473 -27.598 3 1
100.002 99.9973 4 2
99.9973 100.002 5 2
-0.003728 -0.0041
1.841*10-6 2.5*10-6
 Rounding

Several examples

# of significant # of significant
x x digits decimal places
374 380 1 -
-27.6473 -27.598 3 1
100.002 99.9973 4 2
99.9973 100.002 5 2
-0.003728 -0.0041 1 3
1.841*10-6 2.5*10-6
 Rounding

Several examples

# of significant # of significant
x x digits decimal places
374 380 1 -
-27.6473 -27.598 3 1
100.002 99.9973 4 2
99.9973 100.002 5 2
-0.003728 -0.0041 1 3
1.841*10-6 2.5*10-6 0 5
 Propagation of errors

Subtracting of two close numbers leads to

decrement of significant digits
 Propagation of errors

Subtracting of two close numbers leads to

decrement of significant digits

Example:
x
x  4.998949 101 , x  4.999 101 , x  5.10 104 ,  1.020 105 ,
x
4 y
y  5.001848 10 ,
1
y  5.002 10 ,
1
y  1.52 10 ,  3.039 105
y
 Propagation of errors

Subtracting of two close numbers leads to

decrement of significant digits

Example:
x
x  4.998949 101 , x  4.999 101 , x  5.10 104 ,  1.020 105 ,
x
4 y
y  5.001848 10 ,
1
y  5.002 10 ,
1
y  1.52 10 ,  3.039 105
y
then for subtractions z  y  x, z  y  x we get
2 2 3 z
z  2.899 10 , z  3 10 , z  1.0110 ,  3.484 102
z
 Propagation of errors

Subtracting of two close numbers leads to

decrement of significant digits

Example:
x
x  4.998949 101 , x  4.999 101 , x  5.10 104 ,  1.020 105 ,
x
4 y
y  5.001848 10 ,
1
y  5.002 10 ,
1
y  1.52 10 ,  3.039 105
y
then for subtractions z  y  x, z  y  x we get
2 2 3 z
z  2.899 10 , z  3 10 , z  1.0110 ,  3.484 102
z

therefore z has one significant digit

 and
while x y have four significant digits.
 Propagation of errors

Example:

x  1.3262  5 105 , y  6.5347  5 105 , z  13.235  5 104

Find the approximation of

f  xy / z,
absolute and relative errors
and the number of significant digits of result.
 Introductory lecture

Contents

1. Introduction, syllabus, evaluation

2. Source and types of errors
3. Definition of errors
4. Rounding, propagation of errors
5. Representation of numbers
6. Conditionality of numerical problems and
numerical stability of algorithms
 Representation of numbers

Real numbers in computers are represented in the

floating point format.

Basic idea is similar to the

semilogarithmic notation
(i.e. 2.457*105 )

System of normalized floating point numbers 

is characterized by 4 integer numbers:
 Representation of numbers

 base    2
p precision  p  1
 emin , emax  exponent range emin  0  emax 
 Representation of numbers

 base    2
p precision  p  1
 emin , emax  exponent range emin  0  emax 

Each numberx   has form of

d 2 d3 dp
x  m   , where m  d1   2    p1
e
  
 Representation of numbers

 base    2
p precision  p  1
 emin , emax  exponent range emin  0  emax 

Each number x   has form of

d 2 d3 dp
x  m   , where m  d1   2    p1
e
  
m is normalized mantissa (or significand),
di  0,1,...,  1 , i  1, 2,..., p are digits of mantissa,
p is the number of digits of mantissa and
e  emin , emax is integer exponent.
 Representation of numbers

 base    2
p precision  p  1
 emin , emax  exponent range emin  0  emax 

Each number x   has form of

d 2 d3 dp
x  m   , where m  d1   2    p1
e
  
m is normalized mantissa (or significand),
di  0,1,...,  1 , i  1, 2,..., p are digits of mantissa,
p is the number of digits of mantissa and
e  emin , emax is integer exponent.

Normalized mantissa means that for x0 is d1  1.

 Representation of numbers

 2 binary numeral system

  16 hexadecimal system
 8 octal system
  10 decimal system
 Representation of numbers

 2 binary numeral system

  16 hexadecimal system
 8 octal system
  10 decimal system

Set  of floating point numbers is a finite set,

count of number is
 Representation of numbers

 2 binary numeral system

  16 hexadecimal system
 8 octal system
  10 decimal system

Set  of floating point numbers is a finite set,

count of number is

2   1  p1 emax  emin  1  1

two signs,
 Representation of numbers

 2 binary numeral system

  16 hexadecimal system
 8 octal system
  10 decimal system

Set  of floating point numbers is a finite set,

count of number is

2   1  p1 emax  emin  1  1

two signs,
 1 options for the first digit of mantissa,
 Representation of numbers

 2 binary numeral system

  16 hexadecimal system
 8 octal system
  10 decimal system

Set  of floating point numbers is a finite set,

count of number is

2   1  p1 emax  emin  1  1

two signs,
 1 options for the first digit of mantissa,
 options for other p 1 digits of mantissa,
 Representation of numbers

 2 binary numeral system

  16 hexadecimal system
 8 octal system
  10 decimal system

Set  of floating point numbers is a finite set,

count of number is

2   1  p1 emax  emin  1  1

two signs,
 1 options for the first digit of mantissa,
 options for other p 1 digits of mantissa,
emax  emin 1 possible values of exponent
 Representation of numbers

 2 binary numeral system

  16 hexadecimal system
 8 octal system
  10 decimal system

Set  of floating point numbers is a finite set,

count of number is

2   1  p1 emax  emin  1  1

two signs,
 1 options for the first digit of mantissa,
 options for other p 1 digits of mantissa,
emax  emin 1 possible values of exponent
and one zero
 Representation of numbers

The smallest positive number in  is UFL (UnderFlow Level)

UFL   emin ,
which has the first digit of mantissa equal to one, others zero
and exponent the smallest one.

The largest positive number in  is OFL (OverFlow Level)

 
OFL     1 p  U ,
which has all digits of mantissa equal to  1 and
exponent is the largest one.
 Representation of numbers

The gaps between adjacent numbers

scale
with the size of the numbers
 Representation of numbers

The gaps between adjacent numbers

scale
with the size of the numbers

Relative resolution is given by machine epsilon

εmachine = 0.5 β1-p
For all x, there exists a floating point x'
such that |x'−x|≤ εmachine|x|
 Representation of numbers

The gaps between adjacent numbers

scale
with the size of the numbers

Relative resolution is given by machine epsilon

εmachine = 0.5 β1-p
For all x, there exists a floating point x'
such that |x'−x|≤ εmachine|x|

Example:   2, p  3, emin  1, emax  2

 Representation of numbers

The gaps between adjacent numbers

scale
with the size of the numbers

Relative resolution is given by machine epsilon

εmachine = 0.5 β1-p
For all x, there exists a floating point x'
such that |x'−x|≤ εmachine|x|

Example:   2, p  3, emin  1, emax  2

0 1 2 3 4 5 6 7
 Representation of numbers

• ±∞ is returned when an operation overflows

• x/±∞ = 0 for any number x,

• x/0 = ±∞ for any nonzero number x

• Operations with infinity are defined as limits, e.g.

4   lim 4  x  
x

• NaN (Not a Number) is returned when the an operation has no well-

defined finite or infinite result
Examples: ,  / , 0 / 0, NaN ⊙ x
 Representation of numbers

Denormalized Numbers

• With normalized significand there is a “gap” between 0 and β emin

0 β em i n β em i n + 1 β em i n + 2 β em i n + 3
 Representation of numbers

Denormalized Numbers

• With normalized significand there is a “gap” between 0 and β emin

• Solution: Allow non-normalized significand when the exponent is emin

• This gradual underflow garantees that

x = y ⇐⇒ x − y = 0

0 β em i n β em i n + 1 β em i n + 2 β em i n + 3

0 β em i n β em i n + 1 β em i n + 2 β em i n + 3
Representation of numbers
Representation of numbers
Representation of numbers
Representation of numbers
 Introductory lecture

Contents

1. Introduction, syllabus, evaluation

2. Source and types of errors
3. Definition of errors
4. Rounding, propagation of errors
5. Representation of numbers
6. Conditionality of numerical problems and
numerical stability of algorithms
Conditionality of numerical problems and numerical stability of algorithms

We have to investigate the effects

of small changes in input data and rounding
on the result.
Conditionality of numerical problems and numerical stability of algorithms

We have to investigate the effects

of small changes in input data and rounding
on the result.

Mathematical problem can be treated as mapping y  f  x ,

which each data from x the set D of input data
assigns the result y from the set R of output data.
Conditionality of numerical problems and numerical stability of algorithms

We have to investigate the effects

of small changes in input data and rounding
on the result.

Mathematical problem can be treated as mapping y  f  x ,

which each data from x the set D of input data
assigns the result y from the set R of output data.

We say that the mathematical problem

y  f  x  , x  D, y  R,
is correct, when

1. For each input x  D exists only one result y  R ,

2. this result continuously depends on input data,
i.e. if x  a , then f  x   f  a  .
Conditionality of numerical problems and numerical stability of algorithms

We say that the correct problem is well-conditioned, if

small change in input data
will cause small change of result.
Conditionality of numerical problems and numerical stability of algorithms

We say that the correct problem is well-conditioned, if

small change in input data
will cause small change of result.

Condition number is defined as

relative error of input

Cp 
relative error of output
Conditionality of numerical problems and numerical stability of algorithms

We say that the correct problem is well-conditioned, if

small change in input data
will cause small change of result.

Condition number is defined as

relative error of input

Cp 
relative error of output

If C p  1, the problem is well-conditioned.

For large Cp (>100) the problem is ill-conditioned.

Conditionality of numerical problems and numerical stability of algorithms

We say that the algorithm is well-conditioned,

if it is less sensitive to errors in input data.

If the effect of round-off errors on result is small then

we say about numerically stable algorithm.

Well-conditioned and numerically stable algorithm

is called stable.
Conditionality of numerical problems and numerical stability of algorithms

Example:

Estimate the condition number of the problem:

evaluate the functional value of (differentiable) function

y  f  x

show on example function

f  x   tan x
Conditionality of numerical problems and numerical stability of algorithms

Examples:

1. roots of quadratic equation x 2  2bx  c  0

1
2. Evaluation of integral En   x n e x1dx n  1, 2,...
0
Conditionality of numerical problems and numerical stability of algorithms
Conditionality of numerical problems and numerical stability of algorithms
Conditionality of numerical problems and numerical stability of algorithms

for
Conditionality of numerical problems and numerical stability of algorithms

for