Numerical solutions of equations.

Decimal Search

We will look at the polynomial equations which cannot be solved by algebraic methods.  All linear and quadratic equations can be solved algebraically so we are interested in equations with powers of x3 at least.

The first method to be looked at is the Decimal Search.  This involves finding an interval of the x- axis in which a root of the equation lies. 

Let's consider the function: y=x5+4x2-2. The region to scan to find the first root is -4<x<4.

We can identify three intervals which have a change of sign:  [-2,-1]  , [-1,0] , [0,1].

If we sketch the graph of the function three roots are confirmed in these intervals:

I’ll draw a sketch to show the curve crossing the x- axis in this interval.

I am  going to concentrate my search on this interval [0,1]  and look at interval of width 0.1 unit.

The change of sign occurs in [0.6 , 0.7] which is where the root lies.

This process can now be continued using intervals of width 0.01 then by using intervals of width 0.001 etc.

I must think about problems. Are there any occasions when this decimal search method might not find root? I’ve got few examples of that.

1.

In interval [1,2] we have no change of sign (look to the  table above).

The Decimal Searching method disappoints, it is inexact. When the curve touches the x-axis there is no change of sign, so change of sign methods are doomed to failure.

2.

At point x=2, f(x)=0, so I found first root.

We got another root between 0 and 1.

But that one's repeated root. The decimal search method does not show between those values any change, because curve touches  y-axis on that particular point, so there we have no change in sign, as well.

Above we can see interval [0,1] and root which lies there.

3.

I will try two starting point, one at x=0, and next one at x=0.7. Look what I’ve done.

At x=0.

At x=0.7.

This is a little bit weird. Why they not come to this root which I want. Answer is very simple and depends of the gradient of g(x). Gradient is in this method responsible for finding the roots. A rearrangement will find only root at x if the gradient of g(x) at this point x is between -1 and 1. So algebraically, if -1<g(x),1.

I will differentiate the gradient.

g(x) =((6x3-1)/4)0.2

g’(x)=

Therefore at x=0, gradient=

and at x=0.7, gradient=

We can not find the root in [0, 1] using this rearrangement. We can however use a different rearrangement to find this root.

2. Second rearrangement.

I will look on the graph of function y=(x) and y=((-4xn 5-1)/6)1/3. Below I show you that graph.

I must find only one remaining root. I know that it lies in interval [0,1].

I know that gradient at point x=0 is less than 1 and bigger than -1. So I can clearly say that starting pint I’ve choose will go definitely towards the right root.