Lec 13 Newton Raphson Method

Optimization Techniques
Topic: Newton-Raphson Method
Dr. Nasir M Mirza

Email: nasirmm@yahoo.com
Mathematical Background
Objective: Maximize or Minimize f(x)
subject to
d i (x) ai
ei (x) = bi
i = 1,2, , m *
Constraints
i = 1,2, , p *
x = {x1, x2, , xn}

f(x): objective function
di(x): inequality constraints
ei(x): equality constraints
ai and bi are constants
Maximize f ( x )
Minimize f ( x )
Global and Local Optima

A function is said to be multimodal on a given interval if
there are more than one minimum/maximum point in
the interval.
Characteristics of Optima
To find the optima, we can find the zeroes of f'(x).
Newtons Method
Let f(x) = g'(x). Thus the zeroes of f(x) is the optima of g(x).
Substituting f(x) into the updating formula of NewtonRahpson method, we have
f ( xi )
g ' ( xi )
xi +1 = xi
= xi
f ' ( xi )
g " ( xi )
So, Minimize g(x) = Maximize - g(x);
If g'(x) exists, then to find the optima of g(x), we
can find the zero of g'(x);
Beware of inflection points of g(x).
Newton-Raphson Method
This method is one of the most widely used methods to solve
equations also known as the Newton-Raphson.
The idea for the method comes from a Taylor series expansion,
where you know the function and its first derivative.
f(xk+1) = f(xk) + (xk+1 - xk)*f (xk) + ...
The goal of the calculations is to find a f(x)=0, so set f(xk+1) =
0 and rearrange the equation. [ f (xk) is the first derivative of
f(x). ]
0 = f(xk) + (xk+1 - xk)*f (xk)
xk+1 = xk - [ f(xk) / f (xk) ]
Newton-Raphson Method
The method uses the slope
of the line to project to the
x axis and find the root.
f(x)
f(xi)
[x f (x )]
The method converges on

the solution quickly.
i,
f(xi-1)
f(x i )
xi +1 = x i i)
f (x
x
xi+2
xi+1
xi
Derivation
f ( xi )
g' ( xi )
xi+1 = xi
= xi
f ' ( xi )
g"( xi )
f(x)
f(xi)
tan( ) =
xi+1
AB
AC
f ( xi )
f ' ( xi ) =
xi xi +1
A
x
xi
f ( xi )
xi +1 = xi
f ' ( xi )
Newton-Raphson Method:
STEP 1: Evaluate df/dx = f(x) symbolically:
that is find an analytical expression for the first derivative of the
function with respect to x.
STEP 2: Calculate the next estimate of the root
f ( xi )
g' ( xi )
xi+1 = xi
= xi
f ' ( xi )
g"( xi )
Find the absolute relative approximate error
xi +1- xi
a =
x 100
xi +1
Newton-Raphson Method:
STEP 3: Find if the absolute relative approximate

error is greater than the pre-specified relative error
tolerance.
If so, go back to step 2, else stop the algorithm.
Also check if the number of iterations has exceeded

the maximum number of iterations.
Newton-Raphson Method: Example

You are working for DOWN THE TOILET COMPANY that makes
floats for ABC commodes. The ball has a specific gravity of 0.6
and has a radius of 5.5 cm. You are asked to find the optimum
distance to which the ball will get submerged when floating in
water.
Newton-Raphson Method: Example 1

Solution: The equation that gives the depth x to which the ball is
submerged under water is given by
1 4
g ( x ) = x - 0 .055 x 3+ 3 .993 x 10 - 4 x
4
f ( x ) = g ( x ) = x 3 - 0 .165 x 2+ 3 .993 x 10 - 4
f ( x ) = 3 x 2 - 0 .33 x
Use the Newtons method of finding roots
of equations to find the optimum depth x
to which the ball is submerged under
water.
Conduct three iterations to estimate the
optimum for the above model equation.
Graph of function f(x)

0.0005
f ( x ) = x 3 - 0 .165 x 2
0.0004
0.0003
+3.993 x10 - 4
f(x)
0.0002
0.0001
0.0000
-0.0001
-0.0002
-0.0003
-0.0004
-0.02
0.00
0.02
0.04
0.06
0.08
0.10
0.12
Iteration #1
x 0 = 0 . 02
f (x 0 )
x1 = x 0
f ' (x 0 )
3 .413x 10 4
x1 = 0 . 02
5 . 4 x 10 3
= 0.08320
a = 75 . 96 %
Iteration #2
x1 = 0.08320
f ( x1 )
x2 = x1
f ' ( x1 )
1.670 x10 4
x2 = 0.08320
6.689 x10 3
= 0.05824
a = 42 .86%
Iteration #3
x 2 = 0 .05824
f (x2 )
x3 = x2
f ' (x2 )
3 .717 x10 5
= 0 .05284
9 .043 x10 3
= 0.06235
a = 6 .592 %
Newtons Method: computer algo

Do while |x2 - x1| >= tolerance value 1
or |f(x2)|>= tolerance value 2
or f(x1) ~= 0
Set x2 = x1 - f(x1)/f(x1)
Set x1 = x2;
END loop
Advantages
Converges fast, if it converges
Requires only one guess
Drawbacks
10
f(x)
f (x) = (x 1) = 0
3
0
-2
-1
1
-5
-10
-15
-20
Inflection Point
Drawbacks (continued)
1.00E-05
f(x)
7.50E-06
5.00E-06
2.50E-06
0.00E+00
-0.03
-0.02
-0.01
0
-2.50E-06
0.01
0.02
0.03
0.04
0.02
-5.00E-06
-7.50E-06
-1.00E-05
Division by zero
f ( x ) = x3 0.03x 2 + 2.4x106 = 0
f(x)
1.5
0.5
-2
-0.063069
0 0.54990
4.462
7.53982
8
10
-0.5
-1
f ( x ) = Sin x = 0
-1.5
Root Jumping
6
f(x)
f (x ) = x 2 + 2 = 0
3
2
11
4
0
-2
-1.75
-1
-0.3040
0.5
-1
Oscillations near Local Maxima or Minima
3.142
Example 2:
Let us solve the following

problem:
g(x) = x4/4 - 4x3/3 + 0.5x2 10x = 0
100
50
0
Then
f(x) =g(x) = x3 - 4x2 + x 10
df/dx = 3x2 -8 x + 1
Let us first draw a graph and see
where are the roots;
The roots are between (3,6).
Then let us write a computer
program in MATLAB that will
compute the root using NewtonRaphson method.
-50
f(x)
-100
-150
-200
-250
-300
-350
-400
-6
-4
-2
Example 2: Computer Program

%
%
%
%
%
A program that Uses Newton-Raphson method

to find the roots of x = x^3 +x^2 -3x -3
Input: x0 = initial guess;
n = number of iterations; default: n = 10;
Output: x = estimate of the root;
n = 10; x0 = 3.0
x = x0;
% Initial Guess
fprintf('
f(x)
dfdx
x(k+1)\n');
for k=1:n
f
= x^3 - 4*x^2 + x 10.0;
dfdx = 3*x^2 - 8*x + 1.0;
x
= x - f/dfdx;
fprintf('%3d %12.3e
%12.3e %18.15f\n',k-1,f,dfdx,x);
end
Example 2: results
Result of the computer program: x0 = -2.0 and iterations n = 10.
k
0
1
2
3
4
5
6
7
8
9
f(x)
-1.600e+001
1.440e+002
3.781e+001
7.716e+000
7.280e-001
9.181e-003
1.526e-006
4.796e-014
3.553e-015
3.553e-015
dfdx
4.000e+000
9.200e+001
4.613e+001
2.798e+001
2.277e+001
2.220e+001
2.219e+001
2.219e+001
2.219e+001
2.219e+001
x(k+1)
7.000000
5.434783
4.615102
4.339292
4.307327
4.306913
4.306913
4.306913
4.306913
4.306913
>>
The root value is x = 4.306913 and it was obtained after 5 iterations.
Example 2:
In this example we were finding optimum for :
g(x) = x4/4 - 4x3/3 + 0.5x2 10x = 0
Then
f(x) =g(x) = x3 - 4x2 + x 10
The root for f(x) is at x = x = 4.306913
It means g(x) = 0 at this point.
Now
df/dx = d2g/dx2 = 3x2 - 8 x + 1
and At x = 4.306913 it is positive real value.
That is d2g/dx2 > 0
which means x = 4.306913 is a local minimum
Example 3:
Let us first draw a graph and see

where are the roots;
The roots are between (0, 4).
Then let us write a computer
program in MATLAB that will
compute the root using NewtonRaphson method.
40
30
f(x)
Let us solve the following problem

of finding optimum for:
g(x) = exp(x) + 0.5 x2 10x = 0
Then
f(x) = dg/dx = exp(x) + x 10.
df/dx = exp(x) + 1.
50
20
10
-10
-20
-4
-2
Example 3: Computer Program

%
%
%
%
%
A program that Uses Newton-Raphson method

to find the roots of x = x^3 +x^2 -3x -3
Input: x0 = initial guess;
n = number of iterations; default: n = 10;
Output: x = estimate of the root;
n = 10; x0 = 0.0
x = x0;
% Initial Guess
fprintf(' k
x(k+1)\n');
f(x)
for k=1:n
f
= exp(x) + x 10.0;
dfdx = exp(x) + 1.0;
x
= x - f/dfdx;
fprintf('%3d %12.3e
%12.3e
end
dfdx
%18.15f\n',k-1,f,dfdx,x);
Example 3: results
Result of the computer program: x0 = -2.0 and iterations n = 10.
k
0
1
2
3
4
5
6
7
8
9
>>
f(x)
-9.000e+000
8.452e+001
2.914e+001
8.806e+000
1.817e+000
1.337e-001
8.746e-004
3.803e-008
0.000e+000
0.000e+000
dfdx
2.000e+000
9.102e+001
3.657e+001
1.703e+001
1.056e+001
9.048e+000
8.930e+000
8.929e+000
8.929e+000
8.929e+000
The root value is x = 2.070580
x(k+1)
4.500000
3.571415
2.774566
2.257515
2.085456
2.070678
2.070580
2.070580
2.070580
2.070580
Example 3:
In this example we were finding optimum for :
g(x) = exp(x) + 0.5 x2 10x = 0
Then
f(x) = dg/dx = exp(x) + x 10.
The root for f(x) is at x = 2.07058
It means g(x) = 0 at this point.
Now
df/dx = d2g/dx2 = exp(x) + 1. and
At x = 2.07058 it is positive real value.
That is d2g/dx2 > 0
which means x = 2.07058 is a local minimum

Lec 13 Newton Raphson Method

Uploaded by

Copyright:

Available Formats

Lec 13 Newton Raphson Method

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lec 13 Newton Raphson Method

Uploaded by

Copyright:

Available Formats

Optimization Techniques

Topic: Newton-Raphson Method

Dr. Nasir M Mirza

x = {x1, x2, , xn}

Global and Local Optima

To find the optima, we can find the zeroes of f'(x).

The method converges on

STEP 3: Find if the absolute relative approximate

If so, go back to step 2, else stop the algorithm.

Also check if the number of iterations has exceeded

Newton-Raphson Method: Example

Newton-Raphson Method: Example 1

Graph of function f(x)

Newtons Method: computer algo

Oscillations near Local Maxima or Minima

Let us solve the following

Example 2: Computer Program

A program that Uses Newton-Raphson method

The root value is x = 4.306913 and it was obtained after 5 iterations.

Let us first draw a graph and see

Let us solve the following problem

Example 3: Computer Program

A program that Uses Newton-Raphson method

The root value is x = 2.070580

You might also like