(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 .
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.
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
We need to prove that or, equivalently,
Similarly, we need to prove that
Let , so that for , and (recall that ). We have that and therefore . Hence (1) is equivalent to
Similarly, , so that (2) is equivalent to
Now we make use of the following lemma:
Lemma. Suppose that are positive integers with , that and are positive reals, and that
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.
We consider two cases: Suppose first that for all . Then
Using that for all , we conclude that
If, on the other hand, for some , we may as well assume that and, using the convexity of the function , we have that
and the result also follows in this case.
This completes the proof.
[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.