Bagaimana saya bisa membedakan fungsi sampel yang tidak rata secara numerik?

21

Rumus perbedaan hingga standar dapat digunakan untuk menghitung turunan secara numerik di bawah ekspektasi bahwa Anda memiliki nilai fungsi pada titik yang diberi spasi secara merata, sehingga adalah konstanta. Bagaimana jika saya memiliki titik spasi yang tidak rata, sehingga sekarang bervariasi dari satu pasang titik yang berdekatan ke yang berikutnya? Jelas saya masih dapat menghitung turunan pertama sebagai , tetapi apakah ada rumus diferensiasi numerik pada pesanan yang lebih tinggi dan akurasi yang dapat beradaptasi dengan variasi ukuran kisi?h x k + 1 - x k h f ( x ) 1f(xk)hxk+1xkhf(x)1hk[f(xk+1)f(xk)]

David Z
sumber
7
Anda selalu dapat membuat interpolasi polinomial (piecewise) melewati poin Anda, dan kemudian membedakannya.
JM
Atau, Anda dapat merekonstruksi rumus perbedaan hingga tanpa penyederhanaan . Sering kali ini harus dilakukan untuk integrasi, tetapi kemungkinan saran JM lebih stabil. h=xk+1xk
rcollyer
Fungsi macam apa itu?
mbq
Contoh yang mendorong pertanyaan ini adalah fungsi yang diambil sampelnya pada nilai spasi logaritma , tetapi menghitung turunan kedua dari data yang ditransformasi log memberikan hasil yang lucu dan saya ingin memeriksanya. Ditambah lagi, kupikir aku akan mengajukan pertanyaan seluas mungkin. xk=x0δk
David Z
1
Sejauh yang saya ketahui, sesuatu yang hanya berfungsi untuk turunan pertama dan kedua akan menjadi jawaban yang sangat baik untuk pertanyaan itu. Saya menulis pertanyaan seperti yang saya lakukan untuk memungkinkan jawaban umum jika seseorang memiliki satu, tetapi tentu saja dalam praktiknya itu adalah deret pertama dan kedua yang paling berguna.
David Z

Jawaban:

21

Komentar JM benar: Anda dapat menemukan polinomial interpolasi dan membedakannya. Ada cara lain untuk menurunkan formula tersebut; biasanya, mereka semua mengarah pada pemecahan sistem van der Monde untuk koefisien. Pendekatan ini bermasalah ketika stensil perbedaan terbatas mencakup sejumlah besar poin, karena matriks Vandermonde menjadi tidak terkondisikan. Pendekatan yang lebih stabil secara numerik dirancang oleh Fornberg , dan dijelaskan lebih jelas dan umum dalam makalah keduanya .

Berikut ini adalah skrip MATLAB sederhana yang mengimplementasikan metode Fornberg untuk menghitung koefisien dari pendekatan perbedaan hingga untuk setiap turunan pesanan dengan set poin apa pun. Untuk penjelasan yang bagus, lihat Bab 1 teks LeVeque tentang metode beda hingga .

Sedikit lebih banyak tentang rumus FD: Misalkan Anda memiliki kisi 1D. Jika Anda menggunakan seluruh set titik kisi untuk menentukan satu set rumus FD, metode yang dihasilkan setara dengan menemukan polinomial interpolasi melalui seluruh kisi dan membedakannya. Pendekatan ini disebut kolokasi spektral. Atau, untuk setiap titik kisi Anda bisa menentukan rumus FD hanya menggunakan beberapa titik tetangga. Inilah yang dilakukan dalam metode beda hingga tradisional.

Seperti disebutkan dalam komentar di bawah ini, menggunakan perbedaan hingga dari urutan sangat tinggi dapat menyebabkan osilasi (fenomena Runge) jika poin tidak dipilih dengan hati-hati.

David Ketcheson
sumber
3
Di sisi lain, ketika Anda menggunakan polinomial interpolasi, orang harus selalu mengingat hal-hal seperti fenomena Runge yang mungkin terjadi dengan data Anda, jika data Anda cukup dikonfigurasi secara terbalik. Saya akan mengatakan polinomial piecewise mungkin kurang rentan terhadap ini ...
JM
1
Saya ingin tahu apakah karya Koev dan teknik Fornberg dapat dikaitkan?
David Ketcheson
1
Cukup menarik, tampaknya ada kemiripan antara formula Fornberg, dan formula sebelumnya yang dikembangkan oleh Lyness dan Moler berdasarkan pada metode Neville klasik untuk menghasilkan polinomial interpolasi. Mereka mungkin sebenarnya formula yang sama di notasi yang berbeda, tetapi saya belum memeriksa secara menyeluruh.
JM
2
Interpolasi polinomial dengan banyak titik memerlukan distribusi titik khusus untuk dikondisikan dengan baik. Secara umum, untuk distribusi titik yang tidak seragam, tidak disarankan untuk melakukan interpolasi dan kemudian membedakan polinomial interpolasi karena dapat sangat berosilasi (pikirkan "Fenomena Runge" seperti yang disebutkan oleh JM). Bergantung pada kebutuhan Anda, mungkin ide yang lebih baik untuk hanya menggunakan splines kubik yang untuk banyak tujuan praktis dapat memberikan jawaban yang baik untuk masalah perkiraan turunan aproksimasi.
Allan P. Engsig-Karup
1
Jawaban bagus. Sekedar informasi, makalah ini memberikan pendekatan alternatif untuk Fornberg. Ini mengikuti prinsip yang sama, tetapi memberikan algoritma yang berbeda.
davidhigh
2

Jawaban di atas sangat bagus dalam hal memberi Anda kode untuk digunakan, tetapi tidak sebagus dalam hal teori. Jika Anda ingin mempelajari lebih dalam tentang interpolasi polinomial, lihat perlakuan teoretis ini dengan beberapa contoh nyata:

Singh, Ashok K., dan BS Bhadauria. "Rumus perbedaan hingga untuk sub-interval yang tidak sama menggunakan rumus interpolasi lagrange." Jurnal Internasional Matematika dan Analisis 3.17 (2009): 815-827. ( Tautan ke PDF )

Para penulis menggunakan Interpolasi Lagrangian (lihat artikel Wikipedia ) untuk menghitung polinomial interpolasi 3-point, 4-point, dan 5-point, serta turunan pertama, kedua, dan ketiga mereka. Mereka memiliki ekspresi untuk kesalahan pemotongan juga, yang penting untuk dipertimbangkan ketika menggunakan skema beda hingga. Mereka juga memiliki rumus umum untuk menghitung polinomial interpolasi menggunakan titik N.

Polinomial interpolasi Lagrangian berguna karena polinomial dan turunannya bisa sangat akurat dalam domain yang Anda interpolasi, dan mereka tidak mengasumsikan spasi grid genap. Karena sifat polinomial interpolasi Lagrangian, Anda tidak akan pernah memiliki lebih banyak pesanan turunan daripada jumlah titik kisi.

Saya pikir ini menjawab pertanyaan Anda dengan baik karena makalah yang saya kutip memiliki formula untuk skema beda hingga terbatas tingkat tinggi yang sewenang-wenang, yang pada dasarnya adalah untuk grid yang tidak rata dan hanya dibatasi oleh jumlah titik grid yang Anda sertakan dalam stensil Anda. Makalah ini juga memiliki rumus umum untuk kesalahan pemotongan, yang akan membantu Anda mengevaluasi skema polinomial interpolasi Lagrangian dengan skema lain yang mungkin Anda pertimbangkan. Makalah penulis harus memberikan hasil yang sama dengan metode Fornberg. Kontribusi mereka benar-benar hanya menghitung beberapa contoh dan memberikan perkiraan kesalahan, yang mungkin berguna bagi Anda.

Saya menemukan kedua makalah yang saya kutip dan karya Fornberg berguna untuk penelitian saya sendiri.

jvriesem
sumber
1
maaf saya harus menyatakannya, tetapi referensi Anda yang dikutip terlihat aneh - mereka menggunakan formula mengerikan dan hanya menyelesaikan beberapa kasus khusus. Sebaliknya, Fornberg telah memecahkan masalah umum dengan memberikan algoritma sederhana, dan itu sudah ada di tahun 80-an. Lihat di sini
davidhigh
makalah lain yang memecahkan masalah umum ada di sini
davidhigh
2
dan komentar terakhir untuk tidak menghormati makalah ini. Dalam "perlakuan teoretis yang sangat baik", Anda tidak dapat memiliki 9 referensi, di mana 7 merujuk pada karya Anda sendiri dan satu ke buku analisis numerik umum. Setidaknya tidak jika Anda tidak menemukan topiknya sendiri, yang tidak dimiliki oleh para penulis itu.
davidhigh
Anda benar sekali. Saya tidak akan mengatakan formula itu mengerikan, meskipun bisa diperbaiki. Kasus khusus sebenarnya lebih baik sebagai tes / perbandingan, dan mereka memang memberikan formula umum, yang harus sama dengan Fornberg.
jvriesem
1
@ jvriesem Harap dicatat bahwa kertas yang dikutip memiliki tanda yang salah dalam istilah ketiga dalam Persamaan. (15b)
Tarek
-4

Metode paling sederhana adalah dengan menggunakan perkiraan perbedaan hingga.

Estimasi dua titik sederhana adalah menghitung kemiringan garis potong terdekat melalui titik (x, f (x)) dan (x + h, f (x + h)). [1] Memilih sejumlah kecil h, h mewakili perubahan kecil dalam x, dan dapat berupa positif atau negatif. Kemiringan garis ini adalah

f(x+h)f(x)h

Ungkapan ini adalah hasil bagi perbedaan Newton.

Kemiringan garis garis potong ini berbeda dari kemiringan garis garis singgung dengan jumlah yang kira-kira sebanding dengan h. Ketika h mendekati nol, kemiringan garis garis potong mendekati kemiringan garis garis singgung. Oleh karena itu, turunan sebenarnya dari f pada x adalah batas nilai selisih hasil ketika garis potong semakin dekat dan semakin dekat menjadi garis singgung

evion2011
sumber
1
Saya pikir Anda sedang downvoted karena David Zaslavsky secara khusus menyebutkan rumus pembagian selisih, dan pertanyaannya adalah menanyakan apakah ada perkiraan yang lebih baik.
Dan
7
Juga karena ini adalah copy-paste langsung dari Wikipedia , kecuali untuk tautan spam yang awalnya merupakan bagian dari jawabannya.
David Z