Pemeriksaan heuristik stabilitas numerik

12

Asumsikan saya memiliki fungsi bernilai nyata dari beberapa variabel x_i yang ingin saya evaluasi secara numerik. Secara umum rumus untuk f dapat mengandung produk, rasional, fungsi trancendental dll. Dan akan lama untuk menyelidiki stabilitas numerik secara analitik. Atau setidaknya akan memakan waktu untuk melakukannya dalam praktik. Asumsikan saya tidak memiliki padanan yang lebih pendek dengan stabilitas guaruanteed. Apakah ada prosedur metodis untuk menganalisis stabilitas numerik fx i f ff(x1,,xN)xiff. Saya pikir membandingkannya dengan hasil precisioning sewenang-wenang yang diperoleh menggunakan sistem aljabar komputer. Katakanlah fungsi akan diimplementasikan dalam C menggunakan fungsi stdlib dan presisi tunggal atau ganda. Kuantitas mana yang harus saya bandingkan untuk mengukur kualitas perkiraan pada saat terbatas? Bagaimana cara menentukan nilai kritis dari variabel? Bagaimana saya bisa memilih kompiler dan optimisasi kompiler sehingga orang lain dapat dengan mudah mereproduksi hasilnya? ... Saya tahu bahwa pengaturan masalah mungkin adalah generik untuk memberikan jawaban yang baik. Tetapi saya masih berpikir bahwa ini adalah masalah umum dalam ilmu komputer dan bertanya-tanya apakah ada referensi yang mengusulkan standar untuk melakukan analisis tersebut.

kelas tinggi
sumber

Jawaban:

7

Apa yang Anda cari adalah apa yang disebut "Analisis kesalahan otomatis" dan merupakan subjek Bab 26 buku Higham "Akurasi dan Stabilitas Algoritma Angka", edisi ke-2, Penerbit SIAM.

Salah satu teknik yang ia jelaskan adalah menggunakan optimasi pencarian langsung: cobalah untuk merumuskan masalah Anda sebagai masalah optimasi dan menggunakan algoritma optimasi untuk menemukan koefisien atau nilai parameter yang memaksimalkan atau meminimalkan kuantitas yang terkait dengan akurasi algoritma / formula Anda. Dia menggunakan contoh faktor pertumbuhan dalam Eliminasi Gaussian (matriks apa yang memaksimalkan faktor pertumbuhan ini) atau akar kubik (seperti yang saya jawab dalam salah satu pertanyaan Anda sebelumnya).

Saya sarankan agar Anda memperoleh salinan buku ini, membaca bab pengantar dan bab ini 26 dan referensi di dalamnya.

GertVdE
sumber
3

Evaluasi fungsi Anda beberapa kali (3 biasanya cukup) dengan semua input sedikit terganggu secara acak oleh ulp. Deviasi standar dari ketiga hasil akan memberi Anda ukuran sensitivitas numerik kasar (tetapi biasanya cukup). Anda dapat membandingkan ini dengan sensitivitas yang diharapkan dari linierisasi, dan membentuk hasil bagi untuk mendapatkan perkiraan stabilitas.±1

Perhatikan bahwa stabilitas numerik menanyakan seberapa besar kesalahan aktual pada evaluasi tertentu dibandingkan dengan kesalahan yang diharapkan dari analisis sensitivitas ketika mengubah input dengan ulp; kesalahan terakhir yang dinyatakan dalam ulp menentukan kondisi masalah. Kondisi dapat menjadi sangat buruk untuk algoritma yang stabil (contoh: dekat ) dan stabilitas dapat menjadi buruk untuk fungsi yang sangat terkondisi (contoh: dekat ).± 1 1 / x x = 0 1 / ( 1 - x ) - 1 / ( 1 + x ) x = 0x±11/xx=01/(1x)1/(1+x)x=0

Arnold Neumaier
sumber
0

|f(x+ε)f(x)|C|ε|
Cfx,ϵ
Wolfgang Bangerth
sumber
Dan apa yang dapat dilakukan jika fungsinya bervariasi secara liar pada domainnya atau jika tidak ada turunan yang layak tersedia? Apakah ada teknik lain atau kita akan berakhir dengan pendekatan Monte Carlo?
André
1
-1: Anda menjelaskan pengertian kondisi, bukan stabilitas numerik.
Arnold Neumaier