Số hóa Trung tâm Học liệ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 Ngun - 2013 Số hóa Trung tâm Học liệ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 Ngun – 2013 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ MỞ ĐẦU Đặt vấn đề Chúng ta biết hình học Euclide cho phép vẽ đo đạc hình có dạng đường thẳng đường cônic Tuy nhiên thực tế lúc đo đạc với đường Một minh chứng là, để đo đoạn bờ biển từ địa điểm A đến địa điểm B đó, ta sử dụng compa với độ mở mét tiến hành đo sát mép nước Đây cách làm mà thường hay nghĩ tới Tuy nhiên đo vậy, ta bỏ qua lồi lõm nhỏ mét Thu hẹp độ mở compa cịn 100cm ta tính thêm số chỗ lồi lõm, thu giá trị lớn xác chút Cứ tiếp tục làm ta tiến dần tới giới hạn thực địa điểm A địa điểm B Việc làm thực chất ta thay đổi đường cong thực gồ ghề khúc khủy phép đo liên độ mở giảm dần compa Vì chiều dài bờ biển khơng thể vơ tận nên phép đo phải hội tụ Đối với hình học Euclide Chẳng hạn đường tròn, phương pháp tổng dây cung ngày ngắn hội tụ đến chu vi hình trịn Nhưng hình Euclide mà ta quen thuộc từ hàng ngàn năm tam giác, tứ giác Ta thấy rằng, thu nhỏ độ mở compa ta luôn phát ―eo biển‖ nhỏ hơn, giá trị độ dài thực bờ biển tăng lên đến vơ Nói cách sâu xa hơn, phép đo Euclide thông thường không phản ánh hình dáng gồ ghề, phức tạp hình thể tồn thực tế Những đường gồ ghề gọi hình Fractal Ra đời muộn phân mơn hình học, Fractal - hình học phân dạng tên xuất lần đầu vào năm 1975 nhà toán học Benoit Mandelbrot mang hai quốc tịch Pháp - Mỹ Thuật ngữ Fractal ảnh hình dựa "sự tự đồng dạng" gây ấn tượng rõ rệt nhiều người, có người khơng có chút kiến thức khoa học Nó làm cho họ bị sốc thú vị Còn riêng Mandelbrot, làm cho ơng thích thú, tốn học vốn khoa học tiếng khô khan kỳ qi trở thành thiết thực gần gũi Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Hiện nay, cịn nhiều vấn đề lý thuyết Fractal tiếp tục nghiên cứu Một vấn đề quan tâm hàm nội suy Fractal Trước đây, toán nội suy đề cập Vậy tốn nội suy Fractal có khác biệt với tốn nội suy trước đó? Đây lý em chọn làm đề tài nghiên cứu khoa học mình: ‖Phép nội suy Fractal‖ với mục tiêu nắm bắt kiến thức Hình học Fractal, hàm Ftactal tìm hiểu nội suy Fractal có khác biệt với tốn nội suy trước - Đối tượng nghiên cứu: phép nội suy fractal trúc Fractal, phép nội suy thông thường sâu nghiên cứu hàm nội suy Fractal Hƣớng nghiên cứu đề tài - Tìm hiểu tổng quan Fractal - Tìm hiểu phép nội suy thơng thường - Tìm hiểu phép nội suy Fractal - Lập trình tính giá trị nội suy theo phương pháp nội suy Fractal Phƣơng pháp nghiên cứu - Nghiên cứu tài liệu viết tổng quan, phương pháp phân tích thiết kế đối tượng phương pháp thử nghiệm Ý nghĩa khoa học đề tài - Bản thân hiểu sâu hình học Fractal - Xây dựng chương trình nội suy Fractal từ rút khác biệt với tốn nội suy thơng thường Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ CHƢƠNG I: TỔNG QUAN VỀ FRACTAL 1.1 Các khái niệm khơng gian Fractal Tại hình học thường bị ví ―lạnh‖ ―khơ‖ ? Một lí nằm thiếu khả mơ tả hình đám mây, núi, bờ biển hay cối Mây khơng phải hình cầu, núi khơng phải hình nón, bờ biển khơng phải đường trịn, vỏ khơng phải trơn phẳng, tia sét không theo đường thẳng Sự đời lý thuyết hình học Fractal kết nhiều thập kỷ nỗ lực giải vấn đề nan giải nhiều ngành khoa học xác, đặc biệt vật lý toán học Một cách cụ thể, lý thuyết hình học Fractal xây dựng dựa vấn đề lớn quan tâm thập niên đầu kỷ 20 Các vấn đề bao gồm: + Tính hỗn độn q trình phát triển có quy luật tự nhiên + Sự mở rộng khái niệm số chiều độ đo lý thuyết hình học Euclide cổ điển Năm 1979, nhà tốn học Benoit Mandelbrot áp dụng tập Mandelbrot đầy kì ảo lên máy tính Ơng khám phá lãnh vực hình học đầy thú vị cho phép phản ánh giới thực cách tự nhiên so với hình học Euclide Tất hình ảnh mà ta thường gặp tự nhiên : núi, mây, sơng, nước… máy tính có khả mơ tả phương pháp Fractal Để thấy rõ sức mạnh Fractal mô tả tự nhiên bạn xem thêm sưu tập ảnh Fractal kèm theo Hình 1.1 Ảnh Fractal Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Trong giai đoạn B Mandelbrot nhà toán hoc khác A.Douady J.Hubbard đặt móng phát triển lí thuyết cho hình học Fractal Các kết đạt chủ yếu tập trung tính chất cấu trúc Fractal sở tập Maldenbrot tập Julia Ngồi ngiên cứu khác cố gắng tìm kiếm mối quan hệ cấu trúc này, ví dụ mối quan hệ Maldenbrot Julia Dựa cơng trình Maldenbrot (trong năm 1976, 1979, 1982) Hutchinson(1981), vào năm 1986,1988 Michael F.Barnsley M.Begger phát triển lý thuyết biểu diễn đối tượng tự nhiên dựa sở lý thuyết hệ hàm lặp IFS Các hệ hàm lặp bao gồm hữu hạn phép biến đổi affine cho phép với giúp đỡ máy tính tạo nên hình ảnh đối tượng tự nhiên Theo lý thuyết hình học Euclide cổ điển có hiệu lực việc biểu diển đối tượng nhân tạo tòa nhà, cổ máy lại hồn tồn khơng thích hợp cho việc biểu diễn đối tượng giới thực đòi hỏi lượng lớn đặc tả cần có Nếu hình học Euclide yếu tố sở đường thẳng, đường trịn, hình vng,… lý thuyết IFS mở rộng hình học cổ điển với yếu tố sở vô số thuật toán để vẽ nên Fractal tự nhiên Chúng ta nghiên cứu phương pháp Fractal tạo ứng dụng biến đổi đơn giản không gian đơn giản Chúng ta giải thích hệ hàm lặp (IFS) gì? định nghĩa Fractal nào? Hệ hàm lặp cung cấp khung tiện ích cho việc mơ tả, phân loại, liên kết Fractal Hai thuật toán, thuật toán lặp ngẫu nhiên thuật tốn xác định, cho việc tính tốn ảnh Fractal trình bày Đáng ý vấn đề nghịch đảo: đưa đến tập compact R2 làm cách để tìm xấp xỉ Fractal cho nó? Một phần câu trả lời cung cấp Định lý Collage 1.1.1 Các không gian tính chất chúng Trong hình học Fractal quan tâm đến cấu trúc tập khơng gian ―hình học‖ đơn giản khác Như không gian ký hiệu X Nó khơng gian mà vẽ Fractal; Hình học Fractal Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ xây dựng sở lý thuyết giải tích hàm, sử dụng kiến thức khơng gian Metric, khơng gian Hausdorff (cịn gọi không gian Fractal) Từ nay, với chúng ta, tập khơng gian Bởi khơng gian đơn giản, tập Fractal 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 tập hợp.Các điểm không gian phần tử tập hợp Ví dụ + X = R Mỗi điểm x X số thực, đấu chấm dịng Hình 1.2 Một điểm X R + X = C[0,1], tập hợp hàm liên tục hàm khoảng [0,1]= {x ∈ R : 0≤ x ≤1} R Một hàm f ∈ X hàm f: [0,1]→R f biểu thị đồ thị Hình 1.3 Một điểm f khơng gian hàm liên trục đoạn [0, 1] Định nghĩa 1.1.2 Một không gian metric (X, d) không gian X với hàm giá trị thực d: X x X R, d hàm lấy khoảng cách cặp điểm x y X Chúng ta yêu cầu d tuân theo điều kiện sau: a d(x, y) = d(y, x) b 0< d(x, y) < x, y x, y X X, x y Soá hóa Trung tâm Học liệu c d(x, x) = http://lrc.tnu.edu.vn/ x X d d(x, y) < d(x, z) + d(z,y) x, y, z X Hàm d gọi metric Ví dụ 1.: Trong khơng gian X = R2, điểm x R2 là: + d(x,y) = (Metric Euclid) + d(x,y) = |x1-y1|+|x2-y2| Ví dụ Khơng gian mã X định nghĩa: d(x, y)=d(x1x2x3…y1y2y3…) = ∑ i xi yi ( N 1) i (∑, d) không gian metric Một không gian metric tập hợp điểm song song với hàm mang theo hai yếu tố tập hợp đưa khoảng cách chúng Tập hợp tập hợp điểm tập hợp ảnh Một không gian metric tập hợp tất tập hợp ( đóng bị chặn ) khơng gian Tập hợp tưởng tượng tập hợp tất tranh đen trắng, tập hợp khơng gian biểu diễn tranh đen điểm tập hợp nơi khác màu trắng Khơng gian lớn, bao hàm, ví dụ, vẽ đường kẻ bạn, đề địa United Nations ( nhiều tranh khác ) Định nghĩa 1.1.3 Hai metric d1 d2 không gian X tương đương tồn 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) (X2, d2) tương đương có hàm h: X1 ~ X2 ánh xạ 1-1 ánh xạ lên (nó có nghịch đảo), metric d ~ X1 định nghĩa bởi: d (x, y) = d2(h(x), h(y)), x, y X tương đương với d1 Ví dụ + X1 = [1, 2], X2 = [0, 1] với d1: Euclide X1, d2(x, y) = 2.|x - y| X2 Ta có (X1, d1) (X2, d2) hai không gian metric tương đương + X = (0, 1] = {x R: 0< x 1} d1(x, y) = |x - y| d2(x, y)= |1/x – 1/y| Ta có (X, d1) (X, d2) hai khơng gian metric khơng tương đương Số hóa Trung tâm Học liệ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) liên tục với > x X1, có >0 thỏa mãn: d1(x, y) < => d2(f(x), f(y)) < Nếu f ánh xạ 1-1 ánh xạ lên, có nghịch đảo, nghịch đảo f-1 f liên tục, nói f phép biến đổi topo X1 X2 Trong trường hợp đó, nói X1 X2 homeomorphic * Metric Haudoff Mục tiêu định nghĩa metric Hausdorff không gian Metric cho ―khoảng cách‖ tranh Metric Hausdorff thức định nghĩa bên Để tìm thấy khoảng cách Hausdorff h(A,B) hai tập hợp không gian, A B, thực thủ tục sau Với điểm x A, tìm điểm kết thúc y nằm B Đo khoảng cách tối thiểu ( A kết thúc từ B ) chọn lớn Đây khoảng cách Hausdorff Hình 1.4 biểu diễn ba ví dụ tập hợp A B khoảng cách Hausdorff (dựa khoảng cách Euclidean) chúng, đánh dấu dòng Metric Hausdorff khơng nhạy để thỏa mãn, khơng thể lựa chọn khoảng cách hai tranh người nhỏ khoảng cách tranh người tranh dương xỉ Hình 1.4: Các tập hợp A B khoảng cách Hausdorff chúng, biểu thị đường kẻ Trong ví dụ trên, khoảng cách tối thiểu lớn đo từ B đến A; hai khác, đo từ A đến B b Chuỗi Cauchy, điểm giới hạn, tập đóng, tập hồn hảo khơng gian metric đầy đủ Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ KẾT LUẬN CHUNG So với ngành khác hình học fractal ngành khoa học máy tính cịn non trẻ mẻ Mới phát triển khoảng 20 năm với mà ngành đạt khẳng định đạt bước phát triển mạnh mẽ năm tới Nét đẹp điều bí ẩn xung quanh hệ hàm lặp ảnh fractal cịn hút trí tị mị óc tưởng tượng người lao vào khám phá Về mặt thực tiễn, khơng thể phủ nhận với lý thuyết hình học tay người có tay cơng cụ đầy sức mạnh để mô tả giới thực mà trước hình học cổ điển chưa thực Những ứng dụng hình học fractal thực tế ngày phong phú mở rộng tới nhiều ngành, lĩnh vực khác Khi thực đề tài này, mục đích em tìm hiểu vấn đề nhất, lý thuyết tảng để xây dựng nên phép nội suy fractal Từ phần tìm hiểu trên, hiểu tính tốn giá trị nội suy khơng theo phương pháp thơng thường mà cịn tính tốn theo nội suy fractal Với nội suy thơng thường, sử dụng mốc nội suy, cặp giá trị tương ứng cho trước để tính tốn từ xây dựng đồ thị hàm số qua điểm cho Với phương pháp nội suy thông thường, sử dụng hàm thật đa thức nội suy Còn phương pháp nội suy fractal sử dụng hàm thậ hàm nội suy Fractal để tính tốn Cũng giống hàm bản, chúng phận hình học, chúng biểu thị ngắn gọn cơng thức, tính tốn cách nhanh chóng Điểm khác biệt tính chất Fractal chúng Ví dụ, chúng có chiều Fractal không nguyên Chúng dễ dàng làm việc với hàm nội suy Fractal, hàm mà thường làm việc với tập hợp điểm với lý thuyết IFS sử dụng ánh xạ affine để tìm đồ thị qua hàm phải tìm Chúng sử dụng để tạo mơ hình cấu trúc vật chất Qua luận văn này, chúng em trình bày phương pháp nội suy Fractal tìm IFS mà tập hút đồ thị hàm nội suy liệu Thuật toán nội suy Fractal tìm hàm gần cách lặp vơ hạn Fractal Hơn nữa, 61 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ phương pháp Fractal cho kết xấp xỉ tốt Những điều thu sau làm đề tài chưa nhiều chưa thể ứng dụng nhiều vào thực tế bước khởi đầu để nghiên cứu tốt vấn đề phức tạp sau 62 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Tài liệu tham khảo Tiếng Việt: Phạm Kỳ Anh (1996), Giải tích số, NXB Đại học Quốc Gia Hà Nội, Hà Nội Phạm Văn Ất (2006), Kỹ thuật lập trình C sở nâng cao, NXB Giao thông vận tải, Hà Nội Hồng Tụy (2003), Hàm thực giải tích hàm, Nhà xuất Đại học Quốc gia Hà Nội Nguyễn Minh Đức – Phạm Trọng Tơn (2003), Tìm hiểu lý thuyết hình học Fractal ứng dụng việc cài đặt số đường, mặt Fractal phổ biến, Thành phố Hồ Chí Minh Tiếng Anh: M F Barnsley (1988), “Fractals Everywhere”, Academic Press, Inc M.F Barnsley (1986), ― Fractal Functions and interpolation‖, Constr, Approx Stephen Welstead, Fractals and Wavelet Image Compression Internet: http://www.nahee.com/spanky/www/fractint/fractint.html http://en.wikipedia.org/wiki/Fractal.html http://tailieu.vn/xem-tai-lieu/chuong-3-noi-suy-va-xap-xi-ham.148834.html 63 Soá hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ PHỤ LỤC namespace Factal { public partial class frmMain : Form { public frmMain() { InitializeComponent(); } private void thoToolStripMenuItem_Click(object sender, EventArgs e) { this.Close(); } private void langrangToolStripMenuItem_Click(object sender, EventArgs e) { frmLangrang frm = new frmLangrang(); frm.MdiParent = this; frm.Show(); } private void thôngThườngToolStripMenuItem_Click(object sender, EventArgs e) { frmFractal frm = new frmFractal(); frm.MdiParent = this; frm.Show(); } private void biếnẨnToolStripMenuItem_Click(object sender, EventArgs e) { frmFractalbienan frm = new frmFractalbienan(); frm.MdiParent = this; frm.Show(); } private void thôngTinTácGiảToolStripMenuItem_Click(object sender, EventArgs e) { frmAbout frm = new frmAbout(); frm.MdiParent = this; frm.Show(); } } } namespace Factal { public partial class frmFractal : Form { public frmFractal() { InitializeComponent(); } 64 Soá hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ private void button4_Click(object sender, EventArgs e) { this.Close(); } private void button1_Click(object sender, EventArgs e) { OpenFileDialog ofd = new OpenFileDialog(); ofd.Title = "Mở tệp tin"; ofd.Filter = "Text File(*.txt)|*.txt"; DialogResult dr = ofd.ShowDialog(); if (dr == DialogResult.OK) { try { string[] lines = File.ReadAllLines(ofd.FileName); int numrow; numrow = 0; foreach (string line in lines) { if (line.Trim() != "") { char[] seps = { '\t', '|' }; string[] st = line.Split(seps); if (numrow ==2) { clsVariables.n = Convert.ToDouble(st[0]); } if (numrow ==3) { clsVariables.x = new double[Convert.ToInt32(clsVariables.n)+1]; for (int i = 0; i