Back to MAIN
We look for a root r so that f(r) = 0. Let us further assume, we found an interval J = (a,b) where the only root r must exist.
We look for a method to find a sub-interval of J where a must still exist. We must further assume that f ' and f '' don't have a
zero-point on the whole closed interval J+ = [a,b] .
We choose 2 random points R1 and R2 on f, so that their x-projections x1 and x2 both are in J+ and x1 < x2
The classical straight line through the 2 points R1 and R2 tells us that the difference d between the point T
on the tangent and the curve point C must be equal to:
d = f(x1) + [f(x2) - f(x1)](x2 - x1)-1(x - x1) - f(x)
This can be rewritten into:
d = (x2 - x)(x1 - x)(x2 - x1)-1{[f(x2) - f(x)](x2 - x)-1 - [f(x1) - f(x)](x1 - x)-1}
The mean value theorem tells us, that there are points o1 and o2, so that x1 < o1 < x < o2 < x2 and where
must hold:
f(x1) - f(x) = f '(o1)(x1 - x) and also: f(x2) - f(x) = f '(o2)(x2 - x) ..and so
d = (x2 - x)(x1 - x)(x2 - x1)-1[f '(o2) - f '(o1)], which means that if f ''>= 0 over J+, then f ' is monotonic
increasing over J+ (we also say f is convex over J+)
Above graphically shown all 4 cases..in the convex case, the line between A and B lies over the curve.
Our original assumptions (f ' and f '' are never 0 over J+) mean from a geometrical point of view, that
our function f will be always either monotonic increasing or monotonic decreasing over J+. We should not
also forget, that the other assumption was that we have only 1 solution in our chosen interval.
The method, how we can narrow the interval, we see graphically in the next illustration:
b1 is the point of intersection of the tangent in B with the x-axis..so the sequence (b,b1,..,bn) is represented by the recursion
bj+1 = bj - f(bj)[f '(bj)]-1, from the picture - we see bk < bk - 1 and that the sequence converges against r.
Exactly the same follows from the sequence on the right side, but there of course: ak > ak - 1. This method
of retrieving r we know as the Newton method .The remaining task now would be to show, that
a) the sequence { bk } is monotonic decreasing
b) the sequence { ak } is monotonic increasing
c) both sequences converge against the same limit r
These proofs are all a nice exercise for university students in their 1st year, which means for us that we can
skip them Much more interesting, is the following statement:
Let be f a rational function defined over the interval J. Let be a and b 2 different points from J.
Then there is such a number z, with a < z < b, so that
f(b) = f(a) + f '(a)(b - a) + 0.5 f ''(z) (b - a)2
|
From the geometrical point of view, this means that the ordinate-delta between the curve-point C[b,f(b)] and its
projection onto the tangent going through T[b;yt] can be always expressed as 0.5 f ''(z) (b - a)2 with the
appropriately chosen value z.
There is certainly such a number p, that f(b) = f(a) + f '(a)(b - a) + p(b - a)2 holds. If we define an auxiliary function g as :
g(x) = f(b) - f(x) - f '(x)(b - x) - p(b - a)2, then we see that g(a)=0=g(b), then again the mean value theorem is telling us,
that there is a number c in (a , b) , so that g '( c) = 0, but as we can see easily:
g '(x) = (b - x)[2p - f ''(x)] --> (b - c)[2p - f ''(c)] = 0, and because b is different from c, we must have:
p = 0.5 f ''(c), which proves the statement above.
Now, lets look at a sequence {ai} converging against the root r in our "Newton way".. so an = an - 1 - f(an - 1)f-1(an - 1)
and lets define sn - 1 := - f(an - 1)f-1(an - 1), so we obtain an = an - 1 + sn - 1, identifying an-1 as a and an as b, we
can apply the statement from above, eg:
f(an) = f(an - 1) + f '(an - 1)(an - an - 1) + 0.5 f ''(c)(an - an - 1)2, and an - 1 < c < an.
In other words:
f(an) = f(an - 1) + f '(an - 1)sn - 1 + 0.5 f ''(c)s2n - 1, and because of the original definition of sn, we see that
f(an - 1) + f '(an - 1)sn - 1 = 0. We get in the end: f(an) = 0.5 f ''(c)s2n - 1 .. which is an important result, which
is telling us, that if the only root r is in J+:=[a , b] and |f ''(x)| <= M for all x in J+, and using the error-estimation
|r - an|<=|f(an)|m-1 (assuming |f '(x)|>= m > 0 for all x in J+), we will get the handy estimation help:
|r - an| <= 0.5 M m-1s2n - 1 = 0.5 M m-1[f2(an - 1) [f '(an - 1)]-2
|
So, in case of the equation: f(x) = x3 + 2x2 - 9x - 4, and J+=[-0.5;0] we would obtain in the 1st iteration(with
starting point = 0) the value of -0.444444....The absolute value of the first derivation over J+ is larger or equal
to 10.18519.., and the same for the 2nd derivation is smaller than 4.0, which means that our value -0.4444444 is less
than (4/2*10.18519)*16/81 = 0.038787..away from the real solution.
The principle of the Newton interpolation we can understand also from a different angle. Let be r again the root of f, and
b its approximation, so that r = b + h. This means f(b + h) = 0. Now using the Taylor serie for f, we would get:
f(b + h) = f(b) + [f '(b)h]/1! + [f ''(b)h2]/2! + [f '''(b)h3]/3! + ... + [f(n)hn]/n!
|
if we are close enough to the root, eg |h| is "small", in this case all its higher exponents we can ignore...so
we end up with f(b + h) = f(b) + [f '(b)h]/1! = 0, which in reality means, that b - f(b)f-1(b) is the better approximation
In this sense, the Newton method can be also applied to complex roots and equations with complex coefficients
This idea of the "improved" b can be played further, where we try to determine h from the quadratic equation:
f(b) + h f'(b) + 0.5h2f''(b) = 0, which seems to be quite impractical at first glance, but we can linearize it by
stating h is approx -f(b)/f'(b). ==>
0 = f(b) + h f'(b) - 0.5h f(b)f''(b)[f'(b)]-1 eg: h = -f(b)[f'(b) - 0.5f(b)f''(b)[f'(b)]-1]-1
This method is converging very fast...now lets try that in k4 .. one possible solution in k4 handling improved newton-approximations of
polynomial roots can look like that
der:{-1 _ x*|!#x}
pev:{y+z*x}
p:1 0 -25 -97
\P 16
newt2:{pol:y;pol1:der@pol;pol2:der@pol1;
fu:{[pol;pol1;pol2;x];f:pev[;;c:x]/;x0:f@pol;x1:f@pol1;x2:f@pol2;c-x0%x1-x0*x2%2f*x1};
fu0:fu[pol;pol1;pol2;]/;
fu0 x}
Now, lets look at both solutions from a graphical point of view...
case 1: f1 = x3 - 25x - 97 = 0 (Exact root = 6.3468941701122139..)..we take a bad starting point = 2.0
We see here clearly..the improved method does (as expected)..NOT bring the better results in all cases. Until recursion level 8
both methods are behaving similar, then the improved method continues to be at loss in finding the correct value, and only much
later it finds the right way. In such a case the classical newton method would be 2-3 times faster in CPU time.
For starting point 3.0 both methods fail..(3.0 is still a bad starting point, which is of course not the main reason for the failure)
But not lets look at the starting point of 4.0..
And here we see, that in case of a "reasonable" starting-point, our improved method seem to go the faster way.
(but we should really not exaggerate with the starting points)Looking at a rather unspectacular case like:
2x5 - 4x4 + 7x3 - 2x2 + 11x - 39 = 0 and a wild starting point of 35.0, we also see the expected advantage
of the improved method graphically..
The improved method "landing" ability even with this very bad guess is impressing, after 8 iterations we are there,
the classical method converges smoothly too, but reaches the accuracy of its brother function after 15 iterations.
The correct value is 1.650603...and the improved method is because of the lower need for iteration cycles by about
50% faster.
Back to MAIN
©++ MILAN ONDRUS