Bài giảng 9: Nghiệm của Hệ Phương Trình Tuyến Tính

Thuật toán khử Gauss dẫn trực tiếp đến một mô tả rõ ràng về tập nghiệm của một hệ phương trình tuyến tính khi thuật toán này được áp dụng cho ma trận mở rộng của hệ phương trình.

Chẳng hạn, giả sử ma trận mở rộng của một hệ phương trình tuyến tính đã được biến đổi thành dạng bậc thang rút gọn tương đương:

$\begin{bmatrix}1&0&-5&1\\0&1&1&4\\0&0&0&0\\\end{bmatrix}$

Có ba ẩn số vì ma trận mở rộng có bốn cột. Hệ phương trình tương ứng là:

(4) $\begin{equation*}\begin{aligned}x_1\quad-5x_3&=1\\\quad x_2+x_3&=4\\0\quad&=0\end{aligned}\qquad \end{equation*}$

Các biến $x_1$ và $x_2$ tương ứng với các cột chứa phần tử chủ chốt trong ma trận được gọi là biến cơ bản. Biến còn lại, $x_3$ , được gọi là biến tự do.

Mỗi khi một hệ phương trình có nghiệm (như trong phương trình (4)), tập nghiệm có thể được mô tả rõ ràng bằng cách giải hệ phương trình rút gọn để biểu diễn các biến cơ bản theo các biến tự do. Việc này khả thi vì dạng bậc thang rút gọn đảm bảo rằng mỗi biến cơ bản chỉ xuất hiện trong đúng một phương trình. Trong (4), ta giải phương trình thứ nhất theo $x_1$ và phương trình thứ hai theo $x_2$ . (Bỏ qua phương trình thứ ba vì nó không đặt ràng buộc nào lên các biến.)

(5) $\begin{equation*}\left\{\begin{matrix}\begin{aligned}x_1&=1+5x_3\\x_2&=4-x_3\\x_3&\;\text{is free}\\\end{aligned}\end{matrix}\right.\qquad\end{equation*}$

Cụm từ “ $x_{3}$ là tự do” có nghĩa là ta có thể chọn bất kỳ giá trị nào cho $x_{3}$ . Khi đó, các công thức trong (5) xác định giá trị của $x_{1}$ và $x_{3}$ . Chẳng hạn, khi $x_3=0$ , nghiệm là (1, 4, 0); khi $x_3=1$ , nghiệm là (6, 3, 1). Mỗi lựa chọn khác nhau của $x_3$ sẽ tạo ra một nghiệm khác nhau của hệ phương trình, và mọi nghiệm của hệ phương trình đều được xác định bởi một giá trị nào đó của $x_{3}$ .

Ví dụ 4: Tìm nghiệm tổng quát của hệ phương trình tuyến tính có ma trận mở rộng đã được đưa về dạng

$\begin{bmatrix}1&6&2&-5&-2&-4\\0&0&2&-8&-1&3\\0&0&0&0&1&7\\\end{bmatrix}$

Giải: Ma trận đang ở dạng bậc thang, nhưng ta cần đưa nó về dạng bậc thang rút gọn trước khi giải các biến cơ bản. Tiếp theo, ta hoàn tất quá trình khử hàng. Ký hiệu ∼ trước một ma trận cho thấy ma trận đó tương đương hàng với ma trận trước đó.

$\begin{bmatrix}1&6&2&-5&-2&-4\\0&0&2&-8&-1&3\\0&0&0&0&1&7\\\end{bmatrix}\sim\begin{bmatrix}1&6&2&-5&0&10\\0&0&2&-8&0&10\\0&0&0&0&1&7\\\end{bmatrix}\\\\\sim\begin{bmatrix}1&6&2&-5&0&10\\0&0&1&-4&0&5\\0&0&0&0&1&7\\\end{bmatrix}\sim\begin{bmatrix}1&6&0&3&0&0\\0&0&1&-4&0&5\\0&0&0&0&1&7\\\end{bmatrix}$

Có năm ẩn số vì ma trận mở rộng có sáu cột. Hệ phương trình tương ứng là:

(6) $\begin{equation*}\begin{matrix}x_{1}+6x_{2}\quad+3x_{4}\quad=0\\\qquad\qquad x_{3}-4x_{4}\quad=5\\\qquad\qquad\qquad\qquad x_{5}=7\end{matrix}\qquad\end{equation*}$

Các cột chứa phần tử chủ chốt trong ma trận là 1, 3 và 5, do đó các biến cơ bản là $x_1$ , $x_3$ và $x_5$ . Các biến còn lại, $x_2$ và $x_4$ , là biến tự do. Giải các biến cơ bản để thu được nghiệm tổng quát:

(7) $\begin{equation*}\left\{\begin{matrix}\begin{aligned}x_1&=-6x_2-3x_4\\x_2&\text{\;is free}\\x_3&=5+4x_4\\x_4&\;\text{is free}\\x_5&=7\end{aligned}\end{matrix}\right.\qquad\end{equation*}$

Lưu ý rằng giá trị của $x_5$ đã cố định bởi phương trình thứ ba trong hệ phương trình (6).

Mô Tả Tham Số của Tập Nghiệm

Các mô tả trong (5) và (7) là các mô tả tham số của tập nghiệm, trong đó các biến tự do đóng vai trò là tham số. Giải một hệ phương trình tức là tìm một mô tả tham số của tập nghiệm hoặc xác định rằng tập nghiệm là rỗng.

Mỗi khi một hệ phương trình có nghiệm và có biến tự do, tập nghiệm sẽ có nhiều cách biểu diễn tham số. Chẳng hạn, trong hệ phương trình (4), ta có thể cộng 5 lần phương trình thứ hai vào phương trình thứ nhất để thu được hệ phương trình tương đương:

$\begin{aligned}x_1+5x_2\qquad&=21\\\qquad x_2+x_3&=4\\\end{aligned}$

Ta có thể coi $x_2$ là tham số và giải $x_1$ và $x_3$ theo $x_2$ , qua đó thu được một mô tả chính xác về tập nghiệm. Tuy nhiên, để thống nhất, ta áp dụng quy ước (mang tính tùy ý) là luôn sử dụng biến tự do làm tham số khi mô tả tập nghiệm.

Nếu một hệ phương trình vô nghiệm, tập nghiệm là rỗng ngay cả khi hệ có biến tự do. Trong trường hợp này, tập nghiệm không có bất kỳ mô tả tham số nào.

Thế Ngược (Back-Substitution)

Xét hệ phương trình có ma trận mở rộng ở dạng bậc thang nhưng chưa ở dạng bậc thang rút gọn:

$\begin{aligned}x_1-7x_2+2x_3-5x_4+8x_5&=10\\x_2-3x_3+3x_4+x_5&=-5\\x_4-x_5&=4\end{aligned}$

Một chương trình máy tính sẽ giải hệ phương trình này bằng phương pháp thế ngược, thay vì đưa về dạng bậc thang rút gọn. Cụ thể, chương trình sẽ giải phương trình thứ ba theo $x_4$ dưới dạng một biểu thức chứa $x_5$ , sau đó thay thế biểu thức đó vào phương trình thứ hai, rồi giải phương trình thứ hai theo $x_2$ , và tiếp tục thay thế các giá trị của $x_2$ và $x_4$ vào phương trình thứ nhất để giải $x_1$ .

Định dạng ma trận của giai đoạn xử lý ngược trong khử hàng (để tạo ra dạng bậc thang rút gọn) có số lượng phép toán số học tương đương với phương pháp thế ngược. Tuy nhiên, cách làm theo định dạng ma trận giúp giảm đáng kể sai sót khi tính toán bằng tay. Chiến lược tốt nhất là chỉ sử dụng dạng bậc thang rút gọn để giải hệ phương trình!

Ghi Chú Số Học

Nhìn chung, giai đoạn khử tiến của phương pháp khử hàng mất nhiều thời gian hơn so với giai đoạn khử lùi. Một thuật toán giải hệ phương trình thường được đo lường bằng số flop (floating-point operations – phép toán số học trên hai số thực).

Một flop là một phép toán số học cơ bản (+, −, ×, ÷) trên hai số thực. Đối với một ma trận kích thước n×(n+1), số flop cần thiết để đưa về dạng bậc thang có thể lên đến ${2n^3}/{3}+{n^2}/{2}-{7n}/{6}\;\text{flops}$ (xấp xỉ ${2n^3}/{3}\;flops$ khi n đủ lớn, chẳng hạn $n\geq 30$ . Ngược lại, quá trình đưa từ dạng bậc thang về dạng bậc thang rút gọn chỉ cần tối đa $n^2 flops.$

Để lại một bình luận Hủy

Chịu trách nhiệm nội dung

Bản quyền

Ý kiến bạn đọc

Bài giảng 9: Nghiệm của Hệ Phương Trình Tuyến Tính

Lesson Attachments

Để lại một bình luận Hủy