Transcript x 0

Chaos
State-of-the-art
calculator,1974
(about $400)
State-of-the-art
calculator, 2013
(about $40)
How does the `solve’ function work?
Research (looking in the manual) shows that
it employs something called `the secant method’.
Using the secant method to solve f(x)=x3-1=0:
Guess a solution x0
Is it right?
Guess a second solution x1
Is it right?
Construct a third guess:
x2 =x1 - (x0-x1)/(f(x0)-f(x1))
(This is where the secant through the first two
points cuts the x axis)
Repeat indefinitely.
f(x)
x
Find the point(s) at which f(x)=0
f(x0)
x0
First guess: x0
f(x0)
x1
x0
f(x1)
Second guess: x1
x2
Draw the secant and locate x2
x1
x2
Draw another secant and locate x3
x3
Does this always work?
Showing the success of
the secant method for
many different pairs of
initial guesses:
x1
x0
Colour this point
according to how
long it takes to
get to the right
answer.
Complex Numbers
What is the solution to
x2 = -1?
Complex Numbers
-i
0
i
-i
-1
0
1
0
0
0
0
i
1
0
-1
Complex Numbers
i
 (0.5+i)
Complex Numbers
Now the equation
x3 - 1 = 0
has 3 roots:
x=1, x=0.5+√3i/2, x=0.5-√3i/2
Complex Numbers
The secant method doesn’t take us to the
complex roots unless our initial guesses are
complex.
But now our initial two guesses have four
components.
Complex Numbers
We flatten the tesseract by one of several
strategies:
1. Let x0 be 0, choose x1 freely.
Strategy 2:
Choose x0 freely, let x1 be very close to x0.
Newton’s Method
To find the roots of f(x) = 0, construct the series {xi}, where
xi+1 = xi – f(xi)/f/(xi)
(and x0 is a random guess)
Example:
f(x) = x3 -1, so f/(x) = 2x2
x0 = 2, so x1 = 2 –(23-1)/(2*22) = 2 – 7/8 = 1.125
and x2 = 1.125-(1.1253-1)/(2*1.1252) = 0.9575
Newton’s Method
f(x0)
x0
Newton’s Method
x0
x1
Newton’s Method
x0
f(x1)
x1
Newton’s Method
x2
x1
Apply Newton’s method to
z3-1=0
which in the complex plane has three
roots.
Let the x and y axes represent the real and
imaginary components of the initial guess.
Colour them according to which root they
reach, and when.
One more equation to solve by Newton’s
method:
(x+1)(x-1)(x+ß)=0
…where ß is our first guess.
We recognise the Mandelbrot set, which can also
be generated by a simpler process:
Repeat the calculation
zn = z2n-1+z0
until zn > 2 or you give up. Colour in the
complex point z=x+iy according to how
long this took.
Characteristics of Chaos
Two ingredients-- non-linearity and feedback -can give rise to chaos.
Chaos is governed by deterministic rules, yet
produces results that can be very hard to predict.
Images of chaotic processes can display a high
level of order, characterised by self-similarity.
When can chaos arise?
Trying to get two non-linear programs to converge:
x
y