Bối cảnh và vấn đề nghiên cứu

Trong toán học ứng dụng và khoa học kỹ thuật, Đại số tuyến tính giữ vai trò trung tâm đối với nhiều lĩnh vực như Hóa học, Hình học, Lý thuyết đồ thị, Kinh tế lượng, Nén ảnh số và Nhận diện khuôn mặt. Trong khoa học máy tính, mọi dữ liệu tính toán đều được số hóa dưới dạng mảng hoặc dãy số; việc nắm vững và hiện thực hóa các khái niệm đại số là yếu tố then chốt giúp kỹ sư giải quyết các bài toán kỹ thuật phức tạp.

Việc tính toán nghiệm của hệ phương trình đại số tuyến tính quy mô lớn bằng phương pháp thủ công đòi hỏi khối lượng thời gian đáng kể và dễ phát sinh sai số. Sự phát triển của Công nghệ thông tin cho phép tự động hóa quy trình giải các hệ phương trình tuyến tính $Ax = B$ ($n$ phương trình, $n$ ẩn) thông qua các thuật toán số học chính xác hoặc lặp xấp xỉ như Gauss, Gauss-Seidel, Cramer và phương pháp giảm dư. Đồ án "Giải hệ phương trình tuyến tính $Ax=B$ ($n$ phương trình, $n$ ẩn) bằng các phương pháp lặp đơn - Sử dụng danh sách liên kết kép" được thực hiện tại Khoa Công nghệ Thông tin, Trường Đại học Bách khoa – Đại học Đà Nẵng nhằm kết hợp lý thuyết giải thuật số trị với cấu trúc dữ liệu động.

Mục tiêu và nhiệm vụ nghiên cứu của đồ án được xác định cụ thể gồm 7 bước:

  1. Tìm hiểu lý thuyết tổng quan về hệ phương trình đại số tuyến tính.
  2. Nghiên cứu cơ sở toán học của các phương pháp: khử Gauss-Jordan, lặp Gauss-Seidel, quy tắc Cramer và phương pháp giảm dư (relaxation).
  3. Triển khai các ví dụ tính toán thủ công bằng tay trên các hệ phương trình cụ thể để kiểm chứng lý thuyết.
  4. Xây dựng và mô hình hóa thuật toán cho từng phương pháp giải.
  5. Phân tích, đánh giá độ phức tạp thuật toán về thời gian thực thi và không gian bộ nhớ.
  6. Lập trình hiện thực hóa các giải thuật trên máy tính bằng ngôn ngữ lập trình C kết hợp cấu trúc danh sách liên kết kép.
  7. Kiểm thử chương trình, chạy thực nghiệm với các bộ dữ liệu đầu vào và đánh giá kết quả.

Đối tượng và phạm vi nghiên cứu của đề tài tập trung vào việc giải hệ phương trình tuyến tính vuông cấp $n$ với véc-tơ hệ số tự do $B$, xử lý tiền biến đổi ma trận kích thước $n \times (n+1)$ thông qua thao tác xóa cột sau vị trí $n/2$ (hoặc $m/2$), kiểm tra điều kiện hội tụ và tìm nghiệm số của hệ phương trình.

Cơ sở lý thuyết và phương pháp

Khung lý thuyết toán học

Đồ án xây dựng dựa trên nền tảng của đại số tuyến tính và giải thuật số trị:

  • Hệ phương trình đại số tuyến tính: Dạng tổng quát $Ax = B$, trong đó $A$ là ma trận hệ số kích thước $n \times n$, $x$ là véc-tơ ẩn số kích thước $n \times 1$, và $B$ là véc-tơ hệ số tự do kích thước $n \times 1$.
  • Phương pháp khử Gauss: Biến đổi ma trận mở rộng $[A|B]$ về dạng ma trận tam giác trên thông qua các phép biến đổi sơ cấp theo hàng, sau đó áp dụng phép thế lùi để tìm nghiệm duy nhất.
  • Phương pháp lặp Gauss-Seidel: Biến đổi hệ phương trình về dạng lặp $x^{(k+1)} = B^* x^{(k)} + g$. Thuật toán cập nhật nghiệm mới ngay trong quá trình duyệt từng phương trình và dừng lại khi sai số tuyệt đối giữa hai bước lặp thỏa mãn ngưỡng sai số $\varepsilon$ (ngưỡng quy định trong đồ án là esp = 0.001 hoặc 0.0005) hoặc số lần lặp đạt giới hạn MAX_REPE = 80. Điều kiện đủ để chuỗi lặp hội tụ là ma trận $A$ phải là ma trận đường chéo trội nghiêm ngặt (phần tử chéo $|a_{ii}| > \sum_{j \neq i} |a_{ij}|$) hoặc đối xứng xác định dương.
  • Định thức và Phương pháp Cramer: Định thức của ma trận vuông cấp $n$ ($\det(A)$) được tính thông qua quy nạp hoặc khai triển Laplace theo hàng/cột. Hệ Cramer có $\det(A) \neq 0$ sở hữu nghiệm duy nhất xác định bởi công thức $x_i = \det(A_i) / \det(A)$, trong đó $A_i$ là ma trận nhận được từ $A$ khi thay thế cột thứ $i$ bằng véc-tơ cột $B$.
  • Phương pháp giảm dư: Chuẩn hóa ma trận $A$ và véc-tơ $B$ bằng cách chia các phần tử của mỗi hàng cho phần tử chéo chính tương ứng ($a_{ii} \neq 0$). Véc-tơ phần dư ban đầu được xác định bởi $r = B - Ax^{(0)}$. Tại mỗi bước lặp, tìm phần tử có giá trị tuyệt đối cực đại trong $r$, hiệu chỉnh nghiệm $x_i$ và cập nhật lại véc-tơ phần dư cho đến khi đạt tiêu chuẩn hội tụ.

Phương pháp nghiên cứu

Nhóm tác giả sử dụng các phương pháp nghiên cứu học thuật gồm:

  • Phương pháp phân tích và tổng hợp lý thuyết: Hệ thống hóa các định lý, công thức toán học về nghiệm hệ phương trình và các tiêu chuẩn hội tụ giải thuật số.
  • Phương pháp nghiên cứu tài liệu: Khảo sát các giáo trình phương pháp tính và tài liệu cấu trúc dữ liệu giải thuật.
  • Phương pháp tham vấn chuyên môn: Trao đổi, tiếp thu hướng dẫn từ giảng viên hướng dẫn khoa học để chuẩn hóa thiết kế chương trình.
  • Phương pháp thực nghiệm số: Cài đặt mã nguồn, đưa các bộ dữ liệu ma trận từ tệp (DAYSO.IN, MatrixA1.inp, DAYSO_B1.IN...) vào kiểm thử và so sánh kết quả tính toán giữa các phương pháp.

Thiết kế và triển khai

Cấu trúc dữ liệu

Đồ án không sử dụng mảng tĩnh hai chiều thông thường để lưu trữ ma trận mà kết hợp cấu trúc danh sách liên kết kép với danh sách mảng con trỏ nhằm quản lý bộ nhớ động:

  • struct Node: Đại diện cho một phần tử trong danh sách liên kết kép, gồm trường dữ liệu kiểu số thực (float data), con trỏ liên kết kế tiếp (struct Node *next) và con trỏ liên kết phía trước (struct Node *prev).
  • struct ArrayList: Đại diện cho ma trận, gồm trường kích thước tối đa (int max_size) và mảng các con trỏ trỏ đến nút đầu của từng hàng danh sách liên kết (List *PointToHeaderNode).
  • Các hằng số hệ thống định nghĩa trước: #define MAX_SIZE 100, #define MAX_REPE 80, #define esp 0.001.
struct Node {
    float data;
    struct Node *next;
    struct Node *prev;
};
typedef struct Node *List;
typedef struct Node *Position;

struct ArrayList {
    int max_size;
    List *PointToHeaderNode;
};
typedef struct ArrayList *Matrix;

Thiết kế thuật toán và đánh giá độ phức tạp

Chương trình triển khai các giải thuật giải hệ phương trình tuyến tính kết hợp giải thuật tiền xử lý ma trận và biến đổi ma trận về dạng chéo trội.

Thuật toán Mục đích / Nguyên lý chính Độ phức tạp thời gian Độ phức tạp không gian
Khử Gauss Khử phần tử dưới đường chéo chính thành ma trận tam giác trên, thế lùi tìm nghiệm $O(n^3)$ $O(n^2)$ cho ma trận, $O(n)$ cho véc-tơ
Tính định thức (det) Áp dụng phép khử Gauss đưa về ma trận tam giác rồi nhân tích đường chéo chính (thay vì đệ quy $O(n!)$) $O(n^3)$ $O(n^2)$
Quy tắc Cramer Tính định thức ma trận gốc $\det(A)$ và $n$ định thức con $\det(A_i)$ sau khi thế cột $B$ $O(n^4)$ $O(n^2)$
Lặp Gauss-Seidel Lặp cập nhật nghiệm tức thời theo công thức sai số, dừng khi $\Delta \le \varepsilon$ hoặc đạt MAX_REPE $O(n^2 \cdot k)$ ($k \le 80$) $O(n^2)$
Phương pháp giảm dư Chuẩn hóa đường chéo, tìm cực đại véc-tơ phần dư $r$, cập nhật thành phần nghiệm $O(n^2 \cdot k)$ ($k \le 80$) $O(n^2)$
Biến đổi chéo trội (change_Matrix) Tìm phần tử có trị tuyệt đối lớn nhất mỗi hàng, hoán vị hàng để đưa về đường chéo chính $O(n^2)$ $O(n)$

Kiến trúc luồng điều khiển và giao diện

Chương trình được xây dựng trên giao diện dòng lệnh Console của ngôn ngữ C, hỗ trợ hiển thị màu sắc trực quan qua hàm setColor. Luồng thực thi chia thành 6 phân hệ menu chức năng:

  • Nhập dữ liệu: Cho phép người dùng nhập thủ công từ bàn phím hoặc đọc tự động từ các tệp văn bản chuẩn bị sẵn (DAYSO1.IN, DAYSO2.IN, DAYSO3.IN...).
  • Tiền xử lý: Đọc ma trận kích thước $n \times (n+1)$, thực hiện hàm deleteMiddle để xóa cột nằm sau vị trí $n/2$, tạo ra ma trận vuông $n \times n$.
  • Nhập véc-tơ $B$: Nhập trực tiếp hoặc nạp từ các tệp DAYSO_B1.IN, DAYSO_B2.IN, DAYSO_B3.IN.
  • Thực thi tính toán: Gọi các hàm giải nghiệm tương ứng (Gauss, Gauss_Siedel, Krame, Giam_du). Trong quá trình giải lặp, chương trình in chi tiết từng bước lặp ra màn hình Console.
  • Xuất kết quả: Xuất ma trận $A$ sau khi xử lý ra tệp RESULT1.OUT và ghi kết quả véc-tơ nghiệm của hệ phương trình ra tệp RESULT2.

Nội dung chính theo từng chương

Chương 1: TỔNG QUAN ĐỀ TÀI

Chương 1 giới thiệu khái quát về tầm quan trọng của Đại số tuyến tính trong các ngành kỹ thuật, kinh tế và khoa học máy tính. Tác giả trình bày tổng quan các phương pháp giải hệ phương trình tuyến tính cổ điển và hiện đại, bao gồm phương pháp biến đổi ma trận, phương pháp Gauss, Gauss-Jordan, Jacobi, Gauss-Seidel, Cramer và phương pháp giảm dư. Đồng thời, chương này xác định rõ các công cụ kỹ thuật lựa chọn cho đồ án: ngôn ngữ lập trình C, lưu trữ dữ liệu qua tệp tin văn bản định dạng .IN / .OUT, hiển thị giao diện bảng chọn trên màn hình Console và định hình các ý tưởng thuật toán cốt lõi.

Chương 2: CƠ SỞ LÝ THUYẾT

Chương 2 trình bày chi tiết cơ sở toán học phục vụ việc cài đặt chương trình:

  • Nguyên lý phương pháp khử Gauss-Jordan và mục tiêu đưa ma trận về ma trận đường chéo mà không qua bước tính định thức.
  • Cơ chế lặp Gauss-Seidel, công thức ma trận lặp $B$, các điều kiện hội tụ nghiêm ngặt và định nghĩa ma trận chéo trội.
  • Khái niệm ma trận bù $A_{ij}$, định nghĩa định thức cấp $n$ theo quy nạp, định lý khai triển định thức Laplace theo hàng hoặc cột bất kỳ, và các tính chất cơ bản của định thức (đổi dấu khi đổi hàng, định thức bằng 0 khi có hàng tỉ lệ...).
  • Điều kiện áp dụng quy tắc Cramer cho hệ có $\det(A) \neq 0$ và hai cách tiếp cận giải (sử dụng ma trận nghịch đảo $A^{-1}B$ hoặc công thức tỉ số định thức).
  • Điều kiện hội tụ của phương pháp giảm dư: yêu cầu các phần tử trên đường chéo chính phải khác 0, ma trận chéo trội, và phân tích sự phụ thuộc của tốc độ hội tụ vào giá trị riêng $\lambda \ge 1$ cũng như độ vượt trội của phần tử đường chéo $a_{ii}$.

Chương 3: TỔ CHỨC CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN

Chương 3 là phần trọng tâm mô tả chi tiết bài toán và giải pháp kỹ thuật:

  • Phát biểu bài toán: Đọc ma trận $A$ kích thước $n \times m$ ($m = n+1$) từ tệp DAYSO.IN, thực hiện xóa một phần tử sau vị trí $n/2$ trên từng hàng danh sách liên kết để nhận ma trận vuông $n \times n$. Nhập mảng $B$ và tiến hành giải hệ phương trình.
  • Cấu trúc dữ liệu: Khai báo cấu trúc Node cho danh sách liên kết kép và ArrayList cho cấu trúc dữ liệu ma trận.
  • Mô tả thuật toán từng bước và đánh giá độ phức tạp:
    • Thuật toán Gauss với các bước kiểm tra phần tử chéo, khử hàng và thế lùi (thời gian $O(n^3)$).
    • Thuật toán Gauss-Seidel với vòng lặp do-while, tính tổng tích phần tử không chéo, kiểm tra điều kiện sai số esp và giới hạn lặp MAX_REPE (thời gian $O(n^2)$ mỗi chu kỳ lặp).
    • Thuật toán tính định thức ma trận bằng phương pháp khử Gauss thay cho giải thuật đệ quy nhằm tối ưu độ phức tạp từ $O(n!)$ xuống $O(n^3)$.
    • Thuật toán Cramer thực hiện sao chép ma trận, thay thế từng cột bằng $B$ và tính định thức (thời gian $O(n^4)$).
    • Thuật toán giảm dư gồm các bước chuẩn hóa hàng theo phần tử chéo chính, tính véc-tơ phần dư ban đầu $r$, lặp cập nhật thành phần nghiệm cực đại và đánh giá hội tụ.
    • Thuật toán change_Matrix đưa ma trận về dạng chéo trội thông qua tìm phần tử lớn nhất tuyệt đối trên mỗi hàng và hoán vị hàng (thời gian $O(n^2)$, không gian $O(n)$).

Chương 4: CHƯƠNG TRÌNH VÀ KẾT QUẢ

Chương 4 công bố kết quả cài đặt và thực nghiệm phần mềm:

  • Mô tả cấu trúc tổ chức mã nguồn trong môi trường C và thiết kế giao diện Console tương tác qua hệ thống Menu số.
  • Kết quả thực thi với các bộ dữ liệu thử nghiệm chuẩn bị sẵn (MatrixA1.inp, MatrixA2.inp, MatrixA3.inp).
  • Minh chứng các chức năng: tạo ma trận, nhập ma trận thủ công hoặc qua tệp, nhập lại ma trận, in ma trận, xóa cột sau vị trí $n/2$, nhập véc-tơ $B$, in hệ phương trình $Ax = B$.
  • Kết quả giải nghiệm và thông báo hội tụ đối với từng phương pháp: nghiệm phương pháp Gauss, trường hợp ma trận thỏa mãn hoặc không thỏa mãn điều kiện hội tụ của Gauss-Seidel và phương pháp giảm dư, kết quả phương pháp Cramer.
  • Xuất dữ liệu nghiệm và ma trận sau biến đổi ra các tệp tin RESULT1.OUT và RESULT2.
  • Nhận xét, đánh giá hiệu năng và phân tích các điểm hạn chế trong khâu quản lý bộ nhớ của chương trình.

Chương 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN

Chương 5 tổng kết lại toàn bộ kết quả nghiên cứu của đồ án, khẳng định tính đúng đắn của việc ứng dụng các phương pháp số giải hệ phương trình tuyến tính trên cấu trúc dữ liệu động. Đồng thời, tác giả đề xuất các hướng mở rộng nhằm khắc phục các điểm hạn chế về lý thuyết đại số và nâng cao tiện ích ứng dụng trong thực tế.

Kết quả và đóng góp

Kết quả đạt được

Đồ án đã hiện thực hóa thành công một ứng dụng tính toán số học hoàn chỉnh trên nền tảng C với các kết quả cụ thể:

  • Xây dựng thành công cấu trúc dữ liệu ma trận dựa trên danh sách liên kết kép (List, Node, ArrayList), cho phép cấp phát động và thao tác xóa cột linh hoạt trên bộ nhớ.
  • Cài đặt chính xác 4 giải thuật giải hệ phương trình tuyến tính: Gauss, Gauss-Seidel, Cramer và Giảm dư.
  • Cài đặt giải thuật phụ trợ tối ưu: giải thuật tính định thức bằng phép khử Gauss đạt độ phức tạp $O(n^3)$ (loại bỏ chi phí $O(n!)$ của phương pháp đệ quy) và thuật toán hoán vị hàng đưa ma trận về dạng chéo trội với độ phức tạp $O(n^2)$.
  • Hệ thống kiểm soát tốt các điều kiện toán học: tự động kiểm tra phần tử chéo bằng 0, kiểm tra điều kiện hội tụ của phương pháp lặp, xử lý các trường hợp phân kỳ hoặc vượt quá ngưỡng lặp tối đa (MAX_REPE = 80).
  • Giao diện Console hỗ trợ bảng chọn menu đa cấp, định dạng màu sắc trực quan, cho phép tương tác tệp hai chiều (đọc từ .IN / .inp và ghi kết quả ra RESULT1.OUT, RESULT2).

Đóng góp kỹ thuật và học thuật

Đồ án đã chứng minh tính khả thi của việc kết hợp cấu trúc dữ liệu động (danh sách liên kết kép) với các thuật toán đại số tuyến tính số trị. Khác với cách tiếp cận mảng hai chiều truyền thống, mô hình danh sách liên kết kép giúp thao tác xóa phần tử/cột ma trận tại vị trí bất kỳ (cụ thể là sau vị trí $n/2$) diễn ra thuận tiện thông qua việc điều chỉnh các liên kết con trỏ next và prev mà không cần dịch chuyển toàn bộ mảng nhớ liên tục.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế

Nhóm tác giả đã thẳng thắn chỉ ra hai hạn chế tồn tại trong chương trình:

  1. Chưa xác định hạng ma trận (Matrix Rank): Chương trình chưa cài đặt chức năng tìm hạng của ma trận hệ số $A$ và ma trận mở rộng $[A|B]$ (theo định lý Kronecker-Capelli) để biện luận chính xác các trường hợp đặc biệt của hệ phương trình như vô nghiệm hoặc vô số nghiệm (tìm không gian nghiệm không tầm thường).
  2. Chi phí bộ nhớ của cấu trúc dữ liệu: Việc sử dụng cấu trúc danh sách liên kết kép cho từng phần tử số thực tạo ra nhiều con trỏ liên kết (*next, *prev), làm gia tăng phụ phí bộ nhớ (memory overhead) so với việc sử dụng mảng liên tục trong các bài toán ma trận quy mô lớn.

Hướng nghiên cứu và phát triển tiếp

Dựa trên các hạn chế đã xác định, đồ án đề xuất các định hướng mở rộng:

  1. Bổ sung mô-đun tính hạng của ma trận nhằm hoàn thiện khả năng biện luận nghiệm tự động cho mọi dạng hệ phương trình tuyến tính.
  2. Tối ưu hóa cấu trúc lưu trữ dữ liệu để giảm thiểu mức tiêu hao bộ nhớ của hệ thống con trỏ.
  3. Tích hợp chương trình vào các hệ thống tính toán hỗ trợ học tập trong nhà trường, cung cấp giải pháp từng bước giải chi tiết cho học sinh, sinh viên khi xử lý các hệ phương trình tuyến tính bậc cao ($n \ge 5$ ẩn) mà các dòng máy tính cầm tay thông dụng (như Casio) chưa hỗ trợ.

Giá trị tham khảo

Đồ án là tài liệu tham khảo hữu ích cho:

  • Sinh viên chuyên ngành Công nghệ thông tin, Khoa học máy tính, Toán tin và Kỹ thuật phần mềm đang học các học phần Phương pháp tính (Giải thuật số trị) và Cấu trúc dữ liệu và giải thuật.
  • Người học cần tài liệu mẫu về cách thức cài đặt ma trận động bằng danh sách liên kết kép trong ngôn ngữ C thay cho mảng tĩnh hai chiều.
  • Các nhà phát triển phần mềm giáo dục muốn xây dựng các công cụ mô phỏng từng bước giải thuật số học (in chi tiết từng bước khử Gauss, từng chu kỳ lặp Gauss-Seidel và phương pháp giảm dư).

Câu hỏi thường gặp

1. Tại sao nhóm tác giả không dùng phương pháp đệ quy để tính định thức trong thuật toán Cramer?

Phương pháp tính định thức bằng đệ quy dựa trên khai triển Laplace có độ phức tạp thời gian lên tới $O(n!)$, khiến chương trình bị quá tải và thời gian thực thi tăng bùng nổ khi $n$ lớn. Nhóm tác giả đã thay thế bằng phương pháp khử Gauss biến đổi ma trận về dạng tam giác trên, giúp giảm độ phức tạp tính định thức xuống mức đa thức $O(n^3)$.

2. Thuật toán change_Matrix trong đồ án hoạt động theo nguyên lý nào?

Thuật toán duyệt qua từng hàng của ma trận $A$, tìm phần tử có giá trị tuyệt đối lớn nhất trên hàng đó cùng chỉ số cột tương ứng. Sau đó, thuật toán thực hiện hoán vị hàng tương ứng với hàng đang xét để đưa phần tử lớn nhất đó về nằm trên đường chéo chính, hỗ trợ thỏa mãn điều kiện ma trận chéo trội với độ phức tạp $O(n^2)$.

3. Điều kiện dừng của phương pháp lặp Gauss-Seidel và phương pháp giảm dư trong chương trình là gì?

Cả hai phương pháp dừng lại và trả về kết quả thành công khi sai số giữa các bước lặp nhỏ hơn ngưỡng sai số quy định (esp = 0.001 hoặc 0.0005). Trong trường hợp chuỗi nghiệm không hội tụ, vòng lặp sẽ dừng và báo lỗi khi số lần lặp chạm ngưỡng tối đa MAX_REPE = 80.

4. Thao tác tiền xử lý ma trận theo yêu cầu đề bài diễn ra như thế nào?

Dữ liệu ban đầu được đọc từ tệp DAYSO.IN dưới dạng ma trận $A$ kích thước $n \times (n+1)$ biểu diễn bằng danh sách liên kết kép. Trước khi giải hệ phương trình, hàm deleteMiddle duyệt qua từng hàng và xóa bỏ một phần tử nằm sau vị trí $n/2$ (làm tròn nếu lẻ) để đưa kích thước ma trận về dạng vuông $n \times n$.

Kết luận

Đồ án "Giải hệ phương trình tuyến tính $Ax=B$ bằng các phương pháp lặp đơn - Sử dụng danh sách liên kết kép" của nhóm sinh viên Hà Đức Kiên và Ngô Văn Lộc (Trường Đại học Bách khoa – Đại học Đà Nẵng) đã hoàn thành đầy đủ mục tiêu thiết kế và cài đặt hệ thống tính toán số trị trên ngôn ngữ C. Việc kết hợp cấu trúc dữ liệu danh sách liên kết kép với các giải thuật khử Gauss, Gauss-Seidel, Cramer, giảm dư và thuật toán hoán vị chéo trội mang lại giải pháp linh hoạt trong xử lý ma trận động. Đồ án cung cấp nền tảng tốt cho việc phát triển các công cụ hỗ trợ giảng dạy toán học tính toán quy mô lớn và mở ra hướng hoàn thiện về mặt biện luận hạng ma trận trong tương lai.