Saya telah menggunakan metode yang berbeda untuk menghitung peringkat matriks dan solusi sistem persamaan matriks. Saya menemukan fungsi linalg.svd. Membandingkan ini dengan upaya saya sendiri untuk memecahkan sistem dengan Gaussian Elimination, tampaknya lebih cepat dan lebih tepat. Saya mencoba memahami bagaimana ini mungkin.
Sejauh yang saya tahu, fungsi linalg.svd menggunakan algoritma QR untuk menghitung nilai eigen dari matriks saya. Saya tahu bagaimana ini bekerja secara matematis, tetapi saya tidak tahu bagaimana Numpy berhasil melakukannya dengan cepat dan tanpa kehilangan banyak presisi.
Jadi pertanyaan saya: Bagaimana fungsi numpy.svd bekerja, dan lebih khusus lagi, bagaimana ia berhasil melakukannya dengan cepat dan akurat (dibandingkan dengan eliminasi gaussian)?
sumber
dgesdd
untuk SVD bernilai nyata. Jadi pertanyaan Anda yang sebenarnya mungkin adalah "bagaimana cara kerja Lapack dgesdd?", Dan itu cukup banyak topik untuk stackoverflow.Jawaban:
Ada sejumlah masalah dalam pertanyaan Anda.
Jangan gunakan Eliminasi Gaussian (faktorisasi LU) untuk menghitung peringkat numerik dari sebuah matriks. Faktorisasi LU tidak dapat diandalkan untuk tujuan ini dalam aritmatika titik-mengambang. Sebagai gantinya, gunakan dekomposisi QR yang mengungkapkan peringkat (seperti
xGEQPX
atauxGEPQY
di LAPACK, di mana x adalah C, D, S, atau Z, meskipun rutinitas tersebut sulit dilacak; lihat jawaban JedBrown pada pertanyaan terkait ), atau gunakan SVD (dekomposisi nilai singular, sepertixGESDD
atauxGESVD
, di mana x lagi C, D, S, atau Z). SVD adalah algoritma yang lebih akurat dan andal untuk penentuan peringkat numerik, tetapi membutuhkan lebih banyak operasi floating-point.Namun, untuk menyelesaikan sistem linier, faktorisasi LU (dengan pivoting parsial, yang merupakan implementasi standar dalam LAPACK) dalam praktiknya sangat andal. Ada beberapa kasus patologis yang faktorisasi LU dengan pivoting parsial tidak stabil (lihat Kuliah 22 dalam Aljabar Linier Numerik)oleh Trefethen dan Bau untuk detail). Faktorisasi QR adalah algoritme numerik yang lebih stabil untuk menyelesaikan sistem linier, yang mungkin itulah sebabnya ia memberi Anda hasil yang presisi. Namun, itu membutuhkan lebih banyak operasi floating-point daripada faktorisasi LU dengan faktor 2 untuk matriks kuadrat (saya percaya; JackPoulson dapat memperbaiki saya dalam hal itu). Untuk sistem persegi panjang, faktorisasi QR adalah pilihan yang lebih baik karena akan menghasilkan solusi kuadrat-terkecil untuk sistem linier yang ditentukan secara berlebihan. SVD juga dapat digunakan untuk menyelesaikan sistem linear, tetapi akan lebih mahal daripada faktorisasi QR.
janneb benar bahwa numpy.linalg.svd adalah pembungkus
xGESDD
di LAPACK. Dekomposisi nilai singular diproses dalam dua tahap. Pertama, matriks yang akan diurai dikurangi menjadi bentuk bidiagonal. Algoritma yang digunakan untuk mereduksi menjadi bentuk bidiagonal di LAPACK mungkin adalah algoritma Lawson-Hanson-Chan, dan memang menggunakan faktorisasi QR pada satu titik. Kuliah 31 dalam Aljabar Linier Numerik oleh Trefethen dan Bau memberikan ikhtisar proses ini. Kemudian,xGESDD
gunakan algoritma divide-and-conquer untuk menghitung nilai singular dan vektor singular kiri dan kanan dari matriks bidiagonal. Untuk mendapatkan latar belakang pada langkah ini, Anda harus berkonsultasi dengan Komputasi Matriks oleh Golub dan Van Loan, atau Aljabar Linear Numerik Terapan oleh Jim Demmel.Akhirnya, Anda tidak harus mengacaukan nilai singular dengan nilai eigen . Dua set jumlah ini tidak sama. SVD menghitung nilai singular dari sebuah matriks. Komputasi Numerik Cleve Moler dengan MATLAB memberikan gambaran yang bagus tentang perbedaan antara nilai singular dan nilai eigen . Secara umum, tidak ada hubungan yang jelas antara nilai singular dari matriks yang diberikan dan nilai eigennya, kecuali dalam kasus matriks normal , di mana nilai singular adalah nilai absolut dari nilai eigen.
sumber
rank
fungsinya). Ada juga sedikit keleluasaan yang terlibat ketika menggunakan salah satu pendekatan; dalam pendekatan SVD, peringkat numerik adalah jumlah nilai singular di atas batas tertentu (biasanya sangat kecil). (Pendekatan QR serupa, tetapi menggantikan nilai singular dengan entri diagonal dari matriks R.)Karena kata-kata dari pertanyaan Anda, saya mengasumsikan bahwa matriks Anda adalah persegi. Rutinitas SVD LAPACK, seperti zgesvd , pada dasarnya melanjutkan dalam tiga tahap untuk matriks persegi:
sumber
numpy.linalg.svd adalah pembungkus sekitar {Z, D} GESDD dari LAPACK. LAPACK, pada gilirannya, sangat hati-hati ditulis oleh beberapa pakar terkemuka dunia dalam aljabar linear numerik. Memang, akan sangat mengejutkan jika seseorang yang tidak akrab dengan bidang itu akan berhasil mengalahkan LAPACK (baik dalam kecepatan atau akurasi).
Adapun mengapa QR lebih baik daripada eliminasi Gaussian, itu mungkin lebih cocok untuk /scicomp//
sumber