Investigate the three different numerical methods used to solve equations.

Interval Bisection

Interval bisection is another change of sign method, it is very similar to decimal search except it is much quicker because each interval is divided in half to find a change of sign.

2x3-5x+2 can be solved using interval bisection.

X

Y

0

2

-1

0.5

-0.25

0.25

0.78125

0.375

0.23046875

0.4375

-0.020019531

0.40625

0.102844238

0.42188

0.040794373

0.42969

0.010230064

0.43359

-0.00493443

0.43164

0.002637938

0.43262

-0.001150722

0.43213

0.00074299

0.43237

-0.000204021

0.43225

0.000269446

0.43231

3.27031E-05

0.43234

-8.56612E-05

Root =

0.432327

2x4-4x2+2 cannot be solved using interval bisection.

X

Y

X

Y

0

2

-1

0

0

-2

8

2

8

-3

28

3

28

-4

450

4

450

-5

152

5

152

There is no change of sign, therefore the roots cannot be found using the interval bisection method. This is because the curve only touches the axis and does not cross it.

Newton Raphson

The Newton Raphson method is based on tangents to a curve:

The graph above shows that if we start at the point x0 which is a point close to where the root lies and draw a line going straight up, it will hit the curve. From this point on the curve a tangent is drawn and meets with the x-axis, this point is called x1. This point is then used as the next starting point and the process is continued until an estimate is found of where the root lies.

The tangents (gradients) can be worked out by:

F1(x0)

The gap between x0 and x1 is named 'a' then the gradient can be given by:

F(x0) a= f (x0)

a f 1(x0)

The position x1 lies at:

x1 = x0-a

So the Newton Raphson formula is:

x1= x0-f(x0)

f1(x0)

2x3+x2-3x-1 can be solved using the Newton Raphson method.

Producing a graph will give a rough estimate of where the routes lie.

The intervals the roots lie in are: (1, 2), (0,-1), (-1,-2)

To find the roots I will use the Newton Raphson equation.

x-f(x)

f1(x)

I can now input my equation into the formula:

x-2x3+x2-3x-1

6x2+2x-3

= x(6x2+2x-3)-(2x3+x2-3x-1)

6x2+2x-3

x n+1 = 4xn3+xn2+1

6xn2+2xn-3

I have input the formula from above into the spreadsheet to find the 3 roots, this is shown below.

n

Xn

Xn+1

0

-1.00000

-2.00000

-2.00000

-1.58824

2

-1.58824

-1.39563

3

-1.39563

-1.34439

4

-1.34439

-1.34068

5

-1.34068

-1.34067

6

-1.34067

-1.34067

7

Root=-1.340675

Error= +/-0.000005

n

Xn

Xn+1

0

-0.500000

-0.300000

-0.300000

-0.320915

2

-0.320915

-0.321037

3

-0.321037

-0.321037

4

-0.321037

-0.321037

Root= -0.321037

n

Xn

Xn+1

0

.000000

.200000

.200000

.163184

2

.163184

.161704

3

.161704

.161702

4

.161702

.161702

Root=1.161703

Error = +/- 0.0000005

The Newton Raphson method fails when the gradient is too steep. This is the case with the following equation:

0- 1

(x+3)2-0.1

The formula I will enter in the spreadsheet is displayed below:

Xn+1 = -10xn4-120xn3-541xn2-1092xn-837.2

2x+6

The graph shows that the tangents do not appear to converge towards the root.

n

Xn

Xn+1

-2

-8.6

2

-8.6

877.8978571

3

877.8978571

-3417800597

4

-3417800597

.99623E+29

5

.99623E+29

-3.97741E+88

6

-3.97741E+88

#NUM!

7

#NUM!

#NUM!

After entering my formula into the spreadsheet, the table confirms what the graph displayed. The curve of the equation is too steep on both sides of the root. When a tangent is drawn at -2 it crosses the x-axis way past the root at -8.6 and so it is diverging away from the root. This confirms that the Newton Raphson method will not find the roots in this case.

Rearranging Equations

If you use any f(x) equation and rearrange it into the form x = g(x) the point on the graph f(x) where y = 0 (The root) is the same x-value as the point where y = g(x) crosses the line y = x.

To find the roots, I need to find the point where the line y = g(x) crosses the line y = x. I will put in an estimate value of x (X0) and it will lead to a better estimate (X1).

I have chosen the equation f(x) = x3-3x+1

This can then be rearranged into the form:

3x = x3+1

x = (x3+1)

3

This leads to the iteration: xn+1 = xn3+1

3

The equation can be rearranged many different ways, I have chosen to do it this way. Not all of the rearrangements will lead to successful convergence. This is because if the gradient of the point were y=x crosses y=g(x) is greater than 1 or less than -1 the root cannot be found.

I have inputted the iteration formula into the spreadsheet like with the Newton Raphson method in an attempt to find the roots of the equation.

n

Xn

Xn+1

n

Xn

Xn+1

0

0.5

0.375

0

.75

2.11979167

0.375

0.350911

2.119792

3.50843976

2

0.350911

0.347737

2

3.50844

4.7286365

3

0.347737

0.34735

3

4.72864

065.37447

4

0.34735

0.347303

4

065.374

403074755

5

0.347303

0.347297

5

4.03E+08

2.1829E+25

6

0.347297

0.347296

6

2.18E+25

3.4673E+75

7

0.347296

0.347296

7

3.47E+75

.389E+226

Root = 0.3472965

8

.4E+226

#NUM!

Error= +/- 0.0000005

Root cannot be found

n

Xn

Xn+1

0

-2

-2.3333333

-2.33333

-3.9012346

2

-3.90123

-19.45845

3

-19.4585

-2455.5261

4

-2455.53

-4.935E+09

5

-4.9E+09

-4.007E+28

6

-4E+28

-2.145E+85

7

-2.1E+85

-3.29E+255

Root cannot be found

Y=x3-3x+1

I was able to find only one of the roots using this rearrangement. When I attempted to find the other two roots it rapidly diverged away from the root. (shown in the table)

On the next page I have shown why only 1 root could be found.

Y=(x3+1)/3 and y=x

Only one of the roots could be found, the other two roots could not be found using this rearrangement because at these points of intersection the y=g(x) gradient is steeper than y=x. When I attempted to home in on the roots in the table, it rapidly diverged away from the root. Below shows why one of the roots can be found.

When x = 0.347296

X3+1

3

dy/dx = 3x2

3

= x2

= 0.3472965^2

g1(x) = 0.120614511

The gradient is <1 so it converges and the root is able to be found.

To show why it is not possible to find the other two roots using this arrangement I will estimate values of x by looking at where the roots should be on the graph on the previous page.

When x = -1.9

X3+1

3

dy/dx = 3x2

3

= x2

= -1.92

g1(x) = 3.61

The gradient is >1 which is the gradient of the line y=x therefore it diverges and the root cannot be found.

When x = 1.5

X3+1

3

dy/dx = 3x2

3

= x2

= 1.52

g1(x) = 2.25

The gradient is >1 therefore it diverges and the root cannot be found.

From the graph, and the table on the previous pages we can establish that the equation forms a staircase sequence because the x=g(x) gradient is positive. Below the staircase sequence is displayed showing the points used in the table. Some equations will not display a staircase sequence, instead they will show a cobweb sequence. This all depends upon the equation which is used.

Y=(x3+1)/3 and y=x

Comparing the methods

I will now use one of the equations I have already used, and work out one of the roots using all three of the methods. I will then compare the three methods discussing advantages and disadvantages of each one.

I am going to use the equation: y= x3-3x+1

Before I find the roots, I must first calculate the interative formula's for the Newton Raphson method and the Rearranging method.

Newton Raphson

x-f(x)

f1(x)

= x- x3-3x+1

3x2-3

= x(3x2-3)-(x3-3x+1)

3x2-3

Xn+1 = 2xn2-1

3xn2-3

Rearranging

F(x) = x3-3x+1

3x = x3+1

x = x3+1

3

xn+1 = x3n+1

3

Decimal Search

Newton Raphson

Rearrangement

X

Y

n

Xn

Xn+1

n

Xn

Xn+1

0

0

0.7000000

0.2052288

0

0.50000

0.375000

0.1

0.701

0.2052288

0.3419742

0.375000

0.350911

0.2

0.408

2

0.3419742

0.3472853

2

0.350911

0.347737

0.3

0.127

3

0.3472853

0.3472964

3

0.347737

0.347350

0.4

-0.136

4

0.3472964

0.3472964

4

0.347350

0.347303

0.31

0.099791

0.3472964

0.3472964

5

0.347303

0.347297

0.32

0.072768

Root=0.3472964

6

0.347297

0.347296

0.34

0.019304

Error= +/- 0.0000000

7

0.347296

0.347296

0.35

-0.007125

Root = 0.3472965

0.341

0.016651821

Error = +/- 0.0000005

0.342

0.014001688

0.343

0.011353607

0.345

0.006063625

0.346

0.003421736

0.347

0.000781923

0.348

-0.001855808

0.3471

0.000518056

0.3472

0.00025421

0.3473

-9.61518E-06

0.34721

0.000227827

0.34722

0.000201443

0.34723

0.00017506

0.34724

0.000148677

0.34725

0.000122295

0.34726

9.59124E-05

0.34727

6.95302E-05

0.34728

4.31482E-05

0.34729

.67664E-05

0.34730

-9.61518E-06

0.347291

.41282E-05

0.347292

.14901E-05

0.347293

8.8519E-06

0.347294

6.21374E-06

0.347295

3.57558E-06

0.347296

9.37426E-07

0.347297

-1.70073E-06

Root= 0.3472965

Error= +/-0.0000005

Conclusion

All three of the methods used in the investigation have both advantages and disadvantages when being used.

From the table it can be concluded that the Newton Raphson method is the quickest of the three as it shows convergence very quickly each time. The decimal search is the slowest by far of the three methods. It can take around 25 steps to home in on the root. At first the Rearrangement and Newton Raphson methods appear to be the most difficult to use, since the formulas must be calculated before hand. Once the formula has been calculated and inputted for the first estimate, after this it is very simple. When using a spreadsheet it can then just be dragged down until it produces convergence. Even including the calculations needed for the Newton Raphson and rearrangement method, they still prove to be far quicker than either of the change of sign methods.

The main advantage of the change of sign method over the other 2 methods is that it is easy to find all of the roots to almost any equation.

Overall I would say that the Newton Raphson method is the most efficient of the three. Although there is some preparation before using the method, it still ends up being the quickest.

Pure Mathematics 2 Coursework Michael Hatt