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

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+专业的作业代写服务