Introduction

I will be investigating the solutions of equations using the following three methods:

1. Change of sign method

2. Newton-Raphson method

3. Fixed point iteration after rearranging the equation from form f(x) =0 into the form x = g(x)

I will solve the equations with these methods as I cannot solve them by any algebra I have met so far. The equations I am going to use are the following:

* y = 243×3-378×2+192x-32 = 0

* y = ex-x3-1.4 = 0

* y = 43×3-60×2-250x-115 = 0

* y = x3-5x+2.6 = 0

In my investigation I will give illustrated examples of the methods failing for the root I am looking for. All failures will be explained.

In my investigation I will use a Casio calculator to help draw graphs and to help identify where the rots are. I will also have computer software such as Autograph to help draw graphs and to show certain methods graphically.

Change of Sign Method

I will be using the “decimal search” method to check for a change of sign in the equation:

y = 243×3-378×2+192x-32

The graph of this function is given below.

I then decided to confirm the shape of the graph by finding how many turning points there is.

Dy = 729×2-756x+192 = 0

Dx

Quadratic Equation: D= b2-4ac

=-7562-(4*729*192)

=11664 > 0

=> 2 Real Turning Points (Graph Shape Confirmed)

By putting in Values of X into the equation I found some values of Y.

Table 1

x

F(x)

-4

22400

-3

-10571

-2

-3872

-1

-845

0

-32

1

25

2

784

3

3703

4

10240

So I know there is a root between [0,1] but from my earlier graph I know there is two roots between this number. I will need to investigate further and check for roots between 0 and 1. The table of values is given below.

Table 2

x

F(x)

0

-32

0.1

-16.33

0.2

-6.776

0.3

-1.859

0.4

-0.128

0.5

-0.125

0.6

-0.392

0.7

0.529

0.8

4.096

0.9

11.767

1

25

So I know there is a root between [0.6,0.7]. This only accounts for root B. What about Root A? Here is an example of the method failing. I will go into this in more detail further on. Root B, However still needs to be found more accurately. I will know find the values for the function between 0.6 and 0.7.

Table 3

x

F(x)

0.6

-0.392

0.61

-0.377

0.62

-0.349

0.63

-0.306

0.64

-0.247

0.65

-0.171

0.66

-0.075

0.67

0.0412

0.68

0.1797

0.69

0.3418

0.7

0.529

Table 4

x

F(x)

0.665

-0.019

0.666

-0.008

0.667

0.004

0.668

0.016

Table 5

x

F(x)

0.6665

-0.001997

0.6666

-0.0007995

0.6667

0.0004

0.6668

0.0016

Table 6

x

F(x)

0.66665

-0.0002

0.66666

-0.00008

0.66667

0.00004

0.66668

0.00016

I know that root B of the equation y = 243×3-378×2+192x-32 lies somewhere between: x = 0.66666 and x = 0.66667. So taking the answer as the midpoint of the two I get: x = 0.666665 (6 d.p.). But seeing as I only need the answer to 5 decimal places I get x = 0.66667 (5 d.p.).

Answer: 0.66667 (5 d.p.)

Error: 0.66667 + 0.000005

Error Bounds: [0.666665,0.666675]

For these error bounds to be valid there must be a change of sign when the values are input into the equation:

f(x) = 243×3-378×2+192x-32

f(0.666665) = -0.00002

f(0.666675) = 0.00001

There is a change of sign in the two answers so I can say the error bounds are valid.

ROOT B ANSWER = 0.66667 (5 d.p.)

ROOT A

As mentioned earlier the method failed for Root A as there was no change of sign between f(0.4) and f(0.5). I know there is a root because of the graph and f(x) = 0 for x = (4/9) or 0.44444 (5.d.p).

The table is shown again below.

x

F(x)

0

-32

0.1

-16.33

0.2

-6.776

0.3

-1.859

0.4

-0.128

0.5

-0.125

0.6

-0.392

0.7

0.529

0.8

4.096

0.9

11.767

1

25

I will investigate this further: A table is produced of values between 0.4 and 0.5.

x

F(x)

0.4

-0.128

0.41

-0.073

0.42

-0.035

0.43

-0.011

0.44

-0.00109

0.45

-0.0016

0.46

-0.012

0.47

-0.031

0.48

-0.057

0.49

-0.089

0.5

-0.125

Although there is no change of sign there is an evident way of getting nearer to the root. As the table shows the numbers are getting nearer to 0 up to x = 0.44, but x = 0.45 is now starting to move away from 0.

One more table of values between 0.44 and 0.45 should prove this further.

x

F(x)

0.44

-0.0011

0.441

-0.00065

0.442

-0.00033

0.443

-0.00011

0.444

-0.000011

0.445

-0.000017

0.446

-0.00013

0.447

-0.00035

0.448

-0.00067

0.449

-0011

0.45

-0.0016

This also was the case with f(x) getting nearer to 0 up until x = 0.444 and then moves away from 0 for x = 0.445.

So even though I have done three sets of iterations, there is no change of sign.

Newton-Raphson Method

Now I will be using the Newton-Raphson method to find the roots of the equation:

y=ex-x3-1.4

The Graph is shown below and shows there are three roots for the equation.

The table of values is shown below.

x

F(x)

-3

25.650

-2

6.7353

-1

-0.032

0

-0.4

1

0.3183

2

-2.01

3

-8.31

The Newton-Raphson formula is: X1=X0 – f(X0)

f'(X0)

Here, X0 is the current known x-value, f(X0) represents the value of the function at X0, and f'(X0) is the derivative (slope) at X0. X1 represents the next x-value that I am trying to find.

I will now find the function equations for f(X0) and f'(X0).

F(X0) = ex-x3-1.4

F'(X0) = ex -3×2

So my formula is: X1=X0 – ex0-x03-1.4

ex0 -3×02

To find root A.

X0 = -2

X1 = -2-(e-2-(-2)3-1.4) = -1.43232

(e-2 -3-22)

X2 = -1.13190

X3 = -1.02608

X4 = -1.01226

X5 (root) = -1.01203 Answer (5.d.p.)

Answer Root A: -1.01203 (5 .d.p)

Error: -1.01203 + 0.000005

Error bounds: [-1.012025, -1.012035]

F(x) = ex-x3-1.4

F(-1.012025) = -0.0000073

F(-1.012035) = 0.0000198

A change of sign occurs and so confirms there is a root.

Finding Root B

X0 = 0.8

X1 = -0.22618

X2 = 0.69116

X3 = 0.21887

X6 = 0.37282 ( 5.d.p.)

Answer Root B: 0.37282 (5.d.p.)

Finding Root C

X0 = 1

X1 = 2.12979

X2 = 1.62013

X3 = 1.40784

X6 = 1.34816

Answer Root C: 1.34846(5.dp.)

Newton-Raphson Failure

For the Newton-Raphson method to fail the X0 starting position must be between a turning point and the root. This will therefore not find the required root.

For example with the equation:

F(x) = 43×3-60×2-250x-115

The graph for this function is shown below.

The table of values is given below:

x

F(x)

-3

-1066

-2

-199

-1

32

0

-115

1

-382

2

-511

3

-244

4

677

5

2510

Using the Newton-Raphson formula of: X1=X0 – f(X0)

f'(X0)

F(x) = 43×3-60×2-250x-115

F'(x) = 129×2-120x-250

So my formula is: X1=X0 – 43×03-60×02-250×0-115

129×02-120×0-250

Finding Root A

X0 = -1

X1 = -1 – 43(-1)3-60(-1)2-250(-1)-115 = 31

129(-1)2-120(-1)-250

X2 = 20.87085

X3 = 14.14418

X11(root)= 3.36156 This is actually ROOT C.

The graph 1 shows the iteration process. It shows the first iteration more clearly than my graph 2: Only the first 7 or 8 iterations are shown clearly here

The graph 2 below is showing the same iteration process but the y-axis goes up to a million.

Graph 3 shows the iteration process from X7 between the x values of 3.3 and 4

This is an example of the Newton-Raphson failing. I started near to root A but the method went and found the root of C. It failed as I started too near to the turning point. Therefore, f'(x) was very close to value 0. it is illustrated on the next page.

Using autograph I found the turning point to be -1.003 ( 3 d.p.)

The graph below shows that the X0 starting point starting point is very near to the turning point.

Answer Root C: 3.36156 (5 d.p.)

Error: 3.36156 + 0.000005

Error Bounds: [3.361555, 3.361565]

For these error bounds to be valid there must be a change of sign when the values are input into the equation:

f(x) = 43×3-60×2-250x-115

f(3.361555) = -0.00478

f(3.361565) = 0.00327

There is a change of sign in the two answers so I can say the error bounds are valid.

ROOT C ANSWER = 3.36156 (5 d.p.)

This concludes that there is a root but the answer is root C not root A which I was initially trying to find.

Rearrangement

This method uses an estimate for the value of x using an iterative process. By rearranging f(x) = 0 into the form x = g(x) provides an iterative formula which will converge to a required root by picking an appropriate starting value. On a graph the roots will be equal to the values of x where the curve y = f(x) intersects the line y = x. The equation I will use is:

y= x3-5x+2.6

The graph is shown below with 3 roots to the equation.

dy = 3×2-5 =0

dx

= 3×2 = 5 =; 2 turning points

The table of values is given below:

x

F(x)

-3

-9.4

-2

4.6

-1

6.6

0

2.6

1

-1.4

2

0.6

3

14.6

Rearrangement into x= g(x)

x3-5x+2.6

x= 3V(5x-2.6) x = (x3+2.6)

5

Putting these equations onto the graph along with the graph y=x I get the following graphs.

Pink line – y=x

Blue Line – g1 equation

Green Line – g2 equation

Finding Root A

Using g1

x0 = -1

x1 = -1.9661

x2 = -2.3164

x3 = -2.42057

X11(root) = -2.46099

Finding Root B

Using g2

x0 = -1

x1 = 0.32

x2 = 0.52655

x3 = 0.54920

x8(root) = 0.55401

Finding Root C

Using g1

x0 = 1

x1 = 1.33887

x2 = 1.59978

x3 = 1.75429

x17 (root) = 1.90698

All three roots have been found to five decimal places. They are:

Root A = -2.46099 Root B = 0.55401 Root C = 1.90698

All three roots have been found, but why does it depend on which rearrangement is used? It depends on the gradient of each rearrangement. For the iteration to work the gradient of the rearrangement must be between -1 and 1.

For example:

g1(x) = 3V(5x-2.6) g2(x) = (x3+2.6)

5

= (5x-2.6)? dg2 = 3×2

dx 5

dg1= ?(5x-2.6)-? ï¿½5

dx

= 5/3

3V(5x-2.6)2

Root A ï¿½ -2.5

dg1 = 5/3 = 0.27 -1;x;1

dx 3V(5ï¿½(-2.5)-2.6)2

Iteration of g1 converges to find root A.

Root B ï¿½ 0.5

dg2 = (0.53+2.6) = 0.545 -1;x;1

dx 5

Iteration of g2 converges to find Root B.

Root C ï¿½ 1.9

dg1 = 5/3 = 0.46 -1;x;1

dx 3V(5ï¿½(1.9)-2.6)2

Iteration converges to find Root C.

An example of the iteration failing.

For the iteration to fail the gradient of the rearrangement must not be between -1;x;1.

Root A ï¿½ -2.5

x0 = -1

x1 = -0.52655

x2 = 0.54920

x3 = 0.55313

x (root) = 0.55401 = Root B

dg2 = ((-2.5)3+2.6) = -2.605 -1;x;1

dx 5

Therefore, the iteration does not converge to the root of A but to the root of B as the gradient of g2 is below -1. Below it is shown graphically.

Comparison of Methods

Now that I have applied all three methods successfully to my equations I will use the same equation of y= x3-5x+2.6 to find the same root. This will help me to comment on the relative success of: the ease of mathematics/General understanding, Use of calculator/software, speed of convergence and problems with starting points.

The graph of y= x3-5x+2.6 is shown below with 3 roots to the equation.

The table of values is given below:

x

F(x)

-3

-9.4

-2

4.6

-1

6.6

0

2.6

1

-1.4

2

0.6

3

14.6

The 3 roots of the equation found from the rearrangement method are shown below:

Root A = -2.46099 Root B = 0.55401 Root C = 1.90698

For this comparison I will be searching for Root A in every case.

Decimal Search Method.

Finding Root A

x

F(x)

-3

-9.4

-2.9

-7.289

-2.8

-5.352

-2.7

-3.583

-2.6

-1.976

-2.5

-0.525

-2.4

0.776

-2.3

1.933

-2.2

2.952

-2.1

3.839

-2

4.6

x

F(x)

-2.5

-0.525

-2.49

-0.388

-2.48

-0.252

-2.47

-0.119

-2.46

0.013

-2.45

0.1439

-2.44

0.2732

-2.43

0.401

-2.42

0.5275

-2.41

0.6525

-2.4

0.776

x

F(x)

-2.47

-0.119

-2.469

-0.105

-2.468

-0.092

-2.467

-0.079

-2.466

-0.066

-2.465

-0.052

-2.464

-0.039

-2.463

-0.026

-2.462

-0.013

-2.461

-0.0001

-2.46

0.013

x

F(x)

-2.461

-0.0001

-2.4609

0.0012

-2.4608

0.0025

-2.4607

0.0040

-2.4606

0.0050

-2.4605

0.0065

-2.4604

0.0078

-2.4603

0.0091

-2.4602

0.010

-2.4601

0.012

-2.46

0.013

x

F(x)

-2.461

-0.0001

-2.46099

0.00003

-2.46098

0.00017

-2.46097

0.0003

-2.46096

0.00043

-2.46095

0.00056

-2.46094

0.00069

-2.46093

0.00082

-2.46092

0.00096

-2.46091

0.00108

-2.4609

0.00122

x

F(x)

-2.461

-0.000098

-2.460999

-0.000085

-2.460998

-0.000072

-2.460997

-0.000059

-2.460996

-0.000046

-2.460995

-0.000032

-2.460994

-0.000019

-2.460993

-0.000006

-2.460992

0.000007

-2.460991

0.000020

-2.46099

0.000034

I know that root A of the equation y= x3-5x+2.6 lies somewhere between: x = -2.460993 and x =-2.460992. So taking the answer as the midpoint of the two I get: x = -2.4609925 (7 d.p.). But seeing as I only need the answer to 5 decimal places I get x = -2.46099 (5 d.p.). This corresponds with the same answer I got originally.

Answer Root A: -2.46099 (5 d.p.)

Error: -2.46099 + 0.000005

Error Bounds: [-2.460995, -2.460985]

For these error bounds to be valid there must be a change of sign when the values are input into the equation:

f(x) = x3-5x+2.6

f(-2.460995) = -0.00003

f(-2.460985) = 0.00141

There is a change of sign in the two answers so I can say the error bounds are valid.

Newton-Raphson

The Newton-Raphson formula is: X1=X0 – f(X0)

f'(X0)

f(X0) = x3-5x+2.6

f'(X0) = 3×2-5

X0 = -2

X1 = -2 – x3-5x+2.6 = -2.65714

3×2-5

X2 = -2.47948

X4 (Root) = -2.46099

As you can see this is the exact root and has found it in four iterations.

Conclusions

### Ease of Mathematics

The mathematics required for the decimal search method is fairly basic. All that is required is to put values into the formula (substitution) and read of the values and find the change in sign. It is fairly simple to use and quite easy to understand.

The mathematics used in the Newton-Raphson method on the whole is more complicated than the decimal search method as basic concepts of differentiation is required. Difficulties occur with this method when more complex formulas are involved. For example, if I was required to differentiate sin, cos and tan I would have to start to question the method for people that find these difficult to differentiate. Therefore, the ease of this method is based around the complexity of the original equation and the ability to differentiate. The rearrangement method is quite simple as all that is involved is the ability to rearrange an equation. Also, a general understanding of which rearrangement is required so that the iteration converges to the required root.

### Use of Hardware/software

When carrying out the decimal search method, I was reliant on a graphical calculator as it showed the suitability of an equation and gave me all the information for unit tables. The table and graph function was simple to use and very straightforward.

The Newton-Raphson method required me to use my graphical calculator to work out the value of the iterations from the formula. What made it easier was the memory function. Where I could store equations using “ANS” in place of X. I also used Autograph to demonstrate the Newton Raphson method. This was fairly simple to use and did not involve a large amount of time learning to use.

For the rearrangement method I used the calculator and the memory function. I stored the two different arrangements into my calculator and that allowed me to access the two equations quickly to find the roots. I also used autograph to demonstrate graphically the convergences.

### Speed of convergence

Out of all three methods Newton-Raphson appears to converge to the root with the least number of iterations. Where it took four iterations for the Newton-Raphson method it took 11 iterations using the rearrangement method and took 5 iterations using the decimal search method. For decimal search method I classed one unit table from my calculator as 11 iterations as there are 11 calculations being worked out in one unit table. Therefore, there are many more iterations involved with decimal search which correlates with the length of time it takes to converge to the root. For the Newton-Raphson method I classed one iteration to be one calculation using the Newton-Raphson formula. I used my calculator to repeatedly press the execute button and this was used to calculate how many iterations there was. For the rearrangement method I classed one iteration to be one calculation using the iteration formula, whether it is g1 or g2. This was also a repeated process where I pressed execute has many times as required until I found the root to the degree of accuracy I required.

### Problems with Starting Points

There were no problems with starting points in the decimal search method. In the failure of decimal search I had to recognise the f(x) lowering and then raising. For the rearrangement method the starting point mattered depending also on which g(x) to use. I had to view my graph to see which derivative of g(x) was near 1 or -1. I noticed if I selected the other g(x) then I would find another root. When using the Newton-Raphson method the starting value mattered greatly because I noticed if I started with a different value then a different root could have been found. Also with the Newton-Raphson method I could never use the starting value of “0” as the solution of the formula would be trivial as in we would be dividing by zeros. Autograph helped me solve problems with starting points as it showed where about the solutions were, without autograph I would have to try more than one value.