Evaluating Three Methods of Solving Equations.
Maths C3 Coursework
Introduction
I'm going to look at 3 methods used to find the roots of an equation. First the decimal search or the sign change method; second, the Newton-Raphson method and third the fixed point iteration method, also called the x=g(x) method. I will then critically compare the three methods to find their advantages and disadvantages and will finally talk about how the current technology improves the efficiency of these methods.
Change of sign method: Decimal search
This is the first method. In this method we first determine two nearest values of x within which the function changes sign from +ve to -ve or vice versa. This is done with the help of the function graph. Roots of the equation will obviously lie within these two values of x. We then calculate f(x) within this range by splitting the values of x as necessary. Again we note down two adjacent values of x, within this smaller range, between which the function changes sign again and repeat the same exercise again and again till we reach as close to the root as we wish to.
Let me illustrate the point by solving an equation as an example. My equation for this method is:
f(x)=x3-7x2-8x-4
To get my initial values of x, I used a graph:
From the graph it is clear that the roots of this equation lie between the values of x=8 and x= 9. So I set my initial values of x between 8 and 9. Values of the function for different values of x are then tabulated as below.
I have italicised, emboldened and bordered the values of x within which roots of the equation will lie.
This method works because at the root of equation graph the curve must pass through the x-axis and therefore one side of it would be positive and the other negative:
As can be seen, before the curve line passes through the x-axis, f(x) > 0, and then after it passes through the x-axis f(x) < 0, this can be vice-versa if the curve is coming from below the x-axis.
This method does not work all the time. For example, if two roots are very close together, then the decimal search would say there are no roots because the curve goes through the x-axis and then comes up again within the search field, unless of course the initial search field itself is narrowed considerably which may be difficult to ascertain. An example of such an equation is:
y=x3+0.12075x2-14.1508x+19.9297
As you can see, if we were searching for any roots between x-values 2 and 3, or even between 2.12 and 2.14, none would show up because on both sides we'd find a positive value suggesting there are no roots, but in fact the curve line does cross the x-axis.
Newton-Raphson method
The next method I'm going to look at is the Newton-Raphson method. As in the previous method, at first, a value of x is selected near the root of the equation with the help of a graph. Then, at the point on ...
This is a preview of the whole essay
y=x3+0.12075x2-14.1508x+19.9297
As you can see, if we were searching for any roots between x-values 2 and 3, or even between 2.12 and 2.14, none would show up because on both sides we'd find a positive value suggesting there are no roots, but in fact the curve line does cross the x-axis.
Newton-Raphson method
The next method I'm going to look at is the Newton-Raphson method. As in the previous method, at first, a value of x is selected near the root of the equation with the help of a graph. Then, at the point on the curve corresponding to the value of x, a tangent is drawn and extended up to the x-axis. This tangent should intercept the x-axis at a point nearer to the root of our equation. We then draw another tangent to the curve at the point corresponding to this new value of x and continue this process in which every new value of x is getting closer to the root, until we eventually get to it
Let me now illustrate the point by taking an example.
My equation for this method is:
f(x)=x3+8x2-13x-23
From the graph of this function I find that its root must lie between 2<x<4 and therefore take 4 as the initial value of x, and draw a tangent on the curve at the point corresponding to x=4. To determine the point at which this tangent crosses the x-axis, I derive the equation of the tangent by calculating the values of m & c for this tangent from the general line equation of y= mx+c. I found the derivative of the function and got f'(x) = 3x2 +16x-13 which helped me to derive the equation of the tangent. By similar calculation of the value of 'c' we derive the following formula for this tangent and the point x.
We also notice that, at the root of the equation, xn+1 will be equal to xn. We will therefore continue to repeat the same process with the new point xn+1 till we reach root. It was easy to get excel to do these calculations within seconds. As mentioned my initial x-value, pretty close to a root, as looked up from the graph of the function was found to be x=4. I started with this value to get the root. For the other two roots I used x = -2 and x = -9
There are situations where this method does not work. An example of such an equation is f(x) = x0.2+x0.16-1.
The first two tangent lines have been added with my initial value x0 =1. As you can see, the tangent lines instead of converging towards the root, are diverging away from it.
Fixed Point iteration (x = g(x))
The final method I'm going to look at is called fixed point iteration or x=g(x). This method is based on re-arranging the equation f(x) = 0 to x = g(x) format. It is then obvious that the root of equation f(x)=0 will satisfy the condition n=g(n) if n is its root.
As in earlier methods, we then select a value of x, say x', close to the root of the equation and substitute x' for x in the function g(x). As x' is not a root of f(x), the resultant value of g(x), will not be x' but say, x" and x" will then be x"=g(x'). We then repeat the process by substituting x" for x in g(x)=x and keep doing the same until you feel satisfied, you are close enough to the root or actually on the root. When the root is found then every step afterwards gives nearly the same root as at that point x = g(x).
It is for this reason, the formula xr+1 = g(xr) is termed an iterative formula. It may however be noted that the suffix r+1 is not a number next to r, but is the value of the function g(x) arrived at by putting the value of x=r in the equation for reiteration of the exercise to get the roots of function f(x)=0
For solving an example by this method, I have chosen the following equation::
x3-3x2-15x-12 = 0, which can be re-arranged to get:
x = (3x2+15x+12)1/3
In its iterative form this looks like:
xr+1 = (3xr2+15xr+12)1/3
The graph on the right shows y = x, y = f(x) and y = g(x). As you can see from it, the intercepts of y = x and y = g(x) give the roots of y = f(x).
I saw that the value of the root is somewhere between 5 and 6 so I set the initial value xo = 5.
The reason this method works is represented by this graph:
After taking an x-value you find g(x) of that value. You then use this g(x)-value again as the new x and continue along in this manner whilst converging upon the root.
This method like the rest, does not work for every situation. Take the equation 0 = 5x3+x-1 which rearranges to x = 1-5x3.
As you can see, after every iteration, the x-value diverges away from the root. This is because of the gradient at the root. If the gradient of the curve at the root is less than -1, then the cobweb expands, so the iterations will never approach the root.
Comparisons:
To make a comparison of the three methods, I decided to take the formula x3-3x2-15x-12 for which I have earlier applied the fixed point iteration method.
I will now try to find the same root by applying the other two methods.
Decimal Search Method:
From the graph of the function I know the root of the equation lies between 5<x<6. So I carried out the decimal search between 5 and 6, hoping to get the same root as before.
As before, I have italicised, emboldened and bordered the two x-values the root lies within.
Newton-Raphson method:
To apply the Newton-Raphson method, I found the derivative of this function which would be f'(x)=3x2-6x-15, and then applied the formula:
Conclusion:
All three methods seem to work effectively. Each method has however exceptional situations where it fails.
Each method takes however, its own time, but then the added benefit of technology in this day and age, enables one to perform even lengthy calculations in split seconds.
Decimal search method
This method requires no re-arranging of equations or calculation of derivatives etc. You just create intervals and let the computer do its calculations. The time consuming part of this method is that after every set of calculations, you have to look through the data manually, to determine a new range of values within which the root may lie. If the formula was a complicated one, this would be the easiest method to find its roots as long as the roots don't lie too close to each other, or would not show up easily.
Newton- Raphson method
This method requires you to find the derivative of the equation, which can be difficult if it happens to be along & complicated one; but after that, one has to apply an iterative formula which the computer can do instantaneously, leaving you with the root. This can be very effective with any simple equation for which the derivative can be found quite easily and fast of a simple equation which can be applied in the formula.
The fixed point iteration requires you to re-arrange the equation to get it in the form x = g(x), which could be a problem if it was a complicated equation. The part where you turn it into an iterative one is however simple and quick. The final part, just plugging it into the computer is as always, very quick. The only real problem in this method lies with the re-arrangement of the equation, but after that, it's quite simple. The downside to this method, is that it requires a certain gradient of the curve y = g(x) at the point of the root. If the gradient at the point of the root is not between -1 and 1, then the method has a small chance of succeeding to find the root.
Overall, these days with advanced computers , calculations can happen fast. The only part that slows these methods down is the requirement of a human mind in a few key stages of each method. The complexity of the equation affects this as a more complex equation usually takes longer for the human brain to process.
Mohit Gupta Page 1
