Hệ hàm lặp và tập tự đồng dạng
1.1.1 Định nghĩa ([11]) Giả sử D ⊂ R n , D 6= ∅ (thường lấy D = R n ) và ký hiệu
|a−b| là khoảng cách giữa hai điểm a, b trong R n
1) ánh xạf : D → D được gọi là co trên D nếu tồn tại c ∈ [0; 1)sao cho
|f (x)−f (y)| ≤ c|x−y| ∀x, y ∈ D, c được gọi là tỷ số co.
2) ánh xạf : D → D được gọi là đồng dạngtrên D nếu tồn tạic > 0sao cho
|f (x)−f (y)| = c|x−y| ∀x, y ∈ D, c được gọi là tỷ số đồng dạng.
1.1.2 Định nghĩa([11]) Cho D là một tập con đóng trong (R n , d)với d được xác định bởi d(x, y) =|x−y| s n
Với mỗix ∈ R n và mỗi tập con A ⊂ R n ta xác định khoảng cách từ x đến A nh sau d(x, A) = inf{d(x, a) : a ∈ A}
Với mỗi số thực dươngδ, ta đặt
A δ = {x ∈ R n : d(x, A) ≤ δ} là tập gồm những điểm cáchAmột khoảng không quáδ Ta gọiA δ làδ−baocủa
GọiK là lớp tất cả các tập con compact, khác rỗng của D Với hai tập A, B thuộc K, ta ký hiệu d H (A, B) = inf{δ >0 : A ⊂ B δ , B ⊂ A δ }.(1.1)
1.1.3 Định lý([11]) Với cách xác địnhdH như (1.1) thì dH là một mêtric trênK. Hơn nữa, (K, d H ) là không gian mêtric đầy đủ.
1.1.4 Định nghĩa ([11]) Một họ hữu hạn ánh xạ co {S i } N i=1 với S i : D → D được gọi là mộthệ hàm lặp (IFS-Iterated Function System) trên D.
1.1.5 Mệnh đề([8]) Cho N ánh xạ co{S i } N i=1 trên D, ánh xạ S : K → K được xác định bởi
Khi đó, S là ánh xạ co.
Từ Định lý 1.1.3, Mệnh đề 1.1.5 và theo nguyên lý ánh xạ co Banach ta có kết quả sau.
Định lý cho hệ hàm lặp {S i } m i=1 và ánh xạ S được xác định bởi (1.2) khẳng định rằng luôn tồn tại duy nhất một tập F thuộc K sao cho S(F) = F Hơn nữa, nếu có tập E thuộc K với điều kiện S i (E) ⊂ E (1 ≤ i ≤ m), thì S k là sự lặp lại k lần của ánh xạ S.
S k (E). 1.1.7 Định nghĩa ([8]) Cho hệ hàm lặp{S i } m i=1 trên D Khi đó
1) TậpF được xác định như trong Định lý 1.1.6 được gọi là tập bất biếnhay tập hút (attractor) hay tập Fractal của hệ hàm lặp{S i } m i=1
2) NếuSi(1≤ i ≤ m) là ánh xạ đồng dạng thì tập bất biếnF được gọi là tập tự đồng dạng(self - similar set).
Độ đo Hausdorff và chiều Hausdorff
Phần này chúng tôi trình bày khái niệm và các tính chất cơ bản về độ đo, độ đo Hausdorff và chiều Hausdorff.
1.2.1 Định nghĩa([11]) ChoX là một tập hợp tùy ý vàC là đại số các tập con của X.
1) Hàm tập à : C → R được gọi là mộtđộ đo trên C nếu thỏa mãn các điều kiện sau i)à(A) ≥0với mọi A ∈ C; ii)à(φ) = 0; iii)àlàσ- cộng tính, tức là nếuA i ∈ C(i = 1,2, ), A i ∩A j = φ(i 6= j),
2) Hàm à được gọi là một độ đo ngoài trên C nếu à thỏa mãn i), ii) và thay iii) bởi iii') là iii') NÕuA i ∈ C(i = 1,2, ),
P i=1 à(A i ). 1.2.2 Định nghĩa([11]) 1) Cho F ⊂ R n , F 6= ∅ Khi đó, đường kínhcủa tập F được xác định bởi |F| = sup{d(x, y) : x, y ∈ F}.
2) Cho {U i } là một họ các tập con trong R n Nếu F ⊂
Ui thì {U i } được gọi là mộtphủ của F Nếu thêm điều kiện0 < |U i | ≤ δ, với mọi i, trong đó δ > 0 là số cho trước thì{U i } được gọi là mộtδ-phủ F.
|U i | s : {U i }làδ−phủ F }. Khi đó,H δ s (F)là hàm nghịch biến theo δ, nghĩa là nếu δ 1 ≤ δ 2 thì
1.2.3 Định lý ([11]) Cho C là lớp các tập con của R n , với mỗi s ≥ 0 hàm tập
H s (F) = lim δ→0H δ s (F)với mọi F ∈ C là một độ đo ngoài trên C.
Từ Định lý 1.2.3 ta đi đến định nghĩa sau.
1.2.4 Định nghĩa ([11]) Độ đo sinh bởi độ đo ngoài H s trong Định lý 1.2.3 được gọi làđộ đo Hausdorff trên σ- đại sốτ các tập conH s - đo được củaR n Tập
F ⊂R n thỏa mãn0 < H s (F) < ∞được gọi là s - tập.
1.2.5 Mệnh đề ([11]) Cho ∅ 6= F ⊂ R n là tập Borel Khi đó, luôn tồn tại duy nhất một giá trị s F ∈ [0; +∞) để
1.2.6 Định nghĩa ([11]) Cho F ⊂ R n Số s F ∈ [0; +∞] được nói tới trong Mệnh đề 1.2.5 được gọi làchiều Hausdorff của F, ký hiệudimHF.
2) Nếu tồn tạis ∈ [0; +∞] để0< H s (F) < ∞thì dim H F = s.
Điều kiện tập mở
1.3.1 Định nghĩa ([11]) Ta nói rằng hệ hàm lặp{S 1 , S 2 , , S m } trên R n thỏa mãn điều kiện tập mở(OSC- Open Set Condition) nếu tồn tại tập mởV khác rỗng trong
Ngược lại, ta nói hệ hàm lặp có phủ(overlap).
1.3.2 Định nghĩa ([11]) Cho hệ hàm lặp {S 1 , S 2 , , S m }trên R n , F là tập bất biến qua hệ hàm lặp {S i } m i=1 , tức F m
S i (F) Khi đó hệ hàm lặp trên thỏa mãn điều kiện tách mạnh (SSC- Strong Separation Condition) nếu
1.3.3 Định lý ([11]) Cho hệ hàm lặp {S i } m i=1 trên R n thỏa mãn OSC, gồm các ánh xạ đồng dạng với các tỷ số đồng dạng tương ứng là c i ∈ (0; 1), i = 1,2, , m và
F là tập bất biến qua hệ hàm lặp {S i } m i=1 Khi đó, dim H (F) =s với slà nghiệm duy nhất của phương trình m
1.3.4 Ví dụ([11]) Tập CantorF là tập bất biến sinh bởi hệ hàm lặp gồm hai ánh xạ đồng dạng trênR là
S 1 (x) = 1 3 x, S 2 (x) = 1 3 x+ 2 3 với tỷ số đồng dạng c 1 = c 2 = 1 3 thỏa mãnOSC Thật vậy, lấy V = (0,1), khi đó
Theo Định lý 1.3.2, ta códimHF = s với slà nghiệm của phương trình
Một số điều kiện tương đương với điều kiện tập mở
Định lý 1.3.2 cung cấp công thức đơn giản để xác định chiều Hausdorff của tập fractal sinh bởi hệ hàm lặp thỏa mãn điều kiện tập mở Việc xác định xem hệ hàm lặp đã cho có thỏa mãn điều kiện OSC hay không là rất quan trọng Dưới đây là một số nghiên cứu liên quan đến vấn đề này.
Giả sử{S 1 , , S m }là một hệ hàm lặp trênR n vàAlà tập bất biến qua hệ hàm lặp đó. Đặt A s = S s (A) = S s 1 ◦ ◦ S s p (A) Xét g = S t ◦ S s −1 : A s → A t khi đó
A s ∩A t = ∅khi và chỉ khi g là ánh xạ đồng nhấtid.
Với các kết quả trên, năm 1992, C Bandt và S Graf trong ([5]) đã đưa ra kết quả sau.
1.4.1 Định lý([5]).Hệ hàm lặp thỏa mãn điều kiện tập mở khi và chỉ khi tồn tại x ∈ R d và ε > 0sao cho với mọi s, tkhông so sánh được thì
≥ ε. Cho hệ hàm lặp{S 1 , , S m } Khi đó, tập
S i −1 ◦S j (A) : i 6= j được gọi làtập mở trung tâm đối với hệ hàm lặp {S 1 , , S m }.
Năm 2005, C Bandt, N V Hung và H Rao trong ([3]) đã đưa ra kết quả
1.4.2 Định lý ([3]) Nếu hệ hàm lặp {S 1 , , Sm} thỏa mãn OSC thì Vc là tập mở thỏa mãn định nghĩa OSC Nếu hệ hàm lặp {S 1 , , S m } không thỏa mãn OSC thì
1.4.3 Định lý([4]).Đặt G S i −1 ◦S j : i, j ∈ Σ ∗ , i 6= j Khi đó, IFS thỏa mãn OSC khi và chỉ khiid /∈ G
Năm 1994, A Chief trong ([1]) có kết quả
1.4.4 Định lý ([1]) Gọi s là dim H F Khi đó, IFS thỏa mãn OSC khi và chỉ khi
Sè Pisot
Số Pisot, được phát hiện bởi Thue vào năm 1912 và tái khám phá bởi Hardy vào năm 1919 trong bài viết về xấp xỉ Diophantine, đã trở nên nổi tiếng sau luận án của Charles Pisot vào năm 1938 Nghiên cứu về số Pisot tiếp tục được thực hiện bởi Tirukkannapuram Vijayaraghavan và Raphael Salem vào năm 1940.
Số Pisot - Vijayaraghavan, viết tắt là số P.V, là một loại số nguyên đại số lớn hơn 1, trong đó mọi liên hợp Galois của nó đều có giá trị tuyệt đối nhỏ hơn 1.
1.5.2 Chú ý i) Mọi số nguyên lớn hơn 1, đều là P.V số.
Vào năm 1962, Garsia đã chứng minh một kết quả quan trọng liên quan đến số P.V η và các liên hợp của nó, trong đó |η i | < 1 cho mọi i Nếu L(x) = a0 + a1 x + + al x với các hệ số nguyên, thì điều này mở ra những ứng dụng mới trong lý thuyết số.
Sau đây là một số trường hợp về hệ hàm lặp liên quan đến số Pisot đã nghiên cứu
Cho λ −1 > 1là P.V số Xét tập FractalEp,b được sinh bởi hệ hàm lặp
Khi λ = 1 3 ;m = 3;p1 = p2 = p3 = 1b1 = 0;b2 = λ 3 ;b3 = 2 3 thìE p,b được gọi là tập λ−Cantor và đã được nhiều người nghiên cứu về độ đo, chiều và cấu trúc của nó, ký hiệu C λ
Khi λ ∈ Q thì Furstenberg dự đoán dim H E p,b = 1 và Hochman đã chứng minh dự đoán này.
Khi λ = p q ∈ Qvà p≡ q(mod3), q 6= 0thì IF S thỏa mãn OSC và ngược lại. Khi λ = n 1 , chưa kết luận được OSC thỏa mãn khi n, b i như thế nào.
Khi λ = n 1 , p 1 = p 2 = = p m = 1 kết quả là OSC thỏa mãn khi và chỉ khi dim H E p,b = dim S E p,b Khidim S E p,b = 1thì OSC thỏa mãn khi và chỉ khiE o p,b 6= ∅.
Đồ thị và đường đi
Đồ thị có hướng được định nghĩa là một cặp sắp thứ tự G = (V, E), trong đó V là tập hợp không rỗng các đỉnh của đồ thị và E là tập hợp các cặp có sắp thứ tự của hai đỉnh, được gọi là các cung (cạnh) của G Mỗi cung được ký hiệu là e = uv với u, v thuộc V.
Trong đồ thị G = (V, E), hai đỉnh u và v được kết nối bằng một đường đi có chiều dài k, tạo thành một dãy đỉnh và cạnh liên tiếp Đường đi này được biểu diễn dưới dạng v0e1v1e2 vk−1ekvk, với v0 = u và vk = v Các cạnh ei được xác định là vi−1vi cho i = 1, , k.
Đồ thị G = (V, E) được gọi là đồ thị có trọng số khi mỗi cạnh e được gán với một số thực, ký hiệu là w(e) Số thực này được gọi là trọng lượng của cạnh e.
1.6.3 Bài toán tìm đường đi ngắn nhất
1.6.3.1 Bài toán Cho G = (V, E) có trọng số dương (w(uv) > 0 với mọi u khácv) Tìm đường đi ngắn nhất từ u đếnv vớiu, v ∈ V.
1.6.3.2 ý tưởng của thuật toán ([10]) Xác định tuần tự các đỉnh có khoảng cách đếnu từ nhỏ đến lớn.
1 Trước tiên đỉnh có khoảng cách nhỏ nhất đếnulà u.
2 Trong V\ {u} tìm đỉnh có khoảng cách đến u nhỏ nhất (đỉnh này phải là một trong các đỉnh kề với u) giả sử đó làu 1
3 TrongV\ {u, u 1 }tìm đỉnh có khoảng cách đến unhỏ nhất (đỉnh này phải là một trong các đỉnh kề với uhoặc u 1 ) giả sử đó làu 2
4 Tiếp tục như trên cho đến khi tìm được khoảng cách từu đến v.
Bước 1 Xuất phát từ đỉnh a, gán L(a) := 0 Với mọi đỉnh x 6= a ta gán
L(x) := ∞ Đặt T := V (V là tập các đỉnh).
Bước 2 Chọn v ∈ T, v chưa xét sao cho L(v) có giá trị nhỏ nhất ĐặtT 1 :T\ {v}, đánh dấu đỉnhv đã xét.
Nếu T1 = ∅, quá trình kết thúc và L(z) sẽ là chiều dài đường đi ngắn nhất từ đỉnh a đến mọi đỉnh z ∈ V (z ≠ a) Đường đi ngắn nhất được xác định từ các đỉnh đã được ghi nhớ, trong đó nếu L(z) = ∞, điều này có nghĩa là không tồn tại đường đi đến đỉnh z.
Ngược lại ta sang bước 4.
Bước 4 Với mỗix ∈ T kềvta gánL(x) := min{L(x), L(x) +w(v, x)} Nếu
L(x)thay đổi thì ghi nhớ đỉnhv cạnh đỉnhxđể sau này tìm đường đi ngắn nhất.Quay về bước 2.
Thuật toán kiểm tra điều kiện tập mở đối với một lớp hệ hàm lặp 14
Cơ sở của thuật toán
Cố địnhp = (p 1 , , p m )với p i ∈ N, b = (b 1 , , b m ) vớib i ∈ Q, λ −1 là số Pisot. Xét hệ hàm lặp
|b i |, T = max i=1,m p i , E là tập bất biến của IFS và Σ = {1, , m} ∞ ,Σ ∗ = ∪ k≥1{1, , m} k Với u ∈ Σ ∗ , v ∈ Σ hay v ∈ Σ ∗ viết w = u ì v là sự ghép u với v, ký hiệu v ≺ w và v = w\u, [i] k = i i
Với σ ∈ Σ ∗ suy ra σ = (i 1 , , i k ) với k ∈ N nào đó vài 1 , , i k ∈ Σ.
= h (p 1 +p 2 ,λ p 1 b 2 +b 1 )(x) và h (p,b) ◦h (−p,−λ −p b) = h (p+(−p),λ p (−λ −p b)+b) = h (0,0) Suy ra(ZìR) là một nhóm với phép toán hợp và phần tử đối là
Với mỗii ∈ Σ thì tồn tại(p i , b i ) ∈ (NìR) : S i (x) =h (p i ,b i ) , và vớiσ = i 1 i k , theo phép toán hợp xây dựng ở trên ta có
Z − Z={P: Plà đa thức với hệ số trong B −B},
Với các ký hiệu ở trên, ta có kết quả sau
Chứng minh.Với σ = i 1 i k , ta có S σ (x) = S i 1 ◦ ◦S i k (x) Ta có:
Trong đó: p σ = p i 1 +p i 2 + +p i k , Q∈ Z và deg (Q) = pi 1 + +pi k−1 < pσ.
Ta có deg (Q) ≤ p τ + T − 2, và vì |p σ − p τ| < T − 1, suy ra p σ < p τ + T − 1 Đồng thời, deg (Q) = p σ − p i k ≤ p σ − 1 ≤ p τ + T − 2, và λ − p τ [Q(λ) − P(λ)] = λ T − 2 R λ − 1 khi |p σ − p τ| < T − 1 với R(λ) ∈ Z − Z Do đó, π R (p τ, b τ) − 1 (p σ, b σ) = λ T − 2 R λ − 1 khi R(λ) ∈ Z − Z Định nghĩa: Hệ hàm lặp thỏa mãn WSP (Weak Separation Property) khi và chỉ khi ánh xạ đồng nhất id không thuộc.
2.1.4 Mệnh đề([5]).Với hệ hàm lặp đã cho thì điều kiện WSP được thỏa mãn. Chứng minh.Ta cóS τ −1 ◦S σ (x) =λ p σ −p τ x+π R h (p τ , b τ ) −1 (p σ , b σ ) ivíi|p σ −p τ | ≤
: R ∈ Z − Z và theo Bổ đề 2.1.2 thì
: R ∈ Z − Z giảm dần. Để ý rằng nếuS τ −1 ◦S σ gần với ánh xạ đồng nhất idthì π R h (p τ , b τ ) −1 (p σ , b σ ) i
Vậy, hệ hàm lặp đã cho thỏa mãn điều kiện WSP. Để ý rằng OSC kéo theo WSP, nhưng chiều ngược lại thì không đúng.
Tuy nhiên ta có kết quả sau.
2.1.5 Mệnh đề([5]).Tập bất biến của hệ hàm lặp trong R n thì không nằm trong một siêu phẳng Do đó, hệ hàm lặp đã cho thỏa mãn OSC khi và chỉ khi thỏa mãn WSP và S σ 6= S τ khi σ 6= τ với σ, τ ∈ Σ ∗
Từ Mệnh đề 2.1.4 và Mệnh đề 2.1.5 ta có hệ quả sau.
2.1.6 Hệ quả ([5]) Hệ hàm lặp {S i } m i=1 thỏa mãn điều kiện OSC khi và chỉ khi
S i (E) thì tồn tại i ∈ {1, , m} để x = Si(x) = λ p i x+bi hay x−λ p i x = bi Do đó,
Dopi ∈ Nvà λ 1 > 1nếu λ 1 là P V số, đặt
Khi đó,C là tập hữu hạn và lực lượng của nó được ước tính là
(|1−η i |) trong đó,η 1 , , η l là các liên hợp đại số củaλ −1 với|η i | < 1với mọii = 1,2, k. Chứng minh Để ý rằng với bất kỳ R ∈ Z − Z thì các hệ số củaR đều thuộc
B −B, với B = {b 1 , b 2 , , b m } ⊂ Z, cho thấy các hệ số của R không vượt quá 2b 0 Do đó, với λ −1 là P.V có các liên hợp đại số η 1 , η 2 , , η l thỏa mãn |η i | < 1 cho mọi i = 1,2, , l, theo Định lý 1.5.3, ta có R λ −1.
Do đó, với c, c 0 ∈ C thì hoặc c = c 0 hoặc
Từ cách xác địnhC, ta suy ra
Vậy, ta có điều phải chứng minh.
2.1.9 Mệnh đề([5]).NếuS σ = S τ vớiσ 6= τ, σ, τ ∈ Σ ∗ thì luôn tồn tại số nguyên
M và hai dãy{σ k } M k=1 và {τ k } M k=1 ⊂ Σ ∗ sao cho σ M = σ vàσ M = τ và với mọik ≥ 1ta có σ k ≺σ; τ k ≺ τ, và p σ k , p τ k ∈ ((k −1)T, kT], (p τ k , b τ k ) −1 (p σ k , b σ k ) ∈ Ξ.
Chứng minh Giả sử p σ = p τ ∈ ((M −1)T, M T] với k < M, ta lấy σ k hay τ k ngắn nhất củaσ hayτ sao chop σ k , p τ k ∈ ((k−1)T, kT].
Lấy σ M = σ, σ M = τ Lấy α 0 = σ 1 , β 0 = τ 1 với |α 0 | = |β 0 | = 1 và α k σ k+1 \σ k ; β k = τ k+1 \τ k víik ≥ 1.
Khi đó, ta có1 ≤pα k , pβ k ≤ 2T −1với mọik ≥ 0 Vìpσ k , pτ k ∈ ((k −1)T, kT] nên ta có|p σ k −p τ k | ≤ T −1với mọi k, nghĩa là ta có π Z h (p τ k , b τ k ) −1 (p σ k , b σ k ) i ≤ T −1.
Do đó, S σ (E) = S τ (E), kéo theo S σ k (E) ∩ S τ k (E) 6= ∅ hay ta có E ∩
Theo NhËn xÐt 2.1.6 (i) ta cãE ⊂ x : |x| ≤ 1−λ b 0 , nên π R h (pτ k , bτ k ) −1 (pσ k , bσ k ) i
1−λ. Theo Bổ đề 2.1.2, ta cóπ R h (p τ k , b τ k ) −1 (p σ k , b σ k ) i
. 2.1.10 Định nghĩa([5]) Giả sử{α k } t k=0 và {β k } t k=0 ⊂ Σ ∗ vớit ∈ Nhayt = ∞.
Ta nói rằng{(q k , c k )} t+1 k=1 cócấu trúc đệ quyđối với {α k } t k=0 ,{β k } t k=0 nÕu (q 1 , c 1 ) = (p β 0 , b β 0 ) −1 (p α 0 , b α 0 ) (q k+1 , c k+1 ) = (p β k , b β k ) −1 (q k , c k ) (p α k , b α k ) víi 1≤ k ≤t.
2.1.11 Định lý([5]).Hệ hàm lặp {λ p i x+b i } m i=1 không thỏa mãn OSC nếu và chỉ nếu tồn tại số nguyên dương M và các dãy {α k } M k=0 ,{β k } M k=0 ⊂ Σ ∗ với1 ≤ p α k , p β k ≤ 2T −1và |α 0 | = |β 0 | = 1, α 0 6= β 0 sao cho với mọi k ≥ 1ta có
( (q M +1 , c M +1 ) = (0,0) (q k , c k ) ∈ Ξ mà{(q k , c k )} M k=1 +1 có cấu trúc đệ quy đối với
Hệ hàm lặp thỏa mãn điều kiện SSC sẽ đồng thời thỏa mãn điều kiện OSC Do đó, các kết quả nghiên cứu sẽ tập trung vào việc xác định các điều kiện cần và đủ để hệ hàm lặp hoạt động hiệu quả.
{λ p i x+b i } m i=1 thỏa mãn điều kiện SSC.
2.1.12 Mệnh đề([5]).Giả sửi 1 , i 2 , ;j 1 , j 2 , ∈ Σ.NếuS i 1 ,i 2 , (E) =S j 1 ,j 2 , (E) thì tồn tại các dãy {σk} k và {τk} k ⊂ Σ ∗ sao cho với mọi k ≥ 1 ta có σk ≺ i1i2 và τ k ≺ j 1 j 2 thỏa mãn
Chứng minh Với bất kỳ k ≥ 1, ta cố định σk ngắn nhất của i1i2 sao cho p σ k ∈ (kT,(k + 1)T] và lấy τ k ngắn nhất của j 1 j 2 sao cho p τ k ∈ (kT,(k+ 1)T]. V× π Z h
= p σ k −p τ k và p σ k , p τ k ∈ ((k −1)T, kT) ta suy ra π Z h (p τ k , b τ k ) −1 (p σ k , b σ k ) i
Từ giả thiếtS i 1 ,i 2 , (E) =S j 1 ,j 2 , (E) ta suy ra S σ k (E)∩S τ k (E) 6= ∅hay
Từ Nhận xét 2.1.7(i) làE ⊂ x : |x| ≤ max|b i | i
Theo Bổ đề 2.1.2, ta cóπ R h (p τ k , b τ k ) −1 (p σ k , b σ k ) i
. 2.1.13 Mệnh đề ([5]) Giả sử i 1 , i 2 , ;j 1 , j 2 , ∈ Σ Nếu với mỗi k ≥ 1 tồn tại σk ≺ i1i2 và τk ≺j1j2 sao cho pσ k , pτ k ∈ ((k−1)T, kT] và π R h
Chứng minh.Xét khoảng cách giữaS σ k (0)và S τ k (0) Ta có:
(p τ k , b τ k ) −1 (p σ k , b σ k )i nên S τ −1 k Sσ k (0) = πR h (pτ k , bτ k ) −1 (pσ k , bσ k ) i Điều này kéo theo
Do đó, khi chok → ∞ta có S i i (0) = S j j (0) Như vậy, ta có
Từ Mệnh đề 2.1.12 và 2.1.13 ta thu được kết quả sau.
2.1.14 Định lý ([5]) Hệ hàm lặp {λ p i x+bi} m i=1 không thỏa mãn điều kiện SSC khi và chỉ khi tồn tại các dãy{α k } ∞ k=0 ,{β k } ∞ k=0 trongΣ ∗ với1 ≤p α k , p β k ≤ 2T −1với mọi k và |α 0 | = |β 0 | = 1, α 0 6= β 0 , sao cho (q k , c k ) ∈ Ξ với k ≥ 1 trong đó (q k , c k ) k , có cấu trúc đệ quy đối với ({α k } ∞ k=0 ,{β k } ∞ k=0 ).
Chứng minh Nếu hệ hàm lặp đã cho không thỏa mãn điều kiện SSC thì tồn tại i 1 i 2 và j 1 j 2 ∈ Σvới i 1 6= j 1 sao cho
Sử dụng phương pháp như trong chứng minh Mệnh đề 2.1.12, ta có dãy {σ k } k ;{τ k } k với σ1 = i1 = α0 và τ1 = j1 = β0.
Khi đó, lấy(q k , c k ) = (p τ k , b τ k ) −1 (p σ k , b σ k ); α k = σ k+1 \σ k và β k = τ k+1 \τ k với
Theo Mệnh đề 2.1.12, ta có(q k , c k ) ∈ Ξvới mọi k ≥ 1.
Nếu tồn tại các dãy {α k } k≥0 và {β k } k≥0 trong Σ ∗ thỏa mãn giả thiết của định lý, ta định nghĩa σ k = α 0 ∗α 1 ∗α k−1 và τ k = β 0 ∗β 1 ∗β k−1 Khi k tiến tới vô cùng, tồn tại các phần tử 1, 2, và j 1, j 2, trong Σ sao cho σ k ≺ i 1, i 2, và τ k ≺ j 1, j 2, với mọi k và π R h (p τ k , b τ k ) −1 (p σ k , b σ k )i.
Theo Mệnh đề 2.1.13 và Định nghĩa 1.3.2, ta suy ra hệ hàm lặp không thỏa mãn SSC.
Vậy, ta có điều phải chứng minh.
Đồ thị và thuật toán
Phần này trình bày thuật toán kiểm tra với hai bộ giá trị (p1, , pm) ∈ N m và
(b 1 , , b m ) ∈ Z m như thế nào thì hệ hàm lặp S = {λ p i x+b i } m i=1 (λ −1 là P.V số) thỏa mãn điều kiện tập mở.
2.2.1 Các ký hiệu 1) Với T = max i=1,m p i , b 0 = max i=1,m
1−λ ;x = λ T −2 R λ −1 víi R ∈ Z − Z } ta ký hiệu Ξ = {n∈ Z : |n| ≤ T −1} ì C = {(n, x) : n ∈ Z : |n| ≤T −1, x ∈ C} và được gọi làtập đỉnh, mỗi đỉnhlà v = (p, b) ∈ Ξ.
2) Giả sử (p, b) và (p 0 , b 0 ) là hai đỉnh Ta nói có một cạnh trực tiếp e từ đỉnh (p, b) đến (p 0 , b 0 ) nếu và chỉ nếu tồn tại α, β ∈ Σ ∗ sao cho
(chẳng hạn α = α1 αk ∈ Σ k thì pα = pα 1 + +pα m < 2T −1) sao cho
Ký hiệu tập các cạnh làL ={(α, β) : α, β ∈ Σ ∗ ;α, β thỏa mãn (1)}.
2.2.2 Định nghĩa ([7]) Tập sắp thứ tự gồm các bộ đỉnh và cạnh G = (Ξ, L) trong đó Ξ và L được xác định như ở phần Các ký hiệu 2.2.1 được gọi là đồ thị tương ứng với hệ hàm lặp {S i } m i=1 = {λ p i x+b i } m i=1
2) Vìλ p i (b j −b i ) ∈ Z − Z nên mỗi phần tử trongΛlà
(p i , b i ) −1 (p j , b j ) = (p j −p i ;λ −p i (b j −b i )) thỏa mãn pj −pi ∈ Z, |p j −pi| ≤max{p j , pi} −1 = T −1 vàλ −p i (b j −b i ) ∈ Z − Z nên λ −p i (b j −b i ) ∈ C Do đó, ta cóΛ ⊂ Ξ.
Vì với bất kỳR k ∈ Z −Z vớideg (R k ) = k, luôn tồn tại đa thứcR k−1 ∈ Z −Z với deg (R k−1 ) =k −1và b ∈ B −B sao cho
∈ D k V× thÕ, ta cã thÓ biÓu diÔn
2.2.4 Định lý ([7]) Cho hệ hàm lặp {λ p i x+ b i } m i=1 Khi đó, hệ hàm lặp không thỏa mãn OSC khi và chỉ khi tồn tại một đường đi trong G xuất phát từ một đỉnh trong Λvà kết thúc tại đỉnh (0,0).
Chứng minh Từ Định lý 2.1.11 và Định nghĩa 2.2.2 ta có điều phải chứng minh.
2.2.5 Định lý([7]) Hệ hàm lặp trong Định lý 2.2.4 không thỏa mãn SSC khi và chỉ khi tồn tại một đường đi vô hạn trong G xuất phát từ một đỉnh thuộcΛ.
Chứng minh Từ Định lý 2.1.14 và Định nghĩa 2.2.2 ta có điều phải chứng minh.
Dựa trên các kết quả đã trình bày, chúng ta sẽ phát triển thuật toán để kiểm tra xem hệ hàm lặp {λ p i x + bi} m i=1 với λ −1 > 1 có phải là P.V số cố định hay không, trong đó (p1, , pm) ∈ N m và (b1, , bm) ∈ Q m là các tham số thỏa mãn điều kiện OSC.
Bước 1 Nếu (b 1 , , b m ) ∈ Q m nhưng không thuộc Z m , ta lấy a là mẫu số chung bé nhất của b 1 , , b m Khi đó, (b 0 1 , , b 0 m ) ∈ Z m với b 0 i = b i a, với mỗi i = 1, , m.
Khi đó, dễ chứng minh được hệ hàm lặp{λ p i x+bi} m i=1 thỏa mãn OSC khi và chỉ khi hệ hàm lặp {λ p i x+b 0 i } m i=1 thỏa mãn OSC.
Do đó, ta xét trong trường hợp(b 1 , , b m ) ∈ Z m
Bước 2 Tìm tập các đỉnhΞ = {n ∈ Z : |n| ≤T −1} ì C, thực chất là tìm tập
Với các đánh giá như ở Nhận xét 2.2.3 ta tìmC như sau.
Do đó, lấy y ∈ B −B và kiểm tra xem
1−λ có đúng hay không Nếu đúng thì y ∈ D 0 , ngược lại thì y /∈ D 0
Do đó, lấy y ∈ λ −1 D 0 +B −B hay y = λ −1 (bi −bj) +bk −bl với |b i −b j | ≤ d;b i , b j , b k , b l ∈ {b 1 , , b m } và kiểm tra xem |y| ≤ d có đúng không để tìm D 1
Cứ tiếp tục như vậy để tìmD 2 ,D 3 ,
Nếu tìm đượck0 bé nhất sao choD k 0 +1 = D k 0 thì lấyD = D k 0
Khi đó, ta tìm đượcC, tức tìm được tập các đỉnh Ξ.
Bước 3.Vẽ tất cả các cạnh trong đồ thịGkhi tìm được tập các đỉnhΞở Bước 2.
Ta cã Ξ = ([−T + 1,T−1]∩Z)× C. Lấy hai đỉnh(p, b),(p 0 , b 0 ) ∈ Ξ, kiểm tra xem có tồn tại α, β ∈ Σ ∗ với α = i 1 i 2 i k , β = j 1 j 2 j l sao cho
1 ≤ pi 1 +pi 2 + +pi k , pj 1 +pj 2 + +pj l ≤ 2T −1 tức
Nếu tìm được các giá trị α và β thỏa mãn điều kiện (*) thì sẽ có một cạnh nối hai đỉnh (p, b) và (p0, b0) Điều này cho phép chúng ta xác định tất cả các đường đi từ đỉnh này đến đỉnh kia trong đồ thị G, vì số lượng các cạnh là hữu hạn.
Bước 4 là kiểm tra xem có đường đi từ đỉnh trong Λ đến đỉnh (0,0) hay không Nếu có, hệ hàm lặp sẽ không thỏa mãn điều kiện OSC Ngược lại, nếu không tồn tại đường đi, hệ hàm lặp sẽ thỏa mãn điều kiện OSC.
Tương tự, nếu tồn tại đường đi vô hạn trongG, xuất phát từ một đỉnh trong
Gthì hệ hàm lặp không thỏa mãn SSC Ngược lại hệ hàm lặp thỏa mãn SSC suy ra thỏa mãn OSC.
2.2.7 Nhận xét([7]) 1) KhiT = 1, tức max{p 1 , , p m } = 1với p i ∈ N ∗ suy ra p1 = = pm = 1.
= 0 nên mỗi đỉnh(q, c) phải cóq = 0.
VìF = {1, , m} nên pσ k ◦pτ k = k ∈ {1, , m}, do đó ta có π R h (p τ k , b τ k ) −1 (p σ k , b σ k ) i = |x 1 −x 2 | ≤ b∈B−B max 1−λ |b| víi x 1 , x 2 ∈ E.
Do đó, tập đỉnh trong trường hợpT = 1là Ξ = {0} ×C 0 = {0} ×{x : |x| ≤ max b∈B−B |b|
Trong trường hợp này, việc kiểm tra xem hệ hàm lặp có thỏa mãn điều kiện OSC hay không trở nên đơn giản, vì chúng ta có khả năng đánh giá lực lượng C 0 một cách dễ dàng.
2) Khi λ −1 ∈ Nthì ta đánh giá được
2.2.8 Mệnh đề ([7]) Với Thuật toán 2.2.6 thì thời gian chạy của thuật toán (độ phức tạp của thuật toán) được ước lượng là i) Thời gian kiểm tra hệ hàm lặp thỏa mãn OSC là t≤ c.(#Ξ) 2 +m 4T (#Ξ) + (m+ 1) 2 ii) Thời gian kiểm tra IFS thỏa mãn SSC là t 0 ≤c.(#Ξ) 3 +m 4T (#Ξ) + (m+ 1) 2 Trong đóc là hằng số trong thuật toán nguyên thủy của Dijkstra và
Chứng minh.Trong Bước 2, thời gian để tìm tập đỉnh được đánh giá là t 1 = #Ξ ≤ k o
Thời gian tìm các cạnh ở Bước 3 là : Ta cần tìm
Số bước cần thực hiện để tìm cạnh được xác định bởi công thức t 2 ≤ #Ξ.(#F) 2 ≤ m 4T #Ξ Thời gian để kiểm tra thỏa mãn điều kiện OSC ở Bước 4 là t 3 ≤ c.(#Ξ) 2, trong khi thời gian kiểm tra SSC là t 0 3 ≤ c.(#Ξ) 3.
Do vậy, ta thu được đánh giá về độ phức tạp thuật toán như trên.
Một số ví dụ minh họa
2.3.1 Ví dụ 1Xét λ −1 = 3 > 1là P.V số, m = 3; p = (1; 1; 1) vàb = 2 3 ; 3 n+1 2 ; 0
. Theo bước 1, thay vì xét (b 1 , b 2 , b 3 ) = 2 3 ; 3 n+1 2 ; 0
Khi đó, B −B = {−2.3 n ; 2 (1−3 n ) ;−2; 0; 2; 2 (3 n −1) ; 2.3 n }, vì p 1 = p 2 p3 = 1nên T = 1suy ra E = {1,2,3}.
Theo Nhận xét 2.2.7, ta có C 0 ={m : m chẵn và m ∈
Từ bước 3, bước 4 của thuật toán ta có đường đi là
Do đó, hệ hàm lặp này không thỏa mãn SSC và OSC Vì thế, tập bất biếnE của hệ hàm lặp này có chiều Hausdorff là dim H E 6= 1 = dim s E.
Vì các hệ số đồng dạng c1 = c2 = c3 = 1 3 nên dimsE = s là nghiệm của phương trình: 3 1 3 s
= 1, suy ras = 1. Khi đó, ta cũng cóE o = ∅.
Lấyλ = 1 3 và xét hệ hàm lặp với p = (1; 1; 2), b = 11 18 ; 0; 2 3
Lấy a = 18và b bởi − b = (11; 0; 12) Suy raB = {0; 11; 12}, từ đó ta cóB−B = {−12;−11;−1; 0; 1; 11; 12}. Với T = 2, khi đó ta có d = λ
1−λ = 72 Dùng bước 2 của thuật toán ta có: C = [−72; 72] ∩Z và Ξ = {−1,0,1} ì C.
Trong bước 3 và 4, chúng ta nhận thấy rằng đường đi trực tiếp không bắt nguồn từ bất kỳ đỉnh nào trong tập hợp Λ và kết thúc tại tọa độ (0; 0) Do đó, hệ hàm lặp này thỏa mãn điều kiện OSC.
Tuy nhiên, ta có đường đi trực tiếp vô hạn là:
Vậy SSC không thỏa mãn.
2 + 1là P.V số và gọi là tỉ số bạc (silver) XÐt p = (2; 1; 1), b = 2 5 ; 1 2 ; 0
2 Thực hiện bước 2 suy ra E chứa 1059 phần tử.
Theo phương pháp kiểm tra, thực hiện bước 3, 4 của thuật toán ta có đường :
∈ Λ.Vậy OSC và SSC đều không thỏa mãn.
Luận văn đã đạt được các kết quả sau
1 Hệ thống được các điều kiện cần, điều kiện cần và đủ, điều kiện đủ để hệ hàm lặp thỏa mãn OSC.
2 Trình bày và chứng minh chi tiết Bổ đề 2.1.2, Mệnh đề 2.1.9, các cơ sở toán học để xây dựng thuật toán kiểm tra một lớp hệ hàm lặp {λ p i x+b i } m i=1 với λ −1 > 1là P.V số, p i ∈ N, b i ∈ Q, i = 1, m thỏa mãn OSC, SSC dựa vào đồ thị và ® êng ®i.
3 Lấy các ví dụ minh họa thuật toán trong các trường hợp là: Hệ hàm lặp không thỏa mãn OSC, SSC, và Hệ hàm lặp thỏa mãn OSC nhưng không thỏa mãnSSC. tài liệu tham khảo
[1] A Chief (1994), Separation properties for self-similar set, Proc Amer Math. Soc., 122, 995 -1001.
[2] A M Garsia (1962), Arith properties of Bernoulli convolutions, Trans Amer. Math Soc., 102, 409 -432.
[3] C Bandt, N.V Hung and H Rao (2005), On the open set condition for sefl- similar fractals, Proc Amer Math Soc., 134, 1369 -1374.
[4] C Bandt and N.V Hung (2008), Self-similar sets with open set condition and great variety of overlaps, Proc Amer Math Soc., 136, 3895 -3903.
[5] C Bandt and S Graf (1992), Self - Similar sets VII A characterization of self- similar fractal with positive Hausdorff measure, Proc Amer Math Soc., 114,
[6] K S Lau, S M Ngai (2007), A generalized finite type condition for iterated function systems, Adv Math., 208, (2) 647 - 671.
[7] H Q Guo, Q Wang and L F Xi (2014), Algorithms to test open set condition for self - similar set related to p.v.numbers, Math Subject Clasification 28A80.
[8] J E Hutchinson (1981), Fractals and self similarity, Indiana Univ Math J.,
[9] K J Falconer (1990),Fractal Geometry- Mathematical Foundations and Appli- cations, John Wiley Sons.
[10] N D Lau and T N Viet (2012),Thuat toan Dijkstra , Tap chi khoa hoc- Dai hoc Hue, 5, 81-92.