Misalkan saya memiliki beberapa fungsi dan saya ingin mencari sedemikian rupa sehingga . Saya mungkin menggunakan metode Newton-Raphson. Tapi ini mengharuskan saya tahu fungsi turunan . Ekspresi analitik untuk mungkin tidak tersedia. Sebagai contoh, dapat didefinisikan oleh sepotong kode komputer yang rumit yang berkonsultasi dengan basis data nilai eksperimental.f ( x ) ≈ 0 f ′ ( x ) f f
Tetapi bahkan jika rumit, saya dapat memperkirakan untuk tertentu dengan memilih sejumlah kecil dan menghitung .f ′ ( a ) a ϵ f ′ ( a ) ≈ f ( a + ϵ ) - f ( a )
Saya telah mendengar bahwa ada beberapa kelemahan dari pendekatan ini, tetapi saya tidak tahu apa itu. Wikipedia mengisyaratkan bahwa "Menggunakan perkiraan ini akan menghasilkan sesuatu seperti metode garis potong yang konvergensinya lebih lambat daripada metode Newton."
Dapatkah seseorang tolong uraikan hal ini, dan berikan referensi yang secara khusus membahas masalah dengan teknik ini?
sumber
Jawaban:
Demi notasi, anggaplah (yaitu, ini adalah fungsi bernilai vektor yang mengambil vektor sebagai input dan menghasilkan vektor dengan ukuran yang sama). Ada dua masalah: biaya komputasi dan akurasi numerik.f: Rn→ Rn
Menghitung turunan (matriks Jacobian, J ( x ) , atau ( ∇ f ( x ) ) T , atau apapun yang Anda suka) menggunakan perbedaan terbatas akan membutuhkan n evaluasi fungsi. Jika Anda dapat menghitung turunan menggunakan aritmatika titik mengambang langsung dari definisi, Anda harus menghitung hasil bagi selisihD f( x ) J( x ) ( ∇ f( x ) )T n
untuk setiap , dengan asumsi Anda tidak melakukan apapun "terbatas pintar differencing" (seperti Curtis-Powell-Reid) karena Anda tahu (atau dapat mendeteksi) pola sparsity dari D f . Jika n besar, itu bisa menjadi banyak evaluasi fungsi. Jika Anda memiliki ekspresi analitis untuk D f , maka perhitungan itu bisa lebih murah. Otomatis (juga dikenal sebagai algoritmik) metode diferensiasi juga dapat digunakan dalam beberapa kasus untuk menghitung D f pada kira-kira 3 sampai 5 kali biaya evaluasi fungsi.i = 1 , … , n D f n D f D f
Ada juga kekhawatiran numerik. Jelas, di komputer, kita tidak bisa mengambil batas skalar karena pergi ke nol, jadi ketika kita perkiraan , kita benar-benar memilih ε menjadi "kecil" dan menghitungD f ε
di mana berarti perkiraan, dan kami harap ini perkiraan yang benar-benar bagus. Menghitung perkiraan ini dalam aritmatika floating point sulit karena jika Anda memilih ε terlalu besar, perkiraan Anda bisa buruk, tetapi jika Anda memilih ε terlalu kecil, mungkin ada kesalahan pembulatan yang signifikan. Efek-efek ini tercakup dalam artikel Wikipedia tentang diferensiasi numerik dalam detail yang dangkal; referensi yang lebih rinci dapat ditemukan dalam artikel.≈ ε ε
Jika kesalahan dalam Jacobian matriks tidak terlalu besar, Newton-Raphson iterasi akan bertemu. Untuk analisis teoretis terperinci, lihat Bab 25 tentang Keakuratan dan Stabilitas Algoritma Angka oleh Nick Higham , atau makalah dari Françoise Tisseur yang menjadi dasarnya .D f
Perpustakaan umumnya menangani perincian algoritmik ini untuk Anda, dan biasanya, implementasi perpustakaan dari algoritma Newton-Raphson (atau varian-varian daripadanya) akan menyatu dengan cukup baik, tetapi seringkali, akan ada masalah yang menyebabkan beberapa masalah karena kekurangannya. atas. Dalam kasus skalar , saya akan menggunakan metode Brent , karena kekokohan dan tingkat konvergensi yang baik dalam praktiknya.( n = 1 )
sumber