INE205
NUMERICAL ANALYSIS
NUMERICAL METHODS
Numerical Methods:
Algorithms that are used to obtain numerical solutions of
a mathematical problem.
Why do we need them?
1. No analytical solution exists,
2. An analytical solution is difficult to obtain
or not practical.
2
WHAT DO WE NEED?
Basic Needs in the Numerical Methods:
Practical:
Can be computed in a reasonable amount of time.
Accurate:
Good approximate to the true value,
Information about the approximation error (Bounds, error order,… ).
3
ACCURACY AND PRECISION
Accuracy is related to the closeness to the true
value.
Precision is related to the closeness to other
estimated values.
4
5
Error Definitions – True Error
Can be computed if the true value is known:
Absolute True Error
Et true value approximation
Absolute Percent Relative Error
true value approximation
t *100
true value
6
Error Definitions – Estimated Error
When the true value is not known:
Estimated Absolute Error
Ea current estimate previous estimate
Estimated Absolute Percent Relative Error
current estimate previous estimate
a *100
current estimate
7
ROOT FINDING
Analytical Solutions
Graphical Methods
Numerical Methods
Bracketing Methods
Open Methods
8
ROOTS OF EQUATIONS
A number r that satisfies an equation is called a root of the
equation.
The equation : x 4 3x 3 7 x 2 15 x 18
has four roots : 2, 3, 3 , and 1 .
i.e., x 4 3x 3 7 x 2 15 x 18 ( x 2)( x 3) 2 ( x 1)
The equation has two simple roots (1 and 2)
and a repeated root (3) with multiplicity 2.
9
GRAPHICAL INTERPRETATION OF ZEROS
The real zeros of a function f(x)
are the values of x at which the f(x)
graph of the function crosses (or
touches) the x-axis.
Real zeros of f(x)
10
SOLUTION METHODS
Several ways to solve nonlinear equations are possible:
Analytical Solutions
Possible for special equations only
Graphical Solutions
Useful for providing initial guesses for other methods
Numerical Solutions
Open methods
Bracketing methods
11
ANALYTICAL METHODS
Analytical Solutions are available for special equations only.
Analytical solution of : a x 2 b x c 0
b b 2 4ac
roots
2a
No analytical solution is available for : x e x 0
12
GRAPHICAL METHODS
Graphical methods are useful to provide an initial guess to
be used by other methods.
x
Solve e
2 Root
x
xe x
The root [0,1] 1
root 0.6
1 2
13
NUMERICAL METHODS
Many methods are available to solve nonlinear equations:
Bisection Method
Newton’s Method
Secant Method
14
BRACKETING METHODS
In bracketing methods, the method starts with an
interval that contains the root and a procedure is
used to obtain a smaller interval containing the
root.
Examples of bracketing methods:
Bisection method
False position method
15
OPEN METHODS
In the open methods, the method starts with one
or more initial guess points. In each iteration, a
new guess of the root is obtained.
Open methods are usually more efficient than
bracketing methods.
They may not converge to a root.
16
BISECTION METHOD
The Bisection method is one of the simplest methods to
find a zero of a nonlinear function.
To use the Bisection method, one needs an initial interval
that is known to contain a zero of the function.
The method systematically reduces the interval. It does
this by dividing the interval into two equal parts, performs
a simple test and based on the result of the test, half of
the interval is thrown away.
The procedure is repeated until the desired interval size is
obtained.
17
EXAMPLES
If f(a) and f(b) have the same
sign, the function may have an
even number of real zeros or no
real zeros in the interval [a, b]. a b
Bisection method can not be used The function has four real zeros
in these cases.
a b
The function has no real zeros
18
BISECTION METHOD
Assumptions:
Given an interval [a,b]
f(x) is continuous on [a,b]
f(a) and f(b) have opposite signs.
These assumptions ensure the existence of at least one zero in the
interval [a,b] and the bisection method can be used to obtain a
smaller interval that contains the zero.
19
BISECTION METHOD
Assumptions:
f(x) is continuous on [a,b]
f(a) f(b) < 0 f(a)
Algorithm:
c b
Loop
1. Compute the mid point c=(a+b)/2 a
2. Evaluate f(c) f(b)
3. If f(a) f(c) < 0 then new interval [a, c]
If f(a) f(c) > 0 then new interval [c, b]
End loop
20
EXAMPLE
21
EXAMPLE
Find the root of:
f ( x) x 3 3x 1 in the interval : [0,1]
* f(x) is continuous
* f( 0 ) 1, f (1) 1 f (a ) f (b) 0
Bisection method can be used to find the root
22
EXAMPLE
c= (a+b) (b-a)
Iteration a b f(c)
2 2
1 0 1 0.5 -0.375 0.5
2 0 0.5 0.25 0.266 0.25
3 0.25 0.5 .375 -7.23E-3 0.125
4 0.25 0.375 0.3125 9.30E-2 0.0625
5 0.3125 0.375 0.34375 9.37E-3 0.03125
23
FALSE POSITION METHOD
Using similar triangles, the intersection of
the straight line with the x axis can be
estimated as
which can be solved for
24
NEWTON-RAPHSON METHOD
Given an initial guess of the root x0, Newton-Raphson
method uses information about the function and its
derivative at that point to find a better guess of the
root.
Assumptions:
f(x) is continuous and the first derivative is known
An initial guess x0 such that f ’(x0)≠0 is given
25
NEWTON RAPHSON METHOD
26
NEWTON’S METHOD
The Newton-Raphson method can be derived on the basis of this
geometrical interpretation. The first derivative at x is equivalent to the
slope:
27
EXAMPLE
Find a zero of the function f(x) x 3 2 x 2 x 3 , x0 4
f ' (x) 3 x 2 4 x 1
f ( x0 ) 33
Iteration1 : x1 x0 4 3
f ' ( x0 ) 33
f ( x1 ) 9
Iteration 2 : x2 x1 3 2.4375
f ' ( x1 ) 16
f ( x2 ) 2.0369
Iteration 3 : x3 x2 2.4375 2.2130
f ' ( x2 ) 9.0742
28
SECANT METHOD
A potential problem in implementing the Newton-Raphson method is the
evaluation of the derivative. Although this is not inconvenient for polynomials
and many other functions, there are certain functions whose derivatives may
be extremely difficult or inconvenient to evaluate. For these cases, the
derivative can be approximated by a backward finite divided difference, as
in:
29
SECANT METHOD
This approximation can be substituted into Eq. to
yield the following iterative equation
This equation is the formula for the secant method. Notice that the
approach requires two initial estimates of x. However, because f(x)
is not required to change signs between the estimates, it is not
classified as a bracketing method.
30
LINEAR ALGEBRAIC
EQUATIONS
31
LINEAR ALGEBRAIC
EQUATIONS
We deal with linear algebraic equations that are
of the general form
where the a’s are constant coefficients, the b’s are constants, and n is
the number of equations. All other equations are nonlinear.
32
SOLVING SMALL NUMBERS OF
EQUATIONS
we will describe several methods that are
appropriate for solving small (n ≤ 3) sets of
simultaneous equations and that do not require a
computer. These are
the graphical method,
Cramer’s rule, and
the elimination ofunknowns
33
THE GRAPHICAL METHOD
34
THE GRAPHICAL METHOD
35
DETERMINANTS AND CRAMER’S RULE
Determinants
For the third-order case
36
CRAMER’S RULE
37
THE ELIMINATION OF UNKNOWNS
The elimination of unknowns by combining
equations is an algebraic approach that can be
illustrated for a set of two equations:
38
