Phương pháp khử Gauss

Buzz

Nội dung bài viết

Minh họa

Phân tích thuật toán

Ghi chú

Liên kết bên ngoài

Xem thêm

Trong đại số tuyến tính, phương pháp khử Gauss là một thuật toán dùng để giải hệ phương trình tuyến tính, xác định hạng của ma trận và tính ma trận nghịch đảo của ma trận vuông khả nghịch. Thuật toán này được đặt theo tên nhà toán học người Đức Carl Friedrich Gauss.

Thuật toán sử dụng các phép biến đổi hàng cơ bản và được chia thành hai phần. Phần đầu chuyển ma trận về dạng bậc thang hàng, trong khi phần sau đưa nó về dạng bậc thang tối giản. Nhiều ứng dụng chỉ cần phần đầu tiên là đủ.

Phép khử Gauss-Jordan là một thuật toán liên quan, giúp đưa ma trận về dạng bậc thang tối giản chỉ trong một lần duyệt.

Minh họa

Giả sử mục tiêu là xác định và miêu tả nghiệm của hệ phương trình tuyến tính sau (nếu có):

2 x + y - z = 8 (L_{1})

- 3 x - y + 2 z = - 11 (L_{2})

- 2 x + y + 2 z = - 3 (L_{3})

Thuật toán như sau: khử $x$ trong tất cả các phương trình dưới $L_{1}$ , sau đó khử $y$ trong các phương trình dưới $L_{2}$ . Hệ phương trình sẽ trở thành dạng tam giác và sau đó giải bằng phép thay thế ngược.

Trong ví dụ này, ta loại bỏ $x$ khỏi $L_{2}$ bằng cách cộng vào $L_{2}$ , tiếp đó loại bỏ $x$ khỏi $L_{3}$ bằng cách cộng $L_{1}$ vào $L_{3}$ .

L_{2} + \frac{3}{2} L_{1} \to L_{2}

L_{3} + L_{1} \to L_{3}

Kết quả đạt được là:

2x+y−z=8{\displaystyle 2x+y-z=8\,}

\frac{1}{2} y + \frac{1}{2} z = 1

2 y + z = 5

Tiếp theo, chúng ta loại bỏ $y$ khỏi $L_{3}$ bằng cách cộng $- 4 L_{2}$ vào $L_{3}$ :

L_{3} + - 4 L_{2} \to L_{3}

Kết quả cuối cùng là:

2 x + y - z = 8

\frac{1}{2} y + \frac{1}{2} z = 1

- z = 1

Chúng ta đã có hệ phương trình tuyến tính dưới dạng tam giác, phần 1 của thuật toán đã hoàn thành.

Trong bước thứ 2, chúng ta thực hiện phép thay thế ngược để tìm các ẩn số theo thứ tự ngược lại. Do đó, dễ dàng nhận thấy rằng

z = - 1 (L_{3})

Tiếp theo, thay thế $z$ vào $L_{2}$ và giải để có kết quả dễ dàng.

y = 3 (L_{2})

Tiếp theo, chúng ta thay thế $z$ và $y$ vào $L_{1}$ , sau đó giải để tìm được

x = 2 (L_{1})

Vì vậy, chúng ta đã hoàn tất việc giải hệ phương trình.

Thuật toán này áp dụng cho mọi hệ phương trình tuyến tính. Mặc dù có thể hệ không thể chuyển thành dạng tam giác, nhưng ít nhất sẽ có một nghiệm khả dĩ: chẳng hạn, nếu $y$ không xuất hiện trong $L_{2}$ và $L_{3}$ sau bước đầu, thuật toán vẫn có thể đưa hệ về dạng bậc thang. Trong trường hợp này, hệ sẽ không có nghiệm duy nhất mà sẽ có vô số nghiệm do ít nhất có một biến tự do.

Trên thực tế, thay vì sử dụng hệ phương trình trực tiếp, người ta thường dùng ma trận mở rộng (dễ dàng xử lý trên máy tính). Dưới đây là quy trình khử Gauss áp dụng cho ma trận mở rộng của hệ phương trình trên, bắt đầu từ:

[\begin{matrix} 2 & 1 & - 1 & 8 \\ - 3 & - 1 & 2 & - 11 \\ - 2 & 1 & 2 & - 3 \end{matrix}]

Sau khi hoàn thành phần đầu tiên của thuật toán, chúng ta sẽ có kết quả cuối cùng như sau:

[\begin{matrix} 2 & 1 & - 1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 0 & - 1 & 1 \end{matrix}]

Đây là dạng bậc thang của ma trận.

Kết thúc của thuật toán, chúng ta đạt được kết quả là

[\begin{matrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & - 1 \end{matrix}]

Đây là dạng bậc thang rút gọn.

Phân tích thuật toán

Phép khử Gauss đối với một ma trận kích thước n × n yêu cầu khoảng 2n / 3 phép toán, do đó độ phức tạp của nó là .

Thuật toán này có thể xử lý hàng ngàn hệ phương trình và biến số trên máy tính, nhưng không hiệu quả cho hệ thống với hàng triệu phương trình. Đối với các hệ thống lớn như vậy, thường dùng các phương pháp lặp để giải quyết. Có các phương pháp đặc biệt nếu hệ số tuân theo một mẫu nhất định.

Phép khử Gauss có thể được áp dụng cho bất kỳ trường nào.

Phép khử Gauss ổn định về mặt số học cho các ma trận có đường chéo chủ yếu hoặc dương. Đối với các ma trận tổng quát, phép khử Gauss vẫn ổn định nếu sử dụng phương pháp chọn pivot phần.

Ghi chú

Atkinson, Kendall A. An Introduction to Numerical Analysis, ấn bản lần thứ 2, John Wiley & Sons, New York, 1989. ISBN 0-471-50023-2.
Golub, Gene H., và Van Loan, Charles F. Matrix computations, ấn bản lần thứ 3, Johns Hopkins, Baltimore, 1996. ISBN 0-8018-5414-8.
Lipschutz, Seymour, và Lipson, Mark. Schaum's Outlines: Linear Algebra. Tata McGraw-hill edition. Delhi 2001. pp. 69–80.

Liên kết bên ngoài

Phương pháp khử Gaussian Lưu trữ ngày 24-05-2010 tại Wayback Machine www.math-linux.com.
Phương pháp khử Gaussian dưới dạng applet Java Lưu trữ ngày 12-08-2006 tại Wayback Machine trên một trang web địa phương. Chỉ hỗ trợ các hệ số tự nhiên.
Phương pháp khử Gaussian tại Viện Phương pháp Số Toàn diện
LinearEquations.c Lưu trữ ngày 22-10-2011 tại Wayback Machine, cài đặt phương pháp khử Gaussian bằng ngôn ngữ C

Các chủ đề trong Đại số tuyến tính
Khái niệm cơ bản	Vô hướng Vectơ Không gian vectơ Phép nhân vô hướng Chiếu vectơ Hệ sinh Ánh xạ tuyến tính Phép chiếu tuyến tính Độc lập tuyến tính Tổ hợp tuyến tính Cơ sở Chuyển cơ sở Vectơ hàng và cột Không gian hàng và cột Hạt nhân Giá trị riêng và vectơ riêng Ma trận chuyển vị Hệ phương trình tuyến tính
Ma trận	Khối Phân rã Nghịch đảo Định thức con Tích Hạng Biến đổi Quy tắc Cramer Phép khử Gauss
Song tuyến tính	Trực giao Tích vô hướng Không gian tích trong Tích ngoài Quá trình Gram–Schmidt
Đại số đa tuyến tính	Định thức Tích vectơ Tích ba Tích vectơ 7 chiều Đại số hình học Đại số ngoài Song vectơ Đa vectơ Tenxơ Cấu xạ ngoài
Xây dựng không gian vectơ	Không gian đối ngẫu Tổng trực tiếp Không gian hàm Thương Không gian con Tích tenxơ
Đại số tuyến tính số	Floating-point Bình phương tối thiểu tuyến tính Ổn định số Basic Linear Algebra Subprograms Ma trận thưa Comparison of linear algebra libraries
Thể loại Mục lục Chủ đề Toán học Wikibook Wikiversity

Theovi.wikipedia.org

Copy link

Nội dung được phát triển bởi đội ngũ Mytour với mục đích chăm sóc khách hàng và chỉ dành cho khích lệ tinh thần trải nghiệm du lịch, chúng tôi không chịu trách nhiệm và không đưa ra lời khuyên cho mục đích khác.

Nếu bạn thấy bài viết này không phù hợp hoặc sai sót xin vui lòng liên hệ với chúng tôi qua email [email protected]