Diberikan matriks jarang generik dengan m << n (koreksi: ) elemen tidak nol (biasanya ). adalah generik dalam arti bahwa ia tidak memiliki sifat spesifik (misalnya kepastian positif), dan tidak ada struktur (misalnya pita) yang diasumsikan.
Apa saja metode numerik yang baik untuk menghitung polinomial karakteristik atau polinomial minimal ?
Jawaban:
Jika kompleksitas bukan merupakan penghenti maka Anda mungkin ingin melihat metode Danilevskii. Ini cukup terkenal dalam literatur Rusia tentang aljabar linear numerik, tetapi tidak ada banyak informasi dalam bahasa Inggris. Anda bisa mulai dari tautan ini .O(n3)
Idenya agak langsung: matriks secara bertahap dikurangi menjadi bentuk normal Frobenius oleh "mirip Gaussian eliminasi-like" transformasi. Jika Anda tidak menemukan informasi tersebut, saya dapat membuat algoritme lebih rumit.
sumber
Anda bisa menggunakan metode numerik seperti QR Factorization atau Power Method dan realistisnya (daya terbalik dll) untuk menghitung nilai eigen dari matriks generik Anda. Setelah itu, Anda dapat menghitung polinomial karakteristik Anda dengan faktorisasi sebagai: (λ-λ1) (λ-λ2) ... (λ-λn) = 0 di mana λi adalah nilai eigen yang dikomputasi. Berikut adalah presentasi singkat tentang kekuatan dan metode QR:
QR-Power
sumber
Ngomong-ngomong: Apakah Anda ingin mengatakan bahwa Anda memiliki entri ? Jika memang maka mayoritas baris dan kolom akan benar-benar kosong dan ada kemungkinan bahwa polinomial karakteristik sebenarnya bukan derajat tetapi derajat .m≪O(n2) m≪O(n) n O(m)
sumber