Linear Interpolation Methods to Approximate Roots

Date: 12/25/2000 at 07:06:34
From: Threepwood
Subject: Approximation of roots

While combing the Web for resources on linear interpolation methods of 
approximating non-linear equation roots, I noticed several different 
criteria for ending the iteration.

For interval [xa,xb] new endpoint [xc]

(1) end when xa~=xb (approximately equal) up to required dp/sf

(2) end when xc shows no change up to a certain tolerance or precision

(3) end when f(xc)~=0

Unless I'm mistaken, in the linear interpolation formula

     xc = xb-yx((xb-xa)/(yb-ya))

for many functions, one endpoint will remain stationary (i.e. not 
moving at all) while the other endpoint shifts towards the root. Thus, 
criterion (1) will never be reached. Am I correct in assuming that 
criterion (1) is more or less unacceptable?

Criteria (2) and (3) appear to be synonymous to me. Both criteria will 
be fulfilled at roughly the same time in the process. Thus, of these 
three, which is the best method for knowing when the best 
approximation to a certain precision has been found?

For the Newton-Raphson method, I've found two general derivations/ 
explanations. One uses geometry, where the tangent to the first guess 
is shown to cut even closer to the root, and the tangent to that cuts 
even closer, and so on. Another begins with a Taylor's expansion of 
f(x).

     f(x) = f(0) + f'(0)(x-x0)

where x0 is the initial guess. Letting f(x) = 0, we get:

     x1 = x0 + f(x0)/f'(x0)

Which explanation is more accurate, if that is so? Or are there better 
ways to derive this?

Thanks.

Date: 12/26/2000 at 20:57:39
From: Doctor Fenton
Subject: Re: Approximation of roots

Dear Threepwood,

You've asked some very good questions.  I'm not an expert on numerical 
analysis, but I think I might shed some light on the issues you raise.

First of all, when you say "linear interpolation" for finding roots, 
there are actually two methods that use linear interpolation: "False 
Position" (or, in the Latin wording, "Regula Falsi"), and the Secant 
Method. False Position always brackets the root. That is, at each 
stage, the method produces two numbers a_n and b_n, so that the root r 
is between them: a_n < r < b_n. At the next stage, it replaces one of 
the numbers a_n and b_n with a new value and leaves the other value 
unchanged, and the new values a_(n+1) and b_(n+1) still bracket the 
root. The Secant Method produces a sequence of numbers that do not 
necessarily bracket the root.

Your first criterion might be more useful for the False Position 
method, but you are correct that for certain functions, it will tend 
to be only one endpoint that moves, and the method will converge very 
slowly, by that criterion.

Then second and third criteria would be more appropriate for the 
Secant Method, but again, there are functions for which the second 
criterion will produce very slow convergence.

The third criterion can be useful, but it depends upon whether you are 
primarily interested in a value that makes the function small, or 
whether you really need the correct value of the (exact) zero. If the 
root is a multiple one, so that the function is roughly quadratic or 
cubic in (x-r), where r is the exact root, then the function will be 
very flat near the root. For example, x might be .01 units from r, but 
f(x)~10^(-6), so relatively poor approximations of the root r will 
produce very small function values.

So I would say that there is no "universal" criterion. The best one to 
use depends upon what you are trying to find: a good approximation to 
the root, or just a value x which produces a small f(x).

Also, unless you are studying the question just to explore the 
question of how well linear interpolation methods find roots, it 
should be clear that these aren't particularly great methods. If you 
really have a practical problem, and not just an exercise in numerical 
analysis, you would be better off using a more sophisticated 
root-finding method, such as the 'Van Wijngaarden-Dekker-Brent 
Method', which is explained (along with source code) in "Numerical 
Recipes" by Press, et al.

The two methods of deriving Newton-Raphson you describe are the same: 
the Taylor series truncated at the first term just gives the tangent, 
which is what your "geometric" method uses. This is a very powerful 
method, provided one starts sufficiently near the root, so that the 
graph of f is monotone, and preferably of the same concavity near the 
root (which isn't possible if the root is also a point of inflection). 
As with the linear methods, Newton-Raphson can fail (often 
spectacularly) for some functions, if one doesn't start near enough to 
the root.

I hope this is of some help. I'd recommend reading the chapter on 
root-finding in _Numerical Recipes_, which is a good book, especially 
for outlining the main ideas and presenting generally very good 
methods.

If you have further questions, please write us again.

- Doctor Fenton, The Math Forum
  http://mathforum.org/dr.math/