Change of sign method --- interval bisection method

Where (a, b) is the interval of the root.

The graph below shows what I am actually doing. Every time I am using the middle value x of the interval, and find the corresponding y value, then I will get a new but a smaller range. The more steps I do, then closer to the exact root value I will get.

from the results I get from the spreadsheet, the root lies between the interval (1.88500977, 1.88525391),

error bound = 0.00012207

root = 1.88513184 ± 0.00012207

Occasions in which the interval bisection causes problems:

Although in the example above the interval bisection method worked fairly well, there are some cases in which it does not work.

1) One of the condition is that when there are several roots in one interval chosen. For example, y = (x-0.1)(x-0.2)(x-0.25)+1

From this graph we choose the interval as (0,1), then calculate f(0.5), then f(0.25), f(0.125), finally arriving at the root x=0.1. Indeed, there is one root at x=0.1, but also, if we look closer to the graph

In the interval (0,1) there are another two roots. In other words, we are going to miss out the other two roots.

2) The other occasion in which the interval bisection method does not work is when the graph actually “touches” the x axis, but not crossing it, for example

y = (x-2)2(x-4)2

in this case there is no change of sign of f(x), f(x) ≥ 0, the curve is positive everywhere apart from two points where it touches Newton-Raphson Method the x-axis, at 2 and 4. Any search in interval bisection method is unlikely to find these points out, i.e. they are undetected, so the interval bisection method fails in this case.

Newton – Raphson Method

Introduction:

In the Newton-Raphson Method we are actually using the tangents of the curves.  For this method, it is necessary to use an estimate of the root as a starting point.

For example, for the curve shown above, to find the root of the curve, we made a first guess A; then put A in to the equation f(x), find f(A) and f’(A), while f’(A) is going to be the gradient when x=A. Use the coordinate of (A, f(A)) to find out the equation of the tangent when x=A, hence find out the x value at which the tangent crosses the x-axis, the x value will be my next guess, i.e. B in the graph above.

In a word, in the Newton-Raphson method, the equation f(x)=0 is solved using the iteration:

for this method, I am going to use the equation f(x):

y= 3(x-1)(x+1)(x+3)+1

From the graph we can see that there are three roots for f(x)=0 lying in the intervals (-4,-3); (-1,0); (0,1)

I will show how to find the root in (-4,-3) using Newton-Raphson method on autograph:

For this method, my first guess is x=-3.5

on the graph, it shows that when x=-3.5, its tangent at that point cut the x-axis at the point (-3.141, 0), hence my next guess is going to be

-3.141. Continue using the same method, I am going to get a graph as following:

 On the graph it shows that finally when x= -3.04, the value of f(x) ≈0, hence the root should be -3.04 with an accuracy up to two decimal places.

I am going to find out the rest of the two roots using a spreadsheet.

1) for the root lying in the interval (-1,0):

The formula I used in the spreadsheet are shown below:

From the results I get from the spreadsheet, I can see the root lying between the interval (-1,0) is -0.916521.

2) For the root lying between the interval (0,1):

The formula I used in the spread sheet are shown below:

From the results I get from the spreadsheet, I can see the root lying between the interval (0,1) is 0.956954.

Problems with Newton-Raphson method:

There are some cases in which the Newton-Raphson method does not work:

1. The function is discontinuous, for example:

y=-1/x +2

If the graph is discontinuous, and unfortunately I’ve chosen a starting point near the edge of one part of the graph, using the Newton-Raphson method, the next guess will go to the other side of the graph, getting further and further away from the root we are looking for.

2) Poor choice of starting value. If my initial value is quite far way from a root, the iteration may be divergent, i.e. moving away from the root. For example:

    y= x(x-1)(x-2)+1

Using Newton-Raphson method with the first guess x=0.5, from the graph below we can see that actually our second guess is getting further away from the chosen root, so this method failed.

2. if my initial value is near a turning point of y=f(x), the iteration will diverge as well. For example:

y=(x-2)(x-1)x+1

For this equation, there is a station point of maximum at around x=0.5; if my first guess is 0.4 then the gradient of the tangent at that point is actually nearly zero, i.e. horizontal to the x-axis, hence out next guess will be very far from out first guess and the root we are looking for. If out first guess is actually at the turning point, the tangent will be horizontal to the x-axis, it will never cut the x-axis by any chance. In both of the cases, the Newton-Raphson method fails.

Rearranging f(x)=0 in the form x=g(x)

Introduction:

This method is actually finding a single value or point of an estimate value of the root rather than identifying the interval in which the root lies.

The method involves rearranging the function f(x)=0 in the form x=g(x). Drawing the graphs y=x and y=g(x) on the same graph:

The root of the function f(x)=0 is indeed the intersection of the two lines.

The iteration I am going to use in this method is actually based on:

xn+1=g(xn)

Presenting the iteration graphically, we will have either a ‘staircase’ or a ‘cobweb’ diagram.

For the equation:  f(x)=y=x³+6x²+9x+1

 

rearrange f(x)=0, I get x=-(x³+6x²+1)/9

drawing y=x and g(x)=y=-(x³+6x²+1)/9 on the same graph, I get the graph below:

By using the rearranging f(x)=0 into x=g(x) method, it provides the iterative formula xn+1=(-xn³-6xn²-1)/9.  It is shown in the purple line in the graph below.

I chose x=-4 as my starting point, find the corresponding value of g(-4). Next, we take this value g(-4) as the next guess, this means that x2=g(-4) and move the point horizontally towards the right to the line y=x and find the value of g(x2), this process continues until both x and g(x) are the same value.

Showing the method on a spreadsheet:

The formula I used in the spreadsheet are as follows:

From the spreadsheet shown above, it shows that the iteration

xn+1=(-xn³-6xn²-1)/9 converges to the root x=-3.53209.

We also notice the characteristic of the gradient when x=-4 , g’(x)

g’(x)=-1/3x2-4/3x

g’(-4)=0

-1<g’(-4)=0<1

However, this method does not always work.

Rearranged the equation f(x)=x³+6x²+9x+1=0

into x=(-6x2-9x-1)1/3

draw graphs y=x and  on the same graph:

this time the iteration formula is .

The graph below shows the iteration has failed to converge to the required root.

The starting point I chose is 0, showing the rearranging method on the graph:

from the graph we can see that this time the method fails to converge.

Considering g’(x) in this case:

g’(x)=-1/3(12x+9)(6x2+9x+1)-2/3

g’(0)=-1n which is out of the range (-1,1), so the graph is divergent but not convergent, the method failed.

Comparison:

To compare the three method used above, I will choose the equation used in the bisection method as an example:

y=(x-2)(x-4)(x-6)+1

now I am going to use the other two method to find the same root as the one I found in the interval bisection part of my course work: x= 1.88513184

1. using the Newton-Raphson method:

For this method, I am going to choose x= 1.5 as my starting point. Showing the process on the graph below:

For the function: f(x)= (x-2)(x-4)(x-6)+1=x3-12x2+44x-47, f’(x)=3x2-24x+44

Using the iteration:

doing on a spreadsheet, I get the following table:

The formulae I used in the spreadsheet are as follows:

From the table I get the root of f(x)=0 is x=1.88509246

2. using the rearranging f(x)=0 in the form x=g(x) method;

for this method, I am going to rearrange f(x) = x3-12x2+44x-47=0 in the form x=(-x3+12x2+47)/44, i.e. g(x)= (-x3+12x2+47)/44

draw y=x and y=g(x)= (-x3+12x2+47)/44 on the same graph, I get the following:

using the iteration xn+1=g(xn), doing on the spreadsheet with a starting point x=3 I got the following table:

The formulae I used in the spreadsheet are as follows:

According to the spreadsheet above, I got the root of f(x) =0 x=1.885229646