Thuật giải jacobi cho hệ phương trình tuyến tính

Thuật giải Jacobi là một phương pháp số học được sử dụng để giải hệ phương trình tuyến tính. Phương pháp này tập trung vào việc tìm nghiệm dự đoán cho từng biến trong hệ phương trình và sau đó cập nhật nghiệm dự đoán này cho đến khi đạt được sự hội tụ.

PHƯƠNG TRÌNH TUYẾN TÍNH

.

3 VÍ DỤ

4 THUẬT TOÁN

5 CODE MATLAB

6 ƯU ĐIỂM VÀ NHƯỢC ĐIỂM

7 ĐIỀU KIỆN HỘI TỤ

8 CÔNG THỨC SAI SỐ

Cho hệ phương trình tuyến tính:

Phương pháp đúng - phương pháp trực tiếp (Cramer, Gauss, ): Đặc điểm của các phương pháp này là sau một số hữu hạn các bước tính.

Ta nhận được nghiệm đúng nếu trong quá trình tính không làm tròn số.

Phương pháp gần đúng - phương pháp xấp xỉ (Jacoibi ,

Gauss-Seidel, ): Thông thường ta cho ẩn số một giá trị ban đầu, từ giá trị này tính giá trị nghiệm gần đúng tốt hơn theo một quy tắc nào

đó Quá trình này được lặp lại nhiều lần với một số điều kiện nhất định, ta nhận được nghiệm gần đúng.

.

Lịch sử các phương pháp lặp giải hệ pt tuyến tính

- Tài liệu tham khảo sớm nhất về cách tiếp cận bằng phương pháp lặp để giải

quyết hệ phương trình Ax = b dường như được chứa trong một bức thư của Gaussgửi cho sinh viên Gerling ngày 26 tháng 12 năm 1823, trong bối cảnh giải các bàitoán bình phương tối thiểu thông qua các phương trình thông thường

- Cuộc trao đổi trong bức thư này là về việc áp dụng phương pháp bình phươngtối thiểu mà Gauss đã phát minh ra vào đầu những năm 1800, vào ngành trắc địa

Lịch sử các phương pháp lặp giải hệ pt tuyến tính

- Sau đó, năm 1845 Jacobi đã phát triển một phương pháp lặp đơn giản của riêngmình, để giải các phương trình thông thường cho các bài toán bình phương tốithiểu phát sinh trong các phép tính thiên văn Trong đó sửa đổi mới nhất khôngđược đưa ngay vào hệ

- Trong bài báo đó, ông giới thiệu một cách sửa đổi hệ thống tuyến tính bằng cách

sử dụng cái mà ngày nay chúng ta gọi là "phép quay Jacobi" để tăng tốc độ hội tụcủa sự lặp lại, Jacobi đã giới thiệu kỹ thuật sử dụng các phép quay được lựa chọnmột cách khéo léo, đã được giới thiệu trong một bài báo xuất hiện một năm sau đó

để giải các vấn đề về giá trị riêng đối xứng

.

Lịch sử các phương pháp lặp giải hệ pt tuyến tính

- Năm 1874 một Người Đức, Seidel, đã giới thiệu phương pháp lặp của riêng

mình Ông mô tả như một phương pháp cải tiến hơn so với phương pháp của

Jacobi Seidel lưu ý rằng các ẩn số không cần phải được xử lý theo chu kỳ (trênthực tế, ông khuyên không nên làm như vậy!); thay vì, người ta có thể chọn cậpnhật ở mỗi bước mà không biết với lượng dư lớn nhất

- Trong các tài liệu sau đó, phương pháp này thường được gọi là phương pháp củaSeidel Bây giờ nó được gọi là phương pháp Gauss-Seidel

- Một trong những điểm thu hút chính của phiên bản tuần hoàn của phép lặp

Gauss-Seidel là nó có thể dễ dàng được lập trình hoặc “cơ giới hóa”

Lịch sử các phương pháp lặp giải hệ pt tuyến tính

- Vào đầu thế kỷ 20, chúng ta ghi nhận những đóng góp quan trọng sau: Phươngpháp của Richardson (1910); phương pháp của Liebmann (1918) Những bài báonày đánh dấu việc sử dụng phương pháp lặp đầu tiên trong giải pháp xấp xỉ hiệu

số hữu hạn cho elliptic PDEs

- Phương pháp của Richardson ngày nay vẫn còn được biết đến nhiều và có thểđược coi là bước tăng tốc của phương pháp Jacobi nhờ các yếu tố đơn giản quámức Phương pháp do Liebmann đề xuất lại hướng đến việc giải các phương trìnhPoisson rời rạc Phương pháp không khác gì phương pháp Gauss-Seidel, và vì lý

do này, phép lặp Gauss-Seidel khi áp dụng cho các phương trình vi phân từng

phần thường được gọi là phương pháp Liebmann

Giả sử rằng trong hệ phương trình Ax =b, ma trận A có tất cả các phần tử

trên đường chéo chính khác0(trong trường hợp có a ii = 0, ta có thể đổi chỗ

các dòng của A).

Ta tách ma trận A thành hai ma trận D và S như sau:

D khả nghịch khi và chỉ khi detD ̸= 0

D là ma trận đường chéo chính với cái phần tử trên đường chéo chính khác0

= a11a22

= max

Định lý

Nếu A là ma trận đường chéo trội ngặt , khi đó thuật toán Jacobi sẽ hội tụ với bất

kì giá trị dự đoán x(0) nào

Sai số hậu nghiệm(sai số nhận được sau khi thực hiện quá

trình tính toán)

(m) − x ≤ ∥ T ∥

1− ∥ T ∥

(m) − x(m −1)

.

1 Slide Giải tích số 1 - TS Nguyễn Thị Hoài Thương

2 Sử dụng phương pháp lặp đơn và lặp Jacobi để giải hệ phương trình đại sốtuyến tính - Đại học Bách Khoa Hà Nội

3 Numerical Analysis Ninth Edition Richard L Burden and J Douglas

Faires

4 INTRODUCTION TO NUMERICAL ANALYSIS - MIT