Saya perlu menemukan semua akar fungsi skalar dalam interval yang diberikan. Fungsi mungkin memiliki diskontinuitas. Algoritme dapat memiliki ketepatan ε (mis. Ok jika algoritma tidak menemukan dua akar berbeda yang lebih dekat dari ε).
Apakah ada algoritma seperti itu? Bisakah Anda menunjukkan kepada saya makalah tentang itu?
Sebenarnya, saya memiliki fungsi untuk menemukan nol dalam interval yang diberikan menggunakan algoritma Brent, dan fungsi untuk menemukan minimum dalam interval yang diberikan. Dengan menggunakan dua fungsi itu, saya membuat algoritma saya sendiri, tetapi saya bertanya-tanya apakah ada algoritma yang lebih baik. Algoritme saya seperti itu:
Saya mulai dengan interval [a,b]dan fungsi f. Jika sign(f(a+ε)) ≠ sign(f(b-ε)), saya tahu setidaknya ada satu nol di antara adan b, dan saya menemukan z = zero(]a,b[). Saya menguji apakah zbenar-benar nol (bisa berupa diskontinuitas), dengan melihat nilai z-εdan z+ε. Jika ya, saya menambahkannya ke daftar nol yang ditemukan. Jika f(a+ε)dan f(b-ε)keduanya positif, saya mencari m = min(]a, b[). Jika f(m)masih positif, saya mencari m = max(]a,b[)karena mungkin ada diskontinuitas antara adan b. Saya melakukan sebaliknya jika f(a+ε)dan f(b-ε)negatif.
Sekarang, dari titik saya menemukan ( zatau m) saya membangun tumpukan berisi nol, diskontinuitas, dan titik belok fungsi saya. Setelah iterasi pertama, tumpukan sekarang terlihat seperti [a, z, b]. Saya mulai lagi algoritma dari interval ]a,z[dan ]z,b[. Ketika, di antara dua titik adan b, ekstrema memiliki tanda yang sama dari kedua ujung interval, dan tidak ada diskontinuitas pada kedua ekstrema, saya menghapus interval dari tumpukan. Algoritma berakhir ketika tidak ada lagi interval.
sumber
Jawaban:
Jika Anda menggunakan Matlab, Anda mungkin ingin mencoba sistem Chebfun (penafian: Saya dulunya adalah pengembang aktif proyek ini). Ia dapat menemukan semua akar fungsi satu dimensi dalam interval tertutup atau terbuka untuk presisi mesin.
Gagasan utama di balik pencari akar Chebfun adalah untuk menggunakan kombinasi pembelahan rekursif dan Matriks Rekan Kerja, analog dari Matriks Pendamping , pada koefisien interpolant dari fungsi target.
Saya memiliki versi kode yang disederhanakan di sini . Fungsi ini
chebrootsmengambil fungsi anonim sebagai input pertama, interval hingga sebagai argumen kedua dan ketiga, dan gelarNsebagai argumen keempat dan terakhir. Untuk hasil yang masuk akal, Anda dapat mengaturNke100.sumber
Secara umum, ini adalah pencarian tanpa harapan - tanpa beberapa informasi tentang kontinuitas dan / atau perbedaan fungsi, apa pun bisa terjadi. Pertimbangkan misalnya fungsi MATLAB yang didefinisikan pada interval dari 0 hingga 1:
fungsi y = f (x)
y = 1.0;
jika (x == 0,01)
y = 0,0;
akhir
jika (x == 0,013)
y = 0,0;
akhir
if (x == 0.753124)
y = 0,0;
akhir
Memperlakukan fungsi ini sebagai kotak blok, tidak ada cara untuk melihat bahwa ia memiliki nol di tiga titik ini dan tidak ada titik lain dalam interval dari 0 hingga 1 tanpa memeriksa setiap angka floating point antara 0 dan 1.
sumber