Numerical Solutions of Equations.

In this particular example if

f(x) = x2 - 1.62x + 0.6561 then

f(0.81) = 0.812 - 1.62(0.81) + 0.6561 = 0

Therefore there is a repeated root when x = 0.81.

In the table above y is always positive. This because the root is at x = 0.81 but I have only used increments of 0.1. You do not go to the next decimal place until you find f(x) = 0. Decimal search has failed in this case. Below is a zoomed in version of the curve y = x2 - 1.62x + 0.6561 clearly illustrating the problem.

Newton-Raphson

Using this method you start with an estimate (x1) for a root of f(x) = 0. You draw a tangent to the curve at this point. The point where the tangent cuts the x-axis gives the value for x2 and the process is repeated continuously.

The Newton-Raphson iterative formula can be used to rapidly converge to a root.

xn+1 = xn - f(xn)

f'(xn)

For this method I am going to use f(x) = x5 - 3x - 1. Using calculus f'(x) = 5x4 - 3

Therefore, xn+1 = xn - xn5 - 3xn - 1

5xn4 - 3

The graph below shows that the roots lie in the intervals [-2,-1], [-1,0] and [1,2]. I will attempt to find the root in the interval [-2,-1] by taking x = -0.95 as my starting value.

xn

xn+1 = xn - xn5 - 3xn - 1

5xn4 - 3

x0 = -0.95

x1 = (-0.955 - 3 x -0.95 - 1) ÷ (5 x -0.954 - 3) = -1.9534

x1 = -1.9534

x2 = (-1.95345 - 3 x -1.9534 - 1) ÷ (5 x -1.95344 - 3) = -1.6156

x2 = -1.6156

x3 = (-1.61565 - 3 x -1.6156 - 1) ÷ (5 x -1.61564 - 3) = -1.3851

x3 = -1.3851

x4 = (-1.38515 - 3 x -1.3851 - 1) ÷ (5 x -1.38514 - 3) = -1.2590

x4 = -1.2590

x5 = (-1.25905 - 3 x -1.2590 - 1) ÷ (5 x -1.25904 - 3) = -1.2186

x5 = -1.2186

x6 = (-1.21865 - 3 x -1.2186 - 1) ÷ (5 x -1.21864 - 3) = -1.2147

x6 = -1.2147

x7 = (-1.21475 - 3 x -1.2147 - 1) ÷ (5 x -1.21474 - 3) = -1.2146

x7 = -1.2146

x8 = (-1.21465 - 3 x -1.2146 - 1) ÷ (5 x -1.21464 - 3) = -1.2146

The root is x = -1.2146 to 5 s.f . or x = -1.2146 ?0.00005.

When x = (-1.2146 + 0.00005) = -1.21455, y = 7.73 x 10-4 (positive)

When x = (-1.2146 - 0.00005) = -1.21465, y = -1.54 x 10-5 (negative)

This method is demonstrated graphically below.

The pink lines show the Newton-Raphson iteration process. The vertical lines are the xn values while the diagonal lines are the tangents that provide the value for xn+1.

Using Newton-Raphson I can find the remaining roots in the intervals [-1,0] and [1,2]. I will use x = 0 and x = 1 as my starting points.

x

x

x0 =

0

x0 =

x1 =

-0.33333

x1 =

2.5

x2 =

-0.33473

x2 =

2.0364

x3 =

-0.33473

x3 =

.7001

x4 =

.4911

x5 =

.4037

x6 =

.3892

x7 =

.3888

x8 =

.3888

I have found the two remaining roots, which are x = -0.33473 ?0.000005 and x = 1.3888 ?0.000005.

Problems with Newton-Raphson

One example of failure with Newton-Raphson is when it fails to converge to the required root and fined an alternative root instead. An example of this is when the starting value used for Newton-Raphson is close to a stationary point of the curve f(x).

The example below demonstrates this when f(x) = x3 - 2x + 1 and the starting value is x = -0.8.

dy = 3x2 - 2 0 = 3x2 - 2 ?x = ?2/3 = ?0.816

dx

Differentiation has shown that there is a turning point when x = -0.816. The graphs below show that because the gradient at x = 0.81 is almost 0 the tangent diverges away from the required root and thus the remaining iterations converge to the root x = -1.618 as this is nearest to the point where the tangent of x = 0.8 meets the x axis and the following tangents do not have such a low gradient that may cause them to diverge away from x = -1.618 and back towards the root in the interval [0,1].

Fixed Point Iteration (Rearranging f(x) = 0 in the form x = g(x)

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 graph for y = x5-3x+1 shows the roots lie in the intervals [-2,-1], [0,1] and [1,2].

x5-3x+1 = 0, therefore x = x5+1

3

This provides the iterative formula: xn+1 = xn5+1

3

The curves above show y = x and y = g(x) = x5+1.

3

With the equation in the form x = g(x) means that you are now finding the points of intersection between the curves rather than when the curve y = x5-3x+1 crosses the x-axis.

I will first attempt to find the root in the interval [0,1]. I will take the end point of this interval (x = 1) as the starting point.

xn

xn+1 = x5+1

3

x0 = 1

x1 = (15 + 1) ÷ 3 = 0.66667

x1 = 0.66667

x2 = (0.666675 + 1) ÷ 3 = 0.37723

x2 = 0.37723

x3 = (0.377235 + 1) ÷ 3 = 0.33588

x3 = 0.33588

x4 = (0.335885 + 1) ÷ 3 = 0.33476

x4 = 0.33476

x5 = 0.33473

x5 = 0.33473

x6 = 0.33473

The iteration has found the root to an accuracy of five significant figures when x = 0.33473 (x = 0.334730 ?0.000005). This can be proved by substituting the lower and upper error bounds into y = x5-3x+1.

When x = (0.334735 +0.000005) = 0.334735, y = -2.52 x 10-6 (y is negative).

When x = (0.334735 - 0.000005) = 0.334725, y = 2.69 x 10-5 (y is positive).

The diagrams below show two close-ups of the iteration process. The pink lines show how the iterative formula converges on the root from the initial value (x0 = 1).

Problems with fixed point iteration

One limitation of this method is the fact that the gradients of the values around the root x on the curve y = g(x) must be between -1 and 1. In other words: -1 < g'(x) < 1.

g'(x) = 5x4

3

When x = 0.33473, g'(x) = 5 x (0.33473)4 = 0.020923 = -1 < 0.020923 < 1

3

As you can see the root in the interval [0,1] was correctly found as the gradient of g(x) falls within the acceptable boundaries. However, one iterative formula is not always successful at finding the other roots of an equation.

When x = 2, the iterative formula actually diverges away from the required root in the interval [1,2].

xn

xn+1 = x5+1.

3

x0 =

2

x1 = (25 + 1) ÷ 3 = 11

x1 =

1

x2 = (115 + 1) ÷ 3 = 53684

x2 =

53684

x3 = (536845 + 1) ÷ 3 = 1.49 x 1023

This can be explained by looking at the gradient of the values in the interval [1,2].

g'(x) = 5x4

3

When x = 1, g'(x) = 5(1)4 = 1.67 When x = 2, When 1, g'(x) = 5(2)4 = 26.67

3 3

As you can see the gradients are bigger than 1. Therefore, the iterative formula cannot be used to find the root in this interval.

Comparison of Methods

I am now going to make a comparison the three numerical methods that I have used. For fixed point iteration I tried to find a root of y = x5-3x+1. I will now try to find one root of y = x5-3x+1 using decimal search and Newton-Raphson and I will then compare the relative merits of the three methods in terms of speed. I will also talk about the advantages of computer software when using these three numerical methods.

Fixed point iteration: Earlier on it took six calculations to find one of the roots of f(x) = x5-3x+1 to be equal to x = 0.33473 as well as the initial step of rearranging y = f(x) into the form x = g(x).

Decimal search: I will now attempt to find the root of y = x5-3x+1 in the interval [0,1] using decimal search, to an accuracy of five decimal places.

It has taken five steps for me to find a change of sign in the value of y.

It has taken another five steps to find the root to an accuracy of 1 decimal place. (x = 0.3)

I am continuing this process of decimal search until I find the required root to an accuracy of five decimal places.

It has taken me thirty-six calculations to find the root to an accuracy of five decimal places (x = 0.33473 ?0.000005).

Newton-Raphson: I am again going to attempt to find the root of y = x5-3x+1 in the interval [0,1].

xn+1 = xn - f(xn)

f'(xn)

f(x) = x5 - 3x + 1. Using calculus f'(x) = 5x4 - 3

Therefore, xn+1 = xn - xn5 - 3xn + 1

5xn4 - 3

xn

xn+1 = xn - xn5 - 3xn + 1

5xn4 - 3

x0 = 0

x1 = (05 - 3 x 0 + 1) ÷ (5 x 04 - 3) = 0.33333

x1 = 0.33333

x2 = (0.333335 - 3 x 0.33333 + 1) ÷ (5 x 0.333334 - 3) = 0.33473

x2 = 0.33473

x3 = (0.334735 - 3 x 0.33473 + 1) ÷ (5 x 0.334734 - 3) = 0.33473

As you can see Newton-Raphson has converged to the required root very quickly. It only took three steps to confirm that x = 0.33473 ?0.000005. There were also the initial steps to form the Newton-Raphson formula that was used to make the calculations, such as differentiation.

Which method is quickest?

Decimal search required thirty-six calculations to converge to the root but the use of Microsoft Excel meant that the position of the change of sign could be found within seconds. Therefore it only took a few minutes for someone who knew how to use the software to find the root to the required degree of accuracy.

Newton-Raphson was the quickest of the three numerical methods. Newton-Raphson took only four steps and fixed point iteration took six steps to converge to the required root. The use of Microsoft Excel did not make a huge difference because a scientific calculator can easily be programmed with the required iterative formulae. A few presses of the 'equals' button would converge to the required root.

However, I have already shown that both Newton-Raphson and fixed point iteration are not always successful. In this particular example, fixed point iteration was successful at finding the root but if it wasn't then f(x) would have to be rearranged into its alternative form (x = 5V3x-1) to try and find the root (as was the case when attempting to find the root in the interval [1,2] ).

The most likely problem with Newton-Raphson was finding the wrong root if the tangent diverges away from the required root. Yet decimal search also had a problem by not showing a change of sign in the first set of calculations when the root had two decimal places.

Therefore, ignoring any potential problems I think that fixed point iteration and Newton-Raphson are quicker than decimal search at converging to the required root.

I have already made some mention of the use of technology to help speed up the process of finding the roots. Microsoft Excel was of great benefit when making calculations, as it only required the input of the initial values and the formulae. A few mouse clicks gave the results for the entire set of values within a few seconds.

Autograph was another very useful piece of software as it could be used to instantly visualise curves and gradient functions. This meant that within seconds I could produce an accurate curve instead of having to make some calculations and draw the curve myself.

Autograph also allowed me to see the intervals of the roots (or points of intersection in fixed point iteration). This saved a lot of time as I could easily pick appropriate starting values without having to waste time using trial and error to pick my starting value.

Autograph was very useful for both Newton-Raphson and fixed point iteration as it had an inbuilt function to make the various calculations in with a few mouse clicks and these could be used to confirm the values obtained from Microsoft Excel. It was also excellent for showing the iterative processes for both methods by zooming in on the roots as I have shown many times when using these numerical methods.

HANNAN SHAH

P2 Maths Coursework Hannan Shah

Numerical Solutions of Equations Page 2 of 14