Kapan transformasi ortogonal mengungguli eliminasi Gaussian?

Seperti yang kita ketahui, metode transformasi ortogonal (rotasi Givens dan pantulan rumah tangga) untuk sistem persamaan linear lebih mahal daripada eliminasi Gaussian, tetapi secara teoritis memiliki sifat stabilitas yang lebih baik dalam arti bahwa mereka tidak mengubah nomor kondisi sistem. Meskipun saya tahu hanya satu contoh akademik dari sebuah matriks yang dimanjakan oleh eliminasi Gaussian dengan pivoting parsial. Dan ada pendapat umum bahwa sangat tidak mungkin untuk memenuhi perilaku seperti ini dalam praktiknya (lihat catatan kuliah ini [pdf] ).

Jadi, kemana kita mencari jawaban untuk topik itu? Implementasi paralel? Memperbarui? ..

Ketepatan

Trefethen dan Schreiber menulis makalah yang sangat bagus, Stabilitas Kasus Rata-Rata Penghapusan Gaussian , yang membahas sisi akurasi pertanyaan Anda. Berikut adalah beberapa kesimpulannya:

1. "Untuk faktorisasi QR dengan atau tanpa pivoting kolom, elemen maksimal rata-rata dari matriks residual adalah , sedangkan untuk eliminasi Gaussian adalah . Perbandingan ini menunjukkan bahwa eliminasi Gaussian agak tidak stabil. , tetapi ketidakstabilan hanya akan terdeteksi untuk masalah matriks yang sangat besar diselesaikan dengan presisi rendah. Untuk sebagian besar masalah praktis, rata-rata eliminasi Gaussian sangat stabil. "(Penekanan tambang)O ( n $O(n^{1/2})$$O(n)$

2. "Setelah beberapa langkah pertama eliminasi Gaussian, elemen matriks yang tersisa terdistribusi secara normal, terlepas dari apakah mereka memulai dengan cara itu."

Ada banyak hal lain yang tidak dapat saya tangkap di sini, termasuk diskusi tentang matriks terburuk yang Anda sebutkan, jadi saya sangat menyarankan Anda membacanya.

Performa

Untuk matriks nyata persegi, LU dengan pivot parsial membutuhkan sekitar jepit, sedangkan QR berbasis rumah tangga membutuhkan sekitar jepit. Jadi, untuk matriks persegi yang cukup besar, faktorisasi QR hanya akan sekitar dua kali lebih mahal dari faktorisasi LU. 4 / 3 n $2/3 n^3$$4/3 n^3$

Untuk matriks, di mana , LU dengan pivot parsial membutuhkan 3/3 jepit, dibandingkan dengan QR (yang masih dua kali lipat dari faktorisasi LU) . Namun , sangat umum untuk aplikasi menghasilkan matriks kurus sangat tinggi ( ), dan Demmel et al. memiliki kertas yang bagus, faktorisasi QR paralel dan sekuensial yang menghindari Komunikasi , yang (dalam bagian 4) membahas algoritme pintar yang hanya memerlukan pesan untuk dikirim ketika prosesor digunakan, dibandingkan pesan dari pendekatan tradisional . Biayanya adalah itum ≥ n m n 2 - n 3 / 3 2 m n 2 - 2 n 3 / 3 m » n log p p n log p O ( n 3 log p ) $m \times n$$m \ge n$$mn^2 - n^3/3$$2mn^2 - 2n^3/3$$m \gg n$$\log p$$p$$n \log p$$O(n^3 \log p)$ ekstra jepit dilakukan, tetapi untuk sangat kecil ini sering lebih disukai daripada biaya latensi mengirim lebih banyak pesan (setidaknya ketika hanya satu faktorisasi QR yang perlu dilakukan).$n$

Saya terkejut tidak ada yang disebutkan masalah linear kuadrat terkecil , yang sering terjadi dalam komputasi ilmiah. Jika Anda ingin menggunakan eliminasi Gaussian, Anda harus membentuk dan menyelesaikan persamaan normal, yang terlihat seperti:

di mana adalah matriks titik data yang sesuai dengan pengamatan variabel independen, adalah vektor parameter yang akan ditemukan, dan adalah vektor titik data yang sesuai dengan pengamatan variabel dependen.x $A$$x$$b$

Seperti yang sering ditunjukkan oleh Jack Poulson, angka kondisi adalah kuadrat dari angka kondisi , sehingga persamaan normal dapat sangat buruk kondisinya. Dalam kasus seperti itu, meskipun pendekatan berbasis QR dan SVD lebih lambat, mereka menghasilkan hasil yang jauh lebih akurat.$A^{T}A$$A$

Bagaimana Anda mengukur kinerja? Kecepatan? Ketepatan? Stabilitas? Tes cepat di Matlab memberikan yang berikut:

>> N = 100;
>> A = randn(N); b = randn(N,1);
>> tic, for k=1:10000, [L,U,p] = lu(A,'vector'); x = U\(L\b(p)); end; norm(A*x-b), toc
ans =
   1.4303e-13
Elapsed time is 2.232487 seconds.
>> tic, for k=1:10000, [Q,R] = qr(A); x = R\(Q'*b); end; norm(A*x-b), toc             
ans =
   5.0311e-14
Elapsed time is 7.563242 seconds.

Jadi menyelesaikan satu sistem dengan dekomposisi LU sekitar tiga kali lebih cepat menyelesaikannya dengan dekomposisi QR, dengan mengorbankan setengah digit desimal akurasi (contoh ini!).

Artikel yang Anda kutip membela Penghapusan Gaussian dengan mengatakan bahwa meskipun secara numerik tidak stabil, ia cenderung bekerja dengan baik pada matriks acak dan karena sebagian besar matriks dapat dipikirkan seperti matriks acak, kita harus baik-baik saja. Pernyataan yang sama dapat dikatakan tentang banyak metode yang tidak stabil secara numerik.

Pertimbangkan ruang semua matriks. Metode ini bekerja dengan baik hampir di mana-mana. Itu adalah 99,999 ...% dari semua matriks yang dapat dibuat tidak memiliki masalah dengan metode yang tidak stabil. Hanya ada sebagian kecil dari matriks yang GE dan orang lain akan mengalami kesulitan.

Masalah yang peneliti pedulikan cenderung di fraksi kecil itu.

Kami tidak membuat matriks secara acak. Kami membuat matriks dengan properti yang sangat spesial yang sesuai dengan sistem non-acak yang sangat spesial. Matriks ini sering dikondisikan dengan buruk.

Secara geometris Anda dapat mempertimbangkan ruang linear semua matriks. Ada nol volume / ukuran subruang dari matriks singular memotong ruang ini. Banyak masalah yang kami buat berkerumun di sekitar subruang ini. Mereka tidak didistribusikan secara acak.

Sebagai contoh perhatikan persamaan atau dispersi panas. Sistem ini cenderung untuk menghapus informasi dari sistem (semua keadaan awal condong ke keadaan final tunggal) dan akibatnya matriks yang menggambarkan persamaan ini sangat singular. Proses ini sangat tidak mungkin dalam situasi acak namun ada di mana-mana dalam sistem fisik.