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

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.

As announced in the most recent version of the Course Information Sheet, the

DUE DATE FOR TERM PROJECTS AND PAPERS has been moved from

Thursday, April 16, 2020 to MONDAY APRIL 20, 2020 at 3:30 p.m..

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.

1

2. (10 marks) Now consider the following 2-map iterated function system (IFS) on [0, 1],

f1(x) = 1

5

x f2(x) = 2

5

x +

3

5

. (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]:

I0

0 1

I1

0

1

4

2

5

3

5

3

4

1

ˆ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 =

2

5

= 0.4, of the generalized von Koch

generator (see Lecture 31, Page 400), Starting with the set I0 = [0, 1], iteration of this

l

2

5

l

2

5

l

2

5

l

2

5

l

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.

2

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] ⊂ R

2

.

(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

: R

2 → R

2 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 ∈ R

2

, 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 ∈ R

2

,

ˆf(S) = [

3

i=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) = 2

5

x +

2

5

, (ii) f(x) = 1

3

x

2 +

1

3

.

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

4

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=0

dk

10k+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,

r

D + s

D = 1 . (14)

For the remainder of this question, consider the case r = 1

2

and s = 0, i.e., the following

two-map IFS on [0,1],

f1(x) = 1

2

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

5

(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 ∈ R

n

, 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) = 1

3

x , f2(x) = 1

3

x +

2

3

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

6

EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!

**E-mail:** easydue@outlook.com **微信:**easydue

**EasyDue™是一个服务全球中国留学生的专业代写公司
专注提供稳定可靠的北美、澳洲、英国代写服务
专注提供CS、统计、金融、经济、数学等覆盖100+专业的作业代写服务**