Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.1
Lecture 3
Introductio n to Numerical
Fundamentals
Numbers, Errors
IKC-MH.55 Scientific Computing with Python at October 27,
2023
Dr. Cem Özdo
˘
gan
Engineering Sciences Department
˙
Izmir Kâtip Çelebi University
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.2
Contents
1 Numerical Fundamentals
Analysis vs Numerical Analysis
Some disasters attributable to bad numerical computing
Floating-Point Arithmetic
Computer Number Representation
Kinds of Err ors in Numerical Procedures
Absolute vs Relative Error & Convergence
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.3
How a computer can be used
1 to solve problems that may not be solvable by hand.
2 to solve problems (that you may have solved before) in a
different way.
•
Many of these simplified examples can be solved
analytically (by hand)
x
3
− x
2
− 3x + 3 = 0, with solution
√
3
•
But most of the examples can not be simplified and can
not be solved analytically.
•
Mathematical relationships =⇒ simulate some real word
situations.
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.4
Five Basic Operations
•
In mathematics, solve a problem through equations;
algebra, calculus, differential equations (D E), Partial
DE, . . .
•
In numerical analysis; four operations (add, subtract,
multiply, division) and Compar is on.
•
These operations are exactly those that computers can do
Z
π
0
p
1 + cos
2
xdx
•
length of o n e arch of the curve y-sinx; no solution with “a
substitution’ or “integration by parts”
•
numerical analysis can compute the length of this curve by
standardised methods that a p p ly to essentially any integrand
•
Another difference between a numerical r esults and
analytical answer is that the former is always an
approximation
•
this can usually be as accurate as needed (level of
accuracy)
•
Numerical Methods require r epetitive arithmetic operations
⇒ a computer to car ry out
•
Also, a human would make so many mistakes
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.5
Some disasters attributable to bad numerical computing
Have you been paying attention in your numerical analysis or
scientific computation courses? Here are some
real life examples
of what can happen when numerical
algorithms ar e not correctly applied.
•
The Patriot Miss ile failure, in Dharan, Saudi Arabia, on
February 25, 1991 which resulted in 28 deaths, is
ultimately attributable to poor handling of rounding
errors.
•
The explosion of the Ariane 5 rocket just after lift-off on its
maiden voyage off French Guiana, on June 4, 1996, was
ultimately the consequen ce of a simple overflow.
•
The sinking of the Sleipner A offshore platform in
Gandsfjorden near Stavanger, Norway, on August 23,
1991, resulted in a loss of nearly one billion dollars. It was
found to be the result of inaccurate finite element
analysis.
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.6
Floating-Point Arithmetic I
•
Performing an arithmetic operation ⇒ no exact answers
unless only integers or exact powers of 2 are involved,
•
Floating-point (real numbers)→ not integers,
•
Resembles scientific notation,
•
IEEE standard → storing floating-point numbers (see the
Table 1).
Table: Float ing→ Normalised.
floating normalised (shifting the decimal point)
13.524 .13524 ∗ 10
2
(.13524E2)
-0.0442 −.442E −1
•
the sign ±
•
the fraction part (called the mantissa)
•
the exponent part
•
What about the sign of the exponent? Rather than use
one of the bits for the sign of the exponent, exponents are
biased.
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.7
Floating-Point Arithmetic II
For single precision (we have 8 bits reserved for the
exponent):
• 2
8
=256
• 0−→00000000 = 0
• 255−→11111111=255
• 0 (255)=⇒ -127 (128). An exponent of -127 (128) stored
as 0 ( 255).
• So biased−→ 2
128
= 3.40282E + 38, mantissa gets 1 as
maximum
• Largest: 3.40282E+38; Smallest: 5.87747E-39 (!)
• For double and extended precision the bias values are
1023 and 16383, respectively.
•
0
0
, 0 ∗ ∞,
√
−1 =⇒ NaN : Undefined.
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.8
Floating-Point Arithmetic III
There are three levels of precis ion (see the Fig. )
Figure: Level of precision.
week3_HandsOn.py
1 i mport sys
2 p r i n t ( sys . f l o a t _ i n f o )
3 # sys . f l o a t _ i n f o ( max=1.7976931348623157 e+308 , max_exp=1024,
max_10_exp =308 , min=2.2250738585072014 e−3 08, min_exp=−1021,
4 # min_10_exp=−307, di g =15, mant_dig =53, e psil o n =2.220446049250313 e
−16, r a di x =2 , rounds =1)
5 p r i n t ( sys . f l o a t _ i n f o . max)
6 # 1.7976931348623157 e+308
7 p r i n t ( " %10.6e " % 2
**
128)
8 # 3.402824 e+38
9 p r i n t ( " %10.6e " % 2
**
1023)
10 # 8.988466e+307 f
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.9
Floating-Point Arithmetic IV
EPS: short for epsilon−→used for represent the smallest
machine value that can be added to 1.0 that gives a result
distinguishable
from 1.0!
•
eps −→ ε =⇒ (1 + ε) + ε = 1 but 1 + (ε + ε) > 1
•
Two numbers that are very close together on the r eal
number line can not be distinguished on the floating-point
number line if their difference is less than the least
significant bit of their mantissas.
1 im port sys
2 p r i n t ( sys . f l o a t _ i n f o . e psil o n )
3 # 2.220446049250313 e−16
4 eps=sys . f l o a t _ i n f o . ep s ilon
5 p r i n t (1+eps
*
0 . 5)
6 # 1.0
7 p r i n t (1+eps
*
0 . 5)
8 # 1.0
9 p r i n t (( 1+ eps
*
0 . 5) +eps
*
0 . 5)
10 # 1.0
11 p r i n t (1+eps
*
0 . 6)
12 # 1 .0000000000000002
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.10
Computer Number Rep resentation I
Say we have six bit representation (not single, double) (see the
Fig.)
•
1 bit → sign
•
3(+1) bits → mantissa
•
2 bits → exponent
Figure: Computer numbers with six bit representat ion.
•
For positive range
9
32
←→
15
4
•
For negative range
−15
4
←→
−9
32
; even discontinuity at point
zero since it is not in the ranges.
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.11
Computer Number Rep resentation II
Figure: Upper : number line in the hypothetical system, Lower: IEEE
standard.
•
Very simple computer arithmetic system ⇒ the gaps
between stored values are very apparent.
•
Many values can not be stored exactly. i.e., 0.601, it will be
stored as if it were 0.6250 because it is closer to
10
16
, an
error of 4%
•
In IEEE system, gaps are much smaller but they are still
present. (see the lower Fig.)
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.12
Kinds of Errors in Numerical Procedures I
Computers use only a fixed number of digits
to represent a number.
•
As a result, the numerical values stored in a c omputer are
said to have finite precision.
•
Limiting precision has the desirable effects of increasing
the speed of numerical calculations and reducing memory
required to store numbers.
•
But, what are the undesirable effects?
Kinds of Errors:
i Round-off Error
ii Truncatio n Error
iii Propagated Error
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.13
Kinds of Errors in Numerical Procedures II
i Round-off Error:
1 # ! / usr / bi n / python3
2 x = ( 4/ 3 )
*
3; pr i n t ( x )
3 # 4.0
4 a =4/3; p r i n t ( a) # s t o re double pre c i si on approx of 4/3
5 # 1.3333333333333333
6 b=a−1; p r i n t ( b) # rem ove most s i g n i f i c a n t d i g i t
7 # 0.33333333333333326
8 c=1−3
*
b ; p r i n t ( c ) # 3
*
b=1 i n exact m ath
9 # 2.220446049250313 e−16 # should be 0 ! !
1 from m ath i m por t
*
2 # im port numpy as np
3 # k f i r s t =1 .0; k l as t =360.0; kincrement =0.1
4 # f o r j i n np . arange ( k f i r s t , k l a s t + kincrement , kincrement ) :
5 fo r j in range ( 1 , 360 ) : # In degrees (1−360) as i n t . increment
6 j j = j
*
( 2
*
pi / 3 60) # Conversion t o radi an
7 a=cos ( j j ) # Return the cosine of j j ( measured i n radia ns )
8 b= si n ( j j ) # Return the cosine of j j ( measured in radians )
9 z=a−(a / b)
*
b # Expected as being 0 ! !
10 p r i n t ( j , j j , z )
11 352 6.14355896702004 0.0
12 353 6.161012259539984 1.1102230246251565 e−16
13 354 6.178465552059927 1.1102230246251565 e−16
14 355 6.19591884457987 1.1102230246251565 e−16
15 356 6.213372137099813 0.0
16 357 6.230825429619756 0.0
17 358 6.2482787221397 0.0
18 359 6.265732014659643 0.0
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.14
Kinds of Errors in Numerical Procedures III
1 summation =1.0
2 fo r i in range (10000) : # Adding 0.00001 to 1.0 as 10000 times
3 summation=summation +0.00001
4 p r i n t ( ’ summation = ’ , summation )
5 # summation = 1.1000000000006551 # Expected r e s u l t i s j u st 1.1 ! !
6 p r i n t ( " summation = %f " % summation )
7 # summation = 1.100000 # Now expected r e s u l t ??
To see the effects of roundoff in a simple calculation, one need
only to force the computer to store the intermediate results.
•
All computing devices represents numbers, except for
integers and some fractions, with some imprecision.
•
Floating-point numbers of fixed word length; the true
values are usually not expressed exactly by such
representations.
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.15
Kinds of Errors in Numerical Procedures IV
1 i mpo rt numpy as np
2 x=np . tan ( np . pi / 6) ; p r i n t ( x )
3 # 0.5773502691896257
4 y=np . s i n ( np . pi / 6) / np . cos ( np . pi / 6 ) ; p r i n t ( y )
5 # 0.5773502691896256
6 i f x==y :
7 p r i n t ( " x and y are equal " )
8 el s e :
9 p r i n t ( " x and y are not equal : x−y=%e " % ( x−y ) )
10 # x and y are not equal : x−y=1.110223e−16
•
The test is true only if x and y are exactly equal in
bit pattern.
•
Although x and y are equal in exact arithmetic, their
values differ by a small, but nonzero, amount.
•
When working with floating-point values the question “are
x and y equal?” is replaced by “are x and y close?” or,
equivalently, “is x − y small enough?”
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.16
Kinds of Errors in Numerical Procedures IV
ii Truncatio n Error: i.e., approximate e
x
by the cubic power
P
3
(x) = 1 +
x
1!
+
x
2
2!
+
x
3
3!
; e
x
= P
3
(x) +
∞
X
n=4
x
n
n!
•
Approximating e
x
with the cubic gives an inexact answer.
The error is due to truncating
the series,
•
When to cut series expansion =⇒ be satisfied with an
approximation to the exact analytical answer.
•
Unlike roundoff, which is controlled by the hardware and the
computer language being used, truncation error is under
control of the programmer or user.
•
Truncation error can be reduced by selecting more accurate
discrete approximations. But, it can not be elimin ated
entire ly.
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.17
Kinds of Errors in Numerical Procedures V
Evaluating the Series for sin(x) (Example py-file: sinser.py)
sin(x) = x −
x
3
3!
+
x
5
5!
−
x
7
7!
+ . . .
•
An efficient implementation of the series uses recursion to
avoid overflow in the evaluation of individual terms. If T
k
is
the k
th
ter m (k = 1, 3, 5, . . .) then
T
k
=
x
2
k(k − 1)
T
k−2
•
Study the effect of the parameters tol and nmax by
changing their values (Default values are 5e-9 and 15,
respectively).
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.18
Kinds of Errors in Numerical Procedures VI
1 i m p o r t numpy as np
2 d ef si n s e r ( x , t o l , n ) :
3 term = x
4 ssum = term # I n i t i a l i z e s e r i e s
5 p r in t ( " Se r i es approx i m a t i o n t o sin (%f ) \ n k term ssum" % ( x
*
360 / ( 2
*
np . p i ) )
)
6 p r in t ( " 1 % 11.3e %20.16 f " % ( term , ssum ) )
7 f o r k i n range (3 , 2
*
n−1, 2) :
8 term = −term
*
x
*
x / ( k
*
( k−1)) # Next term i n t he s e r ie s
9 ssum = ssum + term
10 p r i nt ( "%3d %11.3e %30.26 f " % ( k , term , ssum ) )
11 i f abs ( t erm / ssum ) < t ol :
12 break # True a t convergence
13 p r i n t ( " Tr u nc at ion er r o r a f t er %d terms i s %g " % ( ( k+1) /2 , abs (ssum−np . sin ( x ) ) ) )
14 s i n s e r ( np . p i / 6 ,5e−9,10)
15 p r i n t ( " si n (% f )=%f w i t h numpy l i b r a r y " % ( np . p i / 6
*
3 6 0 / ( 2
*
np . p i ) ,np . sin ( np . p i / 6 ) ) )
16 i m p o r t math
17 p r i n t ( " si n (% f )=%f w i t h math l i b a r a r y " % ( math . p i / 6
*
3 6 0 / ( 2
*
math . p i ) , math . s i n ( math . pi / 6 ) ) )
Figure: Output of sinser.py
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.19
Kinds of Errors in Numerical Procedures VII
Derivative of Sine function. Truncation & Round-off Errors
(Example py-file: trunroun.py)
Figure: Output and Plot of trunroun.py
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.20
Kinds of Errors in Numerical Procedures VIII
iii Propagated Error:
•
more subtle (difficult to analyse)
•
by propagated we mean an error in the succee ding steps of
a process due to an occurrence of an earlier error
•
of critical importance
•
stable numerical methods; errors made at early points
die out
as the method continues
•
unstable numerical method; does not die out
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.21
Absolute vs Relative Error & C onvergence I
•
Accuracy (how close to the true value) −→ great
importance,
•
absolute error = |true value − approximate error |
A given size of error is usually more serious when the
magnitude of the tr ue value is small,
•
relative error =
absolute error
|true value|
•
Convergence of Iterative Sequences:
•
Iteration is a common component of numerical algorithms.
In the most abstract form, an iteration generates a
sequence of scalar values x
k
, k = 1, 2, 3, . . .. The seque nce
converges to a limit ξ if
|x
k
− ξ| < δ, for all k > N
where δ is a small number called the convergence
tolerance. We say that the sequence has converged to
within the to lerance δ after N iterations.
Introduction to
Numerical
Fundamentals
Dr. Cem Özdo
˘
gan
LOGIK
Numerical
Fundamentals
Analysis vs Numerical
Analysis
Some disasters attributable
to bad numerical computing
Floating-Point Arithmetic
Computer Number
Representation
Kinds of Errors in Numerical
Procedures
Absolute vs Relative Error
& Convergence
3.22
Absolute vs Relative Error & C onvergence II
1 def n ewtsqrt ( x , delt a , maxit ) :
2 r = x / 2 ; r o l d = x # I n i t i a l i z e , make sure convergence t e s t f a i l s on f i r s t t r y
3 i t = 0
4 w h i l e ( r ! = r o l d ) and ( i t < maxit ) : # Convergence t e s t
5 # while ( ( r−r o l d ) > d e lt a ) and ( i t <maxit ) : # Convergence te s t
6 # while ( abs ( r−rol d ) > de l t a ) and ( i t <maxit ) : # Convergence t e s t
7 # while ( abs ( ( r−ro l d ) / r o l d ) > d e l t a ) and ( i t <m axit ) : # Convergence te s t
8 r o l d = r # Save ol d valu e f o r next convergence t e s t
9 r = 0 . 5
*
( r o l d + x / r o l d ) # Upda te the guess
10 i t = i t + 1
11 r e t u r n r
12 # Tes t the newtsqrt f u n c t i o n f o r a range o f in p u t s
13 x t e s t = [4 , 0.04 , 4e−4, 4e−6, 4e−8, 4e−10, 4e−12] # arguments t o t e s t
14 p r i n t ( " Absolute Converg ence C r i t e r i o n " )
15 p r i n t ( " x s q r t ( x ) new t s qrt ( x ) e r r o r r e l e r r " )
16 i m p o r t math
17 f o r x i n xt e s t : # repe a t f o r each element in x t e s t
18 r = math . s q r t ( x )
19 r n = n e wt s qrt ( x , 5 e−9,25)
20 er r = abs ( rn − r )
21 r e l e r r = er r / r
22 p r i n t ( " %10.3e %10.3e %10.3e %10.3e %10.3e " % ( x , r , rn , err , r e le r r ) )
Figure: Output of newtsqrt.py
Newton’s method to
compute the square root
of a number.
Example py-file:
newtsqrt.py
