MEI PURE 2 COURSEWORK
SOLUTION OF EQUATIONS BY NUMERICAL METHODS
. Change of Sign Method
This method makes use of the fact f(x) changes sign at a root of an equation. f(x) must be a continuous function i.e. it must not have any asymptotes or other breaks in it. Once an interval in which f(x) changes sign is located, we know that that interval contains a root. It is best to sketch the diagram of f(x) first so that we can see how many roots the equation has and their approximate positions.
Decimal Search
The equation that will be investigated here is f(x) = 4x3+5, a diagram of which is shown below.
From the graph we can see that there is only one root. Zooming in, as shown below, we can also see that this root lies between X=-1 and X=-2
Taking increments in x of 0.1 within the interval [-2, -1] and working out the value of the function
f(x) = 4x3+5 for each one and then seeing where the sign changes will enable the narrowing down of the interval.
x
-2
-1.9
-1.8
-1.7
-1.6
-1.5
-1.4
-1.3
-1.2
-1.1
-1.0
f(x)
-27
-22.4
-18.3
-14.7
-11.4
-8.5
-6.0
-3.8
-1.9
-0.3
The values calculated in the table above have only been given to 1 decimal place as we are only looking for a change in sign at this stage. We can see that there is a sign change, and therefore a root, in the interval?? [-1.1, -1.0] since the function is continuous. Having narrowed down the interval, we can now continue with increments of 0.01 within the interval [-1.1, -1.0].
x
-1.1
-1.09
-1.08
-1.07
-1.06
-1.05
-1.04
-1.03
-1.02
-1.01
-1.0
f(x)
-0.3
-0.2
-0.04
0.1
This has further narrowed down the interval within which the root lies. The interval has been narrowed down to [-1.08, -1.07]. Continuing to find the third decimal value of the root:
x
-1.08
-1.079
-1.078
-1.077
-1.076
-1.075
-1.074
-1.073
-1.072
-1.071
-1.07
f(x)
-0.04
-0.03
-0.01
0.003
The above calculations show us that the root lies in the interval [-1.078, -1.077]. From this we can conclude that the root to f(x) = 4x3+5 is ?1.0775 +/- 0.0005.
Error Bounds
The change of sign method automatically provide bounds, the two ends of the interval, within which a root lies and hence allowing us to calculate the maximum possible error in a result. From the calculations above, the solution to the function f(x) = 4x3+5 was found to be in the interval [-1.078, -1.077], which allowed for the answer to be quoted as ?1.0775 +/- 0.0005, 0.0005 being half the interval between the error bounds.
Limitations of Decimal Search
The decimal search, an example of a change of sign method, will not work when the curve of a given function touches, but does not cross, the x-axis. In such a case there is no change of sign, and so the method is doomed to failure. An example of this may be the function f(x) = (x-1)(x+2)2.
The graph of f(x) = (x-1)(x+2)2 is illustrated below. As can be seen the curve only touches the point
x = -2 and does not cross the x-axis. x = -2 is clearly ...
This is a preview of the whole essay
Limitations of Decimal Search
The decimal search, an example of a change of sign method, will not work when the curve of a given function touches, but does not cross, the x-axis. In such a case there is no change of sign, and so the method is doomed to failure. An example of this may be the function f(x) = (x-1)(x+2)2.
The graph of f(x) = (x-1)(x+2)2 is illustrated below. As can be seen the curve only touches the point
x = -2 and does not cross the x-axis. x = -2 is clearly a root of the function f(x) = (x-1)(x+2)2 but since there is no change of sign, it will not be detected by the decimal search.
2. Newton-Raphson Method
The Newton-Raphson Method states that if a is a first approximation to a root of f(x) = 0, a better approximation is, in general,???
???????????????????????????????????????????? a-f(a)/f?(a)
The function that will be investigated here is f(x) = x3-5x, the graph of which is illustrated below:
There are 3 roots to this equation. One of the roots is clearly zero as f(0) gives 0. The other two roots, however, can only be approximated. If the first root = a and the second root = b then using the graph the values ?2 and 2 can be assigned to a and b respectively:
a1=-2
b1=2
f?(x) is required and this is obtained simply by differentiating f(x) = x3-5x which gives 3x2-5. The iterative formula is now:
???????????????????????????????????????????? Xn+1 ? (xn3-5x)/(3xn2-5)
The results for successive iterations are given in the table below for a:
Iteration
f(x)
f?(x)
Xn+1
a1
2
7
-1.71429
a2
3.53353
3.81633
-2.64018
a3
-5.20266
5.91170
-2.31321
a4
-0.81183
1.05286
-2.23976
a5
-0.03704
0.04961
-2.23608
a6
-0.00009
0.00012
-2.23607
a7
-5.58x1010
0
-2.23607
Although the values above have been given to 5 decimal places, the exact values were used for the actual calculations. It is clear from the working out above that the values for are converging to
?2.23607. Also, the last value of f(x) which is progressively becoming smaller in size, is so small that any further iterations will not produce any significantly different values since the change in x is given by f(x)/f?(x)The root is therefore ?2.23607 to 5 dp.
Using the same method, the second root, approximated by b, can be calculated.
Iteration
Xn+1
b1
2.28571
b2
2.23764
b3
2.23607
b4
2.23607
b5
2.23607
This iteration converges very quickly and the root is 2.23607 to 5 dp.
Error Bounds
Error bounds can be found by showing a change of sign for f(x). For the second root found above, we can find f(x) where x is 2.23607 exactly.
f(2.23606) = -00008.0
f(2.23607) = 00002.0
From this we can conclude that the error bounds are 2.23606 and 2.23607
Limitations of Newton-Raphson Method
Despite taking a starting value close to a function?s root, it is possible that the Newton-Raphson method fails to find that particular root. An example may be with the function f(x) = 4lnx+6/5x+0.75 which is illustrated below.
As can be seen, if the first approximation is close to a turning point which it is likely to be in this case, f?(x) will be very small. This will result in x2 not being close to the root. The values that are being computed may converge but it may be that they are converging towards a root other than the one we are trying to locate.
3. Rearranging f(x) = 0 in the form x = g(x)
When trying to solve an equation f(x) = 0 by an iterative method, we first rearrange f(x) = 0 into a form x=g(x). The iteration formula is then? xn+1 = g(xn)
The equation that will be looked at here is x3-3x-5=0, the graph of which is illustrated below.
As can be seen above there is a root close to x=2.
Rearranging the equation x3-3x-5=0 gives
x = 3?(3x+5)
Using the formula? xn+1 = 3?(3x+5) and starting with x0 = 2, the results for successive iterations are as follows:
X0
2
X1
2.223980091
X2
2.268372388
X3
2.276967161
X4
2.278623713
X5
2.278942719
From this we can conclude that the root of the equation is 2.279 to 3 d.p.
The convergence of a root such as this is often described as a staircase approach; why this is can be seen from the diagram below:
The successive steps taken to approach the root is like that of a staircase with the values of xn approaching from one side. For this particular rearrangement, g(x)= 3?(3x+5):
g?(x) = (3x+5)-2/3
= 1/(3x+5)-2/3
With x0 = 2
g?(2) =0.202 and because? ?g?(2) ?< 1, the sequence converges.
Situation where Iteration Fails to Converge to required root.
The equation x3-3x-5=0 can be rearranged so that x = (x3-5)/3. Using the iteration formula
xn+1 = (xn3-5)/3 and the starting point x0 = 2, the results for successive iterations are as follows:
X0
2
X1
X2
-1.333333333
X3
-2.456790123
X4
-6.609579113
X5
-97.91653871
X6
-312931.4535
This particular rearrangement of the equation x3-3x-5=0 and successive iteration has failed to converge to a root. The sequence is not convergent. It is a divergent sequence and successive members of the sequence are increasingly negative without limit. Why this happens can be seen in the diagram below:
The rearrangement of the equation x3-3x-5=0 into the form g(x)= 3?(3x+5) as shown in green in the diagram has a gradient that is less than the gradient of the line y = x and so the iteration xn+1 = g(xn) converges to the root. However, when the original equation is rearranged into the form g(x) = (x3-5)/3, its curve (shown in black in the diagram above) has a gradient that is greater than that of y=x and so the iteration xn+1 = g(xn) diverges rather than converging to a root.
For the rearrangement g(x) = (x3-5)/3:
g?(x) = 3x2/3= x2
With X0 = 2
g?(2) = 4 and because? ?g?(2) ?> 1, the sequence diverges.
4. Comparison of Methods
Using change of sign method and rearranging method to equation f(x) = x3-5x
The equation f(x) = x3-5x was originally used to demonstrate the Newton-Raphson method. By using the other two methods to find a root of this equation, a comparison can be made with regards to speed of convergence between the three methods.
Decimal Search
From the graph on page 4 we know there is a root between 2 and 3 and so we can carry out a decimal search.
Taking increments in X of 0.1 within the interval [2, 3]
x
2
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
3.0
f(x)
-2
-1.2
-0.3
0.7
We can now continue with increments of 0.01 within the interval [2.2, 2.3].
x
2.20
2.21
2.22
2.23
2.24
2.25
2.26
2.27
2.28
2.29
2.30
f(x)
-0.3
-0.3
-0.2
-0.1
0.04
The interval has been narrowed down to [2.23, 2.24]. Continuing to find the third decimal value of the root:
x
2.230
2.231
2.232
2.233
2.234
2.235
2.236
2.237
2.238
2.239
2.24
f(x)
-0.06
-0.05
-0.04
-0.03
-0.02
-0.01
-0.0007
0.0009
The above calculations show us that the root lies in the interval [2.236, 2.237]. From this we can conclude that the root is 2.2365 +/- 0.0005. Taking into consideration the error bounds, this is the same answer that was reached when the Newton-Raphson method was used.
Rearranging Method
Rearranging the equation into the g(x) = 3?(5x) we can first check whether this rearrangement will result in the iteration converging or diverging by working out g?(x) and testing it for a value close to the root. Differentiating gives:
g?(x)=5/(3x2/3)
g?(2) >1 however if we use 2.25 instead of 2, which is still close to the root, g?(2.25) < 1 and so the sequence should converge.
X0
2.24070
X1
2.23761
X2
2.23658
X3
2.23624
X4
2.23613
X5
2.23610
The answer is the same as obtained by the other two techniques: 2.236 to 3 d.p.
Conclusion
The three techniques demonstrated in this coursework all have their own merits and the speed with which they converge to the sought-after root depends very much on the desired accuracy. For a relatively low number of decimal places (4 or less) the change of sign method is quite fast. The change of sign method has the added benefits of being somewhat simpler to utilise and being consistent. Needless to say care must be taken that the function is a continuous one and one that crosses the x-axis, not simply touch it. The other two methods gave much more accurate results, to nine or more decimal places, and much quicker relative to the time it would have taken the decimal search to take.
The Newton-Raphson method requires one to differentiate first but once the process is set up, very accurate results can be achieved in quite a short amount of time. Having said that, the equation that was used in this investigation was quite simple and straightforward to differentiate but larger, more complex functions would take more time. The rearranging method can be tedious in the sense that once the equation is rearranged, it has to be checked each time by differentiating and using an approximate value for the root. Again, similar to the Newton-Raphson method, if the rearranged function is a large, complex one a significant amount of time may be spent on the calculus part and with this method there is the added uncertainty that even when the function is differentiated it may not be suitable i.e. it may produce a diverging sequence.
The use of SPA Software Omnigraph, Microsoft Excel and my Casio graphical calculator was beneficial for all three methods. Graphs could be easily plotted so that approximate values for boundaries could be seen and calculations were speeded up by the use of formulae functions. Although the use of software and hardware benefited all three methods it is perhaps the change of sign method that was speeded up most as virtually all the calculation with regards to this technique could be done by Excel/Graphical calculator. The other two techniques required differentiation which had to be done by hand. However, if the equation is a simple one that can be differentiated easily, the Newton-Raphson method, once programmed onto a computer is undoubtedly the quickest and reaches a high degree of accuracy in a relatively short amount of time.
