Bagaimana cara memperkirakan angka kondisi dari matriks besar?

9

Bagaimana cara memperkirakan angka kondisi dari matriks G , jika G adalah kombinasi transformasi Fourier F (tidak seragam atau seragam), beda hingga R , dan matriks diagonal S ?

Matriksnya sangat besar dan tidak disimpan dalam memori dan hanya tersedia sebagai fungsi.

Secara khusus, saya memiliki matriks berikut:

Gμ=SHFHFS+μRHR

Saya ingin menyelidiki hubungan antara dan nomor kondisi k ( G μ ) .μk(Gμ)

Saya menganggap seseorang perlu semacam pendekatan berulang? Secara optimal akan ada beberapa kode MATLAB yang tersedia.

Stiefel
sumber
1
Bagaimana kalau mencoba dengan definisi nomor kondisi dan menggunakan ketimpangan segitiga dan submultiplicativity? Saya kira Anda harus bisa mengatakan sesuatu tentang norma / kondisi masing-masing matriks Anda. Dengan cara ini Anda mendapatkan perkiraan jumlah kondisi . Gμ
Anke

Jawaban:

11

MATLAB memiliki beberapa fungsi "tepat" untuk ini, conddan rcond, dengan yang terakhir mengembalikan kebalikan dari nomor kondisi. Fungsi perkiraan Matlab condestlebih lengkap dijelaskan di bawah ini.

Seringkali perkiraan jumlah kondisi dihasilkan sebagai produk sampingan dari solusi sistem linear untuk matriks, sehingga Anda mungkin dapat mendukung perkiraan jumlah kondisi pada pekerjaan lain yang perlu Anda lakukan pula. Lihat di sini untuk deskripsi singkat tentang bagaimana estimasi dihitung. Juga dokumentasi Sandia Labs AztecOO pernyataan (lihat Sec. 3.1) yang opsional jumlah kondisi perkiraan yang tersedia dari pemecah berulang (menggunakan dihasilkan tridiagonal Lanczos matriks dengan Conjugate Gradien atau dihasilkan matriks Hessenburg dengan ulang GMRES).

Karena matriks Anda "sangat besar" dan "hanya tersedia sebagai fungsi", pendekatan logis akan menjadi metode yang membonceng pada pemecah atau varian konjugasi gradien.

Sebuah makalah arXiv.org baru -baru ini. Perkiraan nilai eigen ekstrem non-stasioner dalam solusi iteratif sistem linier dan estimator untuk kesalahan relatif mengusulkan pendekatan semacam itu dan memiliki beberapa kutipan pada literatur sebelumnya.

Sekarang setelah saya melihat, forum ini memiliki sejumlah Pertanyaan sebelumnya yang berkaitan erat (tidak semua dengan Jawaban, tetapi periksa Komentar):

Perkirakan nilai eigen ekstrem dengan CG

Perkiraan angka kondisi untuk matriks yang sangat besar

Algoritma tercepat untuk menghitung nomor kondisi dari matriks besar di Matlab / Oktaf


condestA 1A - 11A1A11A1A11

Karena matriks Anda tampaknya Hermitian dan pasti positif, mungkin angka kondisi 2-norma lebih menarik. Masalahnya kemudian memperkirakan rasio nilai eigen terbesar (terkecil). Tantangannya agak paralel dengan kasus 1-norma di mana umumnya estimasi yang baik untuk nilai eigen terbesar dapat dengan mudah diperoleh, tetapi memperkirakan nilai eigen terkecil terbukti lebih sulit.

Meskipun ditujukan pada kasus-kasus non-SPD (dan bahkan non-kuadrat), makalah arXiv.org baru-baru ini, Estimasi Angka Kondisi Iteratif yang Dapat Diandalkan , memberikan tinjauan yang baik tentang masalah estimasi nilai eigen terkecil dan garis serangan yang menjanjikan oleh subruang Krylov metode (LSQR) yang berjumlah Konjugat Gradien dalam kasus SPD.

hardmath
sumber
Terima kasih atas jawaban Anda. Bagaimana cara mendapatkan nomor kondisi sebagai produk samping dari pemecah gradien konjugat?
Stiefel
@Stiefel: Ada makalah tahun 1992 Tentang perkiraan nilai eigen ekstrem dan jumlah kondisi matriks nonsingular oleh Lei Guang-yao. Biarkan saya melihat apakah saya dapat menemukan referensi yang lebih baik (bukan di balik dinding bayar).
hardmath
@Stiefel: Menambahkan beberapa tautan. Anda juga mungkin tertarik untuk memeriksa Buku Google (atau perpustakaan) untuk Metode Solusi Iteratif Owe Axelsson (1996), esp. Bab. 13 Tingkat Konvergensi Metode Gradient Konjugat , meskipun penekanannya ada pada mendapatkan estimasi yang lebih baik dari jumlah iterasi yang diperlukan untuk konvergensi daripada jumlah kondisi yang disediakan.
hardmath
1
@Stiefel Dengan nama seperti milik Anda, Anda harus mengajari kami tentang metode CG :) Lihat en.wikipedia.org/wiki/Eduard_Stiefel
stali