## 这个作业是解决迭代函数系统与自相似分形集的构造/分析的数学代写

PMATH 370 Problem Set No. 7 Winter 2020

April 2, 2020

THIS IS THE FINAL PROBLEM SET FOR THE COURSE. SOLUTIONS TO EACH QUESTION ARE TO BE SUBMITTED VIA CROWDMARK.

THERE WILL BE NO FINAL EXAMINATION FOR THIS COURSE.

The readings below are selected from the following source:

• Encounters with Chaos and Fractals, Second Edition, by D. Gulick, to be referred to as “Encounters”. (The first edition of this book should be quite fine.)

Relevant reading:

• Chapter 5 of “Encounters”: Introduction to Fractals, Sections 5.1, 5.2, 5.4

• Chapter 6 of “Encounters”: Creating Fractal Sets

• Weeks 11 and 12 of Lecture Notes (up to and including Lecture 34), posted on LEARN.

PLEASE READ CAREFULLY: Problems 2-4,6-12 are due TUESDAY, APRIL

14, 2020 at 12:00 noon, SHARP. (Problem 13 is a Bonus problem.) It is recommended that you DO NOT wait until a day or so before the due date to start this Problem Set – or a few minutes before the due time to submit it.

Iterated function systems and the construction/analysis of self-similar fractal sets

1. (Warmup practice problem. Not to be handed in. It won’t be marked.) Consider the following 2-map iterated function system (IFS) on [0, 1],

f1(x) = 1 5 x f2(x) = 1 5 x + 4 5. (1)

(a) Let I0 = [0, 1] and I1 = ˆf(I0), where ˆf is the “parallel” IFS operator composed of the maps f1 and f2, i.e.,

I1 = ˆf(I0) = ˆf1(I0) ∪ ˆf2(I0). (2)

Find I1 (expressed as a union of intervals) and sketch it.

(b) Let

I2 = ˆf(I1) = ˆf1(I1) ∪ ˆf2(I1). (3)

Find I2 (expressed as a union of intervals) and sketch it.

(c) Now define the following sequence of sets,In+1 = ˆf(In). (4)

What is I = limn→∞ In? A short answer is sufficient.

(d) Find the fractal dimension D of the limiting set I.

12. (10 marks) Now consider the following 2-map iterated function system (IFS) on [0, 1],f1(x) = 15x f2(x) = 25x +35. (5)

(a) Let I0 = [0, 1] and I1 = ˆf(I0), where ˆf is the “parallel” IFS operator composed of the maps f1 and f2, i.e.,

I1 = ˆf(I0) = ˆf1(I0) ∪ ˆf2(I0). (6)

Find I1 (expressed as a union of intervals) and sketch it.

(b) Let

I2 = ˆf(I1) = ˆf1(I1) ∪ ˆf2(I1). (7)

Find I2 (expressed as a union of intervals) and sketch it.

(c) Now define the following sequence of sets,In+1 = ˆf(In). (8)

What is I = limn→∞ In? A short answer is sufficient.

(d) Write down the equation that must be satisfied by the fractal dimension D of the limiting set I. You do not have to determine D, analytically or numerically.

3. (10 marks)

(a) Find an IFS on [0,1] which produces the following dissection of [0, 1]:

I00 1I10142535341

ˆf1(I0)

ˆf2(I0)

ˆf3(I0)

(b) What is the attractor A of this IFS? A short answer is sufficient.

(c) Write down the equation which must be satisfied by the fractal dimension D of the attractor A.

4. (10 marks) Consider the following special case, r =25= 0.4, of the generalized von Koch generator (see Lecture 31, Page 400), Starting with the set I0 = [0, 1], iteration of thisl2

5l25l25l25l generator produces, in the limit, a generalized von Koch curve C with endpoints at (0,0) and (1,0). Find the four maps fi of the IFS whose fixed point attractor A is identical to this generalized von Koch curve C.

5. (Practice problem. Not to be handed in.) Consider the “Sierpinski carpet” set S shown in

Figure 1 below.

Figure 1: Sierpinski carpet S for Question 5

Assume that the “carpet” is located in the region [0, 1] × [0, 1] ⊂ R2.

(a) Find the IFS for which the Sierpinski carpet S is the fixed point/attractor. (Hint: S is

a union of how many contracted copies of itself? How can these copies be generated?)

(b) Find the fractal dimension D of the Sierpinski carpet.

6. (15 marks) Consider the modified Sierpinski triangle/gasket A shown in Figure 2 below.

Figure 2: Sierpinski triangle A for Question 6

(a) By means of a rough sketch of A, show how it may be viewed as a union of three contracted copies of itself – you may circle each of the copies in your sketch and identify it as a contracted copy.

(b) Find the three affine maps fi: R2 → R2 which produce these copies. In this way, you will find the three-map IFS f = {f1, f2, f3} for which A is the unique fixed point/attractor.

(You’ll have to pay attention to the location of the vertices of the triangle. Note that two vertices are situated at (2,0) and (0,2) and not (1,0) and (0,1).)

(c) Let S0 = [0, 2]2 ∈ R2, i.e., the square region S0 = {(x, y), 0 ≤ x ≤ 2 , 0 ≤ y ≤ 2 .}. On separate sets of xy-axes, sketch the sets S1 = ˆf(S0), S2 = ˆf(S1) and S3 = ˆf(S2), where 3ˆf is the IFS operator defined by the maps fi, 1 ≤ i ≤ 3, i.e., for any S ∈ R2,ˆf(S) = [3i=1ˆfi(S). (9)

(d) What is the set S = limn→∞Sn? A very short answer is sufficient – no proof required.

7. (5 marks) With reference to the Sierpinski triangle S of Question 6, what fourth map f4 can be added to the three-map IFS so that the attractor of the four-map IFS f = {f1, f2, f3, f4} is a solid triangular region, i.e., so that no dissection takes place?

8. (10 marks) Consider the modified Sierpinski triangle S shown in Figure 3 below.

Figure 3: Modified Sierpinski triangle S for Question 8

Find an iterated function system (IFS) f = {f1, · · · , fN } on [0, 1] × [0, 1] for which the set S is the fixed point attractor. For each map fi, explain very briefly – a sentence will do – the

main idea behind how you obtained the map, as you did in Question 6.

Contraction Mappings and Banach’s Fixed Point Theorem 9. (20 marks) Consider each of the following maps:

(i) f(x) = 25x +25, (ii) f(x) = 13×2 +13.

(a) Show, by sketching the graph of each of these functions (using separate sets of xy-axes),that each of these functions maps [0, 1] to itself.

(b) Show that each of these maps are contraction maps on [0,1] by finding their respective contraction factors, i.e., the lowest value of C for each function such that |f(x) − f(y)| ≤ C|x − y| for all x, y ∈ [0, 1] . (10)

(Hint: For (ii), you can use the Mean Value Theorem. There are also other methods.)

(c) For each of these two functions, what can you conclude from Banach’s Fixed Point Theorem (Lecture 34, Week 12)? (State both conclusions.)

(d) Find the fixed point ¯x for each of these functions and plot it on the respective graph of the function from Part (a).

A few additional questions on IFS

Some of the questions in this section may be slightly more challenging but not excessively so. They provide an opportunity to think a little more deeply about the concepts. In most cases, however, the answers are very short.

10. (10 marks) Question 5 of Problem Set No. 5 was concerned with the set S ⊂ [0, 1] of all real numbers with decimal expansions of the form,x =X∞k=0dk10k+1 , dk ∈ {0, 1, 3, 4, 5, 6, 8, 9} . (11)

In other words, the decimal expansion of a point x ∈ S does not contain the decimal digits 2 and 7. (You may wish to consult the posted solution to Question 5 of Problem Set No. 5 for this problem.)

(a) Find an N-map IFS {f1, f2, · · · , fN } on [0, 1] which has the set S as its attractor.

(b) What is the fractal dimension D of set S? A short answer, with a “wee bit” of explanation, will suffice.

(c) (This may be a bit more challenging – worth 2-3 marks at most.) Suppose that you have written a computer program to compute points in the set S using the random iteration algorithm described in Lecture 33. You can assume that the algorithm starts with a “seed point” x0 ∈ S, for example, x0 = 0 = 0.¯0, so that all future points xn generated by the algorithm lie in S. (In other words, you do not have to wait for the iterates to approach the attractor set S sufficiently closely – the iterates xn start in S and therefore remain in S.)

How would you modify your algorithm to compute points in the following subset T ⊂ S:

If x ∈ T, then in the decimal expansion of x,x = 0.d1d2d3 · · · , (12)

if the digit “3” occurs anywhere in the expansion of x, the next digit cannot be a “5”,i.e.,If di = 3 for an i ≥ 1, then di+1 6= 5.

(A short answer – a sentence or two – is sufficient. You don’t have to write any code or pseudocode.)

11. (10 marks) In Lecture 33, we examined briefly the following two-map IFS on [0,1],f1(x) = rx , f2(x) = sx + (1 − s), (13) where 0 < r < 1 and 0 < s < 1 are constants such that r + s < 1. Note that f1(0) = 0 and f2(1) = 1. This IFS produces a dissection of the interval I0 = [0, 1]. Repeated application of the IFS “parallel operator” ˆf produces a sequence of sets In which converge to a Cantor-like set in [0,1]. The fractal dimension D of this set satisfies the equation,rD + sD = 1 . (14)

For the remainder of this question, consider the case r = 12 and s = 0, i.e., the following two-map IFS on [0,1],f1(x) = 12x , f2(x) = 1 . (15)

(In other words, f2 maps all x ∈ [0, 1] to 1. Think of this map as the limiting case of the map f2(x) in Eq. (13) as s → 0+. If this presents a challenge, some diagrams might help.)

(a) Following the same procedure as in Question 2, let I0 = [0, 1], and In+1 = ˆf(In), n ≥ 0 , (16) where ˆf is the “parallel” IFS operator composed of the maps f1 and f2 in (15). Find I1 and I2 and sketch them.

(b) What is A = limn→∞ In, the attractor of this IFS?

(c) Find the dimension D of this set. (It is not guaranteed that Eq. (14) applies in this case, i.e., s = 0. For this reason, you may have to go back to first principles, i.e., look at N(ǫn), the number of intervals of length ǫn needed to “cover” the set A, using appropriate values of ǫn.)

(d) Now consider the case r = s = 0 in Eq. (13), i.e.,f1(x) = 1 , f2(x) = 1 . (17)

What is the attractor A of this IFS? What is the dimension D of A in this case? (Very short answers are sufficient.)

12. (5 marks) Let f = {f1, f2, · · · , fN } be an N-map IFS over a subset D ∈ Rn, i.e., the fk :

D → D are contraction maps with contraction factors Ck ∈ [0, 1). From the Theorem given in Lecture 34 of the lecture notes, there exists a unique set A such thatˆf(A) = A , (18)

where ˆf denotes the “parallel” operator associated with this IFS.

Let ¯xk be a fixed point of IFS map fk for any k ∈ {1, 2, · · · , N}. Prove that ¯xk ∈ A. You should state any Theorems from the course (Lecture Notes) that you use in your proof.

13. (5 marks) Bonus: Consider the 2-map IFS examined quite often in this course,f1(x) = 13x , f2(x) = 13x +23. (19)

The attractor of this IFS is the ternary Cantor set C ⊂ [0, 1].

Sketch the graphical interpretation of the iteration of the “parallel” operator ˆf associated with this IFS, starting with a point x0 ∈ [0, 1].

A few main points outlining the results of this procedure will be sufficient.

This Problem Set will be marked out of 105. The maximum number of marks is 110.