Solutions of Equations by Numerical Methods - Change of sign Method and Decimal Search Method.
Solutions of Equations by Numerical Methods
Change of sign Method
Decimal Search Method
f(x)=x³+2x²-3x+2
The solutions of f(x)=0 are the place where the curve cuts the x-axis.
The graph shows that there is one real root lying in the interval [-4,-3]
f(-4) = -64+32+12+2 = -18
f(-3 )= -27+18+9+2 = 2
The function f(x) is continuous therefore the change of sign form negative to positive in moving from x=-4 to x=-3 shows that there must be a root between the two values.
The decimal search method will locate more accurate values of the root systematically by taking increments of size 0.1 in the interval [-4,-3] until a change of sign occurs.
x
-4
-3.9
-3.8
-3.7
-3.6
-3.5
-3.4
-3.3
-3.2
-3.1
-3
f(x)
-18.000
-15.199
-12.592
-10.173
-7.936
-5.875
-3.984
-2.257
-0.688
0.729
2.000
There is a change of sign between -3.2 and -3.1, this show that the root is in the interval [-3.2,-3.1]
Continuing the decimal search method will increase the accuracy by narrowing down the interval further.
x
-3.20
-3.19
-3.18
-3.17
-3.16
-3.15
-3.14
-3.13
-3.12
-3.11
-3.10
f(x)
-0.688
-0.540
-0.393
-0.247
-0.103
0.039
0.180
0.320
0.457
0.594
0.729
x
-3.16
-3.159
-3.158
-3.157
-3.156
-3.155
-3.154
-3.153
-3.152
-3.151
-3.15
f(x)
-0.103
-0.089
-0.075
-0.060
-0.046
-0.032
-0.018
-0.003
0.011
0.025
0.039
x
-3.153
-3.1529
-3.1528
-3.1527
-3.1526
-3.1525
-3.1524
-3.1523
-3.1522
-3.1521
-3.152
f(x)
-0.003
-0.002
-0.001
0.001
0.002
0.004
0.005
0.007
0.008
0.009
0.011
x
-3.1528
-3.15279
-3.15278
-3.15277
-3.15276
-3.15275
-3.15274
-3.15273
-3.15272
-3.15271
-3.1527
f(x)
-0.00060
-0.00046
-0.00032
-0.00018
-0.00003
0.00011
0.00025
0.00039
0.00053
0.00068
0.00082
The decimal search method has shown that the root lies within the interval
[-3.15276,-3.15275]
The root therefore is -3.152755 with a maximum error of ± 0.000005
Failure of Decimal Search Method
f(x)=x³-2x²-3x-1/2
The graph shows that there is a real root lying in the interval [-1, 0]
f(-1) = -1-2+3-1/2 = -1/2
f( 0 ) = 0-0-0-1/2 = -1/2
The function f(x) is continuous therefore to show that there is a real root a change in sign should occur. However this is the failure of the change in sign method as the change from positive to negative is missed.
Another case where the method would fail would be when using a function which is a discontinuous curve; reciprocal. This is because there may be no roots when f(x) =0 and a change in sign may only occur due to the asymptote.
Fixed Point Estimation Method
Newton-Raphson Method
f(x)=x³-x²-3x+1
The solutions of f(x)=0 are the place where the curve cuts the x-axis.
The graph shows that there are three real roots lying in the intervals [-2,-1], [0,1] and [2,3]
The Newton-Raphson method will locate more accurate values of the roots systematically and with a fast rate of convergence.
f(x) =x³-x²-3x+1
f '(x) =3x²-2x-3
The Iteration formula is: xn+1 = xn - f ( xn )
f '( xn )
f(x)=x³-x²-3x+1
For the interval [-2,-1] :-
X
2
3
4
...
This is a preview of the whole essay
Newton-Raphson Method
f(x)=x³-x²-3x+1
The solutions of f(x)=0 are the place where the curve cuts the x-axis.
The graph shows that there are three real roots lying in the intervals [-2,-1], [0,1] and [2,3]
The Newton-Raphson method will locate more accurate values of the roots systematically and with a fast rate of convergence.
f(x) =x³-x²-3x+1
f '(x) =3x²-2x-3
The Iteration formula is: xn+1 = xn - f ( xn )
f '( xn )
f(x)=x³-x²-3x+1
For the interval [-2,-1] :-
X
2
3
4
5
6
7
8
X
-2
-1.6153846154
-1.4939568508
-1.4813275882
-1.4811943189
-1.4811943041
-1.4811943041
-1.4811943041
The Newton-Raphson method has shown that the root lies within the interval
[-1.48119430405, -1.48119430415]
The root therefore is -1.4811943041 with a maximum error of ± 0.00000000005
f(x)=x³-x²-3x+1
For the interval [0,1] :-
X
2
3
4
5
6
7
8
X
0
0.3333333333
0.3111111111
0.3111078175
0.3111078175
0.3111078175
0.3111078175
0.3111078175
The Newton-Raphson method has shown that the root lies within the interval
[-0.31110781745, -0.31110781755]
The root therefore is -0.3111078175 with a maximum error of ± 0.00000000005
f(x)=x³-x²-3x+1
For the interval [2,3] :-
X
2
3
4
5
6
7
8
X
2
2.2000000000
2.1707865169
2.1700868841
2.1700864866
2.1700864866
2.1700864866
2.1700864866
The Newton-Raphson method has shown that the root lies within the interval
[2.17008648655, 2.17008648665]
The root therefore is 2.17008648655 with a maximum error of ± 0.00000000005
Failure of Newton-Raphson Method
f(x)=x³-3x²+x+1/4
The graph shows that there are three real roots lying in the interval [-1, 0], [0,1] and [2,3]
f(x) = x³-3x²+x+1/4
f '(x) = 3x²-6x+1
For the interval [-1,0] :-
X
2
3
4
5
6
7
8
X
-1
-0.6000000000
-0.4422535211
-0.4150106367
-0.4142142354
-0.4142135624
-0.4142135624
-0.4142135624
For the interval [0,1] :-
X
2
3
4
5
6
7
8
X
0
-1.0000000000
-0.6000000000
-0.4422535211
-0.4150106367
-0.4142142354
-0.4142135624
-0.4142135624
For the interval [2,3] :-
X
2
3
4
5
6
7
8
X
2
2.2000000000
2.1707865169
2.1700868841
2.1700864866
2.1700864866
2.1700864866
2.1700864866
The differentiated function f '(x ) is too small, and is close to a turning point; the iteration converges to another root so that both interval of [-1,0] and [0,1] result in -0.4142135624 with a maximum error of ± 0.00000000005.
Another case where the method would fail would be when using a function which is not defined over the whole of Real Numbers ( ). This method would brake down as the tangent may intersect with the axis at a point outside the domain of the function.
Iterative Method
x = g(x) Method
f(x)=x³-2x²-2x+2
The solutions of f(x)=0 are the place where the curve cuts the x-axis.
The graph shows that there are three real roots lying in the intervals [-2,-1], [0,1] and [2,3].
f(x) can be rearranged and written in the form of x=g(x) to locate more accurate values of the roots systematically.
f(x) = x³-2x²-2x+2
g(x)= 1/2 (x³-2x²+2)
The roots of the equation x=g(x) are the values of x at the points of intersection of the line y=x and the curve y=g(x).
The graph shows that there are three real roots lying in the intervals [-2,-1], [0,1] and [2,3].
By substituting y=g(x) into the iterative formula accurate values of the roots can be located.
xn+1 = g(xn ) = 1/2 { (xn)³-2(xn)²+2) }
I shall use method x=g(x) to obtain the root lying in the interval [0,1].
X
2
3
4
5
6
7
8
X
0
.0000000000
0.5000000000
0.8125000000
0.6080322266
0.7426925379
0.6532395018
0.7126539366
X
67
68
X
0.6888921825
0.6888921825
This shows that the root lies within the interval
[0.68889218245, 0.68889218255]
The root therefore is 0.6888921825 with a maximum error of ± 0.00000000005
For iterations to converge the derivative of g(x) must lie between -1 and 1.
-1< g'(x) <1
g(x) = 1/2 (x³-2x²+2)
g'(x)= 1/2 (3x²-4x)
g'(x)= 1/2 { 3(0.6888921825)²-4(0.6888921825) } = -0.6659257063
This shows that g'(x) lies within the limits and therefore converges to the root.
Failure of x = g(x) Method
f(x) can be rearranged and written in the form of x=g(x) to locate more accurate values of the roots systematically.
f(x) = x³-2x²-2x+2
g(x)= ?(2x²+2x-2)
xn+1 = g(xn ) = ? { 2(xn)²+2(xn)-2 }
I shall use method x=g(x) to obtain the root lying in the interval [0, 1].
X
2
3
4
5
6
7
8
X
0
-1.25992105
-1.103854247
-1.20980852
-1.14276331
-1.187299068
-1.15859719
-1.177473163
X
49
50
X
-1.1700864872
-1.1700864872
This shows that the root lies within the interval
[-1.17008648715,-1.17008648725]
The root therefore is -1.1700864872 with a maximum error of ± 0.00000000005
For iterations to converge the derivative of g(x) must lie between -1 and 1.
-1< g'(x) <1
x = -1.1700864872
g(x) = ? (2x²+2x-2)
g'(x)= 1/3 (2x²+2x-2)-2/3 (4x+2)
g'(x)= 1/3 (2(-1.1700864872)²+2(-1.1700864872)-2)-2/3(4(-1.1700864872)+2) = -1.093834701
This shows that the root is -1.1700864872 which does not lie in the interval [0,1], or the boundary -1< g'(x) <1. This is because the iterations are diverging away from the root.
Numerical Methods
Comparison of Methods
f(x)=x³-x²-3x+1
The solutions of f(x)=0 are the place where the curve cuts the x-axis.
The graph shows that there are three real roots lying in the intervals [-2,-1], [0,1] and [2,3].
I shall apply each of the three methods to the function of f(x) to obtain more accurate values of the root lying in the interval [0,1].
Decimal Search Method:
f(0) = 0-0-0+1 = 1
f(1) = 2-9-9+1= -2
x
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
f(x)
.000
0.691
0.368
0.037
-0.296
-0.625
-0.944
-1.247
-1.528
-1.781
-2.000
x
0.30
0.31
0.32
0.33
0.34
0.35
0.36
0.37
0.38
0.39
0.40
f(x)
0.037
0.004
-0.030
-0.063
-0.096
-0.130
-0.163
-0.196
-0.230
-0.263
-0.296
x
0.31
0.311
0.312
0.313
0.314
0.315
0.316
0.317
0.318
0.319
0.32
f(x)
0.00369
0.00036
-0.00297
-0.00630
-0.00964
-0.01297
-0.01630
-0.01963
-0.02297
-0.02630
-0.02963
x
0.311
0.3111
0.3112
0.3113
0.3114
0.3115
0.3116
0.3117
0.3118
0.3119
0.312
f(x)
0.00036
0.00003
-0.00031
-0.00064
-0.00097
-0.00131
-0.00164
-0.00197
-0.00231
-0.00264
-0.00297
x
0.3111
0.31111
0.31112
0.31113
0.31114
0.31115
0.31116
0.31117
0.31118
0.31119
0.3112
f(x)
0.00003
-0.00001
-0.00004
-0.00007
-0.00011
-0.00014
-0.00017
-0.00021
-0.00024
-0.00027
-0.00031
The decimal search method has shown that the root lies within the interval
[0.31110,0.31111]
The root therefore is 0.31115 with a maximum error of ± 0.000005
Newton-Raphson Method:
f(x) =x³-x²-3x+1
f '(x) =3x²-2x-3
The Iteration formula is: xn+1 = xn - f ( xn )
f '( xn )
f(x)=x³-x²-3x+1
For the interval [0,1] :-
X
2
3
4
5
6
7
8
X
0
0.3333333333
0.3111111111
0.3111078175
0.3111078175
0.3111078175
0.3111078175
0.3111078175
The Newton-Raphson method has shown that the root lies within the interval
[-0.31110781745, -0.31110781755]
The root therefore is -0.3111078175 with a maximum error of ± 0.00000000005
x = g(x) Method:
f(x) = x³-x²-3x+1
g(x)= 1/3 (x³-x²+1)
xn+1 = g(xn ) = 1/3 { (xn)³-(xn)²+1) }
X
2
3
4
5
6
7
8
X
0
0.3333333333
0.3086419753
0.3113804417
0.3110776589
0.3111111535
0.3111074484
0.3111078583
X
2
3
X
0.3111078175
0.3111078175
This shows that the root lies within the interval
[0.31110781745, 0. 31110781755]
The root therefore 0.3111078175 with a maximum error of ± 0.00000000005
For iterations to converge the derivative of g(x) must lie between -1 and 1.
-1< g'(x) <1
g(x) = 1/3 (x³-x²+1)
g'(x)= 1/3 (3x²-2x)
g'(x)= 1/3 { 3(0.3111078175)²-2(0.3111078175) } = -0.1106171376
This shows that g'(x) lies within the limits and therefore converges to the root.
Comparison of Methods
Decimal Search Method: this method is simple and affective and can be carried out with ease using any type of software or hardware including a graphics calculator or Windows Excel. This method is a reliable method which only fails in rare certain circumstances. However, this method is not as accurate or as quick to converge as the other two methods, it is time consuming to carry out especially without the help of software such as Excel which helps to carry out all calculations quickly and efficiently.
Newton-Raphson Method: This method is fairly simple to carry out and is the quickest of the two methods. The iteration formula can be carried out with no difficulty with the help of a computer package such as excel or a graphics calculator. The Newton-Raphson method had a fast rate of convergence and is fairly straightforward in using the results to find where the root lies. This method is also a reliable method only failing in certain situations. It is a very accurate technique and can find the root with a maximum error of ± 0.00000000005. However without the use of software or hardware the calculations can be laborious.
x = g(x) Method: This is the most complicated of the two methods but also very meticulous if conducted correctly. However, there is a lot of room for error and mistakes are hard to see until the very end. This method requires the most work and need for the use of different software and hardware. It has a slower speed of convergence than the Newton-Raphson method and can often diverge away towards another root. Despite the unreliability checks can be made to ensure correct results such as making sure that the derivative of g(x) must lie between -1 and 1. This is what confirms the high level of accuracy within the results.
Overall each method has its own attributes which make it better than the other two, so it depends on what type of method you wish to apply; simple calculations which can be carried out with ease would be the decimal search method; fast rate of convergence would be the Newton-Raphson method; and high level of accuracy would be x=g(x) method. However, the Newton-Raphson method stands out as being the best method as it combines all the qualities of the other method by having fairly simple calculations; high speed of convergence; and accurate results. Also although each method is less time-consuming with the use of various software and hardware it is not vital for this particular method.
2.02.03 Rachel Withey