Newton's method is a technique to estimate roots of a differentiable function. Invented by Newton in 1669, it remains a stalwart tool in numerical analysis. When used as intended it's remarkably efficient and stable. After a little experimentation, Newton's method yields some surprises that are very nice illustrations of chaos.
Let's begin with a look at the example that Newton himself used to illustrate his method. Let \(f(x)=x^3 - 2x - 5\text{.}\) The graph of \(f\) shown in Figure 1 seems to indicate that \(f\) has a root just to the right of \(x=2\text{.}\)
Newton figured that, if the root of \(f\) is a little bigger than \(2\text{,}\) then he could write it as \(2+\Delta x\text{.}\) He then plugged this into \(f\) to get
\begin{align*} f(2+\Delta x) &= (2+\Delta x)^3 - 2(2+\Delta x) - 5\\ &= 8 + 3\times2^2\Delta x + 3\times2\Delta x^2 + \Delta x^3 -4-2\Delta x - 5\\ &= -1 +10\Delta x + 6\Delta x^2 + \Delta x^3\\ &\approx -1+10\Delta x. \end{align*}In that last step, since \(\Delta x\) is small, he figures that higher powers of \(\Delta x\) are negligibly small. Thus, he figures that \(-1+10\Delta x \approx 0\) so that \(\Delta x \approx 1/10\text{.}\)
The point is that, if \(2\) is a good guess at a root of \(f\text{,}\) then \(2+1/10 = 2.1\) should be an even better guess. A glance at the graph seems to verify this. Of course, we could then repeat the process using \(2.1\) as the initial guess. We should get an even better estimate. The process can be repeated as many times as desired. This is the basis of iteration.
Let's take a more general look at Newton's method. The problem is to estimate a root of a real, differentiable function \(f\text{,}\) i.e. a value of \(x\) such that \(f(x)=0\text{.}\) Suppose also that we have an intial guess \(x_0\) for the actual value of the root, which we denote \(r\text{.}\) Often, the value of \(x_0\) will be based on a graph. Since \(f\) is differentiable, we can estimate \(r\) with the root of the tangent line approximation to \(f\) at \(x_0\text{;}\) let's call this point \(x_1\text{.}\) When \(x_0\) is close to \(r\text{,}\) we often find that \(x_1\) is even closer. This process is illustrated in Figure 2 where it indeed appears that \(x_1\) is much closer to \(r\) than \(x_0\text{.}\)
We now find a formula for \(x_1\) in terms of the given information. Recall that \(x_1\) is the root of the tangent line approximation to \(f\) at \(x_0\text{;}\) let's call this tangent line approximation \(\ell\text{.}\) Thus,
\begin{equation*} \ell(x) = f(x_0) + f'(x_0)(x-x_0) \end{equation*}and \(\ell(x_1)=0\text{.}\) Thus, we must simply solve
\begin{equation*} f(x_0) + f'(x_0)(x-x_0) = 0 \end{equation*}for \(x\) to get \(x_1 = x_0-f(x_0)/f'(x_0)\text{.}\)
Now, of course, \(x_1\) is again a point that is close \(r\text{.}\) Thus, we can repeat the process with \(x_1\) as the guess. The new, better estimate will then be
\begin{equation*} x_2 = x_1 - \frac{f(x_1)}{f'(x_1)}. \end{equation*}The process can then repeat. Thus, we can define a sequence \((x_n)\) recursively by
\begin{equation*} x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}. \end{equation*}This process is called iteration and the sequence it generates often converges to the root \(r\text{.}\)
We now present several examples to illustrate the variety of things that can happen when we apply Newton's method. Throughout, we have a function \(f\) and we defined the correpsonding Newton's method iteration function
\begin{equation*} N(x) = x - \frac{f(x)}{f'(x)}. \end{equation*}We then iterate the function \(N\) from some starting point or, perhaps from several starting points.
We start with \(f(x)=x^2-2\text{.}\) Of course, \(f\) has two roots, namely \(\pm\sqrt{2}\text{.}\) Thus, we might think, of the application of Newton's method to \(f\) as a tool to find good approximations to \(\sqrt{2}\text{.}\)
First, we compute \(N\text{:}\)
\begin{align*} N(x) &= x-f(x)/f'(x) = x-\frac{x^2-2}{2x} \\ &= x-\left(\frac{x^2}{2x}-\frac{2}{2x}\right) = x-\left(\frac{x}{2}-\frac{1}{x}\right) = \frac{x}{2}+\frac{1}{x}. \end{align*}Now, suppose that \(x_0=1\text{.}\) Then,
\begin{align*} x_1 &= N(1) = \frac{1}{2}+\frac{1}{1} = \frac{3}{2}\\ x_2 &= N(3/2) = \frac{3/2}{2}+\frac{1}{3/2} = \frac{17}{12}\\ x_3 &= N(17/12) = \frac{17/12}{2}+\frac{1}{17/12} = \frac{577}{408} \end{align*}Note that
\begin{equation*} (577/408)^2 = 332929/166464 = 2+1/166464 \end{equation*}so that third iterate is quite close to \(\sqrt{2}\text{.}\)
Note that we've obtained a rational approximation to \(\sqrt{2}\text{.}\) At the same time, it's clear that it would be nice to perform these computations on a computer. In that context, we might generate a decimal approximation to \(\sqrt{2}\text{.}\) Here's how this process might go in Python:
Note how quickly the process has converged to 12 digits of precision.Of course, \(f\) has two roots. How can we choose \(x_0\) so that the process converges to \(-\sqrt{2}\text{?}\) You'll explore this question computationally in Exercise 1.1.5.1. It's worth noting, though, that a little geometric understanding can go a long way. Figure 3, for example, shows us that if we start with a number \(x_0\) between zero and \(\sqrt{2}\text{,}\) then \(x_1\) will be larger than \(\sqrt{2}\text{.}\) The same picture shows us that any number larger than \(\sqrt{2}\) leads to a sequence that converges to \(\sqrt{2}\text{.}\)
We now take a look at \(f(x)=x^2+3\text{.}\) A simple look at the graph of \(f\) shows that it doesn't even hit the \(x\)-axis; thus, \(f\) has no roots. It's not at all clear what to expect from Newton's method.
A simple computation shows that the Newton's method iteration function is
\begin{equation*} N(x) = \frac{x}{2} - \frac{3}{2x}. \end{equation*}Note that \(N(1)=-1\) and \(N(-1)=1\text{.}\) In the general context of iteration that we'll consider later, we'll say that the points \(1\) and \(-1\) lie on an orbit of period 2 under iteration of the function \(N\text{.}\)
Sequences of other points seem more complicated so we turn to the computer. Suppose that we change the initial seed \(x_0=1\) just a little tiny bit and iterate with Python.
Well, there appears to be no particular pattern in the numbers. In fact, if we generate 1000 iterates an plot those that lie within 10 units of the origin on a number line, we get Figure 4. This is our first illustration of chaotic behavior. Not just because we see points spread all throughout the interval but also because we appeared to have a stable orbit when \(x_0=1\text{.}\) Why should the behavior be so different when we change that initial seed to \(x_0=0.99\text{?}\)
This set of exercises will be mostly experimental. So, fire up your favorite computational environment. This text will include examples using both Python and Mathematica.
Continuing with the example of \(f(x)=x^2-2\) explored in Subsubsection 1.1.3.1, compute ten Newton iterations for several values of \(x_0\text{.}\) Be sure to choose both positive and negative values and values that are both large and small in magnitude.
In the previous exercise, what happens when \(x_0=0\text{?}\) Draw a graph to illustrate the situation.
Let's modify Newton's original example just a little bit to consider
\begin{equation*} f(x) = x^3-2x-2. \end{equation*}