Tài liệu Thuật toán sinh lưới đa giác và ứng dụng để giải phương trình đạo hàm riêng

ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA —————– NGUYỄN THỊ KIM DUYÊN THUẬT TOÁN SINH LƯỚI ĐA GIÁC VÀ ỨNG DỤNG ĐỂ GIẢI PHƯƠNG TRÌNH ĐẠO HÀM RIÊNG POLYGONAL MESH GENERATION ALGORITHM AND ITS APPLICATION TO SOLVE PARTIAL DIFFERENTIAL EQUATION Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 8460112 LUẬN VĂN THẠC SĨ Thành Phố Hồ Chí Minh, tháng 12 năm 2021 ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA NGUYỄN THỊ KIM DUYÊN THUẬT TOÁN SINH LƯỚI ĐA GIÁC VÀ ỨNG DỤNG ĐỂ GIẢI PHƯƠNG TRÌNH ĐẠO HÀM RIÊNG POLYGONAL MESH GENERATION ALGORITHM AND ITS APPLICATION TO SOLVE PARTIAL DIFFERENTIAL EQUATION Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 8460112 LUẬN VĂN THẠC SĨ Thành Phố Hồ Chí Minh, tháng 12 năm 2021 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG - HCM Cán bộ hướng dẫn khoa học 1: TS.ĐẶNG LÊ QUANG Cán bộ hướng dẫn khoa học 2: TS.LÊ XUÂN ĐẠI Cán bộ chấm phản biện 1: TS.NGUYỄN BÁ THI Cán bộ chấm phản biện 2: PGS.TS.NGUYỄN HUY TUẤN Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG TP. HCM ngày 27 tháng 12 năm 2021 . Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: 1. Chủ tịch: PGS.TS.NGUYỄN ĐÌNH HUY 2. Thư ký: TS.ĐẶNG VĂN VINH 3. Phản biện 1: TS.NGUYỄN BÁ THI 4. Phản biện 2: PGS.TS.NGUYỄN HUY TUẤN 5. Ủy viên: TS.CAO THANH TÌNH Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyên ngành sau khi luận văn đã được sửa chữa (nếu có). CHỦ TỊCH HỘI ĐỒNG PGS.TS NGUYỄN ĐÌNH HUY TRƯỞNG KHOA KHOA HỌC ỨNG DỤNG PGS.TS. TRƯƠNG TÍCH THIỆN ĐẠI HỌC QUỐC GIA TP. HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự do - Hạnh Phúc TRƯỜNG ĐẠI HỌC BÁCH KHOA NHIỆM VỤ LUẬN VĂN THẠC SĨ Mã số học viên: 2070238 Nơi sinh: TP. Hồ Chí Minh Mã số: 60460112 Họ tên học viên: NGUYỄN THỊ KIM DUYÊN Ngày, tháng, năm sinh: 21/12/1995 Chuyên ngành: Toán ứng dụng I. TÊN ĐỀ TÀI: THUẬT TOÁN SINH LƯỚI ĐA GIÁC VÀ ỨNG DỤNG ĐỂ GIẢI PHƯƠNG TRÌNH ĐẠO HÀM RIÊNG II. NHIỆM VỤ VÀ NỘI DUNG: - Kiến thức cơ sở. - Xậy dựng thuật toán sinh lưới đa giác từ lưới tam giác. - Giải phương trình Laplace với lưới đa giác. III. NGÀY GIAO NHIỆM VỤ: IV. NGÀY HOÀN THÀNH NHIỆM VỤ: V. CÁN BỘ HƯỚNG DẪN 1: TS. Đặng Lê Quang. CÁN BỘ HƯỚNG DẪN 2: TS. Lê Xuân Đại. Tp. HCM, Ngày........... tháng........ năm.......... CÁN BỘ HƯỚNG DẪN 1 (Họ tên và chữ ký) CÁN BỘ HƯỚNG DẪN 2 (Họ tên và chữ ký) TS. ĐẶNG LÊ QUANG TS. LÊ XUÂN ĐẠI TRƯỞNG BM TOÁN ỨNG DỤNG (Họ tên và chữ ký) TS. NGUYỄN TIẾN DŨNG TRƯỞNG KHOA (Họ tên và chữ ký) PGS. TS. TRƯƠNG TÍCH THIỆN LỜI CẢM ƠN Lời đầu tiên tôi xin gửi lời cảm ơn đến thầy Đặng Lê Quang và thầy Lê Xuân Đại, người đã nhiệt tình hướng dẫn, giúp đỡ tôi hoàn thành luận văn. Bên cạnh đó, tôi cũng xin chân thành cám ơn gia đình tôi, ba mẹ và anh hai đã luôn ủng hộ tôi trên con đường học tập. Tôi xin gửi lời cảm ơn các thầy, cô trong Bộ môn Toán Ứng Dụng, Khoa Khoa học ứng dụng, Trường Đại học Bách Khoa - Đại học Quốc gia Thành phố Hồ Chí Minh đã tạo mọi điều kiện tốt nhất để tôi hoàn thành luận văn của mình. Cuối cùng, trong quá trình thực hiện luận văn khó tránh khỏi những thiếu sót, rất mong nhận được sự góp ý của tất cả thầy cô trong Hội đồng. Tp. Hồ Chí Minh, 16 tháng 11 năm 2021 Tác giả Nguyễn Thị Kim Duyên i TÓM TẮT LUẬN VĂN THẠC SĨ Nội dung của luận văn gồm hai vấn đề chính như sau: 1. Thuật toán sinh lưới đa giác từ lưới tam giác. 2 Áp dụng lưới đa giác để giải phương trình Laplace. ii ABSTRACT In this thesis, there are two main problems as follow: 1. Algorithm which generates a polygonal mesh. 2. Solving the Laplace equation with a polygonal mesh. iii LỜI CAM ĐOAN Tôi tên là Nguyễn Thị Kim Duyên, mã học viên: 2070238, học viên cao học chuyên ngành Toán Ứng Dụng thuộc Bộ môn Toán ứng dụng, Khoa Khoa học ứng dụng, trường Đại học Bách Khoa - Đại học quốc gia Thành phố Hồ Chí Minh. Tôi xin cam đoan rằng ngoại trừ các kết quả tham khảo từ các công trình khác như đã ghi rõ trong luận văn, các vấn đề trình bày trong luận văn này là do chính tôi thực hiện dưới sự hướng dẫn của TS.Đặng Lê Quang và TS. Lê Xuân Đại và tôi hoàn toàn chịu trách nhiệm tính trung thực về đề tài nghiên cứu này. Tp. Hồ Chí Minh, ngày 16 tháng 11 năm 2021 Học viên thực hiện Nguyễn Thị Kim Duyên iv Mục lục LỜI CẢM ƠN i LỜI CAM ĐOAN iv LỜI MỞ ĐẦU 1 Chương 1. KIẾN THỨC CƠ SỞ 4 1.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Phương pháp thể tích hữu hạn trên một lưới bất kì . . . . . 4 1.3 Một số khái niệm mở rộng . . . . . . . . . . . . . . . . . . . 7 1.4 Sự lựa chọn điểm điều khiển trong phương pháp thể tích hữu hạn với lưới tam giác . . . . . . . . . . . . . . . . . . . . . 7 Chương 2. TÍNH CHẤT CỦA LƯỚI VÀ CẤU TRÚC DỮ LIỆU CHO THUẬT TOÁN 9 2.1 Các đối tượng hình học trong lưới . . . . . . . . . . . . . 9 Thành lập cơ sở dữ liệu . . . . . . . . . . . . . . . . . . 10 2.3 Mô tả chi tiết với các đối tượng . . . . . . . . . . . . . . . . 11 2.2 Chương 3. THUẬT TOÁN SINH LƯỚI ĐA GIÁC 15 3.1 Phương pháp luận . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Sinh lưới tam giác . . . . . . . . . . . . . . . . . . . . . . . 18 3.3 Sinh lưới đối ngẫu . . . . . . . . . . . . . . . . . . . . . . . 19 3.3.1 Nút đối ngẫu . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.2 Cạnh đối ngẫu . . . . . . . . . . . . . . . . . . . . . . 21 v 3.3.3 Phần tử đối ngẫu . . . . . . . . . . . . . . . . . . . . . 22 3.4 Sự lựa chọn điểm điều khiển . . . . . . . . . . . . . . . . . . 23 3.5 Lưới đa giác trên những miền hình học khác nhau . . . . . . 25 3.6 Thời gian sinh lưới . . . . . . . . . . . . . . . . . . . . . . . 28 Chương 4. ỨNG DỤNG LƯỚI ĐA GIÁC GIẢI MỘT SỐ PHƯƠNG TRÌNH ĐẠO HÀM RIÊNG 4.1 Phương trình Laplace cơ bản . . . . . . . . . . . . . . . . . 29 29 4.2 Ứng dụng của phương trình laplace trong mô phỏng tính toán chất lưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 KẾT LUẬN 46 TÀI LIỆU THAM KHẢO 47 vi LỜI MỞ ĐẦU Phương pháp thể tích hữu hạn (Finite Volumn Method (FVM)) là một trong những phương pháp số được sử dụng phổ biến để tìm nghiệm xấp xỉ cho hầu hết các phương trình đạo hàm riêng. Đặc biệt,phương pháp này tìm nghiệm xấp xỉ rất tốt cho các phương trình trong lĩnh vực cơ học chất lưu. Hơn nữa, phương pháp này được hầu hết các công ty phần mềm mô phỏng lớn trên thế giới ưa chuộng như ANSYS (FLUENT), SIEMENS( STAR-CCM+)... Hầu hết các lý thuyết trước đây đều xây dựng cơ sở lý thuyết tốt cho lưới tam giác (tetrahedral) hay lưới tứ giác (quadrilaterals) trong bài toán hai chiều [1], [2], [3]. Lưới tam giác và lưới hình chữ nhật còn có thể được dễ dàng tạo ra một cách tự động. Tuy nhiên, việc sinh lưới tự động trên những miền tính toán phức tạp thì kết quả bài toán thu được không được tốt. Lưới tam giác phù hợp cho những bài toán có miền tính toán phức tạp, dễ dàng hiệu chỉnh lưới. Ngoài những mặt tích cực trên, lưới tam giác vẫn còn tồn tại một số bất cập. Việc áp dụng tính toán trên lưới tam giác thì tốn kém chi phí, loại lưới này không được sử dụng trong tính toán ở những miền gần lớp biên. Hơn nữa, với lưới tam giác, mỗi phần tử chỉ có nhiều nhất là 3 phần tử kế bên, tính chất này gây khó khăn trong việc tính toán phần tử gradient trong phương trình dạo hàm riêng. Vì vậy, khi sử dụng lưới tam giác, các nhà khoa học luôn phải đối mặt với những vấn đề liên quan đến sự hội tụ của bài toán, khả năng thu được nghiệm xấp xỉ tốt nhất. Trong một số nghiên cứu gần đây, lưới hình chữ nhật (quadrilateral mesh) được sử dụng và cho kết quả xấp xỉ tốt, nghiệm dễ dàng hội tụ. 1 Tuy nhiên, lưới hình chữ nhật lại không thể dễ dàng tạo ra trên miền tính toán phức tạp, hơn nữa việc hiệu chỉnh lưới trở nên rất khó khăn. Lưới đa giác được đề xuất như là một phương pháp nhằm hạn chế những điểm không tốt của lưới tam giác và phát huy những điểm mạnh của lưới hình chữ nhật. Lưới đa giác được ứng dụng trong bài toán mô phỏng trong lĩnh vực sản xuất ô tô, hàng không, kĩ thuật xây dựng, [11]... Lưới đa giác có số đỉnh và số cạnh bất kì, tính chất này khiến lưới phù hợp cho các miền hình học phức tạp. Lưới đa giác được sử dụng linh hoạt hơn lưới tam giác, ít vi phạm các tiêu chuẩn thiếu đối xứng (skewness) của lưới. Vì vậy, lưới đa giác được mong đợi sẽ cho kết quả tính toán tốt như lưới hình chữ nhật. Một ưu điểm khác của lưới đa giác chính là tính chất sau: một phần tử có thể liên kết được rất nhiều phần tử khác nhau, việc này rất có lợi cho việc tính toán phần tử gradient [4]. Trong những năm 1992, Ghosh và Mukhopadhyay [9] sử dụng lưới đa giác với phương pháp phần tử hữu hạn trong việc tính toán mô phỏng vật liệu sắt đa tinh thể. Vào năm 2000, W. Oaks và S. Paoletti [8] đề xuất một thuật toán sinh lưới đa giác đều từ lưới hình hộp chữ nhật. Tuy nhiên, trong nghiên cứu này, thuật toán sinh lưới khá phức tạp và không có tính ứng dụng cao trong một vài miền tính toán. Trong luận văn này, chúng tôi nghiên cứu một thuật toán để sinh lưới đa giác từ một một lưới tam giác bất kì, kèm theo lớp biên, và sau cùng chúng tôi sẽ giải một phương trình đạo hàm riêng Laplace đơn giản trên lưới đa giác đã sinh ra. Nội dung của luận văn gồm 4 chương: Chương 1 cung cấp những khái niệm cơ bản về phương pháp thể tích hữu hạn. Chương 2 trình bày chi tiết về cách quản lý dữ liệu trong thuật toán sinh lưới. Chương 3 trình bày về thuật toán sinh lưới đa giác, cách chọn điểm 2 điều khiển cho mỗi phần tử. Bên cạnh đó, chúng tôi đưa ra một số hình ảnh về lưới đa giác trong một số miền hình học khác nhau. Chương 4: Ở chương này, chúng tôi sẽ giải phương trình đạo hàm riêng trên một miền hình chữ nhật đơn giản. Mục đích nghiên cứu: Luận văn này nhằm nghiên cứu thuật toán sinh lưới đa giác từ lưới tam giác trên những miền hình học khác nhau. Đối tượng nghiên cứu: Cách sinh lưới trên miền tính toán bất kì kèm theo lớp biên. Phương pháp nghiên cứu: kế thừa và phát triển các kỹ thuật đã có của các tác giả đi trước. Nội dung và phạm vi của vấn đề sẽ nghiên cứu: Ngoài phần lời mở đầu và kết luận, chúng tôi chia luận văn thành bốn chương. 3 Luận văn Thạc sĩ Chuyên ngành Toán ứng dụng Chương 1 KIẾN THỨC CƠ SỞ Trong chương này, chúng tôi xin nhắc lại một số kiến thức cơ sở của phương pháp thể tích hữu hạn, nội dung của chương này được tham khảo từ [12] và [13]. 1.1 Định nghĩa Xét miền Ω được bao phủ bởi lưới tam giác, chúng tôi ký hiệu lưới này là lưới P , các phần tử lưới là Pj , j ∈ [j, J], trong đó J là số phần tử của lưới ban đầu. Từ lưới này chúng tôi sẽ sinh lưới đa giác D, các phần tử của lưới này là Di , i ∈ [1, I]. Trong lưới đa giác này, chúng ta có các cạnh Ak , k ∈ [1, K], K là số cạnh trong lưới, ứng với mỗi cạnh chúng ta sẽ có vector pháp tuyến nk , và vecto tiếp tuyến là τk . Chúng tôi sẽ gọi tên lưới ban đầu là T. Với lưới T , chúng tôi thiết lập một số định nghĩa như sau: nút ban đầu, cạnh ban đầu, phần tử ban đầu. Bên cạnh đó, chúng tôi gọi lưới với các phần tử được sinh ra ứng với các phần tử trong lưới T là D. Với lưới D, chúng tôi thiết lập một số định nghĩa như sau: nút đối ngẫu, cạnh đối ngẫu, phần tử đối ngẫu. 1.2 Phương pháp thể tích hữu hạn trên một lưới bất kì Chúng tôi xin nhắc lại một số khái niệm cơ bản trong phương pháp thể tích hữu hạn. Nguyễn Thị Kim Duyên 4 Luận văn Thạc sĩ Chuyên ngành Toán ứng dụng Xét bài toán Laplace: −∆u = f trên Ω, (1.1) Vì miền Ω được rời rạc thành những phần tử Di , nên chúng tôi sẽ xét bài toán trên những phần tử Di này. Trên mỗi phần tử Di , chúng ta xét phương trình Laplace như sau: −∆u = f trên Di . Lấy tích phân 2 vế ta được: Z Z 1 1 − ∇ · ∇udx = f dx |Di | Di |Di | Di Xét vế trái biểu thức (1.2): Z Z 1 1 ∇ · ∇udx = ∇u · ndS − |Di | Di |Di | ∂Di 1 X (ui − uk ) = . −|Ak | |Di | d(xk , xi ) (1.2) (1.3) (1.4) k∈∂Di Trong đó: • k ∈ ∂Di :k là chỉ số của những phần tử kế bên của phần tử thứ i. • Ak chính là cạnh chung giữa phần tử thứ i và phần tử thứ k. • |Ak | là chiều dài cạnh Ak . • d(xk , xi ) là khoảng cách giữa 2 điểm điều khiển thứ k và thứ i. • Trong trường hợp i là phần tử nằm trên biên, giá trị của k là không xác định, thì vị trí của điểm điều khiển xk được xác định bằng cách lấy trung điểm của của cạnh Ak , nghĩa là: xk = xm + xn 2 (1.5) Với xm và xn là 2 điểm nằm trên cạnh Ak . Nguyễn Thị Kim Duyên 5 Luận văn Thạc sĩ Chuyên ngành Toán ứng dụng Tiếp theo, chúng ta xét vế phải biểu thức (1.2): Z 1 f dx = f (xi ) |Di | Di (1.6) Với công thức rời rạc (1.4) và (1.6) ta được: AU = B (1.7) Với A ∈ M N ×N , B ∈ RN,1 , U ∈ B ∈ RN,1  PNi ui   i=j  j=1 |Aj |. d(xj ,xi ) ,  1 . Aij = |Di |     −|Aj | uj , i ̸= j d(xj ,xi ) Bi = B(xi ), (1.8) Ui = ui (1.9) Tiếp theo chúng tôi xin nhắc lại về cách xử lý điều kiện biên trong phương pháp thể tích hữu hạn. Với bài toán Laplace như trên, tùy theo điều kiện biên Diriclet hay Neumann, chúng ta sẽ có những cách xấp xỉ trên biên khác nhau. • Với điều kiện Dirichlet, giả sử bài toán có điều kiện biên nhau: u(x) = g(x) trên ∂Ω (1.10) giá trị uk được tính như sau: uk = g(xk ) (1.11) • Với điều kiện Neumann, giả sử bài toán có điều kiện biên nhau: ∇u(x) = h(x) trên ∂Ω (1.12) thì ta có xấp xỉ như sau: − (ui − uk ) = hk d(xk , xi ) (1.13) Với hk là giá trị trung bình của h trên cạnh Ak : Nguyễn Thị Kim Duyên 6 Luận văn Thạc sĩ Chuyên ngành Toán ứng dụng 1 hk = |Ak | 1.3 Z h(s)dS. (1.14) Ak Một số khái niệm mở rộng Trong thể tích hữu hạn, chúng ta thường sử dụng một số định nghĩa như sau: • Định nghĩa toán tử divergence: 1 X |Ak |uk · nki (∇ · u)i = |Ti | k∈∂D (1.15) i • Định nghĩa toán tử curl: 1 X (∇ × u)i = |Ak |uk · τki |Ti | k∈∂D (1.16) i Trong đó τki chính là vector tiếp tuyến của cạnh Ak . 1.4 Sự lựa chọn điểm điều khiển trong phương pháp thể tích hữu hạn với lưới tam giác Nếu như với một lưới cấu trúc, tất cả các phần tử là hình chữ nhật hoặc hình vuông thì chúng ta dễ dàng lấy điểm điều khiển của phần tử bằng cách chọn điểm trọng tâm của hình. Tuy nhiên, với lưới tam giác hay lưới tứ giác thì việc chọn nút điều khiển để cho được kết quả xấp xỉ tốt là điều hết sức khó khăn. Nội dung mục này được tham khảo từ tài liệu [12]. Với mỗi phần tử Di , ta có cạnh Ak là cạnh chung giữa phần tử Di và phần tử Dk (Hình 1.1). Một lưới được chấp nhận trong phương pháp thể tích hữu hạn nếu thõa các điều kiện sau đây: • Đường thẳng nối 2 điểm điều khiển xi và xk phải luôn vuông góc với cạnh Ak . Nguyễn Thị Kim Duyên 7 Luận văn Thạc sĩ Chuyên ngành Toán ứng dụng Hình 1.1: Phần tử Di có cạnh chung Ak với phần tử Dk Hình 1.2: Lưới được chấp nhận Hình 1.3: Lưới không được chấp nhận • Trong trường hợp phần tử Di có một cạnh nằm trên biên của Ω , thì hình chiếu vuông góc của điểm điều khiển xi phải đi qua cạnh Ak . Nguyễn Thị Kim Duyên 8