18.091 Lecture 11 Section 14.7: Iterated Function Systems Now we turn to iterated function systems(IFS), which are used to create and analyse fractals. Deﬁnition. Let 0 < β < 1 and let p1 , ...pn be points in the plane. Let Ai (p) = β(p − pi ) + pi for all i = 1...n. The collection of all functions A1 , ...An is called an iterated function system. The IFS draws orbits into the ﬁxed point pi with β as the contraction factor. We use the IFS to produce a fractal by using randomized iteration of the Ai on some arbitrary initial conditions. Example. The Chaos Game IFS produces the Sierpinski Triangle Fractal Arbitrarily choose a ﬁxed point � � x p= y and suppose � � xi pi = , i = 1, 2, 3 yi are the vertices of an equilateral triangle. Then Ai = 0.5|p − pi | + pi is the IFS for the chaos game and produces the Sierpinski Triangle. Note that β here is the invere of the magniﬁcation factor showing the selfsimilarity of the Triangle. Deﬁnition. The set of points to which an arbitrary obit in the plane converges is the attractor for a given iterated function system. 1 It can be proven that an attractor exists for every IFS; however, proof is omitted here. Example. The Cantor MiddleThirds Set as Attractor I claim that the Cantor middlethirds set is an attractor for the following IFS: � � � � x 1 x A0 = 3 y y � � � � � � x 1 1 x−1 A1 = + 3 y y 0 By observation, yn = y/0 3n regardless of the order chosen for iteration of these two contraction functions. So, the orbit of any y0 tends to y = 0 at a geometric rate. To examine the behaviour of the x’s after iteration, we will compute the orbit of x0 by alternating between using function A0 and A1 . That is, the sequence of iterations is {A0 , A1 , A0 , A1 ..} Starting with A0 , our alternating iteration yields � � 2s2 2sn 2s1 x0 + n−1 + ... + , xn = n + 3 3n 3 3 where si = 0 when i is odd and si = 1 when i is even. ∞ � ti where ti are alternately 0 or 2. Consequently, the As n → ∞, xn → 3i i=0 sequence of xn converges to one value if n is even and another if n is odd: lim (x2n ) = n→∞ ∞ � i=0 lim (x2n+1 ) = n→∞ 2 3 = 32i−1 4 ∞ � 1 2 = . 2i 3 4 i=0 We saw both of these points as elements of the Cantor middlethirds set in Section 7.3. This argument is easily expanded to cover general case, which then satisﬁes my claim. So, all orbits of this IFS converge to the Cantor middlethirds set. Notice, however, that this orbit does not converge to a mere point of the Cantor set but eventually visits all regions upon suﬃcient randomized iterations of A0 and A1 . Many variations on the idea of the iterated function system exist. For exam ple, linear contractions may contract points unequally or with diﬀerent proba bilities. We will now consider an IFS that not only contacts points towards but also rotates points around a ﬁxed point. 2 Example. Contraction and Rotation For our IFS, we construct a function, which contracts points by β and rotates points by θ: � � � � � � � � x cos θ − sin θ x − x0 x0 A =β · + y y − y0 y0 sin θ cos θ � � 1 , we get Choosing β = 0.9, θ = π2 , and ﬁxed point p0 = 1 � � x A = y � � � � � � − sin π2 x−1 1 0.9 · + π cos 2 y−1 1 � � � � � � 0 −1 x−1 1 · = 0.9 + 1 0 y−1 1 cos π2 sin π2 The graph of this function is on page 196 of our text. 3

Lecture 11 Section 14.7: Iterated Function Systems

Related Documents

Recommended Documents

Description

Related Documents

Almost There!

Free up your schedule!

Take 5 seconds to unlock