CS1201

Introduction to Computer Programming II

Rangeet Bhattacharyya

January 14, 2014

Root nding: bisection

x2
x1

You have a function in blue and

two initial points bracketing the

root.

Root nding: bisection

x2
x1

x3

Find the intersection of the line

joining the two points and zero
axis.

Check the sign of f (x3 ) f (x1 ).

Root nding: bisection

x2
x1

Get the new bracketing interval.

x1 x3

Root nding: bisection

x3 x2
x1

Find the middle of the bracketing

interval and

check the sign of f (x3 ) f (x1 ).

Root nding: bisection

x2
x1

Get the new bracketing interval.

x2 x3

Root nding: bisection

x3x2
x1

Find the middle of the bracketing

interval and

check the sign of f (x3 ) f (x1 )

Root nding: bisection

x1x2

Get the new bracketing interval.

x1 x3

Stop when |f (xn )| <  or

width of bracket <  or
countMaxIter

Root nding: regula falsi

x2
x1

You have a function in blue and

two initial points bracketing the

root.

Root nding: regula falsi

x2
x1

x3

Find the intersection of the line

joining the two points and zero
axis.

Check the sign of f (x1 ) f (x3 ).

Root nding: regula falsi

x2
x1

Get the new bracketing interval.

x1 x3

Root nding: regula falsi

x2
x1 x3

Find the intersection and

check the sign of f (x1 ) f (x3 ).

Root nding: regula falsi

x2
x1

Get the new bracketing interval.

x1 x3

Root nding: regula falsi

x2
xx13

Find the intersection and

check the sign of f (x1 ) f (x3 )

Root nding: regula falsi

x2
x1

Get the new bracketing interval.

x1 x3

Stop when |f (xn )| <  or

width of bracket <  or
countMaxIter

Root nding: Secant Method

x2x1

You have a function in blue

and

two initial points.

Root nding: Secant Method

y
I

x3 x2x1

Find the intersection of the

line joining the two points and
zero axis.
x
xn 1
xn = xn 1 yn 1 ynn 2
2 yn 1
You got your next guess.

Root nding: Secant Method

x4x3 x2x1

Get the new guess.

xn 2 xn 1
xn 1 xn
x
xn 1
xn = xn 1 yn 1 ynn 2
2 yn 1

Root nding: Secant Method

x5x4x3 x2x1

Get the new guess.

xn 2 xn 1
xn 1 xn
x
xn 1
xn = xn 1 yn 1 ynn 2
2 yn 1

Root nding: Secant Method

xx65x4x3 x2x1

Get the new guess.

xn 2 xn 1
xn 1 xn
x
xn 1
xn = xn 1 yn 1 ynn 2
2 yn 1

Stop when |f (xn )| < 

or countMaxIter

Root nding: Newton Raphson

x1

You have a function in blue

and

one initial point.

Root nding: Newton Raphson

x2

x1

Find the intersection of

the tangent at (x , f (x ))
and zero axis.
f (xn 1 )
xn = xn 1 f 0 (x
1)

You got your next guess.

Root nding: Newton Raphson

x3 x2

x1

Get the new guess.

xn 1 xn
f (xn 1 )
xn = xn 1 f 0 (x
1)

Root nding: Newton Raphson

x4x3 x2

x1

Get the new guess.

xn 1 xn
f (xn 1 )
xn = xn 1 f 0 (x
1)

Root nding: Newton Raphson

xx54x3 x2

x1

Get the new guess.

xn 1 xn
f (xn 1 )
xn = xn 1 f 0 (x
1)

Stop when |f (xn )| < 

or countMaxIter

Iterative methods

y
I

(x1 , 0)

Start with y = x and

y = f (x ).

Iterative methods

(x1 , x2 )

(x1 , 0)

(x2 , x2 )

Calculate xn = f (xn 1 ).
Find (xn , xn ).
Let xn 1 xn .

Iterative methods

y
(x2 , x3 )

(x1 , x2 )

(x1 , 0)

(x3 , x3 )

(x2 , x2 )

Calculate xn = f (xn 1 ).
Find (xn , xn ).
Let xn 1 xn .

Iterative methods

(x3 , x4 )
(x2 , x3 )

(x1 , x2 )

(x1 , 0)

(x4 , x4 )

(x3 , x3 )

Calculate xn = f (xn 1 ).
Find (xn , xn ).
Let xn 1 xn .

Stop when |xn xn 1 | < 

or countMaxIter

(x2 , x2 )

Summary: Root nding

Summary: Root nding

Why nd roots numerically?

Summary: Root nding

Why nd roots numerically?

Most equations cant be solved numerically.

Summary: Root nding

Why nd roots numerically?

Most equations cant be solved numerically.

For polynomial functions there can be no general solution

a root for polynomials of degree 5 or more.

Merits and demerits of the methods

Merits and demerits of the methods

I

Graph plotting
Easiest. Not accurate. Precision depends on plotter

Merits and demerits of the methods

I

Graph plotting
Easiest. Not accurate. Precision depends on plotter

Bisection
Easier, always works (for good brackets). Can be slow

Merits and demerits of the methods

I

Graph plotting
Easiest. Not accurate. Precision depends on plotter

Bisection
Easier, always works (for good brackets). Can be slow

Regular Falsi
Always work (good bracket, no sharp bend). Can be slow

Merits and demerits of the methods

I

Graph plotting
Easiest. Not accurate. Precision depends on plotter

Bisection
Easier, always works (for good brackets). Can be slow

Regular Falsi
Always work (good bracket, no sharp bend). Can be slow

Secant
Fast. Need good guesses (no extrema)

Merits and demerits of the methods

I

Graph plotting
Easiest. Not accurate. Precision depends on plotter

Bisection
Easier, always works (for good brackets). Can be slow

Regular Falsi
Always work (good bracket, no sharp bend). Can be slow

Secant
Fast. Need good guesses (no extrema)

Newton Raphson
Faster. Works for complex numbers May go into traps,
need good guess

Merits and demerits of the methods

I

Graph plotting
Easiest. Not accurate. Precision depends on plotter

Bisection
Easier, always works (for good brackets). Can be slow

Regular Falsi
Always work (good bracket, no sharp bend). Can be slow

Secant
Fast. Need good guesses (no extrema)

Newton Raphson
Faster. Works for complex numbers May go into traps,
need good guess

Iterative methods
Easy Convergence is not guaranteed.

Root nding: useful tips

I

Plotting helps. Visualization often help nd good brackets

(or starting point).

Root nding: useful tips

I

Plotting helps. Visualization often help nd good brackets

(or starting point).

For smooth functions usually Newton Raphson gives good

result.

Root nding: useful tips

I

Plotting helps. Visualization often help nd good brackets

(or starting point).

For smooth functions usually Newton Raphson gives good

result.

For functions with sharp bend or extrema within the

bracket bisection may be better choice.

Root nding: useful tips

I

Plotting helps. Visualization often help nd good brackets

(or starting point).

For smooth functions usually Newton Raphson gives good

result.

For functions with sharp bend or extrema within the

bracket bisection may be better choice.

Always start by restricting the number of iterations to

nite value.

Root nding: useful tips

I

Plotting helps. Visualization often help nd good brackets

(or starting point).

For smooth functions usually Newton Raphson gives good

result.

For functions with sharp bend or extrema within the

bracket bisection may be better choice.

Always start by restricting the number of iterations to

nite value.

Check for roots at the ends (of the bracket).

Root nding: useful tips

I

Plotting helps. Visualization often help nd good brackets

(or starting point).

For smooth functions usually Newton Raphson gives good

result.

For functions with sharp bend or extrema within the

bracket bisection may be better choice.

Always start by restricting the number of iterations to

nite value.

Check for roots at the ends (of the bracket).

Check for good bracketing interval (for bisection and

regula falsi).

Root nding: useful tips

I

Plotting helps. Visualization often help nd good brackets

(or starting point).

For smooth functions usually Newton Raphson gives good

result.

For functions with sharp bend or extrema within the

bracket bisection may be better choice.

Always start by restricting the number of iterations to

nite value.

Check for roots at the ends (of the bracket).

Check for good bracketing interval (for bisection and

regula falsi).

Good luck!