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 Templat:Math titik $(x_0,y_0),\dots ,(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,\dots ,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.Templat:Citation-neededBeberapa 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),\dots ,(x_n,y_n)\in {ℝ}^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-Templat:Mvar (n-tuple) $(y_0,\dots ,y_n)\in {ℝ}^{n+1}$ dan ruang vektor polinomial real $P(n)$ dengan derajat maksimum Templat:Mvar; yakni $L_n:{ℝ}^{n+1}\stackrel{\sim }{⟶}{\mathrm{\Pi }}_n.$

Teorema ini dapat dibuktikan dengan menggunakan fungsi-fungsi basis Langrage$$L_{n,j}(x)=\prod _{k\ne 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,\dots ,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:

$\left[\begin{array}{cccccc}{x}_0^n& x_0^{n-1}& x_0^{n-2}& \dots & x_0& 1\\ x_1^n& x_1^{n-1}& x_1^{n-2}& \dots & x_1& 1\\ ⋮& ⋮& ⋮& & ⋮& ⋮\\ x_n^n& x_n^{n-1}& x_n^{n-2}& \dots & x_n& 1\end{array}\right]\left[\begin{array}{c}{a}_n\\ a_{n-1}\\ ⋮\\ a_0\end{array}\right]=\left[\begin{array}{c}{y}_0\\ y_1\\ ⋮\\ y_n\end{array}\right].$

Fungsi polinomial interpolasi $p(x)$ berkorespondensi pada solusi $A=(a_n,\dots ,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 $\det (X)=\prod _{1\le i<j\le n}(x_j-x_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.

Referensi

• Templat:Cite journal
• Templat:Cite journal
• Templat:Cite book

Bacaan lebih lanjut

• Templat:Cite book
• Templat:Cite journal
• Templat:Cite book
• Templat:Cite book
• Templat:Cite book

Pranala luar

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