Numerical Methods

Lecture Notes #01

Pavel Ludvk,
<pavel.ludvik@vsb.cz>
Department of Mathematics and Descriptive Geometry
VB-TUO

http://homen.vsb.cz/~lud0016/

September 17, 2015

Lecture Notes #01

The Professor

The Professor

Lecture Notes #01

The Professor
Contact Information, Oce Hours

Pavel Ludvk
Oce
Oce phone number
E-mail
Web
Oce Hours

A832
59 732 4179
pavel.ludvik@vsb.cz

http://homen.vsb.cz/~lud0016/
by appointment

Lecture Notes #01

Course Information

Course Information

Lecture Notes #01

Course Information
Expectations and Procedures

Necessary and Sucient Conditions

Exercises
Conditions for obtaining credit points (CP):
Participation in exercises, 20% can be to apologize.

Lecture Notes #01

Course Information
Expectations and Procedures

Necessary and Sucient Conditions

Exercises
Conditions for obtaining credit points (CP):
Participation in exercises, 20% can be to apologize.
Completion of a home project (0-15 CP) and delivering all homeworks
(0-5 CP).

Lecture Notes #01

Course Information
Expectations and Procedures

Necessary and Sucient Conditions

Exercises
Conditions for obtaining credit points (CP):
Participation in exercises, 20% can be to apologize.
Completion of a home project (0-15 CP) and delivering all homeworks
(0-5 CP).

Lecture Notes #01

Course Information
Expectations and Procedures

Necessary and Sucient Conditions

Exercises
Conditions for obtaining credit points (CP):
Participation in exercises, 20% can be to apologize.
Completion of a home project (0-15 CP) and delivering all homeworks
(0-5 CP).
Exam
Written exam 0-60 CP, successful completion at least 25 CP.

Lecture Notes #01

Course Information
Expectations and Procedures

Necessary and Sucient Conditions

Exercises
Conditions for obtaining credit points (CP):
Participation in exercises, 20% can be to apologize.
Completion of a home project (0-15 CP) and delivering all homeworks
(0-5 CP).
Exam
Written exam 0-60 CP, successful completion at least 25 CP.
Oral exam 0-20 CP, successful completion at least 5 CP.

Lecture Notes #01

Course Information
Expectations and Procedures

Necessary and Sucient Conditions

Exercises
Conditions for obtaining credit points (CP):
Participation in exercises, 20% can be to apologize.
Completion of a home project (0-15 CP) and delivering all homeworks
(0-5 CP).
Exam
Written exam 0-60 CP, successful completion at least 25 CP.
Oral exam 0-20 CP, successful completion at least 5 CP.

Lecture Notes #01

Course Information
Expectations and Procedures

Necessary and Sucient Conditions

Exercises
Conditions for obtaining credit points (CP):
Participation in exercises, 20% can be to apologize.
Completion of a home project (0-15 CP) and delivering all homeworks
(0-5 CP).
Exam
Written exam 0-60 CP, successful completion at least 25 CP.
Oral exam 0-20 CP, successful completion at least 5 CP.

Grading (in Czech); International grading system is a little dierent

86 - 100 excellent
66 - 85 satisfactory
51 - 65 mediocre
0 - 50
failed

Lecture Notes #01

Course Information
Expectations and Procedures

Expectations

Please be on time.

Lecture Notes #01

Course Information
Expectations and Procedures

Expectations

Please be on time.
Please pay attention.

Lecture Notes #01

Course Information
Expectations and Procedures

Expectations

Please be on time.
Please pay attention.
Students are expected and encouraged to ask questions in class!

Lecture Notes #01

Course Information
Expectations and Procedures

Expectations

Please be on time.
Please pay attention.
Students are expected and encouraged to ask questions in class!
Students are expected and encouraged to make use of consultations
with the instructor!

Lecture Notes #01

Course Information
Book and Other Study Materials

The recommended text for the course is the book:

Title:
Authors:
Edition:
Publisher:

Numerical Analysis
Richard L. Burden, John D. Faires
9
Cengage Learning, 2011

Lecture Notes #01

Course Information
Book and Other Study Materials

Other materials:

Title:
Authors:
Edition:
Publisher:

Numerical Methods for Engineers

Steven Chapra, Raymond Canale
6
McGraw-Hill Education, 2009

Lecture Notes #01

Course Information
Book and Other Study Materials

Other materials:

Title:
Authors:
Edition:
Publisher:

Numerical Methods for Engineers

Steven Chapra, Raymond Canale
6
McGraw-Hill Education, 2009

Solved examples:

http://mdg.vsb.cz/wiki/public/ZM_NM_examples.pdf

Lecture Notes #01

Course Information
Book and Other Study Materials

Other materials:

Title:
Authors:
Edition:
Publisher:

Numerical Methods for Engineers

Steven Chapra, Raymond Canale
6
McGraw-Hill Education, 2009

Solved examples:

http://mdg.vsb.cz/wiki/public/ZM_NM_examples.pdf
My web: http://homen.vsb.cz/~lud0016/

Lecture Notes #01

Course Information
Book and Other Study Materials

Other materials:

Title:
Authors:
Edition:
Publisher:

Numerical Methods for Engineers

Steven Chapra, Raymond Canale
6
McGraw-Hill Education, 2009

Solved examples:

http://mdg.vsb.cz/wiki/public/ZM_NM_examples.pdf
My web: http://homen.vsb.cz/~lud0016/
Qaurteroni, A., Sacco, R., Saleri, F.:
2007.

Numerical Mathematics.

Springer,

Lecture Notes #01

Course Information
Book and Other Study Materials

Other materials:

Title:
Authors:
Edition:
Publisher:

Numerical Methods for Engineers

Steven Chapra, Raymond Canale
6
McGraw-Hill Education, 2009

Solved examples:

http://mdg.vsb.cz/wiki/public/ZM_NM_examples.pdf
My web: http://homen.vsb.cz/~lud0016/
Qaurteroni, A., Sacco, R., Saleri, F.:

Numerical Mathematics.

Springer,

2007.
Sli, E., Mayers, D.:

An introduction to Numerical Analysis.

University Press, 2003.

Cambridge

Lecture Notes #01

Course Information
Book and Other Study Materials

Software tools

Mathworks Mathlab  available on computers in the classrooms (for

access to the classrooms ask at F312)

Lecture Notes #01

Course Information
Book and Other Study Materials

Software tools

Mathworks Mathlab  available on computers in the classrooms (for

access to the classrooms ask at F312)

Octave  free alternative to MatLab:

http://mdg.vsb.cz/wiki/public/soubory/qtoctave0.7.2_
octave3.0.0_Portable_win32.zip

Lecture Notes #01

Course Information
Book and Other Study Materials

Software tools

Mathworks Mathlab  available on computers in the classrooms (for

access to the classrooms ask at F312)

Octave  free alternative to MatLab:

http://mdg.vsb.cz/wiki/public/soubory/qtoctave0.7.2_
octave3.0.0_Portable_win32.zip

Practical introduction to MatLab  .

Lecture Notes #01

Course Information
Book and Other Study Materials

Software tools

Mathworks Mathlab  available on computers in the classrooms (for

access to the classrooms ask at F312)

Octave  free alternative to MatLab:

http://mdg.vsb.cz/wiki/public/soubory/qtoctave0.7.2_
octave3.0.0_Portable_win32.zip

Practical introduction to MatLab  .

Learning videos for Mathlab:

http://www.mathworks.com/videos/
getting-started-with-matlab-68985.html.
Using Basic Plotting Functions  http://www.mathworks.com/
videos/using-basic-plotting-functions-69018.html.
Writing a MatLab Program  http://www.mathworks.com/videos/
writing-a-matlab-program-69023.html.

Getting Started with MatLab 

Lecture Notes #01

Course Information
Syllabus

Program of Lectures I

Ideal scenerio  one topic per week:

Course Contents, Mathematical Preliminaries and Error Analysis.

Lecture Notes #01

Course Information
Syllabus

Program of Lectures I

Ideal scenerio  one topic per week:

Course Contents, Mathematical Preliminaries and Error Analysis.

Solution of Nonlinear Equations, Roots Separation, Bisection Method,

Regula Falsi (i.e., False-Position Method).

Lecture Notes #01

Course Information
Syllabus

Program of Lectures I

Ideal scenerio  one topic per week:

Course Contents, Mathematical Preliminaries and Error Analysis.

Solution of Nonlinear Equations, Roots Separation, Bisection Method,

Regula Falsi (i.e., False-Position Method).

Newton's Method and Fix-Point Iterations.

Lecture Notes #01

Course Information
Syllabus

Program of Lectures I

Ideal scenerio  one topic per week:

Course Contents, Mathematical Preliminaries and Error Analysis.

Solution of Nonlinear Equations, Roots Separation, Bisection Method,

Regula Falsi (i.e., False-Position Method).

Newton's Method and Fix-Point Iterations.

Direct Methods for Solving Linear Equations, Gaussian Elimination and

LU-Decomposition.

Lecture Notes #01

Course Information
Syllabus

Program of Lectures I

Ideal scenerio  one topic per week:

Course Contents, Mathematical Preliminaries and Error Analysis.

Solution of Nonlinear Equations, Roots Separation, Bisection Method,

Regula Falsi (i.e., False-Position Method).

Newton's Method and Fix-Point Iterations.

Direct Methods for Solving Linear Equations, Gaussian Elimination and

LU-Decomposition.

Eigenvalues and Eigenvectors, Numerical Calculation.

Lecture Notes #01

Course Information
Syllabus

Program of Lectures I

Ideal scenerio  one topic per week:

Course Contents, Mathematical Preliminaries and Error Analysis.

Solution of Nonlinear Equations, Roots Separation, Bisection Method,

Regula Falsi (i.e., False-Position Method).

Newton's Method and Fix-Point Iterations.

Direct Methods for Solving Linear Equations, Gaussian Elimination and

LU-Decomposition.

Eigenvalues and Eigenvectors, Numerical Calculation.

Iterative Methods for Solving Linear Equations.

Lecture Notes #01

Course Information
Syllabus

Program of Lectures I

Ideal scenerio  one topic per week:

Course Contents, Mathematical Preliminaries and Error Analysis.

Solution of Nonlinear Equations, Roots Separation, Bisection Method,

Regula Falsi (i.e., False-Position Method).

Newton's Method and Fix-Point Iterations.

Direct Methods for Solving Linear Equations, Gaussian Elimination and

LU-Decomposition.

Eigenvalues and Eigenvectors, Numerical Calculation.

Iterative Methods for Solving Linear Equations.

Interpolation by Polynomials and Splines.

Lecture Notes #01

Course Information
Syllabus

Program of Lectures I

Ideal scenerio  one topic per week:

Course Contents, Mathematical Preliminaries and Error Analysis.

Solution of Nonlinear Equations, Roots Separation, Bisection Method,

Regula Falsi (i.e., False-Position Method).

Newton's Method and Fix-Point Iterations.

Direct Methods for Solving Linear Equations, Gaussian Elimination and

LU-Decomposition.

Eigenvalues and Eigenvectors, Numerical Calculation.

Iterative Methods for Solving Linear Equations.

Interpolation by Polynomials and Splines.

Least Squares Approximation.

Lecture Notes #01

Course Information
Syllabus

Program of Lectures II

Numerical Dierentiation and Integration.

Lecture Notes #01

Course Information
Syllabus

Program of Lectures II

9
10

Numerical Dierentiation and Integration.

Extrapolation in Integral Calculation. Gaussian Quadrature.

Lecture Notes #01

Course Information
Syllabus

Program of Lectures II

Numerical Dierentiation and Integration.

10

Extrapolation in Integral Calculation. Gaussian Quadrature.

11

Initial Value Problems for Ordinary Dierential Equations - Euler's

method and Runge-Kutta Methods.

Lecture Notes #01

Course Information
Syllabus

Program of Lectures II

Numerical Dierentiation and Integration.

10

Extrapolation in Integral Calculation. Gaussian Quadrature.

11

Initial Value Problems for Ordinary Dierential Equations - Euler's

method and Runge-Kutta Methods.

12

Multistep Methods.

Lecture Notes #01

Course Information
Syllabus

Program of Lectures II

Numerical Dierentiation and Integration.

10

Extrapolation in Integral Calculation. Gaussian Quadrature.

11

Initial Value Problems for Ordinary Dierential Equations - Euler's

method and Runge-Kutta Methods.

12

Multistep Methods.

13

(In Case of Optimistic Scenario:

Higher Order.)

Ordinary Dierential Equations of

Lecture Notes #01

Course Information
Syllabus

Program of Lectures II

Numerical Dierentiation and Integration.

10

Extrapolation in Integral Calculation. Gaussian Quadrature.

11

Initial Value Problems for Ordinary Dierential Equations - Euler's

method and Runge-Kutta Methods.

12

Multistep Methods.

13

(In Case of Optimistic Scenario:

14

Higher Order.)
Stand by.

Ordinary Dierential Equations of

Lecture Notes #01

Course Information
Syllabus

What are numerical methods and what is it for?

Q: What are numerical methods?

Lecture Notes #01

Course Information
Syllabus

What are numerical methods and what is it for?

Q: What are numerical methods?
A: Numerical methods are algorithms based on simple arithmetic
operations on numbers.

Lecture Notes #01

Course Information
Syllabus

What are numerical methods and what is it for?

Q: What are numerical methods?
A: Numerical methods are algorithms based on simple arithmetic
operations on numbers.
Q: What are numerical methods for?

Lecture Notes #01

Course Information
Syllabus

What are numerical methods and what is it for?

Q: What are numerical methods?
A: Numerical methods are algorithms based on simple arithmetic
operations on numbers.
Q: What are numerical methods for?
A: To accurately approximate solutions of problems that cannot be solved
exactly. They reduce the dicult analytic problems to purely
arithmetical ones.

Lecture Notes #01

Course Information
Syllabus

What are numerical methods and what is it for?

Q: What are numerical methods?
A: Numerical methods are algorithms based on simple arithmetic
operations on numbers.
Q: What are numerical methods for?
A: To accurately approximate solutions of problems that cannot be solved
exactly. They reduce the dicult analytic problems to purely
arithmetical ones.
Q: What kind of applications can benet from numerical studies?

Lecture Notes #01

Course Information
Syllabus

What are numerical methods and what is it for?

Q: What are numerical methods?
A: Numerical methods are algorithms based on simple arithmetic
operations on numbers.
Q: What are numerical methods for?
A: To accurately approximate solutions of problems that cannot be solved
exactly. They reduce the dicult analytic problems to purely
arithmetical ones.
Q: What kind of applications can benet from numerical studies?
A: Image processing / computer vision, computer graphics (rendering,
animation), climate modeling, weather predictions, virtual
crash-testing of cars, medical imaging (CT = Computer Tomography),
AIDS research (virus decay vs. medication), nancial mathematics

Lecture Notes #01

Calculus Review

Calculus Review

Lecture Notes #01

Calculus Review
Q: Why to review

calculus?

In numerical mathematics??

Lecture Notes #01

Calculus Review
Q: Why to review

calculus?

In numerical mathematics??

A: When developing numerical schemes we will use theorems from calculus

to guarantee that our algorithms make sense.

Lecture Notes #01

Calculus Review
Q: Why to review

calculus?

In numerical mathematics??

A: When developing numerical schemes we will use theorems from calculus

to guarantee that our algorithms make sense.

Lecture Notes #01

Calculus Review
Q: Why to review

calculus?

In numerical mathematics??

A: When developing numerical schemes we will use theorems from calculus

to guarantee that our algorithms make sense.

Key concepts from calculus:

Limits

Lecture Notes #01

Calculus Review
Q: Why to review

calculus?

In numerical mathematics??

A: When developing numerical schemes we will use theorems from calculus

to guarantee that our algorithms make sense.

Key concepts from calculus:

Limits
Continuity

Lecture Notes #01

Calculus Review
Q: Why to review

calculus?

In numerical mathematics??

A: When developing numerical schemes we will use theorems from calculus

to guarantee that our algorithms make sense.

Key concepts from calculus:

Limits
Continuity
Convergence

Lecture Notes #01

Calculus Review
Q: Why to review

calculus?

In numerical mathematics??

A: When developing numerical schemes we will use theorems from calculus

to guarantee that our algorithms make sense.

Key concepts from calculus:

Limits
Continuity
Convergence
Dierentiability

Lecture Notes #01

Calculus Review
Q: Why to review

calculus?

In numerical mathematics??

A: When developing numerical schemes we will use theorems from calculus

to guarantee that our algorithms make sense.

Key concepts from calculus:

Limits
Continuity
Convergence
Dierentiability
Rolle's Theorem

Lecture Notes #01

Calculus Review
Q: Why to review

calculus?

In numerical mathematics??

A: When developing numerical schemes we will use theorems from calculus

to guarantee that our algorithms make sense.

Key concepts from calculus:

Limits
Continuity
Convergence
Dierentiability
Rolle's Theorem
Mean Value Theorem

Lecture Notes #01

Calculus Review
Q: Why to review

calculus?

In numerical mathematics??

A: When developing numerical schemes we will use theorems from calculus

to guarantee that our algorithms make sense.

Key concepts from calculus:

Limits
Continuity
Convergence
Dierentiability
Rolle's Theorem
Mean Value Theorem
Extreme Value Theorem

Lecture Notes #01

Calculus Review
Q: Why to review

calculus?

In numerical mathematics??

A: When developing numerical schemes we will use theorems from calculus

to guarantee that our algorithms make sense.

Key concepts from calculus:

Limits
Continuity
Convergence
Dierentiability
Rolle's Theorem
Mean Value Theorem
Extreme Value Theorem
Intermediate Value Theorem

Lecture Notes #01

Calculus Review
Q: Why to review

calculus?

In numerical mathematics??

A: When developing numerical schemes we will use theorems from calculus

to guarantee that our algorithms make sense.

Key concepts from calculus:

Limits
Continuity
Convergence
Dierentiability
Rolle's Theorem
Mean Value Theorem
Extreme Value Theorem
Intermediate Value Theorem
Taylor's Theorem

Lecture Notes #01

Calculus Review

Limit/Convergence
Denition (Limit)
A function

dened on a set

X R has the limit L at x0 , written

lim
x x0

> 0 (i.e., > 0). there exists a real

that |f (x ) L| < , whenever x X and

if given any real number

> 0 ( > 0) such

0 < |x x0 | < .

f (x ) = L
number

Lecture Notes #01

Calculus Review

Limit/Convergence
Denition (Limit)
A function

dened on a set

X R has the limit L at x0 , written

lim
x x0

f (x ) = L

> 0 (i.e., > 0). there exists a real

that |f (x ) L| < , whenever x X and

if given any real number

> 0 ( > 0) such

0 < |x x0 | < .

number

Denition (Continuity (at a point))

Let

be a function dened on a set

continuous at x0 if

lim
x x0

X R, and x0 X .

f (x ) = f (x0 ).

Then

is

Lecture Notes #01

Calculus Review

Continuity/Convergence
Denition (Continuity (in an interval))
A function

is

continuous on a set X

continuous at each point

x X.

(i.e.,

f C (X )) if it is

Lecture Notes #01

Calculus Review

Continuity/Convergence
Denition (Continuity (in an interval))
A function

is

continuous on a set X

continuous at each point

x X.

(i.e.,

f C (X )) if it is

Denition (Convergence of a sequence)

Let

{xn }
n=1

be an innite sequence of real numbers. The sequence

converges to x

(or has the limit

x ) if

> 0, N N, n > N : |xn x | < .

We write

x = x.

lim n
n

{xn }
n=1

Lecture Notes #01

Calculus Review

Dierentiability
Theorem

If f is a function dened on a set X R and x0 X , then the following

statements are equivalent:

(a) f is continuous at x0
(b) If {xn }
n=1 is any sequence in X converging to x0 , then limn f (xn ) = f (x0 ).

Lecture Notes #01

Calculus Review

Dierentiability
Theorem

If f is a function dened on a set X R and x0 X , then the following

statements are equivalent:

(a) f is continuous at x0
(b) If {xn }
n=1 is any sequence in X converging to x0 , then limn f (xn ) = f (x0 ).
Denition

f be a function dened on an open interval containing x0

x0 (a, b)). Then f is dierentiable at x0 if

Let

f 0 (x0 ) =
If the limit exists, we call

lim
x x0

f (x ) f (x0 )
x x0

f 0 (x0 ) a derivative of f

exists.

at

x0 .

(i.e.,

Lecture Notes #01

Calculus Review

Continuity/Rolle's Theorem

Theorem (Dierentiability

Continuity)

If f is dierentiable at x0 , then f is continuous at x0 .

Lecture Notes #01

Calculus Review

Continuity/Rolle's Theorem

Theorem (Dierentiability

Continuity)

If f is dierentiable at x0 , then f is continuous at x0 .

Theorem (Rolle's Theorem)

Suppose f C [a, b] and that f is dierentiable on (a, b). If f (a) = f (b),

then c (a, b) : f 0 (c ) = 0.

Lecture Notes #01

Calculus Review

Extreme Value Theorem

Theorem (Extreme Value Theorem)

If f C [a, b] then
m, M [a, b]x [a, b] : f (m) f (x ) f (M ).

I.e., f attains its minimum at m and maximum at M.

Moreover, if f is dierentiable on (a, b) then the numbers m, M occur either
at endpoints a, b or where f 0 (x ) = 0.

Lecture Notes #01

Calculus Review

Mean and Intermediate Value Theorem

Theorem (Mean Value Theorem)

If f C [a, b] and f is dierentiable on (a, b), then c (a, b) such that

f 0 (c ) =

f (b) f (a)
.
ba

Lecture Notes #01

Calculus Review

Mean and Intermediate Value Theorem

Theorem (Mean Value Theorem)

If f C [a, b] and f is dierentiable on (a, b), then c (a, b) such that

f 0 (c ) =

f (b) f (a)
.
ba

Theorem (Intermediate Value Theorem)

If f C [a, b] and K (f (a), f (b)), then there ex ts a number c (a, b) for

which f (c ) = K .

Lecture Notes #01

Calculus Review

Taylor's Theorem
Theorem (Taylor's Theorem)

Suppose f C [a, b], f (n+1) exists on (a, b) and x0 [a, b]. Then
x (a, b), (x0 , x ) with f (x ) = Pn (x ) + Rn (x ) where
Pn (x ) =

n
X
f (k ) (x0 )
k =0

k!

(x x0 )k ,

Rn (x ) =

f n+1 ((x ))
(x x0 )n+1 .
(n + 1)!

Pn is called the Taylor polynomial of degree n, and Rn (x ) is the

remainder term (truncation error).

Lecture Notes #01

Calculus Review

Taylor's Theorem
Theorem (Taylor's Theorem)

Suppose f C [a, b], f (n+1) exists on (a, b) and x0 [a, b]. Then
x (a, b), (x0 , x ) with f (x ) = Pn (x ) + Rn (x ) where
Pn (x ) =

n
X
f (k ) (x0 )
k =0

k!

(x x0 )k ,

Rn (x ) =

f n+1 ((x ))
(x x0 )n+1 .
(n + 1)!

Pn is called the Taylor polynomial of degree n, and Rn (x ) is the

remainder term (truncation error).
This theorem is extremely important for numerical analysis:
Taylor expansion is a fundamental step in the derivation of many of the
algorithms we see in this class.

Lecture Notes #01

Computer Arithmetic and Finite Precision

Computer Arithmetic and Finite Precision

Lecture Notes #01

Computer Arithmetic and Finite Precision

Finite Precision: A 64-bit real number, double

The

Binary Floating Point Arithmetic Standard 754-1985 (IEEE - The

Institute for Electrical and Electronics Engineers) standard specied the

following layout for a 64-bit real number:

sc10 c9 . . . c1 c0 m51 m50 . . . m1 m0

where
Symbol

Bits

Description

The sign bit: 0 = positive, 1 = negative

11

The characteristic (exponent)

52

The mantisa

r = (1)s 2c 1023 (1 + m),

c=

10
X

k =0

ck 2k ,

m=

51
X
mk

k =0

252k

Lecture Notes #01

Computer Arithmetic and Finite Precision

Finite Precision: Examples

r=

(1)s 2c 1023 (1

+ m),

c=

10
X

ck 2 ,

k =0
Remarks:
2

10

= 1024

and

(11111111111)2 = 2047.

We cannot represent zero!

m=

51
X
mk

k =0

252k

Lecture Notes #01

Computer Arithmetic and Finite Precision

Finite Precision: Examples

r=

(1)s 2c 1023 (1

+ m),

c=

10
X

ck 2 ,

k =0

m=

51
X
mk

k =0

252k

Remarks:
2

10

= 1024

and

(11111111111)2 = 2047.

We cannot represent zero!

Example 1: 3.0

0 10000000000 1000000000000000000000000000000000000000000000000000


10
1
3
(1)0 22 1023 1 +
= 1 2 1 = 3 .0
2
2

Lecture Notes #01

Computer Arithmetic and Finite Precision

Finite Precision: Examples

r = (1)s 2c 1023 (1 + m),

c=

10
X

k =0

ck 2k ,

m=

51
X
mk

k =0

252k

Example 2: The Smallest Positive Real Number

0 00000000000 0000000000000000000000000000000000000000000000000001
r

= (1)0 22

1023 1 + 1
252

= (1 + 252 ) 21022 1 10308

Lecture Notes #01

Computer Arithmetic and Finite Precision

Finite Precision: Examples

r = (1)s 2c 1023 (1 + m),

c=

10
X

ck 2k ,

k =0

m=

51
X
mk

k =0

252k

Example 2: The Smallest Positive Real Number

0 00000000000 0000000000000000000000000000000000000000000000000001
r

= (1)0 22

1023 1 + 1
252

= (1 + 252 ) 21022 1 10308

Example 3: The Largest Positive Real Number

0 11111111110 1111111111111111111111111111111111111111111111111111



1
1
1
1
= (1)0 21023 1 + + 2 + + 51 + 52
2 2
2
2



1
= 21023 2 52 10308
2

Lecture Notes #01

Computer Arithmetic and Finite Precision

Finite Precision: Consequences

There are gaps in the oating-point representation. I.e., any number in

the interval


3.0, 3.0

251

is represented by value 3.0.

Floating point numbers represents intervals!

Lecture Notes #01

Computer Arithmetic and Finite Precision

Quantifying the Error

Let

be an approximation to

p , then

Denition (The Absolute Error)

|p p |

Lecture Notes #01

Computer Arithmetic and Finite Precision

Quantifying the Error

Let

be an approximation to

p , then

Denition (The Absolute Error)

|p p |
Denition (The Relative Error)

|p p |
|p | ,

p 6= 0

Lecture Notes #01

Computer Arithmetic and Finite Precision

Sources of Numerical Errors - Roundo Errors (Rounding and

Truncating) I
Examples in 5-digit arithmetic

Rounding 5-digit arithmetic:

(96384 + 26.678) 96410 =
(96384 + 00027) 96410 =
96411

96410 = 1.0000

Lecture Notes #01

Computer Arithmetic and Finite Precision

Sources of Numerical Errors - Roundo Errors (Rounding and

Truncating) I
Examples in 5-digit arithmetic

Rounding 5-digit arithmetic:

(96384 + 26.678) 96410 =
(96384 + 00027) 96410 =
96411

96410 = 1.0000

Truncating 5-digit arithmetic:

(96384 + 26.678) 96140 =
(96384 + 00026) 96410 =
96410

96410 = 0.0000

Lecture Notes #01

Computer Arithmetic and Finite Precision

Sources of Numerical Errors - Roundo Errors (Rounding and

Truncating) II

Rearrangement changes the result:

(96384 96410) + 26.678 = 26.000 + 26.678 = 0.67800

Numerically, order of computation matters!

Lecture Notes #01

Algorithms

Algorithms

Lecture Notes #01

Algorithms

Denition (Algorithm)
An

algorithm is a procedure that describes, in an unambiguous manner, a

nite sequence of steps to be performed in a specic order.

Lecture Notes #01

Algorithms

Denition (Algorithm)
An

algorithm is a procedure that describes, in an unambiguous manner, a

nite sequence of steps to be performed in a specic order.

In this class, the objective of an algorithm is to solve a problem or
approximate a solution to a problem.
Algorithms work very similarly to the meal recipes.

Lecture Notes #01

Algorithms

Key Concepts for Numerical Algorithms  Stability

Denition (Stability)
An algorithms is said to be

stable if small changes in the input, generate

small changes in the output.

Lecture Notes #01

Algorithms

Key Concepts for Numerical Algorithms  Stability

Denition (Stability)
An algorithms is said to be

stable if small changes in the input, generate

small changes in the output.

At some point we need to quantify what small means!
If an algorithm is stable for a certain
be

conditionally stable.

range of initial data, then it is said to

Lecture Notes #01

Algorithms

Key Concepts for Numerical Algorithms  Error Growth

Suppose

E0 > 0 denotes the initial error, and En

represents the error after

operations.
If

En C E0 n

growth is
If

linear.

(for a constant

which is independat of

n), then the

En C n E0 , C > 1, the the growth is exponential  in this case the

error will dominate very fast (undesirable scenario).

Linear error growth is usually unavoidable, and in the case where C and
E0 are small the results are generally acceptable.  Stable algorithm.
Exponential error growth is unacceptable. Regardless of the size of E0 the
error grows rapidly.  Unstable algorithm.

Lecture Notes #01

Algorithms

Reducing the Eects of Roundo Error

The eects of roundo errors can be reduced by using higher-order-digit

arithmetic such as the double or multiple-precision arithmetic available on
most computers.
Disadvantages in using double precision arithmetic are that it takes more

the growth of the roundo error is not

eliminated but only postponed.

computation time and

Sometimes, but not always, it is possible to reduce the growth of the

roundo error by restructuring the calculations.

Lecture Notes #01

Algorithms

Key Concepts - Rate of Convergence

Denition (Rate of Convergence)

= {n }
n=1 converges to zero, and = {n }n=1
converges to a number .

If K > 0 : |n | < K n , for n large enough, then we say that {n }n=1

converges to with
a Rate of Convergence O(n ) (Big Oh of n ).

Suppose the sequence

We write

n = + O(n )

Lecture Notes #01

Algorithms

Key Concepts - Rate of Convergence

Denition (Rate of Convergence)

= {n }
n=1 converges to zero, and = {n }n=1
converges to a number .

If K > 0 : |n | < K n , for n large enough, then we say that {n }n=1

converges to with
a Rate of Convergence O(n ) (Big Oh of n ).

Suppose the sequence

We write

n = + O(n )

Note:

The sequence

= {n }
n =1

is usually chosen to be

n =
for some positive value of

p.

np

Lecture Notes #01

Algorithms

Rate of Convergence: Example

Consider the sequence (as

n )
 
n = sin

Then

n = O

n3

Lecture Notes #01

Algorithms

Generalizing to Limits of Functions

Denition (Rate of Convergence)
Suppose
lim
h 0
If

K > 0h < H

G (h ) = 0 ,

(for some

and lim
h0

F (h) = L.

H > 0):

|F (h) L| K |G (h)|
then

We say that

F (h) = L + O(G (h)).

F (h) converges to L with a Rate of convergence O(G (h)).

Lecture Notes #01

Algorithms

Generalizing to Limits of Functions

Denition (Rate of Convergence)
Suppose
lim
h 0
If

K > 0h < H

G (h ) = 0 ,

(for some

and lim
h0

F (h) = L.

H > 0):

|F (h) L| K |G (h)|
then

F (h) = L + O(G (h)).

We say that

Note:

F (h) converges to L with a Rate of convergence O(G (h)).

Usually we consider

G (h) = hp

for some positive

p.

Lecture Notes #01

Algorithms

Rate of Convergence: Example

Consider the function

(h) = sin(h) .

Then

(h) = O(h3 ).