In this case, using the method of decimal search has caused an incorrect conclusion to be reached. This is because the curve touches the x-axis between x=1 and x=2, therefore there is no change of sign and consequently all change of sign methods are doomed to failure.
Fixed Point Iteration Method
Let y=f(x)=x3+2x2-4x-4.58. The graph is shown below:
The roots of the equation can be found where f(x)=0. From the graph, it is evident that the roots of the equation lie in the intervals [-3,-2],[-1,0] and [1,2].
Using a sign change search verifies that the intervals within which the roots lie are indeed [-3,-2],[-1,0] and [1,2]:
When using the Fixed Point Iteration method, the above equation must be rearranged into the form x=g(x):
x3+2x2-4x-4.58=0
x3+2x2-4.58=4x
¼( x3+2x2-4.58)=x
Therefore the iterative formula for this equation is:
xr+1 = ¼( x3r+2x2r-4.58)
The graph of y=¼( x3+2x2-4.58) and y=x are shown below:
Where these two curves intersect, gives the roots of the original equation y=f(x). It is therefore necessary to find the points of intersection. I will focus on the point of intersection that lies in the interval [-1,0].
I will use the previously evaluated iterative formula, using x0 as 1, for my starting value. For the method to succeed, the iterative formula must converge for the chosen value of x. To ensure that this is so, I will differentiate the iterative formula, and check that the x0 value gives a result that is less than one:
y=0.25x3+0.5x2-1.145
dy
dx
substituting x=-1 gives 0.75(-1)2 + (-1)
= 0.75 – 1
= -0.25
The fact that this value is less than 1, tells us that the chosen value of x0 will lead to a root of the equation.
It is necessary to substitute x0=-1 into the iterative formula to find the value of x.
A line is drawn from x0 to equation 1, and then ‘followed across’ to the closest point on equation 2. Repeating the former process will cause the values where the line meets each of the two equations to come closer together until they converge at the point where the two curves intersect, and therefore at a root. The iterative formula calculates these values as they converge.
xr+1 = ¼( x3r+2x2r-4.58)
x1 = ¼(( -1)3+2(-1)2-4.58)
=¼(-1+2-4.58)
=¼(-3.58)
x1 = -0.895
The following table was obtained using a Microsoft Excel spreadsheet, with the formulae shown. The sequence works using this particular iterative formula because when the gradient of y=g(x) is less that 1, y=x is used as a ‘barrier’ and makes the sequence converge thus allowing the root to be found.
The values that were obtained are as follows:
Error Bounds
Therefore the root to the equation between the interval [-1,0] is –0.9172560 correct to seven decimal places.
To check that this is correct, substitute
x= -0.91725595 into f(x)
= -0.00000031423
and
x= -0.91725605 into f(x)
= 0.000000200258
The above calculations illustrate that there is a change of sign. Therefore the root is -0.9172560±0.00000005.
Failure of the Fixed Point Iteration Method
I will now attempt to find the root that lies in the interval [1,2] of the same equation. As before, the Fixed Point Iteration method will be applied.
My chosen starting value, x0, will be 2.
The following table was constructed using a Microsoft Excel spreadsheet with the formulae displayed:
The values that were obtained are as follows:
The ‘new x values’ can be seen to be getting further and further apart, i.e. they appear to be diverging. The Fixed Point Iteration method has therefore failed, due to the fact that the successive iterations are diverging from the required interval of [1,2].
The above illustration shows that for x0=2, the gradient of y=g(x)= ¼( x3+2x2-4.58) is greater than that of y=x, i.e. greater than 1. Without further calculation, this can be seen by the fact that the line y=g(x) is steeper than the line of y=x.
The gradient of y=g(x) ¼( x3+2x2-4.58) can be found by differentiating:
dy
dx
= 0.75(22) + 2
= 5
When x0=2, g'(x)=5. As the magnitude of g'(x) is greater than 1 and steeper than the gradient of y=x at this point, the successive iterations will diverge instead of converging to the required root.
The graph shows that with this particular iterative formula, the Fixed Point Iteration method fails because y=x can no longer be used to make the sequence converge.
With the equation y=g(x) when x=2, y=2.855
With the equation y=x when x=2, y=2
As 2.855>2, the line from x=2 passes y=x before touching y=g(x) thus causing the sequence to converge and the required root is left unfound.
Newton-Raphson Method
If y=f(x)=1.3x4-2.2x3+0.7, the roots of the equation can be found where f(x)=0 and so where 1.3x4-2.2x3+0.7=0.
This equation cannot be solved algebraically therefore I will use the Newton-Raphson method to determine the roots of the equation.
The curve is show here graphically.
From the sketch of the equation obtained, it is evident that there are two roots to the equation that lie in the intervals [0,1] and [1,2].
I will begin by finding the root that lies in the interval [0,1], taking my first approximation of the value of the root, x0, to be 1. A tangent to the curve, at this point will be drawn. Where this tangent cuts the x-axis, will be my next approximation, x1, of the root.
Using the iterative formula
xr+1 = xr – f(xr)
I will find the roots of the equation.
Taking x0 to be 1,
x1 = x0 - – f(x0)
The process will now be repeated using 0.857142857 as my new approximation of the root. In order to proceed another tangent is dawn at the point where x=x1.
To determine where this tangent crosses the x-axis:
x1 = 0.857142857
f(x1) = 0.016284881
f'(x1) = -1.574344023
x2 = x1 -
I will use a spreadsheet with the following formula to calculate where the tangent crosses the x-axis:
The values that were obtained are shown below:
Error Bounds
The previous calculations show that there is a root to the equation f(x)=y=1.3x4-2.2x3+0.7 when f(x)=0.
This root is 0.86749 correct to five decimal places.
To check that this is correct, substitute:
x= 0.867485 into f(x)
= 0.000013160499
and
x= 0.867495 into f(x)
= -0.000002560434
The above calculations illustrate that there is a change of sign. Therefore the root is 0.86749±0.000005.
I will now find the other root of the equation that lies in the interval [1,2]. I will use my first approximation of the value of the root, x0, to be 2. Again, the Newton-Raphson method will be applied to determine the root.
As before, an Microsoft Excel spreadsheet was used to calculate where the tangent crosses the x-axis:
The values that were obtained are shown below:
The above table shows that the other root to the equation f(x)=y=1.3x4-2.2x3+0.7 when f(x)=0 is 1.54682 correct to five decimal places.
To check that this is correct substitute:
x = 1.546815 into f(x)
= -0.00000260721
and
x = 1.546825 into f(x)
=0.00003192987
The above calculations illustrate that there is a change of sign. Therefore the root is 1.54682±0.000005.
Failure of the Newton-Raphson Method
There are situations when the root you wish to find cannot be determined using the Newton-Raphson method. This will be illustrated using the equation y=3x5-5x4.
Let f(x)=y=3x5-5x4. The rots of the previous equation can be found where f(x)=0.
I will use the Newton-Raphson method to determine the root that lies in the interval [1,2], using x0 as 1, as my first approximation of the value of the root.
The following table was constructed using a Microsoft Excel spreadsheet with the formulae displayed, again applying the iterative formula:
xr+1 = xr – f(xr)
The values obtained are as follows:
It is evident that the ‘new x value’ tends towards 0. This is not in the desired interval [1,2]. Drawing the gradient on the curve illustrates that despite choosing an initial value of x0 that was close to the root, suing the Newton-Raphson method has caused me to find another root. As the turning point of the graph was within the chosen interval, the Newton-Raphson method has failed.
Comparison of Methods
I shall now select one of the previously used equations and apply the other two numerical methods to find the root. The chosen equation is y=f(x)=x3+2x2-4x-4.58. I have already applied the fixed-point iteration method to this equation in order to determine the root that lies in the interval [-1,0]. This value is -0.917 correct to three decimal places.
Change of Sign Method
The decimal search method will be applied to the above equation in order to find the root.
If y=f(x)=x3+2x2-4x-4.58, the roots of the equation can be found where f(x)=0 and so where x3+2x2-4x-4.58=0.
Having illustrated the equation graphically, it is evident that one of the roots of the equation lies in the interval [-1,0]. To check that there is a sign change in this interval:
I will first take the increments in x of size 0.1 within the interval [-1,0], calculating the value of the function x3+2x2-4x-4.58 for each one, until a change of sign is found.
It can therefore be understood that the root lies in the interval [-1, -0.9]. I will continue the decimal search, now using increments of 0.01 within the interval [-1, -0.9].
This indicates that the root lies in the new interval [-0.92, -0.91]. I will continue the process using the increment of 0.001 within the interval [-0.92, -0.91].
The root therefore lies in the interval [-0.918, -0.917]. I shall now use increments of 0.0001 in the interval [-0.918, -0.917].
Therefore the root lies between –0.9173 and –0.9172. Correct to three decimal places the root is –0.917.
When x = -0.9165, f(-0.9165) = -0.00389006712
When x = -0.9175, f(-0.9175) = 0.00125526563
The error bounds of the root –0.917 are –0.917 ± 0.0005.
Newton-Raphson Method
The Newton Raphson method will now be applied to find the same root to the equation. It is first necessary to look for a change of sign between integer values so as to choose a suitable starting value.
The above table illustrates that a sensible first approximation of the value of the root, x0, would be –1. A tangent to the curve at this point is drawn. Where this tangent cuts the x-axis, will be my next approximation of the root.
The value x0 will be taken as -1, and substituted into the iterative formula:
xr+1 = xr – f(xr)
A Microsoft Excel Spreadsheet with the following formulae was used to calculate where the tangent crosses the x-axis:
The values that were obtained are as follows:
Therefore it can be understood that the root is –0.917 correct to three decimal places. To check this is correct, substitute
x = -0.9165 into f(x) = -0.00389006712
x = -0.9175 into f(x) =0.00125526563
The above calculations illustrate that there is a change of sign and therefore the root is –0.917± 0.0005.
Fixed Point Iteration Method
The equation has already been solved to find the root that lies in the interval [-1,0] using this method. The following steps show how this was done. If y=f(x)=x3+2x2-4x-4.58 then the roots of the equation can be found where f(x)=0. It is first necessary to look for a sign change between integer values so as to choose a suitable starting value.
I have chosen to find the root that lies in the interval [-1,0] and therefore an appropriate starting value, x0, for the approximation of the root would be –1. When using the Fixed Point Iteration method, the previous equation must be rearranged into the form x=g(x):
x3+2x2-4x-4.58=0
x3+2x2-4.58=4x
¼( x3+2x2-4.58)=x
Therefore the iterative formula for this equation is:
xr+1 = ¼( x3r+2x2r-4.58)
For the method to succeed, the iterative formula must converge for the chosen value of x. To ensure that this is so, the iterative formula was differentiated, and it was checked that the x0 value gave a result that was less than one:
y=0.25x3+0.5x2-1.145
dy
dx
substituting x=-1 gives 0.75(-1)2 + (-1)
= 0.75 – 1
= -0.25
The fact that this value is less than 1, tells us that the chosen value of x0 will lead to a root of the equation.
The following table was obtained using a Microsoft Excel spreadsheet, with the formulae shown.
The values that were obtained are as follows:
Therefore the root to the equation between the interval [-1,0] is –0.917 correct to three decimal places.
When x = -0.9165, f(-0.9165) = -0.00389006712
When x = -0.9175, f(-0.9175) = 0.00125526563
The error bounds of the root –0.917 are –0.917 ± 0.0005.
