Báo cáo trình bày 5 phương pháp lặp phổ biến để tìm trị riêng và vectơ riêng của ma trận. Đây là bài tập lớn môn Tính toán khoa học IT4110 - Đại học Bách khoa Hà Nội.
Theo lý thuyết, để tìm trị riêng của ma trận A, ta đi giải phương trình đặc trưng det(A - λI) = 0. Tuy nhiên, các ma trận trong thực tế có kích thước rất lớn, khiến việc tính định thức ma trận là không khả thi. Một vấn đề nữa là ta không có công thức nghiệm tổng quát để giải phương trình đa thức có bậc lớn hơn 4. Vì vậy, các phương pháp lặp tìm trị riêng, vector riêng được phát triển để giải quyết vấn đề này.
Báo cáo trình bày mã giả và code bằng python cho 5 phương pháp lặp sau:
- PP lặp lũy thừa: Tìm trị riêng trội nhất (có độ lớn lớn nhất).
- PP lặp nghịch đảo (kết hợp dịch chuyển): Tìm trị riêng gần một giá trị µ cho trước.
- PP lặp tỉ số Rayleigh (RQI): Kết hợp lặp nghịch đảo với cập nhật dịch chuyển tại mỗi bước sử dụng tỉ số Rayleigh.
- PP lặp đồng thời: Tìm nhiều trị riêng cùng lúc bằng cách sử dụng phân rã QR.
- Thuật toán QR: Thuật toán mạnh nhất để tìm toàn bộ các trị riêng của ma trận.
Dựa trên thử nghiệm với các ma trận đối xứng ngẫu nhiên, nhóm rút ra các nhận xét:
- Độ chính xác: Thuật toán QR và PP lặp đồng thời cho kết quả với sai số nhỏ (<1e-6).
- Tốc độ hội tụ: RQI hội tụ nhanh nhất, thường dưới 10 bước lặp. PP Lặp lũy thừa có thể hội tụ chậm nếu các trị riêng có độ lớn xấp xỉ nhau.
- Ứng dụng thực tế: Thuật toán PageRank của Google, phân tích thành phần chính PCA và nhận dạng khuôn mặt.
Yêu cầu hệ thống
- Python 3.x
- Thư viện: numpy, pandas
Chạy chương trình
- Sao chép repository này về máy.
- Cài đặt thư viện bổ trợ: pip install numpy pandas.
- Chạy file mã nguồn để xem kết quả thử nghiệm so sánh với hàm numpy.linalg.eig chuẩn.
M. Panju, “Iterative methods for computing eigenvalues and eigenvectors,” The Waterloo Mathematics Review, 2011.