Bagaimana seseorang menguji implementasi pemecah ODE numerik?

26

Saya akan mulai bekerja di perpustakaan perangkat lunak pemecah ODE numerik , dan saya berjuang dengan cara merumuskan tes untuk implementasi pemecah. Ambisi saya adalah bahwa perpustakaan, akhirnya, akan mencakup pemecah untuk kedua masalah nonstiff dan kaku, dan setidaknya satu pemecah implisit (kurang lebih setara dengan kemampuan yang oderutin di Matlab ), sehingga kebutuhan metodologi tes untuk mencerminkan berbagai jenis masalah dan kriteria untuk pemecah yang berbeda.

Masalah saya sekarang adalah bahwa saya tidak tahu harus mulai dari mana dengan pengujian ini. Saya dapat memikirkan beberapa cara berbeda untuk menguji output suatu algoritma:

  • Tes untuk masalah yang memiliki solusi analitis, dan periksa bahwa solusi numerik berada dalam level toleransi untuk semua titik data yang dikembalikan. Ini membutuhkan pengetahuan tentang sejumlah masalah analitis yang menunjukkan semua sifat yang saya inginkan untuk diselesaikan oleh berbagai solver (kekakuan, masalah implisit, dll.), Yang tidak saya miliki, setidaknya tidak lepas dari pikiran saya.

    Metode ini menguji hasil metode solver. Jadi, tidak ada jaminan bahwa solver benar-benar berfungsi, hanya saja ia berfungsi untuk masalah tes yang diberikan . Oleh karena itu, saya menduga sejumlah besar masalah tes diperlukan untuk memastikan bahwa pemecah berhasil.

  • Secara manual menghitung solusi untuk beberapa langkah waktu menggunakan algoritma yang ingin saya terapkan, dan kemudian melakukan hal yang sama dengan solver dan memeriksa hasilnya hasilnya sama. Ini tidak memerlukan pengetahuan tentang solusi yang sebenarnya untuk masalah tersebut, tetapi pada gilirannya membutuhkan banyak pekerjaan langsung.

    Metode ini, di sisi lain, hanya menguji algoritme , yang baik bagi saya - jika orang lain telah membuktikan bahwa urutan ke- 4 Runge-Kutta berfungsi, saya tidak merasa perlu untuk melakukannya. Namun, saya khawatir bahwa akan sangat merepotkan untuk merumuskan kasus uji, karena saya tidak tahu metode yang baik untuk menghasilkan data uji (kecuali mungkin dengan tangan, yang akan banyak pekerjaan ...).

Kedua metode di atas memiliki keterbatasan serius bagi saya dengan pengetahuan saya saat ini - Saya tidak tahu satu set masalah pengujian yang baik untuk yang pertama, dan saya tidak tahu metode yang baik untuk menghasilkan data uji untuk yang kedua.

Apakah ada cara lain untuk memverifikasi pemecah ODE numerik? Apakah ada kriteria lain tentang implementasi yang harus diverifikasi? Apakah ada sumber daya (gratis) yang bagus untuk menguji pemecah ODE di luar sana 1 ?

EDIT:
Karena pertanyaan ini sangat luas, saya ingin menjelaskan sedikit. Test suite yang ingin saya buat akan memenuhi dua tujuan utama:

  1. Memverifikasi bahwa pemecah berfungsi seperti yang diharapkan, untuk masalah yang ingin mereka selesaikan. Dengan kata lain, seorang pemecah untuk masalah yang tidak kaku dibiarkan menggunakan pisang pada masalah yang kaku, tetapi harus bekerja dengan baik pada masalah yang tidak kaku. Juga, jika ada pemecah lain di perpustakaan yang menawarkan akurasi lebih tinggi, mungkin tidak perlu untuk menegakkan hasil yang sangat akurat - cukup "cukup akurat". Jadi, bagian dari pertanyaan saya adalah tes apa yang harus digunakan untuk pemecah apa; atau, paling tidak, bagaimana seseorang harus beralasan untuk memutuskan itu.

  2. Tes kewarasan pada saat instalasi perpustakaan. Tes ini tidak perlu (tidak seharusnya) rumit atau memakan waktu; hanya dasar-dasar yang dapat dijalankan dalam waktu kurang dari 5 detik, tetapi itu akan mengingatkan pengguna jika ada sesuatu yang aneh. Jadi, saya juga membutuhkan cara untuk membuat tes yang sangat sederhana, tetapi masih memberi tahu saya tentang keadaan perpustakaan.


1 Ya, saya sudah mencari-cari di Googling, tetapi sebagian besar yang saya temukan adalah catatan kuliah dengan contoh-contoh yang sangat sepele, dengan perkecualian khusus dari rangkaian tes CWI ODE dari Bari yang saya tidak tahu jika, atau bagaimana, saya bisa digunakan untuk keperluan saya, karena itu memperlakukan pemecah jauh lebih canggih daripada yang saya ingin menguji ...

Tomas Aschan
sumber
2
@ user75064: Benar-benar! Saya tidak tahu situs itu ada =) Setiap mod, silakan bermigrasi ke sana.
Tomas Aschan
Ada tautan ke set tes lain dalam jawaban ini di Math Stack Exchange .
Geoff Oxberry
@ GeoffOxberry: Saya telah menemukan beberapa dari mereka sebelumnya. Kebanyakan dari mereka diimplementasikan dalam FORTRAN, dan mengasumsikan bahwa pembaca ingin menguji pemecah dalam bahasa yang sama, yang menambahkan sumber kesalahan lain ... Namun, sepasang (artikel tentang suite DETEST) terbukti sangat berguna. Terima kasih banyak!
Tomas Aschan

Jawaban:

12

Ini adalah pertanyaan yang sangat luas dan saya akan memberi Anda beberapa hal untuk dipikirkan (beberapa sudah dimasukkan dalam posting Anda, tetapi mereka diulangi di sini untuk kelengkapan).

Lingkup Masalah

  • Anda perlu menentukan antarmuka cara menentukan masalah.
  • Apakah Anda akan mengizinkan parameter yang dapat diperbaiki atau dapat bervariasi untuk solusi?
  • ϵ
  • Apakah Anda akan memungkinkan ketelitian tanpa batas?
  • Apakah Anda akan menguji kecepatan dan sensitivitas terhadap presisi numerik?
  • Sudahkah Anda memilih dua (mungkin lebih) perpustakaan yang sudah ada untuk membandingkan hasil?
  • Bagaimana Anda memilih kriteria berhenti, apakah Anda akan menggunakan berbagai metode dan membiarkan pengguna memilih atau menentukan sendiri?
  • Apakah Anda akan mengukur kesalahan menggunakan berbagai tindakan dan memungkinkan pengguna untuk mengaktifkan dan menonaktifkannya?
  • Sudahkah Anda melihat paket profesional seperti Computer-Algebra-Systems (CAS) dan memahami semua opsi yang mereka izinkan?
  • Apakah Anda akan mengizinkan menampilkan hasil dan / atau perbandingan dan / atau plot?

Rekomendasi masalah

  • Anda perlu menulis spesifikasi pengujian yang mendefinisikan sumber masalah, ruang lingkup dari bagaimana masalah diuji, menangkap hasil dan metrik dari menjalankan rutinitas.
  • Saya pasti akan melihat ke perpustakaan lain yang sudah ada untuk masalah yang mereka gunakan (mungkin file tes).
  • Saya akan pergi ke perpustakaan perguruan tinggi dan membaca buku tentang ODE dan mengeluarkan semua jenis masalah, mereka yang memiliki bentuk tertutup atau hanya solusi numerik.
  • Kasus 1: Kami ingin sebanyak mungkin variasi masalah solusi formulir tertutup untuk membandingkan hasil yang tepat versus hasil numerik.
  • Kasus 2: Saya akan pergi ke setiap buku analisis numerik yang dapat saya temukan dan menangkap contoh yang dikerjakan dan menduplikasinya. Saya juga akan menangkap set masalah, terutama yang memiliki beberapa patologi yang ada di sebagian besar buku (sensitivitas terhadap jenis ini atau itu).
  • Kasus 3: Saya akan pergi ke berbagai cabang matematika terapan seperti Fisika, Ekologi, Biologi, Ekonomi, et. al dan tangkap masalah dari masing-masing domain tersebut untuk memvalidasi bahwa bahasa spesifikasi Anda untuk masalah memungkinkan untuk contoh seperti itu.
  • Kasus 4: Saya akan meneliti makalah / jurnal yang berisi contoh paling berguna di mana penulis tertentu harus memodifikasi pendekatan tertentu untuk menjelaskan beberapa patologi atau keanehan atau kekerasan.
  • Kasus 5: Cari di web untuk contoh tambahan. Untuk kaku , lihat referensi di sini dan teliti mereka SEMUA untuk menemukan masalah pengujian. Berikut adalah beberapa contoh MATLAB untuk dibaca.

Ini tidak unik. Jika Anda melihat buku "Metode Numerik untuk Optimasi Tanpa Batas dan Persamaan Nonlinier" oleh Dennis dan Schnabel, Lampiran B, "Masalah Uji", Anda dapat melihat bagaimana mereka melakukannya. Setelah mengembangkan salah satu dari set algoritma yang paling indah dari penulisan yang pernah saya lihat, mereka melempar kumpulan masalah yang membuatnya menjadi gila. Anda harus men-tweak di sana-sini! Mereka termasuk lima masalah yang sangat berbeda dan patologis yang menekan kemampuan para pemecah. Ini telah mengajarkan saya bahwa kita dapat terus melempar masalah pada algoritma yang tidak mampu mereka tangani karena berbagai alasan. Catatan, mereka bahkan meminjam serangkaian masalah ini dari More ', Garbow dan Hillstrom (Anda juga dapat mencari referensi itu dan mungkin ada orang lain yang dapat Anda gunakan sebagai panduan).

Dengan kata lain, ini bukan tugas sepele. Anda memerlukan kasus Uji Jawaban yang Diketahui yang selalu memungkinkan Anda menguji validitas pembaruan dan tidak merusak barang. Yaitu, serangkaian masalah yang berulang dan luas dari rendah ke tinggi, dari yang mudah ke yang sulit, dari yang mungkin ke yang tidak mungkin, ... Anda juga membutuhkan sekumpulan masalah yang tidak bisa ditangani oleh pemecah Anda agar benar-benar memahami keterbatasannya.

Amzoti
sumber
2

Satu pemeriksaan kewarasan yang saya jalankan terhadap pemecah ODE saya adalah dengan hanya memeriksanya pada sistem linear yang lebih kecil melalui penghitungan eksponensial dari matriks sistem secara tepat. yaitu diberikan

dudt=Au

periksa kesalahan dalam

exp(tA)u0u^(t)

u^(t)

Hanya saja, jangan menghitung eksponensial dengan salah satu dari stepper waktu Anda (yaitu metode meragukan nomor 6 :) http://www.cs.cornell.edu/cv/researchpdf/19ways+.pdf )

Reid.Atcheson
sumber
Hanya sebuah catatan: DE integrator dianggap "meragukan" karena mereka agak tidak efisien dibandingkan dengan penskalaan + kuadrat, bukan karena ketidaktepatan.
JM
1

Anda dapat mencoba menyelidiki "Metode Solusi yang Diproduksi", yang merupakan metodologi umum yang digunakan untuk menguji implementasi kode yang memecahkan PDE (ini dapat digunakan untuk menemukan kesalahan matematis dan pengkodean). Saya membayangkan itu bisa diadaptasi untuk bekerja untuk memecahkan ODE, jika metodologi solusi Anda cukup umum.

http://prod.sandia.gov/techlib/access-control.cgi/2000/001444.pdf

Kris Kuhlman
sumber