I want to learn about fractals. What should I read first?
"Chaos" is a good book to get a general overview and history. "Fractals Everywhere" is a textbook on fractals that describes what fractals are and how to generate them, but it requires knowing intermediate analysis. "Chaos, Fractals, and Dynamics" is also a good start. There is a longer book list at the end of this file (see "What are some general references?").
Also, use networked resources.
What is a fractal? What are some examples of fractals?
A fractal is a rough or fragmented geometric shape that can be subdivided in parts, each of which is (at least approximately) a reduced-size copy of the whole. Fractals are generally self-similar and independent of scale.
There are many mathematical structures that are fractals; e.g. Sierpinski triangle, Koch snowflake, Peano curve, Mandelbrot set, and Lorenz attractor. Fractals also describe many real-world objects, such as clouds, mountains, turbulence, and coastlines, that do not correspond to simple geometric shapes.
Benoit Mandelbrot gives a mathematical definition of a fractal as a set for which the Hausdorff Besicovich dimension strictly exceeds the topological dimension. However, he is not satisfied with this definition as it excludes sets one would consider fractals.
According to Mandelbrot, who invented the word: "I coined 'fractal' from the Latin adjective 'fractus'. The corresponding Latin verb 'frangere' means 'to break' to create irregular fragents. It is therefore sensible - and how appropriate for our needs! - that, in addition to 'fragmented' (as in 'fraction' or 'refraction'), 'fractus' should also mean 'irregular', both meanings being preserved in 'fragment'."
-- "The Fractal Geometry of Nature", page 4
What is chaos?
Chaos is apparently unpredictable behavior arising in a deterministic system because of great sensitivity to initial conditions. Chaos arises in a dynamical system if two arbitrarily close starting points diverge exponentially, so that their future behavior is eventually unpredictable.
Weather is considered chaotic since arbitrarily small variations in initial conditions can result in radically different weather later. This may limit the possibilities of long-term weather forecasting. (The canonical example is the possibility of a butterfly's sneeze affecting the weather enough to cause a hurricane weeks later.)
Devaney defines a function as chaotic if it has sensitive dependence on initial conditions, it is topologically transitive, and periodic points are dense. In other words, it is unpredictable, indecomposable, and yet contains regularity.
Allgood and Yorke define chaos as a trajectory that is exponentially unstable and neither periodic or asymptotically periodic. That is, it oscillates irregularly without settling down.
What is fractal dimension? How is it calculated?
A common type of fractal dimension is the Hausdorff-Besicovich Dimension, but there are several different ways of computing fractal dimension.
Roughly, fractal dimension can be calculated by taking the limit of the quotient of the log change in object size and the log change in measurement scale, as the measurement scale approaches zero. The differences come in what is exactly meant by "object size" and what is meant by "measurement scale" and how to get an average number out of many different parts of a geometrical object. Fractal dimensions quantify the static *geometry* of an object.
For example, consider a straight line. Now blow up the line by a factor of two. The line is now twice as long as before. Log 2 / Log 2 = 1, corresponding to dimension 1. Consider a square. Now blow up the square by a factor of two. The square is now 4 times as large as before (i.e. 4 original squares can be placed on the original square). Log 4 / log 2 = 2, corresponding to dimension 2 for the square. Consider a snowflake curve formed by repeatedly replacing ___ with _/\_, where each of the 4 new lines is 1/3 the length of the old line. Blowing up the snowflake curve by a factor of 3 results in a snowflake curve 4 times as large (one of the old snowflake curves can be placed on each of the 4 segments _/\_). Log 4 / log 3 = 1.261... Since the dimension 1.261 is larger than the dimension 1 of the lines making up the curve, the snowflake curve is a fractal.
What is topological dimension?
Topological dimension is the "normal" idea of dimension; a point has topological dimension 0, a line has topological dimension 1, a surface has topological dimension 2, etc.
For a rigorous definition:
A set has topological dimension 0 if every point has arbitrarily small neighborhoods whose boundaries do not intersect the set.
A set S has topological dimension k if each point in S has arbitrarily small neighborhoods whose boundaries meet S in a set of dimension k-1, and k is the least nonnegative integer for which this holds.
What is a strange attractor?
A strange attractor is the limit set of a chaotic trajectory. A strange
attractor is an attractor that is topologically distinct from a periodic orbit
or a limit cycle. A strange attractor can be considered a fractal attractor.
An example of a strange attractor is the Henon attractor.
Consider a volume in phase space defined by all the initial conditions a
system may have. For a dissipative system, this volume will shrink as the
system evolves in time (Liouville's Theorem). If the system is sensitive to
initial conditions, the trajectories of the points defining initial
conditions will move apart in some directions, closer in others, but
there will be a net shrinkage in volume. Ultimately, all points will
lie along a fine line of zero volume. This is the strange attractor. All
initial points in phase space which ultimately land on the attractor
form a Basin of Attraction. A strange attractor results if a system is
sensitive to initial conditions and is not conservative.
Note: While all chaotic attractors are strange, not all strange attractors
are chaotic.
What is the Mandelbrot set?
The Mandelbrot set is the set of all complex c such that iterating z -> z^2+c does not go to infinity (starting with z=0).
Click here for an image of the Mandelbrot set.
How is the Mandelbrot set actually computed?
The basic algorithm is:
For each pixel c, start with z=0. Repeat z=z^2+c up to N times, exiting if the magnitude of z gets large. If you finish the loop, the point is probably inside the Mandelbrot set. If you exit, the point is outside and can be colored according to how many iterations were completed. You can exit if |z|>2, since if z gets this big it will go to infinity. The maximum number of iterations, N, can be selected as desired, for instance 100. Larger N will give sharper detail but take longer.
Why do you start with z=0?
Zero is the critical point of z^2+c, that is, a point where d/dz (z^2+c) = 0. If you replace z^2+c with a different function, the starting value will have to be modified. E.g. for z->z^2+z+c, the critical point is given by 2z+1=0, so start with z=-1/2. In some cases, there may be multiple critical values, so they all should be tested.
Critical points are important because by a result of Fatou: every attracting cycle for a polynomial or rational function attracts at least one critical point. Thus, testing the critical point shows if there is any stable attractive cycle.
Note that you can precompute the first Mandelbrot iteration by starting with z=c instead of z=0, since 0^2+c=c.
What are the bounds of the Mandelbrot set? When does it diverge?
The Mandelbrot set lies within |c|<=2. If |z| exceeds 2, the z sequence diverges. Proof: if |z|>2, then |z^2+c|>= |z^2|-|c|> 2|z|-|c|. If |z|>=|c|, then 2|z|-|c|> |z|. So, if |z|>2 and |z|>=c, |z^2+c|>|z|, so the sequence is increasing. (It takes a bit more work to prove it is unbounded and diverges.) Also, note that |z1=c, so if |c|>2, the sequence diverges.
How can I speed up Mandelbrot set generation?
See the information on speed below: "How does Fractint achive its speed?"
What is the area of the Mandelbrot set?
Ewing and Schober computed an area estimate using 240,000 terms of the Laurent series. The result is 1.7274... However, the Laurent series converges very slowly, so this is a poor estimate. A project to measure the area via counting pixels on a very dense grid shows an area around 1.5066. (Contact mrob@world.std.com for more information.) Hill and Fisher used distance estimation techniques to rigorously bound the area and found the area is between 1.503 and 1.5701.
What can you say about the structure of the Mandelbrot set?
Most of what you could want to know is in Branner's article in "Chaos and Fractals: The Mathematics Behind the Computer Graphics".
Note that the Mandelbrot set in general is not strictly self-similar; the tiny copies of the Mandelbrot set are all slightly different, mainly because of the thin threads connecting them to the main body of the Mandelbrot set. However, the Mandelbrot set is quasi-self-similar. The Mandelbrot set is self-similar under magnification in neighborhoods of Misiurewicz points, however (e.g. -.1011+.9563i). The Mandelbrot set is conjectured to be self-similar around generalized Feigenbaum points (e.g. -1.401155 or -.1528+1.0397i), in the sense of converging to a limit set.
Is the Mandelbrot set connected?
The Mandelbrot set is simply connected. This follows from a theorem of Douady and Hubbard that there is a conformal isomorphism from the complement of the Mandelbrot set to the complement of the unit disk. (In other words, all equipotential curves are simple closed curves.) It is conjectured that the Mandelbrot set is locally connected, and thus pathwise connected, but this is currently unproved.
Connectedness definitions:
Connected: X is connected if there are no proper closed subsets A and B of X such that A union B = X, but A intersect B is empty. I.e. X is connected if it is a single piece.
Simply connected: X is simply connected if it is connected and every closed curve in X can be deformed in X to some constant closed curve. I.e. X is simply connected if it has no holes.
Locally connected: X is locally connected if for every point p in X, for every open set U containing p, there is an open set V containing p and contained in the connected component of p in U. I.e. X is locally connected if every connected component of every open subset is open in X.
Arcwise (or path) connected: X is arcwise connected if every two points in X are joined by an arc in X.
(The definitions are from "Encyclopedic Dictionary of Mathematics".)
What is the difference between the Mandelbrot set and a Julia set?
The Mandelbrot set iterates z^2+c with z starting at 0 and varying c. The Julia set iterates z^2+c for fixed c and varying starting z values. That is, the Mandelbrot set is in parameter space (c-plane) while the Julia set is in dynamical or variable space (z-plane).
What is the connection between the Mandelbrot set and Julia sets?
Each point c in the Mandelbrot set specifies the geometric structure of the corresponding Julia set. If c is in the Mandelbrot set, the Julia set will be connected. If c is not in the Mandelbrot set, the Julia set will be a Cantor dust.
How is a Julia set actually computed?
The Julia set can be computed by iteration similar to the Mandelbrot computation. The only difference is that the c value is fixed and the initial z value varies.
Alternatively, points on the boundary of the Julia set can be computed quickly by using inverse iterations. This technique is particularly useful when the Julia set is a Cantor Set. In inverse iteration, the equation z1 = z0^2+c is reversed to give an equation for z0: z0 = +- sqrt(z1-c). By applying this equation repeatedly, the resulting points quickly converge to the Julia set boundary. (At each step, either the postive or negative root is randomly selected.) This is a nonlinear iterated function system. In pseudocode:
z = 1 (or any value)
loop
if (random number < 0.5) then
z = sqrt(z-c)
else
z = -sqrt(z-c)
endif
plot z
end loop
What are some Julia set facts?
The Julia set of any rational map of degree greater than one is perfect (hence in particular uncountable and nonempty), completely invariant, equal to the Julia set of any iterate of the function, and also is the boundary of the basin of attraction of every attractor for the map.
How does complex arithmetic work?
It works mostly like regular algebra with a couple additional formulas:
(note: a,b are reals, x,y are complex, i is the square root of -1)
Powers of i: i^2 = -1
Addition: (a+i*b)+(c+i*d) = (a+c)+i*(b+d)
Multiplication: (a+i*b)*(c+i*d) = a*c-b*d + i*(a*d+b*c)
Division: (a+i*b)/(c+i*d) = (a+i*b)*(c-i*d)/(c^2+d^2)
Exponentiation: exp(a+i*b) = exp(a)(cos(b)+i*sin(b))
Sine: sin(x) = (exp(i*x)-exp(-i*x))/(2*i)
Cosine: cos(x) = (exp(i*x)+exp(-i*x))/2
Magnitude: |a+i*b= sqrt(a^2+b^2)
Log: log(a+i*b) = log(|a+i*b|)+i*arctan(b/a) (Note: log is multivalued.)
Log (polar coordinates): log(r*e^(i*theta)) = log(r)+i*theta
Complex powers: x^y = exp(y*log(x))
DeMoivre's theorem: x^a = r^a * [cos(a*theta) + i * sin(a*theta)]
More details can be found in any complex analysis book.
How does quaternion arithmetic work?
Quaternions have 4 components (a+ib+jc+kd) compared to the two of complex numbers. Operations such as addition and multiplication can be performed on quaternions, but multiplication is not commutative.
Quaternions satisfy the following rules:
i^2 = j^2 = k^2 = -1
ij = -ji = k
jk = -kj = i
ki = -ik = j
What is the logistic equation?
It models animal populations. The equation is x -> c*x*(1-x), where x is the population (between 0 and 1) and c is a growth constant. Iteration of this equation yields the period doubling route to chaos. For c between 1 and 3, the population will settle to a fixed value. At 3, the period doubles to 2; one year the population is very high, causing a low population the next year, causing a high population the following year. At 3.45, the period doubles again to 4, meaning the population has a four year cycle.
The period keeps doubling, faster and faster, at 3.54, 3.564, 3.569, and so forth. At 3.57, chaos occurs; the population never settles to a fixed period. For most c values between 3.57 and 4, the population is chaotic, but there are also periodic regions. For any fixed period, there is some c value that will yield that period. See "An Introduction to Chaotic Dynamical Systems" for more information.
What is Feigenbaum's constant?
In a period doubling cascade, such as the logistic equation, consider the parameter values where period-doubling events occur (e.g. r[1]=3, r[2]=3.45, r[3]=3.54, r[4]=3.564...). Look at the ratio of distances between consecutive doubling parameter values; let delta[n] = (r[n+1]-r[n])/(r[n+2]-r[n+1]). Then the limit as n goes to infinity is Feigenbaum's (delta) constant.
Based on independent computations by Jay Hill and Keith Briggs, it has the value 4.669201609102990671853... Note: several books have published incorrect values starting 4.66920166...; the last repeated 6 is a typographical error.
The interpretation of the delta constant is as you approach chaos, each periodic region is smaller than the previous by a factor approaching 4.669... Feigenbaum's constant is important because it is the same for any function or system that follows the period-doubling route to chaos and has a one-hump quadratic maximum. For cubic, quartic, etc. there are different Feigenbaum constants.
Feigenbaum's alpha constant is not as well known; it has the value 2.502907875095. This constant is the scaling factor between x values at bifurcations. Feigenbaum says, "Asymptotically, the separation of adjacent elements of period-doubled attractors is reduced by a constant value [alpha] from one doubling to the next". If d[n] is the algebraic distance between nearest elements of the attractor cycle of period 2^n, then d[n]/d[n+1] converges to -alpha.
What is an iterated function system (IFS)?
If a fractal is self-similar, you can specify mappings that map the whole onto the parts. Iteration of these mappings will result in convergence to the fractal attractor. An IFS consists of a collection of these (usually affine) mappings. If a fractal can be described by a small number of mappings, the IFS is a very compact description of the fractal. An iterated function system is By taking a point and repeatedly applying these mappings you end up with a collection of points on the fractal. In other words, instead of a single mapping x -> F(x), there is a collection of (usually affine) mappings, and random selection chooses which mapping is used.
For instance, the Sierpinski triangle can be decomposed into three self-similar subtriangles. The three contractive mappings from the full triangle onto the subtriangles forms an IFS. These mappings will be of the form "shrink by half and move to the top, left, or right".
Iterated function systems can be used to make things such as fractal ferns and trees and are also used in fractal image compression. "Fractals Everywhere" by Barnsley is mostly about iterated function systems.
The simplest algorithm to display an IFS is to pick a starting point, randomly select one of the mappings, apply it to generate a new point, plot the new point, and repeat with the new point. The displayed points will rapidly converge to the attractor of the IFS.
What is the state of fractal compression?
Fractal compression is quite controversial, with some people claiming it doesn't work well, and others claiming it works wonderfully. The basic idea behind fractal image compression is to express the image as an iterated function system (IFS). The image can then be displayed quickly and zooming will generate infinite levels of (synthetic) fractal detail. The problem is how to efficiently generate the IFS from the image.
Barnsley, who invented fractal image compression, has a patent on fractal compression techniques (4,941,193). Barnsley's company, Iterated Systems Inc, has a line of products including a Windows viewer, compressor, magnifier program, and hardware assist board.
How can you make a chaotic oscillator?
Two references are:
1. T. S. Parker and L. O. Chua, Chaos: a tutorial for engineers,
"Proceedings IEEE" 75 (1987), pp. 982-1008.
2. "New Scientist", June 30, 1990, p. 37.
What are laboratory demonstrations of chaos?
Robert Shaw at UC Santa Cruz experimented with chaos in dripping taps. This is described in:
1. J. P. Crutchfield, Chaos, "Scientific American" 255, 6 (Dec. 1986), pp. 38-49.
2. I. Stewart, "Does God Play Dice? The Mathematics of Chaos", B. Blackwell, New York, 1989.
Two references to other laboratory demonstrations are:
1. K. Briggs, Simple Experiments in Chaotic Dynamics, "American Journal of Physics" 55, 12 (Dec 1987), pp. 1083-1089.
2. J. L. Snider, Simple Demonstration of Coupled Oscillations, "American Journal of Physics" 56, 3 (Mar 1988), p. 200.
What are L-systems?
A L-system or Lindenmayer system is a formal grammar for generating strings. (That is, it is a collection of rules such as replace X with XYX.) By recursively applying the rules of the L-system to an initial string, a string with fractal structure can be created. Interpreting this string as a set of graphical commands allows the fractal to be displayed. L-systems are very useful for generating realistic plant structures.
What is some information on fractal music?
One fractal recording is "The Devil's Staircase: Composers and Chaos" on the Soundprint label.
Some references, many from an unpublished article by Stephanie Mason, are:
1. R. Bidlack, Chaotic Systems as Simple (But Complex) Compositional Algorithms, "Computer Music Journal, Fall 1992.
2. C. Dodge, A Musical Fractal, "Computer Music Journal" 12, 13 (Fall 1988), p. 10.
How are fractal mountains generated?
Usually by a method such as taking a triangle, dividing it into 3 subtriangles, and perturbing the center point. This process is then repeated on the subtriangles. This results in a 2-d table of heights, which can then be rendered as a 3-d image.
One reference is:
1. M. Ausloos, "Proc. R. Soc. Lond. A" 400 (1985), pp. 331-350.
What are plasma clouds?
They are a Fractint fractal and are similar to fractal mountains. Instead of a 2-d table of heights, the result is a 2-d table of intensities. They are formed by repeatedly subdividing squares.
How can 3-D fractals be generated?
A common source for 3-D fractals is to compute Julia sets with quaternions instead of complex numbers. The resulting Julia set is four dimensional. By taking a slice through the 4-D Julia set (e.g. by fixing one of the coordinates), a 3-D object is obtained. This object can then be displayed using computer graphics techniques such as ray tracing.
What is Fractint?
Fractint is a very popular freeware (not public domain) fractal generator. There are DOS, Windows, OS/2, and Unix/X versions. The DOS version is the original version, and is the most up-to-date. There is a new Amiga version.
How does Fractint achieve its speed?
Fractint's speed (such as it is) is due to a combination of:
1. Using fixed point math rather than floating point where possible (huge improvement for non-coprocessor machine, small for 486's).
2. Exploiting symmetry of the fractal.
3. Detecting nearly repeating orbits, avoid useless iteration (e.g. repeatedly iterating 0^2+0 etc. etc.).
4. Reducing computation by guessing solid areas (especially the "lake" area).
5. Using hand-coded assembler in many places.
6. Obtaining both sin and cos from one 387 math coprocessor instruction.
7. Using good direct memory graphics writing in 256-color modes.
The first four are probably the most important. Some of these introduce errors, usually quite acceptable.
Where can I obtain software packages to generate fractals?
See our links page !
Where are fractal pictures archived?
See our links page !
What is complexity?
Emerging paradigms of thought encompassing fractals, chaos, nonlinear science, dynamic systems, self-organization, artificial life, neural networks, and similar systems comprise the science of complexity.
Several helpful online resources on complexity can be found at:
Institute for Research on Complexity
What are some general references on fractals and chaos?
See our links page !
|
; NeuesFenster.focus(); void''){kind=link}