Newton's Method and Chaos
Return to Contents
In this subsection of the
exploration, will explore the fact that for certain functions, Newton's Method
may never converge to a nearby solution, but may cycle endlessly in a stable
way. Here, stable means that for almost any start point that you choose, the
recursive sequence eventually begins to oscillate among several values.
We will
next explore the "logistic map" mentioned above, on the Recursive
Sequences page. This recursive sequence is defined by choosing a start
point 
in the interval [0,1],
selecting a parameter value C in [0,4], and then by setting 
and letting
The logistic
map has a number of remarkable properties. For example, a point 
= a(k) is fixed
by the sequence if
= a(k) = a(k+1).
Let us
work with a fixed parameter value, say 
for now. For C = 2, 
is fixed.
In
that case, the fixed point 0 is unstable, in that points near 0 tend to be
repelled by 0 or move away from 0 under iteration. Try it. Remember
to Reset before each new recursion.
On
the other hand, is stable, because points near
it tend to be attracted to it. We call
a stable attractor when C = 2.
In
general, a number x is fixed if it satisfies the equation C*x*(1-x)
= x. The fixed points depend on the parameter C, and if C
> 1, there are 2 of them: 
.
In
fact, if C < 1, 0 is a stable attractor. And if 1 <
C < 3, 0 is an unstable attractor and the other fixed point
is stable. Other behaviors can occur. We say a point = a(k)
is periodic of period n by the sequence if = a(k)
= a(k+n). These periodic points arise for various values of C
in surprisingly interesting ways.
The
first periodic point of period 2 (that is not fixed) occurs when the stable
attractor becomes unstable and gives birth to two points near it where the
sequence oscillates back and forth between them in a stable way -- nearby
points also approach them in an oscillating way.
This
happens just after C becomes larger than 3, (as we will see with Newton's
Method) at the fixed point attractor 2/3, and is called a period-doubling
bifurcation. As C increases towards 4, there is a cascade of period-doubling
bifurcations giving rise to stable orbits of period 4, 8, 16, 32, and so on.
As
we increase the values of C, this bifurcation behavior continues until the
values of C arrive at the threshold of chaos (just after 3.6) where
stable periodic orbits disappear for a while and points wander in a seemingly
random (chaotic) fashion all over [0,1] -- except for the rare points that
are exactly on unstable periodic orbits. Some time after that, for example
when C = 3.84 we see a periodic orbit of period 3 !
This
results from another sort of bifurcation, called a tangent bifurcation, and
it is accompanied by orbits of all odd periods, until finally, the whole scenario
dissolves into unregulated chaotic behavior. The following "bifurcation
diagram" from Dr. Samad Mortabit's excellent Mathwright Microworld: Dynamical
Systems Primer shows the itinerary of bifurcations through the threshold
of chaos and explains this fascinating behavior in much more detail than we
can here. The horizontal coordinate measures C values in [0, 4] and the vertical
coordinate measures x values in [0,1].
Exploration: The logistic map and bifurcation
Let us
experiment with bifurcation of the logistic map starting with a fixed parameter
value, say .
For that, go to the Recursive Sequences page. Click the table of contents
button 
and select Recursive Sequences.
Change the a(k) := field to 2*a(k-1)*(1-a(k-1)) and the Initial values fields to 0.7
to set the parameter C to 2 .
Now,
press 
. You will see:
which shows convergence to by the 7th
step. In this example, for C = 2, is a stable
(fixed) point attractor.
Now,
let us look at another parameter value. For example for C = 7/2 there is a
stable periodic orbit of order 4.
To
see this, change the recursion to 3.5*a(k-1)*(1-a(k-1))
and do 100 steps this time: 
then, press Reset, then Iterate!
You will see that the sequence has settled into an orbit of period 4:
89 : 0.382819683017324
90 : 0.826940706591438
91 : 0.500884210307217
92 : 0.874997263602464
93 : 0.382819683017324
94 : 0.826940706591438
95 : 0.500884210307217
96 : 0.874997263602464
97 : 0.382819683017324
98 : 0.826940706591438
99 : 0.500884210307217
100 : 0.874997263602464
Experiment
with other examples here if you like. We will show below that the behavior
of this logistic map is exactly reproduced by Newton's method when we work
with a certain class of parametrized functions. In precise terms, the Newton's
method iteration for this class of functions is conjugate to (identical with)
the logistic iteration for the class of functions just described. Try the
parameter 3.84 which is well within the "chaos" range.
Exploration: Newton's Method and chaos
Now let
us return to Newton's Method. Return to the Newton's Method and Chaos
page. Click the table of contents button
and select Newton's Method and Chaos.
The equation
we will attempt to solve is
The control
panel initially looks like this:
The equation we are using is
with the parameter C set to 3.84. We will explain
later how we calculate such a function and its derivative. For now we observe
that it has a single solution (approximately 0.73958333333333333333) on the
interval 
.
We cannot graph it, because it is complex valued, as we will discuss later,
but the formal Newton recursion is still defined in 
away from the solution. We choose an initial value x = 0.7, although
any other would do.
Now
press
and you will see:
If
we take 1000 steps we will see that the orbit oscillates stably among 3 points.
992
: 0.959447444244211
993
: 0.149406896553456
994
: 0.488004387132369
995
: 0.95944744424421
996
: 0.149406896553456
997
: 0.48800438713237
998
: 0.959447444244211
999
: 0.149406896553456
1000
:
0.488004387132369
These are (to 15 place precision)
0.959447444244211
0.149406896553456
0.488004387132369
We say that
there is a stable orbit of order 3, and we will arrive there from essentially
any initial point (not just 0.7). This is odd behavior for Newton's Method.
To see another example of this strange behavior, let us look at the equation
|
|
|
defined when 
with the solution 
. If our first approximation 
then the next step of Newton's Method gives
(The recursive sequence started
at any 
defined by 
is called a "logistic map" as we saw.)
Now, however, notice that 
,
so f is not defined at 
!
But if we allow f to assume
imaginary values, then the calculation above shows that this formal extension
of Newton's Method takes any real number 
to the real number 
where 
.
The
function we work with on this page has a parameter C:
To
see this example, change the parameter value initially set to 3.84
to 3
so we have the function 
. Next, be sure to press 
after each iteration, then press Iterate .
Now
you will see:
The values are oscillating between roughly 0.646 and 0.685.
They are actually converging very, very slowly to the solution 
as the following picture, that shows 1000 steps indicates:
Now,
change the C parameter to 3.1. 
and press
, then press
. You see
The
sequence is not converging to the solution 
.
Even after 100 steps, it is clearly oscillating between 0.7645665199
and 0.5580141252. If we continue to 1000 steps, we will see that the
oscillation is quite stable and has settled down (to within 15 place accuracy)
to the values: 0.764566519958594 and 0.558014125202696
This behavior is quite different from the lazy convergence for parameter value 3. It is called a bifurcation in behavior from convergence at 3 to a solution to stable oscillation around one at 3.1. Experiment!
We
cannot visualize this on the Newton's Method page, because our function f
now takes imaginary values and we cannot graph them. But since the recursion
only gives real values, we can view those here.
If
we set C to 4, however we will have the function
|
|
|
Here, we do not need an extension to a complex-valued function
to visualize the Newton Method iteration. The graph of this function on 
is pictured below.
Notice
that it has a vertical tangent at the solution, so Newton's Method is not
guaranteed to converge. The Newton's Method recursion in any case stays entirely
in the real domain for 
, but it has the interesting property that it is chaotic. It does not
settle down to the solution 
,
nor does it oscillate about one. This is so for almost any starting point
that you are able to set on a computer. If you start at 
, you will get a division by 0 error because of the vertical tangent there.
Before we look at the graphical representation of this recursion, try it out.
Set
the parameter value to 
: 
and set the initial value of x
to 0.8
. Press Reset, then Iterate, and you see:
The first few values are, for future reference:
1 : 0.8
2
: 0.639999999999999
3
: 0.9216
4
: 0.289013759999999
5
: 0.821939226122649
6
: 0.585420538734199
7
: 0.970813326249436
8
: 0.113339247303766
9
: 0.401973849297529
10
: 0.961563495113825
Remembering
to press Reset:
each time, try different initial values for 
,
and try more steps (up to 1000) and you will see similar seemingly random
wandering.
Now,
let's watch this process on the Newton's Method page. Click the table
of contents button
and select Newton's Recursive Method.
In
the upper right hand corner of the page, you see the buttons:
We
use these buttons for the experiment. First, set the start point to 0.8
You do not
have to change 
since it will not be used. Press Graph chaos example in the cluster
You see the first step:
The
start point and its value are reported in the upper left MathEdit.
Now,
press the Next Step button next to the one just used a few times to
watch the recursion:
Notice
that the itinerary reported in the upper left MathEdit is the same as was
reported in the last experiment above:
