Mengapa poin equi-spaced berperilaku buruk?

24

Deskripsi percobaan:

Dalam interpolasi Lagrange, persamaan yang tepat diambil sampelnya pada titik N (urutan polinomial N1 ) dan diinterpolasi pada titik 101. Di sini N bervariasi dari 2 hingga 64. Setiap kali plot kesalahan L1 , L2 dan L disiapkan. Hal ini terlihat bahwa, ketika fungsi sampel pada titik-titik equi-spasi, kesalahan tetes awalnya (itu terjadi sampai N kurang dari sekitar 15 atau lebih) dan kemudian kesalahan naik dengan peningkatan lebih lanjut dalam N .

Sedangkan, jika pengambilan sampel awal dilakukan pada titik Legendre-Gauss (LG) (akar polinomial Legendre), atau poin Legendre-Gauss-Lobatto (LGL) (akar polinomial Lobatto), kesalahan turun ke tingkat mesin dan tidak meningkat ketika N semakin meningkat.

Pertanyaan saya adalah,

Apa yang sebenarnya terjadi dalam kasus titik yang berjarak sama?

Mengapa peningkatan urutan polinomial menyebabkan kesalahan naik setelah titik tertentu?

Apakah ini juga berarti bahwa jika saya menggunakan titik equi-spaced untuk rekonstruksi WENO / ENO (menggunakan polinomial Lagrange), maka di wilayah yang mulus, saya akan mendapatkan kesalahan? (yah, ini hanya pertanyaan hipotetis (untuk pemahaman saya), benar-benar tidak masuk akal untuk merekonstruksi polinomial urutan 15 atau lebih tinggi untuk skema WENO)

Detil tambahan:

Fungsi diperkirakan:

f(x)=cos(π2 x),x[1,1]

x dibagi menjadiN equispaced (dan nantinya LG) poin. Fungsi ini diinterpolasi pada 101 titik setiap kali.

Hasil:

  1. a) Poin equi-spaced (interpolasi untuk N=65 ):

masukkan deskripsi gambar di sini

  1. b) Poin yang berjarak spasi (plot kesalahan, skala log):

masukkan deskripsi gambar di sini

  1. a) Poin LG (Interpolasi untuk N=65 ): masukkan deskripsi gambar di sini

  2. b) Poin LG (plot kesalahan, skala log):

masukkan deskripsi gambar di sini

Subodh
sumber

Jawaban:

26

Masalah dengan titik equispaced adalah bahwa polinomial kesalahan interpolasi, yaitu

f(x)Pn(x)=f(n+1)(ξ)(n+1)!i=0n(xxi),ξ[x0,xn]

xi

Jika Anda menggunakan titik Gauss-Legendre, polinomial galat lebih baik berperilaku, artinya tidak meledak di tepinya. Jika Anda menggunakan node Chebyshev , persamaan polinomial ini dan kesalahan interpolasi minimal.

Pedro
sumber
6
Ada penjelasan yang cukup terperinci dalam buku John P. Boyd Chebyshev dan Fourier Spectral Methods, di mana polinomial kesalahan interpolasi Pedro juga dijelaskan dengan baik (Bab 4.2).
Bort
Terima kasih. Konstanta Lebesgue juga untuk pilihan yang disebutkan di atas berperilaku berbeda. Untuk titik-titik yang berjarak sama, konstanta Lebesgue meningkat secara eksponensial sedangkan untuk LG, LGL, Chebyshev agak jenuh dengan peningkatan n. en.wikipedia.org/wiki/Lebesgue_constant_(interpolation) , ami.ektf.hu/uploads/papers/finalpdf/AMI_33_from109to123.pdf , tetapi pertanyaan mengenai implementasi numerik masih ada ...
Subodh
Maaf, saya tidak tahu banyak tentang ENO / WENO. Tapi saya tidak akan mengharapkan masalah di wilayah halus untuk interpolasi urutan rendah, meskipun node quadrature jelas merupakan pilihan yang lebih baik untuk alasan yang berbeda.
Bort
22

Ini pertanyaan yang sangat menarik, dan ada banyak kemungkinan penjelasan. Jika kita mencoba menggunakan interpolasi polinomial, maka perhatikan bahwa polinomial memenuhi ketidaksetaraan berikut yang menjengkelkan.

PN

|P(x)|N1x2maxx|P(x)|

x(1,1)

maxx|P(x)|N2maxx|P(x)|

dan perhatikan bahwa ini tajam dalam arti bahwa polinomial Chebysehv menjadikan ini persamaan. Jadi dengan kata lain kita memiliki ikatan gabungan berikut.

|P(x)|min(N1x2,N2)maxx|P(x)|

N21/N2

Namun ternyata ini belum tentu merupakan fenomena polinomial, saya sarankan makalah berikut:

http://math.la.asu.edu/~platte/pub/prevised.pdf

Dikatakan longgar: Jika Anda memiliki kekuatan perkiraan yang sama dari basis polinom, maka Anda tidak dapat menggunakan titik spasi sama dengan cara yang stabil.

Reid.Atcheson
sumber
1

Bukan titik - titik dengan jarak yang sama yang menjadi masalah. Ini adalah dukungan global dari fungsi-fungsi dasar bersama dengan titik-titik yang berjarak sama yang merupakan masalahnya. Suatu interpolant yang dikondisikan dengan baik menggunakan titik-titik yang berjarak sama dijelaskan dalam Analisis Numerik Kress, menggunakan fungsi basis kompak cubic-b spline dari dukungan ringkas.

pengguna14717
sumber
C2
C
C2C4
1

Apa yang sebenarnya terjadi dalam kasus titik yang berjarak sama?

Mengapa peningkatan urutan polinomial menyebabkan kesalahan naik setelah titik tertentu?

Ini mirip dengan fenomena Runge di mana, dengan node yang berjarak sama, kesalahan interpolasi menjadi tak terhingga dengan meningkatnya derajat polinomial, yaitu jumlah titik.

Salah satu akar masalah ini dapat ditemukan dalam konstanta Lebesgue seperti yang dicatat oleh komentar @ Subodh pada jawaban @Pedro. Konstanta ini menghubungkan interpolasi dengan perkiraan terbaik.


Beberapa notasi

fC([a,b])xk

Lk(x)=i=0,ijnxxixkxi

pnPn(xk,f(xk))(xk,fk)

pn(x)=k=0nfkLk(x)

f~kp~n

p~n(x)=k=0nf~kLk(x)

Estimasi kesalahan adalah:

pn(x)p~n(x)=k=0n(fkf~k)Lk(x)

|pn(x)p~n(x)|k=0n|fkf~k||Lk(x)|(maxk|fkf~k|)k=0n|Lk(x)|

Λn

Λn=maxx[a,b]k=0n|Lk(x)|

Dengan ini perkiraan akhir adalah:

||pnp~n||(maxk|fkf~k|)Λn

LL1

Λn

  • independen dari tanggal:
  • hanya tergantung dari distribusi node;
  • indikator stabilitas (semakin kecil, semakin baik).

||||

Dengan mengikuti teorema, kita bisa mendapatkan estimasi kesalahan interpolasi dengan konstanta Lebesgue:

fpn

||fpn||(1+Λn)dn(f)
dn(f)=infqnPn||fqn||

Λn

Λnc

Λn2πlog(n)c

Λn2n+1enlog(n)

Λn2πlog(n)+4

Untuk distribusi node lain, lihat misalnya tabel 1 artikel ini .


Ada banyak referensi di buku tentang interpolasi. Secara online slide ini bagus sebagai resume.

Juga artikel terbuka ini ([1])

Perbandingan Tujuh Grid Interpolasi untuk polinomial pada Interval untuk berbagai perbandingan.

Mauro Vanzetto
sumber
1

{xi}i=1n

d0dnpi{xi,xi+d}f{xi}i=1n

rn(x):=i=0ndλi(x)pi(x)i=0ndλi(x)

dengan "fungsi blending"

λi(x)=(1)i(xxi)(xxi+d)

Beberapa sifat dari interpolant ini:

  • mereka adalah interpolasi rasional barycentric tanpa kutub nyata ;
  • O(hd+1)fCd+2[a,b]
  • p0,pndλ
  • dd+1nd
  • dapat ditulis dalam bentuk barycentric (lihat bagian 4 dari makalah Floater dan Hormann).

d

2d [a,b]f[a,b]f0,fnrn+2d[a,b]

ndd

Perpustakaan Chebfun menggunakan interpolant FH ketika membangun chebfunsdari data equispaced, seperti yang dijelaskan di sini .

Referensi:

MS Floater dan K. Hormann, interpolasi rasional Barycentric tanpa kutub dan tingkat perkiraan tinggi, Numerische Mathematik 107 (2007).

G. Klein, Perpanjangan Keluarga Floater – Hormann dari Interpolasi Rasional Barycentric, Matematika Komputasi , 82 (2011) - pracetak

L. Bos, S. De Marchi, K. Hormann, dan G. Klein, Pada konstanta Lebesgue dari interpolasi rasional barycentric pada node yang sama, Numer. Matematika 121 (2012)

GoHokies
sumber