- Level: AS and A Level
- Subject: Maths
- Word count: 4415
Numerical solution of equations, Interval bisection---change of sign methods, Fixed point iteration ---the Newton-Raphson method
Extracts from this document...
Introduction
A2 Mathematics---Core 3 Coursework Felix Cheng
Numerical solution of equations
Introduction
What is numerical method?
We may occasionally encounter some equations which cannot be solved by algebraic or analytical method. In order to obtain the answers, numerical methods can be used for solving those equations. In this coursework, I am going to use three numerical methods to solve the cubic and non-trivial equations. The methods are shown as follows:
- Interval bisection---change of sign methods
- The Newton-Raphson method---fixed point iteration
- Rearranging the equation f(x)=0 into the form x=g(x)---fixed point iteration
Each method shown above will be applied to one different cubic and non-trivial equation. In addition to the application, I will compare the other two methods by applying one of the three equations, thereby comparing their ease of use and speed of convergence.
*in this coursework, programme including Microsoft Excel (used for calculations) and Autograph 2.10 (used for drawing graphs) will be used so as to enhance the process of the coursework.
Interval bisection---change of sign methods
Given that the equation y=f(x) is a continuous function in which no asymptotes or other breaks occur, we look for the roots of the equation f(x) = 0. In the usual case, all we need to do is just to factorize the formula and then solve the equation easily. In this case, a formula y = (2x-3)(x+1)(x-2)- which is non-trivial equation, is chosen for showing how the roots of the equation will be obtained.
But in my equation the product of the factor is not equal to 0. It implies that neither using algebraic nor analytical method is possible. Thus, an alternative way to find out the solution has to be sought.
The solution I would like to introduce first is the change of sign method.
When we are solving the equation f(x)
Middle
1
-1
-0.3158
0
0.0142
-0.5
-0.0008
0.5
2
-0.5
-0.0008
0
0.0142
-0.25
-0.002675
0.25
3
-0.5
-0.0008
-0.25
-0.002675
-0.38
0.00177813
0.125
4
-0.375
0.001778125
-0.25
-0.002675
-0.31
-0.000302
0.0625
5
-0.375
0.001778125
-0.3125
-0.000301953
-0.34
0.00086626
0.03125
6
-0.34375
0.00086626
-0.3125
-0.000301953
-0.33
0.00030275
0.015625
7
-0.328125
0.000302753
-0.3125
-0.000301953
-0.32
4.1191E-06
0.0078125
8
-0.320313
4.11911E-06
-0.3125
-0.000301953
-0.32
-0.0001482
0.00390625
9
-0.320313
4.11911E-06
-0.31641
-0.000148166
-0.32
-7.181E-05
0.001953125
10
-0.320313
4.11911E-06
-0.31836
-7.18133E-05
-0.32
-3.379E-05
0.000976563
11
-0.320313
4.11911E-06
-0.31934
-3.37918E-05
-0.32
-1.482E-05
0.000488281
12
-0.320313
4.11911E-06
-0.31982
-1.48222E-05
-0.32
-5.348E-06
0.000244141
13
-0.320313
4.11911E-06
-0.32007
-5.34794E-06
-0.32
-6.135E-07
0.00012207
14
-0.320313
4.11911E-06
-0.32019
-6.13511E-07
-0.32
1.753E-06
6.10352E-05
15
-0.320251
1.75303E-06
-0.32019
-6.13511E-07
-0.32
5.6981E-07
3.05176E-05
16
-0.320221
5.69814E-07
-0.32019
-6.13511E-07
-0.32
-2.183E-08
1.52588E-05
17
-0.320221
5.69814E-07
-0.32021
-2.18343E-08
-0.32
2.7399E-07
7.62939E-06
18
-0.320213
2.73993E-07
-0.32021
-2.18343E-08
-0.32
1.2608E-07
3.8147E-06
19
-0.32021
1.2608E-07
-0.32021
-2.18343E-08
-0.32
5.2123E-08
1.90735E-06
20
-0.32021
5.21233E-08
-0.32021
-2.18343E-08
-0.32
1.5145E-08
9.53674E-07
Spreadsheet 1.8
Graph2.9--- bisection of y = (x+0.3) (x+0.5) (x+0.1)-0.0008
Consequently, we have got a root of -0.32021 (to five decimal places) between the interval [-1, 0]. The answer obtained in fact is one of the right roots. However, from the graph above, the graph intersects the x-axis three times, thereby giving 3 different roots. They all lie in the same interval [-1, 0]. Bisectional method has failed to find all the roots when several roots are too close with each other.
Fixed point iteration ---the Newton-Raphson method
An estimate of the root as a starting point has to be set. First of all, for one root of f(x) = 0. We then can draw a tangent to the curve y=f(x) at the point (x1, f(x1)). The point which the tangent cuts the x axis gives the next approximation for the root. Then the process is repeated, as shown in graph 2
The gradient of the tangent at (x1, f(x1)) is f’(x1). Since the equation of a straight line can be written
y-y1 = m(x-x1),
The equation of the tangent is
y-f (x1) = f(x1) [x-x1]
This tangent cuts the x-axis at (x2, 0), so
0- f(x1) = f(x1) [x2-x1]
Rearranging this gives
The Newton-Raphson iterative formulais then formed
On viewing the graph 2.1, the intervals in which the roots lie are [-3,-2], [-1, 0], [0, 1] respectively.
Graph 2.1---
In this case, I choose [0, 1] as the root presented graphically as follows.
First of all, I am going to show the way to find the root in the interval [0, 1]
Graph 2.2---Newton-Raphson for
By using the help of autograph, in interval [0, 1], I get a root of 3 decimal places0.908.
r | Xr | f(Xr) | f'(Xr) | f(Xr)/f'(Xr) |
1 | 2 | 29 | 47 | 0.617021277 |
2 | 1.382978723 | 7.671007388 | 23.2775011 | 0.329546 |
3 | 1.053432723 | 1.678766068 | 13.4149463 | 0.125141468 |
4 | 0.928291256 | 0.205236732 | 10.1818519 | 0.020157112 |
5 | 0.908134144 | 0.004995226 | 9.68744176 | 0.000515639 |
6 | 0.907618504 | 3.23625E-06 | 9.67489018 | 3.345E-07 |
7 | 0.90761817 | 1.36247E-12 | 9.67488204 | 1.40825E-13 |
Spreadsheet 2.3
From spreadsheet 2.3 above, rounding up the solution to 5 decimal places, I get the solution of 0.90762. The error bounds for this is ±0.000005. Hence, the solution is between 0.907615< x < 0.907625
f(0.907625) =
f(0.907615) =
After having checked for the existence of sign change, the method is proved to be successful.
By applying the same method, and choosing 2 other iteration as -2 and 0. I get the following 2 other roots.
r | Xr | f(Xr) | f'(Xr) | f(Xr)/f'(Xr) |
1 | -3 | -31 | 52 | -0.59615385 |
2 | -2.40384615 | -7.53856822 | 27.7755178 | -0.27141054 |
3 | -2.13243562 | -1.23905137 | 18.86605 | -0.06567625 |
4 | -2.06675937 | -0.06467851 | 16.9093736 | -0.00382501 |
5 | -2.06293436 | -0.00021345 | 16.7978087 | -1.2707E-05 |
6 | -2.06292165 | -2.3521E-09 | 16.7974385 | -1.4003E-10 |
7 | -2.06292165 | 1.77636E-15 | 16.7974385 | 1.05752E-16 |
Spreadsheet 2.4
r | Xr | f(Xr) | f'(Xr) | f(Xr)/f'(Xr) |
1 | -1 | 5 | -4 | -1.25 |
2 | 0.25 | -1.953125 | -2.4375 | 0.801282051 |
3 | -0.55128205 | 2.46943433 | -6.67504931 | -0.36994998 |
4 | -0.18133208 | 0.02029835 | -6.15472471 | -0.00329801 |
5 | -0.17803406 | 2.58642E-05 | -6.13900736 | -4.2131E-06 |
6 | -0.17802985 | 4.25595E-11 | -6.13898716 | -6.9327E-12 |
7 | -0.17802985 | 0 | -6.13898716 | 0 |
Conclusion
Secondly, Newton-Raphson method is relatively trickier, includinginserting four formulae into Excel to define Xn, f(Xn), f'(Xn)andf(Xn)/f'(Xn). At the same time, the equation of f(Xn) is needed to be calculated by differentiation algebraically. Further, the calculator is not the only thing needed. It can only work with the aid of autograph programme. The reason is that this can give us a clue of what approximation value of the roots should be taken, thereby avoiding taking any approximation value which is near the turning point and converse to a false root.
Thirdly, when applying rearranging equations, the equation f(x) has to be converted into the form of g(x) algebraically. After that, I use Autograph to draw the curve y = x and g(x) to find where the intersection points lie. I can then use Excel spreadsheet to insert one approximation value of the starting point and the accuracy of the method can be found. In the whole process, one formula is going to be put in. However, the gradient of the graph at the root have to be less than on, otherwise it will fail to find the root. All in all, the less complex the f (x) is, the more convenient we can use this method by rearranging the f(x) = 0 into the form x = g(x).
To conclude, it is most convenient, just typing one formula, to use Excel spreadsheet when using the method of rearranging equations. But, the bisection method is considered to be the easiest one when considering the whole process. It is because all we need to do is just use Excel and even a calculator only, whilst algebraic works is involved in the other two methods which may take longer time and increase the possibility to make mistake. Though I need to type more formulae than the others in Excel, it is still the easiest to deal with.
Page of
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