In this investigation I aim to investigate three methods of finding the roots to equations and then compare them. I aim to be able to use fully and understand all three techniques.

Here we can see that there are two roots and that they are in-between -5 and +5, so this is where I will start searching at integer intervals, before searching at intervals ten times smaller within the two values I know the root to be in. (Full tables can be seen in the TABLES section of this project)

The two values that I found were -2.48715 and 0.55450 (5d.p.). These numbers are correct to 5 decimal places. To test this I took ±0.000005 from the numbers and tried to display a sign change. I did this in my worksheet, but will display an example here:

-2.48715 + 0.000005 = -2.487155 f(-2.487155) = 3.19373*10-5

-2.48715 - 0.000005 = -2.487145 f(-2.487145) = -2.29477*10-7

As you can see there is a sign change in f(x) between the two values of x. This means that, due to the fat that this is a continuous function, there must be a root between -2.487155 and -2.487145 meaning that the root will be -2.48715 to five decimal places. The same method is used for the other root and can be found in TABLES.

The decimal search method can fail though. This occurs when the resolution of the search is not high enough. What this means is that the decimal search cannot tell if a curve has crossed the x-axis twice or if a double root occurs if it is between two of the values. This means that any function with roots that begin with the same integer value (eg -5.2 & -5.8, 0.6 & 0.9, pi and 3.7) will be a failure case with decimal search. Even when you search to a resolution of tenths will still sometimes fail. In fact even when you search with and infinitely high resolution there will be an infinite number of functions that will become failure cases. To illustrate this point I have chosen an equation which has two roots very close to each other. The equation is f(x)=2x5+3x4+x3+x2+SIN(x)-0.162 and is displayed here.

We can see here that there are two roots at roughly -1 and -1.1. If you look at my TABLES section you will see that I have easily found the root at roughly 0.14. But if we look at the two charts in green we can see that this method does not find any negative roots even when the resolution is increased. It is only when, with information, not from the search method but from omnigraph, that we can find the solutions between -1.1 -1. The solutions can be seen closer in a graphical from here.

I have not gone further with the decimal search method to find them, because I have already proved that I can find roots and all I needed to do here was to prove that first it seemed as is they didn't exist and then that they did.

The Newton-Raphson method

The Newton-Raphson method is much more sophisticated than the Decimal Search method. It involves a very clever method to find out where the roots of an equation are. It works on the principle that a curve will be pointing (it's tangent) at the root of an equation. To find the roots it takes the derivative of the equation and then calculates where the tangent to the line at a given point will cross the x-axis. It does this using the derivative to find out the gradient of the tangent and then the equation x(n+1) = xn-(f(xn)/f'(xn)) to find out where the tangent hits the x-axis. It then takes this new value of x and uses that as the value to find the tangent at. If you were to look at an example graphically it would look like this.

The equation that I used in this example is f(x)=sinx-x4-10, it is displayed in black, and the tangents used are in the different colours. I have only displayed the first five tangents because the graph would become confusing had I displayed any more. Even with only five lines the root is located to one decimal place. This is a lot quicker than the decimal search method which took pages rather than lines of working. A further table solving this equation to 10 decimal places for both the roots can be found in my TABLES section. To prove that I definitely had solved the equation to 10 decimal places I used the same method that I used to check the decimal search results. For this I will use the other root of this equation:

-1.8198815765 + 0.00000000005 = -1.81988157655 f(-1.81988157655) = 1.04225 x 10-8

-1.8198815765 - 0.00000000005 = -1.81988157645 f(-1.81988157645) = -1.02236 x 10-8

From this it seems that the Newton-Raphson Method is infallible, but it call fail and in many ways. Take the equation f(x)=ln(x)+sin(9x2)+0.900904237825 which looks like this:

From this graph we can see that it has three roots between 0 and 1. Obviously we cannot start with the value 0 because the function includes a ln(x) function as the gradient would be ?. This is the first of many problems that the Newton-Raphson.

has with this equation proving that it does not always work. There are also many other problems with this equation, for example let us consider the starting value x=0.44. What happens when the value 0.44 is displayed on the diagram in the red line. We can see that the tangent crosses the x-axis at a negative value, and so due to the ln(x) function there is no f(x) to a negative x. So again this method has failed. The same theory is behind why it fails when a turning point is taken as a starting value of x. Because the gradient is O at that point at would never reach the x axis and so there is no solution.

A further reason that this equation fail to find the roots is if a high value of x is used as a starting value. If we can see how steep the gradient is at a value like 4 you would imagine that the tangents would get stuck in one of the sin curves as displayed in this diagram:

And you would be right to imagine this as this is in fact a graph of what happens when 4 is used as a starting value. The tangents are in blue in this diagram and you can see that they get stuck in this sin curve, again showing this method to fail, although the starting value was only just over 3 away from three roots.

I have demonstrated four failures with the Newton-Raphson Method, but there I still one more even in this equation! The Newton-Raphson method can in fact find a root that doesn't even exist. If you look in the tables section you will see one root that is found where I haven't tested form accuracy. This root does not exist. This is because the root almost exists, it is where it looks like a double root on the large scale picture

But as you can see from this graph it is about a 1trillionth away from the x-axis, but does not touch and then due to software and/or hardware limitations the spreadsheet program thinks that there is a double root at this point and creates a non-existent root, with is a far worse fault than missing out on a root that does exist.

Software/Hardware limitations are a large problem in situations like this. Most programs will only use a certain number of bits to determine a point and that number may further be limited if it being used on a low quality computer. If you look on the graph above you can see the resolution. The values all seem to be distinct trillionths away from each other and this can be problem in scenarios like this.

The Re-arrangement Method

Original y=(x^6-2*x^4+4*x^2-8x+3.141592654)/20

Success y=(x^6-2*x^4+4*x^2+3.141592654)/8

Failure y=((x{^{6}+4x{^{2}-8x+3.141592654)/2){^{0.25}

Comparison of Methods