• Join over 1.2 million students every month
• Accelerate your learning by 29%
• Unlimited access from just £6.99 per month

# 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!

 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

Not the one? Search for your essay title...
• Join over 1.2 million students every month
• Accelerate your learning by 29%
• Unlimited access from just £6.99 per month

# Related AS and A Level Core & Pure Mathematics essays

1.  5 star(s)

-1 2 0.5 -0.25 3 0.333333 -0.111111111 4 0.25 -0.0625 I predict that the gradient function for when n=-1 = -x -2, in correspondence to the formula nx n-1. I can tell whether these data do in fact agree with this gradient function, but I shall binomially expand this to verify this is the case: 1 .

2. ## MEI numerical Methods

One thing to note is the amount of iterations for the bisection method compared to secant and false position, bisection has a lot more iterations. As a result the value of K is a constant when the first order of convergence is used.

1. ## Numerical solution of equations, Interval bisection---change of sign methods, Fixed point iteration ---the Newton-Raphson ...

--> by differentiation, Have a look on spreadsheet 3.6; the values of x are diverging. It then becomes further from the actual root. This can be shown graphically on the Graph 3.7.

2. ## Different methods of solving equations compared. From the Excel tables of each method, we ...

Zoom in on the axes we can clearly see that using the Newton-Raphson method gives us one root efficiently. How does the Newton-Raphson method actually work? The graph above shows a part of a function (the blue curve). Suppose we have an estimated value of a root, xn.

1. ## The method I am going to use to solve x&amp;amp;#8722;3x-1=0 is the Change ...

Therefore, to avoid this, we should try both starting value at both end of the interval, but it really consume time to do it. In conclusion, the less steep the grdient, the faster the coverging is. If the gradient is steep, the root can also be found but not as efficient as a less steep g'(x).

2. ## Numerical integration can be described as set of algorithms for calculating the numerical value ...

M1- M2= 0.014904178 M2-M4 = 0.003624350 The ratio between the differences is (0.003624350/0.014904178)= 0.2421. This means that as the height of the rectangles half (h/2) and the number of rectangles doubles, the error is 1/22. This absolute error can be derived form the following concept: An area under a curve uses Mn rectangles, each of height h.

1. This graph will be at a minimum curve. When a curve is at a minimum it always encompasses a gradient which goes from a negative to a positive. y=x2 is a minimum curved graph. Results x Gradient 3 6.54 4 8.33 -2 -4.44 From this graph, the results achieved are not absolute accurate, this is due to the graph plot.

2. ## Fractals. In order to create a fractal, you will need to be acquainted ...

Therefore, any point on the complex plane would have (real #, imaginary #). For example, the orbit of constant i and seed 0 under x2 + i is given by z0 = 0 z1 = i z2 = -1 + i z3 = -i z4 = -1 + i z5 • Over 160,000 pieces
of student written work
• Annotated by
experienced teachers
• Ideas and feedback to 