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 , 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.[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 yang unik dan menginterpolasi himpunan titik , jika tidak ada dua yang sama.[2] Dalam sudut pandang lain, untuk sebuah pemilihan titik-titik interpolasi , interpolasi polinomial mendefinisikan sebuah bijeksi linear antara bilangan real rangkap-n (n-tuple) dan ruang vektor polinomial real dengan derajat maksimum n; 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[3] 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
- ^ Tiemann, Jerome J. (May–June 1981). "Polynomial Interpolation". I/O News. 1 (5): 16. ISSN 0274-9998. Diakses tanggal 3 November 2017.
- ^ 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.
- ^ 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 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.