• 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)

    80 3 81 405 4 256 1280 Points Gradient 1,1 5 2,32 80 3,243 405 4,(1024) 1280 The general pattern here between the two values of x and the gradient, the value of the gradient function here is 5x4, as seen when comparing the two smaller tables above.

  2. Marked by a teacher

    Estimate a consumption function for the UK economy explaining the economic theory and statistical ...

    3 star(s)

    The second part consists of some economy theories and separate analyzing is given to support or against the hypothesis. For instance, the higher value of R^2 indicates the better prediction by the consumption. The final part summary the whole project.

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

    This tell us the magnitude of the gradient of g(x) at the point of x = 0.093078 is less than 1, (<1) that means that the slope of it is less than that of the line y = x. Failure of the method x=(x�+8)/13 n x 1 4 2 5.53846154

  2. Methods of Advanced Mathematics (C3) Coursework.

    I can now find the routes by using the rearrangement of the formula to give the iterative formula, so xn+1=(4x-2)^0.2 -1 -1.43097 -1.43097 -1.50511 -1.50511 -1.51649 -1.51649 -1.51821 -1.51821 -1.51847 -1.51847 -1.51851 -1.51851 -1.51851 -1.51851 -1.51851 I first took an estimate of -1 and then found g(x) by substitueing in.

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

    -9.36675E-07 1.269758 1.26976 -9.36675E-07 3.80883E-06 1.269759 1.43609E-06 This is a bisection failure. As the graph shows, we can't solve the other roots. We can only find one root, so the failure exists. Newton-Raphson Method: First of all, I am trying to estimate the root, and I start to work with tangents to find a more accurate estimation.

  2. Investigate the relationships between the lengths of the 3 sides of the right angled ...

    this to eliminate C from these equations 9a + 3b + c = 25 -eqn3 - 4a + 2b + c = 13 -eqn2 5a + b = 12 -eqn4 Equation 2 - Equation 1 I am doing this to eliminate C and form a fifth equation that I will subtract with equation 4.

  1. Analyse the use of three methods which are called the: change of sign, Newton-Raphson ...

    in the form "x = g(x)"). An initial value for x is entered producing a value for g(x). This value of g(x) is then used as the new value of x2. This process is repeated and after appropriate iteration a very accurate value of a root can be found.

  2. 2D and 3D Sequences Project

    If a = 2 then c = 1 and a + b = 0 If 2 is equal to b- then b = -2 I will now work out the equation using the information I have obtained through using the difference method: 1)

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