- Trang Chủ
- Khoa học tự nhiên
- ĐỒ ÁN TỐT NGHIỆP: Nghiên cứu về hình học practal. Viết chương trình cài đặt một số đường và mặt practal
Xem mẫu
- TRƯỜNG………………………
KHOA……………………
ĐỒ ÁN TỐT NGHIỆP:
" Nghiên cứu về hình học practal. Viết chương
trình cài đặt một số đường và mặt practal "
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
LỜI NÓI ĐẦU
Trong những năm gần đây, toán học và khoa học tự nhiên đã bước lên
một bậc thềm mới, sự mở rộng và sáng tạo trong khoa học trở th ành một cuộc
thử nghiệm liên ngành. Cho đ ến nay nó đ ã đưa khoa học tiến những bước rất
dài. Hình học phân hình đ ã được đông đảo mọi người chú ý và thích thú nghiên
cứu. Với một người quan sát tình cờ màu sắc của các cấu trúc phân hình cơ sở
và vẽ đẹp của chúng tạo nên một sự lôi cuốn h ình thức hơn nhiều lần so với
các đối tư ợng toán học đã từng đư ợc biết đến. Hình học phân hình đã cung cấp
cho các nhà khoa học một môi trường phong phú cho sự thám hiểm và mô hình
hoá tính phức tạp của tự nhiên. Những nguyên nhân của sự lôi cuốn do hình
học phân hình tạo ra là nó đã ch ỉnh sửa được khái niệm lỗi thời về thế giới thực
thôn g qua tập hợp các bức tranh mạnh mẽ và duy nhất của nó.
Nh ững thành công to lớn trong các lĩnh vực của khoa học tự nhiên và k ỹ
thuật dẫn đến sự ảo tưởng về một thế giới hoạt động như một cơ chế đồng hồ
vĩ đại, trong đó các quy luật của nó chỉ còn phải chờ đợi để giải m ã từng bước
một. Một khi các quy luật đã được biết, ngư ời ta tin rằng sự tiến hoá hoặc phát
triển của các sự vật sẽ được dự đoán trước chính xác hơn nhiều, ít ra là về mặt
nguyên tắc. Những bước phát triển ngoạn mục đầy lôi cuốn trong lĩnh vự c k ỹ
thuật máy tính và sự hứa hẹn cho việc điều khiển thông tin nhiều h ơn n ữa của
nó đ ã làm gia tăng hy vọng của nhiều người về máy móc hiện có và cả những
máy móc ở tương lai. Nhưng ngày nay người ta đ ã biết chính xác dựa trên cốt
lỗi của khoa học hiện đại là khả năng xem xét tính chính xác các phát triển ở
tương lai như thế sẽ không bao giờ đạt được. Một kết luận có thể thu được từ
các lý thuyết mới còn rất non trẻ đó là : giữa sự xác định có tính nghiêm túc
với sự phát triển có tính ngẫu nhiên không nhữn g không có sự loại trừ lẫn nhau
mà chúng còn cùng tồn tại nh ư một quy luật trong tự nhiên. Hình học phân
hình và lý thuyết hỗn độn xác định kết luận này. Khi xét đến sự phát triển của
một tiến trình trong một khoảng thời gian, chúng ta sử dụng các thuật ngữ của
lý thuyết hỗn độn, còn khi quan tâm nhiều hơn đến các dạng có cấu trúc mà
một tiến trình hỗn độn để lại trên đường đi của nó, chúng ta dùng các thuật ngữ
của hình h ọc phân h ình là bộ môn hình học cho phép “sắp xếp thứ tự” sự hỗn
độn. Trong ngữ cảnh n ào đó hình học phân h ình là ngôn ngữ đầu tiên để mô tả,
mô hình hoá và phân tích các dạng phức tạp đã tìm thấy trong tự nhiên. Nhưng
trong khi các phần tử của ngôn ngữ truyền thống (Hình học Euclide) là các
dạng hiển thị cơ bản như đoạn thẳng, đường tròn và hình cầu th ì trong hình học
phân hình đó là các thuật toán chỉ có thể biến đổi thành các d ạng và cấu trúc
nhờ máy tính.
Việc nghiên cứu ngôn ngữ hình học tự nhiên này mở ra nhiều hướng
mới cho khoa học cơ b ản và ứng dụng. Trong đề tài này chỉ mới thực hiện
nghiên cứu một phần rất nhỏ về hình học phân hình và ứng dụng của nó. Nội
dung của đề tài gồm có ba chương được trình bày như sau:
Đề tài : Hình học Fractal Trang 1
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Chương I: Trình bày các kiến thức tổng quan về lịch sử hình học phân
hình, về các kết quả của cơ sở lý thuyết.
Chương II: Trình bày các k ỹ thuật hình học phân hình thông qua sự
khảo sát các cấu trúc Fractal cơ sở và thuật toán chi tiết để tạo n ên các cấu trúc
này.
Chương III: Kết quả cài đ ặt chương trình vẽ một số đường mặt fractal
và các hiệu ứng.
Nhân đây, em xin chân thành cảm ơn thầy T.S Huỳnh Quyết Thắng đã
tận tình h ướng dẫn, chỉ dạy giúp đỡ em trong suốt thời gian thực hiện đề tài
nghiên cứu n ày.
Em cũng xin chân thành cảm ơn quý thầy cô khoa công nghệ thông tin
đã tận tình giảng dạy, trang bị cho chúng em những kiến thức cần thiết trong
suốt quá trình học tập, và em cũng xin gởi lòng biết ơn đ ến gia đình, cha, mẹ,
và bạn b è đ ã ủng hộ, giúp đỡ và động viên em trong những lúc khó khăn.
Đề tài được thực hiện trong một thời gian tương đối ngắn, nên dù đã hết
sức cố gắng ho àn thành đ ề tài nhưng chắc chắn sẽ không thể tránh khỏi những
thiếu sót nhất định. Rất mong nhận đ ược sự thông cảm và đóng góp những ý
kiến vô cùng quý báu của các Thầy Cô, bạn bè, nh ằm tạo tiền đề thuận lợi cho
việc phát triển đề tài trong tương lai.
Sinh viên thực hiện
Nguyễn Ngọc Hùng Cường.
Đề tài : Hình học Fractal Trang 2
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
MỤC LỤC
Trang
LỜI NÓI ĐẦU. ................................................................ ..................................... 1
Chương I:SỰ RA ĐỜI VÀ CÁC KẾT QUẢ CỦA HÌNH HỌC PHÂN HÌNH. ..... 5
I.1 Sự ra đời của lý thuyết hình học phân h ình ................................ .................. 5
Tính hỗn độn của các quá trình phát triển có quy luật trong tự nhiên ............. 5
Sự mở rộng khái niệm số chiều và độ đo trong lý thuyết hình h ọc Eulide
cổ điển ................................................................ ................................ .................. 8
I.2 Sự phát triển c ủa l ý thuyết h ình học phân hình ......................................... 9
I.3 Các ứng dụng tổng quát của hình học phân hình ....................................... 10
Ứng dụng trong vấn đề tạo ảnh trên máy tính .............................................. 11
Ứng dụng trong công nghệ nén ảnh ................................ ............................. 11
Ứng dụng trong khoa học cơ bản ................................................................. 13
I.4 Các kiến thức cơ sở của h ình học phân hình .............................................. 13
I.4.1 Độ đo Fractal ................................................................ ....................... 13
I.4.2 Các h ệ h àm lặp IFS ............................................................................. 17
Chương II : MỘT SỐ KỸ THUẬT CÀI ĐẶT HÌNH HỌC PHÂN HÌNH. .......... 21
II.1 Họ đường Von Ko ck ................................ ................................ ................ 21
Đường hoa tuyết Von Kock-Nowflake ........................................................ 21
Đường Von Kock-Gosper ........................................................................... 26
Đường Von Kock bậc hai 3-đo ạn ................................................................ 28
Đường Von Kock bậc hai 8-đo ạn ................................................................ 30
Đường Von Kock bậc hai 18-đoạn............................................................... 32
Đường Von Kock bậc hai 32-đoạn............................................................... 33
Đường Von Kock bậc hai 50-đoạn............................................................... 35
Generator phức tạp ................................ ................................ ...................... 38
II.2 Họ đường Peano ................................ ................................ ...................... 44
Đường Peano nguyên thu ỷ........................................................................... 44
Đường Peano cải tiến................................................................................... 45
Tam giác Cesaro .......................................................................................... 49
Tam giác Cesaro cải tiến.............................................................................. 51
Một dạng khác của đ ường Cesaro ................................................................ 54
Tam giác Polya ................................ ............................................................ 56
Đường Peano-Gosper ................................................................................. 58
Đường hoa tuyết Peano 7-đo ạn ................................ ................................... 62
Đường hoa tuyết Peano 13-đoạn ................................................................. 66
II.3 Đường Sierpinski ..................................................................................... 70
II.4 Cây Fractal............................................................................................... 73
Các cây thực tế ........................................................................................... 73
Biểu diễn toán học của cây ................................ ......................................... 73
II.5 Phong cảnh Fractal................................................................................... 77
II.6 Hệ thống h àm lặp (IFS) ............................................................................ 84
Các phép biến đổi Affine trong không gian R2 ............................................ 84
Đề tài : Hình học Fractal Trang 3
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
IFS của các pháp biến đổi Affine trong không gian R2 ................................ 85
Giải thuật lặp ngẫu nhiên ............................................................................ 86
II.7 Tập Mandelbrot ........................................................................................ 88
Đặt vấn đề ................................ .................................................................. 98
Công th ức toán học................................ ................................ ...................... 88
Thu ật toán thể hiện tập Mandelbrot ................................ ............................. 89
II.8 Tập Julia ................................................................ ................................... 94
Đặt vấn đề ................................ .................................................................. 94
Công th ức toán học ..................................................................................... 94
Thu ật toán thể hiện tập Julia ........................................................................ 95
II.9 Họ các đư ờng cong Phoenix...................................................................... 97
Chương III : GIỚI THIỆU VỀ NGÔN NGỮ CÀI ĐẶT VÀ KẾT QUẢ
CHƯƠNG TRÌNH. ................................................................ ........................... 100
III.1 Giới thiệu về ngôn ngữ cài đặt ............................................................... 100
III.2 Kết quả chương trình ................................ ............................................. 111
TÀI LIỆU THAM KHẢO ................................................................................. 116
Đề tài : Hình học Fractal Trang 4
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
CHƯƠNG I: SỰ RA ĐỜI VÀ CÁC KẾT QUẢ CỦA H ÌNH HỌC
PHÂN HÌNH.
I.1 SỰ RA ĐỜI CỦA LÝ THUYẾT HÌNH HỌC PHÂN HÌNH:
Sự ra đời của lý thuyết h ình học phân hình 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 phân hình
đượ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 lực 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.
□ TÍNH HỖN ĐỘN CỦA CÁC QUÁ TRÌNH PHÁT TRIỂN CÓ QUY
LUẬT TRONG TỰ NHIÊN:
Các công thức lặp có dạng:
Xn+1=f(Xn)
thường đư ợc sử dụng trong các ngành khoa học chính xác để mô tả các quá
trình lặp đi lặp lại có tính xác định. Các quá trình được xác định bởi công thức
trên, trong đó f thể hiện mối liên hệ phi tuyến giữa hai trạng thái nối tiếp nhau
Xn và Xn+1, được quan tâm đặc biệt. Các khảo sát trong những thập niên gần
đây đã phát hiện ra các cư xử kỳ dị của các tiến trình lặp như vậy.
Kh ảo sát chi tiết đầu tiên được nh à khí tượng học Edward N. Lorenz
tiến hành vào năm 1961 khi nghiên cứu hệ toán học mô phỏng dự báo thời tiết.
Về mặt lý thuyết, hệ n ày cho ra các kết quả dự đoán chính xác về thời tiết trong
một khoảng thời gian d ài. Tuy nhiên, theo Lorenz quan sát, khi bắt đầu tính
toán lại dựa vào dữ liệu cho bởi hệ tại một thời điểm tiếp sau đó không giống
với các kết quả dự đoán ban đầu. Hơn nữa sai số tính toán sẽ tăng lên nhanh
chóng theo thời gian. Điều này d ẫn đến kết luận là nếu tiến trình d ự đoán lại từ
một thời điểm nào đó trong tiến trình dự báo, khoảng thời gian để các kết quả
dự báo tiếp theo vẫn còn chính xác sẽ bị thu hẹp lại tức là không th ể dự báo
chính xác về thời tiết trong một khoảng thời gian khá lớn. Vấn đề được Lorenz
tìm th ấy ở đây ngày nay đư ợc gọi là sự hiện diện của tính chất hỗn độn trong
các tiến trình lặp xác định.
Tiếp theo sau phát hiện của Lorenz, vào năm 1976 Robert May trong
bài viết với tựa đề “Các mô h ình toán học đ ơn giản với các h ệ động lực phức
tạp” đã đề cập đến một vấn đề tương tự. Đó là sự hỗn độn của quá trình phát
triển dân số trong tự nhiên, vốn đư ợc xem là đ ã được xác định rất rõ ràng và
chi tiết nhờ mô hình dân số Verhulst xây dựng dưới đây.
Nếu ký hiệu:
Đề tài : Hình học Fractal Trang 5
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
R là tốc độ gia tăng dân số mỗi năm.
-
Po là lượng dân số khởi điểm (của một quốc gia, một th ành
-
phố,…).
Pn là lượng dân số có được sau n năm phát triển.
-
Ta có quan hệ sau:
Pn+1 - Pn
, n > 0 (1)
R=
Pn
Để ý là nếu dân số phát triển đều, tức là R không đổi từ năm này sang
năm khác, từ (1) ta sẽ có:
Pn+1 = f(Pn) = (1+R)Pn
Do đó sau n năm, lượng dân số khảo sát sẽ là:
Pn = (1+R)n .P o
Công thức này chỉ ra sự gia tăng dân số theo hàm mũ là một điều không
thực tế. Vì vậy Verhulst đề nghị R thay đổi cùng với lượng dân số được khảo
sát. Một cách cụ thể, Verhust cho R tỉ lệ với tốc độ phát triển dân số theo môi
trường (P-Pn) / N. Trong đó N là lượng dân số tối đa có thể có ứng với điều
kiện môi trường cho trước. Nh ư vậy có thể biểu diễn R dưới dạng:
N - Pn
R=r (2)
N
Với r là hệ số tỷ lệ gọi là tham số phát triển theo môi trường.
Từ (1) và (2) suy ra:
Pn+1 - Pn N - Pn
=r
Pn N
Do đó:
Pn+1 - Pn
N Pn
=r
Pn N
N
Pk
Đặt:
Pk = ta có:
N
P n+1 - Pn
= r(1 - Pn)
Pn
Đề tài : Hình học Fractal Trang 6
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Suy ra:
Pn+1 = Pn + rPn(1 – Pn)
Phương trình này được gọi là phương trình dân số Verhust. Rõ ràng
phương trình được xác định rất đ ơn giản. Do đó, kể từ khi được đưa ra người ta
áp dụng m à không nghi ngờ gì về tính ổn định của nó. Tuy nhiên khi May khảo
sát phương trình này thì với r thay đổi trong phạm vi khá lớn, ông đã khám phá
ra sự bất ổn định về tỉ lệ phát triển dân số theo môi trường Pk.
Các kết quả quan sát chi tiết cho thấy khi số lần lặp n trở nên khá lớn ta
có các trường hợp sau:
- Với 0 < r < 2: Dãy (Pn) tiến đến 1, tức là sự phát triển dân số đạt
mức tối đa.
- Với 2 < r < 2,449: Dãy (Pn) dao động tuần hoàn giữa hai giá trị,
tức là sự phát triển dân số biến động giữa hai mức xác định. Hình
vẽ (I.1) minh hoạ cho trường hợp r = 2.3 và Po
Dân số:
Thời gian
Hình vẽ I.1 với r = 2.3 và P0 = 0.01
Với 2,449 < r < 2,570: Dãy (Pn) dao động ổn định với các giá trị
-
được lặp lại theo chu kỳ lần lượt đ ược nhân đôi khi giá trị r chạy
từ 2,449 đến 2,570. Hình vẽ (I.2) minh hoạ trường hợp r = 2,5 và
sự dao động ở đây có chu kỳ 4.
Dân số:
Thời gian
Hình vẽ I.2 với r = 2.5
Với r > 2.570: Dãy (Pn) không còn tuần ho àn nữa mà trở nên hỗn
-
độn, theo nghĩa các giá trị của dãy được chọn một cách ho àn toàn
xác đ ịnh nhưng không có thể dự đoán chính xác. Hình vẽ (I.3)
minh hoạ trường hợp r = 3.0 và P o = 0 .1
Đề tài : Hình học Fractal Trang 7
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Dân số
Thời gian
Hình vẽ I.3 với r = 3.0 và Po = 0.1
Một kết quả lý thuyết cũng đã đ ược chứng minh bởi Jame York và Tiên
Yien Li trong bài viết ”Các chu kỳ 3 chứa đựng sự hỗn độn” vào tháng
12/1975. York và Li đã chỉ ra rằng mọi hàm số được xác định tương tự nh ư
phương trình dân số có một chu kỳ tuần hoàn 3 thì cũng có chu kỳ tuần hoàn n,
với n là số tự nhiên khác 0 và 1. Điều này d ẫn đến sự kiện là vô số các tập giá
trị tuần hoàn khác nhau được sản sinh bởi loại phương trình này.
Vào năm 1976, Mitchell Feigenbaum đ ã nghiên cứu phương trình này
một cách độc lập với May và York. Feigenbaum xét phương trình dân số ở
dạng đ ơn giản:
y = x(1- x)
và thể hiện nó trên sơ đồ phân nhánh. Nếu gọi rn là giá trị tham số phát
triển theo môi trường của mô h ình Verhulst tại lần rẻ nhánh thứ n (là lúc ứng
với rn đó, chu k ỳ 2n trở nên không ổn định nữa và chu kỳ 2n+1 đạt được sự ổn
định), thì tỷ số của các khoảng liên tiếp n xác định bởi:
rn - rn-1
n =
rn+1 - rn
Sẽ tiến về giá trị = 4.669 khi n . Tính chất này cũng được tìm thấy
trong các tiến trình có chu k ỳ lần lượt đư ợc nhân đôi và khác với tiến trình
Verhulst. Do đó giá trị n ày ngày nay được gọi là hằng số phổ dụng
Feigenbaum (trong lý thuyết hỗn độn).
□ SỰ MỞ RỘNG KHÁI NIỆM SỐ CHIỀU VÀ ĐỘ ĐO TRONG LÝ
THUYẾT HÌNH HỌC EULIDE CỔ ĐIỂN:
Vào các năm 1890 & 1891, trong khi tìm kiếm các đặc trưng bất biến
của các đối tượng h ình học qua các phép biến đổi đồng phôi trong lý thuyết
topo, các nhà toán học Peano & Hilbert đ ã phát minh ra các đường cong có
tính chất rất đặc biệt. Đó là các đường cong không tự cắt theo một quy luật
được chỉ ra bởi Peano và Hilbert, chúng lấp đầy mọi miền hữu hạn của mặt
phẳng. Hình học Euclide cổ điển quan niệm các đường cong như vậy vẫn chỉ là
Đề tài : Hình học Fractal Trang 8
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
các đối tượng một chiều nh ư các đường thẳng. Tuy nhiên trực quan cho thấy
cách nhìn như vậy về số chiều là rất gò bó. Do đó người ta bắt đầu nghĩ đến
một sự phân lớp mới, trong đó các đường có số chiều bằng 1 đư ợc đại diện bởi
đường thẳng, các đối tượng hai chiều được đại diện bởi mặt phẳng, còn các
đường cong lấp đầy mặt phẳng đại diện cho các đối tượng có số chiều giữa 1
và 2. Ý tưởng cách mạng này đ ã d ẫn đến việc hình thành và giải quyết b ài toán
số chiều hữu tỷ gây ra nhiều tranh luận toán học trong các thập kỷ gần đây.
Tiếp sau đó, vào năm 1904 nhà toán học Thụy Điển Helge Koch đã đưa
ra một loại đường cong khác với những đường cong của Peano và Hilbert. Các
đường cong Von Koch không lấp đầy mặt phẳng nhưng lại có độ dài thay đ ổi
một cách vô hạn mặc dù chúng được chứa trong một miền hữu hạn. Những
đường cong như vậy có rất nhiều trong tự nhiên, ví dụ như các đư ờng bờ biển,
đường biên của một bông hoa tuyết, các đám mây, vv… Tất vả các đường cong
này đều một tính chất đặc trưng là đồng dạng. Nó đư ợc biểu hiện bởi sự giống
nhau giữa một phần rất nhỏ của đ ường cong đư ợc phóng lớn với một phần
khác lớn hơn của cùng một đường cong đó. Tính chất này giữ một vị trí quan
trọng trong việc hình thành nên các d ạng cấu trúc vô cùng phức tạp của tự
nhiên, nhưng vào th ời Von Koch lại được hiểu biết rất sơ lược.
Ch ỉ với sự giúp đỡ của máy tính điện tử, bản chất của tính đồng dạng
mới được nghiên cứu đầy đủ và chi tiết trong tác phẩm “Hình học phân hình
trong tự nhiên” của Benoit B. Mandelbrot xuất bản năm 1982. Trong tác phẩm
của mình, Mandelbrot đ ã phân rã các d ạng cấu trúc phức tạp của tự nhiên
thành các thành ph ần cơ bản gọi là fractal. Các fractal này chứa đựng các hình
dáng tự đồng dạng với nhiều kích thước khác nhau. Mandelbrot đ ã tạo nên
những bức tranh fractal trừu tượng đầu tiên và nh ận thấy rằng đằng sau các đối
tượng tự nhiên như các đám mây, các dãy núi, các khu rừng, vv… là các cấu
trúc toán học tương tự nhau. Chúng có khuynh hướng hài hoà về màu sắc và
cân đối về hình thể. Ngoài ra Mandelbrot cũng thiết lập cách xác định số chiều
và độ d ài của các dạng fractal cơ sở. Chính với định nghĩa về số chiều n ày, bài
toán số chiều không nguyên mới được giải quyết một cách ho àn ch ỉnh. Có thể
nói công trình của Benoit B.Mandelbrot đã chính thức khai sinh lý thuyết hình
học phân hình sau hơn nửa thế kỷ nghiên cứu liên tục.
I.2 SỰ PHÁT TRIỂN CỦA LÝ THUYỂT H ÌNH HỌC PHÂN HÌNH:
Kể từ khi ra đời một cách chính thức vào năm 1982 cho đ ến nay, lý
thuyết hình học phân h ình học phân hình đ ã phát triển một cách nhanh chóng.
Sau khi đặt nền móng cho lý thuyết phân hình, Mandelbrot cùng với các
nhà toán học khác như A. Douady và J.Hubbard đã phát triển lý thuyết về các
mặt 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 Mandelbrot và tập Julia. Ngo ài ra các nghiên cứu
cũng cố gắng tìm kiếm mối liên h ệ giữa các cấu trúc n ày, ví dụ như mối liên hệ
giữa tập Mandelbrot và Julia.
Đề tài : Hình học Fractal Trang 9
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Dựa trên các công trình của Mandelbrot (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á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 toà 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.
Ngoài ra các công trình có tính ch ất lý thuyết, hình học phân hình còn
được bổ sung bởi nhiều nghiên cứu ứng dụng lý thuyết v ào khoa học máy tính
và các khoa học chính xác khác, ví dụ dựa trên lý thuyết IFS, Barnsley đã phát
triển lý thuyết biến đổi phân h ình áp dụng vào công ngh ệ nén ảnh tự động trên
máy tính, là một lĩnh vực đòi hỏi những kỹ thuật tiên tiến nhất của tin học hiện
đại.
Hiện nay nhiều vấn đề, về lý thuyết phân hình vẫn đang được tiếp tục
nghiên cứu. Một trong những vấn đề lớn đang được quan tâm là bài toán về các
độ đo đa phân hình (multifractal measurement) có liên quan đ ến sự mở rộng
các khái niệm số chiều fractal với đối tượng fractal trong tự nh iên, đồng thời
cũng liên quan đ ến việc áp dụng các độ đo fractal trong các ngành khoa học tự
nhiên.
I.3 CÁC Ứ NG DỤNG TỔNG QUÁT CỦA H ÌNH HỌC PHÂN HÌNH:
Hiện nay có 3 hướng ứng dụng lớn của lý thuyết hình học phân hình,
bao gồm:
▪ Ứng dụng trong vấn đề tạo ảnh trên máy tính.
▪ Ứng dụng trong công nghệ nén ảnh.
▪ Ứng dụng trong nghiên cứu khoa học cơ bản.
□ Ứ NG DỤNG TRONG VẤN ĐỀ TẠO ẢNH TRÊN MÁY TÍNH:
Cùng với sự phát triển vư ợt bậc của máy tính cá nhân trong những năm
gần đây, công nghệ giải trí trên máy tính bao gồm các lĩnh vực như trò chơi,
anmation video… nhanh chóng đ ạt đỉnh cao của nó. Công nghệ này đ òi hỏi sự
mô tả các hình ảnh của máy PC với sự phong phú về chi tiết và màu sắc với sự
tốn kém rất lớn về thời gian và công sức. Gánh nặng đó hiện nay đã đư ợc giảm
nhẹ đáng kể nhờ các mô tả đơn giản nhưng đ ầy đủ của lý thuyết fractal về các
đối tượng tự nhiên. Với hình học phân hình khoa học máy tính có trong tay
một công cụ mô tả tự nhiên vô cùng mạnh mẽ.
Đề tài : Hình học Fractal Trang 10
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Ngoài các ứng dụng trong lĩnh vực giải trí, hình học phân hình còn có
mặt trong các ứng dụng tạo ra các hệ đồ hoạ trên máy tính. Các hệ này cho
phép người sử dụng tạo lập và chỉnh sửa hình ảnh, đồng thời cho phép tạo các
hiệu ứng vẽ rất tự nhiên hết sức hoàn hảo và phong phú, ví dụ hệ phần mềm
thương mại Fractal Design Painter của công ty Fractal Design. Hệ này cho
phép xem các hình ảnh dưới dạng hình hoạ véctơ cũng như sử dụng các ảnh
bitmap như các đối tượng. Nh ư đã biết, các ảnh bitmap hiển thị hết sức nhanh
chóng, thích hợp cho các ứng mang tính tốc độ, các ảnh véctơ m ất nhiều thời
gian hơn đ ể trình bày trên màn hình (vì phải được tạo ra bằng cách vẽ lại)
nhưng đòi hỏi rất ít vùng nh ớ làm việc. Do đó ý tưởng kết hợp ưu điểm của hai
loại đối tượng này sẽ giúp tiết kiệm nhiều thời gian cho người sử dụng các hệ
phần mềm này trong việc tạo và hiển thị các ảnh có độ phức tạp cao.
□ Ứ NG DỤNG TRONG CÔNG NGHỆ NÉN ẢNH:
Một trong những mục tiêu quan trọng hàng đầu của công nghệ xử lý
hình ảnh hiện nay là sự thể hiện hình ảnh thế giới thực với đầy đủ tính phong
phú và sống động trên máy tính. Vấn đề nan giải trong lĩnh vực này chủ yếu do
yêu cầu về không gian lưu trữ thông tin vư ợt quá khả năng lưu trữ của các thiết
bị thông thường. Có thể đơn cử một ví dụ đơn giản: 1 ảnh có chất lượng gần
như chụp đòi hỏi vùng nh ớ 24 bit cho 1 điểm ảnh, nên để hiện ảnh đó trên màn
hình mày tính có độ phân giải tương đối cao như 1024x768 cần xấp xỉ 2.25Mb.
Với các ảnh “thực” 24 bit này, để thể hiện được một hoạt cảnh trong thời gian
10 giây đòi hỏi xấp xỉ 700Mb dữ liệu, tức là bằng sức chứa của một đĩa CD-
ROM. Như vậy khó có thể đưa công nghệ multimedia lên PC vì nó đòi hỏi một
cơ sở dữ liệu ảnh và âm thanh khổng lồ.
Đứng trước bài toán này, khoa học máy tính đã giải quyết bằng những
cải tiến vượt bậc cả về phần cứng lẫn phần mềm. Tất cả các cải tiến đó dựa trên
ý tưởng nén thông tin hình ảnh trùng lặp. Tuy nhiên cho đ ến gần đây, các
phương pháp nén thông tin hình ảnh đều có 1 trong 2 yếu điểm sau:
● Cho tỉ lệ nén không cao. Đây là trường hợp của các phương pháp nén
không m ất thông tin.
● Cho tỉ lệ nén tương đối cao nhưng chất lượng ảnh nén quá kém so với
ảnh ban đầu. Đây là trường hợp của các ph ương pháp nén m ất thông
tin, ví dụ chuẩn nén JPEG.
Các nghiên cứu lý thuyết cho thấy để đạt một tỷ lệ nén hiệu quả (kích
thước dữ liệu nén giảm so với ban đầu ít nhất h àng trăm lần), phương pháp nén
mất thông tin là bắt buộc. Tuy nhiên một vấn đề đặt ra là làm th ế n ào có được
một phương pháp nén kết hợp cả tính hiệu quả về tỷ lệ nén lẫn chất lượng ảnh
so với ảnh ban đầu? Phương pháp nén ảnh phân h ình được áp dụng gần đây bởi
Iterated System đáp ứng đư ợc yêu cầu này.
Đề tài : Hình học Fractal Trang 11
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Như đã biết, với một ánh xạ co trên một không gian metric đầy đủ, luôn
tồn tại một điểm bất động xr sao cho:
Xr = f(xr)
Micheal F.Barnsley đã m ở rộng kết quả n ày cho một họ các ánh xạ co
f.Barnsley đã chứng minh được với một họ ánh xạ như vậy vẫn tồn tại một
“điểm” bất động xr.. Để ý rằng với một ánh xạ co, ta luôn tìm đ ược điểm bất
động của nó bằng cách lấy một giá trị khởi đầu rồi lặp lại nhiều lần ánh xạ đó
trên các kết quả thu được ở mỗi lần lặp. Số lần lặp càng nhiều thì giá trị tìm
được càng xấp xỉ chính xác giá trị của điểm bất động. Dựa vào nh ận xét này,
người ta đề nghị xem ảnh cần nén là “điểm bất động” của một họ ánh xạ co.
Khi đó đối với mỗi ảnh chỉ cần lưu thông tin về họ ánh xạ thích hợp, điều này
làm giảm đi rất nhiều dung lượng cần có để lưu trữ thông tin ảnh.
Việc tìm ra các ảnh co thích hợp đ ã được thực hiện tự động hoá nhờ quá
trình fractal một ảnh số hoá do công ty Iterated System đưa ra với sự tối ưu về
thời gian thực hiện. Kết quả nén cho bởi quá trình này rất cao, có thể đạt tỷ lệ
10000: 1 hoặc cao hơn. Một ứng dụng thương mại cụ thể của kỹ thuật nén phân
hình là bộ bách khoa toàn thư multimedia với tên gọi “Microsoft Encarta”
được đưa ra vào tháng 12/1992. Bộ bách khoa này bao gồm hơn 7 giờ âm
thanh, 100 hoạt cảnh, 800 bản đồ màu cùng với 7000 ảnh chụp cây cối, hoa
quả, con người, phong cảnh, động vật,… Tất cả đ ược mã hoá dưới dạng các dữ
liệu fractal và ch ỉ chiếm xấp xỉ 600Mb trên một đĩa compact.
Ngoài phương pháp nén phân hình của Barnsley, còn có một phương
pháp khác cũng đang được phát triển. Phương pháp đó do F.H.Preston,
A.F.Lehar, R.J.Stevens đưa ra dựa trên tính chất của đường cong Hilbert. Ý
tưởng cơ sở của phương pháp là sự biến đổi thông tin n chiều về thông tin một
chiều với sai số cực tiểu. Ảnh cần nén có thể xem là một đối tượng 3 chiều,
trong đó hai chiều dùng để thể hiện vị trí điểm ảnh, chiều thứ ba thể hiện màu
sắc của nó. Ảnh được quét theo thứ tự hình thành nên đường cong Hilbert chứ
không theo hàng từ trái sang phải nh ư thường lệ để đảm bảo các dữ liệu nén kế
tiếp nhau đại diện cho các khối ảnh kế cạnh nhau về vị trí trong ảnh gốc. Trong
quá trình quét như vậy, thông tin về m àu sắc của mỗi điểm ảnh đư ợc ghi nhận
lại. Kết quả cần nén sẽ được chuyển thành một tập tin có kích th ước nhỏ hơn
rất nhiều vì ch ỉ gồm các thông tin về m àu sắc. Phương pháp này thích hợp cho
các ảnh có khối cùng tông màu lớn cũng như các ảnh dithering.
□ Ứ NG DỤNG TRONG KHOA HỌC CƠ BẢN:
Có thể nói cùng với lý thuyết topo, hình học phân hình đ ã cung cấp cho
khoa học một công cụ khảo sát tự nhiên vô cùng mạnh mẽ như đã trình bày
trong phần I.1, vật lý học và toán học thế kỷ XX đối đầu với sự xuất hiện của
tính hỗn độn trong nhiều quá trình có tính quy luật của tự nhiên. Từ sự đối đầu
đó, trong những thập niên tiếp theo đ ã hình thành một lý thuyết mới chuyên
nghiên cứu về các hệ phi tuyến, gọi là lý thuyết hỗn độn. Sự khảo sát các bài
toán phi tuyến đòi h ỏi rất nhiều công sức trong việc tính toán và thể hiện các
quan sát một cách trực quan, do đó sự phát triển của lý thuyết này bị hạn chế
Đề tài : Hình học Fractal Trang 12
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
rất nhiều. Chỉ gần đây với sự ra đời của lý thuyết fractal và sự hỗ trợ đắt lực
của máy tình, các nghiên cứu chi tiết về sự hỗn độn mới được đẩy mạnh. Vai
trò của hình học phân hình trong lĩnh vực này thể hiện một cách trực quan các
cư xử kỳ dị của các tiến trình được khảo sát, qua đó tìm ra được các đặc trưng
hoặc các cấu trúc tương tự nhau trong các ngành khoa học khác nhau. Hình học
phân hình đã được áp dụng vào nghiên cứu lý thuyết từ tính, lý thuyết các phức
chất trong hoá học, lý thuyết tái định chuẩn và phương trình Yang & Lee của
vật lý, các nghiệm của các hệ phương trình phi tuyến được giải dựa trên
phương pháp xấp xỉ liên tiếp của Newton trong giải tích số,… Các kết quả thu
được giữ vai trò rất quan trọng trong các lĩnh vực tương ứng.
I.4 CÁC KIẾN THỨC CƠ SỞ CỦA LÝ THUYẾT H ÌNH HỌC PHÂN
HÌNH:
I.4.1 ĐỘ ĐO FRACTAL:
□ Số chiều Hausdorff của một tập hợp A Rn:
Cho trước các số thực dương s và . Gọi hs (A) là độ đo Hausdorff s-
chiều của tập A thì hs (A) được xác định bởi:
Hs (A) = lim h s (A)
0
với:
s
diam(Ui)s
h (A) = inf
i=1
trong đó:
diam (Ui) = sup [ d(x,y) : x,y Ui ], với d là metric Euclide trong không
gian Rn, [U1, U2,… ] là một phủ mở của A và diam(Ui) < , i.
Hausdorff đã chứng minh được sự tồn tại của một số DH(A) sao cho:
0 khi s > DH(A)
S
h (A) =
khi s < DH(A)
Giá trị DH(A) đư ợc gọi là số chiều Hausdorff của tập A.
Nói cách khác:
DH(A) thì hS(A) có th ể là một số thực dương 0 hay .
Định nghĩa n ày giữ vai trò quan trọng trong lý thuyết h ình học phân
hình hiện đại nhưng không có tính thực tiễn vì việc xác định số chiều theo định
ngh ĩa n ày rất phức tạp ngay cả với trường hợp tập A rất đơn giản. Do đó, xuất
phát từ định nghĩa này, Mandelbrot đã đưa ra khái niệm số chiều fractal tổng
quát dễ xác định hơn với ba dạng đặc biệt áp dụng cho từng loại đối tượng (tập
A) cụ thể. Sau đây chúng tôi sẽ trình bày các đ ịnh nghĩa về các dạng đặc biệt
Đề tài : Hình học Fractal Trang 13
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
đó, đồng thời chỉ ra mối liên hệ giữa chúng với định nghĩa số chiều của
Hausdorff.
□ SỐ CHIỀU TỰ ĐỒNG DẠNG: (SỐ CHIỀU HAUSDORFF-
BESCOVITCH ):
Định nghĩa:
Cho trước một cấu trúc tự đồng dạng được chia th ành N ph ần, hệ số thu
nhỏ của mỗi phần so với cấu trúc ban đầu là r. Ký hiệu DS là đ ại lư ợng xác
định bởi:
log N
DS =
log 1/r
Khi đó DS được gọi là số chiều tự đồng dạng của cấu trúc đó.
Ví dụ:
◊ Xét một hình vuông được chia th ành 9 hình vuông nhỏ với tỷ lệ đồng
dạng là 1/3. Khi đó số chiều tự đồng dạng của h ình vuông ban đầu
được xác định bởi:
log 9 log 3 2
2
Ds
1 log 3
log
1
3
◊ Xét một khối lập phương được chia thành 27 khối lập phương nhỏ
hơn với tỷ lệ đồng dạng 1/3. Ta có số chiều của tự đồng dạng của
khối lập phương được xác định bởi:
log 27 log 33
3
Ds
1 log 3
log
1
3
Hai ví dụ trên cho thấy định nghĩa số chiều tự đồng dạng phù h ợp với
định nghĩa thông thường của h ình học Euclide.
□ SỐ CHIỀU COMPA:
Số chiều được xác định theo định nghĩa này đư ợc áp dụng cho các
đường cong không phải là các đường cong tự đồng dạng hoàn toàn (như các
đường bờ biển, các con sông,…), nhưng có th ể sử dụng nhiều đơn vị khác nhau
để xác định độ dài của chúng.
Định nghĩa:
Đề tài : Hình học Fractal Trang 14
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Xét một đường cong không tự đồng dạng. Biểu diễn số đo của đường
cong trên hệ toạ độ log / log với:
- Trục ho ành: th ể hiện logarit của độ chính xác trong phép đo chiều
dài đư ờng cong. Độ chính xác được đặc tả bởi 1/s, với s là đơn vị
đo độ d ài. Ở đây giá trị s càng nhỏ thì độ chính xác của phép đo
càng lớn.
- Trục tung: thể hiện logarit của độ dài u đo được ứng với một đơn
vị đo s.
- d: là h ệ số góc của đ ường thẳng hồi qui dùng đ ể xấp xỉ các giá trị
đo u đo được dựa trên phương pháp bình phương cực tiểu. Ta có
quan hệ:
log u = d . log (1/s + b), b là hệ số tự do.
Khi đó số chiều compa DC đ ược xác định bởi:
DC = 1 + d
Ví dụ:
Xét đường cong 3/2 được xây dựng theo kỹ thuật initiator / generator
chỉ ra bởi h ình vẽ sau:
generator
initiator
generator
Biểu diễn các đại lượng có liên quan trên hệ toạ độ log/log đ ã được trình
bày ở trên với chú ý sau bước tạo sinh thứ k, đư ờng cong gồm 8 k đoạn, mỗi
đoạn có độ d ài s = 1 / 4k n ên độ dài của đường cong sẽ là 8k.1/4k = 2 k.
Khi đó giá trị trên trục hoành là log41 / 1 / 4k = k ứng với giá trị trên trục
tung là: log42k = k / 2 . Do đó ta xác định được d = 0.5.
Vậy: DC = 1 + 0.5 = 1.5
Đề tài : Hình học Fractal Trang 15
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
□ SỐ CHIỀU BOX-COUNTING:
Số chiều xác định theo định nghĩa này đư ợc áp dụng cho các đường
cong fractal không thể xác định số chiều theo 2 cách vừa trình bày. Cách tính
số chiều này có th ể áp dụng cho mọi cấu trúc trong mặt phẳng và mở rộng cho
cấu trúc trong không gian.
Định nghĩa:
Xét một cấu trúc fractal bất kỳ. Lần lượt đặt cấu trúc này lên một dãy
các lưới có kích thước ô lưới s giảm liên tiếp theo tỉ lệ ½. Gọi N(s) là các ô
lưới có kích thư ớc s có chứa một phần cấu trúc. Ta xây dựng hệ toạ độ log/log
như sau:
- Trục hoành biểu thị giá trị của đại lượng log2 (1/s).
- Trục tung biểu thị giá trị của đại lư ợng log2 N((s)).
- DB là hệ số góc của đường thẳng hồi qui đối với tập hữu hạn các
điểm (s, N(s)) của hệ toạ độ.
Khi đó ta có:
log2N(2 – (k+1)) – log2N(2 – k) N(2 – (k + 1))
DB = = log2
k+1 k
N(2 – k)
log22 – log2 2
DB xác định như vậy được gọi là số chiều box-counting của cấu trúc
fractal đ ã cho.
□ SỐ CHIỀU BOX-COUNTING TRONG MỐI LIÊN HỆ VỚI SỐ
CHIỀU HAUSDORFF:
Khoù khaên chuû yeáu khi tính soá chieàu Hausdorff laø vieäc xaùc ñònh toång voâ
haïn Σ diam(U )s . Soá chieàu box - counting ñôn giaûn hoùa thao taùc naøy
i
i 1
baèng caùch thay caùc soá haïng diam(U )s bôûi caùc soá haïng δ s . Ta coù moät
i
ñònh nghóa hình thöùc cuûa soá chieàu box - counting D treân moät taäp con
B
bò chaën A cuûa R n nhö sau
Định nghĩa:
Gọi N (A) là giá trị nhỏ nhất của các tập hợp có khả năng phủ A và có
đường kính tối đa là . Khi đó ta có:
Đề tài : Hình học Fractal Trang 16
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
log Nδ (A)
D b (A) lim
1
δ0 log
δ
Ñònh nghóa treân chæ ra raèng :
0 khi s Db (A)
N (A) . δ s
δ khi s Db (A)
Do ñoù :
D (A) inf { s : N (A) . δ s 0 } sup { s : N (A) . δ s }
b δ δ
Vaäy roõ raøng ñònh nghóa cuûa D B (A) töông töï vôùi ñònh nghóa cuûa D H (A) .
Tuy nhieân xaùc ñònh D B (A) ñôn giaûn hôn vì :
N (A) . δ s inf { Σ δs }
δ i1
trong ñoù :
{ U1, U 2 , ...} laø moät phuû höõu haïn cuûa A vaø diam(U ) δ, i
i
Tuy nhiên 2 định nghĩa số chiều này không phảI luôn cho kết quả
giống nhau. Ví dụ xét tập các số hữu tỷ trong khoảng đóng [0, 1]. Tập này có
số chiều box-counting là 1 trong khi số chiều Hausdorff tương ứng bằng 0.
Kết quả n ày còn có thể mở rộng cho tập con trù mật A của Rn, vớI DB(A) = n
và DH(A) n.
I.4.2 CÁC HỆ H ÀM LẶP IFS:
□ K hông gian ảnh Hausdorff:
Giả sử (X, d) là một không gian mtric đầy đủ. Ở đây X được giới hạn
bằng R2 và d là metric Euclide. Ký hiệu H(X) là không gian các tập con
compact khác rỗng của X. Ta có các định nghĩa sau:
Định nghĩa 1:
Khoảng cách từ một điểm x X đến một tập B H(X) được xác định
d(x, B) min d(x, y) : y B
bởi:
Định nghĩa 2:
Khoảng cách từ một tập A H(X) đ ến một tập B H(B) được xác định
bởi:
d(x, B) max d(x, B) : x A
Định nghĩa 3:
Đề tài : Hình học Fractal Trang 17
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Khoảng cách Hausdorff giữa hai điểm A và B H(H) được xác định
bởi:
h(A, B) max d(A, B), d(B, A
Với các định nghĩa trên ta có định lý:
Định lý về sự tồn tại của các IFS Fractal:
Ta có (H(X), h) là một không gian metric đầy đủ. Hơn nữa nếu
AnH(X) với n = 1,2,… lập th ành một d ãy Cauchy thì tập hợp A xác định bởi:
A = lim An
0
cũng thuộc H(X). A có thể đư ợc đặc tả như sau:
A = [ x X : một d ãy Cauchy [ xn An] hội tụ về x]
□ Ánh xạ co trên không gian Hausdorff:
Bổ đề 1:
Giả sử w: X X là một ánh xạ co liên tục trên không gian metric (X,
d). Khi đó w liên tục.
Ch ứng minh:
Cho s > 0. Gọi s là hệ số co của w. Khi đó:
d(w(x), w(y)) s.d(x,y) <
Khi và ch ỉ khi:
D(x,y) < = / s
Từ đó suy ra điều phải chứng minh.
Bổ đề 2:
Giả sử w: X X là m ột ánh xạ liên tục trên không gian metric(X,d).
Khi đó w ánh xạ không gian H(X) lên chính nó.
Ch ứng minh:
Giả sử S là một tập con compact khác rỗng của X. Khi đó ta có:
w(S) = [w(x) : x S] là một tập khác rỗng. Ta chứng minh w(S)
compact. Xét [ yn = w(xn) ] là m ột dãy vô hạn điểm của w(S).
Khi đó [xn] cũng là một dãy vô hạn điểm trong S. Vì S compact
nên tồn tại một dãy con [xn ] h ội tụ về một điểm x’ S, nhưng do
tính liên tục của w suy ra được [ yNn = f (xNn ) ] là một d ãy con
của [ yn ] h ội tụ về y’ w(S). Vậy w(S) compact.
Bổ đề được chứng minh.
Bổ đề 3 sau đây chỉ ra cách tạo một ánh xạ co trên không gian metric
(H(X), h) dựa trên một ánh xạ co trên (X,d).
Bổ đề 3:
Giả sử w: X X là một ánh xạ có không gian metric (X,d) với hệ số co
s. Khi đó ánh xạ w: H(X) H(X) được xác định bởi:
Đề tài : Hình học Fractal Trang 18
- ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
W(B) = [w(x): x B], với B thuộc H(X) cũng là một ánh xạ co trên
(H(X), h(d)) với hệ số co s.
Ch ứng minh:
Từ bổ đề 1 suy ra w: X X liên tục. Do đó theo bổ đề 2, ánh xạ H(X)
lên chính nó. Bây giờ xét B, C thuộc H(X).
Ta có:
d( w(B), w(C)) = max [ min [ d(w(x), w(y)): y C ] : x B ]
m ax [ min [ s.d(x,y) : y C ]: x B ]
= s.d(B, C)
Một cách tương tự:
d( w(C), w(B)) s.d(C, B)
Do đó:
H(w(B), w(C)) = max [d(w(B), w(C), w(C), w(B)) ]
s.max [ d(B, C), d(C, B) ]
= s.h(B, C)
Từ đó suy ra điều phải chứng minh.
Bổ đề 4 sau đây cung cấp một cách thức cơ b ản để nối kết các ánh xạ co
trên (H(X), h) thành các ánh xạ co mới trên (H(X), h):
Bổ đề 4:
Ký hiệu [wn ] là các ánh xạ co trên (H(X), h) với các hệ số co tương ứng
sn, n = 1, 2,…,N. Xác định W : H(X) H(X) bởi:
N
W(B) = wn (B)
n=1
với B H(X). Khi đó W là ánh xạ co với hệ số co s = max sn.
1n N
Ch ứng minh:
Kết quả trên được chứng minh bằng qui nạp.
Với N = 2: Xét B, C H(X).
Ta có:
h(W(B) , W(C)) h(w1(B) w 2 (B) , w1(C) w 2 (C))
max { h(w1(B) , w1(C)) , h(w2 (B) , w 2 (C))}
max { s1.h(B,C) , s 2 .h(B, C)}
s.h(B, C)
Vậy W là ánh xạ co với N = 2.
Giả sử khẳng định đúng với N = k. Ta chứng minh khẳng định đúng
với N = k + 1. Thật vậy, ta có:
Đề tài : Hình học Fractal Trang 19
nguon tai.lieu . vn