Interpolasi polinomial

Dalam analisis numerik, interpolasi polinomial adalah sebuah metode interpolasi untuk suatu himpunan titik, dengan menggunakan polinomial derajat terkecil yang melewati semua titik pada himpunan tersebut. Secara lebih formal, untuk himpunan  titik , dengan tidak ada dua  yang sama, sebuah fungsi polinomial   dikatakan menginterpolasi data jika  untuk setiap .

Dua rumus eksplisit yang umum untuk jenis polinomial ini adalah polinomial Langrange dan polinomial Newton.

Penerapan 
Polinomial dapat digunakan untuk menghampiri bentuk kurva-kurva yang rumit, contohnya kurva yang membentuk huruf-huruf dalam tipografi.Beberapa penerapan lainnya adalah untuk menaksir nilai fungsi logaritma alami dan fungsi-fungsi trigonometri. Hal ini dilakukan dengan menghitung nilai fungsi di beberapa titik, lalu membuat polinomial interpolasi dari titik-titik tersebut. Perhitungan menggunakan polinomial memungkinkan hasil didapatkan dalam waktu yang lebih singkat. Interpolasi polinomial berperan penting dalam algoritma perkalian dan pemangkatan sub-kuadratik, seperti perkalian Karatsuba dan perkalian Toom–Cook. Interpolasi polinomial juga menjadi dasar algoritma-algoritma integrasi numerik, solusi numerik dari sistem persamaan diferensial biasa, dan skema-skema pembagian rahasia.

Teorema interpolasi 
Teorema ini menyatakan keberadaan sebuah polinomial dengan derajat maksimum  yang unik dan menginterpolasi himpunan titik , jika tidak ada dua  yang sama. Dalam sudut pandang lain, untuk sebuah pemilihan titik-titik interpolasi , interpolasi polinomial mendefinisikan sebuah bijeksi linear antara bilangan real rangkap- (n-tuple)  dan ruang vektor polinomial real  dengan derajat maksimum ; yakni 

Teorema ini dapat dibuktikan dengan menggunakan fungsi-fungsi basis Langrageyang setiap fungsinya, , adalah sebuah polinomial berderajat . Lebih lanjut,  berlaku untuk setiap , dengan  adalah fungsi delta Kronecker. Hal ini dapat digunakan untuk menunjukkan kombinasi linear adalah sebuah fungsi polinomial interpolasi berderajat . Sifat unik (tunggal) dari fungsi ini dibuktikan secara kontradiksi: anggap ada polinomial interpolasi  lainnya yang berderajat maksimum . Karena  untuk setiap , polinomial   memiliki  akar yang berbeda. Akan tetapi,  memiliki derajat maksimum  sehingga berdasarkan teorema dasar aljabar fungsi  hanya memiliki  akar yang berbeda. Karena anggapan salah,  (tidak ada polinomial interpolasi lainnya).

Teorema ini juga dapat dibuktikan dengan bantuan matriks Vandermonde. Sistem persamaan linear dapat dihasilkan lewat menjabarkan persamaan interpolasi  dengan untuk setiap pasangan . Dalam bentuk matriks, sistem persamaan dalam koefisien  tersebut dapat dituliskan sebagai perkalian:

 

Fungsi polinomial interpolasi  berkorespondensi pada solusi  dari persamaan matriks  di atas. Matriks  di sisi kiri merupakan matriks Vandermonde, dengan nilai determinannya ditentukan dari persamaan  Nilai determinan ini tidak nol karena setiap titik  berbeda. Hal ini memastikan matriks dapat diinvers dan persamaan tersebut memiliki solusi unik . Dengan kata lain  ada dan unik.

Sebagai akibat dari teorema ini, jika  adalah polinomial berderajat maksimum , maka polinomial interpolasi dari  dengan menggunakan  titik berbeda, akan menghasilkan  itu sendiri.

Catatan kaki

Referensi

Bacaan lebih lanjut

Pranala luar 

 
 Implementasi oleh ALGLIB yang menggunakan C++ / C#.
 Kode interpolasi polinomial GSL dalam bahasa C.