plik

NUMERICAL METHODS

AND PROGRAMMING

BASIC CONCEPTS AND FIELDS OF

APPLICATIONS OF NUMERICAL

ANALYSIS

Joanna Iwaniec

SHORT

HISTORY OF NUMERICAL

ANALYSIS

2000 years ago -

inear interpolation

was already in use …

Works of great mathematicians on numerical analysis →

important

algorithms:

Newton's

method

Newton's

method

Lagrange

interpolation polynomial, Gaussian elimination, Euler's

method

, etc.

Books containing formulas, tables of data such as interpolation
points and function coefficients, making it possible to:

look up values to plug into the formulas given and achieve
very good numerical estimates of some functions.

Invention of

mechanical calculator

for hand computation.

1940s - invention of electronic computers.

BASIC CONCEPTS AND

DEFINITIONS

BASIC DEFINITIONS

NUMERICAL ANALYSIS

the study of approximation

techniques for solving mathematical problems, taking into account
the extent of possible errors.

NUMERICAL ANALYSIS

the study of

algorithms

for the

problems of continuous mathematics. Example areas of interest are:

real variable or complex variable questions,

numerical linear algebra,

solution of

differential equations

other problems arising in the physical sciences and engineering.

ALGORITHM

step-by-step

problem-solving

procedure,

especially an established, recursive computational procedure for
solving a problem in a finite number of steps

NUMERICAL PROBLEM / ALGORITHM

NUMERICAL PROBLEM

: clear and unequivocal description of

functional relation between

input data

(independent data) and

output

data

(problem solution).

•

INPUT / OUTPUT DATA

consist of finite number of real /

conjugant values and can be represented in the form of finite-
dimensional vectors.

ALGORITHM

: for a given numerical problem - a complete

description of operations transforming vector of input data into vector
of output data.

•

OPERATION

: arithmetic or logical operation that can be

performed by a computer as well as calls for previously defined
algorithms.

WHY DO WE USE NUMERICAL ANALYSIS?

Many problems in continuous mathematics do not possess a

closed

form solution

EXAMPLES

finding the

integral

of exp(-x

) ,

solving a general

polynomial

equation of degree five or higher.

In these situations, one has two options left:

try to find an approximate solution using

asymptotic analysis

seek a numerical solution

e latter choice describes the field of numerical

analysis

DIRECT METHOD

: an algorithm providing the exact

solution of a given problem.

Examples

Gaussian elimination

for solving

systems of linear equations

simplex method

linear programming

For most problems no direct methods exist . In such cases
it is sometimes possible to use an

iterative method

ITERATIVE METHOD

: method starting from a guess

and finds successive approximations that hopefully

converge

to the solution.

Even when a direct method does exist, an iterative method
may be preferable because it is more efficient or more stable

DIRECT AND ITERATIVE METHODS

ITERATION:

repeating certain model activity or process.

EXAMPLE:

iterative method of solving equation in the following

form:

x = F(x)

where: F: differentiable function, which values can be calculated for
an arbitrary value of variable x (from a given band).

By the use of iterative method, starting from initial approximation x

the following sequence is calculated:

= F(x

), x

= F(x

), x

= F(x

), ...

where: x

n+1

= F(x

): iteration.

If the sequence {x

} is convergent to limit value α, then:

ITERATIVE METHODS

⇔

)

(

)

(

)

(

lim

satisfies

⇔

DISCRETIZATION

•

DISCRETIZATION:

process

replacing

the

continuous problem by a discrete problem whose solution
is known to approximate that of the continuous problem.

XAMPLE

• the solution of a

differential equation

is a function. This

function must be represented by a finite amount of data,
for instance by its value at a finite number of points at its
domain, even though this domain is a continuum.

NUMERICAL REPRESENTATION

BINARY SYSTEM

FLOATING POINT NOTATION

NUMERICAL REPRESENTATION

Numerical data

: written in basic units of storage made up of a fixed

number of consecutive bits.

The most commonly used units:

byte (8 consecutive bits),
the word (16 consecutive bits),
double word (32 consecutive bits)

Number:

is represented (in each unit type) by setting the bits

according to the binary representation of the number.

Bits in a byte

are numbered, from right to left, beginning with 0.

The rightmost bit

(numbered 0) is called the least significant bit

The leftmost bit

(numbered 7) is called the most significant bit.

Higher units

are numbered also from right to left: the rightmost bit

is labeled 0 and the leftmost bit is labeled (n ? 1), where n is the
number of bits available.

NUMERICAL REPRESENTATION

Since each bit may have one of two values, 0 or 1,

bits

can represent

different unsigned numbers.

To represent positive or negative numbers, one of the bits
is chosen as the

sign bit

Usually, the

leftmost bit

(or most significant bit) is

considered the

sign bit

In the sign bit:

0 - positive number, 1- negative one

Similar convention is followed for higher storage units,
including words and double words.

Since each position indicates a specific power of 2,e.g.:

342 = (3 × 102) + (4 × 101) + (2 × 100)

decimal equivalent of a binary number can be calculated by adding
together each digit multiplied by its power of 2, e.g.:

binary number 1011010 ↔ (1 × 26) + (0 × 25) + (1 × 24) + (1 × 23) +
+ (0 × 22) + (1 × 21) + (0 × 20) = 64 + 0 + 16 + 8 + 0 + 2 + 0 = 90 in the
decimal system.

Binary numbers

are sometimes written with a subscript “b” to distinguish

them from decimal numbers having the same digits.

In computer applications

, any binary digit, or bit, can be transmitted and

recorded electronically simply by the presence or absence of an electrical
pulse or current.

BINARY SYSTEM

Binary system

: system based on powers of 2, in which only the

digits 0 and 1 are used.

Floating-point notation

In computer systems, real numbers

are stored as:

x = M * N

where:

M – mantissa of number x

W – exponent

(in Polish:

‘wykładnik części potęgowej’),

N – base of power

(in Polish:

‘podstawa potęgi’).

Base N

: 2 or 10 (usually 2)

In the floating point notation real number is represented by two

groups of bits:

M (0.5 ≤ M < 1): interpreted as fractional part (‘część

ułamkowa’),

W: interpreted as integer (‘liczba całkowita’)

Errors of floating point notation

Assuming that:

x – certain number in decimal system,

x’ – floating-point representation of x

Absolute error:

|x – x’|

(‘błąd bezwzgldny’):

Relative error:

e’

such that

x’ = x(1 + e’)

In computer systems it is possible to increase the precision of

computations by usage of so called ‘

double precision

’ (

In DP, M and W are represented by

twice

as many bits as

normally, which reduces relative error according to relation:

= e

Floating-point notation

Example 1

: the following notation:

x = (1)1101

(0)10

in binary system equals:

-0,1101 * 2

+10

= -(1/2 + 1/4 + 0/8 + 1/16) * 2

+(1*2 +0*1) =

= -3,25

GENERATION AND

PROPAGATION OF ERRORS

GENERATION AND PROPAGATION OF

ERRORS

There are several ways in which error can be introduced in the
solution of the problem:

Round

off errors

arise because it is impossible to represent all

real

numbers

exactly on a

finite-state machine

(which is what all practical

digital computers

are).

Truncation

errors

are committed when an iterative method is

terminated

and the approximate solution differs from the exact

solution.

iscretization error

result from discretization process since the

solution of the discrete problem does not coincide with the solution of
the continuous problem.

GENERATION OF ERRORS

EXAMPLES

Rounding error:

difference between the calculated approximation

of a number and its exact mathematical value.

In numerical analysis

rounding error

is estimated when using

approximation equations / algorithms, especially when using finite
digits to represent infinite digits of real numbers.

EXAMPLE:

GENERATION OF ERRORS

–

EXAMPLES

•The length of representation is unimportant.
•If a representation has finitely many digits, there will be error for

uncountably many

real numbers.

This kind of error is unavoidable for conventional representations of

numbers

• The most popular ways of performing the

termination at the limited

digit place

•

truncation

: simply chop off the remaining digits.

0,142857 ≈ 0,142 (

chopping

at the 5th digits.)

•

rounding:

add 5 to the next digit and then chop it.

0,142857 ≈ 0,143 (

rounding up

at the 5th digits)

0,142857 ≈ 0,14 (

rounding down

at the 4th digits)

PROPAGATION OF ERRORS

Once an error is generated, it will generally

propagate

through

the calculation.

This leads to the notion of

numerical stability

An algorithm is numerically stable if an error, once it is generated,
does not grow too much during the calculation.

Only well-conditioned problems can be numerically stable.

The problem is said to be

well-conditioned

if the solution changes

by only a small amount if the problem data are changed by a small
amount. If a problem is

ill-conditioned

, even small data errors

result in significant solution errors.

NUMERICAL STABILITY

WELL

POSED PROBLEMS

WELL

CONDITIONED PROBLEMS

NUMERICAL STABILITY, WELL

POSED

WELL

CONDITIONED PROBLEMS

An algorithm that solves a

well-conditioned problem

may or

may not be

numerically stable

An art of numerical analysis is:

to find a

stable algorithm

for solving a

well-posed

mathematical problem.

to find

stable algorithms

for solving

ill-posed problems

Ill-posed problem

solving: finding a well-posed problem

whose solution is close to that of the ill-posed problem and
solving this well-posed problem instead.

Mathematical model of a physical phenomena is

well-posed

(according

to definition given by Hadamard) if:

Its solution exists,
The solution is unique,
The solution depends continuously on the data.

WELL

POSED PROBLEM

Problems that are

not well-posed

on the sense of Hadamard are

termed

ill-posed

. (Inverse problems are often ill-posed).

A measure of

well-posedness

of a discrete linear problem is the

condition number

If a problem is

well-posed

, its solution can be find on a computer

using a stable algorithm.

If it is

ill-posed

, it needs to be re-formulated (

regularized

) for

numerical treatment (e.g. additional assumptions, such as smoothness of
solution, should be made).

APPLICATIONS OF NUMERICAL ANALYSIS

Algorithms of numerical analysis

are applied to solve many

problems in science and engineering, e.g. to:

design of structures like bridges and airplanes,
weather forecasting, climate models,
analysis and design of molecules (computational chemistry).

Almost all

supercomputers

are continually running numerical

analysis algorithms.

Since efficiency plays an important role, a heuristic method may be

preferred above a method with a solid theoretic foundation because it
is more efficient.

Generally, numerical analysis uses

empirical

results

computation runs to probe new methods and analyze problems,
though it of course also employs

mathematical

axioms

theorems

and

proofs

‘

DISCIPLINES

’

OF NUMERICAL ANALYSIS

According to the problem that is to be solved, numerical analysis

can be divided into different disciplines, e. g.:

Computing values of functions

Curve fitting

Interpolation, approximation

Solving equations and systems of equations

Optimization

Evaluating integrals

Differential equations

Solving eigenvalue problems

Thank you for your attention!

Differential equation

: an equation that expresses a relationship

between functions and their derivatives.

Polynomial

: mathematical expression which is a finite sum, each

term being a constant times a product of one or more variables raised

to powers. With only one variable the general form of a polynomial

is:

+ a

n−1

n−2

+ ... + a

n−1

x + a

where n: is a positive integer, a

, a

,..., a

are any numbers.

Degree of a polynomial:

in one variable is the highest power of

the variable appearing with a nonzero coefficient.

DIFFERENTIAL EQUATION / POLYNOMIAL

DEFINITIONS

CLOSED

FORM SOLUTION

quation

/ system of equations is said to have a closed

form

solution

if, and only if, at least one solution can be expressed

analytically in terms of a bounded number of

well

known operations.

Traditionally, the

well

known functions

were limited to the

elementary functions.

EXAMPLE:

two roots of a quadratic equation, which can be expressed

in closed form in terms of addition and subtraction, multiplication and
division, and square root extraction.

When no closed

form solutions exist

(e. g. in case of 5

order or

higher polynomial

equations), equations have to be solved

numerically

, typically by using some

root

finding algorithm.

ASYMPTOTIC ANALYSIS

symptotic analysis

a method of classifying limiting behaviour, by

concentrating on some trend. It is sometimes expressed in the
language of

equivalence relations

EXAMPLE

: given complex-valued functions f and g of a natural

number variable n, one can write

This defines an equivalence relation; and the equivalence class of f
consists of all functions g with similar behaviour to f, in the limit.

to express the concept that