Phép Khử Gauss – Wikipedia Tiếng Việt

Trong đại số tuyến tính, phép khử Gauss là một thuật toán có thể được sử dụng để tìm nghiệm của một hệ phương trình tuyến tính, tìm hạng (hay rank) của một ma trận, để tính ma trận nghịch đảo của một ma trận vuông khả nghịch. Phép khử Gauss được đặt theo tên của nhà toán học Đức là Carl Friedrich Gauss.

Các thao tác cơ bản trên hàng được sử dụng trong suốt thuật toán. Thuật toán có 2 phần, mỗi phần đều xem xét các hàng của ma trận theo thứ tự. Phần đầu biến ma trận về dạng hàng bậc thang trong khi phần thứ 2 biến ma trận về dạng hàng bậc thang tối giản. Phần đầu là đủ cho nhiều áp dụng.

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

Ví dụ

[sửa | sửa mã nguồn]

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

2 x + y − z = 8 ( L 1 ) {\displaystyle 2x+y-z=8\quad (L_{1})} − 3 x − y + 2 z = − 11 ( L 2 ) {\displaystyle -3x-y+2z=-11\quad (L_{2})} − 2 x + y + 2 z = − 3 ( L 3 ) {\displaystyle -2x+y+2z=-3\quad (L_{3})}

Thuật toán là như sau: khử x {\displaystyle x} trong tất cả các phương trình bên dưới L 1 {\displaystyle L_{1}} , sau đó khử y {\displaystyle y} trong tất cả các phương trình bên dưới L 2 {\displaystyle L_{2}} . Việc này sẽ làm hệ trở thành dạng tam giác. Sau đó, sử dụng phép thay thế ngược, các ẩn số có thể được giải.

Trong ví dụ, ta khử x {\displaystyle x} từ L 2 {\displaystyle L_{2}} bằng cộng 3 2 L 1 {\displaystyle {\begin{matrix}{\frac {3}{2}}\end{matrix}}L_{1}} vào L 2 {\displaystyle L_{2}} , và sau đó khử x {\displaystyle x} từ L 3 {\displaystyle L_{3}} bằng cộng L 1 {\displaystyle L_{1}} vào L 3 {\displaystyle L_{3}} . Công thức hóa:

L 2 + 3 2 L 1 → L 2 {\displaystyle L_{2}+{\frac {3}{2}}L_{1}\rightarrow L_{2}} L 3 + L 1 → L 3 {\displaystyle L_{3}+L_{1}\rightarrow L_{3}}

Kết quả là:

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

Bây giờ ta khử y {\displaystyle y} từ L 3 {\displaystyle L_{3}} bằng cách cộng − 4 L 2 {\displaystyle -4L_{2}} vào L 3 {\displaystyle L_{3}} :

L 3 + − 4 L 2 → L 3 {\displaystyle L_{3}+-4L_{2}\rightarrow L_{3}}

Kết quả là:

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

Kết quả này là một hệ phương trình tuyến tính dưới dạng tam giác, do đó phần 1 của thuật toán là xong.

Phần thứ 2, thay thế ngược, là giải cho các ẩn số trong thứ tự ngược lại. Do đó, chúng ta có thể dễ dàng thấy rằng

z = − 1 ( L 3 ) {\displaystyle z=-1\quad (L_{3})}

Sau đó, thế z {\displaystyle z} vào L 2 {\displaystyle L_{2}} , giải dễ dàng để có

y = 3 ( L 2 ) {\displaystyle y=3\quad (L_{2})}

Kế tiếp, z {\displaystyle z} và y {\displaystyle y} có thể được thế vào L 1 {\displaystyle L_{1}} , có thể được giải để có

x = 2 ( L 1 ) {\displaystyle x=2\quad (L_{1})}

Do vậy, hệ phương trình đã được giải.

Thuật toán này dùng được trên mọi hệ phương trình tuyến tính. Có thể là hệ không thể được đưa về dạng tam giác, tuy nhiên vẫn có ít nhất một lời giải có giá trị: ví dụ, nếu y {\displaystyle y} không có trong L 2 {\displaystyle L_{2}} và L 3 {\displaystyle L_{3}} sau bước thứ 1 ở trên, thuật toán sẽ không thể đưa hệ về dạng tam giác. Tuy nhiên, nó vẫn đưa hệ về dạng bậc thang. Trong trường hợp này, hệ không có nghiệm duy nhất, và sẽ có vô số nghiệm, vì nó có ít nhất một biến tự do.

Trong thực tế, người ta thường không sử dụng hệ phương trình không mà sử dụng ma trận mở rộng (dễ dàng giải trên máy tính). Sau đây là thuật toán của phép khử Gauss áp dụng trên ma trận mở rộng của hệ bên trên, bắt đầu với:

[ 2 1 − 1 8 − 3 − 1 2 − 11 − 2 1 2 − 3 ] {\displaystyle {\begin{bmatrix}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{bmatrix}}}

mà, cuối cùng của phần 1 của thuật toán ta sẽ có:

[ 2 1 − 1 8 0 1 2 1 2 1 0 0 − 1 1 ] {\displaystyle {\begin{bmatrix}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&-1&1\end{bmatrix}}}

Đó là dạng bậc thang.

Cuối cùng của thuật toán, ta có được

[ 1 0 0 2 0 1 0 3 0 0 1 − 1 ] {\displaystyle {\begin{bmatrix}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{bmatrix}}}

Đó là dạng bậc thang tối giản.

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

[sửa | sửa mã nguồn]

Phép khử Gauss trên một ma trận n × n cần khoảng 2n3 / 3 phép tính toán. Do đó nó có độ phức tạp là O ( n 3 ) {\displaystyle {\mathcal {O}}(n^{3})\,} .

Thuật toán này có thể được sử dụng trên máy tính với hàng ngàn hệ phương trình và ẩn số. Tuy nhiên, phương pháp này không thích hợp với hệ có hàng triệu phương trình. Những hệ lớn như vậy thường được giải bằng các phương pháp lặp lại (iterative method). Có những phương pháp đặc biệt nếu như hệ số theo một khuôn mẫu nào đó.

Phép khử Gauss có thể được tiến hành trên bất cứ trường nào.

Phép khử Gauss là ổn định về phương pháp số cho các ma trận đường chéo chủ yếu hay xác định dương. Cho ma trận tổng quát, phép khử Gauss là ổn định nếu như sử dụng partial pivoting.[1]

Chú thích

[sửa | sửa mã nguồn]

1. ^ Golub and Van Loan, §3.4.6

Tham khảo

[sửa | sửa mã nguồn]

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

Liên kết ngoài

[sửa | sửa mã nguồn]

• Gaussian elimination Lưu trữ 2010-05-24 tại Wayback Machine www.math-linux.com.
• Gaussian elimination as java applet Lưu trữ 2006-08-12 tại Wayback Machine at some local site. Only takes natural coefficients.
• Gaussian elimination at Holistic Numerical Methods Institute
• LinearEquations.c Lưu trữ 2011-10-22 tại Wayback Machine Gaussian elimination implemented using C language

x t s 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