• 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

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

Extracts from this document...

Introduction

                                      A2 Mathematics---Core 3 Coursework                  Felix Cheng

Numerical solution of equations

Introduction

What is numerical method?

We may occasionally encounter some equations which cannot be solved by algebraic or analytical method. In order to obtain the answers, numerical methods can be used for solving those equations. In this coursework, I am going to use three numerical methods to solve the cubic and non-trivial equations. The methods are shown as follows:

  • Interval bisection---change of sign methods
  • The Newton-Raphson method---fixed point iteration
  • Rearranging the equation f(x)=0 into the form x=g(x)---fixed point iteration

Each method shown above will be applied to one different cubic and non-trivial equation. In addition to the application, I will compare the other two methods by applying one of the three equations, thereby comparing their ease of use and speed of convergence.

*in this coursework, programme including Microsoft Excel (used for calculations) and Autograph 2.10 (used for drawing graphs) will be used so as to enhance the process of the coursework.

Interval bisection---change of sign methods

Given that the equation y=f(x) is a continuous function in which no asymptotes or other breaks occur, we look for the roots of the equation f(x) = 0. In the usual case, all we need to do is just to factorize the formula and then solve the equation easily. In this case, a formula y = (2x-3)(x+1)(x-2)- which is non-trivial equation, is chosen for showing how the roots of the equation will be obtained.

 But in my equation the product of the factor is not equal to 0. It implies that neither using algebraic nor analytical method is possible. Thus, an alternative way to find out the solution has to be sought.

The solution I would like to introduce first is the change of sign method.

When we are solving the equation f(x)

...read more.

Middle

Max. possible error

1

-1

-0.3158

0

0.0142

-0.5

-0.0008

0.5

2

-0.5

-0.0008

0

0.0142

-0.25

-0.002675

0.25

3

-0.5

-0.0008

-0.25

-0.002675

-0.38

0.00177813

0.125

4

-0.375

0.001778125

-0.25

-0.002675

-0.31

-0.000302

0.0625

5

-0.375

0.001778125

-0.3125

-0.000301953

-0.34

0.00086626

0.03125

6

-0.34375

0.00086626

-0.3125

-0.000301953

-0.33

0.00030275

0.015625

7

-0.328125

0.000302753

-0.3125

-0.000301953

-0.32

4.1191E-06

0.0078125

8

-0.320313

4.11911E-06

-0.3125

-0.000301953

-0.32

-0.0001482

0.00390625

9

-0.320313

4.11911E-06

-0.31641

-0.000148166

-0.32

-7.181E-05

0.001953125

10

-0.320313

4.11911E-06

-0.31836

-7.18133E-05

-0.32

-3.379E-05

0.000976563

11

-0.320313

4.11911E-06

-0.31934

-3.37918E-05

-0.32

-1.482E-05

0.000488281

12

-0.320313

4.11911E-06

-0.31982

-1.48222E-05

-0.32

-5.348E-06

0.000244141

13

-0.320313

4.11911E-06

-0.32007

-5.34794E-06

-0.32

-6.135E-07

0.00012207

14

-0.320313

4.11911E-06

-0.32019

-6.13511E-07

-0.32

1.753E-06

6.10352E-05

15

-0.320251

1.75303E-06

-0.32019

-6.13511E-07

-0.32

5.6981E-07

3.05176E-05

16

-0.320221

5.69814E-07

-0.32019

-6.13511E-07

-0.32

-2.183E-08

1.52588E-05

17

-0.320221

5.69814E-07

-0.32021

-2.18343E-08

-0.32

2.7399E-07

7.62939E-06

18

-0.320213

2.73993E-07

-0.32021

-2.18343E-08

-0.32

1.2608E-07

3.8147E-06

19

-0.32021

1.2608E-07

-0.32021

-2.18343E-08

-0.32

5.2123E-08

1.90735E-06

20

-0.32021

5.21233E-08

-0.32021

-2.18343E-08

-0.32

1.5145E-08

9.53674E-07

Spreadsheet 1.8

image34.png

Graph2.9--- bisection of y = (x+0.3) (x+0.5) (x+0.1)-0.0008

Consequently, we have got a root of -0.32021 (to five decimal places) between the interval [-1, 0]. The answer obtained in fact is one of the right roots. However, from the graph above, the graph intersects the x-axis three times, thereby giving 3 different roots. They all lie in the same interval [-1, 0]. Bisectional method has failed to find all the roots when several roots are too close with each other.

Fixed point iteration ---the Newton-Raphson method

An estimate of the root as a starting point has to be set. First of all, for one root of f(x) = 0. We then can draw a tangent to the curve y=f(x) at the point (x1, f(x1)). The point which the tangent cuts the x axis gives the next approximation for the root. Then the process is repeated, as shown in graph 2

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) = fimage35.png(x1) [x-x1]

This tangent cuts the x-axis at (x2, 0), so

             0- f(x1) = fimage35.png(x1) [x2-x1]

Rearranging this gives

image36.png

The Newton-Raphson iterative formulais then formed

image05.png

image06.pngimage07.png

            On viewing the graph 2.1, the intervals in which the roots lie are [-3,-2], [-1, 0], [0, 1] respectively.image08.png

Graph 2.1---image09.png

In this case, I choose [0, 1] as the root presented graphically as follows.

First of all, I am going to show the way to find the root in the interval [0, 1]

image10.png

Graph 2.2---Newton-Raphson forimage09.png

By using the help of autograph, in interval [0, 1], I get a root of 3 decimal places0.908.

r

Xr

f(Xr)

f'(Xr)

f(Xr)/f'(Xr)

1

2

29

47

0.617021277

2

1.382978723

7.671007388

23.2775011

0.329546

3

1.053432723

1.678766068

13.4149463

0.125141468

4

0.928291256

0.205236732

10.1818519

0.020157112

5

0.908134144

0.004995226

9.68744176

0.000515639

6

0.907618504

3.23625E-06

9.67489018

3.345E-07

7

0.90761817

1.36247E-12

9.67488204

1.40825E-13

Spreadsheet 2.3

From spreadsheet 2.3 above, rounding up the solution to 5 decimal places, I get the solution of 0.90762. The error bounds for this is ±0.000005. Hence, the solution is between 0.907615< x < 0.907625

f(0.907625) = image11.png

f(0.907615) = image12.png

After having checked for the existence of sign change, the method is proved to be successful.

By applying the same method, and choosing 2 other iteration as -2 and 0. I get the following 2 other roots.

r

Xr

f(Xr)

f'(Xr)

f(Xr)/f'(Xr)

1

-3

-31

52

-0.59615385

2

-2.40384615

-7.53856822

27.7755178

-0.27141054

3

-2.13243562

-1.23905137

18.86605

-0.06567625

4

-2.06675937

-0.06467851

16.9093736

-0.00382501

5

-2.06293436

-0.00021345

16.7978087

-1.2707E-05

6

-2.06292165

-2.3521E-09

16.7974385

-1.4003E-10

7

-2.06292165

1.77636E-15

16.7974385

1.05752E-16

Spreadsheet 2.4

r

Xr

f(Xr)

f'(Xr)

f(Xr)/f'(Xr)

1

-1

5

-4

-1.25

2

0.25

-1.953125

-2.4375

0.801282051

3

-0.55128205

2.46943433

-6.67504931

-0.36994998

4

-0.18133208

0.02029835

-6.15472471

-0.00329801

5

-0.17803406

2.58642E-05

-6.13900736

-4.2131E-06

6

-0.17802985

4.25595E-11

-6.13898716

-6.9327E-12

7

-0.17802985

0

-6.13898716

0

...read more.

Conclusion

Secondly, Newton-Raphson method is relatively trickier, includinginserting four formulae into Excel to define Xn, f(Xn), f'(Xn)andf(Xn)/f'(Xn). At the same time, the equation of fimage31.png(Xn) is needed to be calculated by differentiation algebraically. Further, the calculator is not the only thing needed. It can only work with the aid of autograph programme. The reason is that this can give us a clue of what approximation value of the roots should be taken, thereby avoiding taking any approximation value which is near the turning point and converse to a false root.

Thirdly, when applying rearranging equations, the equation f(x) has to be converted into the form of g(x) algebraically. After that, I use Autograph to draw the curve y = x and g(x) to find where the intersection points lie. I can then use Excel spreadsheet to insert one approximation value of the starting point and the accuracy of the method can be found. In the whole process, one formula is going to be put in. However, the gradient of the graph at the root have to be less than on, otherwise it will fail to find the root.  All in all, the less complex the f (x) is, the more convenient we can use this method by rearranging the f(x) = 0 into the form x = g(x).

To conclude, it is most convenient, just typing one formula, to use Excel spreadsheet when using the method of rearranging equations. But, the bisection method is considered to be the easiest one when considering the whole process. It is because all we need to do is just use Excel and even a calculator only, whilst algebraic works is involved in the other two methods which may take longer time and increase the possibility to make mistake. Though I need to type more formulae than the others in Excel, it is still the easiest to deal with.

Page  of

...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

    C3 Coursework - different methods of solving equations.

    5 star(s)

    Here is the proof: Newton Raphson method This method works by plotting the f(x) on a graph and visually looking at between what two points the root is (in single units such as 1 or 5 or 9). Then we draw a tangent at that point on the graph. E.g.

  2. OCR MEI C3 Coursework - Numerical Methods

    Unlike the other two methods, the change of sign method takes a similar length of time for any equation. This means that it may be faster or slower than using the rearrangement x=g(x). Ease of use The decimal search is the easiest method to automate, either using a spreadsheet or when programming.

  1. Numerical solutions of equations

    0.680 -0.005007 0.681 0.001510 The change of sign is between x = 0.680 and x = 0.681 x f(x) 0.6801 -4.355665x10-3 0.6802 -3.704544x10-3 0.6803 -3.053279x10-3 0.6804 -2.401872x10-3 0.6805 -1.750322x10-3 0.6806 -1.098629x10-3 0.6807 -4.467927x10-4 0.6808 2.051866x10-4 The change of sign is between x = 0.6807 and x = 0.6808 x f(x)

  2. This coursework is about finding the roots of equations by numerical methods.

    Newton Raphson converges to a value near to -0.6180 The Newton Raphson does NOT automatically trap the root between two values In our example it looks like the root is just below 1.618034. We proposed it was 1.6180 to 5sf We need to use the change of sign method to trap the root between two solution bounds We evaluate f(1.61805)

  1. Mathematical equations can be solved in many ways; however some equations cannot be solved ...

    � It allows us to find the intervals of the values very easily. � It has the greatest possibility of failing.

  2. Numerical Solutions of Equations

    It does reply on being able to differentiate the f(x) though. The Decimal Search method is quite a slow method, because it takes a lot of time to prepare the spreadsheet on Excel: especially the various formulas for the different calculations.

  1. Methods of Advanced Mathematics (C3) Coursework.

    I am going to look at the route between -2 and -1 particularly. To do this I need to rearrange my formula into the form x=g(x) F(x)=x^5-4x+2 ==> x^5-4x+2=0 ==>x^5=4x-2 ==>x=(4x-2)^0.2 if I plot the graphs of y=x and of y=(4x-2)^0.2 then these graphs will intersect at the points of the routes.

  2. Fixed point iteration: Rearrangement method explained

    will be the g (x0) value. Then in the g (x) column for x1 it will be g(x1) To tabulate my calculations I will use excel.

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