Bài giảng 8: Thuật toán Khử Hàng
Thuật toán sau bao gồm bốn bước và tạo ra một ma trận ở dạng bậc thang. Bước thứ năm tạo ra một ma trận ở dạng bậc thang rút gọn. Chúng tôi minh họa thuật toán bằng một ví dụ.
Ví dụ: Áp dụng các phép biến đổi hàng sơ cấp để chuyển ma trận sau đầu tiên thành dạng bậc thang, sau đó thành dạng bậc thang rút gọn:
GIẢI
Bước 1: Bắt đầu với cột không chứa toàn số 0 nằm xa bên trái nhất. Đây là cột trụ. Vị trí trụ nằm ở hàng trên cùng.
Bước 2: Chọn một phần tử khác 0 trong cột trụ làm trụ. Nếu cần, hoán đổi các hàng để đưa phần tử này vào vị trí trụ.
Hoán đổi hàng 1 và hàng 3. (Chúng ta cũng có thể hoán đổi hàng 1 và hàng 2.)
Bước 3: Sử dụng phép thay thế hàng để tạo các số 0 ở tất cả các vị trí bên dưới trụ.
Là một bước chuẩn bị, chúng ta có thể chia hàng trên cùng cho trụ, 3. Nhưng vì có hai số 3 trong cột 1, nên cũng dễ dàng cộng −1 lần hàng 1 vào hàng 2.
Bước 4: Che (hoặc bỏ qua) hàng chứa vị trí trụ và che tất cả các hàng phía trên nó (nếu có). Áp dụng lại các bước 1–3 cho ma trận con còn lại. Lặp lại quá trình này cho đến khi không còn hàng khác 0 nào để biến đổi.
Với hàng 1 bị che, bước 1 cho thấy rằng cột 2 là cột trụ tiếp theo. Ở bước 2, chọn phần tử “trên cùng” trong cột đó làm trụ.
Ở bước 3, chúng ta có thể thêm một bước tùy chọn là chia hàng “trên cùng” của ma trận con cho trụ, 2. Thay vào đó, ta cộng −3/2 lần hàng “trên cùng” vào hàng bên dưới.
Khi che hàng chứa vị trí trụ thứ hai để thực hiện bước 4, chúng ta còn lại một ma trận con chỉ có một hàng:
Các bước 1–3 không yêu cầu thêm công việc nào cho ma trận con này, và chúng ta đã đạt được dạng bậc thang của ma trận ban đầu. Nếu chúng ta muốn dạng bậc thang rút gọn, ta thực hiện một bước nữa.
Bước 5: Bắt đầu từ trụ bên phải nhất, làm việc lên trên và sang trái, tạo các số 0 phía trên mỗi trụ. Nếu một trụ khác 1, biến nó thành 1 bằng phép nhân vô hướng.
Trụ bên phải nhất nằm ở hàng 3. Tạo các số 0 phía trên nó bằng cách cộng các bội số thích hợp của hàng 3 vào hàng 2 và hàng 1.
Trụ tiếp theo nằm ở hàng 2. Chia hàng này cho giá trị trụ để chuẩn hóa về 1.
Tạo số 0 trong cột 2 bằng cách cộng 9 lần hàng 2 vào hàng 1.
Cuối cùng, chuẩn hóa hàng 1, chia cho trụ, 3.
Đây là dạng bậc thang rút gọn của ma trận ban đầu.
Tổ hợp các bước 1–4 được gọi là giai đoạn tiến của thuật toán khử hàng. Bước 5, tạo ra dạng bậc thang rút gọn duy nhất, được gọi là giai đoạn lùi.
Lưu ý về số học
Ở bước 2, một chương trình máy tính thường chọn làm trụ phần tử có giá trị tuyệt đối lớn nhất trong cột. Chiến lược này, được gọi là pivoting từng phần (partial pivoting), được sử dụng vì nó giúp giảm lỗi làm tròn trong các phép tính.