In maths equations can be solved using various methods. A very common and efficient method in solving equations is algebraically. But not all equations can be solved algebraically; these equations must be solved using numeric methods.
I will study three specific numeric methods on different equations.
~ Change of sign, decimal search process.
~ Newton-Raphson method.
~ Re-arrangement method.
I will be testing the numeric methods with separate equations which cannot be solved algebraically. I will also apply all of the methods to one of the equations and check if all the methods give me the same value for the root I want to find.
Change of Sign, Decimal Search
To find the root of the equation f(x) = 0 means finding values of x for the graph y = f(x). The change of sign method works on the bases that the y = f(x) graph changes signs when it crosses the x-axis.
y = f(x)
The sketch above shows that there is a root between the interval [b , c] and the curve of y = f(x) crosses the x-axis and changes its sign from negative ( – ) to positive ( + ), and at the interval [a , b] f(x) curve crosses the x-axis changing its sign from positive ( + ) to negative ( – ).
An initial interval of where a root lies can be obtained from a sketch. By taking the values of the initial interval we can increase the value of x by increments of 0.1 within the initial interval. Then if each of the increments of x is substituted into function of x a value can be obtained, and where there is change in sign from the values of f(x); it will state a closer interval (second interval) of where the root lies. Then new values of x are obtained by taking increments of 0.01 within the second interval, these values are again substituted into the f(x) until there is a change of sign, this will give an even closer interval of where the root lies. This process can be repeated and the increments of x are increased by another decimal place (i.e. 0.1, 0.01, 0.001, etc) until the interval can no longer be taken further or by stopping till the interval of where the root lies reaches required number of decimal places.
Failure of Change of Sign Method
The change of sign method may not always work; the failing of the change of sign method relies on the equation being used.
The change of sign method will fail if the following features occur with an equation.
If the curve touches the x-axis, ie the turning point is exactly on the x-axis there will be no change of sign; therefore the change of sign method will fail.
y = f(x)
The root for the function of x will not show using the change of sign method as the curve does not cross the x-axis and change signs.
As the curve only touches the x-axis there will be no change of sign for the values of f(x) in the chosen interval, hence resulting in the failure of obtaining a root using the change of sign, decimal search method.
This method works using tangents to cut the x-axis from a fixed estimated point. The f(x) graph is sketched, and then an estimate value for x is taken using the sketch. Where the estimate point of x touches the f(x) curve is the point where a tangent is drawn. Where this tangent crosses the x-axis will be the new estimate value of x. The new estimate of x is again located on the f(x) curve, and a tangent is drawn from this point; this locates another estimate for x. This procedure is repeated until the x value converges to a fixed value, the root of f(x).
The tangent produces a closer estimate of the root. This eventually leads to the actual root.
From this procedure the Newton-Raphson iterative formula is produced.
A chosen equation and an estimate root value are used with the iterative Newton-Raphson formula to eventually converge to the actual root.
Failure of Newton-Raphson Method
The Newton-Raphson method will fail if the starting point is carelessly selected. If the initial value of x is not close to the root needed to be found, the Newton-Raphson formula may not converge to the root. Also if the initial value is selected close to a turning point then it will also cause the formula to either diverge or converge to another root.
The selected initial value lies to close to the turning point of the f(x) curve, this creates the tangent from the initial value to diverge outside the area of the f(x) curve. This subsequently renders the method to fail as no further estimates of the root can be obtained.
When trying to find the root between the interval [0 , 1] and using the initial value as 0.88.
The tangent is forced to diverge from the f(x) curve, this illustrates the failure of the Newton-Raphson method.
Newton-Raphson Method in Practise
The equation to be used in finding a root using the Newton-Raphson method is,
y = xï¿½ – 3x + 1
Sketch of y = xï¿½ – 3x + 1
Sketch of y = xï¿½ – 3x + 1 with tangent line markings.
Initial value = 2 (x )
Magnified view of tangent markings.
Newton-Raphson formula calculations.
This method operates by re-arranging the initial equation, f(x) = 0 into the form of g(x) = x, this makes the values of x the root of the equation.
This method also works using a fixed point estimation process. The sketch of y = g(x) and y = x are plotted on the same set of axes, where the y = x line crosses y = g(x), produces the root(s) of the equation.
This method will only work if the gradient of the point of intersection between the y =g(x) and the line y =x, is less than the gradient of the y = x line.
Equation to be used,
The sketch illustrates that a root lies in the interval [0 , 1] therefore I shall choose the initial value as 1.
From the initial value of the x-axis, a vertical movement till the g(x) curve is hit is performed. From the point where the initial value hits the g(x) curve, a horizontal movement is performed till the y = x line is reached, and from the point where it hits the y = x line a vertical movement is performed back to the x-axis; giving the second estimate for the root; this produces a staircase diagram on the graph. This procedure is repeated with all the estimate values of the root until it converges to a single value.
zoomed view of boxed area
As the method is applied in an iterative manner, an iterative formula using the re-arranged equation can be produced.
To iterative formula,
Calculations using the iterative formula, to find the root in the interval [0 , 1].
Failure of Re-arrangement Method
Knowing that the method relies on the gradient of the point being less than that of the y = x line, I can state that any point of intersection which has a gradient that exceeds that of the y = x line will fail.
Re-arranging the initial equation into form of y = g(x),
The diagram shows that there is a root in the interval [1 , 2], but when an initial value between 1 and 2 is chosen, the method tends to diverge of the course of the y = g(x) curve. This is because of the gradient at the point of intersection in the interval [1 , 2], exceeds the gradient of the y = x line.
Gradient of the y = x line equals 1, y = g (x) >1 at the point of intersection in the interval [1 , 2]; this leads to the failure in obtaining the root at the interval [1 , 2].
To evaluate the best method, I will compare all of the selected methods using the same equation.
I have chosen the equation which I used to test the re-arrangement method.
I will be looking to find the root between the interval [0 , 1], when applying the equation to the other two methods.
The re-arrangement method produced the root being 0.375938, in the interval [0 ,1]. I will be checking that the change of sign and the Newton-Raphson methods produce the same root value.
Comparison Calculation for Newton-Raphson Method
Using the equation,
And the Newton-Raphson iterative formula,
Initial value =
After comparing all the methods with a single equation, I can state that the Newton-Raphson method is the most efficient method in terms of speed of convergence.
The Newton-Raphson method only required two iterations before converging to the required root.
The change of sign method had to go through six cycles before producing the required root correct to six decimal places.
The re-arrangement method went through four iterations to produce the root value.
Although the re-arrangement method only marginally lost in time efficiency when compared to the Newton-Raphson method; the re-arrangement method proves to be the most demanding. As the re-arrangement method relies on producing a re-arrangement to the form of y = g(x) and satisfies the fact y = g` (x) < y = x`.
The change of sign, decimal search method is a very straight forward method which can be applied easier then the other methods, but lacks in its rate of convergence.
So in an overall comparison I can state that the Newton-Raphson method has the fastest rate of convergence, and thus has an efficient process of finding the desired root of an equation that must be solved numerically.
The use of software packages and hardware devices make understanding the methods and application of the methods faster and more accurate.
Using Excel spreadsheet in displaying the calculations for the change of sign method proved to be efficient as it enabled repetitions of calculations to be performed much faster than by manual process.
Also using graphical displaying software such as Autograph allowed easier demonstration of the process of the different methods, and a more accurate interpretation of the methods.