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

    This repeats until we find the root of the equation, (when x value starts repeating or reached enough significant levels). I will attempt to solve f(x) = y = x�-6x�+2x+2 Here's y = f(x) plotted: From the graph, we can tell that roots are between (-1 and 0), (0 and 1)

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

  2. Am going to use numerical methods to solve equations that can't be solved algebraically

    = x5-6x+2 f ' (x)= 5x4-6 x1= x0- x5-6x+2 5x4-6 x1= 2 - (2)5-6(2)+2 5(2)4-6 = 1.702702703 x2= 1.702702703 -(1.702702703)5- 6(1.702702703)+2 5(1.702702703)4-6 =1.533506547 x3= 1.533506547 - (1.533506547)5-6(1.533506547)+2 5(1.533506547)4-6 =1.474406026 x4= 1.474406026 - (1.474406026 )5-6(1.474406026 )+2 5(1.474406026)4-6 = 1.467530824 x5= 1.467530824- (1.467530824)5-6(1.467530824)+2 5(1.467530824)4-6 =1.467443081 After a while the values started to converge rapidly.

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

    Speed of Convergence To calculate the root to 3 decimal places using decimal search it requires 4 tables of values to calculate the root whereas with x=g(x) iteration and also Newton Raphson only 1 table of values is required. We can thereby conclude that the Decimal search method is the slowest.

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

    What can cause failure? One reason that the decimal search can fail is that there are several roots very close together in the same integer range. For example, the equation y=54x�-225x�+309x-140 x y x y x y x y 1 -2 1.61 -0.37533 1.661 -0.04956 1.6661 -0.00509 1.1 -0.476 1.62

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

  2. C3 COURSEWORK - comparing methods of solving functions

    This is because of the steep gradient where the graph crosses the x-axis, meaning that the resulting tangent is directed further away from the root.

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