• Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month
Page
  1. 1
    1
  2. 2
    2
  3. 3
    3
  4. 4
    4
  5. 5
    5
  6. 6
    6
  7. 7
    7
  8. 8
    8
  9. 9
    9
  10. 10
    10
  11. 11
    11
  12. 12
    12
  13. 13
    13
  14. 14
    14
  15. 15
    15
  16. 16
    16
  17. 17
    17
  18. 18
    18
  19. 19
    19
  20. 20
    20

Change of sign method --- interval bisection method

Extracts from this document...

Introduction

Winnie Zheng

Pure Mathematics 2 Coursework

Change of sign method --- interval bisection method

Introduction:

When I am looking for the roots of the equation, actually what I want is the values of x for which the graph y=f(x) crosses the x-axis. As the graph f(x) crosses the x-axis, there is going to be a sign change of y value on the two sides of the root. Hence provided the function gives a continuous graph, if there is a sign change in a located interval, I will know that the interval contains one root.

For interval bisection method, what I am actually going to do is to divide the interval into two parts, then take the half which contains sign changes of y.

Y=(x-2)(x-4)(x-6)+1

image00.png

From the graph we can see that there are three roots lying in the interval (1,2); (4,5); (5,6). I am going to focus on the root lying in the interval (1,2)

image01.png

I will show the steps on a spreadsheet:

a

b

(a+b)/2

f(x)

error

1

1.00000000

2.00000000

1.50000000

-4.62500000

0.50000000

2

1.50000000

2.00000000

1.75000000

-1.39062500

0.25000000

3

1.75000000

2.00000000

1.87500000

-0.09570313

0.12500000

4

1.87500000

2.00000000

1.93750000

0.47631836

0.06250000

5

1.87500000

1.93750000

1.90625000

0.19644165

0.03125000

6

1.87500000

1.90625000

1.89062500

0.05191422

0.01562500

7

1.87500000

1.89062500

1.88281250

-0.02150679

0.00781250

8

1.88281250

1.89062500

1.88671875

0.01530045

0.00390625

9

1.88281250

1.88671875

1.88476563

-0.00307896

0.00195313

10

1.88476563

1.88671875

1.88574219

0.00611680

0.00097656

11

1.88476563

1.88574219

1.88525391

0.00152043

0.00048828

12

1.88476563

1.88525391

1.88500977

-0.00077889

0.00024414

13

1.88500977

1.88525391

1.88513184

0.00037087

0.00012207

14

1.88500977

1.88513184

1.88507080

-0.00020399

0.00006104

15

1.88507080

1.88513184

1.88510132

0.00008345

0.00003052

16

1.88507080

1.88510132

1.88508606

-0.00006027

0.00001526

17

1.88508606

1.88510132

1.88509369

0.00001159

0.00000763

18

1.88508606

1.88509369

1.88508987

-0.00002434

0.00000381

The formulae I used in the spreadsheet are shown below:

a

b

(a+b)/2

f(x)

error

1

1

2

=1/2*(B2+C2)

=(D2-2)*(D2-4)*(D2-6)+1

=1/2*(C2-B2)

2

=IF(E2<0,D2,B2)

=IF(E2<0,C2,D2)

=1/2*(B3+C3)

=(D3-2)*(D3-4)*(D3-6)+1

=1/2*(C3-B3)

3

=IF(E3<0,D3,B3)

=IF(E3<0,C3,D3)

=1/2*(B4+C4)

=(D4-2)*(D4-4)*(D4-6)+1

=1/2*(C4-B4)

4

=IF(E4<0,D4,B4)

=IF(E4<0,C4,D4)

=1/2*(B5+C5)

=(D5-2)*(D5-4)*(D5-6)+1

=1/2*(C5-B5)

5

=IF(E5<0,D5,B5)

=IF(E5<0,C5,D5)

=1/2*(B6+C6)

=(D6-2)*(D6-4)*(D6-6)+1

=1/2*(C6-B6)

6

=IF(E6<0,D6,B6)

=IF(E6<0,C6,D6)

=1/2*(B7+C7)

=(D7-2)*(D7-4)*(D7-6)+1

=1/2*(C7-B7)

7

=IF(E7<0,D7,B7)

=IF(E7<0,C7,D7)

=1/2*(B8+C8)

=(D8-2)*(D8-4)*(D8-6)+1

=1/2*(C8-B8)

8

=IF(E8<0,D8,B8)

=IF(E8<0,C8,D8)

=1/2*(B9+C9)

=(D9-2)*(D9-4)*(D9-6)+1

=1/2*(C9-B9)

9

=IF(E9<0,D9,B9)

=IF(E9<0,C9,D9)

=1/2*(B10+C10)

=(D10-2)*(D10-4)*(D10-6)+1

=1/2*(C10-B10)

10

=IF(E10<0,D10,B10)

=IF(E10<0,C10,D10)

=1/2*(B11+C11)

=(D11-2)*(D11-4)*(D11-6)+1

=1/2*(C11-B11)

11

=IF(E11<0,D11,B11)

=IF(E11<0,C11,D11)

=1/2*(B12+C12)

=(D12-2)*(D12-4)*(D12-6)+1

=1/2*(C12-B12)

12

=IF(E12<0,D12,B12)

=IF(E12<0,C12,D12)

=1/2*(B13+C13)

=(D13-2)*(D13-4)*(D13-6)+1

=1/2*(C13-B13)

13

=IF(E13<0,D13,B13)

=IF(E13<0,C13,D13)

=1/2*(B14+C14)

=(D14-2)*(D14-4)*(D14-6)+1

=1/2*(C14-B14)

14

=IF(E14<0,D14,B14)

=IF(E14<0,C14,D14)

=1/2*(B15+C15)

=(D15-2)*(D15-4)*(D15-6)+1

=1/2*(C15-B15)

15

=IF(E15<0,D15,B15)

=IF(E15<0,C15,D15)

=1/2*(B16+C16)

=(D16-2)*(D16-4)*(D16-6)+1

=1/2*(C16-B16)

16

=IF(E16<0,D16,B16)

=IF(E16<0,C16,D16)

=1/2*(B17+C17)

=(D17-2)*(D17-4)*(D17-6)+1

=1/2*(C17-B17)

17

=IF(E17<0,D17,B17)

=IF(E17<0,C17,D17)

=1/2*(B18+C18)

=(D18-2)*(D18-4)*(D18-6)+1

=1/2*(C18-B18)

18

=IF(E18<0,D18,B18)

=IF(E18<0,C18,D18)

=1/2*(B19+C19)

=(D19-2)*(D19-4)*(D19-6)+1

=1/2*(C19-B19)

...read more.

Middle

0.000000

-11.937282

-0.916521

0.000000

-11.937282

The formula I used in the spreadsheet are shown below:

x

f(x)

f'(x)

-1

=3*(B3-1)*(B3+1)*(B3+3)+1

=9*B3^2+18*B3-3

=B3-C3/D3

=3*(B4-1)*(B4+1)*(B4+3)+1

=9*B4^2+18*B4-3

=B4-C4/D4

=3*(B5-1)*(B5+1)*(B5+3)+1

=9*B5^2+18*B5-3

=B5-C5/D5

=3*(B6-1)*(B6+1)*(B6+3)+1

=9*B6^2+18*B6-3

From the results I get from the spreadsheet, I can see the root lying between the interval (-1,0) is -0.916521.

2) For the root lying between the interval (0,1):

x

f(x)

f'(x)

1.000000

1.000000

24.000000

0.958333

0.031033

22.515625

0.956955

0.000033

22.467057

0.956954

0.000000

22.467005

The formula I used in the spread sheet are shown below:

x

f(x)

f'(x)

1

=3*(B3-1)*(B3+1)*(B3+3)+1

=9*B3^2+18*B3-3

=B3-C3/D3

=3*(B4-1)*(B4+1)*(B4+3)+1

=9*B4^2+18*B4-3

=B4-C4/D4

=3*(B5-1)*(B5+1)*(B5+3)+1

=9*B5^2+18*B5-3

=B5-C5/D5

=3*(B6-1)*(B6+1)*(B6+3)+1

=9*B6^2+18*B6-3

From the results I get from the spreadsheet, I can see the root lying between the interval (0,1) is 0.956954.

Problems with Newton-Raphson method:

There are some cases in which the Newton-Raphson method does not work:

  1. The function is discontinuous, for example:

y=-1/x +2

image04.png

If the graph is discontinuous, and unfortunately I’ve chosen a starting point near the edge of one part of the graph, using the Newton-Raphson method, the next guess will go to the other side of the graph, getting further and further away from the root we are looking for.

2) Poor choice of starting value. If my initial value is quite far way from a root, the iteration may be divergent, i.e. moving away from the root. For example:

    y= x(x-1)(x-2)+1

image05.png

Using Newton-Raphson method with the first guess x=0.5, from the graph below we can see that actually our second guess is getting further away from the chosen root, so this method failed.

image06.png

  1. if my initial value is near a turning point of y=f(x), the iteration will diverge as well. For example:

y=(x-2)(x-1)x+1

image07.png

For this equation, there is a station point of maximum at around x=0.5; if my first guess is 0.4 then the gradient of the tangent at that point is actually nearly zero, i.e. horizontal to the x-axis, hence out next guess will be very far from out first guess and the root we are looking for. If out first guess is actually at the turning point, the tangent will be horizontal to the x-axis, it will never cut the x-axis by any chance. In both of the cases, the Newton-Raphson method fails.

Rearranging f(x)=0 in the form x=g(x)

Introduction:

This method is actually finding a single value or point of an estimate value of the root rather than identifying the interval in which the root lies.

The method involves rearranging the function f(x)=0 in the form x=g(x). Drawing the graphs y=x and y=g(x) on the same graph:

image08.png

The root of the function f(x)=0 is indeed the intersection of the two lines.

The iteration I am going to use in this method is actually based on:

xn+1=g(xn)

Presenting the iteration graphically, we will have either a ‘staircase’ or a ‘cobweb’ diagram.

For the equation:  f(x)=y=x³+6x²+9x+1

image09.png

rearrange f(x)=0, I get x=-(x³+6x²+1)/9

drawing y=x and g(x)=y=-(x³+6x²+1)/9 on the same graph, I get the graph below:

image10.png

By using the rearranging f(x)=0 into x=g(x) method, it provides the iterative formula xn+1=(-xn³-6xn²-1)/9.  It is shown in the purple line in the graph below.

image11.png

I chose x=-4 as my starting point, find the corresponding value of g(-4). Next, we take this value g(-4) as the next guess, this means that x2=g(-4) and move the point horizontally towards the right to the line y=x and find the value of g(x2), this process continues until both x and g(x) are the same value.

Showing the method on a spreadsheet:

n

x

g(x)

1

-4.0000000000

-3.6666666667

2

-3.6666666667

-3.5967078189

3

-3.5967078189

-3.5655250877

4

-3.5655250877

-3.5499338288

5

-3.5499338288

-3.5417564282

6

-3.5417564282

-3.5373669161

7

-3.5373669161

-3.5349823162

8

-3.5349823162

-3.5336786021

9

-3.5336786021

-3.5329633716

10

-3.5329633716

-3.5325702506

11

-3.5325702506

-3.5323539521

12

-3.5323539521

-3.5322348755

13

-3.5322348755

-3.5321693010

14

-3.5321693010

-3.5321331835

15

-3.5321331835

-3.5321132887

16

-3.5321132887

-3.5321023293

17

-3.5321023293

-3.5320962919

18

-3.5320962919

-3.5320929660

18

-3.5320929660

-3.5320911338

The formula I used in the spreadsheet are as follows:

n

x

g(x)

1

-4

=-(B2^3+6*B2^2+1)/9

2

=C2

=-(B3^3+6*B3^2+1)/9

3

=C3

=-(B4^3+6*B4^2+1)/9

4

=C4

=-(B5^3+6*B5^2+1)/9

5

=C5

=-(B6^3+6*B6^2+1)/9

6

=C6

=-(B7^3+6*B7^2+1)/9

7

=C7

=-(B8^3+6*B8^2+1)/9

8

=C8

=-(B9^3+6*B9^2+1)/9

9

=C9

=-(B10^3+6*B10^2+1)/9

10

=C10

=-(B11^3+6*B11^2+1)/9

11

=C11

=-(B12^3+6*B12^2+1)/9

12

=C12

=-(B13^3+6*B13^2+1)/9

13

=C13

=-(B14^3+6*B14^2+1)/9

14

=C14

=-(B15^3+6*B15^2+1)/9

15

=C15

=-(B16^3+6*B16^2+1)/9

16

=C16

=-(B17^3+6*B17^2+1)/9

17

=C17

=-(B18^3+6*B18^2+1)/9

18

=C18

=-(B19^3+6*B19^2+1)/9

18

=C19

=-(B20^3+6*B20^2+1)/9

...read more.

Conclusion

=B5^3-12*B5^2+44*B5-47

=3*B5^2-24*B5+44

5

=B5-C5/D5

=B6^3-12*B6^2+44*B6-47

=3*B6^2-24*B6+44

6

=B6-C6/D6

=B7^3-12*B7^2+44*B7-47

=3*B7^2-24*B7+44

From the table I get the root of f(x)=0 is x=1.88509246

  1. using the rearranging f(x)=0 in the form x=g(x) method;

for this method, I am going to rearrange f(x) = x3-12x2+44x-47=0 in the form x=(-x3+12x2+47)/44, i.e. g(x)= (-x3+12x2+47)/44

draw y=x and y=g(x)= (-x3+12x2+47)/44 on the same graph, I get the following:

image19.png

using the iteration xn+1=g(xn), doing on the spreadsheet with a starting point x=3 I got the following table:

n

x

g(x)

1

3

2.909090909

2

2.909090909

2.816696264

3

2.816696264

2.724052084

4

2.724052084

2.632540869

5

2.632540869

2.543614417

6

2.543614417

2.458694812

7

2.458694812

2.379066113

8

2.379066113

2.305774054

9

2.305774054

2.23955144

10

2.23955144

2.180782149

11

2.180782149

2.129507776

12

2.129507776

2.085471395

13

2.085471395

2.048185863

14

2.048185863

2.017011601

15

2.017011601

1.991230661

16

1.991230661

1.970108315

17

1.970108315

1.952938344

18

1.952938344

1.939072123

19

1.939072123

1.927933996

20

1.927933996

1.919026346

21

1.919026346

1.911927722

22

1.911927722

1.906286852

23

1.906286852

1.901814605

24

1.901814605

1.89827533

25

1.89827533

1.895478454

26

1.895478454

1.89327079

27

1.89327079

1.891529794

28

1.891529794

1.890157808

29

1.890157808

1.889077232

30

1.889077232

1.888226552

31

1.888226552

1.887557093

32

1.887557093

1.887030397

33

1.887030397

1.886616109

34

1.886616109

1.886290296

35

1.886290296

1.886034098

36

1.886034098

1.885832661

37

1.885832661

1.885674295

38

1.885674295

1.885549798

39

1.885549798

1.885451931

40

1.885451931

1.885375002

41

1.885375002

1.885314533

42

1.885314533

1.885267004

43

1.885267004

1.885229646

44

1.885229646

1.885200282

The formulae I used in the spreadsheet are as follows:

n

x

g(x)

1

3

=(-B2^3+12*B2^2+47)/44

2

=C2

=(-B3^3+12*B3^2+47)/44

3

=C3

=(-B4^3+12*B4^2+47)/44

4

=C4

=(-B5^3+12*B5^2+47)/44

5

=C5

=(-B6^3+12*B6^2+47)/44

6

=C6

=(-B7^3+12*B7^2+47)/44

7

=C7

=(-B8^3+12*B8^2+47)/44

8

=C8

=(-B9^3+12*B9^2+47)/44

9

=C9

=(-B10^3+12*B10^2+47)/44

10

=C10

=(-B11^3+12*B11^2+47)/44

11

=C11

=(-B12^3+12*B12^2+47)/44

12

=C12

=(-B13^3+12*B13^2+47)/44

13

=C13

=(-B14^3+12*B14^2+47)/44

14

=C14

=(-B15^3+12*B15^2+47)/44

15

=C15

=(-B16^3+12*B16^2+47)/44

16

=C16

=(-B17^3+12*B17^2+47)/44

17

=C17

=(-B18^3+12*B18^2+47)/44

18

=C18

=(-B19^3+12*B19^2+47)/44

19

=C19

=(-B20^3+12*B20^2+47)/44

20

=C20

=(-B21^3+12*B21^2+47)/44

21

=C21

=(-B22^3+12*B22^2+47)/44

22

=C22

=(-B23^3+12*B23^2+47)/44

23

=C23

=(-B24^3+12*B24^2+47)/44

24

=C24

=(-B25^3+12*B25^2+47)/44

25

=C25

=(-B26^3+12*B26^2+47)/44

26

=C26

=(-B27^3+12*B27^2+47)/44

27

=C27

=(-B28^3+12*B28^2+47)/44

28

=C28

=(-B29^3+12*B29^2+47)/44

29

=C29

=(-B30^3+12*B30^2+47)/44

30

=C30

=(-B31^3+12*B31^2+47)/44

31

=C31

=(-B32^3+12*B32^2+47)/44

32

=C32

=(-B33^3+12*B33^2+47)/44

33

=C33

=(-B34^3+12*B34^2+47)/44

34

=C34

=(-B35^3+12*B35^2+47)/44

35

=C35

=(-B36^3+12*B36^2+47)/44

36

=C36

=(-B37^3+12*B37^2+47)/44

37

=C37

=(-B38^3+12*B38^2+47)/44

38

=C38

=(-B39^3+12*B39^2+47)/44

39

=C39

=(-B40^3+12*B40^2+47)/44

40

=C40

=(-B41^3+12*B41^2+47)/44

41

=C41

=(-B42^3+12*B42^2+47)/44

42

=C42

=(-B43^3+12*B43^2+47)/44

43

=C43

=(-B44^3+12*B44^2+47)/44

44

=C44

=(-B45^3+12*B45^2+47)/44

According to the spreadsheet above, I got the root of f(x) =0 x=1.885229646

...read more.

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

See related essaysSee related essays

Related AS and A Level Core & Pure Mathematics essays

  1. Marked by a teacher

    The Gradient Function

    5 star(s)

    (xn-2)(h) + ... + hn-1 h 2! Since h limits to 0, all values containing an h term are therefore all worth 0, so therefore the gradient function for xn = nxn-1 However, in this section, this is perhaps only true for positive integers for the value of n.

  2. Methods of Advanced Mathematics (C3) Coursework.

    by substitueing in. I then used the g(x) of -1 as x and found g(x) of this.I repeated this until I had an accurate value of the route. This came out to be -1.51851. The value of g(X) was less than one enabling the route to be found but if it was grater

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

    = 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 formula is then formed On viewing the graph 2.1, the intervals in which the roots lie are [-3,-2], [-1, 0], [0, 1] respectively.

  2. I am going to solve equations by using three different numerical methods in this ...

    <1, X=-0.34500825, g'(x) =-0.271173069, and that is a success example. Rearranging equation failure: To show that failure I chose the root in the interval (+1 to +2), and apply the same rearrangement: g(x) = (2x�-3x�-2)/5.Because I think there are still some cases that this method fails.

  1. Change of Sign Method.

    x -2 -1 0 1 2 3 f(x) -11.37 0.63 2.63 0.63 0.63 8.63 From the graph it is evident that the equation x�-2x�-x+2.63=0 has more than one root, i.e. roots that lie in the intervals [-2,-1] and [1,2]. However, the above table illustrates that the method used only detects one such root that lies in the interval [-2,-1].

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

    0.77929020 -0.00000271 0.77928972 -0.00000098 0.00000173 0.77928925 0.00000075 0.77928972 -0.00000098 0.77928948 -0.00000012 0.00000087 0.77928925 0.00000075 0.77928948 -0.00000012 0.77928936 0.00000032 0.00000043 0.77928936 0.00000032 0.77928948 -0.00000012 0.77928942 0.00000010 0.00000022 0.77928942 0.00000010 0.77928948 -0.00000012 0.77928945 -0.00000001 0.00000011 0.77928942 0.00000010 0.77928945 -0.00000001 0.77928944 0.00000005 0.00000005 0.77928944 0.00000005 0.77928945 -0.00000001 0.77928945 0.00000002 0.00000003 0.77928945 0.00000002 0.77928945 -0.00000001 0.77928945 0.00000001 0.00000001 Error bound: �0.000000005 (9dp)

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

    The root now is -0.3475 and the maximum error of this root would be 0.0005. The "Change Of Sign" is very effective, however, sometimes the Decimal Search method would not work with some function. An example is 5x^4+x�-2x�-0.1x+0.1=0 . This would not work because the roots are so near.

  2. The Gradient Fraction

    Then similar like the Triangle method, you need to draw the 'x' and 'y' differences. The purpose of this method is to find the angle in the right angled triangle. It is a trigonometry method you will need to use.

  • Over 160,000 pieces
    of student written work
  • Annotated by
    experienced teachers
  • Ideas and feedback to
    improve your own work