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.[1] Secara lebih formal, untuk himpunan n + 1 titik ( x 0 , y 0 ) , … , ( x n , y n ) {\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})} , dengan tidak ada dua x j {\displaystyle x_{j}} yang sama, sebuah fungsi polinomial p ( x ) {\displaystyle p(x)} dikatakan menginterpolasi data jika p ( x j ) = y j {\displaystyle p(x_{j})=y_{j}} untuk setiap j ∈ { 0 , 1 , … , n } {\displaystyle 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.[butuh rujukan]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 {\displaystyle n} yang unik dan menginterpolasi himpunan titik ( x 0 , y 0 ) , … , ( x n , y n ) ∈ R 2 {\displaystyle (x_{0},y_{0}),\dotsc ,(x_{n},y_{n})\in \mathbb {R} ^{2}} , jika tidak ada dua x j {\displaystyle x_{j}} yang sama.[2] Dalam sudut pandang lain, untuk sebuah pemilihan titik-titik interpolasi x j {\displaystyle x_{j}} , interpolasi polinomial mendefinisikan sebuah bijeksi linear antara bilangan real rangkap-n (n-tuple) ( y 0 , … , y n ) ∈ R n + 1 {\displaystyle (y_{0},\ldots ,y_{n})\in \mathbb {R} ^{n+1}} dan ruang vektor polinomial real P ( n ) {\displaystyle P(n)} dengan derajat maksimum n; yakni L n : R n + 1 ⟶ ∼ Π n . {\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 ) = ∏ k ≠ j x − x k x j − x k , {\displaystyle L_{n,j}(x)=\prod _{k\neq j}{\frac {x-x_{k}}{x_{j}-x_{k}}},}
yang setiap fungsinya, L n , j {\displaystyle L_{n,j}} , adalah sebuah polinomial berderajat n {\displaystyle n} . Lebih lanjut, L n , j ( x k ) = δ k j {\displaystyle L_{n,j}(x_{k})=\delta _{kj}} berlaku untuk setiap x k {\displaystyle x_{k}} , dengan δ k j {\displaystyle \delta _{kj}} adalah fungsi delta Kronecker. Hal ini dapat digunakan untuk menunjukkan kombinasi linear
p ( x ) = ∑ j = 0 n y j L n , j ( x ) {\displaystyle p(x)=\sum _{j=0}^{n}y_{j}L_{n,j}(x)}
adalah sebuah fungsi polinomial interpolasi berderajat n {\displaystyle n} . Sifat unik (tunggal) dari fungsi ini dibuktikan secara kontradiksi: anggap ada polinomial interpolasi q ( x ) {\displaystyle q(x)} lainnya yang berderajat maksimum n {\displaystyle n} . Karena p ( x k ) = q ( x k ) {\displaystyle p(x_{k})=q(x_{k})} untuk setiap k = 0 , … , n {\displaystyle k=0,\dotsc ,n} , polinomial p − q {\displaystyle p-q} memiliki n + 1 {\displaystyle n+1} akar yang berbeda. Akan tetapi, p − q {\displaystyle p-q} memiliki derajat maksimum n , {\displaystyle n,} sehingga berdasarkan teorema dasar aljabar[3] fungsi p − q {\displaystyle p-q} hanya memiliki n {\displaystyle n} akar yang berbeda. Karena anggapan salah, p = q {\displaystyle 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 {\displaystyle p(x_{j})=y_{j}} dengan

p ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 2 x 2 + a 1 x + a 0 , {\displaystyle 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 ) {\displaystyle (x_{j},\,y_{j})} . Dalam bentuk matriks, sistem persamaan dalam koefisien a j {\displaystyle a_{j}} tersebut dapat dituliskan sebagai perkalian:

[ x 0 n x 0 n − 1 x 0 n − 2 … x 0 1 x 1 n x 1 n − 1 x 1 n − 2 … x 1 1 ⋮ ⋮ ⋮ ⋮ ⋮ x n n x n n − 1 x n n − 2 … x n 1 ] [ a n a n − 1 ⋮ a 0 ] = [ y 0 y 1 ⋮ y n ] . {\displaystyle {\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 ) {\displaystyle p(x)} berkorespondensi pada solusi A = ( a n , … , a 0 ) {\displaystyle A=(a_{n},\ldots ,a_{0})} dari persamaan matriks X ⋅ A = Y {\displaystyle X\cdot A=Y} di atas. Matriks X {\displaystyle X} di sisi kiri merupakan matriks Vandermonde, dengan nilai determinannya ditentukan dari persamaan det ( X ) = ∏ 1 ≤ i < j ≤ n ( x j − x i ) . {\displaystyle \textstyle \det(X)=\prod _{1\leq i<j\leq n}(x_{j}-x_{i}).} Nilai determinan ini tidak nol karena setiap titik x j {\displaystyle x_{j}} berbeda. Hal ini memastikan matriks dapat diinvers dan persamaan tersebut memiliki solusi unik A = X − 1 ⋅ Y {\displaystyle A=X^{-1}\cdot Y} . Dengan kata lain p ( x ) {\displaystyle p(x)} ada dan unik.

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

Catatan kaki

  1. ^ Tiemann, Jerome J. (May–June 1981). "Polynomial Interpolation". I/O News. 1 (5): 16. ISSN 0274-9998. Diakses tanggal 3 November 2017. 
  2. ^ Humpherys, Jeffrey; Jarvis, Tyler J. (2020). "9.2 - Interpolation". Foundations of Applied Mathematics Volume 2: Algorithms, Approximation, Optimization. Society for Industrial and Applied Mathematics. hlm. 418. ISBN 978-1-611976-05-2. 
  3. ^ Humpherys, Jeffrey; Jarvis, Tyler J.; Evans, Emily J. (2017). "15.3: The Fundamental Theorem of Arithmetic". Foundations of Applied Mathematics Volume 1: Mathematical Analysis. Society for Industrial and Applied Mathematics. hlm. 591. ISBN 978-1-611974-89-8. 

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 AnalysisPerlu mendaftar (gratis) (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.