{"id":482,"date":"2007-08-03T15:15:18","date_gmt":"2007-08-03T15:15:18","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/08\/03\/iterated-function-systems-and-attractors\/"},"modified":"2007-08-03T15:15:18","modified_gmt":"2007-08-03T15:15:18","slug":"iterated-function-systems-and-attractors","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/08\/03\/iterated-function-systems-and-attractors\/","title":{"rendered":"Iterated Function Systems and Attractors"},"content":{"rendered":"

Most of the fractals that I’ve written about so far – including all of the L-system fractals – are
\nexamples of something called iterated function systems<\/em>. Speaking informally, an iterated function
\nsystem is one where you have a transformation function<\/em> which you apply repeatedly. Most iterated
\nfunction systems work in a contracting<\/em> mode, where the function is repeatedly applied to smaller
\nand smaller pieces of the original set.<\/p>\n

There’s another very interesting way of describing these fractals, and I find it very surprising
\nthat it’s equivalent. It’s the idea of an attractor<\/em>. An attractor is a dynamical system<\/em> which, no matter what its starting point, will always evolve towards a particular shape. Even if you
\nperturb the dynamical system, up to some point, the pertubation will fade away over time, and the system
\nwill continue to evolve toward the same target.<\/p>\n

<\/p>\n

The classic example of this is something called the chaos game<\/em>. In the chaos
\ngame, you take a sheet of paper, and draw three points, A, B, and C. Then you pick a point P0<\/sub>, something where inside the triangle formed by A,B, and C. Then you do the following repeatedly, for each iteration i+1:<\/p>\n

    \n
  1. Randomly select one of A, B, and C.<\/li>\n
  2. Draw a line segment between the most recent pi<\/sub> and the selected point. Find
    \nthe midpoint of that segment. That is point pi+1<\/sub>. Draw a dot on pi+1<\/sub><\/li>\n<\/ol>\n

    \"sier-attract.png\"<\/p>\n

    Keep doing that, over and over again. If you try this yourself for a few iterations, you’ll see
    \nwhy it’s called the chaos game: the point jumps around seemingly at random within the triangle. The
    \nset of points that results from this seemingly random process is the attractor<\/em> for the
    \ndynamical system described by the chaos game. For example, over to the right, I started with P0<\/sub>, and then did iterations with line segments from p0<\/sub> to A, from p1<\/sub> to C, from p2<\/sub> to C, p3<\/sub> to B, and from p4<\/sub> back to C.<\/p>\n

    So what’s the result? What does the attractor for the chaos game look like?<\/p>\n

    \"sier-shear.png\"<\/p>\n

    It’s the Sierpinski gasket, distorted so that the triangles are shaped the same as the
    \ntriangle defined by A, B, and C:<\/p>\n

    For any of the L-system fractals, there’s a dynamical system for which the fractal is
    \nthe attractor.<\/p>\n

    Let’s step back just for a moment. What’s going on here? The starting point is the dynamical system.
    \nJust what is<\/em> a dynamical system?<\/p>\n

    A dynamic system is basically a kind of differential equation – it’s a rule that specifies a future
    \nstate of a system in terms of a previous state of the system. The states in this system are really points
    \nwithin some kind of topologial manifold. Every dynamical system has something called a state space<\/em>
    \n– that is, the space which includes the set of points within the manifold that are reachable by some
    \nsequence of iterations of the system. <\/p>\n

    On some level, the basic study of differential equations – what most of us math geeks studied in our
    \ndiffeq courses in college is largely about trying to find closed form<\/em> equivalents of a given
    \ndynamical system: that is, a solution for the system where you can find the value of the state of a system
    \nat a specified point in time in one step, without needing to iterate through its previous states. <\/p>\n

    The attractor is the set defined by a dynamical system. What makes it an attractor is the somewhat
    \nodd property that instead of varying
    \nwildly, the attractor will always try to push the system back into its basic space. Its state space
    \nis strongly centered on some basic set of points, and it will always drift back towards those points. Fractal attractors (also called strange attractors<\/em>) are dynamical systems with a fractal
    \nstructure. The chaos game contains embedded within it the self-similarity property of the
    \nSierpinski gasket; so its attractor set has that structure.<\/p>\n

    For another fascinating example of this, taken from this excellent explanation of
    \niterated function systems<\/a>, here’s a more complex dynamical system. The
    \nway that it works is that there are 4 possible rules for getting the next point, each of which
    \nhas an assigned probability. The next rule is selected randomly, according to the specified
    \nprobability distribution.<\/p>\n\n\n\n\n\n\n
    Rule<\/th>\nProbability<\/th>\nNext X<\/th>\nNext Y<\/th>\n<\/tr>\n
    1<\/td>\n1\/100<\/td>\n0.16<\/td>\n0x+0y<\/td>\n<\/tr>\n
    2<\/td>\n85\/100<\/td>\n0.85x+0.04y<\/td>\n-0.04x+0.85y+1.6<\/td>\n<\/tr>\n
    3<\/td>\n7\/100<\/td>\n0.2x-0.26y<\/td>\n0.23x+0.22y+1.6<\/td>\n<\/tr>\n
    4<\/td>\n7\/100<\/td>\n-0.15x+0.28y<\/td>\n0.26x+0.24y+0.44<\/td>\n<\/tr>\n<\/table>\n

    This is the classic Barnsley Fern fractal:<\/p>\n

    \"fb.gif\"<\/p>\n

    That strange set of equations contains the structure of a fern. <\/p>\n

    One of the interesting things about the notion of fractal attractors is that one of the objections
    \nto fractals is that they’re too irregular, too strange. Mathematicians tend to like things to be clean and simple. They like continuous, differentiable functions; they like their diffEQs to have closed forms. The idea that most<\/em> functions are irregular, and that the functions we’ve spent so much time studying are less than a grain of sand on the beach is a depressing one to most people in math. One
    \nof the things that originally caused some resistance to the idea of fractals is that they’re not<\/em> from the world of clean functions, the world of regularity and continuity that we so adore.
    \nBut the fact that attractors include fractals – that out of the universe of iterative systems, nearly
    \nall of them escape – turn into erratic scattering chaos, except for the tiny spec of dust that we call attractors – that tells us that fractals are part of the world of things that we can analyze and understand, even if they seem strange.<\/p>\n

    We can understand what these iterative functions systems do – how they generate the fractal attractors – by looking at them as affine transformations, and appyling techniques from conventional euclidean geometry to them. Next post, I’ll show you why<\/em> the chaos game is just another way of defining the
    \nSierpinski gasket.<\/p>\n","protected":false},"excerpt":{"rendered":"

    Most of the fractals that I’ve written about so far – including all of the L-system fractals – are examples of something called iterated function systems. Speaking informally, an iterated function system is one where you have a transformation function which you apply repeatedly. Most iterated function systems work in a contracting mode, where the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[86],"tags":[],"class_list":["post-482","post","type-post","status-publish","format-standard","hentry","category-fractals"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7M","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/482","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=482"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/482\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=482"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=482"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=482"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}