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 n + 1 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 \mathbb {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 (n-tuple) $(y_{0},\ldots ,y_{n})\in \mathbb {R} ^{n+1}$ dan ruang vektor polinomial real $P(n)$ dengan derajat maksimum n; yakni ${\textstyle L_{n}:\mathbb {R} ^{n+1}{\stackrel {\sim }{\longrightarrow }}\,\Pi _{n}.}$

Teorema ini dapat dibuktikan dengan menggunakan fungsi-fungsi basis Langrage$$L_{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\leq i<j\leq 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

• Bernstein, Sergei N. (1912). "Sur l'ordre de la meilleure approximation des fonctions continues par les polynômes de degré donné" [On the order of the best approximation of continuous functions by polynomials of a given degree]. Mem. Acad. Roy. Belg. (dalam bahasa Prancis). 4: 1–104. 
• Faber, Georg (1914). "Über die interpolatorische Darstellung stetiger Funktionen" [On the Interpolation of Continuous Functions]. Deutsche Math. Jahr. (dalam bahasa Jerman). 23: 192–210. 
• Watson, G. Alistair (1980). Approximation Theory and Numerical Methods. John Wiley. ISBN 0-471-27706-1. 

Bacaan lebih lanjut

• Atkinson, Kendell A. (1988). "Chapter 3.". An Introduction to Numerical Analysis (edisi ke-2nd). John Wiley and Sons. ISBN 0-471-50023-2. 
• Brutman, L. (1997). "Lebesgue functions for polynomial interpolation — a survey". Ann. Numer. Math. 4: 111–127. 
• Powell, M. J. D. (1981). "Chapter 4". Approximation Theory and Methods. Cambridge University Press. ISBN 0-521-29514-9. 
• Schatzman, Michelle (2002). "Chapter 4". Numerical Analysis: A Mathematical Introduction. Oxford: Clarendon Press. ISBN 0-19-850279-6. 
• Süli, Endre; Mayers, David (2003). "Chapter 6". An Introduction to Numerical Analysis. Cambridge University Press. ISBN 0-521-00794-1. 

Pranala luar

• Hazewinkel, Michiel, ed. (2001) [1994], "Interpolation process", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4 
• Implementasi oleh ALGLIB yang menggunakan C++ / C#.
• Kode interpolasi polinomial GSL dalam bahasa C.