Luận Văn Thạc Sĩ Về Thuật Toán Sinh Lưới Đa Giác Và Ứng Dụng Trong Giải Phương Trình Đạo Hàm Riêng

Luận văn thạc sĩ nghiên cứu toán ứng dụng 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, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp

• Tác giả: Nguyễn Thị Kim Duyên
• Người hướng dẫn: TS. Đặng Lê Quang
• Trường học: Đại học Bách Khoa - Đại học Quốc gia TP. Hồ Chí Minh
• Chuyên ngành: Toán ứng dụng
• Đề 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
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2021
• Địa điểm: Thành phố Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• LỜI MỞ ĐẦU
• 1. CHƯƠNG 1: KIẾN THỨC CƠ SỞ
• 1.1. Phương pháp thể tích hữu hạn trên một lưới bất kì
• 1.2. Một số khái niệm mở rộng
• 1.3. 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
• 2. CHƯƠNG 2: TÍNH CHẤT CỦA LƯỚI VÀ CẤU TRÚC DỮ LIỆU CHO THUẬT TOÁN
• 2.1. Các đối tượng hình học trong lưới
• 2.2. Thành lập cơ sở dữ liệu
• 2.3. Mô tả chi tiết với các đối tượng
• 3. CHƯƠNG 3: THUẬT TOÁN SINH LƯỚI ĐA GIÁC
• 3.1. Phương pháp luận
• 4. 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
• 4.2. Ứng dụng của phương trình laplace trong mô phỏng tính toán chất lưu
• KẾT LUẬN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu về thuật toán sinh lưới đa giác

Thuật toán sinh lưới đa giác là một phương pháp quan trọng trong lĩnh vực toán học ứng dụng, đặc biệt trong việc giải quyết các bài toán liên quan đến giải phương trình đạo hàm riêng. Lưới đa giác có khả năng mô phỏng các miền tính toán phức tạp mà lưới tam giác không thể thực hiện hiệu quả. Lưới đa giác không chỉ linh hoạt hơn mà còn giúp giảm thiểu các vấn đề liên quan đến sự hội tụ của bài toán. Theo đó, việc sử dụng lưới đa giác trong mô phỏng chất lưu và các lĩnh vực khác như kỹ thuật xây dựng và công nghiệp ô tô đã được chứng minh là hiệu quả. Cụ thể, lưới đa giác cho phép tạo ra các phần tử có số đỉnh và cạnh tùy ý, điều này rất có lợi cho việc tính toán trong các miền hình học phức tạp.

1.1. Tầm quan trọng của lưới đa giác

Lưới đa giác không chỉ giúp cải thiện độ chính xác trong việc giải phương trình mà còn giảm thiểu chi phí tính toán. Việc áp dụng thuật toán này trong các phần mềm mô phỏng như ANSYS hay SIEMENS đã cho thấy sự cần thiết của nó trong việc giải quyết các bài toán phức tạp. Hơn nữa, lưới đa giác có khả năng tương tác tốt với các phương pháp số khác nhau, từ đó tạo ra những kết quả đáng tin cậy hơn trong các mô phỏng vật lý.

II. Cơ sở lý thuyết của thuật toán

Chương này tập trung vào việc xây dựng cơ sở lý thuyết cho thuật toán sinh lưới đa giác. Phương pháp thể tích hữu hạn (FVM) là nền tảng để phát triển thuật toán này. FVM cho phép rời rạc hóa miền tính toán thành các phần tử nhỏ, từ đó dễ dàng áp dụng các phương trình đạo hàm riêng. Các khái niệm như điểm điều khiển, cạnh và phần tử được định nghĩa rõ ràng trong bối cảnh lưới tam giác và lưới đa giác. Đặc biệt, việc lựa chọn điểm điều khiển là yếu tố quan trọng quyết định đến độ chính xác của kết quả tính toán. Các nghiên cứu trước đây đã chỉ ra rằng việc chọn điểm điều khiển hợp lý có thể cải thiện đáng kể hiệu suất của thuật toán.

2.1. Phương pháp thể tích hữu hạn

Phương pháp thể tích hữu hạn là một trong những phương pháp số phổ biến nhất hiện nay, được sử dụng rộng rãi trong giải quyết các bài toán đạo hàm riêng. Bằng cách chia miền tính toán thành các phần tử nhỏ và áp dụng các định luật vật lý, phương pháp này cho phép tìm kiếm nghiệm xấp xỉ cho các phương trình phức tạp. Việc áp dụng phương pháp này trong lưới đa giác giúp tối ưu hóa quá trình tính toán, đồng thời giảm thiểu các sai số có thể xảy ra trong quá trình mô phỏng.

III. Ứng dụng của lưới đa giác trong giải phương trình đạo hàm riêng

Lưới đa giác đã được áp dụng thành công trong việc giải nhiều loại phương trình đạo hàm riêng, đặc biệt là phương trình Laplace. Việc sử dụng lưới đa giác giúp cải thiện độ chính xác của nghiệm cũng như khả năng hội tụ của các phương pháp số. Các ứng dụng trong mô phỏng chất lưu, nhiệt động học và các lĩnh vực khác cho thấy tính khả thi và hiệu quả của phương pháp này. Nghiên cứu cho thấy rằng lưới đa giác có thể được tối ưu hóa cho các miền hình học phức tạp mà lưới tam giác không thể xử lý một cách hiệu quả.

3.1. Giải phương trình Laplace

Phương trình Laplace là một trong những phương trình phổ biến trong toán học và kỹ thuật. Việc áp dụng lưới đa giác để giải phương trình này đã cho thấy những kết quả khả quan. Lưới đa giác không chỉ giúp cải thiện độ chính xác của các nghiệm mà còn giảm thiểu thời gian tính toán. Nghiên cứu đã chỉ ra rằng việc sử dụng lưới đa giác trong giải phương trình Laplace có thể mang lại những lợi ích đáng kể trong các ứng dụng thực tiễn.

Nội dung chính

Tổng quan nghiên cứu

Phương pháp thể tích hữu hạn (Finite Volume Method - FVM) là một trong những kỹ thuật số phổ biến để tìm nghiệm xấp xỉ cho các phương trình đạo hàm riêng, đặc biệt trong lĩnh vực cơ học chất lưu. Theo ước tính, hơn 80% các phần mềm mô phỏng chất lưu hàng đầu thế giới như ANSYS FLUENT và SIEMENS STAR-CCM+ sử dụng phương pháp này. Tuy nhiên, việc sinh lưới tự động trên các miền tính toán phức tạp vẫn còn nhiều thách thức, đặc biệt với lưới tam giác truyền thống. Lưới tam giác mặc dù dễ tạo và hiệu chỉnh, nhưng lại gây tốn kém chi phí tính toán và khó khăn trong việc tính toán gradient do mỗi phần tử chỉ có tối đa 3 phần tử kề bên. Trong khi đó, lưới hình chữ nhật cho kết quả hội tụ tốt hơn nhưng khó áp dụng trên miền phức tạp.

Luận văn này tập trung nghiên cứu thuật toán sinh lưới đa giác từ lưới tam giác nhằm khắc phục những hạn chế trên. Lưới đa giác có thể có số đỉnh và cạnh bất kỳ, phù hợp với miền hình học phức tạp, đồng thời cho phép liên kết nhiều phần tử hơn, thuận lợi cho tính toán gradient. Mục tiêu cụ thể là xây dựng thuật toán sinh lưới đa giác từ lưới tam giác có sẵn, kèm theo lớp biên, và ứng dụng lưới đa giác này để giải phương trình Laplace trên miền hình chữ nhật. Nghiên cứu được thực hiện trong phạm vi miền tính toán hai chiều, với dữ liệu lưới ban đầu được sinh tự động từ phần mềm ANSYS Workbench. Ý nghĩa của nghiên cứu thể hiện qua việc nâng cao hiệu quả và độ chính xác trong mô phỏng tính toán chất lưu, góp phần phát triển các công cụ tính toán số trong kỹ thuật.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên nền tảng phương pháp thể tích hữu hạn (FVM) để giải các phương trình đạo hàm riêng, trong đó phương trình Laplace được chọn làm bài toán mẫu. Các khái niệm chính bao gồm:

• Lưới tam giác và lưới đa giác: Lưới tam giác là dạng lưới truyền thống với mỗi phần tử có 3 cạnh, trong khi lưới đa giác có thể có số cạnh và đỉnh tùy ý, giúp mô tả miền phức tạp hơn.
• Điểm điều khiển (control points): Vị trí điểm điều khiển trong mỗi phần tử ảnh hưởng lớn đến độ chính xác của phương pháp thể tích hữu hạn. Luận văn sử dụng cách chọn điểm điều khiển kết hợp giữa trọng tâm và tâm đường tròn ngoại tiếp tam giác để tránh phần tử lõm và cải thiện hội tụ.
• Cấu trúc dữ liệu lưới: Bao gồm các đối tượng nút, cạnh, phần tử và mối quan hệ giữa chúng, được quản lý bằng các mảng hai chiều để tối ưu truy vấn và xử lý dữ liệu.
• Thuật toán sinh lưới đa giác đối ngẫu: Dựa trên việc tạo nút đối ngẫu từ điểm điều khiển của lưới tam giác, xây dựng cạnh đối ngẫu và phần tử đối ngẫu, đặc biệt xử lý riêng các phần tử trên biên và phần tử tứ giác để đảm bảo tính chính xác và ổn định.

Phương pháp nghiên cứu

Nguồn dữ liệu chính là các lưới tam giác được sinh tự động từ phần mềm ANSYS Workbench, với cỡ mẫu lưới đa dạng từ vài trăm đến vài nghìn phần tử. Phương pháp nghiên cứu bao gồm:

• Tiền xử lý dữ liệu lưới tam giác: Xây dựng cấu trúc dữ liệu đầy đủ cho nút, cạnh, phần tử, phân biệt phần tử tam giác và tứ giác, cũng như xác định lớp biên.
• Phát triển thuật toán sinh lưới đa giác: Thuật toán được lập trình bằng ngôn ngữ C++ với cấu trúc dữ liệu tối ưu, cho phép sinh lưới đa giác nhanh chóng (ví dụ, với 7466 nút và 10350 cạnh, thời gian xử lý chưa đến 1 giây).
• Giải phương trình Laplace trên lưới đa giác: Áp dụng phương pháp thể tích hữu hạn để giải phương trình đạo hàm riêng trên miền hình chữ nhật, với các điều kiện biên Dirichlet và Neumann.
• Phân tích kết quả: So sánh nghiệm xấp xỉ với nghiệm chính xác, đánh giá sai số trung bình và tốc độ hội tụ trên các lưới đa giác có kích thước khác nhau.

Thời gian nghiên cứu kéo dài trong năm 2021 tại Trường Đại học Bách Khoa - Đại học Quốc gia TP. Hồ Chí Minh, dưới sự hướng dẫn của các chuyên gia trong lĩnh vực Toán ứng dụng.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Thuật toán sinh lưới đa giác hiệu quả và nhanh chóng: Với lưới đầu vào có 430 nút, thời gian sinh lưới đa giác chỉ khoảng 0.016 giây. Với lưới lớn hơn gồm 7466 nút và 10350 cạnh, thời gian xử lý chưa đến 1 giây, chứng tỏ thuật toán có tính ứng dụng cao trong thực tế.

2. Chất lượng lưới đa giác đảm bảo tính toán chính xác: Lưới đa giác sinh ra có thể kết hợp với lưới lớp biên gồm phần tử tứ giác, giúp mô phỏng chính xác các giá trị vận tốc và áp suất trong cơ học chất lưu. Số phần tử đối ngẫu bằng số nút ban đầu, đảm bảo cấu trúc lưới phù hợp.

3. Giải phương trình Laplace trên lưới đa giác cho kết quả hội tụ tốt: Trên miền hình chữ nhật [0,4] × [0,2], nghiệm xấp xỉ thu được từ lưới đa giác với số phần tử tăng dần (từ 223 đến 3851 phần tử) cho sai số trung bình giảm rõ rệt, thể hiện qua biểu đồ sai số trung bình. Ví dụ, sai số trung bình giảm từ khoảng 0.05 xuống dưới 0.01 khi tăng số phần tử.

4. Ứng dụng trong mô phỏng dòng chảy không xoáy, không nén được: Khi giải bài toán mô phỏng dòng chảy đều với điều kiện biên Dirichlet và Neumann, lưới đa giác cho kết quả hội tụ nhanh hơn so với lưới tam giác truyền thống. Nghiệm xấp xỉ gần sát nghiệm chính xác u(x) = 5x + 6, với sai số trung bình giảm dần khi tăng số phần tử lưới từ 126 đến 544.

Thảo luận kết quả

Nguyên nhân chính của hiệu quả này là do lưới đa giác cho phép mỗi phần tử liên kết với nhiều phần tử kề hơn, thuận lợi cho việc tính toán gradient và cải thiện độ hội tụ của phương pháp thể tích hữu hạn. Việc lựa chọn điểm điều khiển kết hợp giữa trọng tâm và tâm đường tròn ngoại tiếp giúp tránh tạo ra phần tử lõm, vốn gây sai số lớn và khó xử lý trong tính toán số.

So với các nghiên cứu trước đây chỉ tập trung vào lưới tam giác hoặc lưới tứ giác, nghiên cứu này mở rộng khả năng sinh lưới đa giác trên miền phức tạp, đồng thời giữ được tính linh hoạt và độ chính xác cao. Kết quả hội tụ nhanh hơn trên lưới đa giác cũng phù hợp với các báo cáo ngành về ưu điểm của lưới đa giác trong mô phỏng chất lưu.

Dữ liệu có thể được trình bày qua các biểu đồ sai số trung bình theo số phần tử lưới, bảng so sánh thời gian sinh lưới và số lượng nút, cạnh, phần tử đối ngẫu, giúp minh họa rõ ràng hiệu quả thuật toán và chất lượng nghiệm.

Đề xuất và khuyến nghị

1. Phát triển phần mềm sinh lưới đa giác tích hợp: Đề xuất xây dựng module sinh lưới đa giác tích hợp vào các phần mềm mô phỏng hiện có như ANSYS hoặc STAR-CCM+, nhằm tận dụng ưu điểm của lưới đa giác trong mô phỏng chất lưu. Thời gian thực hiện dự kiến 1-2 năm, do các nhóm phát triển phần mềm kỹ thuật thực hiện.

2. Mở rộng nghiên cứu sang mô hình 3D: Nghiên cứu áp dụng thuật toán sinh lưới đa giác trong không gian ba chiều, đặc biệt cho các bài toán phức tạp trong kỹ thuật hàng không và xây dựng. Mục tiêu nâng cao độ chính xác và giảm chi phí tính toán. Thời gian nghiên cứu 2-3 năm, do các nhóm nghiên cứu toán ứng dụng và kỹ thuật tính toán phối hợp thực hiện.

3. Tối ưu hóa thuật toán chọn điểm điều khiển: Đề xuất nghiên cứu thêm các phương pháp chọn điểm điều khiển tự động dựa trên chất lượng phần tử và đặc điểm miền tính toán, nhằm cải thiện hơn nữa độ hội tụ và độ chính xác của nghiệm. Thời gian thực hiện khoảng 1 năm, do nhóm nghiên cứu toán ứng dụng đảm nhận.

4. Ứng dụng thuật toán trong mô phỏng thực tế: Khuyến nghị các doanh nghiệp và viện nghiên cứu trong lĩnh vực cơ học chất lưu, sản xuất ô tô, hàng không áp dụng thuật toán sinh lưới đa giác để nâng cao hiệu quả mô phỏng, giảm thời gian tính toán và chi phí. Thời gian áp dụng tùy thuộc quy mô dự án, có thể bắt đầu ngay trong các dự án hiện tại.

Đối tượng nên tham khảo luận văn

1. Nghiên cứu sinh và sinh viên cao học ngành Toán ứng dụng, Khoa học máy tính: Luận văn cung cấp kiến thức sâu về phương pháp thể tích hữu hạ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, hỗ trợ phát triển đề tài nghiên cứu liên quan.

2. Kỹ sư và chuyên gia mô phỏng trong lĩnh vực cơ học chất lưu, kỹ thuật hàng không, ô tô: Thuật toán sinh lưới đa giác giúp cải thiện chất lượng mô phỏng, giảm chi phí tính toán, phù hợp cho các bài toán phức tạp với miền hình học đa dạng.

3. Nhà phát triển phần mềm mô phỏng kỹ thuật: Cấu trúc dữ liệu và thuật toán sinh lưới được trình bày chi tiết, có thể tích hợp vào các phần mềm hiện có để nâng cao hiệu quả xử lý và độ chính xác.

4. Giảng viên và nhà quản lý đào tạo trong lĩnh vực Toán ứng dụng và Kỹ thuật tính toán: Tài liệu luận văn là nguồn tham khảo quý giá để xây dựng giáo trình, bài giảng về phương pháp thể tích hữu hạn, sinh lưới và ứng dụng trong mô phỏng số.

Câu hỏi thường gặp

1. Thuật toán sinh lưới đa giác có ưu điểm gì so với lưới tam giác truyền thống?
   Thuật toán cho phép tạo lưới với số cạnh và đỉnh tùy ý, phù hợp với miền phức tạp, giúp tăng số phần tử kề bên mỗi phần tử, thuận lợi cho tính toán gradient và cải thiện độ hội tụ. Ví dụ, lưới đa giác có thể liên kết nhiều phần tử hơn so với tối đa 3 phần tử kề bên của lưới tam giác.

2. Làm thế nào để chọn điểm điều khiển trong phần tử tam giác để sinh lưới đa giác?
   Điểm điều khiển được chọn kết hợp giữa trọng tâm và tâm đường tròn ngoại tiếp tam giác, nhằm tránh tạo phần tử lõm và đảm bảo điều kiện vuông góc với cạnh chung, giúp cải thiện độ chính xác và hội tụ của phương pháp thể tích hữu hạn.

3. Thuật toán có thể áp dụng cho miền tính toán 3D không?
   Hiện tại nghiên cứu tập trung trên miền 2D, tuy nhiên phương pháp và cấu trúc dữ liệu có thể mở rộng sang 3D với các phần tử đa diện, cần nghiên cứu thêm để xử lý phức tạp hơn về mặt hình học và tính toán.

4. Thời gian sinh lưới đa giác có phù hợp cho các ứng dụng thực tế không?
   Kết quả cho thấy với lưới lớn hơn 7000 nút, thời gian sinh lưới chưa đến 1 giây trên máy tính tiêu chuẩn, rất phù hợp cho các ứng dụng mô phỏng cần sinh lưới nhanh và hiệu quả.

5. Lưới đa giác có thể áp dụng cho các bài toán mô phỏng chất lưu nào?
   Lưới đa giác phù hợp cho các bài toán mô phỏng dòng chảy không xoáy, không nén được, cũng như các bài toán phức tạp trong cơ học chất lưu, giúp cải thiện độ chính xác và tốc độ hội tụ so với lưới tam giác truyền thống.

Kết luận

• Thuật toán sinh lưới đa giác từ lưới tam giác được phát triển thành công, cho phép sinh lưới nhanh chóng với chất lượng cao.
• Lưới đa giác cải thiện khả năng tính toán gradient và độ hội tụ của phương pháp thể tích hữu hạn so với lưới tam giác truyền thống.
• Ứng dụng giải phương trình Laplace trên lưới đa giác cho kết quả nghiệm xấp xỉ chính xác, hội tụ tốt trên miền hình chữ nhật.
• Thuật toán có tiềm năng ứng dụng rộng rãi trong mô phỏng cơ học chất lưu, kỹ thuật hàng không, ô tô và các lĩnh vực kỹ thuật khác.
• Các bước tiếp theo bao gồm mở rộng sang mô hình 3D, tối ưu hóa thuật toán chọn điểm điều khiển và tích hợp vào phần mềm mô phỏng thực tế.

Để khai thác tối đa lợi ích từ nghiên cứu này, các nhà nghiên cứu và kỹ sư được khuyến khích áp dụng thuật toán sinh lưới đa giác trong các dự án mô phỏng số, đồng thời tiếp tục phát triển và hoàn thiện các phương pháp liên quan.

Trích đoạn nội dung tài liệu

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 Đị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.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 .2) Lấy tích phân 2 vế ta được: 1 1 Z Z − ∇ · ∇udx = f dx (1.3) |Di | Di |Di | Di Xét vế trái biểu thức (1.2): 1 1 Z Z − ∇ · ∇udx = ∇u · ndS |Di | Di |Di | ∂Di 1 X (ui − uk ) = −|Ak | .4) |Di | k∈∂Di d(xk , xi ) 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à: xm + xn xk = (1.5) 2 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.6) |Di | Di Với công thức rời rạc (1.6) ta được: AU = B (1.7) Với A ∈ M N ×N , B ∈ RN,1 , U ∈ B ∈ RN,1  PNi ui j=1 |Aj |.8) |Di |   −|Aj | uj , i ̸= j   d(xj ,xi ) Bi = B(xi ), 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 (1.3 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 (∇ · u)i = |Ak |uk · nki (1.15) |Ti | k∈∂D i • Định nghĩa toán tử curl: 1 X (∇ × u)i = |Ak |uk · τki (1.16) |Ti | k∈∂D i Trong đó τki chính là vector tiếp tuyến của cạnh Ak .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. 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 Luận văn Thạc sĩ Chuyên ngành Toán ứng dụng Chương 2 TÍNH CHẤT CỦA LƯỚI VÀ CẤU TRÚC DỮ LIỆU CHO THUẬT TOÁN Sự rời rạc hóa một miền tính toán liên tục thành các phần tử thể tích là một bước quan trọng trong việc tính toán mô phỏng chất lưu. Trong những năm gần đây, các nhà nghiên cứu thường tập trung vào việc tối ưu hóa bộ nhớ và tốc độ xử lý trong quá trình sinh lưới. Việc thiết kế một cấu trúc dữ liệu tốt cho thuật toán đóng vai trò quan trọng trong việc đẩy nhanh quá trình xử lý.

Chúng tôi cần phải thiết kế cơ sở dữ liệu cho các đối tượng như nút, cạnh, phần tử sao cho quá trình truy vấn diễn ra nhanh chóng. Trong chương này, chúng tôi xin trình bày cấu trúc dữ liệu cho thuật toán.1 Các đối tượng hình học trong lưới Thông tin về cấu trúc lưới cho chúng ta về cái nhìn tổng quát về lưới cũng như về miền hình học tính toán đang xét. Thông tin này nói về mối quan hệ giữa các đối tượng trong lưới. Trong tính toán một chiều các đối tượng sẽ chỉ là nút và cạnh.

Trong tính toán hai chiều, chúng ta sẽ quan tâm đến ba đối tượng đó là: nút, cạnh và phần tử (face hoặc facets). Đặc biệt, trong tính toán ba chiều, chúng ta cần phải quản lý dữ liệu cho 4 Nguyễn Thị Kim Duyên 9 Luận văn Thạc sĩ Chuyên ngành Toán ứng dụng đối tượng: nút, cạnh, mặt (face hoặc facets), và phần tử (cell, volumes, regions hoặc solids), thuật ngữ "phần tử" cho lưới 2D khác với lưới 3D, "phần tử" trong 2 chiều là đối tượng được tạo ra bởi các cạnh, ngược lại "phần tử" trong 3 chiều là đối tượng được tạo ra bởi các mặt, các mặt này được tạo ra bởi các cạnh. Trong luận văn này, chúng tôi hướng đến việc sinh lưới đa giác trong miền tính toán hai chiều, do đó cơ sở dữ liệu được thiết kế cho ba giá trị là nút, cạnh và phần tử.2 Thành lập cơ sở dữ liệu Mỗi đối tượng hình học được cấu thành từ đối tượng có cấp thấp hơn một bậc. Phần tử được tạo thành bởi các cạnh, cạnh được tạo thành bởi 2 nút, và thông tin về 1 nút là tọa độ của nút này.

Mối quan hệ này chính là nền tảng để chúng tôi thiết kế cấu trúc dữ liệu cho lưới.1: Mối liên hệ giữa các đối tượng vậy, nhìn vào hình 2.1, chúng tôi thấy được rằng, trong lưới tính toán 2 chiều, chúng ta có bốn mối quan hệ, ứng với mỗi mối quan hệ chúng tôi sẽ tạo ra một mảng hai chiều (cấu trúc mảng hai chiều trong ngôn ngữ lập trình C++,) để xử lý. Mối quan hệ (1), (2) là mối quan hệ từ phần tử cấp cao đến phần tử cấp thấp, và mối quan hệ (3),(4) là mối quan hệ từ phần tử cấp thấp đến phần tử cấp cao. Nguyễn Thị Kim Duyên 10 Luận văn Thạc sĩ Chuyên ngành Toán ứng dụng Lưu ý rằng, chúng tôi không sử dụng mối quan hệ giữa các đối tượng cùng cấp với nhau nhằm làm giảm khối lượng lưu trữ tính toán. Dựa vào hình 2.1, chúng tôi sẽ mô tả cách truy vấn dữ liệu như sau: • Từ chỉ số của một cạnh, chúng tôi có thể biết được thông tin của hai nút tạo ra cạnh này (quan hệ (1)).

• Từ thông tin về một nút, chúng tôi có thể truy vấn thông tin của một cạnh được tạo thành bởi nút này (quan hệ (4)). • Bên cạnh đó, thông qua chỉ số của phần tử chúng tôi biết được chỉ số của các cạnh tạo ra phần tử này. • Tương tự như vậy, từ chỉ số của một cạnh, chúng tôi cũng sẽ truy vấn được thông tin về chỉ số của hai phần tử có chung cạnh này. Trong mục tiếp theo, chúng tôi sẽ mô tả chi tiết về các đối tượng dữ liệu (mảng 2 chiều) sẽ được sử dụng trong thuật toán.3 Mô tả chi tiết với các đối tượng Như đã đề cập trong mục trước, những mối quan hệ trong hình 2.1 sẽ trở thành một mảng hai chiều trong cấu trúc code.

Như vậy, chúng ta sẽ khởi tạo bốn mảng 2 chiều theo cấu trúc sau: • Ứng với mối quan hệ (1), chúng tôi đặt tên là mảng 1, mảng này chứa thông tin về chỉ số của các cạnh có chung một nút ( hình 2. Ví dụ, dòng thứ nhất của mảng sẽ chứa thông tin về các chỉ số của các cạnh được tạo thành bởi nút 1. Một cách tổng quát, ta có dữ liệu ở dòng thứ i sẽ chứa thông tin về chỉ số của các cạnh mà cạnh đó được tạo thành bởi nút thứ thứ i. • Ứng với mối quan hệ (4), chúng tôi đặt tên là mảng 2, mảng này chứa thông tin về chỉ số của các nút có chung một cạnh (hình 2.

Nguyễn Thị Kim Duyên 11 Luận văn Thạc sĩ Chuyên ngành Toán ứng dụng Hình 2.2: Mảng 1 Tổng quát, với dòng thứ i trong mảng 2 này, chúng ta sẽ biết thông tin về các nút tạo bởi cạnh thứ i.