Newton's Method: Cute trick.

I noticed a cute trick regarding Newton's Method;
never having actually read any proofs of theorems
giving conditions under which it's guaranteed to
work, I'm curious whether the trick is well known.

First, what a person might call a "naive Newton's
Method":

Thm 0. Suppose f : R -> R is twice differentiable,
f'(x) >= a > 0 for all x and |f''(x)| <= b for all x.
Suppose x_0 is such that |f(x_0)| < 2 a^2/b. Let

x_{n+1} = x_n - f(x_n)/f'(x_n).

Then x_n -> p, where f(p) = 0, and in fact

|p - x_n| <= 2a/b [(b/2a^2) f(x_0)]^(2^n) .

I imagine that or things very much like it are
well-known. Just for the record:

Proof: Taylor's Theorem shows that

|f(x+h) - (f(x) + h f'(x))| <= b h^2 / 2.

If x = x_n and h = - f(x)/f'(x) then
x + h = x_{n+1} and f(x) + h f(x)/f'(x) = 0
so

|f(x_{n+1}| <= b h^2 / 2
<= (b/2a^2) f(x_n)^2.

By induction this shows that

|f(x_n)| <= 2a^2/b [(b/2a^2) f(x_0)]^(2^n) .

But

|f(x_n)| = |f(x_n) - f(p)| >= a |x_n - p|.

QED.

It's more or less obvious that the hypothesis
on the second derivative can be replaced by
the weaker assumption that

|f'(x+h) - f'(x)| <= b |h|.

In case this is not obvious:

Thm 1. Suppose f : R -> R is differentiable,
f'(x) >= a > 0 for all x and

|f'(x+h) - f'(x)| <= b |h|

for all x, h. Suppose x_0 is such
that |f(x_0)| < 2 a^2/b. Let

x_{n+1} = x_n - f(x_n)/f'(x_n).

Then x_n -> p, where f(p) = 0, and in fact

|p - x_n| <= 2a/b [(b/2a^2) f(x_0)]^(2^n) .


Proof:

f(x+h) - (f(x) + h f'(x))

= int_0^h (f'(x+t) - f'(x)) dt,

so

|f(x+h) - (f(x) + h f'(x))|

<= int_0^h bt dt = b h^2 / 2.

(That's for h > 0; for h < 0 the notation
might need to be slightly different.)
The rest of the proof is the same.

QED.

I call that "naive" because in actual applications
f may not be defined on the whole line or if it is
you're not going to know those inequalities on the
whole line. Maybe "useless" would be better.

More realistically, say f is defined on the closed
interval I = [p,q], f(p) < 0, f(q) > 0, and we
have f' >= a > 0 and |f'(x) - f'(y)| <= b |x - y|
on I.

You could do the same thing as before, except you
have to add on some extra fussiness regarding x_0
to ensure that x_n is in I for all n. The "cute
trick" I noticed is a way to avoid those details:

Let F:R -> R be the differentiable function such
that f = F on I, F'(x) = f'(p) for x < p and
F'(x) = f'(q) for x > q. I'll leave it to you
to write down a formula for F. Then F' >= a
and |F'(x) - F'(y)| <= b |x - y| on the entire
line. (The fact that F may not be twice differentiable
even if f is is why I gave Theorem 1...)
So Theorem 1 gives a way to find a zero
of F, and of course a zero of F must be _the_ zero
of f, since F is strictly increasing.

It gets cuter: Thinking about actually implementing
the above plan in code, it seems like a pain to have
to define F and use it, especially since it's only
going to come up a small number of times. I noticed
that if x < p then

x - F(x)/F'(x) = p - f(p)/f'(p).

Similarly for x > q. So if x_n ever wanders outside
of I it doesn't matter, just replace x_n by the
appropriate endpoint.

Define clamp(x, p, q) to be p for x < p, x for
p <= x <= q, and q for x > q. We've proved this:

Thm 2. Suppose I = [p,q], f : I -> R is differentiable,
f'(x) >= a > 0 for all x in I and

|f'(x) - f'(y)| <= b |x - y|

for all x, y in I. Suppose x_0 in I is such
that |f(x_0)| < 2 a^2/b. Let

x_{n+1} = clamp(x_n - f(x_n)/f'(x_n), p, q).

Then x_n -> p, where f(p) = 0, and in fact

|p - x_n| <= 2a/b [(b/2a^2) f(x_0)]^(2^n) .



David C. Ullrich

"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)
.

Relevant Pages

  • Re: Three point determinant simplification
    ... And this implies the algebraic manipulation that does the trick. ... The rightmost term is zero. ... ultimately trumps geometric reasoning. ...
    (comp.graphics.algorithms)
  • Re: Date Function
    ... That translates to ... The trick is that the zero day of a month is the day previous to the first ... I am working on the last month minus 12 months. ...
    (microsoft.public.access.queries)
  • Re: Interesting theory on dance
    ... to zero were intentionally misled because that was the ... only way to trick them into leading lightly enough. ... I talk about pressure guages because might be the simplest ... rhn A.T nicholson d.0.t C-o-M ...
    (rec.arts.dance)
  • Re: Sum alternate columns over a large (>100) range
    ... You want to ignore numbers less than or equal to zero, ... minor modification to Max's first formula that should do the trick: ...
    (microsoft.public.excel.misc)
  • Re: why put #?!
    ... Gee, that is a cute trick, is it not? ... "trick" of using compiler directives is a rather good idea..and one I never ...
    (microsoft.public.access.modulesdaovba)
Loading