Hướng dẫn giải của Giá trị riêng của ma trận


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, hohoanghai5042011, lephuochauhungvuong, TP25_B044

Editorial for ptit039: Giá trị riêng của ma trận

Hiểu bài toán

Cho ma trận vuông A cấp N (2 ≤ N ≤ 10). Bài toán yêu cầu tính:

  1. Tổng các giá trị riêng (eigenvalues) của ma trận.
  2. Tích các giá trị riêng của ma trận. Dựa vào toán học:
  • Tổng các giá trị riêng bằng vết (trace) của ma trận, tức là tổng các phần tử trên đường chéo chính.
  • Tích các giá trị riêng bằng định thức (determinant) của ma trận. Vì N rất nhỏ (≤ 10), ta có thể tính định thức bằng phương pháp sơ cấp (Gauss hoán vị dòng) hoặc phương pháp định nghĩa (quy hoạch động), hoặc dùng công thức Row Holland (thuật toán Rybicki - Press cho ma trận nhỏ). Đề bài đảm bảo input và output là số thực trong khoảng tương thích.

Các cách tiếp cận

Cách Tính trực tiếp qua Trace và Determinant
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<vector<long double>> a(n, vector<long double>(n));
    long double trace = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            long long x;
            cin >> x;
            a[i][j] = x;
            if (i == j) trace += x;
        }
    }

    // Tính định thức bằng Gauss Elimination
    const long double EPS = 1e-12L;
    long double det = 1.0L;
    int sign = 1;

    for (int i = 0; i < n; ++i) {
        // Tìm pivot
        int piv = i;
        for (int j = i + 1; j < n; ++j) {
            if (fabsl(a[j][i]) > fabsl(a[piv][i])) piv = j;
        }

        if (fabsl(a[piv][i]) < EPS) {
            det = 0.0L;
            break;
        }

        if (piv != i) {
            swap(a[i], a[piv]);
            sign = -sign;
        }

        det *= a[i][i];

        for (int j = i + 1; j < n; ++j) {
            long double factor = a[j][i] / a[i][i];
            for (int k = i; k < n; ++k) {
                a[j][k] -= factor * a[i][k];
            }
        }
    }

    det *= sign;

    cout << fixed << setprecision(0) << trace << "\n" << det << "\n";
    return 0;
}
  • Time Complexity: O(N^3)
  • Space Complexity: O(N^2)

Đây là cách tiếp cận chuẩn và hiệu quả nhất cho N nhỏ.

  1. Tính tổng giá trị riêng (Trace): Duyệt qua các phần tử a[i][i] và cộng dồn.
  2. Tích giá trị riêng (Determinant): Sử dụng thuật toán Gauss Elimination để biến đổi ma trận về dạng tam giác trên. Tích các phần tử trên đường chéo chính sau khi biến đổi (và nhân với -1 nếu có hoán vị dòng) chính là định thức. Sử dụng long double để đảm bảo độ chính xác khi chia số nhỏ.
Cách Phương pháp định nghĩa (Recursive Determinant)
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

using Matrix = vector<vector<long double>>;

long double determinant(Matrix a, int n) {
    if (n == 1) return a[0][0];
    if (n == 2) return a[0][0] * a[1][1] - a[0][1] * a[1][0];

    long double det = 0;
    int sign = 1;
    // Mở rộng theo hàng đầu tiên
    for (int i = 0; i < n; ++i) {
        // Tạo ma trận con
        Matrix sub(n - 1, vector<long double>(n - 1));
        for (int r = 1; r < n; ++r) {
            int c_sub = 0;
            for (int c = 0; c < n; ++c) {
                if (c == i) continue;
                sub[r - 1][c_sub++] = a[r][c];
            }
        }
        det += sign * a[0][i] * determinant(sub, n - 1);
        sign = -sign;
    }
    return det;
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    Matrix a(n, vector<long double>(n));
    long double trace = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            long long x;
            cin >> x;
            a[i][j] = x;
            if (i == j) trace += x;
        }
    }

    long double det = determinant(a, n);
    // In output theo format yêu cầu (số nguyên nếu làm tròn)
    // Tuy nhiên input đảm bảo output là số thực, nhưng sample in số nguyên.
    // Ta dùng cout với precision 0 để in số tròn.
    cout << (long long)(trace + 0.5) << "\n" << (long long)(det + 0.5) << "\n";
    return 0;
}
  • Time Complexity: O(N!)
  • Space Complexity: O(N^2)

Dựa trên định nghĩa định thức: Det(A) = Σ (-1)^(i+j) * a[0][j] * Det(M_{0,j}). Phương pháp này đơn giản để hiểu nhưng rất chậm do số lượng phép toán tăng factorial. Với N=10, độ phức tạp ~3.6 triệu phép tính, vẫn chạy được nhưng chậm hơn Gauss nhiều. Cần lưu ý việc tạo ma trận con (sub-matrix) gây tốn bộ nhớ và thời gian sao chép.

Cách Sử dụng Row-Holland (Eigenvalues computation)
#include <iostream>
#include <vector>
#include <cmath>
#include <complex>
#include <iomanip>
using namespace std;

typedef complex<double> cd;

// Hàm tính giá trị riêng bằng QR Decomposition (tương tự Row-Holland)
// Sau đó tính tổng và tích
int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<vector<double>> a(n, vector<double>(n));
    double trace = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int x; cin >> x;
            a[i][j] = x;
            if (i == j) trace += x;
        }
    }

    // Biến đổi ma trận về dạng Hessenberg (tối ưu cho QR)
    // ...
    // (Code đầy đủ cho QR decomposition khá dài, thường dùng thư viện)
    // Trong contest nhỏ, dùng Trace và Det là đủ.
    // Dưới đây là minh họa logic nếu dùng thư viện Eigen (cấm trong CP)
    // Hoặc implement đơn giản:
    // Tính Det bằng Gauss (như approach 1)
    // Tính tổng bằng Trace

    // Giả lập output
    cout << (long long)trace << "\n"; 
    // Tính det... (gọi hàm det)
    return 0;
}
  • Time Complexity: O(N^3)
  • Space Complexity: O(N^2)

Approach này đề cập đến thuật toán tìm giá trị riêng thực sự (Real Eigenvalues) hoặc phức. Tuy nhiên, do bài toán chỉ yêu cầu TỔNG và TÍCH, ta không cần tìm từng giá trị riêng. Nếu bắt buộc phải tìm giá trị riêng (ví dụ để in ra từng cái), ta dùng thuật toán QR (QR Decomposition) lặp lại cho đến khi ma trận chéo hóa. Tuy nhiên, với bài toán này, Approach 1 là tối ưu nhất.

Phân tích độ phức tạp

Cách tiếp cận Time Space Tên
1 O(N^3) O(N^2) Tính trực tiếp qua Trace và Determinant
2 O(N!) O(N^2) Phương pháp định nghĩa (Recursive Determinant)
3 O(N^3) O(N^2) Sử dụng Row-Holland (Eigenvalues computation)

Bài học kinh nghiệm

  • Tổng các giá trị riêng (Eigenvalues) luôn bằng Vết (Trace) của ma trận: Σλi = Σaii. Đây là tính chất định lý (Cayley-Hamilton hoặc do tính chất của đa thức đặc trưng).
  • Tích các giá trị riêng luôn bằng Định thức (Determinant) của ma trận: Πλ_i = det(A).
  • Với N ≤ 10, ta không cần thuật toán tìm giá trị riêng phức tạp mà chỉ cần tính Trace và Det.

Lỗi thường gặp

  • Sai số dấu (Precision): Khi tính định thức bằng phép biến đổi Gauss, cần dùng kiểu dữ liệu double hoặc long double và có ngưỡng sai số (EPS) để so sánh số khác 0.
  • Tràn số nguyên: Mặc dù N nhỏ, nhưng tích các giá trị riêng có thể lớn. Nên dùng long long cho Trace (vì a[i][i] ≤ 5, N=10 => max 50) và long double cho Det.
  • Xử lý ma trận rỗng (Determinant = 0): Nếu tìm thấy cột toàn 0 ở bước Gauss, phải dừng và gán det = 0 ngay.

Bình luận

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.