(Disclaimer: This is planned to be part of a larger set of notes on the dynamics of Newton’s method.)
We present Barna’s proof of the following result: Suppose that
is a polynomial all of whose roots are real and
is is associated Newton’s function. If
is a root of
and its immediate basin of attraction
is bounded, then
and
.
1. Introduction
If is a differentiable function, we define
, Newton’s function for
, by
for all values of such that
. Under reasonable assumptions on
,
can be extended (by continuity) so that it is also defined at those points
such that
. Note that if
, then
exists, and we have
The function is of course the function obtained through the application of the familiar Newton’s method for approximating roots of
. Recall that (under reasonable assumptions on
) the method starts with a guess
for a root of
, and refines this guess successively, with each new guess
being obtained from the previous one
by replacing
with its linear approximation at
, that is, with the line
, and letting
be the value of
where this approximation equals
, that is,
.
One can say much about what makes a function “reasonable”, but for the purposes of this note it suffices that polynomials certainly fall under this category. One easily verifies that if ( is a real valued polynomial and)
then there is an open neighborhood
of
such that if
, then for all
we have that
is defined,
, and
. This is perhaps easiest to see if we assume that
is a simple zero, that is,
. In this case
and, by continuity,
and
are defined, and
, for all
in a neighborhood
of
. But if
is in this neighborhood, by the mean value theorem we have that
. It follows that
is also in this neighborhood, and that successive applications of
result in a sequence that converges to
.
The largest interval about
such that for any point
in
the sequence
is well defined and converges to
, we call the immediate basin of attraction of
. One can verify that
is open, that
, and that if
is bounded, say
, then
and
, so that
is a cycle of period
for
. By the observations above, we know that if
is whichever of
and
is closest to
, then
.
The study of the dynamics of Newton’s method is very interesting. Nowadays, most work on the subject is part of the more general topic of complex dynamics, but the study of the dynamical behavior on deserves to be better known. In this note I present a result of Barna, who in the late 1950s and early 1960s began such a study. The result is an inequality that improves the observation at the end of the previous paragraph. This inequality is useful in studying the chaotic behavior of the method for polynomials of degree at least
, see for instance [SU84].
2. Barna inequality
Theorem (Barna [Bar61]). Suppose that
is a polynomial all of whose roots are real. If
is a root of
and its immediate basin of attraction
is bounded, then
and
.
Barna’s argument is completely elementary, but it is not easy to locate it in modern literature.
Proof.
Let where
,
, and the
are positive integers. Suppose that
has degree
, so that
. Letting
we see that and
. Suppose
,
, and
are as in the statement of the theorem, so that
,
,
, and all other
lie outside of
. Since
, in particular we have that
, though we do not need to assume this (it will follow from the analysis below). Note that
and
Also,
We need to prove that or, equivalently,
Similarly, we need to prove that
Since , our task is to deduce from (1) and (2) that
and
Let , so that
for
, and
(recall that
). We have that
and therefore
. Hence (1) is equivalent to
or
or
Similarly, , so that (2) is equivalent to
while (3) and (4) are respectively equivalent to
and
Now we make use of the following lemma:
Lemma. Suppose that
are positive integers with
, that
and
are positive reals, and that
and
hold. It then follows that
First we prove that the lemma gives us the result. Note first that, under the assumptions of the lemma, we also have that
To see this, simply apply the lemma with and
in place of
and
.
Now, if ,
, and for each
with
and
, we have that
for precisely
indices
, then the assumptions of the lemma correspond exactly to (5) and (6), while its conclusion is precisely (7), and the additional conclusion remarked in the paragraph above is precisely (8).
It remains to prove the lemma.
Proof.
We consider two cases: Suppose first that for all
. Then
or
Using that for all
, we conclude that
as wanted.
If, on the other hand, for some
, we may as well assume that
and, using the convexity of the function
, we have that
so
and the result also follows in this case.
This completes the proof.
References
[Bar61] Béla Barna. Über die Divergenzpunkte des Newtonschen Verfahrens zur Bestimmung von Wurzeln algebraischer Gleichungen. III. Publ. Math. Debrecen, 8:193–207, 1961. MR0135224 (24 #B1274).
[SU84] Donald G. Saari and John B. Urenko. Newton’s method, circle maps, and chaotic motion. Amer. Math. Monthly, 91(1):3–17, 1984. MR0729188 (85a:58060).
Pdf version of this note.