Đăng ký Đăng nhập
Trang chủ Tính tích phân bội bằng phương pháp mô phỏng số monte carlo...

Tài liệu Tính tích phân bội bằng phương pháp mô phỏng số monte carlo

.PDF
71
1009
111

Mô tả:

TRƯỜNG ĐẠI HỌC CẦN THƠ KHOA KHOA HỌC TỰ NHIÊN BỘ MÔN TOÁN ------------ LUẬN VĂN TỐT NGHIỆP ĐẠI HỌC TÍNH TÍCH PHÂN BỘI BẰNG PHƯƠNG PHÁP MÔ PHỎNG SỐ MONTE CARLO GIÁO VIÊN HƯỚNG DẪN SINH VIÊN THỰC HIỆN Ths. Nguyễn Thị Hồng Dân Lê Thị Vân Anh (Bộ môn Toán – Khoa KHTN) MSSV: 1090142 Ngành: Toán Ứng Dụng K35 CẦN THƠ 05/2013 LỜI CẢM ƠN Em xin bày tỏ lòng biết ơn của mình đến cô Nguyễn Thị Hồng Dân đã tận tình giúp đỡ để em có thể hoàn thành luận văn, đồng thời cũng là người cố vấn học tập đã dìu dắt em trong suốt bốn năm học của quãng đời sinh viên. Cám ơn Cô đã luôn lắng nghe, giúp đỡ và chỉ bảo để em có thể vượt qua những khó khăn mà mình vấp phải trong quá trình làm luận văn. Em xin cảm ơn quý Thầy Cô trường Đại Học Cần Thơ đã dạy dỗ em, chuẩn bị cho em những hành trang tri thức để bước vào đời. Đặc biệt là những Thầy Cô trong bộ môn Toán của khoa Khoa Học Tự Nhiên đã tận tình truyền đạt cho em những kiến thức quý báu và tạo mọi điều kiện thuận lợi cho em trong suốt quá trình học tập nghiên cứu và đến khi hoàn thành đề tài luận văn này. Xin chân thành cảm ơn các Thầy, Cô trong hội đồng chấm luận văn đã cho em những đóng góp quý báu để hoàn chỉnh luận văn này. Cảm ơn bố mẹ đã luôn ở bên em, yêu thương, dạy dỗ và dõi theo những bước chân của em từ khi còn bé cho đến lúc trưởng thành, là người luôn động viên và chăm sóc cho em để em có thể yên tâm học tập. Và cuối cùng xin cảm ơn những người bạn thân thiết đã cùng em đi qua quãng đời sinh viên với biết bao kỉ niệm đẹp, cùng em vượt qua những khó khăn, thử thách trong học học tập và trong cuộc sống hàng ngày. Một lần nữa em xin chân thành cảm ơn. Chúc tất cả mọi người sức khỏe và thành đạt. Cần Thơ, ngày 20 tháng 03 năm 2013 Lê Thị Vân Anh 1 DANH MỤC CÁC BẢNG Bảng 2.1……............................……………………………………………………49 Bảng 2.2………............................…………………………………………………53 Bảng 2.3…………………............................……………………………………....61 Bảng 2.4……………………............................…………………………………....63 2 DANH MỤC CÁC HÌNH Hình 1: mô hình mô phỏng Monte Carlo………………………………………….26 Hình 2: Miền D là hình thang cong loại 1…………………………………………34 Hình 3: Thể tích của vật thể………………………………………..……………....35 Hình 4: Miền D là hình thang cong loại 2………………………....………………36 3 MỤC LỤC LỜI CẢM ƠN ............................................................................................................1 PHẦN MỞ ĐẦU ........................................................................................................5 CHƢƠNG 1................................................................................................................7 1.1 Giới thiệu .........................................................................................................7 1.2 Những nội dung cơ bản của phƣơng pháp Monte Carlo ............................ 9 1.3 Thể hiện các vectơ ngẫu nhiên và thể hiện các phân bố đều .................... 10 1.4. Các bƣớc trong một bài toán mô phỏng số Monte Carlo ......................... 25 1.5 Sự mô phỏng và sai số ƣớc lƣợng ................................................................ 26 1.6 Các phƣơng pháp làm giảm phƣơng sai trong mô phỏng ........................ 29 1.7 Ví dụ dùng mô phỏng Monte Carlo tính xấp xỉ giá trị của  ..................32 1.8 Sơ lƣợc về các phƣơng pháp tính tích phân bội trong giải tích ................33 CHƢƠNG 2..............................................................................................................44 2.1 Phƣơng pháp cơ bản tính tích phân: .......................................................... 44 2.2 Phƣơng pháp hình học tính tích phân: ....................................................... 50 2.3 Phƣơng pháp kết hợp với giải tích số .......................................................... 57 CHƢƠNG 3..............................................................................................................66 PHỤ LỤC CÁC ĐOẠN CODE MATLAB...........................................................68 TÀI LIỆU THAM KHẢO ...................................................................................... 70 4 PHẦN MỞ ĐẦU I. Lý do chọn đề tài Tính tích phân nói chung và tích phân bội nói riêng là một trong những lĩnh vực lý thú và có tính ứng dụng cao trong toán học. Việc tính tích phân bằng tay đã được phát triển từ rất lâu và trở thành một trong những kĩ năng quen thuộc và cần thiết của những người học toán. Khi tính toán tích phân bằng tay, người ta cần lựa chọn các phương pháp có khối lượng tính toán ít do sự hạn chế về sức lực và thời gian của người giải. Tuy nhiên, sự ra đời của các máy tính điện tử đã đảo lộn những quan niệm trước đó về phương pháp giải mỗi bài toán. Khi sử dụng các máy tính điện tử ta lại lựa chọn các phương pháp thích hợp với hoạt động của máy, nghĩa là chúng được diễn đạt bằng những thuật toán đơn giản, ít những lệnh lôgic mặc dù khối lượng tính toán có thể tăng lên so với các phương pháp giải bằng tay. Một trong những phương pháp đó là “phương pháp mô phỏng số Monte Carlo”. Phương pháp Monte Carlo đóng một vai trò hết sức to lớn trong toán học. Đây là phương pháp tính bằng số hiệu quả cho nhiều bài toán liên quan đến nhiều biến số mà không dễ dàng giải được bằng các phương pháp khác, chẳng hạn như tính tích phân bội. Vì thế khi có thể dùng phương pháp Monte Carlo kết hợp với máy tính để tính tích phân bội thì sẽ làm cho công việc trở lên nhẹ nhàng hơn và tiết kiệm rất nhiều công sức, tiền của. Đây cũng là lý do khiến em chọn đề tài này. II. Mục đích nghiên cứu - Tìm hiểu về phương pháp Monte Carlo. - Xem xét đến các phương pháp phù hợp và ứng dụng của phương pháp Monte Carlo trong tính tích phân bội. - Kiểm chứng lại độ chính xác của việc tính tích phân bội bằng phương pháp mô phỏng số Monte Carlo. III. Đối tƣợng và phạm vi nghiên cứu - Đối tượng nghiên cứu: tích phân bội. 5 - Phạm vi nghiên cứu: các tích phân cơ bản và dạng hỗn hợp. Tập trung chủ yếu vào tích phân hai lớp và ba lớp. IV. Phƣơng pháp nghiên cứu - Tổng hợp lý thuyết liên quan đến phương pháp mô phỏng số Monte Carlo. - Thử nghiệm với các tích phân bội được dùng làm ví dụ. - Sử dụng phần mềm Matlab thực hiện các xử lý. - So sánh độ chính xác giữa việc tính bằng tay và tính bằng máy tính. 5. Nội dung Luận văn được cấu trúc gồm có phần mở đầu, phần nội dung, phụ lục và tài liệu tham khảo. Phần nội dung gồm có 3 chương: Chương 1: Tổng quan về phương pháp mô phỏng số Monte Carlo. Chương này trình bày các khái niệm, định lý và mệnh đề cần thiết cho luận văn như những nội dung cơ bản của phương pháp mô phỏng số Monte Carlo, các phương pháp tạo số ngẫu nhiên, các kĩ thuật làm giảm phương sai, sơ lược về các phương pháp tính tích phân bội trong giải tích. Kết quả của chương này được dùng cho các chương sau. Chương 2: Sử dụng phương pháp mô phỏng số Monte Carlo trong tính tích phân bội. Chương này giới thiệu cụ thể về sử dụng phương pháp mô phỏng số Monte Carlo trong việc tính tích phân bội và so sánh với tính tích phân bội bằng tay. Chương 3: Kết luận. Chương này đưa ra những nhận xét về hiệu quả và các thuận lợi trong việc sử dụng phương pháp mô phỏng số Monte Carlo để tính tích phân bội. 6 CHƢƠNG 1 TỔNG QUAN VỀ PHƢƠNG PHÁP MÔ PHỎNG SỐ MONTE CARLO 1.1 Giới thiệu Vào những năm 1930, các nhà vật lý hạt nhân của phòng thí nghiệm quốc gia Los Alamos là Enrico Fermi và Stanislaw Ulam đầu tiên đã có ý tưởng về mô phỏng, sau đó Ulam liên lạc với John Von Neuman để nghiên cứu về ý tưởng đó. Phòng thí nghiệm vật lý ở Los Alamos đã nghiên cứu che chắn bức xạ và khoảng cách mà các neutron có khả năng sẽ đi qua các vật liệu khác. Mặc dù đã có hầu hết dữ liệu cần thiết, chẳng hạn như thời gian mà các neutron sẽ đi trong một chất trước khi va chạm với một nguyên tử hay có bao nhiêu năng lượng sẽ được tạo ra khi va chạm các hạt trên, tuy nhiên vấn đề không thể giải quyết với các phân tích tính toán thông thường. John von Neumann và Stanislaw Ulam cho rằng vấn đề nên được giải quyết theo một mô hình thử nghiệm trên một máy tính. Sau đó họ đặt tên phương pháp này là phương pháp mô phỏng Monte Carlo. Tuy nhiên, phương pháp Monte Carlo này thật sự tỏ ra hữu hiệu và được phát triển mạnh mẽ gắn liền với việc ra đời của máy tính điện tử đầu tiên (từ năm 1945) trong những nghiên cứu của dự án Mahattan, hoặc nghiên cứu bom Hydrogen ở Los Alamos... và đến nay nó đã và đang đóng góp rất to lớn cho nhiều lĩnh vực, mang lại hiệu quả kinh tế cao và tiết kiệm được nhiều thời gian, công sức và của cải cho các nhà nghiên cứu. Ưu điểm nổi bật của phương pháp mô phỏng Monte Carlo là có thể áp dụng vào các bài toán thực tế dạng rất khó hoặc không có khả năng quan sát diễn tiến của nó, để xây dựng mô hình mô phỏng hiệu quả trên máy tính và cho ra nhiều kịch bản tương lai của vấn đề giúp người nghiên cứu có thể phân tích, đánh giá vấn đề một cách tổng quát và hiệu quả. Ví dụ, các thí nghiệm loại diễn biến quá chậm (như diễn biến các quá trình sinh học trong sự cân bằng sinh thái…), thí nghiệm diễn biến quá nhanh (các quá trình khuếch tán,…),nguy hiểm (các phản ứng hạt nhân,…) hoặc loại thí nghiệm giá đắt (như rủi ro trong kinh doanh). 7 Như khi nghiên cứu quá trình khuếch tán qua những lá chắn dày của các hạt, bài toán của vật lý hạt nhân đưa về việc tính các tích phân bội 3n lớp (trong đó n là số lần va chạm của một hạt qua lá chắn). Ngay cả khi số lần va chạm nói trên không lớn lắm như n  4 , thì ta đã cần tính một tích phân bội 12 lớp. Với phương pháp kinh điển của giải tích số thì số phép tính cần thực hiện để tính tích phân bội này là 2, 4.1014 . Nếu dùng máy tính loại Minsk-22 với 5000 phép tính/giây thì nó phải làm việc liên tục trong một khoảng thời gian là: 2, 4.1024 T  1543 năm  15 thế kỉ. 5000  3600  24  30 12 Tuy nhiên khi chúng ta sử dụng phương Monte Carlo để mô hình hóa trên máy tính điện tử và sử dụng công thức gần đúng thì số lần lặp lại phép thử cần là N=10.000 thì ta nhận thấy rằng việc tính tích phân 12 lớp đã nêu có thời gian tính bằng phút chứ không phải bằng thế kỉ. Việc dùng các phép thử ngẫu nhiên trên máy tính để tính tích phân bội nói trên cũng như để giải các hệ phương trình đại số tuyến tính liên quan đến các phương trình tích phân dịch chuyển (trong không gian nhiều chiều của vật lý hạt nhân) là những ứng dụng đầu tiên của phương pháp Monte Carlo. Những ứng dụng này đã được người Mỹ giữ bí mật cùng với hàng loạt bí mật khác liên quan đến việc chế tạo bom hạt nhân. Mãi đến năm 1949 (hai năm sau khi Liên Xô thử quả bom hạt nhân đầu tiên), người ta mới cho công bố ở Mỹ các công trình gắn với tên gọi “phương pháp Monte Carlo”. Sau người Mỹ, những công trình nghiên cứu và ứng dụng phương pháp Monte Carlo của người Nga (Liên Xô cũ) đã xuất hiện vào những năm 1955-1956. Nhưng do tầm quan trọng của nó nên chỉ 15 năm sau (1955-1970) đã có tới 2000 công trình được công bố ở Liên Xô về phương pháp Monte Carlo. Có thể khái quát về phương pháp Monte Carlo (MC) là một lớp các thuật toán tính toán dựa trên lấy mẫu lặp đi lặp lại để tính các kết quả, nó đặc biệt phù hợp với việc sử dụng máy tính điện tử làm công cụ tính toán do phải tạo ra các số ngẫu nhiên đầu vào (random number), giả ngẫu nhiên (pseudo random number) hay tựa ngẫu nhiên (quasi-random number). 8 Sau cùng, có thể thấy được một vài thuận lợi khi sử dụng mô phỏng hơn các thuật toán xác định khác là: - Hiệu suất thực thi: đối với nhiều vấn đề thuật toán mô phỏng MC là nhanh nhất so với các thuật toán xác định khác. - Tính dễ dàng: nó thường dễ mô tả và tiến hành so với những thuật toán xác định do tiến hành trên máy tính. - Tính linh hoạt: việc mô phỏng có thể được thực hiện nhiều lần hoặc sửa lại cho phù hợp một cách dễ dàng mà các thuật toán xác định khó có thể làm được. - Ít tốn kém: do không phải tiến hành thí nghiệm trên thực tế. Chương này giới thiệu về mô hình của phương pháp mô phỏng, cách tạo ra số ngẫu nhiên và lấy mẫu trong mô phỏng. 1.2 Những nội dung cơ bản của phƣơng pháp Monte Carlo - Nội dung thứ nhất: thiết lập được mô hình xác suất tương ứng với mỗi bài toán tất định cần giải bằng số. Nghĩa là ta phải xác lập được một bài xác suất tương đương mà lời giải y của bài toán tất định được xác định từ lời giải x của bài toán xác suất bởi một quan hệ hàm tuyến tính: y  f ( x) - Nội dung thứ hai : Ta phải giải gần đúng bài toán xác suất tương đương trong mô hình thông qua các phép thử ngẫu nhiên. Đây là quá trình thể hiện mô hình xác suất tương ứng. Từ kết quả của các phép thử trong quá trình nói trên, ta có thể thiết lập một vectơ (hay đại lượng) ngẫu nhiên X  Rm xấp xỉ với lời giải x  R m của mô hình xác suất. Nếu lời giải y  R n của bài toán tất định được xác định từ x bởi quan hệ hàm tuyến tính y  f ( x) (với f là hàm liên tục), thì ta có thể xấp xỉ nó bởi vectơ (hay đại lượng ngẫu nhiên) Y  f ( X )  R n nghĩa là: X  x  R m ; Y  f ( X )  f ( x)  y  R n Trong đó, Y là ước lượng Monte Carlo (hoặc phỏng ước) đối với lời giải y của bài toán tất định, X là ước lượng Monte Carlo (hoặc phỏng ước) đối với lời giải x của bài toán xác suất. 9 - Nội dung thứ ba: Giải bằng số các bài toán xác suất với các hiện tượng ngẫu nhiên không quan sát được đã đề cập đến ở trên, ta cũng thiết lập một bài toán xác suất tương đương (mô hình mô phỏng tương ứng) sao cho tuy nó có cùng lời giải x với bài toán xác suất ban đầu nhưng lại có thể mô hình hóa trên máy tính. Nghĩa là ta có thể xác định phỏng ước X đối với lời giải x thông qua quá trình thể hiện một mô hình xác suất cơ bản nào đó. - Nội dung thứ tư : đó là vấn đề giảm sai số trong phương pháp Monte Carlo. Với số lần lặp lại mô phỏng các quá trình ngẫu nhiên càng lớn thì ước lượng càng chính xác hơn và ngược lại. Trên đây là 4 nội dung khác nhau của phương pháp Monte Carlo, chúng có đặc điểm chung là để giải mỗi bài toán ta cần phải thể hiện mô hình xác suất cơ bản trên máy tính. Chẳng hạn mô hình xác suất nguyên thủy là tạo ra trên máy tính những thể hiện độc lập của đại lượng ngẫu nhiên có phân bố đều trên đoạn [0,1] (gọi là các số ngẫu nhiên). Từ đó ta có thể định nghĩa phương pháp Monte Carlo là phương pháp giải bằng số các bài toán thông qua việc tạo ra và sử dụng các số ngẫu nhiên. 1.3 Thể hiện các vectơ ngẫu nhiên và thể hiện các phân bố đều 1.3.1 Thể hiện các vectơ ngẫu nhiên Trước hết ta xét “phương pháp nghịch đảo phân bố”(Smiernov) để tạo vectơ ngẫu nhiên   1 ,..., n   R n có hàm phân bố đã cho: F ( x1 ,..., xn )  P 1  x1 ,..., n  xn . Liên quan đến điều này, ta gọi: F1 ( x1 )  P 1  x1   x1   x2   ... dF (t1 , t2 ,..., tn )  F2 ( x2 | x1 )  P 2  x2 | 1  x1   x1  x2        ... dF ( x1 , t2 , t3 ,..., tn      (1.1)  ... dF ( x1 , t2 ,..., tn )  1 (1.2) Fn ( xn | x1 ,..., xn1 )  P n  xn | 1  x1 ,..., n1  xn1 (1.3)    dF ( x1 ,..., xn1 , tn ).   dF  x1 ,..., xn1 , tn      xn 10 1 Trong đó: Fi (. | x1 ,..., xn1 ) là hàm phân bố có điều kiện của đại lượng ngẫu nhiên  i với điều kiện 1  x1 , 2  x2 ,..., i 1  xi 1 (2  i  n) , còn hàm F (.) là hàm phân bố biên duyên (không điều kiện) của đại lượng ngẫu nhiên 1 . Có thể chỉ ra rằng mỗi hàm phân bố có điều kiện nói trên có dạng một hàm phân bố xác suất, nghĩa là Fi (. | x1 ,..., xi 1 ) là hàm không giảm, liên tục trái và 0  Fi ( x | x1 ,..., xi 1 )  1 (xR1 ) (1.4) Khi đó tương tự như trường hợp n  1 ta có thể xác định hàm ngược đơn trị của hàm phân bố: y  Fi ( x | x1 ,..., xi 1 ) (1.5) Dưới dạng: x  Fi 1 ( y | x1 ,..., xi 1 )  inf x : y  Fi  x | x1 ,..., xi 1  (1.5*) Nếu a   0,1 thì phương trình Fi  x | x1 ,..., xi 1   a (1.6) Có nghiệm x  xo với xo  Fi 1  a | x1 ,..., xi 1  (1.7) Sự mở rộng định lý của “phương pháp nghịch đảo phân bố” để tạo vectơ ngẫu nhiên   1 ,..., n  cho trong kết quả sau: Định lý 1.1: Giả sử F  x1 ,..., xn  là một hàm phân bố và F1  x1  , F2  x2 | x1  ,..., Fn  xn | x1 ,..., xn1  là các hàm phân bố có điều kiện dạng (1.1)- (1.3). Gọi: 1  F11 ( R1 ), 2  F21 ( R2 | 1 ),..., n  Fn1 ( Rn | 1,..., n )  Rn (1.8) Trong đó R1 ,..., Rn là các số ngẫu nhiên liên tiếp. Khi đó vectơ ngẫu nhiên   1 ,..., n  sẽ có hàm phân bố (đồng thời) là F  x1 ,..., xn  . Chứng minh: Vì 1  F11  R1  nên từ định nghĩa (1.1) của hàm ngược đơn trị ta suy ra rằng x1  1 là nghiệm của phương trình 11 F1  x1   R1 (1) Ngoài ra từ (1.1) ta suy ra 1  F11  R1  có hàm phân bố F1  x1  . Nghĩa là: P 1  x1  F1  x1  (2) Với i  2  n , từ (1.7) ta có: Vì hàm (1.5*) là hàm ngược đơn trị của (1.5) nên từ (1.3*), (1.4) và (1.5) ta suy ra: P i  xi |   x1 ,..., i 1  xi 1  P Ri  Fi  xi | x1 ,..., xi 1   Fi  xi | x1 ,..., xi 1  , 2  i  n Trên cở sở (2) và (3) ta nhận thấy các nghiệm (1.7) của hệ (1.8) là những đại lượng ngẫu nhiên với các hàm phân bố có điều kiện (1.1)-(1.3). Khi đó, có thể chỉ ra rằng hàm phân bố đồng thời của vectơ ngẫu nhiên   1 ,..., n  là F ( x1 ,..., xn ) . Thật vậy, từ (2) và công thức tính xác suất có điều kiện ta có: P 1  x1 | 2  x2   P 1  x1 P 2  x2 | 1  x1 ,  2  i  n  .   P 2  x2 |   t1 dF1  t1  x1  Khi đó, từ (3), (1.1), (1.2) ta suy ra: P 1  x1 | 2  x2    F2  x2 | t1  d x1   t1     ...  x2  ...  dF  t , y , y   1 2 n     ... dF  y1 ,..., yn           ... dF y ,..., y     1 n      d x1  t1       ... dF  y1 ,..., yn   (4) Để định ý ta giả thiết rằng tồn tại hàm mật độ f  x1 , x2 ,..., xn  ứng với hàm phân bố F  x1 ,..., xn    ... x1 xn   f  t1 ,..., tn  dt1...dtn Khi đó từ công thức Newton-Leibnitz ta có: 12 (5) d      ...  dF  t , y ,..., y  dt ... dF y ,..., y    1 n 1 2 n  1        x2  (6) Từ (5) ta còn suy ra: x2       ... dF  t1 , y2 ,..., yn    x2     ...  f  t1 , y2 ,..., yn  dy2 ...dyn  (7) Khi thay (6),(7) vào (4) ta thu được: P 1  x1 , 2  x2   x1  x1   x2     x2          x1 x2     ...   ...    f  t1 , y2 ,..., yn dy2 ...dyn dt1 f  t1 ,..., tn dt1...dtn  ... dF  t1 ,..., tn   Tương tự bằng phép quy nạp ta có thể suy ra: P P 1  x1 ,..., i  xi    ... x1  x2      ... dF  t1 ,..., tn   i  1  n  (8) Với i  1  n công thức (8) có dạng: P 1  x1 ,..., i  xi    ... dF  t1 ,..., tn  x1 xn    F  x1 ,..., xn  Nghĩa là vectơ ngẫu nhiên   1 ,..., n  (với các thành phần cho bởi nghiệm (1.7) của hệ phương trình (1.8) )có hàm phân bố là F  x1 ,..., xn  . Trong trường hợp cần tạo vectơ ngẫu nhiên liên tục   1 ,..., n  có hàm mật độ p  x1 ,..., xn  , ta xét hàm phân bố F  x1 ,..., xn  dưới dạng: F  x1 ,..., xn    ... p  t1 ,..., tn  dt1...dtn . x1 xn   (1.9) Khi đó các hàm phân bố biên duyên F1 ( x1 ) và phân bố có điều kiện Fi  xi | x1 ,..., xi 1   i  2  n  trong (1.1), (1.2)-(1.3) có thể biểu diễn dưới dạng: 13 F1  x1   P 1  x1   p1  t1  dt1 x1 (1.10)  Fi  xi | x1 ,..., xi 1   P i  xi | 1  x1 ,..., i 1  xn    pi  ti | x1 ,..., xi 1 dti xi  i  2  n  (1.11) Trong đó:     p1  x1    ... p2  x2 | x1   p  x1 , t2 ,..., tn dt2 ...dtn (1.12)   1 ... p  x1 , x2 , t3 ,..., tn dt3 ...dtn  p1  x1    p3  x3 | x1 , x2      ...   p  x1 , x2 , x3 , t4 ,..., tn dt4 ...dtn p1  x1  p2  x2 | x1  … pn1  xn1 | x1 , x2 ,..., xn2   pn  xn1 | x1 , x2 ,..., xn1      p  x1 , x2 , xn1 , tn dtn p1  x1  p2  x2 | x1  ... pn2  xn2 | x1 ,..., xn3  p  x1 , x2 ,..., xn  p1  x1  p2  x2 | x1  ... pn1  xn1 | x1 ,..., xn2  là hàm mật độ biên duyên và mật độ có điều kiện của 1 và i (1.13) i  2  n xác định từ hàm mật độ đồng thời p  x1 ,..., x n  . Tương tự như các hàm phân bố có điều kiện, ta có thể chỉ ra rằng các hàm p1 (.) và pi . | x1 ,..., xi 1  cũng là những hàm mật độ, có nghĩa là: p1  x1   0  x1  R1  ; pi  xi | x1 ,..., xi 1   0;       p1  x1  dx1  1 pi  ti | x1 ,..., xi 1  dti  1 Khi đó, từ (1.10) và (1.11) ta có thể phát biểu định lý (1.1) dưới dạng sau: Hệ quả 1.1: Giả sử p( x1 ,..., xn ) là một hàm mật độ (trong R n ) và 14 p1  x1  , pi  xi | x1 ,..., xn   i  2  n  là những hàm mật độ biên duyên và mật độ có điều kiện dạng (1.12)-(1.13). Khi đó nghiệm   1 ,...,  n  của hệ phương trình:  1  p1  t1  dt1  R1;  i  pi  ti | 1 ,..., i 1  dti  Ri i  2  n  Với ( R1 ,..., Rn là các số ngẫu nhiên) sẽ là vectơ ngẫu nhiên có mật độ đồng thời p  x1 ,..., xn  . Trong định lý (1.3) và hệ quả trên đây ta đã thiết lập các phương trình đệ quy xác định lần lượt các thành phần 1 , 2 ,..., n của vectơ ngẫu nhiên   1 ,..., n  có hàm phân bố F  x1 ,..., xn  (hoặc mật độ p  x1 ,..., xn  ). Nếu thay cho các hàm phân bố (1.1)-(1.3), ta sử dụng các hàm phân bố: F1  x2   P  2  x2  ; F2  x1 | x2   P 1  x1 |  2  x2  ; F3  x3 | x2 , x1   P 3  x3 | 2  x2 , 1  x1 ;... Thì các phương trình đệ quy (1.8) thay bởi các phương trình: F1  x2   R1; F2  x1 | 1   R2 ; F3   x3 | 2 , 1   R3 ;... Và ta thu được lần lượt các nghiệm x2  2 ; x1  1; x3  3 ;... trong vectơ ngẫu nhiên   1 ,..., n  cần tạo ra. Lẽ đương nhiên các nghiệm 2  F11  R1  ,1  F21 R2 | 2 ,3  F3 1 R3 | 2 ,1 ,... tương ứng sẽ có những biểu diễn giải tích (theo R1 , R2 ,... ) khác với (1.7). Điều này sẽ kéo theo sự khác nhau về độ phức tạp tính toán giữa 2 cách làm trên đây. Ví dụ 1.1: Xét việc tạo vectơ ngẫu nhiên  ,    có giá:    x, y R 2 : x  y 1, x  0, y  0 Là tam giác vuông cân giới hạn bởi trục hoành Ox , trục tung Oy và đường thẳng y  1 x . Giả sử hàm mật độ (đồng thời) của  ,  có dạng: p  x, y   6 x   x, y   . (1) Nếu gọi p1  x   p  x  là mật độ biên duyên của thành phần  , ta có: 15 p1  x   p  x    1 x 0 p  x, y  dy  6 x 1  x  ,  0  x  1 (2) Khi đó mật độ có điều kiện của  (với   x ) sẽ là : p2  y | x   p  y | x   p x | y 6x 1   ,    x, y   (3) p  x  6 x 1  x  1  x Từ (1.10) và (2) ta thu được hàm phân bố biên duyên của  có dạng: x x 0 0 F1 ( x)  F ( x)   p (t )dt   6t (1  t )dt  3x 2  2 x3 (0  x  1) (4) Từ (1.11) và (3) ta suy ra hàm phân bố có điều kiện của  (với   x ) là: y F2 ( y | x)  F ( y | x)   p ( z, x)dz  0 y , (( x, y )  ) 1 x (5) Từ (4) và (5) ta thu được hệ phương trình:   p1  x  dx  3 2  2 3  R1 0   0  p2  y |   dy  1  (6)  R2 (6*) trong đó R1 , R2 là các số ngẫu nhiên. Sau khi giải phương trình (6) (để thu được nghiệm  ), ta giải phương trình (6*) (để thu được nghiệm  ) và tạo được các thành phần  , của vectơ ngẫu nhiên nói trên theo trình tự ngược lại. Với mục đích này, trước hết ta xét mật độ biên duyên của thành phần  dưới dạng: p1  y   p  y    1 y 0 p  x, y  dx  3 1  y  2 (7) Tiếp theo xét mật độ có điều kiện của  (với điều kiện   y ) dưới dạng: p2  x | y   p  x | y   p  x, y  2x  p y  y  1  y 2 (8) Khi đó từ (1.10) và (7) ta suy ra hàm phân bố biên duyên của  có dạng: F1  y   F  y    p  t  dt   3 1  t  dt  1  1  y  y 0 y 2 0 3 (9) Từ (1.11) và (8) ta suy ra hàm phân bố có điều kiện của  (với điều kiện   y ) sẽ có dạng: 16 F2  x | y   F  x | y    p  t | y  dt  x 0 x2 1  y  2 (10) Từ (9), (10) ta thu được hệ phương trình : F2    1  1     1  R1 3 F2  |    (11) 2  R2 2 1    (11*) Giải (11) ta thu được:   1  3 R1 (12) Khi đó, từ (11) ta thu được:   R2 . 3 R1 (12*) Nghĩa là lời giải tường minh của hệ (11), (11*) có dạng (12), (12*). Khi so sánh kết quả này với việc giải phương trình cấp 1 dạng (6) rồi tiếp theo giải phương trình tuyến tính (6*) ta nhận thấy rằng cách tạo các thành phần của vectơ ngẫu nhiên  ,  theo phương pháp thứ nhất có độ phức tạp tính toán lớn hơn so với phương án sau. Qua trường hợp hệ phương trình (6), (6*) của ví dụ trên đây ta nhận thấy nhiều trường hợp của phương pháp nghịch đảo phân bố đưa về việc giải gần đúng hệ phương trình (1.8). Nghĩa là chỉ đạo được một cách gần đúng vectơ ngẫu nhiên   1 ,..., n  ứng với hàm phân bố hoặc mật độ (đồng thời) đã cho. Nhằm khắc phục những khó khăn trên, ta có thể dử dụng phương pháp loại trừ Vonn-Neuman dưới đây: Giả sử   1 ,..., n  ứng với hàm phân bố hoặc mật độ (đồng thời) đã cho. Nhằm khắc phục những khó khăn trên ta có thể sử dụng phương pháp loại trừ Vonn-Neuman dưới đây: Giả sử   1 ,..., n  là vectơ ngẫu nhiên với hàm mật độ p  x   p  x1 ,..., xn  biểu diễn dưới dạng: p  x  f  x g  x,  xR  ; n Trong đó g là hàm không âm giới nội: 17 x  R  0  g  x   a  const    n Còn f ( x) có dạng của hàm mật độ phân bố xác suất trên miền G  R n f  x   0  xG  ;  f  x  dx  1 G Định lý 1.2: Giả sử   1 ,...,n  là vectơ ngẫu nhiên tạo được từ hàm mật độ f ( x) và đại lượng ngẫu nhiên   U 0, a  độc lập với  . Khi đó ta có thể thu được  từ phương pháp loại trừ (Vonn-Neuman) sau:   (nếu   g   ) Trong đó xác suất để thu được vectơ ngẫu nhiên  trong một phép thứ là: P   g    1 a Hệ quả 1.2: với các điều kiện p  x   0  xR n  , p  x   0  x  G  ,  p  x  po  x    P  Go   0  Và  p  x  dx  1 G  xGo   xGo  Thì vectơ ngẫu nhiên o Go  G (với mật độ po  x  ) có thể tạo được nhờ vectơ ngẫu nhiên   G (với mật độ p  x  ) bằng phương pháp loại trừ: o   (Nếu  Go ) Hệ quả 1.3: Giả sử vectơ ngẫu nhiên   1 , 2 ,...,  n  có hàm mật độ p  x   p  x1 ,..., xn  giới nội trên miền hữu hạn G : 0  p  x   A    x R n  ; p  x   0 x G  ; G p  x  dx  1 0  G  mesG   Và giả sử   1 ,...,n   U  G  . Khi đó có thể thu được  bằng phương pháp loại trừ sau:   (khi   p   ) 18 Trong đó đại lượng ngẫu nhiên   U 0, A độc lập với  . Đồng thời ta còn có P   p     A | G  . 1 Định lý 1.3: Cho a   a1 ,..., an R n là một vectơ có các thành phần hữu hạn và B   ij  nn  R n là một ma trận xác định dương cấp n , nghĩa là n n  Bx, x    ij xi x j  0 i 1 j 1 Khi đó hệ x   x ,..., x   0 1 n 1 n  n  1 hệ phương trình đệ quy (truy hồi) luôn có nghiệm 2   cij 1  i  j  n  với mọi  2 0   2   . Đồng thời: E    a   a1 ,..., an  D    B   ij  nn Trong đó   1 ,..., n  là vectơ ngẫu nhiên với các thành phần:    1  c11  1    a1    2  c12  1    c22   2    a2   .......   1  2  n   n  c1n    c2 n     ...cnn     an           Với    ,...,   là các thể hiện độc lập của đại lượng ngẫu nhiên  có kì vọng  , 1 n phương sai  2 . Cuối cùng, ta xét phương pháp trộn phân bố (superposition) bắt nguồn từ kết quả của J-Butler để tạo các vectơ ngẫu nhiên   1 , 2 ,...,  n  có hàm phân bố Fn  F  x1 , x2 ,...xn  biểu diễn dưới dạng tổ hợp tuyến tính của một số hữu hạn các hàm phân bố (gọi là phân bố trộn): F  x    pk Fk  x  kI Trong đó I là tập hợp hữu hạn hay đếm được các chỉ số: I  1,..., m , I  1,2,..., m,... 19
- Xem thêm -

Tài liệu liên quan