Motilal Nehru National Institute of Technology

Civil Engineering Department

Computer Based Numerical Techniques

CE-401

Roots of the equations: Open Methods

Open Methods
Bracketing methods are based on assuming an
interval of the function which brackets the root.
The bracketing methods always converge to the
root.
Open methods are based on formulas that
require only a single starting value of x or two
starting values that do not necessarily bracket
the root.
These method sometimes diverge from the true
root.

1. Simple Fixed-Point Iteration

Rearrange the function so that x is on

the left side of the equation:
f ( x) 0 g ( x) x
xi 1 g ( xi )

Bracketing methods are convergent.

Fixed-point methods may sometime diverge,
depending on the stating point (initial guess) and
how the function behaves.

Simple Fixed-Point Iteration

Examples:
1. f ( x) x 2 x 2

x0

g ( x) x 2 2
or
g ( x) x 2
or

2.
3.
3.

2
g ( x) 1
x
f(x) = x 2-2x+3 x = g(x)=(x2+3)/2
f(x) = sin x x = g(x)= sin x + x
f(x) = e-x- x x = g(x)= e-x

Simple Fixed-Point Iteration Convergence

x = g(x) can be
expressed as a pair of
equations:
y1= x
y2= g(x). (component
equations)
Plot them separately.

Simple Fixed-Point Iteration Convergence

Fixed-point iteration converges if :

g (x ) 1

(slope of the line f (x ) x )

When the method converges, the error

is roughly proportional to or less than the

error of the previous step, therefore it is
called linearly convergent.

Simple Fixed-Point Iteration-Convergence

Steps of Simple Fixed Pint Iteration

1. Rearrange the equation f(x) = 0 so that x is
on the left hand side and g(x) is on the right
hand side.
e.g f(x) = x2-2x-1 = 0 x= (x2-1)/2
g(x) = (x2-1)/2

2. Set xi at an initial guess xo.

3. Evaluate g(xi)
4. Let xi+1 = g(xi)
5. Find a=(Xi+1 xi)/Xi+1, and set xi at xi+1
6. Repeat steps 3 through 5 until |a|<= s

Example: Simple Fixed-Point Iteration

f(x) = e-x - x

f(x)
f(x)=e-x - x

1. f(x) is manipulated so that we get

x=g(x) g(x) = e-x

2. Thus, the formula predicting the
new value of x is: xi+1 = e-xi
3. Guess xo = 0
4. The iterations continues till the

approx. error reaches a certain

limiting value

Root

f(x)

f1(x) = x
g(x) = e-x

Example: Simple Fixed-Point Iteration

i

xi

g(xi)

0
1
2
3
4
5
6
7
8
9
10

0
1.0
0.367879
0.692201
0.500473
0.606244
0.545396
0.579612
0.560115
0.571143
0.564879

1.0
0.367879
0.692201
0.500473
0.606244
0.545396
0.579612
0.560115
0.571143
0.564879

a%

t%

100
171.8
46.9
38.3
17.4
11.2
5.90
3.48
1.93
1.11

76.3
35.1
22.1
11.8
6.89
3.83
2.2
1.24
0.705
0.399

Example: Simple Fixed-Point Iteration

i

xi

g(xi)

0
1
2
3
4
5
6
7
8
9
10

0
1.0
0.367879
0.692201
0.500473
0.606244
0.545396
0.579612
0.560115
0.571143
0.564879

1.0
0.367879
0.692201
0.500473
0.606244
0.545396
0.579612
0.560115
0.571143
0.564879

a%

t%

100
171.8
46.9
38.3
17.4
11.2
5.90
3.48
1.93
1.11

76.3
35.1
22.1
11.8
6.89
3.83
2.2
1.24
0.705
0.399

Example

Flow Chart Fixed Point

Start

Input: xo , s, maxi

i=0
a=1.1s

1
while
a< s &
i >maxi
x n g x 0

False

Print: xo, f(xo) ,a , i

i i 1

xn=0

True

x n xo
100%
xn

x0=xn

Stop

2. The Newton-Raphson Method

Most widely used method.

Based on Taylor series expansion:
2
x
f ( xi 1 ) f ( xi ) f ( xi )x f ( xi )
...
2!
The root is the value of xi 1 when f(xi 1 ) 0
Solve for
Rearranging,
0 f(xi ) f (xi )( xi 1 xi )
f ( xi ) Newton-Raphson formula
xi 1 xi
f ( xi )

The Newton-Raphson Method

A tangent to f(x) at the

initial point xi is extended f(x)
till it meets the x-axis at f(xi)
the improved estimate of
Slope f /(xi)
f(x)
the root xi+1.
x
Root
xi+1
The iterations continues
xi
till the approx. error
f ( xi ) 0
/
f ( xi )
reaches a certain limiting
xi xi 1
value.
f ( xi )
xi 1 xi

f / ( xi )

Example: The Newton Raphson Method

Use the Newton-Raphson method to find the
root of e-x-x= 0 f(x) = e-x-x and f`(x)= -e-x-1;
thus
x
x
f ( xi )
e x
e x
xi 1 xi /
xi x
xi x
f ( xi )
e 1
e 1

Iter.
0
1
2
3
4

xi
0
0.5
0.566311003
0.567143165
0.567143290

t%
100
11.8
0.147
0.00002
<10-8

Flow Chart Newton Raphson

Start

Input: xo , s, maxi

i=0
a=1.1s

1
while
a >s &
i <maxi

xn x0

False

f x 0
f

'

x 0

Print: xo, f(xo) ,a , i

i i 1

xn=0

True

x n xo
100%
xn

x0=xn

Stop

M-file for Newton Raphsons Method

function [root,ea,iter]=newtraph(func, dfunc, xr, es, maxit, varargin)
% newtraph: Newton-Raphson root location zeroes
% [root,ea,iter]=newtraph(func,dfunc,xr,es,maxit,p1,p2,...):
% uses Newton-Raphson method to find the root of func
% input:
% func = name of function
% dfunc = name of derivative of function
% xr = initial guess
% es = desired relative error (default = 0.0001%)
% maxit = maximum allowable iterations (default = 50)
% p1,p2,... = additional parameters used by function
% output:
% root = real root
% ea = approximate relative error (%)
% iter = number of iterations

M-file for Newton Raphsons Method

if nargin<3,error('at least 3 input arguments required'),end
if nargin<4|isempty(es),es=0.0001;end
if nargin<5|isempty(maxit),maxit=50;end
iter = 0;
while (1)
xrold = xr;
xr = xr - func(xr)/dfunc(xr);
iter = iter + 1;
if xr ~= 0, ea = abs((xr - xrold)/xr) * 100; end
if ea <= es | iter >= maxit, break, end
end
root = xr;

Pitfalls of The Newton Raphson Method

Cases where Newton Raphson method diverges or exhibit poor

convergence.
a) Reflection point
c) Near zero slope , and

b) oscillating around a local optimum

d) zero slope

Example Newton Raphsons Method

Evaluate 29 to five decimal places by NewtonRaphsons iterative method

Solution
Evaluate 29 to five decimal places by NewtonRaphsons iterative method

Solution

3. The Secant Method

The derivative f / ( x i ) is
sometimes difficult to evaluate
by the computer program. It
may be replaced by a backward
finite divided difference

f (x i ) f (x i 1 )
f (x i )
x i x i 1
/

Thus, the formula

predicting the xi+1 is:

xi 1

f ( xi )( xi 1 xi )
xi
f ( xi 1 ) f ( xi )

The Secant Method

Requires two initial estimates of x , e.g,

xo, x1.
However, because f(x) is not required to change
signs between estimates, it is not classified as a
bracketing method.

The scant method has the same properties as

Newtons method. Convergence is not
guaranteed for all xo, x1, f(x).

Secant Method: Example

Determine a root of the equation sin x + 3 cos x 2 = 0
using the secant method. The initial approximations
x0 and x1 are 0 and 1.5.

Comparison of convergence of False Position and

Secant Methods
False Position
x r xu

f (x u )(x l x u )
f (x l ) f (x u )

Use two estimate xl and xu

Secant Method
x i 1 x i

f (x i )(x i 1 x i )
f (x i 1 ) f (x i )

Use two estimate xi and xi-1

f(x) must changes signs between xl f(x) is not required to change signs
between xi and xi-1
and xu
Xr replaces whichever of the original
values yielded a function value with
the same sign as f(xr)

Xi+1 replace xi
Xi replace xi-1

Always converge

May be diverge

Slower convergence than Secant in

case the secant converges.

If converges, It does faster then False

Position

Comparison of convergence of False Position and

Secant Methods

Use the false-position and secant method to find the root of

f(x)=logex. Start computation with xl= xi-1=0.5, xu=xi = 5.
1.
False position method
Iter
1
2
3

xl
0.5
0.5
0.5

xu
5.0
1.8546
1.2163

xr
1.8546
1.2163
1.0585

Secant method

2.

Iter

xi-1

xi

0.5

5.0

1.8546

xi+1
1.8546
-0.10438

 Comparison of
the true percent
relative Errors Et
for the methods
to the determine
the root of
f(x)=e-x-x

Flow Chart Secant Method

Start

Input: x-1 , x0,s, maxi

i=0
a=1.1s

1
while
a >s &
i < maxi

x i 1 x i

f (x i )(x i 1 x i )
f (x i 1 ) f (x i )

False

Print: xi , f(xi) ,a , i

i i 1

Xi+1=0

True

x i 1 x i
100%
x i 1

Xi-1=xi
Xi=xi+1

Stop

Modified Secant Method

Rather than using two initial values, an alternative
approach is using a fractional perturbation of the
/
f
independent variable to estimate (x i )

f (x i x i ) f (x i )
f (x i )
xi
/

is a small perturbation fraction

x i 1

x i f (x i )
xi
f (x i x i ) f (x i )

Modified Secant Method: Example

Use the modified secant method to find the root of
f(x) = e-x-x and, x0=1 and =0.01
First Iteration
x 0 1

f x 0 0.63212

x 0 x 0 1.01

f x 0 x 0 0.64578

x 1 x i 1 x i

x i f (x i )
0.537263
f (x i x i ) f (x i )

t 5.3%

Second Iteration
x 1 0.537263
x 1 x 1 0.542635

f x 1 0.047083
f x 1 x 1 0.038579

x i f (x i )
x 2 x i 1 x i
0.56701
f (x i x i ) f (x i )

t 0.0236%

Multiple Roots
f(x)= (x-3)(x-1)(x-1)(x-1)
= x4- 6x3+ 125 x2- 10x+3

f(x)= (x-3)(x-1)(x-1)
= x3- 5x2+7x -3
f(x)

f(x)
Double roots
1

triple roots

3
x

Multiple Roots

Multiple root corresponds to a point

where a function is tangent to the x axis.
Difficulties
- Function does not change sign with double
(or even number of multiple root), therefore,
cannot use bracketing methods.
- Both f(x) and f(x)=0, division by zero with
Newtons and Secant methods which may
diverge around this root.

4. The Modified Newton Raphson Method by

Ralston and Rabinowitz
Another u(x) is introduced such that u(x)=f(x)/f /(x);
Getting the roots of u(x) using Newton Raphsons
technique:
This function has roots
at all the same locations
as the original function

u ( xi )
xi 1 xi /
u ( xi )
/
/
//
f
(
x
)
f
(
x
)

f
(
x
)
f
( xi )
/
i
i
i
u ( xi )
[ f / ( xi )]2

xi 1 xi

f ( xi ) f ( xi )
/

( xi ) f ( xi ) f // ( xi )

Modified Newton Raphson Method: Example

Using the Newton Raphson and Modified Newton
Raphson evaluate the multiple roots of
f(x)= x3-5x2+7x-3 with an initial guess of x0=0
Newton Raphson formula:

xi 1

f ( xi )
xi3 5 xi2 7 xi 3
xi /
xi
f ( xi )
3 xi2 10 x 7

Modified Newton Raphson formula:

xi 1 xi

f ( xi ) f / ( xi )

( x ) f ( x ) f
2

//

( xi )

( xi3 5 xi2 7 xi 3)(3 xi2 10 xi 7)

xi
(3 xi2 10 xi 7) 2 ( xi3 5 xi2 7 xi 3)(6 xi 10)

Modified Newton Raphson Method: Example

Newton Raphson
Iter
xi
0
0
1
0.4286
2
0.6857
3
0.83286 17
4
0.91332 8.7
5
0.95578 4.4
6
0.97766 2.2

t%
100
57
31

Modified Newton-Raphson
iter
xi
t%
0
0
100
1
1.10526
11
2
1.00308
0.31
3
1.000002
00024

Newton Raphson technique is linearly converging towards the

true value of 1.0 while the Modified Newton Raphson is
quadratically converging.
For simple roots, modified Newton Raphson is less efficient
and requires more computational effort than the standard
Newton Raphson method

Systems of Nonlinear Equations

Roots of a set of simultaneous equations:

f1(x1,x2,.,xn)=0
f2 (x1,x2,.,xn)=0
fn (x1,x2,.,xn)=0
The solution is a set of x values that
simultaneously get the equations to zero.

Systems of Nonlinear Equations

Example: x2 + xy = 10 & y + 3xy2 = 57
u(x,y) = x2+ xy -10 = 0
v(x,y) = y+ 3xy2 -57 = 0

The solution will be the value of x and y which makes

u(x,y)=0 and v(x,y)=0

These are x=2 and y=3

Numerical methods used are extension of the open

methods for solving single equation; Fixed point
iteration and Newton-Raphson. (we will only discuss
the Newton Raphson)

Systems of Nonlinear Equations:

2. Newton Raphson Method

Systems of Nonlinear Equations:

2. Newton Raphson Method

Systems of Nonlinear Equations:

2. Newton Raphson Method
x 2+ xy =10 and y + 3xy 2 = 57
are two nonlinear simultaneous equations with two unknown x and y they can
be expressed in the form: use the point (1.5,3.5) as initial guess.

u
u
2 x y,
x
x
y
v
v
3y2 ,
1 6 xy
x
y
i

xi

yi

Ui

Vi

ui,x

ui,y

vi,x

vi,y

1.5

3.5

-2.5

1.625

6.5

1.5

36.75

32.5

2.03603

2.84388

-.06435

-4.7560

6.91594

2.03603

24.26296

35.74135

1.9987

3.00229

a,x

a,y

26.3

23.1

1.87

5.27

Systems of Nonlinear Equations:

2. Newton Raphson Method
i

xi

yi

Ui

Vi

ui,x

ui,y

vi,x

vi,y

1.5

3.5

-2.5

1.625

6.5

1.5

36.75

32.5

2.03603

2.84388

-.06435

-4.7560

6.91594

2.03603

24.26296

35.74135

1.9987

3.00229

a,x

a,y

26.3

23.1

1.87

5.27

Problem
The polynomial f (x) = x3 -6x2 +11x- 6.1 has a real root
between 3 and 5. Apply the Newton-Raphsons method to
this function using an initial guess of x0 = 3.5. Explain your
results

Problem
The polynomial f (x) = x3 -6x2 +11x- 6.1 has a real root
between 3 and 5. Apply the Newton-Raphsons method to
this function using an initial guess of x0 = 3.5. Explain your
results

Problem
The polynomial f (x) = x3 -6x2 +11x- 6.1 has a real root
between 3 and 5. Apply the Newton-Raphsons method to
this function using an initial guess of x0 = 3.5. Explain your
results

Problem
The polynomial f (x) = x3 -6x2 +11x- 6.1 has a real root
between 3 and 5. Apply the Newton-Raphsons method to
this function using an initial guess of x0 = 3.5. Explain your
results

Problem
Find the root of polynomial f (x) = x3 -6x2 +11x- 6.1. Apply
the Secants method to this function using an initial guess
of x-1= 2.5 and x0 = 3.5.

Problem
Find the root of polynomial f (x) = x3 -6x2 +11x- 6.1. Apply
the Secants method to this function using an initial guess
of x-1= 2.5 and x0 = 3.5.

Problem
Find the root of polynomial f (x) = x3 -6x2 +11x- 6.1. Apply
the Secants method to this function using an initial guess
of x-1= 2.5 and x0 = 3.5.