Giả sử rằng tôi có một hình vuông matrixM
. Giả sử rằng tôi muốn invert ma trận M
.Đảo ngược ma trận nhanh mà không cần gói
Tôi đang cố gắng sử dụng các phân số mpq
lớp trong số gmpy2 làm thành viên của ma trận M
. Nếu bạn không quen thuộc với các phân số này, chúng có chức năng tương tự như gói được xây dựng sẵn của python fractions
. Vấn đề duy nhất là, không có gói nào sẽ đảo ngược ma trận của tôi trừ khi tôi lấy chúng ra khỏi dạng phân số. Tôi yêu cầu các số và câu trả lời ở dạng phân số. Vì vậy, tôi sẽ phải viết chức năng của riêng tôi để đảo ngược M
.
Có các thuật toán đã biết mà tôi có thể lập trình, chẳng hạn như gaussian elimination. Tuy nhiên, hiệu suất là một vấn đề, do đó, câu hỏi của tôi là như sau:
Có một thuật toán nhanh về tính toán mà tôi có thể sử dụng để tính toán nghịch đảo của ma trận M
?
Bất kỳ thuật toán nhanh hợp lý nào để thực hiện việc này sẽ _have_ được triển khai trong C, dưới dạng tiện ích mở rộng. Một cách tiếp cận khác là nhân tất cả chúng với GCD của họ, hoặc chỉ là sản phẩm của mẫu số của chúng, để tạo thành các số nguyên và sử dụng các gói có phần mở rộng C và nhiều thời gian hơn để tối ưu hóa. Đây là 'O (n)', do đó, trừ khi thuật toán đảo ngược tốt hơn 'O (n)', nó sẽ không làm tổn thương độ phức tạp của thời gian. – Artyer
Bạn đã nhìn vào sympy chưa? Nó hoạt động tốt với gmpy2 và ma trận: http://docs.sympy.org/dev/modules/matrices/matrices.html#linear-algebra – denfromufa
Có, nhưng sự đảo ngược của sympy chậm hơn so với việc mã hóa loại bỏ Gaussian bằng tay. Tôi có thể chia sẻ mã của tôi để loại bỏ gaussian với điểm chuẩn. –