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 (x_0,y_0), \ldots, (x_n,y_n), dengan tidak ada dua x_j yang sama, sebuah fungsi polinomial  p(x) dikatakan menginterpolasi data jika p(x_j)=y_j untuk setiap j\in\{0,1,\dotsc,n\}.

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 n yang unik dan menginterpolasi himpunan titik (x_0,y_0),\dotsc,(x_n,y_n) \in \R^2, jika tidak ada dua x_j yang sama. Dalam sudut pandang lain, untuk sebuah pemilihan titik-titik interpolasi x_j, interpolasi polinomial mendefinisikan sebuah bijeksi linear antara bilangan real rangkap- (n-tuple) (y_0,\ldots,y_n)\in \R^{n+1} dan ruang vektor polinomial real P(n) dengan derajat maksimum **; yakni L_n : \mathbb{R}^{n+1}  \stackrel{\sim}{\longrightarrow}\,  \Pi_n.

Teorema ini dapat dibuktikan dengan menggunakan fungsi-fungsi basis LangrageL_{n,j}(x)=\prod_{k\neq j}\frac{x-x_k}{x_j-x_k},yang setiap fungsinya, L_{n,j}, adalah sebuah polinomial berderajat n. Lebih lanjut, L_{n,j}(x_k)=\delta_{kj} berlaku untuk setiap x_k, dengan \delta_{kj} adalah fungsi delta Kronecker. Hal ini dapat digunakan untuk menunjukkan kombinasi linear p(x)=\sum_{j=0}^n y_j L_{n,j}(x)adalah sebuah fungsi polinomial interpolasi berderajat n. Sifat unik (tunggal) dari fungsi ini dibuktikan secara kontradiksi: anggap ada polinomial interpolasi q(x) lainnya yang berderajat maksimum n. Karena p(x_k)=q(x_k) untuk setiap k=0,\dotsc,n, polinomial  p-q memiliki n+1 akar yang berbeda. Akan tetapi, p-q memiliki derajat maksimum n, sehingga berdasarkan teorema dasar aljabar fungsi p-q hanya memiliki n akar yang berbeda. Karena anggapan salah, p=q (tidak ada polinomial interpolasi lainnya).

Teorema ini juga dapat dibuktikan dengan bantuan matriks Vandermonde. Sistem persamaan linear dapat dihasilkan lewat menjabarkan persamaan interpolasi p(x_j) = y_j dengan p(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0, untuk setiap pasangan (x_j,\,y_j). Dalam bentuk matriks, sistem persamaan dalam koefisien a_j tersebut dapat dituliskan sebagai perkalian:

: \begin{bmatrix}
x_0^n  & x_0^{n-1} & x_0^{n-2} & \ldots & x_0 & 1 \\
x_1^n  & x_1^{n-1} & x_1^{n-2} & \ldots & x_1 & 1 \\
\vdots & \vdots    & \vdots    &        & \vdots & \vdots \\
x_n^n  & x_n^{n-1} & x_n^{n-2} & \ldots & x_n & 1
\end{bmatrix}
\begin{bmatrix} a_n \\ a_{n-1} \\ \vdots \\ a_0 \end{bmatrix}  =
\begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_n \end{bmatrix}.

Fungsi polinomial interpolasi p(x) berkorespondensi pada solusi A = (a_n,\ldots,a_0) dari persamaan matriks X \cdot A = Y di atas. Matriks X di sisi kiri merupakan matriks Vandermonde, dengan nilai determinannya ditentukan dari persamaan \textstyle \det(X) = \prod_{1 \le i  Nilai determinan ini tidak nol karena setiap titik x_j berbeda. Hal ini memastikan matriks dapat diinvers dan persamaan tersebut memiliki solusi unik A = X^{-1}\cdot Y. Dengan kata lain p(x) ada dan unik.

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

## Catatan kaki

## Referensi

* 
* 
* 

## Bacaan lebih lanjut

* 
* 
* 
* 
* 

## Pranala luar

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