Trực chuẩn hóa Gram-Schmidt cải tiến (Modified Gram-Schmidt) và phân rã QR

Mục tiêu kiến thức

• Hiểu quá trình trực giao hóa và trực chuẩn hóa các vector cột.
• Phân biệt Classical Gram-Schmidt (CGS) dễ mất tính trực giao do sai số làm tròn số thực và Modified Gram-Schmidt (MGS) có tính ổn định số học cao.
• Phân rã ma trận A = Q · R trong đó Q là ma trận trực chuẩn (Q^T Q = I_N) và R là ma trận tam giác trên.

Mô tả bài toán

Viết hàm qr_gram_schmidt(A: np.ndarray) -> tuple[np.ndarray, np.ndarray]:

• A: Ma trận thực kích thước (M, N) với M ≥ N.
• Kiểm tra tính hợp lệ:
• Nếu M < N hoặc len(A) == 0, raise ValueError("Ma tran phai co so hang lon hon hoac bang so cot").
• Khởi tạo:
• Ma trận Q kích thước (M, N) khởi tạo từ bản sao của A.
• Ma trận R kích thước (N, N) khởi tạo toàn số 0.
• Thuật toán Modified Gram-Schmidt (MGS):
• Với mỗi cột i = 0, 1, …, N-1:
• Tính độ dài chuẩn cột: R[i, i] = |Q[:, i]|₂ = √(∑_r=0^M-1 Q[r, i]²).
• Nếu R[i, i] < 10^-12, cột phụ thuộc tuyến tính, gán Q[:, i] = 0.
• Ngược lại: chuẩn hóa Q[:, i] = Q[:, i]R[i, i].
• Với từng cột còn lại j = i + 1, …, N-1:
• Chiếu: R[i, j] = Q[:, i]^T · Q[:, j].
• Trừ hình chiếu trực tiếp (ngay lập tức cập nhật Q[:, j]):

Q[:, j] = Q[:, j] - R[i, j] · Q[:, i].

• Trả về (Q, R).

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.