Newton's Method for Finding Roots

An algorithm leads to chaotic behavior if two starting points which are close together generate iterates which are sometimes far apart and sometimes close together: $\left|a_{0}-b_{0}\right|$ is small but $\left|a_{n}-b_{n}\right|$ is large for lots (infinitely many) of values of $\mathrm{n}$ and $\left|\mathrm{a}_{\mathrm{n}}-\mathrm{b}_{\mathrm{n}}\right|$ is small for lots of values of $\mathrm{n}$.

The iterates of the next simple algorithm exhibit chaotic behavior. 

A Simple Chaotic Algorithm: Starting with any number between $\mathrm{0}$ and $\mathrm{1}$, double the number and keep the fractional part of the result: $\mathrm{x}_{1}$ is the fractional part of $2 \mathrm{x}_{0}, \mathrm{x}_{2}$ is the fractional part of $2 \mathrm{x}_{1}$, and in general, $x_{n+1}=2 x_{n}-\left[2 x_{n}\right]=2 x_{n}-\operatorname{INT}\left(2 x_{n}\right)$.

If $x_{0}=0.33$, then the iterates of the algorithm are $0.66,0.32$ (= fractional part of $\left.2 \cdot 0.66\right), 0.64,0.28,0.56, \ldots$ The iterates for two other starting values close to $\mathrm{33}$ are given below as well as the iterates of $0.470$ and $0.471$:

$\begin{array}{rlllll}\text { start }= & \mathbf{x}_{\mathbf{0}} & \mathbf{0. 3 2} & \mathbf{0. 3 3} & \mathbf{0. 3 4} & \mathbf{0. 4 7 0} & \mathbf{0. 4 7 1} \\ & \mathrm{x}_{1} & 0.64 & 0.66 & 0.68 & 0.940 & 0.942 \\ & \mathrm{x}_{2} & 0.28 & 0.32 & 0.36 & 0.880 & 0.884 \\ & \mathrm{x}_{3} & 0.56 & 0.64 & 0.72 & 0.760 & 0.768 \\ & \mathrm{x}_{4} & 0.12 & 0.28 & 0.44 & 0.520 & 0.536 \\ & \mathrm{x}_{5} & 0.24 & 0.56 & 0.88 & 0.040 & 0.072 \\ & \mathrm{x}_{6} & 0.48 & 0.12 & 0.76 & 0.080 & 0.144 \\ & \mathrm{x}_{7} & 0.96 & 0.24 & 0.56 & 0.160 & 0.288 \\ & \mathrm{x}_{8} & 0.92 & 0.48 & 0.12 & 0.320 & 0.576 \\ & \mathrm{x}_{9} & 0.84 & 0.96 & 0.24 & 0.640 & 0.152\end{array}$

There are starting values as close together as we want whose iterates are far apart infinitely often. Many physical, biological, and business phenomena exhibit chaotic behavior. Atoms can start out within inches of each other and several weeks later be hundreds of miles apart. The idea that small initial differences can lead to

dramatically diverse outcomes is sometimes called the "Butterfly Effect" from the title of a talk ("Predictability: Does the Flap of a Butterfly's Wings in Brazil Set Off a Tornado in Texas?") given by Edward Lorenz, one of the first

people to investigate chaos. The "butterfly effect" has important implications about the possibility, or rather the impossibility, of accurate long–range weather forecasting. Chaotic behavior is also an important aspect of studying turbulent air and water flows, the incidence and spread of diseases, and even the fluctuating behavior of the stock market. 

Newton's method often exhibits chaotic behavior, and, since it is a relatively easy to study, is often used as a model to study the properties of chaotic behavior. If we use Newton's method to approximate the roots of $\mathrm{f}(\mathrm{x})=\mathrm{x}^{3}-\mathrm{x}$ (with roots $0,+1$ and $-1$), then starting points which are very close together can have iterates which converge to different roots. The iterates of $.4472$ and $.4473$ converge to the roots $\mathrm{0}$ and $+1$, respectively. The iterates of the middle point $.44725$ converge to the root $-1$, and the iterates of another nearby point, $\sqrt{1 / 5} \approx.44721$, simply cycle between $-\sqrt{1 / 5}$ and $+\sqrt{1 / 5}$ and do not converge at all.

Practice 6: Find the first 4 Newton's method iterates of $\mathrm{x}_{0}=.997$ and $\mathrm{x}_{0}=1.02$ for $\mathrm{f}(\mathrm{x})=\mathrm{x}^{2}+1$. Try two other starting values very close to $\mathrm{1}$ (but not equal to $\mathrm{1}$) and find their first $\mathrm{4}$ iterates. Use the graph of $\mathrm{f}(\mathrm{x})=$ $\mathrm{x}^{2}+1$ to explain how starting points so close together can quickly have iterates so far apart.