Hange of sign, Newton-Raphson and the rearrangement method and are going to use them to find roots of different equations, and hence
INTRODUCTION
For my investigation, I will analyse the use three methods which are called the: change of sign, Newton-Raphson and the rearrangement method and are going to use them to find roots of different equations, and hence compare the merits and flaws of the methods with each other. I will analyse which is the best in terms of factors such as a speed of convergence and ease of use with available software and hardware.cocb
1. For Change of sign method (Decimal search) I use these equations:
2. For Newton-Raphson method (Fixed point iteration) I use these equations:
-3ex +2x3+6=0
x3-2x2-2x+3=0
3. For Rearranging f(x) = 0 in the form x = g(x), I use these equations:
In my course work, I will use computer (hardware) and Autograph (plot the graph), and
Microsoft Excel (spreadsheet), Microsoft Word.
Change of sign method:
This method finds the roots of an equation by looking at the points where the graph crosses x axis. In these case the value of f(x) change sign from positive to negative or vice versa. And the root must be some where between two values that change.
For this equation:
Function . I am going to use the decimal search.
Check the shape of the graph
This is quadratic equation a = 6, b = 0, c = -4
D = b2-4ac = 0)2- 4x6x(-4) = 96>0 the graph has 2 turning points.
As the graph shows there are three roots.
I calculated each of the f(x) values in order to see where the change in sign was, as shown in the table on follow page 3 :
There is a root in the interval of [1, 2] which I have chosen to investigate. Now I use excel to calculate the change values of f(x) by taking increments in x of size 0.1 for the equation that we are using.
As the graph and the table show, there is a change of sign between x=1.5 and x=1.6. and thus the new interval in [1.5,1.6]. I then take decimal search to 2 decimal places. The result is:
I will carry on using this method to find the root to 6 decimal places for accuration. And the result tables are placed on the next page..
By increasing in x of size 0.001
By increasing in x of size 0.0001
By increasing in x of size 0.00001
So, using these tables we can say that the root is 1.525685 with maximum error bounds of 0.000005
Where this method fails
The change of sign method was succesfull in the equation above. However it can fail in many cases when the curve touches the x axis, but does not cross it. It is repeated root, so it does not have the change of sign from positve to negetive or vice versa. Therefore the change of sign can not be carried on. For this case I'll survey this equation: .
x
f(x)
-3
...
This is a preview of the whole essay
So, using these tables we can say that the root is 1.525685 with maximum error bounds of 0.000005
Where this method fails
The change of sign method was succesfull in the equation above. However it can fail in many cases when the curve touches the x axis, but does not cross it. It is repeated root, so it does not have the change of sign from positve to negetive or vice versa. Therefore the change of sign can not be carried on. For this case I'll survey this equation: .
x
f(x)
-3
7744
-2
1600
-1
100
0
4
1
16
2
784
3
4900
As the graph shown, the curve just touch x axis at two points, and the table shown, does not change of sign where the root is. Thus no estimates for roots can be made, as it never change of sign.
Newton_Raphson method
This method involves taking a rough approximation of x, and then improving this each time to get a more accurate value for x.
This method uses interation process in order to find all the roots of the equation. I start to draw a tangent to the curve at point (x0,f(x0)) which x0 near the root of f(x)=0. The tangent cut x axis at x1 which nearer the root. Then I draw a tangent to the curve at point (x1, f(x1)). I will reapet this process untill it coverges to the root. Each iteration is caculated from last value by this formula:
For this method, I'll ivestigate this equation: f(x) = -3ex +2x3+6
x
f(x)
-2
-10.406
-1
2.896362
0
3
1
-0.15485
2
-0.16717
3
-0.25661
4
-29.7945
As the graph and table shown, there were three roots A, B, C and D. I will chose root A to investigate which was interval between [-2, -1]. I will draw a tangent to the graph at the point x1=-1. Where the tangent cuts the x axis I have the second point x2. I will continue to draw the new tangent to the curve at x2, and repeat this process untill it converges to the root A.
Now I will use the Newton_Raphson formula to calcultate each iteration.
f'(xn) is the tangent of the curve at xn
With as the tangent of the curve at x
And x0 = -1
Now I have:
x2 = -1.40826
x3 = -1.37965
x4 = -1.37898
x5 = -1.37898
When the values of x iteration, we know that the root is x =-1.37898 0.000005.
To check error bound of this root, I will check the sign of the y-co-ordinate on each side of the root
f(-1.378975) = 0.0000497031
f(-1.378985) = -0.0000568370
There is a change of sign so there is a root
Now I will find the other roots without illustrated it graphically
For root B
x0 =
0.5
x1 =
0.878344
x2 =
0.930251
x3 =
0.932149
x4 =
0.932252
x5=
0.932252
x = 0.932252±0.0000005 is root B
For root C
x0 =
2.5
x1 =
.762462
x2 =
2.221205
x3 =
2.086422
x4 =
2.087997
x5=
2.087996
x6=
2.087996
x = 2.087996±0.0000005 is root C
For root D
x0 =
3
x1 =
2.95898
x2 =
2.95524
x3 =
2.95521
x4 =
2.95521
x=2.95521±0.000005 is root D
Failure of Newton_Raphson method:
However, there are times when Newton_Raphson is failed to find the root. Failure can happen when the iteration does not converge towards the root.
For this failure I'll draw a graph of f(x) =x3-2x2-2x+3 .
As the graph shown on the previous page, there is a root between the interval of [-2, -1 Normally when the value in the graph is chosen the calculations would have led the tangent the root found between the x values -2 and -1.As shown on the graph above, the interation converges towards another root which is in another side of y axis, and not the root that I was investigating.
Rearranging f(x)=0 in the form x=g(x)
The rearranging is also a fixed point iteration.
I will be using this equation .
Function
With iteration process, I'll rearranging f(x)=0 in the form x =g(x)
3x3 -4x -1/2 = 0
And then my rearranged equation is
g1(x) =
g2(x) = (3x3-0.5)/4
The gradient of the curve g(x)=0 at root must be between -1 and 1.Its mean -1<g'(x)<1
Now I'll plot the graph and two function g(x)
As the graph shown there was three roots. I am going to find the value of the root which is between interval of [1, 2].
On the graph f(x) =0 when g(x) intersects the line y=x
I'll be using g1(x) to find the root C for this investigation.
And this is iteration formula for g1(x):
xn+1 =
I start with x0 = 1
x1 = ((4x0+1/2)/3)1/3
x1 = (4x(-1)+1/2)/3)1/3
Now I use excel to calculate the next values of x.
x0 =
x1 =
.14471
x2 =
.19183
x3 =
.20640
x4 =
.21083
x5 =
.21217
x6 =
.21257
x7 =
.21270
x8 =
.21273
x9 =
.21275
x10 =
.21275
-->Corret to 5 decimal place
The root is x=1.21275±0.000005
f(1.212745)= -0.0000442910 and
f(1.212755)= 0.0000480776.
Differentiated
g1'(1.2)0.34<1 this confirm that g1(x) does work to find root C.
Where is this method failed:
This method of rearrangement also fails to produce roots in certain cases. Consider the same graph but this time it is the second intersection of the line and g2(x). I'm going to find the root between interval [1, 2]
Start from x0 = 1.3
x1 = (3x03-0.5)/4
x1 = (3x1.33-0.5)/4
x1 = 1.52275
x2 = 2.52318
x3 = 11.92271
As you can see, the iterations just keep getting further and further from the point
Differentiated
g2'(2) = 9>1 Converges fails to find root C using g2(x)
COMPARISON
The equation used in the change of sign method and the root I found is 1.21275±0.000005 be solved using the Change of Sign and Newton-Raphson methods.
Change of sign:
Equation:
Function:
Newton-Raphson
Equation:
Function:
Change of sign method
x
y
-2
-16.5
-1
0.5
0
-0.5
1
-1.5
2
15.5
To get an answer as accurate as the previous methods, I need an accuracy of ±0.00005. This takes another 20 iterations.
x
y
x
y
x
y
x
y
x
y
1
-1.5
1.2
-0.116
1.21
-0.02532
1.212
-0.00692
1.2127
-0.00046
1.1
-0.907
1.21
-0.02532
1.211
-0.01613
1.2121
-0.006
1.21271
-0.00037
1.2
-0.116
1.22
0.067544
1.212
-0.00692
1.2122
-0.00508
1.21272
-0.00028
1.3
0.891
1.23
0.162601
1.213
0.002312
1.2123
-0.00415
1.21273
-0.00018
1.4
2.132
1.24
0.259872
1.214
0.011565
1.2124
-0.00323
1.21274
-9E-05
1.5
3.625
1.25
0.359375
1.215
0.02084
1.2125
-0.00231
1.21275
1.89E-06
1.6
5.388
1.26
0.461128
1.216
0.030137
1.2126
-0.00138
1.21276
9.43E-05
1.7
7.439
1.27
0.565149
1.217
0.039456
1.2127
-0.00046
1.21277
0.000187
1.8
9.796
1.28
0.671456
1.218
0.048797
1.2128
0.000464
1.21278
0.000279
1.9
12.477
1.29
0.780067
1.219
0.058159
1.2129
0.001388
1.21279
0.000371
2
15.5
1.3
0.891
1.22
0.067544
1.213
0.002312
1.2128
0.000464
So root in [1.21274, 1.21275], x = 1.212745 with maximum error bounce is ±0.000005.
For Newton -Raphson, using x0 = 1 as starting point
x1 = 1.3
x2 = 1.22052
x3 = 1.21282
x4 = 1.21275
x5 = 1.21275
This shown that the root is 1.21275 ±0.000005,
it took only 5 iterations.
So in speeds of convergence, the Change of Sign method takes 20 steps, x=g(x) method takes 10 steps and the Newton-Raphson method takes 5 for this equation. This order of speed is a good representation of most equations that I have investigated.
The three methods (Change of Sign, Newton-Raphson, and the Rearrangement Method) differ in their ease-of-use and speed. The Change of Sign method takes the simple initial work; for the Newton-Raphson method and rearranging, f'(x) and g'(x) needs to be calculated. For many equations, differentiating them is very complicated, more calculations are required. And the rearranging method requires rearranging the formula to start with. There for spend more time to build the formula. For g(x) functions with more than one root, the rearranging method will usually fail to find at least one of them.
The Hardware available such as computer is used a large part in the ease of each method, it helps greatly, as complex calculations can be done easily. This is helpful in all three methods, as may be seen above.
Graphical calculators can also make a comprehensive view of three methods.
The Software available also can make different methods a lot easier. Spreadsheets (using Microsoft Excel) and Graphs (entirely drawn using Autograph) can be link into text documents (Microsoft Word) quickly and clearly, and thus reference can be made to them throughout a report. Therefore, the software available is used a large part in the ease of which each method can be completed.
C3 Coursework
