Saya punya program yang menghitung nilai eigen terbesar dari banyak matriks simetris 50x50 nyata dengan melakukan dekomposisi nilai singular pada semuanya. SVD adalah hambatan dalam program ini.
Apakah ada algoritma yang jauh lebih cepat dalam menemukan nilai eigen terbesar, atau akan mengoptimalkan bagian ini tidak memberikan banyak pengembalian investasi?
Jawaban:
Bergantung pada presisi yang Anda butuhkan untuk nilai eigen terbesar, Anda bisa mencoba menggunakan Power Iteration .
Untuk contoh spesifik Anda, saya akan sejauh tidak membentuk secara eksplisit, tetapi menghitung x ← X ( X T x ) di setiap iterasi. Komputasi A akan membutuhkan operasi O ( n 3 ) sedangkan produk vektor-matriks hanya membutuhkanA=XXT x←X(XTx) A O(n3) .O(n2)
Tingkat konvergensi tergantung pada pemisahan antara dua nilai eigen terbesar, jadi ini mungkin bukan solusi yang baik dalam semua kasus,
sumber
Jika hanya 5 nilai eigen yang sangat signifikan, algoritma Lanczsos dengan sebagai perkalian matriks-vektor harus memberikan konvergensi linier cepat setelah 5 langkah awal, maka nilai eigen terbesar yang cukup akurat dengan sedikit iterasi.X(XTx)
sumber
Untuk matriks semi-pasti positif seperti mungkin perlu upaya untuk mempercepat konvergensi dengan pergeseran spektrum . Yaitu, skalar μ yang cocok dipilih dan metode daya diterapkan pada A - μ I alih-alih AA=XXT μ A−μI A .
Beberapa iterasi metode daya dasar harus memberi Anda perkiraan kasar dari nilai eigen terbesar λ 1 . Dengan asumsi nilai eigen dominan memiliki multiplisitas 1 dan semua yang lainnya berada dalam [ 0 , 5||Ax||/||x|| λ1 , laluA-5[0,56λ1] akan memiliki nilai eigen terbesar7A−512λ1I dan sisanya di[-5712λ1 .[−512λ1,512λ1]
Dengan kata lain Anda akan meningkatkan dominasi nilai eigen terbesar dari 20% di atas terbesar berikutnya menjadi 40% di atas nilai eigen terbesar berikutnya (nilai absolut dari suatu). Konvergensi geometrik dari metode daya akan mempercepat sesuai. Setelah nilai eigen terbesar dari ditemukan keakuratan yang cukup, λ 1 diperkirakan dengan menambahkan kembali shift μ yang telah diambil.A−μI λ1 μ
sumber