💾 Archived View for tilde.team › ~smokey › fractal_compendium › faq › fractal-faq.gmi captured on 2023-11-04 at 12:05:43. Gemini links have been rewritten to link to archived content

View Raw

More Information

⬅️ Previous capture (2022-07-16)

-=-=-=-=-=-=-

Fractal FAQ

Notes/Preface

This FAQ is sourced from an old file belonging to a long defunct usenet community, sci.fractals . The file is a fossil age-wise and all the links were dead, but the core information contained is still suprisingly relevant and well put-together. I have done my best to give this FAQ a new lease on life in the 21st century, touching it up to fit gemtext specifications, cutting out the fat of dead links, editing some new info in, and attaching it to the Fractal Compendium project. A list of its original contributors is still rightfully included at the bottom. Keep in mind this article was last dated at '8 May 1994', nearly 30 years ago as of this writing on 24 may 2022.

Learning about fractals

I want to learn about fractals. What should I read first?

'Chaos' by James Gleick is a good book to get a general overview and history. 'Fractals Everywhere' by Miachel Barnsley 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?").

What is a fractal?

Gemipedia Entry: Fractal

Fractal Picture

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.

Picture References

Sierpinski Triangle

Koche Snowflake

Peano Curve

Fractal Tree

Barnsley Fern

Mandelbrot Set

Chaos

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.

Fractal dimension

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.

For more information on fractal dimension and scale, access via the WWW http://life.anu.edu.au/complex_systems/tutorial3.html .

Fractal dimension references:

many color and black and white photographs, high level math, and several

pseudocoded algorithms.

References on how to estimate fractal dimension:

three fractal measurement algorithms for analysis of remote-sensing data.,

_Computers & Geosciences_ 19, 6 (July 1993), pp. 745-767.

0-471-53372-6 Discusses methods of computing fractal dimension. Includes

several short programs for nonlinear analysis.

of America A-Optics and Image Science_ 7, 6 (June 1990), pp. 1055-1073.

There are some programs available to compute fractal dimension. They are listed in a section below (see "Fractal software").

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 smallneighborhoods whose boundaries meet S in a set of dimension k-1, and k is the least nonnegative integer for which this holds.

Strange attractors

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.

Reference:

1. Grebogi, et al., Strange Attractors that are not Chaotic, _Physica D_ 13 (1984), pp. 261-268.

The Mandelbrot set

Gemipedia Entry: The Mandelbrot Set

The Mandelbrot Set Image

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).

How is the Mandelbrot set actually computed?

The basic algorithm is:

iterations were completed.

will go to infinity.

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. See also:

1. M. Frame and J. Robertson, A Generalized Mandelbrot Set and the Role of Critical Points, _Computers and Graphics_ 16, 1 (1992), pp. 35-40.

Note: you can precompute the first Mandelbrot iteration by starting withcz=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.

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 Hill and Fisher used distance estimation techniques to rigorously bound the area and found the area is between 1.503 and 1.5701.

References:

1. J. H. Ewing and G. Schober, The Area of the Mandelbrot Set, _Numer. Math._

61 (1992), pp. 59-72.

2. Y. Fisher and J. Hill, Bounding the Area of the Mandelbrot Set,

_Numerische Mathematik_, .

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.

References:

1. T. Lei, Similarity between the Mandelbrot set and Julia Sets, _Communications in Mathematical Physics_ 134 (1990), pp. 587-617.

2. J. Milnor, Self-Similarity and Hairiness in the Mandelbrot Set, in _Computers in Geometry and Topology_, M. Tangora (editor), Dekker, New York, pp. 211-257.

The "external angles" of the Mandelbrot set (see Douady and Hubbard or brief sketch in "Beauty of Fractals") induce a Fibonacci partition onto it.

The boundary of the Mandelbrot set and the Julia set of a generic c in M have Hausdorff dimension 2 and have topological dimension 1. The proof is based on the study of the bifurcation of parabolic periodic points. (Since the boundary has empty interior, the topological dimension is less than 2, and thus is 1.) Reference:

1. M. Shishikura, The Hausdorff Dimension of the Boundary of the Mandelbrot Set and Julia Sets

: 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_.)

Julia sets

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 < .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.

Julia set references:

1. A. F. Beardon, _Iteration of Rational Functions : Complex Analytic Dynamical Systems_, Springer-Verlag, New York, 1991.

2. P. Blanchard, Complex Analytic Dynamics on the Riemann Sphere, _Bull. of the Amer. Math. Soc_ 11, 1 (July 1984), pp. 85-141. This article is a detailed discussion of the mathematics of iterated complex functions. It covers most things about Julia sets of rational polynomial functions.

Complex arithmetic and quaternion arithmetic

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 rules i^2=j^2=k^2=-1, ij=-ji=k, jk=-kj=i, ki=-ik=j.

Logistic equation

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.

Feigenbaum's constant

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.

References:

1. K. Briggs, How to calculate the Feigenbaum constants on your PC, _Aust.

Math. Soc. Gazette_ 16 (1989), p. 89.

2. K. Briggs, A precise calculation of the Feigenbaum constants, _Mathematics

of Computation_ 57 (1991), pp. 435-439.

3. K. Briggs, G. R. W. Quispel and C. Thompson, Feigenvalues for Mandelsets,

_J. Phys._ A24 (1991), pp. 3363-3368.

4. M. Feigenbaum, The Universal Metric Properties of Nonlinear

Transformations, _J. Stat. Phys_ 21 (1979), p. 69.

5. M. Feigenbaum, Universal Behaviour in Nonlinear Systems, _Los Alamos Sci_

1 (1980), pp. 1-4. Reprinted in _Universality in Chaos_ , compiled by P.

Cvitanovic.

Iterated function systems and compression

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.

Fractal compression is covered in detail in the comp.compression FAQ file(See "compression-faq"). Ftp: rtfm.mit.edu:/pub/usenet/comp.compression[18.70.0.209].

Two books describing fractal image compression are:

1. M. Barnsley, _Fractals Everywhere_, Academic Press Inc., 1988. ISBN 0-12-079062-9. This is an excellent text book on fractals. This is probably the best book for learning about the math underpinning fractals. It is also a good source for new fractal types.

2. M. Barnsley and L. Hurd, _Fractal Image Compression_, Jones and Bartlett. ISBN 0-86720-457-5. This book explores the science of the fractal transform in depth. The authors begin with a foundation in information theory and present the technical background for fractal image compression. In so doing, they explain the detailed workings of the fractal transform. Algorithms are illustrated using source code in C.

An introductory paper is:

1. A. E. Jacquin, Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformation, _IEEE Transactions on Image Processing_, January 1992.

Chaotic demonstrations

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

L-Systems

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.

Some references are:

1. P. Prusinkiewicz and J. Hanan, _Lindenmayer Systems, Fractals, and Plants_, Springer-Verlag, New York, 1989.

2. P. Prusinkiewicz and A. Lindenmayer, _The Algorithmic Beauty of Plants_, Springer-Verlag, NY, 1990. ISBN 0-387-97297-8. A very good book on L-systems, which can be used to model plants in a very realistic fashion. The bookcontains many pictures.

Fractal music

What is some information on fractal music?

One fractal recording is "The Devil's Staircase: Composers and Chaos" on

the Soundprint label.

References

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.

3. K. J. Hsu and A. Hsu, Fractal Geometry of Music, _Proceedings of the National Academy of Science, USA_ 87 (1990), pp. 938-941.

4. K. J. Hsu and A. Hsu, Self-similatrity of the '1/f noise' called music.,_Proceedings of the National Academy of Science USA_ 88 (1991), pp. 3507-3509.

5. C. Pickover, _Mazes for the Mind: Computers and the Unexpected_, St. Martin's Press, New York, 1992.

6. P. Prusinkiewicz, Score Generation with L-Systems, _International Computer Music Conference 86 Proceedings_, 1986, pp. 455-457.

7. _Byte_ 11, 6 (June 1986), pp. 185-196.

Fractal mountains

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.

Plasma clouds

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.

Lyapunov fractals

Where are the popular periodically-forced Lyapunov fractals described?

1. A. K. Dewdney, Leaping into Lyapunov Space, _Scientific American_, Sept. 1991, pp. 178-180.

2. M. Markus and B. Hess, Lyapunov Exponents of the Logistic Map with Periodic Forcing, _Computers and Graphics_ 13, 4 (1989), pp. 553-558.

3. M. Markus, Chaos in Maps with Continuous and Discontinuous Maxima, _Computers in Physics_, Sep/Oct 1990, pp. 481-493.

What are Lyapunov exponents?

Lyapunov exponents quantify the amount of linear stability or instability of an attractor, or an asymptotically long orbit of a dynamical system. There are as many lyapunov exponents as there are dimensions in the state space of the system, but the largest is usually the most important.

Given two initial conditions for a chaotic system, a and b, which are close together, the average values obtained in successive iterations for a and b will differ by an exponentially increasing amount. In other words, the two sets of numbers drift apart exponentially. If this is written e^(n*(lambda)) for n iterations, then e^(lambda) is the factor by which the distance between closely related points becomes stretched or contracted in one iteration. Lambda is the Lyapunov exponent. At least one Lyapunov exponent must be positive in a chaotic system. A simple derivation is available in:

1. H. G. Schuster, _Deterministic Chaos: An Introduction_, Physics Verlag, 1984.

How can Lyapunov exponents be calculated?

For the common periodic forcing pictures, the lyapunov exponent is:

lambda = limit as N->infinity of 1/N times sum from n=1 to N of log2(abs(dx sub n+1 over dx sub n))

In other words, at each point in the sequence, the derivative of the iterated equation is evaluated. The Lyapunov exponent is the average value of the log of the derivative. If the value is negative, the iteration is stable. Note that summing the logs corresponds to multiplying the derivatives; if the product of the derivatives has magnitude < 1, points will get pulled closer together as they go through the iteration.

Computing Lyapunov exponents in general is more difficult. Some references are:

1. H. D. I. Abarbanel, R. Brown and M. B. Kennel, Lyapunov Exponents in Chaotic Systems: Their importance and their evaluation using observed data, _International Journal of Modern Physics B_ 56, 9 (1991), pp. 1347-1375.

2. A. K. Dewdney, Leaping into Lyapunov Space, _Scientific American_, Sept.1991, pp. 178-180.

3. M. Frank and T. Stenges, _Journal of Economic Surveys_ 2 (1988), pp. 103-133.

4. T. S. Parker and L. O. Chua, _Practical Numerical Algorithms for Chaotic Systems_, Springer Verlag, 1989.

Subject: Fractal items

Where can I get fractal T-shirts and posters?

3-D fractals

How can 3-D fractals be generated?

A modern software called Mandelbox can be used. Also, 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.

The papers to read on this are:

1. J. Hart, D. Sandin and L. Kauffman, Ray Tracing Deterministic 3-D Fractals, _SIGGRAPH_, 1989, pp. 289-296.

2. A. Norton, Generation and Display of Geometric Fractals in 3-D, _SIGGRAPH_, 1982, pp. 61-67.

3. A. Norton, Julia Sets in the Quaternions, _Computers and Graphics,_ 13, 2 (1989), pp. 267-278.

Two papers on cubic polynomials, which can be used to generate 4-D fractals:

1. B. Branner and J. Hubbard, The iteration of cubic polynomials, part I., _Acta Math_ 66 (1988), pp. 143-206.

2. J. Milnor, Remarks on iterated cubic maps, This paper is available from anonymous ftp: math.sunysb.edu:/preprints/ims90-6.ps.Z . Published in 1991 SIGGRAPH Course Notes 14: Fractal Modeling in 3D Computer Graphics and Imaging.

Instead of quaternions, you can of course use other functions. For instance, you could use a map with more than one parameter, which would generate a higher-dimensional fractal.

Another way of generating 3-D fractals is to use 3-D iterated function systems (IFS). These are analogous to 2-D IFS, except they generate points in a 3-D space.

A third way of generating 3-D fractals is to take a 2-D fractal such as the Mandelbrot set, and convert the pixel values to heights to generate a 3-D "Mandelbrot mountain". This 3-D object can then be rendered with normal computer graphics techniques.

Fractal software

Where can I obtain software packages to generate fractals?

XAOS, FRACTINIT, Kalles Fractal Generator

References

What are some general references on fractals and chaos?

1. M. Barnsley, _Fractals Everywhere_, Academic Press Inc., 1988. ISBN 0-12-079062-9. This is an excellent text book on fractals. This is probably the best book for learning about the math underpinning fractals. It is also a good source for new fractal types.

2. M. Barnsley and L. Anson, _The Fractal Transform_, Jones and Bartlett, April, 1993. ISBN 0-86720-218-1. This book is a sequel to _Fractals Everywhere_. Without assuming a great deal of technical knowledge, the authors explain the workings of the Fractal Transform (tm). The Fractal Transform is the compression tool for storing high-quality images in a minimal amount of space on a computer. Barnsley uses examples and algorithms to explain how to transform a stored pixel image into its fractal representation.

3. R. Devaney and L. Keen, eds., _Chaos and Fractals: The Mathematics Behind the Computer Graphics_, American Mathematical Society, Providence, RI, 1989. This book contains detailed mathematical descriptions of chaos, the Mandelbrot set, etc.

4. R. L. Devaney, _An Introduction to Chaotic Dynamical Systems_, Addison-Wesley, 1989. ISBN 0-201-13046-7. This book introduces many of the basic concepts of modern dynamical systems theory and leads the reader to the point of current research in several areas. It goes into great detail on the exact structure of the logistic equation and other 1-D maps. The book is fairly mathematical using calculus and topology.

5. R. L. Devaney, _Chaos, Fractals, and Dynamics_, Addison-Wesley, 1990. ISBN 0-201-23288-X. This is a very readable book. It introduces chaos fractals and dynamics using a combination of hands-on computer experimentation and precalculus math. Numerous full-color and black and white images convey the beauty of these mathematical ideas.

6. R. Devaney, _A First Course in Chaotic Dynamical Systems, Theory and Experiment_, Addison Wesley, 1992. A nice undergraduate introduction to chaos

and fractals.

7. G. A. Edgar, _Measure Topology and Fractal Geometry_, Springer- Verlag Inc., 1990. ISBN 0-387-97272-2. This book provides the math necessary for the study of fractal geometry. It includes the background material on metric topology and measure theory and also covers topological and fractal dimension, including the Hausdorff dimension.

8. K. Falconer, _Fractal Geometry: Mathematical Foundations and Applications_, Wiley, New York, 1990.

9. J. Feder, _Fractals_, Plenum Press, New York, 1988. This book is recommended as an introduction. It introduces fractals from geometrical ideas, covers a wide variety of topics, and covers things such as time series and R/S analysis that aren't usually considered.

10. J. Gleick, _Chaos: Making a New Science_, Penguin, New York, 1987.

11. B. Hao, ed., _Chaos_, World Scientific, Singapore, 1984. This is an excellent collection of papers on chaos containing some of the most significant reports on chaos such as ``Deterministic Nonperiodic Flow'' by E.N.Lorenz.

12. S. Levy, _Artificial life : the quest for a new creation_, Pantheon Books, New York, 1992. This book takes off where Gleick left off. It looks at many of the same people and what they are doing post-Gleick.

13. B. Mandelbrot, _The Fractal Geometry of Nature_, W. H. FreeMan and Co., New York. ISBN 0-7167-1186-9. In this book Mandelbrot attempts to show that reality is fractal-like. He also has pictures of many different fractals.

14. H. O. Peitgen and P. H. Richter, _The Beauty of Fractals_, Springer- Verlag Inc., New York, 1986. ISBN 0-387-15851-0. This book has lots of nice pictures. There is also an appendix giving the coordinates and constants for the color plates and many of the other pictures.

15. H. Peitgen and D. Saupe, eds., _The Science of Fractal Images_, Springer-Verlag Inc., New York, 1988. ISBN 0-387-96608-0. This book contains many color and black and white photographs, high level math, and several pseudocoded algorithms.

16. H. Peitgen, H. Juergens and D. Saupe, _Fractals for the Classroom_, Springer-Verlag, New York, 1992. These two volumes are aimed at advanced secondary school students (but are appropriate for others too), have lots of examples, explain the math well, and give BASIC programs.

17. H. Peitgen, H. Juergens and D. Saupe, _Chaos and Fractals: New Frontiers of Science_, Springer-Verlag, New York, 1992.

18. C. Pickover, _Computers, Pattern, Chaos, and Beauty: Graphics from an Unseen World_, St. Martin's Press, New York, 1990. This book contains a bunch of interesting explorations of different fractals.

19. J. Pritchard, _The Chaos Cookbook: A Practical Programming Guide_, Butterworth-Heinemann, Oxford, 1992. ISBN 0-7506-0304-6. It contains type-in-and-go listings in BASIC and Pascal. It also eases you into some of the mathematics of fractals and chaos in the context of graphical experimentation. So it's more than just a type-and-see-pictures book, but rather a lab tutorial, especially good for those with a weak or rusty (or even non-existent) calculus background.

20. P. Prusinkiewicz and A. Lindenmayer, _The Algorithmic Beauty of Plants_, Springer-Verlag, NY, 1990. ISBN 0-387-97297-8. A very good book on L-systems, which can be used to model plants in a very realistic fashion. The book contains many pictures.

21. M. Schroeder, _Fractals, Chaos, and Power Laws: Minutes from an Infinite Paradise_, W. H. Freeman, New York, 1991. This book contains a clearly written explanation of fractal geometry with lots of puns and word play.

22. J. Sprott, _Strange Attractors: Creating Patterns in Chaos_, M&T Books (subsidary of Henry Holt and Co.), New York. " ISBN 1-55851-298-5. This book describes a new method for generating beautiful fractal patterns by iterating simple maps and ordinary differential equations. It contains over 350 examples of such patterns, each producing a corresponding piece of fractal music. It also describes methods for visualizing objects in three and higher dimensions and explains how to produce 3-D stereoscopic images using the included red/blue glasses. The accompanying 3.5" IBM-PC disk contain source code in BASIC, C, C++, Visual BASIC for Windows, and QuickBASIC for Macintosh as well as a ready-to-run IBM-PC executable version of the program. Available for $39.95 + $3.00 shipping from M&T Books (1-800-628-9658).

23. D. Stein, ed., _Proceedings of the Santa Fe Institute's Complex Systems Summer School_, Addison-Wesley, Redwood City, CA, 1988. See especially the first article by David Campbell: ``Introduction to nonlinear phenomena''.

24. R. Stevens, _Fractal Programming in C_, M&T Publishing, 1989 ISBN 1-55851-038-9. This is a good book for a beginner who wants to write a fractal program. Half the book is on fractal curves like the Hilbert curve and the von Koch snow flake. The other half covers the Mandelbrot, Julia, Newton, and IFS fractals.

25. I. Stewart, _Does God Play Dice?: the Mathematics of Chaos_, B. Blackwell, New York, 1989.

26. T. Wegner and M. Peterson, _Fractal Creations_, The Waite Group, 1991. This is the book describing the Fractint program.

Journals:

"Chaos and Graphics" section in the quarterly journal _Computers and Graphics_. This contains recent work in fractals from the graphics perspective, and usually contains several exciting new ideas.

"Mathematical Recreations" section by A. K. Dewdney in _Scientific American_.

Algorithm - The Personal Computer Newsletter. P.O. Box 29237, Westmount Postal Outlet, 785 Wonderland Road S., London, Ontario, Canada, N6K 1M6.

Fractal Report. Reeves Telecommunication Labs. West Towan House, Porthtowan, TRURO, Cornwall TR4 8AX, U.K.

FRAC'Cetera. This is a gazetteer of the world of fractals and related areas, supplied in IBM PC format HD disk. For more information, contact: Jon Horner, Editor, FRAC'Cetera, Le Mont Ardaine, Rue des Ardains, St. Peters, Guernsey GY7 9EU, Channel Islands, United Kingdom.

Fractals, An interdisciplinary Journal On The Complex Geometry of Nature. This is a new journal published by World Scientific. B.B Mandelbrot is the Honorary Editor and T. Vicsek, M.F. Shlesinger, M.M Matsushita are the Managing Editors). The aim of this first international journal on fractals is to bring together the most recent developments in the research of fractals so that a fruitful interaction of the various approaches and scientific views on the complex spatial and temporal behavior could take place.

Acknowledgements

For their help with this file, thanks go to:

Alex Antunes, Steve Bondeson, Erik Boman, Jacques Carette, John Corbit, Abhijit Deshmukh, Tony Dixon, Robert Drake, Detlev Droege, Gerald Edgar, Gordon Erlebacher, Yuval Fisher, Duncan Foster, David Fowler, Murray Frank, Jean-loup Gailly, Noel Giffin, Earl Glynn, Lamont Granquist, Luis Hernandez- Ure:a, Jay Hill, Arto Hoikkala, Carl Hommel, Robert Hood, Oleg Ivanov, Simon Juden, J. Kai-Mikael, Leon Katz, Matt Kennel, Tal Kubo, Jon Leech, Brian Meloon, Tom Menten, Guy Metcalfe, Eugene Miya, Lori Moore, Robert Munafo, Miriam Nadel, Ron Nelson, Tom Parker, Dale Parson, Matt Perry, Cliff Pickover, Francois Pitt, Kevin Ring, Michael Rolenz, Tom Scavo, Jeffrey Shallit, Rollo Silver, Gerolf Starke, Bruce Stewart, Dwight Stolte, Tommy Vaske, Tim Wegner, Andrea Whitlock, Erick Wong, Wayne Young, and others.

Special thanks to Matthew J. Bernhardt for collecting many of the chaos definitions.

Special thanks to Smokey for their efforts in adapting this modern Gemini edition of a 30 year old forgotten FAQ, perserving it for the future

Link to original file