Apa sajakah aplikasi yang membutuhkan aritmatika interval?

Saya memiliki gagasan yang sangat mendasar tentang interval aritmatika (IA), tetapi tampaknya menjadi cabang ilmu komputasi yang sangat menarik baik secara teoritis maupun praktis. Jelas bahwa aplikasi yang jelas adalah komputasi terverifikasi dan masalah yang keliru, tetapi ini terlalu abstrak. Karena ada banyak orang yang terlibat dalam perhitungan terapan di sini, saya ingin tahu tentang masalah dunia nyata yang sulit atau tidak mungkin diselesaikan tanpa IA .

Jawaban ini sebagian menanggapi komentar JackPoulson (karena panjang), dan sebagian lagi menjawab pertanyaan.

Aritmatika interval adalah prosedur komputasi untuk memberikan batasan yang ketat pada jumlah yang dihitung, hanya dalam arti bahwa ekstensi interval dari fungsi bernilai nyata pada suatu interval membungkus gambar fungsi tersebut pada interval yang sama. Tanpa menghitung apa pun, aritmatika interval tidak dapat memberi Anda wawasan apa pun tentang faktor-faktor apa yang memengaruhi kesalahan numerik dalam suatu perhitungan, sedangkan teorema dalam buku Higham dan yang lain memberi Anda wawasan tentang faktor-faktor yang memengaruhi kesalahan numerik, dengan mengorbankan kemungkinan batas yang lemah. Memang, batas-batas yang diperoleh dengan menggunakan aritmatika interval mungkin juga lemah, karena masalah ketergantungan yang disebut , tetapi kadang-kadang mereka jauh lebih kuat. Misalnya, batas interval yang diperoleh menggunakan paket integrasi COZY Infinityjauh lebih ketat daripada jenis batas kesalahan yang akan Anda dapatkan pada integrasi numerik dari hasil Dahlquist (lihat Hairer, Wanner, dan Nørsett untuk detailnya); hasil ini (saya secara khusus merujuk pada Teorema 10.2 dan 10.6 di Bagian I) memberikan lebih banyak wawasan tentang sumber kesalahan, tetapi batasannya lemah, sedangkan batasan menggunakan COZY bisa ketat. (Mereka menggunakan beberapa trik untuk mengurangi masalah ketergantungan.)

Saya ragu-ragu untuk menggunakan kata "bukti" ketika menggambarkan apa interval aritmatika tidak. Ada bukti yang melibatkan aritmatika interval, tetapi hasil perhitungan menggunakan aritmatika interval dengan pembulatan ke luar benar-benar hanya alat pembukuan untuk secara konservatif mengikat rentang fungsi. Perhitungan aritmatika interval bukan bukti; mereka adalah cara untuk menyebarkan ketidakpastian.

Sejauh aplikasi berjalan, selain pekerjaan Stadtherr di bidang teknik kimia, interval aritmatika juga telah digunakan untuk menghitung batas untuk eksperimen berkas partikel (lihat karya Makino dan Berz, terkait dengan situs web COZY Infinity), mereka telah digunakan dalam optimasi global dan aplikasi desain teknik kimia (antara lain) oleh Barton (tautannya adalah ke daftar publikasi), desain pesawat ruang angkasa dan optimasi global (antara lain) oleh Neumaier (sekali lagi, tautannya adalah daftar publikasi ), optimisasi global dan pemecah persamaan nonlinier oleh Kearfott (daftar publikasi lain), dan untuk kuantifikasi ketidakpastian (berbagai sumber; Barton adalah salah satunya).

Akhirnya, penafian: Barton adalah salah satu penasihat tesis saya.

Aritmatika interval memberi Anda bukti dengan ketelitian matematika.

Contoh bagus dari aplikasi aktual adalah karya Mark Stadtherr dan grup risetnya. Secara khusus, keseimbangan fase dan perhitungan stabilitas berhasil diselesaikan dengan metode interval.

Kumpulan tolok ukur yang bagus, dengan mengacu pada latar belakang fisik mereka, ada di situs web ALIAS .

Fitur lain dari aritmatika interval dan generalisasi adalah bahwa ia memungkinkan eksplorasi adaptif domain fungsi. Dengan demikian dapat digunakan untuk pemodelan geometris adaptif, pemrosesan, dan rendering, hanya untuk mengambil contoh dari grafik komputer.

Metode interval telah ditampilkan dalam beberapa bukti terbaru dari teorema matematika keras seperti adanya kekacauan di penarik Lorenz dan Kepler Conjecture. Lihat http://www.cs.utep.edu/interval-comp/kearfottPopular.pdf untuk ini dan aplikasi lainnya.

Interval arithmetics sangat berguna untuk algoritma geometrik. Algoritma geometris seperti itu mengambil sebagai input seperangkat objek geometris (misalnya seperangkat titik) dan membangun struktur data kombinatorial (misalnya triangulasi) berdasarkan hubungan spasial antara titik-titik tersebut. Algoritma ini bergantung pada sejumlah kecil fungsi, yang disebut 'predikat', yang mengambil input sejumlah objek geometri dan mengembalikan nilai diskrit (biasanya salah satu dari 'di atas, disejajarkan, di bawah'). Predikat tersebut biasanya sesuai dengan tanda penentu koordinat titik.

Menggunakan angka floating-point standar tidak cukup, karena mungkin gagal menghitung secara akurat tanda determinan, dan bahkan lebih buruk, mengembalikan hasil yang tidak jelas (yaitu, mengatakan bahwa A di atas B dan B di atas A, sehingga membuat algoritma membuat berantakan bukannya jala!). Secara sistematis menggunakan multi-presisi (seperti di perpustakaan Multi-Precision Gnu dan ekstensi MPFR ke angka floating point multi-presisi) bekerja tetapi menyebabkan penalti kinerja yang signifikan. Ketika predikat geometri adalah tanda dari sesuatu (seperti dalam kebanyakan kasus), menggunakan interval arithmetics memungkinkan seseorang untuk melakukan perhitungan yang lebih cepat, dan kemudian hanya meluncurkan perhitungan multi-presisi yang lebih luas jika nol berada dalam interval.

Pendekatan semacam itu digunakan dalam beberapa kode geometri komputasi yang besar (misalnya CGAL).