行列式計算：上三角化演算法（高斯消元法）C++ 完整實作

前言

行列式計算是線性代數核心問題。本文實作**高斯消元法**將矩陣轉化為上三角形式，行列式等於對角線元素乘積（乘以行交換次數的符號）。代碼包含：列主元選擇（優化數值穩定性）、特殊情況處理（首元為零）、過程輸出、文件 I/O。

演算法流程

1. **讀入矩陣** 從文件
2. **列重排序** ：統計每列零的個數，零多的列優先（減少後續除零風險）
3. **首元為零處理** ：若 (1,1) 為零，向下尋找非零行交換
4. **高斯消元** ：對第 j 列，將第 j+1 到 n 行的第 j 列元素消為零
5. **計算行列式** ：對角線乘積 × (-1)^(行交換次數+列交換次數)

完整 C++ 代碼（現代化重構版）

#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <iomanip>

using namespace std;

const double EPS = 1e-4;

int main() {
    int n;
    cout << "階數: ";
    if(!(cin >> n) || n <= 0 || n > 20) {
        cerr << "無效階數\n";
        return 1;
    }

    vector<vector<double>> a(n, vector<double>(n));
    
    ifstream infile("input.txt");
    if(!infile) {
        cerr << "無法開啟輸入文件\n";
        return 1;
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(!(infile >> a[i][j])) { cerr << "輸入數據不足\n"; return 1; }
    infile.close();

    ofstream outfile("output.txt");
    if(!outfile) { cerr << "無法開啟輸出文件\n"; return 1; }

    // 1. 列重排序：統計每列零的個數
    vector<int> zero_count(n, 0);
    for(int j = 0; j < n; j++)
        for(int i = 0; i < n; i++)
            if(fabs(a[i][j]) < EPS) zero_count[j]++;

    // 排序列索引：零多的在前
    vector<int> col_order(n);
    for(int i = 0; i < n; i++) col_order[i] = i;
    sort(col_order.begin(), col_order.end(), 
         [&](int x, int y) { return zero_count[x] > zero_count[y]; });

    // 應用列交換並記錄交換次數
    int col_swaps = 0;
    vector<vector<double>> mat(n, vector<double>(n));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            mat[i][j] = a[i][col_order[j]];
    
    // 計算列交換次數（逆序對數）
    for(int i = 0; i < n; i++)
        for(int j = i+1; j < n; j++)
            if(col_order[i] > col_order[j]) col_swaps++;

    outfile << "第1步：換列：\n";
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) outfile << setw(8) << mat[i][j];
        outfile << "\n";
    }

    // 2. 首元為零處理
    int row_swaps = 0;
    if(fabs(mat[0][0]) < EPS) {
        for(int i = 1; i < n; i++) {
            if(fabs(mat[i][0]) >= EPS) {
                swap(mat[0], mat[i]);
                row_swaps++;
                break;
            }
        }
        outfile << "第2步：換行（首元為零處理）：\n";
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) outfile << setw(8) << mat[i][j];
            outfile << "\n";
        }
    }

    // 3. 高斯消元
    int step = 2 + row_swaps;
    for(int col = 0; col < n-1; col++) {
        for(int row = col+1; row < n; row++) {
            if(fabs(mat[row][col]) < EPS) continue;
            
            // 尋找主元行（部分主元法：選絕對值最大行）
            int pivot_row = col;
            for(int r = col; r < n; r++)
                if(fabs(mat[r][col]) > fabs(mat[pivot_row][col]))
                    pivot_row = r;
            
            if(pivot_row != row) {
                swap(mat[row], mat[pivot_row]);
                row_swaps++;
            }

            double factor = mat[row][col] / mat[col][col];
            for(int c = col; c < n; c++) {
                mat[row][c] -= factor * mat[col][c];
                if(fabs(mat[row][c]) < EPS && row != c) mat[row][c] = 0;
            }

            outfile << "第" << ++step << "步：R" << row+1 << " - (" 
                    << fixed << setprecision(4) << factor << ") * R" << col+1 << ":\n";
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) outfile << setw(10) << mat[i][j];
                outfile << "\n";
            }
        }
    }

    // 4. 計算行列式
    double det = 1.0;
    for(int i = 0; i < n; i++) det *= mat[i][i];
    
    int total_swaps = row_swaps + col_swaps;
    if(total_swaps % 2) det = -det;

    outfile << "最終行列式值 = " << det << "\n";
    outfile.close();

    cout << "計算完成，結果見 output.txt\n";
    return 0;
}

關鍵改進點（對比原代碼）

數學驗證

對於 3×3 矩陣：

輸入:
2 1 3
1 2 1
3 1 2

行列式 = 2*(4-1) - 1*(2-3) + 3*(1-6) = 6 + 1 - 15 = -8

程式輸出應為 -8（或接近值）。

複雜度與數值穩定性

• 時間：O(n³)
• 空間：O(n²)
• 部分主元法大幅減少除以微小數導致的誤差放大
• 對於病態矩陣（如 Hilbert 矩陣），建議用 LU 分解或任意精度庫

總結

高斯消元法是行列式計算、線性方程組求解的基石。現代 C++ 實作應善用 STL 容器、演算法、RAII 資源管理，配合部分主元法保證數值穩定，產出可維護、高效、跨平台的數值計算程式碼。