- Level: AS and A Level
- Subject: Maths
- Word count: 1974
Decimal search.
Extracts from this document...
Introduction
Decimal search
The equation f (x) = 0, where f (x) = x3-x2+x-2, has only one real root, but there is no simple analytical method of finding it. Therefore, a spreadsheet had been used to solve the equations numerically using decimal search.
x | f(x) |
-3 | -41 |
-2 | -16 |
-1 | -5 |
0 | -2 |
1 | -1 |
2 | 4 |
3 | 19 |
The table and graph above illustrated the first approximations to the roots of the equation x3-x2+x-2=0.
As the curve crosses the x-axis, f (x) changes sign, so provided that f (x) is a continuous function, once you have located an interval in which f(x) changes sign, you know that that interval must contain a root.
In the table, you first take increments in x of size 1 within the interval 1<x<2, working out the value of the function x5-5x+3 for each one. You do this until you find a change of sign of f(x) between the value of x = 1 and 2 , so you should know that there is a root lying in the interval 1<x<2 on the graph.
Having narrow down the interval, you can now continue 1.3<x<1.4, you could now homing in on such root using decimal search.
x | f(x) |
1 | -1 |
1.1 | -0.779 |
1.2 | -0.512 |
1.3 | -0.193 |
1.4 | 0.184 |
1.5 | 0.625 |
1.6 | 1.136 |
1.7 | 1.723 |
1.8 | 2.392 |
1.9 | 3.149 |
2 | 4 |
- Tabulate f (x) for 1<x<2 with increments in x of 0.1, a change of sign reveals that 1.3<α<1.4.
- Tabulate f (x) for 1.3<x<1.4 with increments in x of 0.01, a change of sign gives 1.35<α<1.36
x | f(x) |
1.3 | -0.193 |
1.31 | -0.158009 |
1.32 | -0.122432 |
1.33 | -0.086263 |
1.34 | -0.049496 |
1.35 | -0.012125 |
1.36 | 0.025856 |
1.37 | 0.064453 |
1.38 | 0.103672 |
1.39 | 0.143519 |
1.4 | 0.184 |
- Tabulate f (x) for 1.35<x<1.36 with increments in x of 0.001, a change of sign gives 1.353<α<1.354
x | f(x) |
1.35 | -0.012125 |
1.351 | -0.008354449 |
1.352 | -0.004577792 |
1.353 | -0.000795023 |
1.354 | 0.002993864 |
1.355 | 0.006788875 |
1.356 | 0.010590016 |
1.357 | 0.014397293 |
1.358 | 0.018210712 |
1.359 | 0.022030279 |
1.36 | 0.025856 |
Middle
1.3534
0.000719797
1.3535
0.001098655
1.3536
0.001477575
1.3537
0.001856555
1.3538
0.002235597
1.3539
0.0026147
1.354
0.002993864
Having established that 1.3532 <α<1.3533, since f(1.3532) <0 and f(1.3533) >0, the maximum error is 1.3533 –1.3532 = 0.0001, which is more than sufficient to give the root correct to 3
decimal places as α = 1.353
Example for problems with change of sign method
If the curve touches the x-axis without crossing it, there will be no change of sign, so change of sign methods are doomed to failure. For example, has a repeated rational root, which can be expressed as a recurring decimal i.e = 0.3333……
Sketch graph of f (x) =(3x-1)2(2x+4) is drawn below, you would notice that there is no change of sign on the graph as well as the table. It seems that there is repeated root between the interval 1<x<2 , it touches the x-axis when you looking at the graph, however, the table shows that all the values of f(x) within the interval 1<x<2 are all positive, there is no change of sign. You are unable to do any further by decimal search for a root without a change of sign.
x | f(x) |
1 | 24 |
1.1 | 32.798 |
1.2 | 43.264 |
1.3 | 55.506 |
1.4 | 69.632 |
1.5 | 85.75 |
1.6 | 103.968 |
1.7 | 124.394 |
1.8 | 147.136 |
1.9 | 172.302 |
2 | 200 |
Newton-Raphson Iteration
This method is based on the iteration.
xn+1 = xn - , n = 0,1,2,3,…….with initial approximation x0.
The Newton – Raphson iterative formula is based on evaluating the gradient of the tangent to the curve y = f(x) at
x = x0
The gradient of the tangent at (x0, f (x0) is f ′ (x)
f ′ (x0) =
Rearranging this,
⇒ x1 = x0 –
To solve the equation ex-7x-3, f (x) = ex-7x-3⇒ f ′ (x) = ex-7. This will give rise to the Newton Raphson iteration formula, that is,
xn+1 = xn –
You will then be able to find the upper root α, let the initial approximation x0 = 4
etc
The sequence converge rapidly towards the upper root to give α=3.2478 to 5 s.f.
In this case, Newton-Raphson Iteration gives an extremely rapid rate of convergence. This is the case for examples, even when the first approximation is not particularly good. For manual caluations it is almost always the most efficient method.
You may try to solve the equation using spreadsheet, it gives a
Iteration: xn+1 = x0 - (ex-7x-3)/(ex-7) | |
Convergence towards upper root | |
n | xn |
0 | 4 |
1 | 3.504221277 |
2 | 3.286134403 |
3 | 3.248830171 |
4 | 3.247850646 |
5 | 3.247849987 |
6 | 3.247849987 |
7 | 3.247849987 |
8 | 3.247849987 |
9 | 3.247849987 |
10 | 3.247849987 |
Conclusion
When the formula for a rearrangement of an equation g(x) is entered correctly with an input of initial approximation(i.e. x0 in this case). Then the approximation would converge towards the root required by simply copy and paste the formula until there is no any changing result.
Sometimes, you have to try which rearrangement is suitable for a particular roots. Plot the line y =x and the curve g (x), then find the gradient near the root, if the gradient is greater than 1 (i.e. the gradient of the line y = x ), illustrated that this is a unsuitable rearrangement of finding the root, and vice versa.
It requires the same techniques as you used in Fixed Point Iteration.
With the first approximation, it then converges gradually to the root required.
Sometimes, there is a problem of plotting a graph by using spreadsheet. For example, +5 ,
it is impossible to plot the point where x = 0, it ends up with a continuous function which is not the expected discontinuous function.
This student written piece of work is one of many that can be found in our AS and A Level Core & Pure Mathematics section.
Found what you're looking for?
- Start learning 29% faster today
- 150,000+ documents available
- Just £6.99 a month