Week 3
Math505
Solution of Nonlinear Equations
Regula Falsi and Newton-Raphson
Method
Dr. BEDA T. ALETA
CILOs
C1. Recognize the importance of computers and the
role of approximations and errors in the
implementation and development of numerical
methods.
C2. Apply the different methods of error
approximation, numerical solutions (such as
Bisection, False position, Newton-Raphson) to solve
non-linear systems of equations.
Week 2<Math505>: Solution of Nonlinear Equations Bisection Method >
Outline
• Regula Falsi Method
• Solved Examples
• Newton-Raphson Method
• Solved Examples
Method of False Position
• This is another method to find the roots of
f(x)=0.
• It is also called Regula Falsi Method.
• We choose two points a and b in such a way
that f(a) and f(b) are of opposite signs
• Root lies between two points.
• Equation of chord joining two points
(a,f(a))and (b, f(b) is
MATH505 4
Method of False Position
MATH505 5
Method of False Position
(1)
• Intersection of the chord with x-axis is taken as
the approximated root.
• From figure one can see y=0. Use in equation (1)
(2)
MATH505 6
Method of False Position
• If f(x1) and f(a) are of opposite sign.
• Roots will lie between a and x1.
• Otherwise we generate the next
approximations.
• Repeat the procedure till root is obtained to
desired accuracy.
MATH505 7
Method of False Position Cont..
Example1:
MATH505 8
Method of False Position Cont..
MATH505 9
Method of False Position Cont..
MATH505 10
Method of False Position Cont..
Example2
MATH505 11
Method of False Position Cont..
MATH505 12
Method of False Position Cont..
Example 3:
MATH505 13
Method of False Position Cont..
MATH505 14
Newton-Raphson Method
Assumptions
Interpretation
Examples
15
Newton-Raphson
The Newton-Raphson method, or Newton
Method, is a powerful technique for solving
equations numerically. Like so much of the
differential calculus, it is based on the simple
idea of linear approximation.
Newton-Raphson
Most widely used method.
Based on Taylor series expansion:
∆x 2
f ( xi +1 ) = f ( xi ) + f ′( xi )∆x + f ′′( xi ) + O∆x 3
2!
The root is the value of x i +1 when f(x i +1 ) = 0
Rearranging,
Solve for
0 = f(xi ) + f ′(xi )( xi +1 − xi )
f ( xi )
xi +1 = xi − Newton-Raphson
f ′( xi )
formula
Newton-Raphson
A convenient method for
functions whose
derivatives can be
evaluated analytically.
It may not be
convenient for functions
whose derivatives
cannot be evaluated
analytically.
Newton-Raphson Method:
Geometrical Derivation:
Slope of tangent at xi is
f (x i ) − 0
f '(x i ) =
x i − x i+1
Solve for xi+1:
f (x i )
x i+=
1 xi −
f '(x i )
[Note that this is the same form as the
generalized one-point iteration, xi+1 = g(xi)]
NEWTON’S METHOD
The geometry behind Newton’s method
is shown here.
The root that we
are trying to find
is labeled r.
NEWTON’S METHOD
We start with a first approximation x1,
which is obtained by one of the following
methods:
Guessing
A rough sketch
of the graph of f
A computer-
generated graph
of f
NEWTON’S METHOD
Consider the tangent line L to the curve
y = f(x) at the point (x1,f(x1)) and look at
the x-intercept of L, labeled x2.
NEWTON’S METHOD
Here’s the idea behind the method.
The tangent line is close to the curve.
So, its x-intercept, x2 , is close to the x-intercept
of the curve
(namely, the root r
that we are seeking).
As the tangent is
a line, we can easily
find its x-intercept.
NEWTON’S METHOD
To find a formula for x2 in terms of x1,
we use the fact that the slope of L is f’(x1).
So, its equation is:
y - f(x1) = f’(x1)(x - x1)
SECOND APPROXIMATION
As the x-intercept of L is x2, we set y = 0
and obtain: 0 - f(x1) = f’(x1)(x2 - x1)
If f’(x1) ≠ 0, we can solve this equation for x2:
f ( x1 )
x2= x1 −
f '( x1 )
We use x2 as a second approximation to r.
THIRD APPROXIMATION
Next, we repeat this procedure with x1
replaced by x2, using the tangent line at
(x2,f(x2)).
This gives a third approximation:
f ( x2 )
x=
3
x2 −
f '( x2 )
SUCCESSIVE APPROXIMATIONS
If we keep repeating this process,
we obtain a sequence of approximations
x1, x2, x3, x4, . . .
SUBSEQUENT APPROXIMATION Equation/Formula 2
In general, if the nth approximation is xn and
f’(xn) ≠ 0, then the next approximation is
given by:
f ( xn )
xn +=
1 xn −
f '( xn )
NEWTON’S METHOD
Example 1
Starting with x1 = 2, find the third
approximation x3 to the root of the
equation
x3 – 2x – 5 = 0
NEWTON’S METHOD Example 1
We apply Newton’s method with
f(x) = x3 – 2x – 5 and f’(x) = 3x2 – 2
Equation becomes:
x − 2 xn − 5
3
xn + 1 = xn − n
3 xn − 2
2
NEWTON’S METHOD Example 1
With n = 1, we have:
x − 2 x1 − 5
3
x2= x1 − 1
3 x1 − 2
2
2 − 2(2) − 5
3
= 2−
3(2) − 2
2
= 2.1
NEWTON’S METHOD Example 1
With n = 2, we obtain:
x − 2 x2 − 5
3
x= x2 − 2
3 x2 − 2
3 2
2.1 − 2(2.1) − 5
3
= 2.1 −
3(2.1) − 2
2
≈ 2.0946
this third approximation x3 ≈ 2.0946
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
Iteration 1 : 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
Example : Slow Convergence
Find the positive roots of :
f(x) = x10 − 1
N - R Formula :
xi10 − 1
xi +1 = xi − use xo = 0.5
10 xi9
34
Example :
You are working for a start-up computer assembly company and
have been asked to determine the minimum number of computers
that the shop will have to sell to make a profit. The equation that
gives the minimum number of computers to be sold after
considering the total costs and the total sales is n
f (n) = 40n1.5 − 875n + 3500 = 0
Use the Newton-Raphson method of finding roots of equations to
find the minimum number of computers that need to be sold to
make a profit. Conduct three iterations to estimate the root of the
above equations. Find the absolute relative approximate error at the
end of each iteration
Solution
_______________________________
k xk f(xk)
_______________________________
0 1.0000 -1.0000
1 1.5000 8.8906
2 1.0506 -0.7062
3 1.0836 -0.4645
4 1.1472 0.1321
5 1.1331 -0.0165
6 1.1347 -0.0005
43