Về kỹ thuật tiền tác động giải hệ phương trình tuyến tính cỡ lớn

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

PHẠM TRỊNH CƯƠNG CHÍNH

VỀ KỸ THUẬT TIỀN TÁC ĐỘNG GIẢI HỆ

PHƯƠNG TRÌNH TUYẾN TÍNH CỠ LỚN

LUẬN VĂN THẠC SĨ TOÁN HỌC

Thái Nguyên - 2015

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

PHẠM TRỊNH CƯƠNG CHÍNH

VỀ KỸ THUẬT TIỀN TÁC ĐỘNG GIẢI HỆ

PHƯƠNG TRÌNH TUYẾN TÍNH CỠ LỚN

Chuyên ngành: Toán ứng dụng

Mã số: 60 46 01 12

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC

TS. NGUYỄN THANH SƠN

Thái Nguyên - 2015

i

Mục lục

Lời cảm ơn iii

Mở đầu 1

1 Kiến thức chuẩn bị 4

1.1 Hệ phương trình tuyến tính . . . . . . . . . . . . . . . . . . . . . . 4

1.1.1 Định lí Kronecker-Capelli . . . . . . . . . . . . . . . . . . 4

1.1.2 Định lí Cramer . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Phương pháp giải trực tiếp . . . . . . . . . . . . . . . . . . . . . . 5

1.2.1 Phương pháp khử Gauss . . . . . . . . . . . . . . . . . . . 5

1.2.2 Phương pháp phân tích LU . . . . . . . . . . . . . . . . . . 6

1.3 Phương pháp lặp cổ điển . . . . . . . . . . . . . . . . . . . . . . . 8

1.3.1 Phương pháp lặp đơn . . . . . . . . . . . . . . . . . . . . . 8

1.3.2 Phương pháp Jacobi . . . . . . . . . . . . . . . . . . . . . 8

1.3.3 Phương pháp Gauss - Seidel . . . . . . . . . . . . . . . . . 9

1.4 Phương pháp không gian con Krylov . . . . . . . . . . . . . . . . . 10

1.4.1 Không gian con Krylov và Thuật toán Arnoldi . . . . . . . 10

1.4.2 Phương pháp CG . . . . . . . . . . . . . . . . . . . . . . . 12

1.4.3 Phương pháp GMRES . . . . . . . . . . . . . . . . . . . . 14

1.4.4 Phương pháp Arnoldi . . . . . . . . . . . . . . . . . . . . . 15

2 Kĩ thuật tiền tác động 18

2.1 Tiền tác động trong các phép lặp cổ điển . . . . . . . . . . . . . . . 18

ii

2.1.1 Jacobi, SOR(Successive Overrelaxtion) và SSOR(Symetric

SOR) nhân tử tiền tác động. . . . . . . . . . . . . . . . . . 18

2.2 Kĩ thuật tiền tác động tổng quát . . . . . . . . . . . . . . . . . . . . 21

2.2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2.2 Phân tích ILU . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2.3 Phân tích Cholesky thiếu (IC) . . . . . . . . . . . . . . . . 23

2.3 Tiền tác động khối thiếu . . . . . . . . . . . . . . . . . . . . . . . 23

2.3.1 Phân tích Cholesky khối thiếu . . . . . . . . . . . . . . . . 23

2.3.2 Ý tưởng phân chia miền . . . . . . . . . . . . . . . . . . . 25

2.3.3 Ma trận ba đường chéo khối . . . . . . . . . . . . . . . . . 25

2.3.4 Ma trận với cấu trúc đều . . . . . . . . . . . . . . . . . . . 26

2.3.5 Xấp xỉ nghịch đảo . . . . . . . . . . . . . . . . . . . . . . 26

2.3.6 Phép lặp toàn cục . . . . . . . . . . . . . . . . . . . . . . . 27

2.4 Kỹ thuật tiền tác động với các phương pháp lặp . . . . . . . . . . . 28

2.4.1 PCG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.4.2 PGMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3 Ví dụ số 35

3.1 Phương pháp CG và PCG . . . . . . . . . . . . . . . . . . . . . . . 35

3.2 Phương pháp GMRES và PGMRES . . . . . . . . . . . . . . . . . 36

3.3 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Kết luận 38

Tài liệu tham khảo 39