Khử Gauss: Phương pháp giải hệ phương trình

Khử Gauss là một trong những thuật toán nền tảng nhất của đại số tuyến tính để giải các hệ phương trình tuyến tính. Được đặt theo tên nhà toán học người Đức Carl Friedrich Gauss, phương pháp này biến đổi một hệ phương trình sang một dạng tương đương, đơn giản hơn bằng cách thực hiện một chuỗi phép toán trên biểu diễn ma trận của hệ.

Bài viết này sẽ tìm hiểu cách khử Gauss hoạt động, hiện thực nó bằng Python, và xem xét các ứng dụng trong khoa học dữ liệu và tính toán số. Bằng cách hiểu thuật toán này, chúng ta sẽ có cái nhìn sâu hơn về một kỹ thuật cơ bản làm nền tảng cho nhiều phương pháp tính toán trong phân tích dữ liệu.

Khử Gauss là gì?

Khử Gauss là một thuật toán giải hệ phương trình tuyến tính bằng cách lần lượt biến đổi ma trận mở rộng của hệ thành dạng bậc thang theo hàng (REF). Quá trình biến đổi này giữ nguyên tập nghiệm, đồng thời giúp việc tìm giá trị các ẩn dễ dàng hơn.

Một ma trận ở dạng bậc thang theo hàng khi:

• Tất cả các hàng toàn số 0 nằm ở cuối ma trận
• Phần tử dẫn đầu (phần tử khác 0 đầu tiên) của mỗi hàng khác 0 nằm bên phải phần tử dẫn đầu của hàng ngay phía trên
• Mọi phần tử bên dưới một phần tử dẫn đầu đều bằng 0

Để đạt dạng bậc thang theo hàng, ta dùng ba loại phép biến đổi hàng sơ cấp:

• Hoán vị hàng: Đổi chỗ hai hàng
• Nhân hàng: Nhân tất cả phần tử trong một hàng với một hằng số khác 0
• Cộng hàng: Thay một hàng bằng tổng của chính nó và một bội của hàng khác

Ngoài ra, cần phân biệt giữa khử Gauss và khử Gauss–Jordan:

• Khử Gauss biến đổi ma trận về dạng bậc thang theo hàng, sau đó cần thế lùi để tìm giá trị các biến
• Khử Gauss–Jordan tiếp tục quá trình đến dạng bậc thang theo hàng rút gọn (RREF), nơi mọi phần tử dẫn đầu đều bằng 1 và mọi phần tử khác trong cột chứa phần tử dẫn đầu đó đều bằng 0

Mặc dù khử Gauss–Jordan cho nghiệm trực tiếp hơn, khử Gauss thường hiệu quả hơn cho các hệ lớn, đặc biệt khi kết hợp với thế lùi và các kỹ thuật như phân rã LU.

Phân tích từng bước thuật toán khử Gauss

Hãy cùng đi qua quy trình khử Gauss bằng một ví dụ đơn giản. Xét hệ phương trình tuyến tính sau:

Hệ phương trình tuyến tính. Ảnh: Tác giả.

Bước 1: Lập ma trận mở rộng

Trước hết, ta biểu diễn hệ dưới dạng ma trận mở rộng, kết hợp ma trận hệ số với các hằng số:

Ma trận mở rộng. Ảnh: Tác giả.

Bước 2: Khử tiến (forward elimination)

Giờ ta thực hiện các phép biến đổi hàng sơ cấp để đưa ma trận về dạng bậc thang theo hàng.

Chọn phần tử đầu tiên của cột thứ nhất làm điểm tựa (pivot) và khử mọi phần tử bên dưới nó:

• Cộng 3/2 × Hàng 1 vào Hàng 2:

Cộng 3/2 × Hàng 1 vào Hàng 2. Ảnh: Tác giả.

• Cộng Hàng 1 vào Hàng 3:

Cộng Hàng 1 vào Hàng 3. Ảnh: Tác giả.

Chuyển sang cột thứ hai và khử tất cả phần tử bên dưới điểm tựa:

• Nhân Hàng 2 với 2 để điểm tựa bằng 1:

Nhân Hàng 2 với 2. Ảnh: Tác giả.

• Trừ 2 × Hàng 2 khỏi Hàng 3:

Trừ 2 × Hàng 2. Ảnh: Tác giả.

Làm cho điểm tựa ở hàng thứ ba dương:

• Nhân Hàng 3 với -1:

Nhân Hàng 3 với -1. Ảnh: Tác giả.

Khi này ma trận đã ở dạng bậc thang theo hàng.

Bước 3: Thế lùi

Giờ ta có thể tìm giá trị các biến bằng phép thế lùi:

Từ Hàng 3: 

          z = -1

Từ Hàng 2: 

          y + z = 2,

          nên y + (-1) = 2,

          suy ra y = 3

Từ Hàng 1: 

          2x + y - z = 8,

          nên 2x + 3 - (-1) = 8,

          suy ra 2x = 4,

          do đó x = 2

Vậy nghiệm là x = 2, y = 3, z = -1.

Mặc dù ta áp dụng khử Gauss cho ví dụ này, các bước vẫn giữ nguyên đối với các hệ phương trình tuyến tính khác.

Hiện thực khử Gauss trong Python

Dù có thể viết thuật toán bằng Python cơ bản, các phép toán vector hóa của NumPy giúp việc hiện thực gọn gàng hơn và nhanh hơn đáng kể. 

Vì mục đích học tập, việc hiểu thuật toán nền tảng là hữu ích, nhưng cho môi trường sản xuất, nên tận dụng các thư viện đã được tối ưu. Sau khi đã hiểu thuật toán ở phần trước, giờ chúng ta sẽ đi sâu vào hiện thực bằng các thư viện tối ưu trong Python.

Hiện thực dựa trên NumPy

NumPy cung cấp hàm numpy.linalg.solve(), hiện thực một lời giải tối ưu cao cho hệ phương trình tuyến tính:

import numpy as np

# Define the coefficient matrix A and constant vector b
A = np.array([[2, 1, -1],
             [-3, -1, 2],
             [-2, 1, 2]], dtype=float)
b = np.array([8, -11, -3], dtype=float)

# Solve the system Ax = b
x = np.linalg.solve(A, b)

print("Solution:", x)Được hỗ trợ bởi

Trong đoạn mã trên, ta xác định ma trận hệ số A cùng với vectơ hằng b, giống với ma trận mở rộng ta đã lập ở bước 1 của ví dụ khử Gauss bên trên. 

Ta sử dụng hàm numpy.linalg.solve() để tìm nghiệm và in kết quả như bên dưới:

Lời giải bằng triển khai mã. Ảnh: Tác giả.

Hiện thực này dùng LAPACK ở tầng dưới, áp dụng phân rã LU (một biến thể của khử Gauss) được tối ưu về ổn định số và hiệu năng.

Xử lý các trường hợp đặc biệt

Khi hiện thực khử Gauss, bạn sẽ gặp một số trường hợp đặc biệt cần xử lý cẩn thận:

• Ma trận suy biến (singular): Nếu định thức của ma trận hệ số bằng 0 hoặc xấp xỉ 0, hệ hoặc là vô nghiệm hoặc có vô số nghiệm. Hàm linalg.solve() của NumPy sẽ phát sinh LinAlgError trong trường hợp này.

• Ổn định số: Với số chấm động, sai số làm tròn có thể tích lũy và dẫn đến kết quả thiếu chính xác. Chọn điểm tựa từng phần (partial pivoting), tức chọn phần tử lớn nhất trong một cột làm điểm tựa, giúp giảm thiểu vấn đề này.

• Hệ thừa hoặc thiếu phương trình: Khi số phương trình không khớp số ẩn, bạn có thể dùng numpy.linalg.lstsq() để tìm nghiệm bình phương tối thiểu.

Với các hệ lớn có nhiều số 0, các bộ giải ma trận thưa của SciPy có thể nhanh hơn hàng bậc độ so với các bộ giải ma trận đặc:

from scipy.sparse import csr_matrix
from scipy.sparse.linalg import spsolve

# For large sparse matrices
A_sparse = csr_matrix(A)
x = spsolve(A_sparse, b)Được hỗ trợ bởi

Dù hiểu cơ chế của thuật toán là giá trị, trong thực tế, tận dụng các hiện thực đã tối ưu của NumPy và SciPy giúp bạn giải hệ tuyến tính hiệu quả và tin cậy mà không cần tái phát minh bánh xe.

Khử Gauss được dùng ở đâu

Khử Gauss vượt xa phạm vi toán học lý thuyết và có vô số ứng dụng thực tiễn trong nhiều lĩnh vực khoa học, kỹ thuật và phân tích dữ liệu. 

Dưới đây là một số ứng dụng thực tế quan trọng nhất của thuật toán nền tảng này:

• Hồi quy tuyến tính: Trong khoa học dữ liệu, khử Gauss được dùng để giải các phương trình chuẩn xuất hiện khi tìm tham số khớp tốt nhất trong mô hình hồi quy tuyến tính. Điều này giúp nhà phân tích đưa ra dự đoán dựa trên dữ liệu lịch sử.
• Phân tích mạng: Kỹ sư dùng khử Gauss để giải các dòng điện hoặc điện áp chưa biết trong mạch điện bằng cách áp dụng định luật Kirchhoff, sinh ra các hệ phương trình tuyến tính cần giải đồng thời.
• Nghịch đảo ma trận: Khử Gauss là nền tảng để tính nghịch đảo ma trận, rất quan trọng trong các phép biến đổi, phân tích thống kê và giải các bài toán phức tạp trong thuật toán học máy.
• Tích phân số: Khi triển khai các phương pháp số tiên tiến như Euler ẩn hay Runge–Kutta, khử Gauss được dùng để giải các hệ phương trình phát sinh, đảm bảo tính ổn định trong mô phỏng hệ động lực.

Hiểu các ứng dụng này cho thấy một kỹ thuật toán học đơn lẻ có thể làm xương sống cho nhiều công cụ mà các nhà khoa học dữ liệu, kỹ sư và nhà nghiên cứu sử dụng hằng ngày.

Kết luận

Bài viết đã trình bày thuật toán nền tảng khử Gauss để giải hệ phương trình tuyến tính bằng cách biến đổi ma trận về dạng bậc thang theo hàng. Chúng ta cũng đã học cách hiện thực kỹ thuật này trong Python bằng các hàm tối ưu của NumPy, và hiểu các ứng dụng thực tiễn trong hồi quy tuyến tính, phân tích mạng, nghịch đảo ma trận, và các phương pháp số. 

Để đào sâu kiến thức đại số tuyến tính và ứng dụng trong khoa học dữ liệu, hãy cân nhắc đăng ký khóa học Linear Algebra của chúng tôi, nơi bạn sẽ khám phá các khái niệm nâng cao và cách hiện thực những kỹ thuật nền tảng này.