Release 4.0 | |||
| |||
Julia and Mandelbrot Sets - Theory |
|||
1. Julia sets
He studied iterative dynamic systems, i.e. a system with (1) z ---> f(z) where z is a complex number. 'Iterative', because the function f is applied again and again, so he examined the sequence of points z, f(z), f(f(z)), f(f(f(z))), ..., for different initialization values of z. The sequence of those points is called orbit of the initialization value z, or to define it: Definition Orbit of z: Let f be a function. Then the list of successive iterates of a point or number is called the orbit of that point. In a common sense the Julia set (named after Gaston Julia) consists of all starting points z, whose orbits behave abnormal. Normally the orbit leads to something, the orbit leads to an attracting point, or, to be more general, to an attracting set. For example consider f=z*z: If we start with z=1, then the orbit is (1,1,1,...), so the orbit converges to the number 1, so 1 is an attracting point. If we start with z=0.5, then the orbit is (0.5,0.25,0.0625,0.0039, ...), which converges to 0, so 0 is an attracting point, too. If we start with z=2, the orbit is (2,4,16,256,65536,...), which converges (diverges) to infinity, so infinity is an attracting point, too. In this case you see that the orbits of all initialization values lead to an attracting point. But this is not a must. If we use another function we will see that some orbits lead to nothing, they simply jump around, not knowing where they should go. The Julia set consists of all numbers whose orbits don't know where to go. That's a rather strange definition, isn't it? I'm limiting my explanations mainly to quadratic systems, i.e. systems where f(z) is a polynomial of degree 2 in the form f(z)=a*z*z+b*z+c. Now let me define some things: Definition Critical Point of function f: Let f be a function. Then every point z with f'(z)=0 (first derivation of f at point z is null) is called Critical point of f. Definition fixed point of f: Let f be any function. Then every point z with z=f(z) (f lets z invariable) is called fixed point. Additionally, if infinity is invariable, i.e. f(infinity)=infinity, then infinity is a fixed point, too. If you have headaches on reading such stuff, then please consider another mapping of the complex number plane, the so called Riemann sphere, where infinity indeed is a single point, and not a strange expression for something unimaginable. The function f(z)=a*z^2+b*z+c can be simplified by applying a transformation. Such a transformation assigns special values to some points. Most of the time people work with two standard forms of f: (1) f(z)=z*z+c and (2) f(z)=m*z+(1-m)*z*z In the first case the critical point of f is at 0, and in some situations this can be very useful for theoretical and practical purposes. The (finite) fixed points of f are a bit more complicated: 0.5+sqrt(0.25-c) and 0.5-sqrt(0.25-c). In the second case the (finite) fixed points of f are at 0 and 1. Most of the time fractal programs use standard formula (1). (As you can imagine, such transformations do not change the fractal itself, transformations just distort the image. So all strange and beautiful structures found in any Julia set using the function f(z)=m*z+(1-m)*z^2 are found in a special Julia set using the function f(z)=z^2+c, too, at least in a mathematical sense...) The property of a Julia set is mainly determined by its attracting fixed points. You know what a fixed point is, but how can one determine whether it is an attracting fixed point? Lets assume p is a fixed point of f, i.e. f(p)=p If we zoom in at p very deep and take z0 close to p, then z1=f(z0) is similar to: z1-p=m*(z0-p), with m=f'(p) Quite clear, if we write it in another way: The first derivation of f at point p is: f(z)-f(p) f'(p)= lim ----------- z->p z - p Now if we choose z0 close to p, an approximation of m=f'(p) is: f(z0)-f(p) z1 - p m = ------------ = -------- z0 - p z0 - p The so called eigen value m of a fixed point p of f is m=f'(p). As we see from above, if |m| is less than 1, then z1 is more close to p than z0, so we have an attracting fixed point. If |m| is greater than 1, then z1 is more far away than z0, so we have a repulsing fixed point. If |m|=1, then the fixed point is neutral or indifferent. Then numerous interesting effects can occur (at least theoretically interesting). So if one wants to obtain an interesting Julia set, one should pay attention to the attracting fixed points. Enough said about critical points, fixed points and so on? Well, how does one actually calculate a Julia set? What we have to do is the following: We have to search for all points whose orbits lead to something. All those points don't belong to the Julia set, the Julia set consists of all other (remaining) points. Well, now the question is: What do you want to calculate? A nice image or the Julia set? If you want to calculate a nice image then simply do what most other fractal programmers do: Check the orbits of all points: If they bail out some predefined value, color it according to the time needed to bail out (escape time algorithm). If they don't bail out stop after a predefined number of iterations and color the pixel black. That's it. So what do these programmers? Well, they look for all points, whose orbits lead to infinity. They simply don't care about attracting fixed points, attracting cycluses etc. They assume that infinity is the only one. All they want to do is to calculate nice images under the label 'fractal', because it's modern and looks funny and this is all people want nowadays. In order to calculate the Julia set one has to check whether the point is attracted by infinity, by a finite attractor, or by an attracting cyclus. If it is, then the according pixel can be colored in some way to indicate it does not belong to the Julia set. If it is not attracted after some time, it can be colored accordingly. An algorithm could look like follows: z=complex number corresponding to screen pixel to examine Bail_in=0.0000000001 Bail_out=16 for i=0 to MaxIter step 1 loop begin z=f(z) if i=MaxIt/2 then cyclus_search=z; if i>MaxIt/2 then begin if |z-cyclus_search|<Bail_in then break; // point does not belong to Julia set // point is attracted by a cyclus of length i-MaxIt/2 end if if |z|>Bail_out then break; // point is attracted by infinity end loop if i<MaxIter then point does not belong to Julia set else point could belong to Julia set Well, this algorithm is one of the most inefficient algorithms used to calculate the Julia set. But it shows the Julia set and produces nice images. Calculating the Julia set alone can be done very easy and quick by using the inverse iteration and starting with a point which is already known to be on the Julia set. Gaston Julia produced some interesting results. The most important ones are as follows (without proof...): Let J(f) be any Julia set using function f. Then:
Enough said about Julia sets? Well, then let's continue explaining Mandelbrot sets... 2. Mandelbrot Sets Result (4) from Mr. Julia tells us, that it is possible to classify the Julia sets. There are exactly two types of Julia sets: Either J(f) is connected or it is comprised of dust of infinitely many points. Well, how about calculating an image displaying this behaviour? Let's define an image as follows: Take a complex number c and calculate the Julia set J(f) using that number, i.e. J(z^2+c). Then try to find out whether the Julia set J(z^2+c) is connected or like 'dust'. As a formula: c is a complex number. { 0 if J(z^2+c) is connected G(c)= { { 1 if J(z^2+c) is dust like Now simply visualize the result. Well, it's something you most probably have seen before: The Mandelbrot set Each point in a Mandelbrot set shows us the type of the Julia set: If we take an arbitrary point 'c' and it lies 'inside' the Mandelbrot set (i.e. normally the black region), then this tells us, that the Julia set J(z^2+c) is connected. If we take another point 'd' from 'outside' the Mandelbrot set, then this tells us, that the Julia set J(z^2+d) is dust like. Quite amazing, isn't it? But one question I did not answer: How can we actually determine the type of a Julia set? Do we have to calculate and to examine it to determine the type? This would be very difficult and very very time consuming. Fortunately another algorithm can be used: We do not have to calculate the whole Julia set, we only have to examine the orbits of specific points: These specific points are the critical points, i.e. all points where the first derivation vanishes (f'(z)=0), as defined above. The orbits of the critical points define the type of the Julia set: If all orbits stay limited, then the Julia set is connected. If at least one orbit tends to converge to infinity, then the Julia set is dust like. Lets make an example: Most of the time one examines z^2+c. In this case there is only one critical point: f'(z)=2*z=0, i.e. z=0 is the only critical point. So in this case we only have to examine the orbit of 0. As an algorithm we then would have (looks mostly like the algorithm used for calculating the Julia set, except the changing value 'c' and the initialization value...) c=complex number corresponding to screen pixel to examine Bail_out=16 z=0 for i=0 to MaxIter step 1 loop begin z=z^2+c if |z|>Bail_out then break; // orbit is attracted by infinity end loop if i<MaxIter then point does not belong to the Mandelbrot set, orbit of critical point 0 of Julia set z^2+c converges to infinity else point could belong to the Mandelbrot set So you see that the Mandelbrot set is simply a one page dictionary for Julia sets. The most interesting Julia sets are those which lie near the border of the Mandelbrot set. So if you want to calculate an interesting Julia set, then set the parameter 'c' to a value which lies near the border of the Mandelbrot set. Last update on Nov 26 2002. |