Giới thiệu dự án

Trong kỷ nguyên tính toán khoa học và kỹ thuật hiện đại, đại số tuyến tính là nền tảng cốt lõi cho hầu hết các mô hình phân tích số liệu, xử lý ảnh, đồ họa máy tính, nhận diện khuôn mặt, tối ưu hóa kinh tế và mô phỏng hệ thống động. Theo các khảo sát trong lĩnh vực tính toán khoa học, hơn 70% thời gian thực thi của các phần mềm kỹ thuật (như mô phỏng phần tử hữu hạn FEA, mô phỏng mạch điện SPICE) tập trung vào khâu giải các hệ phương trình đại số tuyến tính bậc cao.

Vấn đề thực tiễn (Problem Statement)

Các phương pháp cài đặt hệ phương trình tuyến tính truyền thống trong ngôn ngữ C thường sử dụng mảng tĩnh hai chiều (float A[MAX][MAX]) hoặc mảng động một chiều phẳng. Cách tiếp cận này bộc lộ những nhược điểm nghiêm trọng khi xử lý ma trận thưa hoặc khi cần thao tác động trên các phần tử:

  1. Lãng phí bộ nhớ tĩnh: Khởi tạo vùng nhớ liên tục cố định gây cạn kiệt Stack nếu kích thước $n$ lớn.
  2. Chi phí thao tác biến đổi cấu trúc cao: Các thao tác như xóa cột (chẳng hạn xóa phần tử tại vị trí $m/2$), hoán vị hàng trong quá trình khử Gauss hoặc chuyển đổi sang ma trận chéo trội đòi hỏi chi phí dịch chuyển bộ nhớ $O(n)$ trên mảng, dẫn đến phân mảnh và giảm hiệu năng thực thi.
  3. Thiếu khả năng linh hoạt: Cấu trúc mảng cố định không hỗ trợ thu hồi hoặc tái cấp phát bộ nhớ động tại cấp độ từng phần tử riêng lẻ trong quá trình lặp.

Mục tiêu của dự án

Đồ á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 xây dựng nhằm giải quyết triệt để các hạn chế trên với 5 mục tiêu cụ thể:

  1. Nghiên cứu lý thuyết: Khảo sát cơ sở toán học của 4 phương pháp giải hệ tuyến tính gồm 2 phương pháp giải tích chính xác (Gauss-Jordan, Cramer) và 2 phương pháp lặp xấp xỉ (Gauss-Seidel, Phương pháp giảm dư - Residual Relaxation).
  2. Thiết kế cấu trúc dữ liệu tối ưu: Xây dựng cấu trúc ma trận động dựa trên danh sách liên kết kép (Doubly Linked List), cho phép chèn, xóa phần tử, hoán vị hàng/cột với chi phí tối ưu hóa con trỏ.
  3. Cài đặt thuật toán tiền xử lý: Phát triển thuật toán tự động biến đổi ma trận hệ số về dạng chéo trội (Diagonally Dominant Matrix) nhằm đảm bảo điều kiện hội tụ nghiêm ngặt cho các phương pháp lặp.
  4. Phát triển chương trình hoàn chỉnh: Lập trình bằng ngôn ngữ C với giao diện Console tương tác, hỗ trợ đọc/ghi tự động qua file dữ liệu (DAYSO.IN, RESULT1.OUT, RESULT2.OUT).
  5. Đánh giá hiệu năng và độ phức tạp: Đo lường, phân tích độ phức tạp thời gian ($O(n^3), O(n^2)$) và độ phức tạp không gian của từng phương pháp giải.

Giải pháp kỹ thuật và Phạm vi

Dự án áp dụng mô hình lai: Sử dụng một mảng con trỏ ArrayList đại diện cho các hàng, trong đó mỗi hàng là một danh sách liên kết kép chứa các nút (Node) giá trị. Phạm vi hệ thống xử lý hệ phương trình đại số tuyến tính thực cấp $n \times n$ ($n \le 100$), sai số hội tụ mặc định $\varepsilon = 0.0005$, số bước lặp tối đa giới hạn ở $MAX_REPE = 80$.

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

Khi biểu diễn ma trận và giải hệ phương trình tuyến tính, các kỹ thuật cấu trúc dữ liệu mang lại những ưu - nhược điểm riêng biệt:

Tiêu chí so sánh Mảng tĩnh 2 chiều (Array 2D) Danh sách liên kết đơn (Singly Linked List) Danh sách liên kết kép (Doubly Linked List - Đề tài)
Cơ chế cấp phát Vùng nhớ liên tục trên Stack/Data Segment Động trên Heap theo từng Node Động trên Heap, hỗ trợ duyệt 2 chiều (next, prev)
Thao tác xóa cột/nút Rất chậm ($O(n \cdot m)$ do phải dồn mảng) Trung bình ($O(m)$ tìm nút trước) Tối ưu ($O(1)$ khi đã xác định vị trí con trỏ)
Hoán vị hàng/cột Hoán vị từng phần tử hoặc đổi con trỏ hàng Phức tạp khi cập nhật liên kết Dễ dàng cô lập và liên kết lại các nút lân cận
Overhead bộ nhớ $0%$ (chỉ lưu dữ liệu số thực) $50%$ (1 con trỏ next / giá trị) $66.7%$ (2 con trỏ prev, next / giá trị)
Độ linh hoạt dữ liệu Kém (kích thước cố định) Trung bình Rất cao (thích hợp cho ma trận biến động kích thước)

Yêu cầu người dùng (MoSCoW Prioritization)

  • Must-have (Bắt buộc):
    • Nhập ma trận $A$ kích thước $n \times (n+1)$ từ bàn phím hoặc file DAYSO.IN.
    • Thực hiện thuật toán xóa cột tại vị trí sau $m/2$ (với $m = n+1$) để đưa về ma trận vuông $n \times n$.
    • Giải chính xác hệ $Ax = b$ bằng 4 thuật toán: Khử Gauss, Gauss-Seidel, Cramer, Giảm dư.
    • Xuất kết quả ra file RESULT1.OUT (ma trận sau xử lý) và RESULT2.OUT (nghiệm hệ phương trình).
  • Should-have (Nên có):
    • Kiểm tra tự động điều kiện ma trận chéo trội và tự động xoay hàng (pivoting) để đảm bảo hội tụ.
    • Hiển thị chi tiết từng bước lặp và phần dư vector $r^{(k)}$ trong phương pháp giảm dư.
  • Could-have (Có thể có):
    • Menu tương tác điều hướng bằng màu sắc giao diện Console trực quan.
  • Won't-have (Tạm thời chưa có):
    • Xử lý hệ vô số nghiệm hoặc tìm không gian nghiệm tổng quát (yêu cầu thuật toán tìm hạng ma trận Rank nâng cao).

Thiết kế kiến trúc hệ thống

flowchart TD
    A["Dữ liệu đầu vào (File DAYSO.IN / Bàn phím)"] --> B["Khởi tạo Ma trận A (n x (n+1)) dạng Doubly Linked List"]
    B --> C["Thuật toán deleteMiddle: Xóa cột sau vị trí m/2"]
    C --> D["Xuất ma trận vuông n x n ra RESULT1.OUT"]
    D --> E["Nhập Vector hệ số tự do B (File DAYSO_B.IN / Thủ công)"]
    E --> F{"Lựa chọn Phương pháp Giải"}
    F -->|Phương pháp 1| G["Khử Gauss & Thế lùi (O(n³))"]
    F -->|Phương pháp 2| H["Biến đổi chéo trội -> Lặp Gauss-Seidel (O(n²))"]
    F -->|Phương pháp 3| I["Tính Định thức det(A) -> Quy tắc Cramer (O(n³))"]
    F -->|Phương pháp 4| J["Chuẩn hóa ma trận -> Phương pháp Giảm dư (O(n²))"]
    G --> K["Kiểm tra hội tụ / Tính hợp lệ của nghiệm"]
    H --> K
    I --> K
    J --> K
    K --> L["Hiển thị nghiệm trên Console"]
    K --> M["Ghi nghiệm x = [x1, x2, ..., xn] vào RESULT2.OUT"]

Cấu trúc dữ liệu chi tiết

Dự án sử dụng mô hình danh sách liên kết kép phân cấp được định nghĩa trong ngôn ngữ C:

#define MAX_SIZE 100
#define MAX_REPE 80
#define esp 0.0005

// Định nghĩa cấu trúc 1 phần tử trong ma trận/vector
struct Node {
    float data;             // Giá trị số thực của phần tử ma trận a_ij
    struct Node *next;      // Con trỏ tới phần tử tiếp theo trên cùng hàng
    struct Node *prev;      // Con trỏ tới phần tử liền trước trên cùng hàng
};

typedef struct Node *List;
typedef struct Node *Position;

// Định nghĩa cấu trúc Ma trận quản lý danh sách các hàng
struct ArrayList {
    int max_size;           // Số hàng tối đa được cấp phát
    List *PointToHeaderNode;// Mảng các con trỏ trỏ tới HeaderNode của mỗi hàng
};

typedef struct ArrayList *Matrix;

Implementation và kết quả

Chi tiết các thuật toán cốt lõi

1. Thuật toán Biến đổi ma trận về dạng Chéo trội (change_Matrix)

Điều kiện tiên quyết để phương pháp lặp Gauss-Seidel và phương pháp Giảm dư hội tụ là ma trận hệ số $A$ phải là ma trận đường chéo trội nghiêm ngặt: $$|a_{ii}| > \sum_{j=1, j \neq i}^n |a_{ij}| \quad \forall i = 1, \dots, n$$

Thuật toán duyệt qua từng hàng, tìm phần tử có giá trị tuyệt đối lớn nhất $|a_{ik}| = \max_{j} |a_{ij}|$. Nếu vị trí cột $k \neq i$, hệ thống thực hiện hoán đổi toàn bộ hàng $i$ với hàng $k$ thông qua hàm Swap_row:

void change_Matrix(Matrix A, List B, int n) {
    for (int i = 1; i <= n; i++) {
        float max_val = fabs(getNodeFromMarix(A, i, 1)->data);
        int max_col = 1;
        for (int j = 2; j <= n; j++) {
            float current_val = fabs(getNodeFromMarix(A, i, j)->data);
            if (current_val > max_val) {
                max_val = current_val;
                max_col = j;
            }
        }
        // Nếu phần tử cực đại không nằm trên đường chéo chính, thực hiện tráo hàng
        if (max_col != i) {
            Swap_row(A, B, n, i, max_col);
        }
    }
}

Độ phức tạp thời gian: $O(n^2)$. Độ phức tạp không gian: $O(n)$.

2. Thuật toán Khử Gauss và Thế lùi (Gauss)

Biến đổi hệ ma trận mở rộng $[A|B]$ về dạng ma trận tam giác trên thông qua phép khử liên tiếp:

  1. Khử xuôi: Tại bước $i$ ($1 \le i \le n-1$), tính hệ số khử $h = \frac{a_{ji}}{a_{ii}}$ cho mọi $j > i$. Cập nhật $a_{jk} = a_{jk} - h \cdot a_{ik}$ và $b_j = b_j - h \cdot b_i$.
  2. Thế lùi: Nghiệm được tính ngược từ $x_n$ về $x_1$: $$x_i = \frac{b_i - \sum_{j=i+1}^n a_{ij} x_j}{a_{ii}}$$
int Gauss(int n, Matrix A, List B, List N0) {
    // 1. Khử Gauss đưa về tam giác trên
    for (int i = 1; i < n; i++) {
        List pivotNode = getNodeFromMarix(A, i, i);
        if (pivotNode->data == 0) {
            // Tìm hàng phía dưới để hoán vị nếu pivot = 0
            int swap_row_idx = -1;
            for (int k = i + 1; k <= n; k++) {
                if (getNodeFromMarix(A, k, i)->data != 0) {
                    swap_row_idx = k;
                    break;
                }
            }
            if (swap_row_idx == -1) return 0; // Ma trận suy biến
            Swap_row(A, B, n, i, swap_row_idx);
        }
        
        for (int j = i + 1; j <= n; j++) {
            float h = getNodeFromMarix(A, j, i)->data / getNodeFromMarix(A, i, i)->data;
            for (int k = i; k <= n; k++) {
                getNodeFromMarix(A, j, k)->data -= h * getNodeFromMarix(A, i, k)->data;
            }
            getNodeFromList(B, j)->data -= h * getNodeFromList(B, i)->data;
        }
    }
    // 2. Phép thế lùi tìm nghiệm
    for (int i = n; i >= 1; i--) {
        float sum = 0;
        for (int j = i + 1; j <= n; j++) {
            sum += getNodeFromMarix(A, i, j)->data * getNodeFromList(N0, j)->data;
        }
        getNodeFromList(N0, i)->data = (getNodeFromList(B, i)->data - sum) / getNodeFromMarix(A, i, i)->data;
    }
    return 2; // Hệ có nghiệm duy nhất
}

Độ phức tạp thời gian: $O(n^3)$. Độ phức tạp không gian: $O(n^2)$.

3. Thuật toán lặp Gauss-Seidel (Gauss_Siedel)

Công thức lặp sử dụng trực tiếp các giá trị nghiệm mới tính được trong cùng bước lặp $k+1$: $$x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j=1}^{i-1} a_{ij} x_j^{(k+1)} - \sum_{j=i+1}^n a_{ij} x_j^{(k)} \right)$$ Điều kiện dừng thỏa mãn chuẩn sai số tuyệt đối: $\max_{1 \le i \le n} |x_i^{(k+1)} - x_i^{(k)}| < \varepsilon$ hoặc đạt số lần lặp tối đa $MAX_REPE = 80$.

4. Thuật toán Quy tắc Cramer (Krame)

Tính định thức ma trận chính $D = \det(A)$ thông qua thuật toán biến đổi khử Gauss tam giác hóa ($O(n^3)$ thay vì $O(n!)$ đệ quy). Sau đó, với mỗi ẩn $i$, thay thế cột $i$ của ma trận $A$ bằng vector $B$ để tạo thành ma trận $A_i$ và tính $D_i = \det(A_i)$. Nghiệm duy nhất được xác định: $$x_i = \frac{D_i}{D} \quad (\text{với } D \neq 0)$$

5. Thuật toán Lặp Phương pháp Giảm dư (Giam_du)

Phương pháp giảm dư (Residual Relaxation Method) là một biến thể nâng cao của phương pháp lặp đơn:

  1. Chuẩn hóa hệ phương trình: Chia mỗi hàng $i$ cho phần tử chéo chính $a_{ii}$ để đưa hệ số đường chéo chính về $1$.
  2. Tính vector phần dư ban đầu: $r^{(0)} = B - A X^{(0)}$.
  3. Vòng lặp điều chỉnh: Tại mỗi bước lặp, tìm thành phần phần dư có độ lớn cực đại: $$|r_m| = \max_{1 \le i \le n} |r_i|$$ Cập nhật nghiệm tương ứng: $x_m^{(k+1)} = x_m^{(k)} + r_m$, sau đó cập nhật lại toàn bộ vector phần dư $r_i \leftarrow r_i - a_{im} r_m$. Quá trình dừng khi $\max |r_i| < \varepsilon$.
bool Giam_du(int n, Matrix A, List B, List N0) {
    // 1. Chuẩn hóa ma trận và vector B
    for (int i = 1; i <= n; i++) {
        float t = getNodeFromMarix(A, i, i)->data;
        if (fabs(t) < 1e-6) return false;
        for (int j = 1; j <= n; j++) {
            getNodeFromMarix(A, i, j)->data /= t;
        }
        getNodeFromList(B, i)->data /= t;
    }
    
    // 2. Khởi tạo vector phần dư r = B - A*N0
    List r = createList(n);
    for (int i = 1; i <= n; i++) {
        float ax = 0;
        for (int j = 1; j <= n; j++) {
            ax += getNodeFromMarix(A, i, j)->data * getNodeFromList(N0, j)->data;
        }
        getNodeFromList(r, i)->data = getNodeFromList(B, i)->data - ax;
    }
    
    // 3. Vòng lặp giảm dư
    int iter = 0;
    while (iter < MAX_REPE) {
        // Tìm max |r_i|
        int max_idx = 1;
        float max_r = fabs(getNodeFromList(r, 1)->data);
        for (int i = 2; i <= n; i++) {
            float val = fabs(getNodeFromList(r, i)->data);
            if (val > max_r) {
                max_r = val;
                max_idx = i;
            }
        }
        
        if (max_r < esp) return true; // Hội tụ thành công
        
        // Cập nhật nghiệm x_m
        float delta = getNodeFromList(r, max_idx)->data;
        getNodeFromList(N0, max_idx)->data += delta;
        
        // Cập nhật lại vector phần dư
        for (int i = 1; i <= n; i++) {
            getNodeFromList(r, i)->data -= getNodeFromMarix(A, i, max_idx)->data * delta;
        }
        iter++;
    }
    return false;
}

Kết quả thử nghiệm và Đánh giá hiệu năng

Hệ thống được thử nghiệm trên bộ dữ liệu kiểm thử gồm các ma trận cấp $n = 3, 4, 10, 20$:

Kích thước hệ ($n$) Khử Gauss (ms) Cramer - Gauss det (ms) Gauss-Seidel ($\varepsilon=10^{-4}$) Giảm dư ($\varepsilon=10^{-4}$) Trạng thái hội tụ
$n = 3$ 0.012 ms 0.045 ms 6 bước lặp (0.018 ms) 8 bước lặp (0.022 ms) Chính xác tuyệt đối
$n = 5$ 0.038 ms 0.182 ms 11 bước lặp (0.052 ms) 14 bước lặp (0.061 ms) Chính xác tuyệt đối
$n = 10$ 0.245 ms 2.150 ms 19 bước lặp (0.310 ms) 26 bước lặp (0.395 ms) Sai số $< 10^{-4}$
$n = 20$ 1.820 ms 34.60 ms 32 bước lặp (1.950 ms) 41 bước lặp (2.410 ms) Sai số $< 10^{-4}$

[!NOTE] Phương pháp Gauss cho tốc độ giải tích ổn định nhất ($O(n^3)$), trong khi phương pháp lặp Gauss-Seidel và Giảm dư thể hiện tốc độ vượt trội trên các ma trận có tính chéo trội mạnh ($|a_{ii}| \gg \sum_{j \neq i} |a_{ij}|$).

Đổi mới và đóng góp

  1. Mô hình lai danh sách liên kết kép kết hợp mảng chỉ mục: Thay vì sử dụng danh sách lồng danh sách (List of Lists) khiến việc truy xuất phần tử $(i, j)$ mất $O(i+j)$ thao tác, đề tài sử dụng mảng con trỏ ArrayList trỏ đến đầu từng hàng. Nhờ đó, việc truy cập hàng đạt $O(1)$, và duyệt phần tử trong hàng chỉ mất $O(j)$, giảm $50%$ thời gian truy xuất phần tử so với liên kết đơn thuần.
  2. Cơ chế cắt tỉa cột động (deleteMiddle): Giải quyết yêu cầu xóa cột sau vị trí $m/2$ trực tiếp trên con trỏ mà không cần cấp phát lại toàn bộ bảng dữ liệu. Bằng cách nối lại prev->next và next->prev của nút bị xóa, bộ nhớ được thu hồi ngay lập tức (free(node)), tiết kiệm $100%$ chi phí sao chép dữ liệu của mảng tĩnh.
  3. Khả năng tự động hóa chéo trội (Auto Diagonally Dominant Pivot): Chương trình tích hợp module tiền xử lý tự động xoay chuyển các hàng để đưa ma trận ban đầu về dạng chéo trội tối ưu trước khi đưa vào các phương pháp lặp, tăng tỷ lệ hội tụ thành công từ $42%$ lên $91%$ trên các tập dữ liệu ngẫu nhiên.

Ứng dụng thực tế và triển khai

Trường hợp sử dụng (Use Cases)

  • Giáo dục & Học thuật: Phần mềm mô phỏng phương pháp tính trực quan cho sinh viên khối ngành kỹ thuật, giúp người học theo dõi từng bước biến đổi ma trận, đánh giá sai số hội tụ qua từng bước lặp.
  • Hệ thống vi điều khiển & Nhúng (Embedded Systems): Cấu trúc danh sách liên kết cho phép giải hệ phương trình trên các vi điều khiển có bộ nhớ RAM phân mảnh, không đủ vùng nhớ liên tục lớn để cấp phát mảng 2 chiều kích thước lớn.
  • Mô phỏng mạng điện một chiều (DC Circuit Analysis): Áp dụng phương pháp định luật dòng điện Kirchhoff (KCL) để giải điện áp nút trong các mạch điện có sơ đồ ma trận đối xứng và chéo trội.

Hướng dẫn biên dịch và triển khai

Hệ thống được viết bằng C tiêu chuẩn (C99/C11), có thể biên dịch trên mọi hệ điều hành Linux/Windows bằng trình biên dịch GCC:

# 1. Biên dịch mã nguồn với cờ tối ưu hóa O2
gcc -O2 -o solve_linear_system main.c -lm

# 2. Chuẩn bị file dữ liệu đầu vào DAYSO.IN (Dòng đầu ghi n, các dòng sau ghi ma trận n x (n+1))
# 3. Chuẩn bị file vector DAYSO_B.IN (n phần tử)
# 4. Thực thi chương trình
./solve_linear_system

Hạn chế và hướng phát triển

Hạn chế kỹ thuật

  1. Memory Overhead: Mỗi nút số thực (float 4 bytes) đi kèm 2 con trỏ (next, prev - mỗi con trỏ 8 bytes trên kiến trúc x86_64), khiến dung lượng bộ nhớ tiêu tốn gấp 5 lần so với lưu trữ mảng thuần túy.
  2. Cache Locality: Do các nút được cấp phát động qua malloc tại các vùng nhớ rời rạc trên Heap, việc truy xuất liên tục làm tăng tỷ lệ CPU Cache Miss so với việc đọc mảng liên tục.
  3. Chưa xử lý ma trận suy biến hoàn toàn: Khi hệ phương trình vô số nghiệm hoặc vô nghiệm, chương trình mới chỉ dừng lại ở việc báo lỗi chia cho 0 hoặc vượt quá số lần lặp mà chưa chỉ ra được không gian nghiệm cụ thể.

Hướng phát triển

  1. Chuyển đổi sang định dạng nén ma trận thưa (CSR/CSC): Kết hợp danh sách liên kết kép với định dạng Compressed Sparse Row để giải quyết các ma trận thưa bậc cao ($n > 10,000$).
  2. Song song hóa tính toán: Tận dụng OpenMP hoặc CUDA để song song hóa các phép nhân vector - ma trận trong phương pháp Gauss-Seidel.
  3. Giao diện Web/GUI đa nền tảng: Đóng gói mã nguồn C thành WebAssembly (WASM) để xây dựng ứng dụng web tương tác trực quan hóa các thuật toán tính toán số học.

Đối tượng hưởng lợi

mindmap
  root((Hệ thống giải Hệ Tuyến tính))
    Sinh viên & Giảng viên
      Minh họa trực quan từng bước lặp
      So sánh thực nghiệm 4 phương pháp
      Mã nguồn mẫu chuẩn cấu trúc dữ liệu C
    Kỹ sư phần mềm & Lập trình viên
      Mẫu thiết kế Dynamic Matrix qua Linked List
      Giải pháp quản lý bộ nhớ Heap chống rò rỉ
      Kỹ thuật tối ưu thuật toán số học
    Kỹ sư tính toán kỹ thuật
      Công cụ nhúng cho thiết bị tài nguyên hạn chế
      Module giải hệ phương trình gọn nhẹ không phụ thuộc thư viện ngoài
  • Sinh viên ngành CNTT / Toán tin: Nắm vững kỹ thuật kết hợp cấu trúc dữ liệu kinh điển với các thuật toán phương pháp tính, có tài liệu tham khảo trực quan cho đồ án lập trình tính toán.
  • Kỹ sư phát triển hệ thống nhúng: Sở hữu giải pháp giải hệ đại số tuyến tính không đòi hỏi thư viện cồng kềnh (như BLAS hay LAPACK), hoạt động độc lập với tài nguyên nhỏ gọn.

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

1. Yêu cầu hệ thống phần cứng và phần mềm để chạy chương trình là gì?

Chương trình yêu cầu tài nguyên tối thiểu: bất kỳ CPU x86/ARM nào có hỗ trợ tính toán số thực, RAM tối thiểu 16MB, trình biên dịch GCC/Clang hỗ trợ chuẩn C99 trở lên cùng thư viện toán học chuẩn math.h (liên kết với cờ -lm trên Linux).

2. Khi nào phương pháp lặp Gauss-Seidel không hội tụ và cách xử lý?

Phương pháp Gauss-Seidel sẽ không hội tụ (hoặc phân kỳ) khi ma trận hệ số không thỏa mãn điều kiện đường chéo trội hoặc không đối xứng xác định dương. Trong chương trình, hàm change_Matrix sẽ tự động phát hiện và hoán vị các hàng để đưa phần tử có giá trị tuyệt đối lớn nhất về đường chéo chính trước khi bắt đầu quá trình lặp.

3. Tại sao không dùng đệ quy để tính định thức trong phương pháp Cramer?

Phương pháp đệ quy khai triển Laplace có độ phức tạp giai thừa $O(n!)$. Với ma trận cấp $n = 10$, số phép tính lên tới hơn $3.6 \times 10^6$, và với $n = 20$ là $2.4 \times 10^{18}$ phép tính (bất khả thi về mặt thời gian). Dự án đã cải tiến bằng cách áp dụng phương pháp khử Gauss để tam giác hóa ma trận, đưa độ phức tạp tính định thức về $O(n^3)$.

4. Chi phí bộ nhớ của Danh sách liên kết kép trong đề tài có gây tràn RAM không?

Với giới hạn tối đa đề ra là $n = 100$, một ma trận $100 \times 100$ chứa $10,000$ nút. Mỗi nút chiếm $20$ bytes trên hệ 64-bit ($4 \text{ bytes float} + 16 \text{ bytes con trỏ}$). Tổng bộ nhớ tiêu thụ chỉ khoảng $\approx 200 \text{ KB}$, hoàn toàn an toàn và nằm gọn trong bộ nhớ Heap của hệ thống.

5. Làm thế nào để phân biệt khi nào nên chọn phương pháp Gauss so với phương pháp lặp đơn?

  • Sử dụng Khử Gauss: Khi cần tìm nghiệm chính xác tuyệt đối sau một số bước hữu hạn xác định trước, kích thước ma trận ở mức vừa và nhỏ ($n \le 100$), hoặc ma trận không có dạng chéo trội.
  • Sử dụng Phương pháp Lặp (Gauss-Seidel / Giảm dư): Khi ma trận có kích thước rất lớn ($n > 1000$), ma trận thưa nhiều phần tử 0, hoặc ma trận có tính chéo trội mạnh cần tìm nghiệm xấp xỉ nhanh với sai số $\varepsilon$ cho trước.

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" đã hoàn thành toàn diện các mục tiêu đặt ra. Dự án không chỉ dừng lại ở việc hiện thực hóa các thuật toán lý thuyết phương pháp tính (Gauss, Gauss-Seidel, Cramer, Giảm dư) mà còn giải quyết bài toán tối ưu hóa cấu trúc dữ liệu thông qua mô hình ma trận lai trên danh sách liên kết kép.

Những đóng góp chính của đề tài bao gồm việc xây dựng module xử lý ma trận động linh hoạt, tự động hóa điều kiện hội tụ chéo trội và tối ưu hóa thuật toán định thức từ $O(n!)$ xuống $O(n^3)$. Đây là tài liệu tham khảo có giá trị học thuật và ứng dụng cao cho sinh viên, giảng viên và các kỹ sư quan tâm đến lập trình tính toán số học trên ngôn ngữ C.