The root is in the interval [1.12, 1.13]
The root is somewhere inside the interval [1.127, 1.128]. It is required that the root is found to 3 decimal places. Therefore it is essential to know the value of f(x) when x=1.1275
It is clear that f(x) is negative when x=1.1275. This means that the root lies in the interval [1.127, 1.1275]. Due to the fact that all values within this interval, when rounded to 3 decimal places, equal 1.127, the root of f(x)=3x3-7x2-11x+17 correct to 3 decimal places is 1.127. The error bond for this root is 1.12725 ± 0.00025.
Failure of Decimal Search:
The decimal search method can fail to find the roots of a function. An example of this is when the method is applied to find the roots of the function f(x)=x3-3.3x2+0.24x+4.72
Using the table as the method to find the roots, the following results are obtained.
From the table, it would appear that there is only one root between the values for x of -4 to 5. However, the graph on the next page shows that there are two more roots in this interval, both between the values of 2 and 3.
This can be confirmed with a table showing the values of f(x) when x is between 2 and 3.
As shown, there are two roots in this interval, 2.1 and 2.2 this due to the fact as the f(x) value is shown as zero, which led to the table not being able recognize a change in sign, as looking at the whole picture those changes cancel each other out.
The Newton-Raphson Method:
The Newton-Raphson method is much more sophisticated than the Decimal Search method. It depends on the principle that a curve will be pointing (its tangent) at the root of an equation. To find the roots it takes the derivative of the equation and then calculates where the tangent to the line at a given point will cross the x-axis. This is done using the derivative to find out the gradient of the tangent and then the equation x(n+1) = xn(f(xn)/f'(xn)) to find out where the tangent hits the x-axis. It then takes this new value of x and uses that as the value to find the tangent. Below a graphical illustration has been added.
The Newton-Raphson method is a method whereby an irregular approximation of the root is made (called x1) and the tangent to the curve at x1 is drawn. The point on the x-axis where this tangent hits is made x2 (see diagram) and again a tangent to the curve is drawn at x2. The process continues until the root is found.
In order to set up a table to be able to find the root, a calculation must be created to find x2 quickly from x1. This is done using the following equations.
The gradient of y=f(x) at a certain point P on the graph whose x-coordinate is x1 is equal to both f1(x1) and also f(x1)-0
x1-x2
Therefore, f1(x1)=f(x1)
x1-x2
and x2= x1-f(x1)
f1(x1)
So, in order to calculate the next estimate of x, called xn+1, place the value for xn into this equation:
xn+1= xn- f(xn)
f1(xn)
This method was adopted to be able find all three roots for the function:
f(x)=2x3-13x2+7x+11
The following tables of data could be obtained by the use of the formula:
The root is therefore found to be -0.66529 ± 0.000005, as the calculations are only accurate as required to 5 decimal places.
The finding of the roots has been illustrated in the diagram below:
Further roots can also be found, by adapting the same process but with a different initial xn.
AS i have been asked to find all the roots all the other roots have been presented below:
This table shows that the function has a root of 1.44528 ± 0.000005
This table shows that the function has a root of 5.72001 ± 0.000005
Failure of the Newton-Raphson Method:
The Newton-Raphson method can fail to find the root of a function, as in the following example. The function is f(x)=20-((x-3)2+0.05)-1
It is clear from simply looking at the function that one root is going to be x=3. However, if the Newton-Raphson method is used, the following data is obtained
As can be seen on the diagram below, these figures are clearly divergent, which means that xn+1 is further from the root than xn, and so there is no use in finding the root of the function.
Fixed Point Iteration:
This method to find the roots of a function is done by rearranging the function f(x) into the form x=g(x). This i will be explaining with an example. If the expression xn+1=0.8+2.6/xn is used to create a large table of values for xn+1, it is found that after x50 and x51 are both 2.061324773. This means that xn+1 converges on this figure. If we let the limit L=2.061324773, then L satisfies the equation L=0.8+2.6/L and therefore L2-0.8L-2.6=0 and therefore L is a root of f(x). The function that I will be finding the roots of is f(x)=x3-4x2-7x+11. In order to find the roots, the equation f(x)=0 must be rearranged into the form x=g(x). Therefore, g(x) = (x3-4x2+11)/7
Now, xn+1=xn3-4xn2+11 is used to generate a table of values for xn, the results
7
are as follows:
Failure of Fixed Point Iteration:
There are certain functions where the sequence does not converge on a root. An example of this is the function f(x)=x3-4x2-3x+11. When rearranged, g(x) = (1/3)(x3-4x2+11)
The following data can then be obtained using the rearranged function.
It would appear that the sequence does not converge upon any one root as no consistency can be found. The diagram below shows that this is indeed the case.
After approximately 400 calculations, the sequence has not got close to converging on the root. The closest x value to the root appears to be x1 and so it can reasonably be assumed that it will never converge.
Looking again at g1(x), in this case
g1(x) = (1/3)(3x2-8x)
and as the root is approximately -1.6 g1(d) equals:
g1(d) = -1.707 (to 3 decimal places)
Therefore |g1(d)|>1 and the sequence does not converge.
Comparison of Methods:
The function whose roots will be found by every method was chosen to be f(x)=2x3-13x2+7x+11, whose three roots have already been found using the Newton-Raphson method. Using the decimal search method,
It is clear that there is a root in the interval [1, 2]
The root is in the interval [1.4, 1.5]
The root is in the interval [1.44, 1.45]
The root is in the interval [1.445, 1.446]
As the root is in the interval [1.445, 1.4455] and all the numbers within that range, when rounded to 3 decimal places, equals 1.445, then one of the roots of that function is 1.445 correct to 3 decimal places. This result agrees with the Newton Raphson method which gave the root to 5 decimal places as 1.44528 which, when rounded to 3 decimal places, gives 1.445
Using the fixed point iteration by rearrangement method, the function can be rearranged to give
xn+1 = √((2xn3+7xn+11)/13)
When data is obtained from this calculation, the following sequence is recived:
As noticeable, the sequence clearly converges to 1.445281, and as a result agrees with both of the other methods as the root for this function, when rounded to 3 decimal places is 1.445.
Weighing up the quality’s of those Methods:
Using the three methods it is noticeable that the method that is the slowest to obtain the root is the decimal search method. The quickest method is the Newton-Raphson method, closely followed by the fixed point iteration. However, although both iteration methods can find the root correct to several decimal places very quickly, there is more preliminary work in order to start using these methods in comparison to decimal search. Formulae must be rearranged or new formulae are required to be constructed in order to begin the search. Also, the speed is dependent on the tools used such as the computer where the repetitive iteration speed depends on the computer. They are well suited to the use of computers whereas the decimal search method is relatively slow even with the use of computers as spreadsheets have to be drawn up and entered manually several times to get to the correct answer, also human abilities in spotting the change in sign are clearly time consuming and so with an extra delay is added.
Conclusion:
In Conclusion, there is no reason why the decimal search method could fail when used in conjunction with a graph plotted accurately using a calculator or computer to determine the rough approximations of the roots before actually obtaining the root, while with the other two methods some functions will be present where it will be impossible to obtain even an estimate of the roots.