So x=4.4227 ±0.0005. To prove that this is a root I will now enter this value with an additional 0.00005 above and below into the original equation which give two results one positive and one negative:
F(4.42265)= 4.42265³-4*4.42265²-3*4.42265+5
= -0.000986573
F(4.42275) = 4.42275³-4*4.42275²-3*4.42275+5
= 0.00104335
However, this method sometimes fails to find the root of an equation. For example, consider the equation: x^4-4x²-3x+8.49=0. Constructing a table of values would usually reveal a root between x=1 and x=2 based on looking for a sign change. However, as illustrated by the graph above, there are two roots that lie between x=1 and x=2. Constructing a table of values for this method would clearly fail to produce a change in sign solution to equations such as this.
Fixed point iteration: Newton-Raphson Method
To investigate this method, I shall use the function x³-3x²-3x+4=0. The equation is shown above. This method involves taking a rough approximation of x, and then improving this each time to get a more accurate value for x. Each successive iteration is calculated from the last using the formula: x1=x0-(F(x0))/(F’(x0)).
The differential of my formula is 3x²-6x-3=0. There is a root between x=0 and x=1 as indicated by the graph so I shall take my first value to be x=1. Therefore, the next value of x is calculated as follows:
x1=1-(F(1)/(F’(1))
x1=1-(-1/-6)
x1=0.833333333
Taking the x1=1, the new approximation of x is calculated as follows:
X2=0.833333333-(F(0.833333333)/(F’(0.833333333))
X2=0.833333333-(-1.963*10^-3/-5.916)
X2=0.832668188
And the next value of x:
X2=0.832668188-(F(0.832668188)/(F’(0.832668188))
X2=0.832668188-(-6.94*10-04/-5.92)
X2=0.832550958
Any other number of repetitions of this process past this point gives the same value of x of 0.83255, correct to 5 s.f.; i.e. ±0.000005.
To test that 0.83255 is a root, f(0.832545) and f(0.832555) are calculated. These equal
3.44*10-05 and -2.48*10-04 respectively. As there is a change of sign ±0.000005 either side of 0.83255, it can be concluded that this is a root.
This method can quickly find a very accurate estimate of the root in very few steps, with the accuracy limited only by the device used to calculate x. This is done by firstly drawing a tangent to the curve at the initial value. Where the tangent hits the x axis is where the next tangent is started from. Repetition of this process take the point at which the tangent of the curve at the original approximation of x to be the new value of x to take the tangent from, until the correct value of accuracy has been achieved. This is graphically illustrated to the below.
I shall now find the other two roots of x³-3x²-3x+4=0, which are between [-2,-1] and [3,4].
Root [-2,-1]:
Testing: F(-1.36145) = 2.01*10-04, F(-1.36155) = -8.72*10-04, so -1.3615 is a root.
Root [3,4]:
Testing, F(3.5289175) = -6.03*10-06, F(3.5289185) = 7.16*10-06, so 3.528918 is a root.
The roots of the equation x³-3x²-3x+4=0 are 0.83255, -1.3615 and 3.528918.
However, there are times when the Newton-Raphson method fails to find the root of an equation. For example, consider the equation x5-7x+3=0, whose graph is shown above. Normally when the value in the graph is chosen the calculations would have led the blue line to the root found between the x values -2 and -1. However the tangent produced has shot across to the other side of the y axis and found the root at the opposite end of the curve.
Rearranging f(x)=0 to the form x=g(x)
To investigate this numerical method, I shall be using the function x5-7x-3=0. The equation f(x) =0 can be rearranged in the form of x = g(x). On a graph, f(x) = 0 when g(x) intersects the line y = x. x5-7x-3=0 is rearranged into the form (x5+3)/7=0.
Starting with x=5, successive iterations are shown in the table below. This is represented graphically in the graph above, with g(x) in blue and y=x in red.
The calculation for this method will now be done manually to
confirm that the table is correct: (0.571435+3)/7= 0.43728,
(0.437285+3)/7= 0.43086,
(0.430865+3)/7= 0.43069,
(0.430865+3)/7= 0.43069.
It would seem that a root exists at x=0.43069. F(0.430685)= 2.33*10-05 and F(0.430695)=
-4.49*10-05 which is correct.
This method of rearrangement also fails to produce roots in certain circumstances. Consider the same graph but this time it is the second intersection of the line and curve.
Any effort to attempt successful iteration to find the second root always leads to failure because of the large steepness of the curve at the point which causes the stepping method to divert away from the root causing an overflow error. This is shown in the graph above and the table below.
Comparison of Methods
To compare the methods, I shall use the equation x³-5x+3=0 which is shown below.
For the Change of Sign: Decimal Search method, I shall start with table of values between 0 and 1:
However to get an answer as accurate as the previous methods, I need an accuracy of ±0.00005. This takes another 24 iterations:
So 0.65662 < x < 0.656621. By contrast, the equivalent result of ±0.00005 using the Newton-Raphson method takes only three iterations:
The G(x) iteration method is also faster than the decimal search method with 7 iterations:
So in speeds of convergence, the Change of Sign method takes 24 steps, x=g(x) method takes 7 steps and the Newton-Raphson method takes 3 for this equation. This order of speed is a good representation of most equations that I have encountered.
However, the Change of Sign method takes the least initial work; for the Newton-Raphson method, f'(x) needs to be calculated. For many possible equations, differentiating them is very tedious and for some advanced equations beyond my capabilities and for each step, more calculations are required. The x=g(x) method requires rearranging the formula to start with, and in many cases, this results in a non-continuous function (e.g. involving odd roots). For continuous functions with more than one root, the G(x) method will usually fail to find at least one of them due to the differences in gradient steepness.
I believe that the Change of Sign method is the best for finding all the roots of a function, considering that I use specialized graph producing software (Autograph) to do all the calculations in these methods. The time taken to perform calculations is negligible, especially when placed in context with the time to calculate the f'(x) or g(x). Also, this method is the most reliable with most equations that I have encountered.
