BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI Bounchanh NORHER PHƯƠNG PHÁP MONTE-CARLO VÀ ỨNG DỤNG TRONG BÀI TOÁN NỘI SUY HÀM NHIỀU BIẾN LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - 2016 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI Bounchanh NORHER PHƯƠNG PHÁP MONTE-CARLO VÀ ỨNG DỤNG TRONG BÀI TOÁN NỘI SUY HÀM NHIỀU BIẾN Chuyên ngành : Lý Thuyết Xác Suất Thống kê Toán học Mã số : 60.46.01.06 LUẬN VĂN THẠC SĨ TOÁN HỌC Giảng viên hướng dẫn : TS Nguyễn Văn Khải Hà Nội - 2016 MỤC LỤC Trang Lời cảm ơn iii Phần mở đầu iv Chương Kiến thức chuẩn bị 1.1 Không gian xác suất 1.2 Đại lượng ngẫu nhiên số đặc trưng 1.3 Vectơ ngẫu nhiên độc lập đại lượng ngẫu nhiên 1.4 Sự hội tụ dãy đại lượng ngẫu nhiên 1.4.1 Kì vọng, phương sai biến ngẫu nhiên 1.4.2 Sự độc lập biến ngẫu nhiên 1.4.3 Sự hội tụ dãy biến ngẫu nhiên Chương Phương pháp Monte-Carlo 2.1 Nội dung phương pháp Monte-Carlo 2.1.1 Khái niệm phương pháp Monte-Carlo 2.1.2 Các nội dung phương pháp Monte-Carlo 10 2.2 Sai số phương pháp Monte-Carlo 11 2.3 Đại lượng ngẫu nhiên phân bố mô hình hóa phép thử 19 2.4 2.3.1 Các phương pháp tạo số ngẫu nhiên 19 2.3.2 Thể đại lượng ngẫu nhiên 26 Thể mô hình rời rạc 31 i Chương Ứng dụng toán nội suy hàm nhiều biến 35 3.1 Nội suy hàm nhiều biến 35 Kết luận 49 Tài liệu tham khảo 50 ii Lời cảm ơn Trong trình học tập, nghiên cứu hoàn thành luận văn "Phương pháp Monte-Carlo ứng dụng toán nội suy hàm nhiều biến" nhận giúp đỡ động viên nhiều cá nhân tập thể tạo điều kiện giúp đỡ Trước hết, xin bày tỏ lòng biết ơn chân thành tới thầy cô giáo khoa Toán - Tin trường Đại học Sư phạm Hà Nội đem lại cho kiến thức bản, vô có ích năm học vừa qua Tôi xin gửi lời cảm ơn chân thành đến TS Nguyễn Văn Khải - người thầy trực tiếp hướng dẫn, tận tình bảo, giúp đỡ trình nghiên cứu hoàn thành luận văn Cuối xin gửi lời cảm ơn đến gia đình, bạn bè, người bên tôi, động viên khuyến khích trình thực đề tài nghiên cứu Mặc dùng có nhiều cố gắng song trình độ thời gian có giới hạn nên khóa luận không tránh khỏi thiếu sót Vì vậy, mong ý kiến đóng góp thầy cô bạn để khóa luận hoàn thành Tôi xin chân thành cảm ơn Hà Nội, tháng 10 năm 2016 Bounchanh NORHER Phần mở đầu Lý chọn đề tài Phương pháp Monte-Carlo đời thời với hệ máy tính điện tử Kể từ xuất vào khoảng năm 1950, phương pháp Monte-Carlo quan tâm nghiên cứu lý thuyết ứng dụng Phương pháp Monte-Carlo hiệu cho toán phức tạp có khối lượng tính toán lớn mà không dễ dàng giải phương pháp khác Một ứng dụng phương pháp Monte-Carlo giải toán nội suy hàm nhiều biến Về mong muốn tìm hiểu phương pháp Monte-Carlo, hướng dẫn TS Nguyễn Văn Khải, nghiên cứu đề tài “Phương pháp Monte-Carlo ứng dụng toán nội suy hàm nhiều biến” Mục đích nghiên cứu Luận văn nghiên cứu phương pháp Monte-Carlo ứng dụng toán nội suy hàm nhiều biến Nhiệm vụ nghiên cứu Luận văn nghiên cứu số kiến thức sở lý thuyết xác suất thống kê toán học, phương pháp Monte-Carlo (nội dung phương pháp, sai số phương pháp ứng dụng toán nội suy hàm nhiều biến ) Đối tượng nghiên cứu - Phương pháp Monte-Carlo vấn đề liên quan - Ứng dụng toán nội suy hàm nhiều biến Phương pháp nghiên cứu Phương pháp phân tích tổng hợp tài liệu có từ thống lại vấn liên quan Luận văn có cấu trúc chương: • Chương Kiến thức chuẩn bị : Chương trình bày số kiến thức lý thuyết xác suất thống kê toán học • Chương Cơ sở lý thuyết phương pháp Monte-Carlo : Chương trình bày nội dung phương pháp Monte-Carlo mô hình hóa phép thử • Chương Ứng dụng toán nội suy hàm nhiều biến : Chương trình bày ứng dụng phương pháp Monte-Carlo cho toán nội suy hàm nhiều biến Hà Nội, tháng 10 năm 2016 Bounchanh NORHER v Chương Kiến thức chuẩn bị 1.1 Không gian xác suất Định nghĩa 1.1.1 Xét tập Ω = ∅ Một σ - đại số tập Ω tập hợp F với tính chất : i) ∅, Ω ∈ F ii) Nếu A ∈ F Ac ∈ F Ac := Ω \ A phần bù A; ∞ iii) Nếu A1 , A2 ∈ F ∞ Ak ∈ F , k=1 Ak ∈ F k=1 Mỗi phần tử F gọi biến cố Định nghĩa 1.1.2 Giả sử F σ - đại số tập Ω Ta gọi P : F −→ [0, 1] độ đo xác suất : i) P(∅) = 0, P(Ω) = 1; ii) Nếu A1 , A2 , ∈ F tập đôi rời F ∞ ∞ Ak P = k=1 P (Ak ) k=1 Điều kéo theo A1 , A2 ∈ F : A1 ⊆ A2 P (A1 ) ≤ P (A2 ) Định nghĩa 1.1.3 Bộ ba (Ω, F, P) gọi không gian xác suất Ω tập khác ∅, F σ− đại số tập Ω P độ đo xác suất F Giả sử A, B ∈ F biến cố với P (B) > 0, xác suất để biến cố A xảy biết biến cố B xảy : P (A\B) := P (A ∩ B) P (B) Định nghĩa 1.1.4 Hai biến cố A B gọi độc lập : P (A ∩ B) = P (A) P (B) Định nghĩa 1.1.5 Cho Fi ⊆ F dãy σ - đại số với i = 1,2, Ta nói σ - đại số {Fi }∞ i=1 độc lập ∀1 ≤ k1 < < km biến cố Aki ∈ Fki ta có: P (Ak1 ∩ ∩ Akm ) = P (Ak1 ) P (Akm ) Ví dụ 1.1.1 Đem gieo đồng xu liên tiếp lần Gọi A1 biến cố : "Lần gieo thứ đồng xu xuất mặt ngửa", gọi A2 biến cố : "Lần gieo thứ đồng xu xuất mặt sấp" Khi A1 , A2 biến cố độc lập 1.2 Đại lượng ngẫu nhiên số đặc trưng Định nghĩa 1.2.1 Cho (Ω, F, P) không gian xác suất Một ánh xạ X : Ω −→ R gọi biến ngẫu nhiên B ∈ B (với B tập tập Borel R) ta có X−1 (B) ∈ F Khi ta nói X F - đo Định nghĩa 1.2.2 Hàm phân phối xác suất biến ngẫu nhiên X xác định theo công thức : FX(x) = P {X ≤ x}, ∀ x ∈ R Nếu hàm phân phối xác suất biến ngẫu nhiên X có đạo hàm: f (x) = F (x), ∀x ∈ R ta gọi f (x) hàm mật độ X Định nghĩa 1.2.3 Biến ngẫu nhiên X có phân bố đoạn [a, b] hàm mật độ có dạng :   b−a f (x) = 0 x ∈ [a, b] x ∈ / [a, b] Kí hiệu X ∼ U ([a, b]) Định nghĩa 1.2.4 Biến ngẫu nhiên X có phân phối Poisson với tham số λ > phân phối xác suất có dạng : λk e−λ , k = 0, 1, P [X = k] = k! Kí hiệu : X ∼ P (λ) Định nghĩa 1.2.5 Biến ngẫu nhiên X có phân phối mũ với tham số λ > hàm mật độ có dạng : λe−λx x ≥ f (x) = x < Định nghĩa 1.2.6 Với tập A ∈ F ta định nghĩa hàm tiêu tập A sau : IA (ω) = ω ∈ A ω ∈ /A Giả sử Ai ∈ F, i = 1, 2, , k dãy biến cố F , đó: k X= IAi i=1 gọi biến ngẫu nhiên đơn gản giá trị thực ( ∈ R) Ta có : ˆ k X dP := P (Ai ) Ω i=1 Nếu X biến ngẫu nhiên không âm : ˆ ˆ X dP := sup Y dP Y ≤X Ω Ω Gh := {X1 (i1 ), , Xm (im ) ∈ Rm : Xk (ik ) = Xk (0) + ik hk , ik ∈ Ik , ≤ k ≤ m} (3.2) đó: xk = Xk (0), xk = Xk (nk )(k = 1, m) Ik := {0, 1, , nk }, hk := Xk (nk ) − Xk (0) nk (3.3) hk > bước lưới trục Oxk Các điểm lưới Gh tạo thành đỉnh hình hộp rời Rm với cạnh có độ dài là: h1 , , hm Trong số hình hộp kể trên, xét hình hộp ∆(i), i ∈ I nằm hẳn miền G(gọi lưới nội suy) Trong đó: ∆(i) = ∆((i1 , , im )) := {(x1 , , xm ) ∈ Rm : Xk (ik ) ≤ xk < Xk (ik+1 ) = Xk (ik ) + hk , < k ≤ m} (3.4) I = {i = (i1 , , im ) ∈ I1 × × Im : ∆(i) ⊂ G} (3.4*) Cho Ký hiệu tập Gh tập hợp điểm lưới nằm miền G : ∆(i) ∩ Gh ⊂ G ∪ Gh Gh := i∈I gọi chúng mốc nội suy Tại mốc nội suy này, giả sử cho giá trị hàm f : F (i1 , , im ) := f (X1 (i1 ), , Xm (im )) (∀ (X1 (i1 ), , Xm (im )) ∈ Gh ) (3.5) Khi hk 0) (3.27) Nδ k=1 Hay là: P |f (x) − η N (x)| < D(η) ≥1− N ( − 2M m k=1 hk ) m (∀ > 2M hk ) k=1 (3.28) 46 η N (x) xác định theo công thức (3.26) Chứng minh Ta biết rằng: 1 E{η } = q1 (δ1 , x1 ) qm (δm , xm )×F (i1 +δ1 , , im +δm ) < +∞ δ1 =0 δm =0 Bởi vậy: D(η) = E(η ) − (E(η))2 < +∞ Trên sở bổ đề (1.1.3) ta có bao hàm thức biến cố sau: D(η) |Φ(x) − η N (x)| ≤ √ ⊂ Nδ D(η) ⊂ |Φ(x) − η N (x)| + |f (x) − Φ(x)| ≤ √ + 2M Nδ m hk ⊂ k=1 D(η) + 2M ⊂ |f (x) − η N (x)| ≤ √ Nδ m hk k=1 Khi ta suy ra: D(η) P |f (x)−η N (x)| ≤ √ +2M Nδ m hk ≥ P |Φ(x)−η N (x)| ≤ k=1 D(η) √ δ N (1) Nhưng từ (3.25), (3.26) bất đẳng thức Chebyshev ta có: D(η) P |Φ(x)−η N (x)| ≤ √ = P |E(η)− N Nδ Từ (1), (2) ta thu (3.27) m D(η) Trong (3.27) thay √ + 2M hk Nδ k=1 sai số (3.28) Từ (3.28) ta có: lim N D(η) η (j) | < √ ≥ 1−δ Nδ j=1 (2) ta có công thức đánh giá lim P {|f (x) − η N (x)| < } = (∀x ∈ ∆(i), ∀ > 0) N −→∞ |h|−→0 đó: (3.29) m |h| := hk k=1 47 (3.30) nghĩa (xem định nghĩa (1.3.4)): η N (x) ước lượng vững f (x), ∀x ∈ ∆ ⊂ G ⊂ G (khi N −→ ∞, |h| −→ 0) Để đánh giá sai số ước lượng (khi sử dụng để xấp xỉ hàm f (x)), ta ý tới (3.27) cần có tương đương sai số phương pháp 2M |h| D(η) sai số tính toán (theo phương pháp Monte-Carlo) √ , nghĩa là: Nδ D(η) 2M |h| ≈ √ Nδ hay |h| ≈ D(η) √ 2M δ N (3.31) Khi (3.27) có dạng: P |f (x) − η N (x)| < D(η) √ ≥ − δ (∀ > 0) δ N Kết hợp kết với (3.31) ta suy cho trước sai số độ tin cậy p xác định bước lưới nội suy hk (1 ≤ k ≤ m) số phép lặp N ước lượng vững η N (x) ≈ f (x) từ điều kiện: 4D(η) N≥ , (1 − p) m |h| = hk ≤ k=1 4M (3.32) Khi dùng thuật toán đệ quy dạng (1.3.1) để xác định số N thỏa mãn điều kiện (2.1.32) (thông qua việc ước lượng dần phương sai D(η) trình tính η N (x)) Tuy nhiên, với giả thiết nêu bổ đề (3.1.2), người ta M2 (xem [9]) D(η) ≤ |h|( + log m) Trên sở thay 2N (3.32)bởi điều kiện mạnh đây: M (1 + log m) 2, N≥ (1 − p) |h| ≤ 4M (3.32*) Trên ta xét việc sử dụng PPMC vào toán nội suy tuyến tính khúc Tương tự sử dụng phương pháp vào toán nội suy phi tuyến (nội suy Lagrange) 48 Kết luận Luận văn "Phương pháp Monte-Carlo ứng dụng toán nội suy hàm nhiều biến" tập trung nghiên cứu vấn đề sau : 1) Trình bày vấn đề sở lý thuyết lý thuyết xác suất thống kê 2) Trình bày nội dung phương pháp Monte-Carlo, cách đánh giá sai số theo ước lượng mô hình hóa phép thử 3) Nghiên cứu ứng dụng phương pháp Monte-Carlo toán nội suy hàm nhiều biến Các vấn đề phương pháp Monte-Carlo ứng dụng toán nội suy hàm nhiều biến phong phú đa dạng Tác giả mong nhận đóng góp thầy cô bạn để nghiên cứu sâu lý thuyết ứng dụng TÀI LIỆU THAM KHẢO [1] Nguyễn Quý Hỷ, phương pháp mô số Monte-Carlo, NXBĐHQG Hà Nội, 2004 [2] Nguyễn Văn Hạp, Nguyễn Quý Hỷ, Hồ thuần, Nguyễn Công Thúy, phương pháp tính, NXBĐH-Trung cấp chuyên nghiệp, 1970 [3] Nguyễn Duy Tiến, Vũ Viết Yên, Lý thuyết xác suất, NXBGD, 2003 [4] Phạm Văn Kiều, Lý thuyết xác suất thống kê toán học, NXBĐHSPHN, 1993 [5] X.M.Ermakov Phương pháp Monte-Carlo vấn đề liên quan., NXB Khoa học kỹ thuật, 1976 50 ... toán học, phương pháp Monte-Carlo (nội dung phương pháp, sai số phương pháp ứng dụng toán nội suy hàm nhiều biến ) Đối tượng nghiên cứu - Phương pháp Monte-Carlo vấn đề liên quan - Ứng dụng toán. .. nghiên cứu đề tài Phương pháp Monte-Carlo ứng dụng toán nội suy hàm nhiều biến Mục đích nghiên cứu Luận văn nghiên cứu phương pháp Monte-Carlo ứng dụng toán nội suy hàm nhiều biến Nhiệm vụ nghiên... GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI Bounchanh NORHER PHƯƠNG PHÁP MONTE-CARLO VÀ ỨNG DỤNG TRONG BÀI TOÁN NỘI SUY HÀM NHIỀU BIẾN Chuyên ngành : Lý Thuyết Xác Suất Thống kê Toán học