I can express this interval using the Error bounds.
Change of sign method has big advantage because they provide bounds (the two ends of the interval) within root lies. Knowing that the root lies in the interval [0.680760, 0.680770] means that you can take the root as 0.680765 with a maximum error of +/- 0.000005.
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.
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.
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.
As we can see we have change of sign in place where no curve of that function is. This method shows us that root is situated in interval [2, 3]. But between those points we have empty space only. This is another example when the decimal searching method failure.
The equation 1/(x-2.5)=0 has no root, but change of sign methods will converge on a false root at x=2.5.
Newton – Raphson Method
I start with an initial guess which is reasonably close to the true (real) root, then the function is approximated by its tangent and one computes the x-intercept of this tangent line this x-intercept will typically be a better approximation to the function's root than the original guess, and the method can be iterated.
The formula for converging on the root can be easily derived. Suppose I have some current approximation xn. Then I can derive the formula for a better approximation, xn+1 by referring to the diagram on the right hand side.
The equation of the straight line may be written as:
Therefore the equation of the tangent can be written:
y- f(xn)= f ‘(xn)( xn+1- xn)
The tangent cuts the x-axis at (xn+1, 0)
0-f(xn)= f ‘(xn)( xn+1- xn)
This rearrangement gives our iterative formula for Newton Raphson method:
xn+1=xn- (f(xn)/( f ‘(xn))
An illustration of iteration of Newton's method (the function f is shown in blue and the tangent line is in red). We see that xn + 1 is a better approximation than xn for the root x of the function f(x).
Below I have example how the Newton –Raphson’s method looks like, when we will zoom it out. It is some kind of zigzag, which is made by triangles.
Last root is situated at point x=1,348047 (6d.p.)
WHEN NEWTON - RAPHSON METHOD FAILURE?
If I will take a starting point of x0=0, look what give us Autograph software:
The point at x0=0 is one of two stationery points. If my starting values are closes to those stationery points, the autograph will draw a tangent which will be parallel to y-axis. In dialog window I will see OVERFLOW.
If I will choose the point, which is the one of the stationery points, this method will failure. Because in this case I will not have any chances to find another, closes to truth root point. Below you can see those points. They are marked by green.
Rearranging the equation into form x=g(x)
I have choose the function y=4x5−6x³+1 for this section of my coursework.
I will try to rearrangement the equation 4x5−6x³+1=0 into form x=g(x).
In other words I should have a single x on left hand side and a function of x on the right hand side.
This can be rearrangement in two ways.
Those rearrangements give me my iterative formulas:
For first case:
For next case:
Graph of y=(x) and y=g(x)
1. First rearrangement.
I will look on the graph of function y=(x) and y=((6x3-1)/4)0.2. Below I show you that graph.
The x-coordinates of the three points where these graphs intersect are the roots of the original equation.
I will perform the iteration using a starting value of x0 =-2 and attempt to find the root in the interval [-2,-1]. We must also remember this graph is an example of a Staircase convergence.
And I have found the first root, which lies in that interval. I must say that that process will take a bit of time if somebody would like to work in Excel. But I’ve found the root at x= -1.273 (3d.p)
I’m, trying to find now next root which lies in [1,2]. For my starting value I choose x0 =1.
The staircase diagram goes towards the root. Because gradient at x=1 is less than 1.
To show that method could also failure. If I would like to find where exactly the root lies, we now that in an interval [0,1]. But where is it exactly?
I will try two starting point, one at x=0, and next one at x=0.7. Look what I’ve done.
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.
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.