Tài liệu Phép nội suy fractal

Soá hoùa bôûi Trung taâm Hoïc lieäu .. http://lrc.tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG LÝ THỊ THU HÀ PHÉP NỘI SUY FRACTAL LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2013 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG LÝ THỊ THU HÀ PHÉP NỘI SUY FRACTAL Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN HỮU ĐIỂN Thái Nguyên – 2013 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ MỞ ĐẦU 1. Đặt vấn đề Chúng ta đều biết rằng hình học Euclide cho phép vẽ và đo đạc các hình có dạng là các đường thẳng và các đường cônic. Tuy nhiên trong thực tế không phải lúc nào chúng ta cũng chỉ đo đạc với các đường này. Một minh chứng là, để đo đoạn bờ biển từ một địa điểm A đến địa điểm B nào đó, ta có thể sử dụng compa với độ mở 1 mét và tiến hành đo sát mép nước. Đây là cách làm mà chúng ta thường hay nghĩ tới. Tuy nhiên khi đo như vậy, ta đã bỏ qua các lồi lõm nhỏ hơn 1 mét. Thu hẹp độ mở của compa còn 100cm ta tính thêm được một số chỗ lồi lõm, và thu được giá trị lớn hơn và chính xác hơn chút nữa. Cứ tiếp tục làm như vậy ta tiến dần tới giới hạn thực của địa điểm A và địa điểm B. Việc làm trên đây thực chất là ta thay đổi một đường cong thực quá gồ ghề khúc khủy bằng các phép đo liên tiếp theo độ mở giảm dần của compa. Vì chiều dài bờ biển không thể vô tận nên các phép đo này phải hội tụ. Đối với hình học Euclide thì là đúng. Chẳng hạn đối với một đường tròn, phương pháp tổng các dây cung ngày một ngắn và hội tụ đến chu vi hình tròn. Nhưng đó là các hình Euclide mà ta quen thuộc từ hàng ngàn năm nay như tam giác, tứ giác.... Ta thấy được rằng, khi thu nhỏ độ mở của compa ta luôn luôn phát hiện những ―eo biển‖ nhỏ hơn, do vậy giá trị độ dài thực của bờ biển tăng lên mãi đến vô cùng. Nói một cách sâu xa hơn, phép đo Euclide thông thường không phản ánh được các hình dáng gồ ghề, phức tạp của các hình thể tồn tại trong thực tế. Những đường gồ ghề ấy được gọi là các hình Fractal. Ra đời muộn trong các phân môn của hình học, Fractal - hình học phân dạng là cái tên xuất hiện lần đầu vào năm 1975 bởi nhà toán học Benoit Mandelbrot mang hai quốc tịch Pháp - Mỹ. Thuật ngữ Fractal và những ảnh hình dựa trên "sự tự đồng dạng" đã gây ấn tượng rõ rệt đối với nhiều người, trong đó có cả những người không hề có một chút kiến thức khoa học nào. Nó làm cho họ bị sốc nhưng thú vị. Còn đối với riêng Mandelbrot, nó làm cho ông thích thú, vì toán học vốn là một khoa học nổi tiếng khô khan và kỳ quái đã trở thành một cái gì đó rất thiết thực và gần gũi. 1 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ Hiện nay, vẫn còn rất nhiều vấn đề về lý thuyết Fractal vẫn đang được tiếp tục nghiên cứu. Một trong các vấn đề được quan tâm đó là hàm nội suy Fractal. Trước đây, các bài toán nội suy đã được đề cập. Vậy bài toán về nội suy Fractal có gì khác biệt với những bài toán nội suy trước đó? Đây cũng chính là lý do em chọn làm đề tài nghiên cứu khoa học của mình: ‖Phép nội suy Fractal‖ với mục tiêu nắm bắt những kiến thức cơ bản về Hình học Fractal, hàm Ftactal và tìm hiểu về nội suy Fractal có gì khác biệt với các bài toán nội suy trước đó. 2. - Đối tượng nghiên cứu: phép nội suy fractal. trúc về Fractal, các phép nội suy thông thường và đi sâu nghiên cứu về hàm nội suy Fractal. 3. Hƣớng nghiên cứu của đề tài - Tìm hiểu tổng quan về Fractal - Tìm hiểu các phép nội suy thông thường - Tìm hiểu về phép nội suy Fractal - Lập trình tính các giá trị nội suy theo phương pháp nội suy Fractal 4. Phƣơng pháp nghiên cứu - Nghiên cứu các tài liệu và viết tổng quan, phương pháp phân tích và thiết kế đối tượng và phương pháp thử nghiệm 5. Ý nghĩa khoa học của đề tài - Bản thân hiểu sâu về hình học Fractal. - Xây dựng được chương trình nội suy Fractal từ đó rút ra sự khác biệt với các bài toán nội suy thông thường. 2 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ CHƢƠNG I: TỔNG QUAN VỀ FRACTAL 1.1. Các khái niệm cơ bản về không gian của Fractal Tại sao hình học thường bị ví như ―lạnh‖ và ―khô‖ ? Một lí do nằm trong sự thiếu khả năng của nó trong mô tả hình đám mây, núi, bờ biển hay cây cối. Mây không phải là hình cầu, núi không phải là hình nón, bờ biển không phải là đường tròn, và vỏ cây thì không phải là trơn phẳng, tia sét cũng không đi theo một đường thẳng. Sự ra đời của lý thuyết hình học Fractal là kết quả của nhiều thập kỷ nỗ lực giải quyết các vấn đề nan giải trong nhiều ngành khoa học chính xác, đặc biệt là vật lý và toán học. Một cách cụ thể, lý thuyết hình học Fractal được xây dựng dựa trên 2 vấn đề lớn được quan tâm ở những thập niên đầu thế kỷ 20. Các vấn đề đó bao gồm: + Tính hỗn độn của các quá trình phát triển có quy luật trong tự nhiên. + Sự mở rộng khái niệm số chiều và độ đo trong lý thuyết hình học Euclide cổ điển. Năm 1979, nhà toán học Benoit Mandelbrot áp dụng tập Mandelbrot đầy kì ảo lên máy tính. Ông đã khám phá ra một lãnh vực hình học mới đầy thú vị cho phép phản ánh thế giới thực một cách tự nhiên hơn so với hình học Euclide. Tất cả những hình ảnh mà ta thường gặp trong tự nhiên như : núi, mây, sông, nước… nay máy tính đã có khả năng mô tả được bằng phương pháp Fractal. Để thấy rõ hơn sức mạnh của Fractal trong mô tả tự nhiên bạn có thể xem thêm bộ sưu tập ảnh Fractal kèm theo. Hình 1.1. Ảnh Fractal 3 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ . Trong giai đoạn này B. Mandelbrot và các nhà toán hoc khác như A.Douady và J.Hubbard đã đặt nền móng và phát triển lí thuyết cho hình học Fractal. Các kết quả đạt được chủ yếu tập trung ở các tính chất của các cấu trúc Fractal cơ sở như tập Maldenbrot và tập Julia. Ngoài ra các ngiên cứu khác cũng cố gắng tìm kiếm mối quan hệ giữa các cấu trúc này, ví dụ như mối quan hệ giữa Maldenbrot và Julia. Dựa trên các công trình của Maldenbrot (trong những năm 1976, 1979, 1982) và Hutchinson(1981), vào các năm 1986,1988 Michael F.Barnsley và M.Begger đã phát triển lý thuyết biểu diễn các đối tượng tự nhiên dựa trên cơ sở lý thuyết về các hệ hàm lặp IFS. Các hệ hàm lặp này bao gồm một bộ hữu hạn các phép biến đổi affine cho phép với sự giúp đỡ của máy tính tạo nên hình ảnh của các đối tượng trong tự nhiên. Theo lý thuyết này hình học Euclide cổ điển rất có hiệu lực trong việc biểu diển các đối tượng nhân tạo như một tòa nhà, một cổ máy nhưng lại hoàn toàn không thích hợp cho việc biểu diễn các đối tượng của thế giới thực vì đòi hỏi một lượng quá lớn các đặc tả cần có. Nếu như trong hình học Euclide các yếu tố cơ sở là đường thẳng, đường tròn, hình vuông,… thì lý thuyết IFS mở rộng hình học cổ điển với các yếu tố cơ sở mới là vô số thuật toán để vẽ nên các Fractal của tự nhiên. Chúng ta nghiên cứu phương pháp Fractal được tạo ra bởi ứng dụng của biến đổi đơn giản trong các không gian đơn giản. Chúng ta giải thích hệ hàm lặp (IFS) là gì? và nó có thể định nghĩa Fractal như thế nào? Hệ hàm lặp cung cấp một khung tiện ích cho việc mô tả, phân loại, và liên kết của Fractal. Hai thuật toán, thuật toán lặp ngẫu nhiên và thuật toán xác định, cho việc tính toán ảnh Fractal được trình bày. Đáng chú ý là vấn đề nghịch đảo: đưa đến một tập compact của R2 và làm cách nào để tìm được xấp xỉ Fractal cho nó? Một phần của câu trả lời được cung cấp bởi Định lý Collage. 1.1.1. Các không gian cơ bản và tính chất của chúng Trong hình học Fractal chúng ta quan tâm đến cấu trúc của các tập con của các không gian ―hình học‖ đơn giản khác nhau. Như một không gian được ký hiệu là X. Nó là không gian mà trên đó chúng ta sẽ vẽ các Fractal; Hình học Fractal được 4 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ xây dựng trên cơ sở lý thuyết giải tích hàm, sử dụng các kiến thức về không gian Metric, không gian Hausdorff (còn được gọi là không gian Fractal). Từ nay, với chúng ta, nó chỉ là một tập con của một không gian. Bởi vì không gian đơn giản, tập con Fractal có thể là hình học phức tạp. a. Không gian metric Định nghĩa 1.1.1. Một không gian X là một tập hợp.Các điểm của không gian là các phần tử của tập hợp. Ví dụ. + X = R. Mỗi điểm x X là một số thực, hoặc một đấu chấm trên một dòng. Hình 1.2. Một điểm X R + X = C[0,1], tập hợp các hàm liên tục những hàm trong khoảng [0,1]= {x ∈ R : 0≤ x ≤1} trong R. Một hàm f ∈ X là một hàm f: [0,1]→R. f có thể biểu thị bởi đồ thị của nó. Hình 1.3. Một điểm f trong không gian các hàm liên trục trên đoạn [0, 1]. Định nghĩa 1.1.2. Một không gian metric (X, d) là một không gian X cùng với hàm giá trị thực d: X x X R, d là hàm lấy khoảng cách giữa cặp điểm x và y trong X. Chúng ta yêu cầu d tuân theo những điều kiện sau: a. d(x, y) = d(y, x) b. 0< d(x, y) < x, y x, y X X, x 5 y Soá hoùa bôûi Trung taâm Hoïc lieäu c. d(x, x) = 0 http://lrc.tnu.edu.vn/ x X d. d(x, y) < d(x, z) + d(z,y) x, y, z X Hàm d được gọi là một metric. Ví dụ 1.: Trong không gian X = R2, một điểm x R2 là: + d(x,y) = (Metric Euclid) + d(x,y) = |x1-y1|+|x2-y2| Ví dụ 2. Không gian mã X định nghĩa: d(x, y)=d(x1x2x3…y1y2y3…) = ∑ i xi 1 yi ( N 1) i (∑, d) là một không gian metric. Một không gian metric là một tập hợp của các điểm song song với một hàm mang theo hai yếu tố của tập hợp và đưa ra khoảng cách giữa chúng. Tập hợp có thể là một tập hợp của các điểm hay là một tập hợp của ảnh. Một trong những không gian metric của chúng ta sẽ là tập hợp của tất cả các tập hợp con ( đóng và bị chặn ) của không gian. Tập hợp này có thể tưởng tượng là tập hợp của tất cả các bức tranh đen trắng, trong đó một tập hợp con của không gian được biểu diễn bởi một bức tranh đen tại các điểm của tập hợp con và ở một nơi nào khác màu trắng. Không gian rất lớn, bao hàm, ví dụ, bức vẽ một đường kẻ của bạn, đề địa chỉ United Nations ( cũng như nhiều bức tranh khác ). Định nghĩa 1.1.3. Hai metric d1 và d2 của không gian X là tương đương nếu tồn tại hằng số 0< c1 < c2 < thỏa mãn: c1d1(x, y) < d2(x, y) < c2d1(x, y), (x,y) X x X. Định nghĩa 1.1.4. Hai không gian (X1, d1) và (X2, d2) là tương đương nếu có một hàm h: X1 ~ X2 là ánh xạ 1-1 và ánh xạ lên (nó có nghịch đảo), metric d 1 ~ trên X1 định nghĩa bởi: d 1 (x, y) = d2(h(x), h(y)), x, y X là tương đương với d1. Ví dụ. + X1 = [1, 2], X2 = [0, 1] với d1: Euclide trong X1, d2(x, y) = 2.|x - y| trong X2. Ta có (X1, d1) và (X2, d2) là hai không gian metric tương đương. + X = (0, 1] = {x R: 0< x 1} và d1(x, y) = |x - y| và d2(x, y)= |1/x – 1/y|. Ta có (X, d1) và (X, d2) là hai không gian metric không tương đương. 6 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ Định nghĩa 1.1.5. Một hàm f: X1 X2 từ không gian metric (X1, d1) tới không gian metric (X2, d2) là liên tục nếu với mỗi > 0 và x X1, có một >0 thỏa mãn: d1(x, y) < => d2(f(x), f(y)) < Nếu f là một ánh xạ 1-1 và ánh xạ lên, và do đó có nghịch đảo, và nếu nghịch đảo f-1 của f là liên tục, thì chúng ta nói f là một phép biến đổi topo giữa X1 và X2. Trong trường hợp đó, chúng ta nói rằng X1 và X2 là homeomorphic. * Metric Haudoff Mục tiêu đầu tiên của chúng ta là định nghĩa metric Hausdorff trên không gian này. Metric này sẽ cho chúng ta ―khoảng cách‖ giữa 2 bức tranh bất kì. Metric Hausdorff chính thức được định nghĩa bên dưới. Để tìm thấy khoảng cách Hausdorff h(A,B) giữa hai tập hợp con của không gian, A và B, chúng ta thực hiện thủ tục sau. Với mỗi điểm x A, tìm điểm kết thúc y nằm trong B. Đo các khoảng cách tối thiểu này ( bắt đầu từ A và kết thúc từ B ) và chọn cái lớn nhất. Đây là khoảng cách Hausdorff. Hình 1.4 biểu diễn ba ví dụ của các tập hợp A và B và khoảng cách Hausdorff (dựa trên khoảng cách Euclidean) giữa chúng, đánh dấu bằng một dòng. Metric Hausdorff không nhạy để thỏa mãn, nó không thể lựa chọn khoảng cách giữa hai bức tranh của người là nhỏ hơn khoảng cách giữa một bức tranh người và một bức tranh cây dương xỉ. Hình 1.4: Các tập hợp A và B và khoảng cách Hausdorff giữa chúng, biểu thị bằng một đường kẻ. Trong các ví dụ trên, khoảng cách tối thiểu lớn nhất được đo từ B đến A; trong hai cái khác, nó được đo từ A đến B. b. Chuỗi Cauchy, điểm giới hạn, tập đóng, tập hoàn hảo và không gian metric đầy đủ. 7 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ Hình học Fractal có liên quan tới mô tả, phân loại, phân tích và quan sát của tập con của không gian metric (X, d). Các không gian metric thường là các hình học đơn giản nhưng không phải luôn là như vậy; các tập con thường là những hình học phức tạp. Có một số các tính chất chung của các tập con của không gian metric, nó xảy ra lặp đi lặp lại. Nó là cơ sở, là một phần của từ vựng để mô tả các tập Fractal và các tập con khác của không gian metric. Một số tính chất đóng, mở, tính chất topo. Để nói rằng, chúng bất biến dưới phép biến đổi topo. Định nghĩa 1.1.6. Một chuỗi {xn} n 1 các điểm trong không gian metric (X, d) được gọi là chuỗi Cauchy nếu với một số bất kỳ > 0, có một số nguyên N > 0 sao cho: với d(xn, xm) < n, m > N. Định nghĩa 1.1.7. Một chuỗi {xn} n 1 các điểm trong không gian metric (X, d) được gọi là hội tụ đến điểm x X nếu với một số bất kỳ > 0, tồn tại một số nguyên N > 0 thỏa mãn: d(xn, x) < với n > N. Trong trường hợp này điểm x X, điểm mà chuỗi hội tụ đến, được gọi là giới hạn của chuỗi và chúng ta sử dụng ký hiệu: x= limn xn. Giới hạn x của một chuỗi hội tụ {xn} n 1 có tính chất này: cho B(x, ) = {y X: d(x, y) ký hiệu một hình cầu đóng bán kính > 0 tâm x. Định lý 1.1.1. Nếu một chuỗi các điểm {xn} n d) hội tụ đến điểm x } 1 trong không gian metric (X, X, thì {xn} n 1 là một chuỗi Cauchy. Định nghĩa 1.1.8. Một không gian metric (X, d) là đầy đủ nếu mọi chuỗi Cauchy {xn} n 1 trong X đều có một giới hạn là x X. Một cách khác có thể nói rằng, trong không gian tồn tại một điểm x mà các chuỗi Cauchy đang hội tụ tới. Đương nhiên điểm x này chính là giới hạn của chuỗi. Nếu {xn} n 1 là một chuỗi Cauchy các điểm trong X và nếu X là đầy đủ, thì có một 8 Soá hoùa bôûi Trung taâm Hoïc lieäu điểm x X như vậy, với mỗi http://lrc.tnu.edu.vn/ > 0, B(x, ) chứa xn với những số nguyên vô hạn n. Đôi khi, chúng ta sẽ sử dụng ký hiệu {xn} thay cho {xn} n 1 và lim thay cho limn . Ví dụ: + (R2, metric Euclide) là một không gian metric đầy đủ. + (C[0, 1], D) là một không gian metric đầy đủ. Với D được định nghĩa bởi: D(f, g) = max{|f(s) - g(s)|: s [0, 1]}. Định nghĩa 1.1.9. Cho S X là một tập con của một không gian metric (X, d). Một điểm x {xn} n 1 các điểm xn X được gọi là một điểm giới hạn của S nếu có một chuỗi S \{x} sao cho limn xn=x. Ví dụ: + 0 là một giới hạn của chuỗi {xn} n 1 trong không gian metric ([0, 1], Euclide). Định nghĩa 1.1.10. Cho S X là một tập con của một không gian metric (X, d). Tập bao đóng của S ký hiệu là S , được định nghĩa là S = S {Các điểm giới hạn của S}. S là tập đóng nếu nó chứa tất cả các điểm giới hạn của nó, nghĩa là S = S. S là tập hoàn hảo nếu nó bằng tập của tất cả các điểm giới hạn của nó. Ví dụ. + Tập con S = {x = 1 , n = 1, 2, 3, ...} là tập đóng trong không gian metric n ((0, 1], Euclide). + S = [0, 1] là tập con hoàn hảo trong không gian metric (R, Euclide). c. Tập compact, tập bị chặn, tập mở và biên. Chúng ta tiếp tục mô tả các tính chất cơ bản được sử dụng để mô tả các tập hợp và tập con của các không gian metric. Vậy Fractals ở đâu? Chúng là gì? Chúng ở khắp mọi nơi và bạn sẽ có thể nhìn thấy chúng sớm thôi. Không hẳn là những hình ảnh, nó là những hình chiếu của Fractals. Định nghĩa 1.1.11. Cho S X là một tập con của một không gian metric (X, d). S là tập compact nếu mọi chuỗi vô hạn {xn} n 1 trong S chứa một chuỗi con có giới hạn trong S. 9 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ Định nghĩa 1.1.12. Cho S X là một tập con của không gian metric (X,d). S bị chặn nếu tồn tại một điểm a X và một số R > 0 sao cho: d(a, x) < R x X. Định nghĩa 1.1.13. Lấy S X là một tập con của không gian metric (X, d). S bị chặn hoàn toàn nếu với mỗi > 0, tồn tại một tập hữu hạn các điểm {y1, y2, ., yn} S sao cho với mỗi điểm x X ta có d(xi, yi) < yn}. Tập các điểm {y1, y2, ..., yn} được gọi là một với yi {y1, y2, ..., - net. Định lý 1.1.2. Cho (X, d) là một không gian metric đầy đủ. Cho S X. S là một tập compact nếu và chỉ nếu nó đóng và bị chặn hoàn toàn. Định nghĩa 1.1.14. Cho S X là một tập con của một không gian metric (X, d).S là tập mở nếu với mỗi x S tồn tại >0 sao cho B(x, ) = {y X: d(x, y) } S. Ví dụ. + Nếu (X, d) là một không gian metric thì X là tập mở. + Nếu (X, d) là một không gian metric, thì ―S X là tập mở‖ tương đương ―X\S là tập đóng‖. Định nghĩa 1.1.15. Cho S X là một tập con của không gian metric(X, d). Một điểm x X là điểm biên của S nếu với mọi số > 0, B(x, ) chứa một điểm trong X\S và một điểm trong S. Tập hợp tất cả những điểm biên của S được gọi là biên của S và ký hiệu là S. Định nghĩa 1.1.16. Cho S X là một tập con của không gian metric(X, d). Một điểm x X được gọi là một điểm trong của S nếu có một số B(x, ) > 0 sao cho S. Tập hợp các điểm trong của S được gọi là tập trong cùa S và ký hiệu là S0. Ví dụ. + Cho S là tập con của một không gian metric. Ta có S S + Cho S là một tập con mở trong không gian metric. Ta có S S= + Cho S là một tập con của không gian metric compact. Ta có compact. 10 . S là tập Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ 1.1.2. Không gian của Fractal Chúng ta xét đến không gian lý tưởng để nghiên cứu hình học Fractal. Để bắt đầu, luôn ở mức thấp nhất, chúng ta làm việc trong một số không gian metric đầy đủ như (R2, Euclide) hoặc ( Ĉ , hình cầu), chúng ta ký hiệu bằng (X, d). Nhưng sau đó, khi chúng ta muốn thảo luận về những hình ảnh, tranh, những tập con ―đentrắng‖ của không gian, không gian được giới thiệu là H. Định nghĩa 1.1.17. Cho (X, d) là không gian metric đầy đủ. Ký hiệu H(X) là không gian mà các điểm của nó là các tập con compact khác rỗng của X. Định nghĩa 1.1.18. Cho (X, d) là một không gian metric đầy đủ, x X và B H(X). Ta định nghĩa: d(x, B)=min{d(x, y): y B} d(x, B) được gọi là khoảng cách từ điểm x đến tập B. Làm thế nào chúng ta biết tập hợp các số thực {d(x, y): y B} chứa một giá trị nhỏ nhất, như định nghĩa trên? Điều này dẫn tới những tập compact và tập khác rỗng của tập B H(X). Xét hàm f: B R định nghĩa như sau: f(y)=d(x, y) y B. Từ định nghĩa của tập metric ta có f là hàm liên tục, hiển thị như một hàm từ không gian metric (B, d) đến không gian (R, Euclide). Cho P = inf {f(y): y 0 B}. Vì f(y) y B => P là hữu hạn. Chúng ta giả sử có một điểm ŷ B mà d(x, ŷ ) = P. Chúng ta có thể tìm được một chuỗi vô hạn các điểm {yn: n=1, 2, 3, ..} B mà f(yn) - P < 1/n với mỗi số nguyên dương n. Sử dụng những tập compact của B, chúng ta tìm được {yn: n=1,2,3,.} có một giới hạn ŷ B. Sử dụng tính liên tục của f chúng ta thu được f( ŷ ) = P. Đây là điều mà chúng ta cần chỉ ra. Định nghĩa 1.1.19. Cho (X, d) là một không gian metric, A, B H(X). Định nghĩa: d(A, B) = max{d(x, B): x A}. d(A, B) được gọi là khoảng cách từ tập A H(X) đến tập B H(X). Định nghĩa 1.1.20. Cho (X, d) là một không gian metric đầy đủ. Khoảng cách Hausdorff giữa hai điểm A và B trong H(X) được định nghĩa như sau: 11 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ h(A, B)=d(A, B) d(B, A). Ta có h là một metric trên H(X). Tính đầy đủ của không gian của Fractal Chúng ta ta coi (H(X), h) là một không gian của Fractals. Còn quá sớm để định nghĩa chính xác của một ―Fractal‖. Ở giai đoạn hiện nay của sự phát triền khoa học và toán học, quan niệm về Fractals rất hữu ích như một khái niệm rộng. Fractals không được định nghĩa bởi một câu đúng đắn ngắn gọn, nhưng bằng nhiều hình ảnh và bối cảnh giới thiệu về chúng. Coi tập con của (H(X), h) là một Fractal. Mục tiêu chính của chúng ta là đi xây dựng không gian của Fractals (H(X), h) là một không gian metric đầy đủ. Ngoài ra, mô tả những chuỗi hội tụ trong H(X). Để đạt được những mục đích này thì việc chỉ sử dụng những công cụ đã giới thiệu từ trước đến giờ thì quá khó khăn. Thật vậy, vào thời điểm này, chúng ta cần giới thiệu một khái niệm khác; cụ thể là, một ý tưởng về việc mở rộng những chuỗi con Cauchy. Định nghĩa 1.1.21. Cho S X và Đôi khi, S + 0. S+ = {y X: d(x, y) được gọi là sự giãn nở của S bởi một hình tròn bán kính với x S}. trong lý thuyết tập hợp hình thái học. Bổ đề 1.1.1. Cho A và B thuộc vào H(X) với (X, d) là một không gian metric. Cho > 0. Khi đó: h(A, B) < A B+ và B A + Bổ đề 1.1.2. (Bổ đề mở rộng) Cho (X, d) là một không gian metric, {An: n=1, 2, ..., } là một chuỗi Cauchy các điểm trong (H(X), h), {nj} j 1 là một chuỗi vô hạn các số nguyên: 0< n1 < n2 < ... Giả sử rằng chúng ta có một chuỗi Cauchy {xn j An j : j=1, 2, 3, ...} trong An: n= 1, 2, ...} sao cho ~x n j = (X, d). Thì có một chuỗi Cauchy { ~ xn j=1, 2, 3, ... xn j , Định lý 1.1.3.(Tính đầy đủ của không gian của Fractals) Cho (X, d) là một không gian metric đầy đủ. Thì (H(X), h) là một không gian metric đầy đủ. Hơn nữa, 12 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ nếu {An H(X)} n 1 là một chuỗi Cauchy, thì: A = limn An H(X) có thể được mô tả như sau: X: có một chuỗi Cauchy {xn A = {x Định lý 1.1.4. Hàm f: R An} hội tụ đến x}. H cho bởi f(x) = {x} là một hàm liên tục. Định lý 1.1.5. Hàm fx: [0, 1] H cho bởi fx(a) = [x, x+a], 0 a 1 là hàm liên tục, qua đó cho thấy có một đường trong H từ một khoảng đến một trong các điểm cuối của nó. Định lý 1.1.6. Nếu A là một tập con compact của R thì hàm fA: [0, b] cho bởi fA(a) = H [x, x+a] với x A là hàm liên tục. Định lý 1.1.7. Nếu A là một tập con compact của R thì tập [x, x+b] với x A là một khoảng với b đủ lớn. Định lý 1.1.8. Nếu A và B là các tập con compact của R thì có một đường trong H liên kết chúng với nhau. 1.1.3. Những định lý mở rộng về không gian Metric Định lý 1.1.9. Cho (X, d) là một không gian metric, {xn} là một chuỗi Cauchy hội tụ tới x X (hoặc tương đương cho {xn} là một chuỗi và x là một điểm sao cho limn X là liên tục. Thì: d ( x , xn) =0). Cho f: X limn f ( x n) = f(x). Định lý 1.1.10. Cho (X1, d1) và (X2, d2) là các không gian metric. Cho f: X1 với X2 là hàm liên tục, E X1 là compact. Thì f: E > 0, tồn tại một số X2 là liên tục đều: nghĩa là, > 0 sao cho: d2(f(x), f(y)) < bất cứ khi nào d1(x, y) < với x, y E. Định lý 1.1.11. Cho (Xi,di) là các không gian metric với i = 1, 2, 3. Cho f: X1 x X2 X3 có tính chất sau: với mỗi e > 0 tồn tại ô > 0 sao cho: a. d1(x1, y1) < => d3(f(x1, x2), f(y1, y2) < , x 1 , y1 b. d2(x2, y2) < => d3(f(y1, x2), f(y1, y2) < , y1 X1, thì f là hàm liên tục trên không gian metric (X = X1xX2, d), với d((x1, x2), (y1, y2)) = max{d1(x1, y1), d2(x2, y2)} 13 X1 , x 2 , y2 x2 , y2 X2 X2.. Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ Định lý 1.1.12. Cho (Xi, di) là các không gian metric, với i = 1, 2 và cho không gian metric (X, d) được định nghĩa như trong Định lý 1.1.11. Nếu K1 X1 và K2 X2 là compact thì K1 x K2 X là compact. Định lý 1.1.13. Cho (Xi, di) là các không gian metric compact với i = 1, 2. Cho f: X1 X2 là liên tục, một - một, và lên. Vậy f là một phép biến đổi topo. 1.2. Cấu trúc của Fractal 1.2.1 Các phép biến đổi trên không gian Metric a. Những biến đổi trên đƣờng thẳng thực. Hình học Fractal nghiên cứu các tập con ―phức‖ của các không gian hình học ―đơn giản‖ như R2, C, R và Ĉ . Trong hình học Fractal tập trung vào các tập con này của một không gian được tạo ra, hoặc có tính chất bất biến, các phép biến đổi hình học cơ bản của không gian vào chính nó. Một phép biến đổi hình học cơ bản dễ dàng để truyền đạt hoặc giải thích cho bất kỳ ai. Thông thường, nó có thể được quy định bởi một tập hợp nhỏ các thông số. Ví dụ như, các phép biến đổi affine trong R2, được miêu tả bằng cách sử dụng các ma trận 2 x 2 và 2 vector, và các phép biến đổi hữu tỷ trên hình cầu Riemann. Định nghĩa 1.2.1. Cho (X, d) là một không gian metric. Một phép biến đổi trên X là một hàm f: X điểm x X, nó xác định chính xác một điểm f(x) X với mỗi X. Nếu S X thì f(S) = {f(x): x S}. f là một - một (đơn ánh) nếu x, y X với f(x) = f(y) thì x=y. f là ánh xạ lên nếu f(X) = X. f được gọi là có nghịch đảo nếu nó là một - một và lên: trong trường hợp này nó có thể xác định một phép biến đổi f1 : X X, được gọi là nghịch đảo của f, với f-1(y) = x với x X là điểm duy nhất thỏa mãn y = f(x). Định nghĩa 1.2.2. Cho f: X X là một phép biến đổi trên một không gian metric. Lặp trước của f là các phép biến đổi f°n: X X định nghĩa bởi f°°(x) = x, fo1(x) = f(x), fo(n+1)(x) = f o f°n(x) = f(fn(x)) với n = O, 1, 2, .... Nếu f là khả nghịch thì lặp sau của f là các phép biến đổi f°(-m)(x): X 1 X định nghĩa bởi f°(-1)(x) = f (x), f°(-m)(x) =( f m)-1(x) với m = 1, 2, 3, .. Các phép biến đổi affine trong R là các phép biến đổi có dạng f(x) = a.x + b, trong đó a và b là các hằng số. Một khoảng I = [0, 1], nếu f(I) là một khoảng mới 14 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ có độ dài |a| và f thay đổi tỷ lệ bởi a. Điểm đầu mút bên trái 0 của khoảng được dịch chuyển tới b, và f(I) nằm bên trái hoặc bên phải của b tương ứng với a dương hoặc âm. Định nghĩa 1.2.3. Một phép biến đổi f: R R f(x) = a0 + a1x + a2x2 + .+ anxn, Với các hệ số ai (i = 0, 1, 2, ..., N) là các số thực, an 0, và N là một số nguyên không âm, được gọi là một phép biến đổi đa thức. N được gọi là bậc của phép biến đổi. Định nghĩa 1.2.4. Một phép biến đổi f: sau: f(x) = ax b với a, b, c, d cx d R̂ được R̂ định nghĩa như R, ad bc được gọi là một phép biến đổi phân đoạn tuyến tính hay một phép biến đổi Mobius. Nếu c 0 thì f(-d/c) = f( ) = a/c. Nếu c = 0 thì f( ) = và . b.Các phép biến đổi affine trong mặt phẳng Euclide. Định nghĩa 1.2.5. Một phép biến đổi : R2 R2 cho bởi: (x1, x2) = (ax1 + bx2 + e, cx1 + dx2 + f), ở đây a, b, c, d, e và f là các số thực, được gọi là một (2 chiều) phép biến đổi affine. Chúng ta sẽ thường xuyên sử dụng các kí hiệu tương đương sau đây: (x)= x1 x2 = a b x1 c d x2 2x2 và t là vector cột e f e + f = Ax+ t . ở đây A = a b c d là ma trận thực , mà chúng ta không phân biệt từ cặp tọa độ (e, f) R2. Như các phép biến đổi có tính chất hình học và đại số quan trọng. Ma trận A có thể được viết dưới dạng: a b c d ở đây (r1, 1) = r1 sin 1 r1 sin 1 r2 sin r2 sin 2 2 là tọa độ cực của điểm (a, c) và (r2, điểm(b, d). Phép biến đổi tuyến tính: 15 2 + /2) là tọa độ cực của Soá hoùa bôûi Trung taâm Hoïc lieäu x1 x2 =A http://lrc.tnu.edu.vn/ x1 x2 trong R2 ánh xạ một hình bình hành bất kỳ có một đỉnh tại gốc tọa độ tới một hình bình hành khác có một đỉnh tại gốc tọa độ như minh họa trong H ì n h 1 . 5 . Chú ý rằng hình bình hành có thể ―lật ngược lại‖ bởi ánh xạ như trong H ì n h 1 . 6 . Hình 1.5. Một phép biến đổi affine đưa các hình bình hành vào các hình bình hành. Hình 1.6. Một phép biến đổi tuyến tính có thể lật ngược các hình ảnh. Định nghĩa 1.2.6. Một phép biến đổi w: R 2 R 2 được gọi là một p h é p b i ế n đ ổ i đ ồ n g d ạ n g nếu nó là một phép biến đổi affine có một trong những dạng đặc biệt sau: x1 x2 x1 x2 = = r cos r sin x1 r sin r cos x2 r cos r sin r sin r cos x1 x2 e + + với sự dịch chuyển (e, f) R2, số thực r 0, và góc f e f :0 góc quay trong khi r được gọi là hệ số tỷ lệ hoặc thước tỷ lệ. Phép biến đổi tuyến tính: 16 2 . được gọi là Soá hoùa bôûi Trung taâm Hoïc lieäu R x1 x2 = http://lrc.tnu.edu.vn/ r cos r sin x1 r sin r cos x2 là một phép quay. Phép biến đổi tuyến tính: R1 x1 x2 = 1 0 0 1 x1 x2 là một phép đối xứng. c. Các phép biến đổi Mobius trên hình cầu Riemanm. ( az b) ~ Định nghĩa 1.2.7. Một phép biến đổi f: C—> C định ngĩa bởi:f(z)= , với a, (cz d ) b, c và d C, ad - bc 0 được gọi là một phép biến đổi Mqobius trên Ĉ . Nếu c 0 thì f(-d/c) = . Lập đồ thị toàn bộ mặt phẳng C, cùng với điểm vô hạn, trên hình cầu Ĉ . Một chuỗi các tác động được áp dụng cho hình cầu. Mỗi tác động là sơ bộ và có tính chất lấy một hình tròn tới một hình tròn. Tác động có thể là quay quanh một trục, và dịch chuyển (toàn bộ hình cầu được đưa lên và di chuyển tới một vị trí mới trên hình cầu, không phải quay). Cuối cùng, hình cầu ánh xạ lên mặt phẳng theo cách thông thường. Vì ánh xạ trở lại và ra từ mặt phẳng tới hình cầu lấy những đường thẳng và những hình tròn trong mặt phẳng tới những hình tròn trên hình cầu, chúng ta thấy rằng một phép biến đổi Mobius dịch chuyển tập những đường thẳng và những hình tròn trong mặt phẳng lên chính nó. Ngoài ra, chúng ta thấy rằng một phép biến đổi Mobius là khả nghịch. d. Hàm giải tích. Hàm f: Ĉ Ĉ định nghĩa bởi f(z) = 3z + 1 là một ví dụ về hàm giải tích. Nó ánh xạ các hình tròn tới các hình tròn phóng đại với tỷ lệ 3. Một đĩa với tâm ở z 0 được đưa vào một đĩa với tâm f(z0) = 3z0 + 1. Phép biến đổi là liên tục và nó ánh xạ các tập mở tới các tập mở. Hàm f: Ĉ Ĉ định nghĩa bởi f(z) = (3 + 3i)z + (1- 2i) được miêu tả tương tự. Những hình tròn và những chiếc đĩa bây giờ được quay 45o trong sự phóng đại và dịch chuyển. 17