--- Bài mới hơn ---
Chuong 2 Dai So Tuyen Tinh 2 Cách Chia Đa Thức Bằng Lược Đồ Hoocner Hay Phương Pháp Quản Lý Tiền Jars Cho Cá Nhân Phương Pháp Lặp Trong Giải Toán Bằng Máy Tính Casio Just In Time (Jit): Không Tồn Kho, Không Chờ Đợi, Không Chi Phí
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
VŨ THỊ VUI
PHƯƠNG PHÁP LẶP GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH
SỐ CHIỀU LỚN
LUẬN VĂN THẠC SĨ TOÁN HỌC
Hà Nội – 2022
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
VŨ THỊ VUI
PHƯƠNG PHÁP LẶP GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH
SỐ CHIỀU LỚN
Chuyên ngành: Toán giải tích
Mã số: 60 46 01 02
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học:
TS. Hà Bình Minh
Hà Nội – 2022
Lời cảm ơn
Luận văn được hoàn thành tại trường Đại học Sư phạm Hà Nội 2 dưới
sự hướng dẫn của thầy giáo TS. Hà Bình Minh. Sự giúp đỡ và hướng
dẫn tận tình, nghiêm túc của thầy trong suốt quá trình thực hiện luận văn
này đã giúp tôi trưởng thành hơn rất nhiều trong cách tiếp cận một vấn
đề mới. Tôi xin bày tỏ lòng biết ơn, lòng kính trọng sâu sắc nhất đối với
thầy.
Tôi xin trân trọng cảm ơn Ban giám hiệu trường Đại học Sư phạm Hà
Nội 2, phòng Sau đại học, các thầy cô giáo trong nhà trường đã giúp đỡ,
tạo điều kiện thuận lợi cho tôi trong suốt quá trình học tập.
Tôi xin chân thành cảm ơn gia đình, người thân, bạn bè đã giúp đỡ,
động viên và tạo điều kiện thuận lợi để tôi hoàn thành khóa học Thạc sĩ
cũng như hoàn thành luận văn này.
Hà Nội, ngày 09 tháng 06 năm 2022
Tác giả
Vũ Thị Vui
Lời cam đoan
Luận văn được hoàn thành tại trường Đại học Sư phạm Hà Nội 2 dưới
sự hướng dẫn của TS. Hà Bình Minh.
Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng tôi.
Trong quá trình nghiên cứu và hoàn thành luận văn tôi đã kế thừa
những thành quả khoa học của các nhà khoa học và đồng nghiệp với sự
trân trọng và biết ơn.
Tôi xin cam đoan rằng các thông tin trích dẫn trong luận văn đã được
chỉ rõ nguồn gốc.
Hà Nội, ngày 09 tháng 06 năm 2022
Tác giả
Vũ Thị Vui
i
i
Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
Chương 1. Một số phương pháp lặp cổ điển . . . . . . . . . . . . . . .
3
1.1. Phương pháp Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.1. Giới thiệu phương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.2. Điều kiện hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.1.3. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.2. Phương pháp Gauss – Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.2.1. Giới thiệu phương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.2.2. Điều kiện hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.2.3. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
Chương 2. Các phương pháp Krylov . . . . . . . . . . . . . . . . . . . . .
14
2.1. Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.2. Phương pháp Gradient liên hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.2.1. Giới thiệu phương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.2.2. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.3. Phương pháp GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
2.3.1. Giới thiệu phương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
2.3.2. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.4. Phương pháp QMR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
2.4.1. Giới thiệu phương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
2.4.2. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
2.5. Phương pháp Bi-CGSTAB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
2.5.1. Giới thiệu phương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
2.5.2. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
ii
Chương 3. Ứng dụng của phương pháp lặp . . . . . . . . . . . . . . .
39
3.1. Ứng dụng trong giải phương trình Poisson . . . . . . . . . . . . . . . . . .
39
3.2. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
Phụ lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
1
Mở đầu
1. Lí do chọn đề tài
Nhiều bài toán trong thực tế đòi hỏi phải giải hệ phương trình tuyến
tính cỡ lớn có dạng Ax b, trong đó A là ma trận có số chiều lớn và
thưa (tức là chỉ có một số ít các phần tử khác 0). Chẳng hạn, những hệ
phương trình này xuất hiện ta giải bài toán biên của phương trình đạo
hàm riêng bằng các phương pháp rời rạc hóa, như phương pháp sai phân
hoặc phương pháp phần tử hữu hạn. Những phương pháp cổ điển để giải
hệ phương trình tuyến tính, chẳng hạn như phương pháp khử Gauss, sẽ
rất khó có thể áp dụng để giải những hệ này. Lý do là vì phương pháp khử
Gauss được áp dụng cho ma trận đặc và khi áp dụng cho ma trận thưa sẽ
làm cho số phép toán trở nên rất lớn, không thể thực hiện nổi đối với máy
tính thông thường. Hơn nữa, số lượng bộ nhớ sử dụng cho phương pháp
Gauss cũng trở nên rất lớn.
Với những lý do nêu trên, phương pháp lặp giải hệ phương trình tuyến
tính cỡ lớn được nghiên cứu từ lâu. Theo phương pháp này, bắt đầu từ
một vector khởi tạo xp0q , ta sẽ sinh ra một dãy các vector
xp0q
Ñ xp1q Ñ xp2q Ñ . . .
hội tụ đến nghiệm x. Quá trình sinh vector xpk 1q từ vector xpkq sử dụng
phép nhân ma trận A với một vector nào đó. Phép nhân này rất tiết kiệm
do A là ma trận thưa và chỉ cần số ít bộ nhớ để lưu trữ. Hai phương pháp
lặp được biết đến nhiều nhất theo hướng này là phương pháp Jacobi và
phương pháp Gauss-Seidel.
Bên cạnh đó, một lớp các phương pháp lặp được phát triển trong thời
gian gần đây là lớp các phương pháp Krylov. Đặc trưng của lớp các phương
pháp này quá trình lặp sẽ hội tụ đến nghiệm chính xác sau một số hữu hạn
bước lặp. Cụ thể, quá trình lặp sẽ cho nghiệm xpkq sẽ là xấp xỉ tốt nhất
2
nghiệm của hệ Ax b trong không gian Krylov k chiều. Một số phương
pháp lặp thuộc lớp này phải kể đến là: phương pháp gradient liên hợp của
Hestenes và Stiefel (1952) cho hệ tuyến tính có ma trận A đối xứng xác
định dương; phương pháp GMRES của Saad và Schultz (1986); phương
pháp QMR của Freund và Nachtigal (1991); và phương pháp Bi-CGSTAB
của van der Vorst (1992).
2. Mục đích và nhiệm vụ nghiên cứu
Khảo cứu một số phương pháp lặp dùng để giải hệ phương trình tuyến
tính cỡ lớn, và áp dụng để nghiệm số cho phương trình đạo hàm riêng.
3. Đối tượng và phạm vi nghiên cứu
Hệ phương trình tuyến tính cỡ lớn, phương trình vi phân đạo hàm riêng.
4. Phương pháp nghiên cứu
Sử dụng các phương pháp giải số, ngôn ngữ lập trình MATLAB,…
5. Đóng góp mới của đề tài
Áp dụng phương pháp lặp để giải hệ phương trình tuyến tính cỡ lớn, sau
đó lập trình, thực hiện các phương pháp này bằng phần mềm MATLAB.
3
CHƯƠNG 1
Một số phương pháp lặp cổ điển
Nội dung của chương này được tham khảo chủ yếu từ các tài liệu , mục
8.7.
2.1. Giới thiệu
Xét hệ phương trình tuyến tính
Ax b,
với A là ma trận thực không suy biến. Bắt đầu từ một vector xp0q , phương
pháp Krylov sẽ sinh ra một dãy các vector
xp0q
Ñ xp1q Ñ Ñ xpmq,
tiến tới nghiệm chính xác xpmq
m ¤ n.
x : A1b sau nhiều nhất m bước, với
Các Phương pháp Krylov: sử dụng phép lặp để sinh ra dãy txpkq u
thỏa mãn
xpkq
P xp0q
Kk prp0q , Aq, với mọi k
1, 2, . . . ,
trong đó Kk prp0q , Aq là không gian Krylov được định nghĩa như sau:
Kk prp0q , Aq : spanrrp0q , Arp0q , . . . , Ak1 rp0q s, k
1, 2, . . .
--- Bài cũ hơn ---
Dây Chuyền Máy Làm Giò Chả Những Phương Pháp Giúp Chả Lụa Tự Làm Trở Nên Dai Ngon Hơn Học Cách Làm Chả Lụa Ngon, Giòn Dai, Không Hàn The Bạn Đã Biết Gì Về Phương Pháp In Chuyển Nhiệt Và In Lưới? Các Phương Pháp In Ấn Kỹ Thuật Trên Vải Lụa