- Level: AS and A Level
- Subject: Maths
- Word count: 4169
Change of sign method.
Extracts from this document...
Introduction
Melanie Sawyer 7436
52207
Change of sign method
In order to find the roots of an equation that cannot be solved algebraically, I can use numerical methods to do this instead. One of these methods is the change of sign method. From looking at a graph of my equation I can find two integers that my root lies between, then from there, using spreadsheets, I can use the change of sign method to discover where the root lies to five decimal places.
I have chosen to try to solve the equation: 5x3-7x+1=0
First, I drew the graph of y=5x3-7x+1 in autograph to find where the roots roughly lie by looking where the graph cuts the x-axis.
From this graph I can see that there are three roots, in the intervals [-2, -1], [0, 1] and [1, 2]. Looking at the root in the interval [1, 2], we bisect this interval and find the midpoint, 1.5.
f(1.5) = 7.375, so f(1.5) > 0. Since f(1) < 0, the root is in [1, 1.5].
Now I am going to take the midpoint of this second interval, 1.25.
f(1.25) = 2.016, so f(1.25) > 0. Since f(1) < 0, the root is in [1, 1.25].
The midpoint of this reduced interval is 1.125.
f(1.125) = 0.244, so f(1.125) > 0. Since f(1) < 0, the root is in [1, 1.125].
The method then continues in this manner until the required degree of accuracy is achieved. However, this takes a long time to converge the root, and can be solved more rapidly using a spreadsheet.
To put my data into a spreadsheet, I first needed to design one that achieved the desired purpose: finding the roots of the equation using the change of sign method. Below, the formula which I typed into my spreadsheet are shown:
Change of sign method | |||||
y=5x^3-7x+1 | |||||
a | b | (a+b)/2 | f(a) | f(b) | f((a+b)/2) |
1 | 2 | =(A5+B5)/2 | =5*A5^3-7*A5+1 | =5*B5^3-7*B5+1 | =5*C5^3-7*C5+1 |
=IF(D5*F5<0,A5,C5) | =IF(D5*F5<0,C5,B5) | =(A6+B6)/2 | =5*A6^3-7*A6+1 | =5*B6^3-7*B6+1 | =5*C6^3-7*C6+1 |
=IF(D6*F6<0,A6,C6) | =IF(D6*F6<0,C6,B6) | =(A7+B7)/2 | =5*A7^3-7*A7+1 | =5*B7^3-7*B7+1 | =5*C7^3-7*C7+1 |
=IF(D7*F7<0,A7,C7) | =IF(D7*F7<0,C7,B7) | =(A8+B8)/2 | =5*A8^3-7*A8+1 | =5*B8^3-7*B8+1 | =5*C8^3-7*C8+1 |
=IF(D8*F8<0,A8,C8) | =IF(D8*F8<0,C8,B8) | =(A9+B9)/2 | =5*A9^3-7*A9+1 | =5*B9^3-7*B9+1 | =5*C9^3-7*C9+1 |
=IF(D9*F9<0,A9,C9) | =IF(D9*F9<0,C9,B9) | =(A10+B10)/2 | =5*A10^3-7*A10+1 | =5*B10^3-7*B10+1 | =5*C10^3-7*C10+1 |
From this spread sheet I can find the upper and lower bounds of the intervals so that I can narrow down the accuracy of the root of the equation. Shown above are only the first few rows of the spreadsheet, to find the roots to a high enough accuracy, the formulas are filled down for more rows. If I look at the numbers that are present in the spreadsheet once the equation has been entered, we can find the root to a give number of decimal places.
Change of sign method | |||||
y=5x^3-7x+1 | |||||
a | b | (a+b)/2 | f(a) | f(b) | f((a+b)/2) |
1.0000000000 | 2.0000000000 | 1.5000000000 | -1.0000000000 | 27.0000000000 | 7.3750000000 |
1.0000000000 | 1.5000000000 | 1.2500000000 | -1.0000000000 | 7.3750000000 | 2.0156250000 |
1.0000000000 | 1.2500000000 | 1.1250000000 | -1.0000000000 | 2.0156250000 | 0.2441406250 |
1.0000000000 | 1.1250000000 | 1.0625000000 | -1.0000000000 | 0.2441406250 | -0.4401855469 |
1.0625000000 | 1.1250000000 | 1.0937500000 | -0.4401855469 | 0.2441406250 | -0.1140441895 |
1.0937500000 | 1.1250000000 | 1.1093750000 | -0.1140441895 | 0.2441406250 | 0.0609855652 |
1.0937500000 | 1.1093750000 | 1.1015625000 | -0.1140441895 | 0.0609855652 | -0.0275378227 |
1.1015625000 | 1.1093750000 | 1.1054687500 | -0.0275378227 | 0.0609855652 | 0.0164708495 |
1.1015625000 | 1.1054687500 | 1.1035156250 | -0.0275378227 | 0.0164708495 | -0.0055966303 |
1.1035156250 | 1.1054687500 | 1.1044921875 | -0.0055966303 | 0.0164708495 | 0.0054213097 |
1.1035156250 | 1.1044921875 | 1.1040039063 | -0.0055966303 | 0.0054213097 | -0.0000916085 |
1.1040039063 | 1.1044921875 | 1.1042480469 | -0.0000916085 | 0.0054213097 | 0.0026638633 |
1.1040039063 | 1.1042480469 | 1.1041259766 | -0.0000916085 | 0.0026638633 | 0.0012858806 |
1.1040039063 | 1.1041259766 | 1.1040649414 | -0.0000916085 | 0.0012858806 | 0.0005970744 |
1.1040039063 | 1.1040649414 | 1.1040344238 | -0.0000916085 | 0.0005970744 | 0.0002527175 |
1.1040039063 | 1.1040344238 | 1.1040191650 | -0.0000916085 | 0.0002527175 | 0.0000805507 |
1.1040039063 | 1.1040191650 | 1.1040115356 | -0.0000916085 | 0.0000805507 | -0.0000055299 |
1.1040115356 | 1.1040191650 | 1.1040153503 | -0.0000055299 | 0.0000805507 | 0.0000375101 |
1.1040115356 | 1.1040153503 | 1.1040134430 | -0.0000055299 | 0.0000375101 | 0.0000159901 |
.1040115356 | 1.1040134430 | 1.1040124893 | -0.0000055299 | 0.0000159901 | 0.0000052301 |
1.1040115356 | 1.1040124893 | 1.1040120125 | -0.0000055299 | 0.0000052301 | -0.0000001499 |
1.1040120125 | 1.1040124893 | 1.1040122509 | -0.0000001499 | 0.0000052301 | 0.0000025401 |
1.1040120125 | 1.1040122509 | 1.1040121317 | -0.0000001499 | 0.0000025401 | 0.0000011951 |
Middle
0.0042419434
-0.0039885210
0.0001235805
0.3769531250
0.3789062500
0.3779296875
0.0001235805
-0.0039885210
-0.0019332887
0.3769531250
0.3779296875
0.3774414063
0.0001235805
-0.0019332887
-0.0009050543
0.3769531250
0.3774414063
0.3771972656
0.0001235805
-0.0009050543
-0.0003907864
0.3769531250
0.3771972656
0.3770751953
0.0001235805
-0.0003907864
-0.0001336152
0.3769531250
0.3770751953
0.3770141602
0.0001235805
-0.0001336152
-0.0000050205
0.3769531250
0.3770141602
0.3769836426
0.0001235805
-0.0000050205
0.0000592792
0.3769836426
0.3770141602
0.3769989014
0.0000592792
-0.0000050205
0.0000271292
0.3769989014
0.3770141602
0.3770065308
0.0000271292
-0.0000050205
0.0000110543
0.3770065308
0.3770141602
0.3770103455
0.0000110543
-0.0000050205
0.0000030169
0.3770103455
0.3770141602
0.3770122528
0.0000030169
-0.0000050205
-0.0000010018
0.3770103455
0.3770122528
0.3770112991
0.0000030169
-0.0000010018
0.0000010076
0.3770112991
0.3770122528
0.3770117760
0.0000010076
-0.0000010018
0.0000000029
0.3770117760
0.3770122528
0.3770120144
0.0000000029
-0.0000010018
-0.0000004994
0.3770117760
0.3770120144
0.3770118952
0.0000000029
-0.0000004994
-0.0000002483
From this chart we can see that when the formulas look to find the root between [0,1], however when it sees the root between [0, 0.5], it does not try to look for the other two, between [0.5, 1]. Hence, failure.
Newton – Raphson method
This is another fixed-point estimation method, and as for the previous method, it is necessary to use an estimate of the root as a starting point.
I start with an estimate, x, for a root of f(x) = 0. Next, I must draw a tangent to the curve y = f(x) at the point (x, f(x)). The tangent will cut the x axis at the next approximation for the root, then tangent will then be found at that new point and so on.
I chose to start looking trying to find the roots for the equation: 3(x/2)3-4(x/2)+1.5=0
so I plotted the graph of y=3(x/2)3 -4(x/2)+1.5 in autograph.
I can see that there are three roots to my equation, in the intervals [0, 1], [1, 2], [-2, -3]. I can use a spreadsheets and close ups of my graph to find the roots to a given number of decimal places. I have chosen to look closely at the root in the interval [0, 1].
Shown below are the formulae that I entered into the spreadsheet to obtain my required results.
Newton Raphson | |
y=3(x/2)^3-4(x/2)+1.5 | |
0 | =A4-((3*(A4/2)^3-4*(A4/2)+1.5)/(((9*A4^2)/8)-2)) |
=B4 | =A5-((3*(A5/2)^3-4*(A5/2)+1.5)/(((9*A5^2)/8)-2)) |
=B5 | =A6-((3*(A6/2)^3-4*(A6/2)+1.5)/(((9*A6^2)/8)-2)) |
=B6 | =A7-((3*(A7/2)^3-4*(A7/2)+1.5)/(((9*A7^2)/8)-2)) |
=B7 | =A8-((3*(A8/2)^3-4*(A8/2)+1.5)/(((9*A8^2)/8)-2)) |
=B8 | =A9-((3*(A9/2)^3-4*(A9/2)+1.5)/(((9*A9^2)/8)-2)) |
The reason the formula A4-((3*(A4/2)^3-4*(A4/2)+1.5)/(((9*A4^2)/8)-2)) is used is because we are trying to find out the new point where the tangent of my equation at my given integer point crosses the x-axis. As we can see from the close up of my graph below, tangents are used to get an increasingly more accurate value for my root.
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]
The tangent cuts the x-axis at (x2, 0), so
0-f(x1)=f’(x1)[x2-x1]
-f(x1)= f’(x1)x2-f’(x1)x1
f’(x1)x1-f(x1)=f’(x1)x2
(f(x1)/f’(x1))x1-(f(x1)/ f’(x1)= x2
x2= x1-(f(x1)/ f’(x1))
Hence the equation is re-arranged to give a closer value for my root on the x-axis. This is the equation that is then typed into my spreadsheet, shown above.
The final value for my root is shown in the numerical spreadsheet below, for the root between [0, 1].
Newton Raphson | |
y=3(x/2)^3-4(x/2)+1.5 | |
0.000000000000000 | 0.750000000000000 |
0.750000000000000 | 0.865714285714286 |
0.865714285714286 | 0.875982340295208 |
0.875982340295208 | 0.876073029827270 |
0.876073029827270 | 0.876073036958846 |
0.876073036958846 | 0.876073036958846 |
0.876073036958846 | 0.876073036958846 |
0.876073036958846 | 0.876073036958846 |
0.876073036958846 | 0.876073036958846 |
0.876073036958846 | 0.876073036958846 |
0.876073036958846 | 0.876073036958846 |
So to five decimal places, the root in the interval [0,1], is 0.87607. To find the other two roots of the equation, I can enter in different starting integers into my spreadsheet to find the root to a given number of decimal places, I have chosen to look at it to five. So for the root in the interval [1, 2], the value is 1.74318 and for the root in the interval [-2, -3], the value is –2.61925.
Error bounds need to be established for the roots however, if we look at our final answer to five decimal places, then take that accuracy one decimal place further, we can see whether our answer is correct.
So for 0.87607:
f(0.876065) = 0.00000913453385
f(0.876075) = -0.0000022311064
Because, the function of one of these numbers is positive and the other is negative, the root that I am searching for must be between the two, hence my answer of 0.87607 is a sensible one.
However, there are some equations that this method fails to find the roots of. If the gradient of the tangent is more than 1 or less than –1, the tangent crosses the x-axis at a point that is further away from the root than the original integer, and hence an increasingly less accurate answer is obtained.
To demonstrate this failure, I have chosen to use the equation: y=ln(2x2-4)+x and to solve it using the equation ln(2x2-4)+x=0. First, I shall look at the graph, as shown below.
This equation fails not only because the gradient of the graph is too steep but also because the graph is discontinuous and there are actually no values for x between [-2, 2] anyway.
When we apply the Newton Raphson tangents, as shown in the graph below, we can see that the tangent moves off away from the root, and an overflow is produced, hence spreadsheets also fail.
Neither integers either side of the root are able to move towards a value for it, and I am also able to see this with the use of a spreadsheet. The formulae that are entered into this spreadsheet are the same that would be applied in a successful Newton Raphson investigation (see above). However, when the numbers are entered, the spreadsheet looks like this:
2.000000000000000 | 0.871235212960036 |
0.871235212960036 | #NUM! |
#NUM! | #NUM! |
#NUM! | #NUM! |
And for when we start with 1 as our integer, the spreadsheet simply looks like this:
1.000000000000000 | #NUM! |
#NUM! | #NUM! |
#NUM! | #NUM! |
#NUM! | #NUM! |
It is not possible to use the Newton Raphson method to solve this equation.
Rearranging f(x)=0 in the form x=g(x)
The first step I must take to find a root for the equation f(x)=0, is to rearrange it in the form x=g(x). To set up the spreadsheet we must look at the line of y=x in conjunction with the rearrangement of my equation.
There are some rearrangements that can be solved using this method and others that this method fails to find the root for. I am going to look at the equation: y=3x3-2x2+4x+7.
I am first going to rearrange it so that: y=3x3-2x2+4x+7
3x3=4x-2x2+7
x3=(4x-2x2+7)
3
x=((4x-2x2+7)/3)(1/3) then I will solve it so that ((4x-2x2+7)/3)(1/3)=0.
This is the graph of y=((4x-2x2+7)/3)(1/3). I can see here that the line y=x and my g(x) cross at one point between the coordinates ([1, 2],[1, 2]). I can now use a spreadsheet to find this root to a given number of decimal places. The root is found in the fixed point iteration method by taking a line from my chosen integer to my g(x) line, then from that point to the y=x line, then back to the g(x) line and so on until the root is found to the highest possible degree of accuracy. As shown on the graph below, this equation creates a cobweb effect when these lines are drawn. Here we can see how the method converges to the root by moving between the two lines until a suitable value is found.
To find these roots on a spreadsheet I must enter these formulae, as explained below:
x | g(x) |
1 | =((4*A2-2*A2^2+7)/3)^(1/3) |
=B2 | =((4*A3-2*A3^2+7)/3)^(1/3) |
=B3 | =((4*A4-2*A4^2+7)/3)^(1/3) |
=B4 | =((4*A5-2*A5^2+7)/3)^(1/3) |
=B5 | =((4*A6-2*A6^2+7)/3)^(1/3) |
=B6 | =((4*A7-2*A7^2+7)/3)^(1/3) |
Conclusion
For this investigation I used several different types of software on my computer. For the spreadsheets I use edexcel, which was easy to use and much more efficient than trying to work out f(x) or g(x) for each line. Autograph was another very useful program because the graphs are drawn neatly and accurately, with no chance of error, and is also very quick to use. The other benefit of autograph is that there are certain functions that can be used, such as the Newton Raphson lines and g(x) iteration lines can be drawn on the graph in autograph.
I used two different types of hardware, my computer with all the programmes listed above and my graphics calculator. The computer was much easier to use because it has a larger screen which I can zoom in on, and more than one thing can be looked at at one time. The graphics calculator was also unreliable and often difficult to pinpoint the exact root that I was trying to look for.
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