Transcript Linear Iteration

Iteration,
the Julia Set,
and the Mandelbrot Set
Iteration Terminology
• Iteration – to repeat a process over and over.
• Iteration rule – the process that will be repeated
over and over. (Can be numerical or geometric)
• Seed – the place to begin the iteration .
• Orbit of the iteration rule – the list of numbers or
geometric figures obtained by successively applying
the iteration rule to the output of the previous
iteration.
Linear Iteration
A linear iteration rule is an iteration rule of the form
x → Ax + B where A and B are constants.
Linear Iteration
1
Iteration rule: x → x – 2
2
Seed: 0
Applying the iteration rule produces the following orbit.
0 → –2 → –3 → –3.5 → –3.75 → –3.875 → –3.9375 → …
The numbers in the orbit are getting closer and closer
to –4.
The fate of this orbit is: It approaches –4.
Linear Iteration
The seed of an iteration rule is denoted x0, the next
term in the iteration is x1, then x2, x3, and so on.
For the orbit
0 → –2 → –3 → –3.5 → –3.75 → …
x0 = 0, x1 = –2, x2 = –3, x3 = –3.5, and so on.
Linear Iteration
1
Iteration rule: x → x – 2
2
Seed: x0 = –4
The orbit is
–4 → –4 → –4 → –4 → –4 → …
The orbit stays constant at –4. The number –4 is called
a fixed point for this iteration rule.
Linear Iteration
The fixed point can be determined by solving the
equation x = Ax + B .
Linear Iteration
1
Iteration rule: x → x – 2
2
Seed: x0 = 5
The orbit is
5 → 0.5 → –1.75 → –2.875 → –3.4375 → –3.71875 →
–3.859375 → …
The orbit of this seed also approaches –4.
The orbit of any seed will approach –4 for this iteration
rule.
Linear Iteration
Iteration rule: x → 2x + 1
Seed: x0 = 0
The orbit is
0 → 1 → 3 → 7 → 15 → 31→ 63 → …
The numbers in this orbit grow larger and larger. This
orbit tends to infinity.
Linear Iteration
With the iteration rule x → 2x + 1, the orbit of x0 = –2
tends to (negative) infinity since the orbit is
–2 → –3 → –5 → –9 → –17 → –33 → …
The orbit of x0 = –1 is fixed under this iteration rule
since x1 = –1.
Linear Iteration
For the iteration rule x → –2x, 0 is a fixed point. All
other orbits eventually alternate between large positive
and large negative values.
The orbit of x0 = 2 under this rule begins
2 → –4 → 8 → –16 → 32 → –64 → 128→ –256 → …
This orbit tends to positive and negative infinity.
Linear Iteration
Orbits may also cycle. The orbit of x0 = 4 for the linear
iteration rule x → –x + 2 is
4 → –2 → 4 → –2 → 4 → –2 → 4 → …
This orbit is a cycle of period 2 since the orbit repeats
every second iteration.
Types of Fixed Points
1
An earlier iteration rule we looked at was x → x – 2.
2
We said the fixed point for this rule was –4.
When the seed x0 = 5 was used, the orbit was
5 → 0.5 → –1.75 → –2.875 → –3.4375 → –3.71875 →
–3.859375 → …
This orbit tends to –4.
The orbit of 0 also tended to –4.
Types of Fixed Points
1
For the iteration rule x → x – 2 , –4 is called an
2
attracting fixed point.
The fixed point for the linear iteration rule x → Ax + B is
attracting if all other orbits tend to the fixed point
under iteration.
Types of Fixed Points
The fixed point of the iteration rule x → 2x + 1 is –1.
The orbit of x0 = 0 tended to infinity.
The orbit of x0 = –2 tended to (negative) infinity.
The fixed point –1 is called a repelling fixed point.
A fixed point for which all other orbits tend to move
away from under iteration is a repelling fixed point.
Types of Fixed Points
The linear iteration rule x → –x + 2 has a fixed point at
x0 = 1, but it is neither attracting nor repelling.
The orbit of x0 = 4 is
4 → –2 → 4 → –2 → 4 → –2 → 4 → …
The orbit of x0 = 7 is
7 → –5 → 7 → –5 → 7 → –5 → 7 → …
Types of Fixed Points
If we choose any other seed x0 for the iteration rule
x → –x + 2 then the orbit is
x0 → –x0 + 2 → –(–x0 + 2 ) + 2 = x0.
This orbit begins to cycle after two iterations. This orbit
is a cycle of period 2. The fixed point is neither
attracting nor repelling, it is a neutral fixed point
Quadratic Iteration
A quadratic iteration rule is an iteration rule of the form
x → x2 + c where c is a constant.
The fate of the orbit of x → x2 + c depends on the seed
and the parameter c.
Quadratic Iteration
The orbit of zero, under x → x2 + c, has different fates
for different values of c.
When c = 1, the orbit of 0 tends to infinity:
0 → 1 → 2 → 5 → 26 → 677 → …
When c = 0, the orbit remains fixed at 0:
0→0→0→0→…
When c = −1, the orbit cycles with period 2:
0 → −1 → 0 → −1 → …
When c = −2, the orbit of 0 is eventually fixed:
0 → −2 → 2 → 2 → 2 → …
Quadratic Iteration
The orbit of 0 is called the critical orbit of the iteration
rule x → x2 + c.
The value 0 is special because the minimum value of
y = x2 + c occurs at x = 0.
Quadratic Iteration
Fixed points can also be determined algebraically for
quadratic iteration rules.
To find the fixed points, solve the equation
x = x2 + c
Quadratic Iteration
Solving the equation x = x2 + c
is equivalent to determining
the place where the graph of
y = x2 + c crosses the diagonal
y = x.
The behavior near a fixed
point can be determined
graphically.
fixed point
Quadratic Iteration
The initial seed is a point on
the line y = x (or x-axis). The
result of an iteration is the
y-value on y = x2 + c
associated with that x-value.
That y-value becomes the
next x-value to be iterated.
Quadratic Iteration
A repelling fixed point
y = x2 + c
y=x
Quadratic Iteration
An attracting fixed point
y=
x2
+c
y=x
Quadratic Iteration
y = x2 + 0.25
The graph of y = x2 + 0.25
has a fixed point at x = 0.5.
Appears to be
attracting from
the left
y=x
Appears to be
repelling to
the right
The fixed point 0.5 is
neither attracting nor
repelling, it is a neutral
fixed point
Quadratic Iteration
Orbits of a quadratic iteration may be attracted to a
fixed point or they may be repelled from it. Orbits may
also cycle or tend to cycles with different periods.
Quadratic Iteration
Finding cycles for quadratic iterations algebraically is
usually extremely difficult or impossible.
To find the 2-cycle for the rule x → x2 + c, iterate twice
x → x2 + c → (x2 + c)2 + c
And then solve the equation
x = (x2 + c)2 + c
To find the 3-cycle, iterate three times and solve the
resulting equation.
Complex Linear Iteration
• A complex number is a number of the form a + b𝑖.
• The magnitude of a complex number is the distance
of the complex number from the origin.
The magnitude of a + b𝑖 is
a2
2
+b
• The polar angle of a complex number is the angle
formed by the positive x-axis and line connecting
the complex number to the origin.
a + b𝑖
θ
Complex Linear Iteration
If a + b𝑖 is a complex number with polar angle θ and
magnitude r, then
a = r cos θ
b = r sin θ
a + b𝑖 = r cos θ + 𝑖r sin θ = r(cos θ + 𝑖 sin θ)
This is the polar representation of the complex number
a + b𝑖.
Complex Linear Iteration
For two complex numbers a + b𝑖 and c + d𝑖:
(a + b𝑖) + (c + d𝑖) = (a + c) + (b + d)𝑖
e(a + b𝑖) = ea + eb𝑖
If a + b𝑖 = r1(cos θ1 + 𝑖sin θ1)
and c + d𝑖 = r2(cos θ2 + 𝑖sin θ2)
(a + b𝑖)(c + d𝑖) = r1r2(cos θ1cos θ2 - sin θ1 sin θ2)
+ 𝑖 r1r2(sin θ1cos θ2 + sin θ2 cos θ1)
(a + b𝑖)(c + d𝑖) = r1r2(cos (θ1+θ2) + 𝑖(sin (θ1+θ2))
Complex Linear Iteration
(a + b𝑖)(c + d𝑖) = r1r2(cos (θ1+θ2) + 𝑖(sin (θ1+θ2))
To multiply two complex numbers geometrically, add
their polar angles and multiply their magnitudes.
Complex Linear Iteration
Iteration rule: x → 2x
Seed: x0 = 1 + 𝑖
The orbit is
1 + 𝑖 → 2 + 2𝑖 → 4 + 4𝑖 → 8 + 8𝑖 → 16 + 16𝑖 → …
The orbit moves farther and farther away from the
origin. This orbit tends to infinity.
4 + 4𝑖
2 + 2𝑖
1+𝑖
Complex Linear Iteration
Iteration rule: x → 𝑖x
Seed: x0 = a + b𝑖
The orbit is
a + b𝑖 → –b + a𝑖 → –a – b𝑖 → b – a𝑖 → a + b𝑖 → …
Which is a 4-cycle in the complex plane.
(Magnitude is the same, but each point is rotated 90°)
–b + a𝑖
a + b𝑖
–a – b𝑖
b – a𝑖
Complex Linear Iteration
1 1
Iteration rule: x → ( + 𝑖) x
2 2
Seed: 1
1 1
1
1 1
1
1→ + 𝑖→ 𝑖→− + 𝑖→− →…
2 2
2
4 4
4
This orbit tends to 0.
1 1
− + 𝑖
4 4
1
𝑖
2
1 1
+ 𝑖
2 2
1
Complex Linear Iteration
Complex iteration rule: x → Ax where A = a + b𝑖
If the magnitude of a + b𝑖 is greater than 1, then when
we multiply a number by a + b𝑖, the resulting complex
number has greater magnitude.
The orbit of any nonzero number moves further and
further from the origin and these orbits tend to infinity.
The origin is a repelling fixed point for this iteration
rule.
Complex Linear Iteration
Complex iteration rule: x → Ax where A = a + b𝑖
If the magnitude of a + b𝑖 is less than 1, then each
successive multiplication results in a complex number
with smaller magnitude.
The orbit of any nonzero number moves closer and
closer to the origin and these orbits tend to 0.
The origin is an attracting fixed point for this iteration
rule.
Complex Linear Iteration
Complex iteration rule: x → Ax where A = a + b𝑖
If the magnitude of a + b𝑖 is equal to 1, then the
magnitude of the seed is not changed. Multiplication
rotates the given point by the polar angle of a + b𝑖.
The origin is a neutral fixed point for this iteration rule.
The Squaring Rule
Iteration rule: x → x2
y = x2
y=x
The Squaring Rule
Iteration rule: x → x2
• If x0 = 0 or 1, the orbit is fixed
• If 0 < | x0| < 1, the orbit tends to 0
• If | x0| >1, the orbit goes to infinity
• If x0 = –1, the orbit is eventually fixed at 1.
The Squaring Rule
Iteration rule: x → x2
Seed: x0 = r(cos θ + 𝑖 sin θ)
x0 = r(cos θ + 𝑖 sin θ)
x1 = r2(cos 2θ + 𝑖 sin 2θ)
x2 = r4(cos 4θ + 𝑖 sin 4θ)
x3 = r8(cos 8θ + 𝑖 sin 8θ)
..
.
xn = r2n(cos 2nθ + 𝑖 sin 2nθ)
The Squaring Rule
Complex squaring iteration does not differ very much
from the real case for most seeds.
If r > 1, the orbit tends to infinity since r2n will get larger
and larger.
If r < 1, the orbit tends to 0 since r2n will get very small.
If r = 1, the entire orbit lies on the circle of radius 1.
The Julia Set
Orbits can be categorized into two types: the orbit
tends to infinity or it does not.
If the orbit tends to infinity, the orbit “escapes.”
The collection of all seeds that do not escape is called a
filled Julia set.
For the squaring iteration, the filled Julia set consists of
all those seeds on and inside the circle of radius 1
centered at the origin.
The Julia Sets
The filled Julia set
for the squaring
iteration.
The Julia Set
Seeds inside the circle of radius 1 tend to the attracting
fixed point at the origin and those that lie on the circle
have orbits that stay on the circle forever.
The circle of radius 1 is called the Julia set for this
iteration rule.
The Julia set is the boundary between the seeds whose
orbits escape and those whose orbits do not.
Julia Sets of Quadratic Iterations
Instead of using the squaring iteration rule, x → x2, the
more general quadratic iteration rule, x → x2 + c, can be
used.
Julia Sets of Quadratic Iterations
It is important to be able to determine the fate of an
orbit. If the orbit does not escape, it is in the filled Julia
set. If it does escape, it is not in the set.
An orbit will escape under the iteration rule x → x2 + c
if its magnitude ever exceeds an escape value.
The escape value is the larger of 2 and the magnitude
of the given value of c.
Julia Sets of Quadratic Iterations
Suppose that xn is a complex number and denotes the
nth point along an orbit.
According to the Triangle Inequality
| xn +1| = | xn2 + c | ≥ | xn|2 - |c|
If | xn| > 2, then
| xn|2 - |c| > 2| xn |- |c|.
And if | xn| > |c|, then
2| xn|- |c| > | xn|.
Julia Sets of Quadratic Iterations
So if | xn | > 2 and | xn | > |c|, then | xn+1| > | xn |.
The sequence is continuously increasing and the orbit
of the seed must escape to infinity.
Therefore, the escape value is the larger of 2 and the
magnitude of c.
Julia Sets of Quadratic Iterations
The first step in computing a filled Julia set is to
determine the escape value.
Next, divide the complex plane into a grid of complex
numbers. Each point on the grid represents a seed.
Compute the orbit of each grid point. If a point on an
orbit ever has a magnitude greater than the escape
value, then this orbit tends to infinity and is not in the
filled Julia set. If that point does not tend to infinity it
is in the set.
Julia Sets of Quadratic Iterations
Compute the filled Julia set by hand for
x → x2 − 1
Escape value = 2
Julia Sets of Quadratic Iterations
On a TI-83:
Enter the seed, then press enter. (For complex seeds,
use 𝑖 on the bottom row.)
Press 2nd ANS x2 − 1 ENTER (This gives x1)
Pressing enter again gives x2.
Continue pressing enter until the magnitude of the
answer is > 2 or you have pressed enter 10 times.
If the orbit does not exceed the escape value, plot that
point.
Draw Julia Set
Julia Sets of Quadratic Iterations
c = –1
Julia Sets of Quadratic Iterations
c = –0.75
Julia Sets of Quadratic Iterations
c = 0.25
Julia Sets of Quadratic Iterations
c = –0.12 + 0.75𝑖
This is sometimes
called the fractal
rabbit.
Julia Sets of Quadratic Iterations
This is a fractal
because it is self
similar.
Julia Sets of Quadratic Iterations
c = 0.27 + 0.53𝑖
Julia Sets of Quadratic Iterations
c = –0.75 + 0.2𝑖
This is fractal dust. Under more iterations, the set of
points will becomes smaller and smaller, but there are
some points that will never escape.
Julia Sets of Quadratic Iterations
The orbit of 0 is called the critical orbit and it plays a
role in determining the shape of the filled Julia set.
Julia Sets of Quadratic Iterations
x → x2 – 0.12 + 0.75𝑖
x0 = 0
x1 = –0.1200 + 0.7500𝑖
x2 = –0.6681 + 0.5700 𝑖
x3 = –0.0015 + 0.0116 𝑖
x4 = – 0.1201 + 0.7500𝑖
x5 = –0.6680 + 0.5698 𝑖
x6 = 0.0016 + 0.0113 𝑖
x7 = –0.1201 + 0.7500𝑖
The orbit tends to a 3-cycle.
Julia Sets of Quadratic Iterations
The cycle gives the number
of pieces in the set.
–0.1201 + 0.7500𝑖
–0.6680 + 0.5698 𝑖
0.0016 + 0.0113 𝑖
Julia Sets of Quadratic Iterations
Julia Sets of Quadratic Iterations
If the orbit of 0 does not cycle, but escapes to infinity,
then the corresponding filled Julia set for that c-value is
fractal dust.
When the orbit of 0 does not go to infinity, the filled
Julia set is one connected piece, and its boundary, the
Julia set, is often a fractal.
The Mandelbrot Set
The set of all c-values for which the orbit of 0 does not
escape is called the Mandelbrot set.
It is the set of all c-values for which the corresponding
Julia set is connected.
It is the set of c-values for which the corresponding
orbit of 0 under x → x2 + c does not go to infinity.
The Mandelbrot Set
The Mandelbrot Set
This set has a very intricate geometry and there is a
connection between the position on the Mandelbrot
set and the shape of the Julia set, as well as the fate of
the orbit of 0.
The Mandelbrot Set
The Mandelbrot Set
Rather than studying the Mandelbrot set itself, quite
often the region very near to the set is studied.
Here, the orbit of 0 escapes to infinity. Sometimes,
though, these orbits escape slowly. The number of
iterations needed for the orbit to surpass some value is
counted and a color is assigned to the point based on
that value. The results can be quite aesthetically
pleasing.
The Mandelbrot Set
for (cr = left; cr<=right; cr+=step)
{
for (ci = top; ci<=bottom; ci+=step)
{
zr = zi = zro = n = 0;
while (n <= nmax && (zr * zr + zi * zi)< escape_value)
{
zr = zr * zr - zi * zi + cr;
zi = 2 * zi * zro + ci;
zro = zr;
n++;
}
if (n == nmax + 1)
color = 0;
else
color = colors[n];
SetPixel(hdc, hcenter+cr*scale, vcenter+ci*scale, color);
}
}
For more information on the Julia set and the
Mandelbrot set, check out the following website.
http://math.bu.edu/DYSYS/explorer/index.html
References
Devaney, R. & Choate, J. (2000). Chaos: A tool kit of
dynamics activities. Emeryville, CA: Key Curriculum
Press.
Devaney, R. (2000). The Mandelbrot and Julia sets: A
tool kit of dynamics activities. Emeryville, CA: Key
Curriculum Press.
All graphics produced by Ron Koehn.