This coursework is about finding the roots of equations by numerical methods.

There is a root in the range (2.5615, 2.5616)

Now use decimal search and Excel within the interval [2.5615, 2.5616]

There is a root in the range (2.56155, 2.56156)

Error bounds

I saw from my last table in Excel that the root lies in range (2.56155, 2.56156)

So the solution bounds are 2.56155 and 2.56156

I can also write the solution bounds as 2.561555 ± 0.000005. These are the error bounds.

Approximate value of root

The root is 2.5615 to 4 decimal places.

Illustrate the method graphically

The fact that f(2) is negative and f(3) is positive tells us the graph must cross the x axis between 2 and 3. Hence there is a root in the range (2, 3)

This graph shows us how the root is finally trapped in the range (2.56155, 2.56156)

What can cause failure?

One reason that the decimal search can fail is that there are several roots very close together in the same integer range.

For example, the equation y=54x³−225x²+309x−140

There appears to be only one root in the interval (1, 2) but there are three.

After finding the first root we might miss the other two.

There are three roots close together.

We only get one change of sign when we do the integer search.

The search will find the first root 1.6666 in this interval
Unless we have drawn a graph there is a big danger we may miss the other two roots.

Newton Raphson

An example is given: y=x³−2x²+1

We can see there are roots in the intervals [-1, 0] and [1, 2]

We will find the root in the interval [-1, 0]

        

Xn+1= Xn–f(Xn)/f’(Xn)

If f(X)= x³−2x²+1    then   f’(x)= 3x²-4x

Xn+1= Xn–( Xn ³−2 Xn ²+1)/ (3 Xn ²-4 Xn)

Using our example : y=x³−2x²+1

To find the root in the interval [-1, 0] we can take x1 =-1 or x1 = 0            

I will use x1 = -1

Can see that root is near to -0.6180 to 4 sf

Using Newton Raphson and Autograph Solver to find the root in the interval [-1, 0]  Solution: x=-0.61803399, y=0

Then find the root in the interval [1, 2]

To find the root in the interval [-1, 0] we can take x1 =1 or x1 = 2          

I will use x1 = 2

Can see that root is near to 1.6180 to 5 sf

Then 1 is one of the roots of the equation.

Newton Raphson converges to a value near to -0.6180

The Newton Raphson does NOT automatically trap the root between two values

In our example it looks like the root is just below 1.618034. We proposed it was 1.6180 to 5sf

We need to use the change of sign method to trap the root between two solution bounds

We evaluate f(1.61805) and f(1.61795)

We can also write the solution bounds as the error bounds 1.6180± 0.00005

The example below shows that NR fails to find the root.

y=x³−5x²+4.67x−0.418

The turning point near to x1 caused the divergence

Xn+1= Xn–f(Xn)/f’(Xn)

If f(X)= x³−5x²+4.67x−0.418 then   f’(x)= 3 x²-10x+4.67

Xn+1= Xn– (Xn ³−5 Xn ²+4.67 Xn −0.418) / (3 Xn ²-10 Xn +4.67

X=g(x) method

Example: y=−3x³−x²+x+2

The solution is near to 1

Take x1 = 1

Roots are given by −3x³−x²+x+2=0

Rearranges to:

                3x³= −x²+x+2

                x³ = 1/3(−x²+x+2)

                        x= [1/3(−x²+x+2)]1/3

Iteration is Xn +1 = [1/3(−Xn ²+ Xn +2)]1/3 

Using our example and finding the root in the interval [0, 1] , using X1=1

           

Can see that root is near to 0.8736 to 4 sf

Since g(x) = [1/3(−x²+x+2)]1/3

g‘(x) =1/9*((-x^2+x+2)^(-2/3))*(-2*x+1)

The root was x= 0.8878

Hence g‘(root) = -0.0.03618

Since -1< g'(x) <0 then we would expect the iteration to converge as a Cobweb

y=−3x³−x²+x+2

Rearrange to x=3x³+x²-2 leads to failure.

x1=1

x’=9x^2+2x

g’(0.8878)= 8.86929956

Since g‘(root) >1 then we would expect the iteration to diverge away from the root as a staircase.

Comparison

I am going to compare advantages and disadvantages of all three methods.

y=−3x³−x²+x+2

There are three intervals containing roots:

(-0, 1)

To find the root in the interval (0, 1)

Decimal search

The root is0.8878 to 4 s.f.

Newton-Raphson

• To find the root in the interval [0, 1] we can take x1 =0 or x1 =1            

I will use x1 = 1

xn+1= xn - (3xn^3+xn^2-xn-2)/(9xn^2+2xn-1)

Can see that root is near to 0.8878 to 4 sf

x = g(x)

Take x1 = 1

Roots are given by −3x³−x²+x+2=0

Rearranges to:

                3x³= −x²+x+2

                x³ = 1/3(−x²+x+2)

                        x= [1/3(−x²+x+2)]1/3

• Iteration is Xn +1 = [1/3(−Xn ²+ Xn +2)]1/3 

Using our example and finding the root in the interval [0, 1] , using X1=1

           

Can see that root is near to 0.8736 to 4 sf

Each method achieved the same accuracy in:

16 calculations for change of sign

4 calculations for Newton Raphson

1 calculation for x = g(x)

The x=g(x) method was the fast one in this particular example

Change of sign was much slower than NR and x=g(x)

If I only had a scientific calculator – the change of sign method is easier to operate.

If I also have Excel - the x=g(x) method is easier because there was only one calculation.

If I also have Autograph – the x=g(x) method is easier because there was only one calculation..