Interpolasi Polinomial Lagrange dan Newton dengan Python
Analisis Numerik Python |
| Contoh interpolasi Newton titik-titik (10, 15), (15, 20), (20, 100), (30, 10) |
Intepolation atau dalam bahasa Indonesia interpolasi adalah jenis estimasi (perkiraan), metode membangun titik data baru dalam kisaran set diskrit dalam titik data yang diketahui. Dalam sebuah eksperimen, peneliti menemukan data sejumlah titik dari hasil eksperimen atau penelitian yang dilakukan. Titik-titik data dari sebuah eksperimen mewakili variable yang diamati oleh peneliti. Dari titik-titik data hasil eksperimen ini, peneliti akan mencari nilai fungsi dari titik-titik data yang diperoleh sehingga membentuk fungsi yang kontinu. Sering kali peneliti menginterpolasikan atau memperkirakan nilai fungsi tersebut dengan beberapa metode yang tersedia.
Sementara itu dalam bidang komputer, Interpolasi digunakan untuk membuat sketsa, figure, atau bentuk dari berbagai benda dan makhluk hidup. Interpolasi dapat digunakan untuk peramalan data menggikuti pola suatu grafik yang ada. Seperti apabila memiliki sekumpulan data pengangguran di Indonesia. Data tersebut dapat dilakukan interpolasi hingga terbentuk grafik yang menunjukkan peramalan jumlah pengangguran di tahun-tahun berikutnya. Namun peramalan ini tidak akan akurat karena hanya berasal dari data, dan tidak memasukkan variable yang lain seperti jumlah lapangan kerja, banyak PHK dan variable lainnya.
Pengertian dari Interpolasi polynomial sendiri adalah teknik interpolasi dengan mengikuti pola data polinomial baik berderajat satu atau yang lebih tinggi.
Sampai tulisan ini dibuat penulis Divergensi Code hanya mengetahui tiga jenis Interpolasi Polinomial. Barang kali di luar sana masih ditemukan cara melakukan Interpolasi Polinomial yang lebih baik. Interpolasi Polinomial yang diketahui penulis yaitu interpolasi Lagrange, Interpolasi Newton, dan Interpolasi Spline. Namun dalam artikel ini hanya akan dibahas dua jenis interpolasi saja yaitu Interpolasi Lagrange dan Interpolasi Newton.
Interpolasi Polinomial Newton
Persamaan polinomial liniear akan memiliki persamaan 
misalnya
dan 
maka persamaan tersebut dapat dituliskan sebagai berikut 
. Misalkan a1 dituliskan dalam bentuk fungsi maka akan menghasilkan persamaan fungsi 
. Fungsi a1 ini dalam interpolasi newton disebut dengan fungsi selisih terbagi (divided difference).
Persamaan polinomial kuadrat akan memiliki persamaan
. Persamaan tersebut dapat di sederhanakan dengan menggabungkan persamaan polinomial liniear menghasilkan 
di mana 
, kemudian dilakukan subtitusi akan menjadi 
. Dengan persamaan aljabar maka akan dihasilkan 
. Jika kita teruskan persamaan diatas akan menjadi
dengan nilai a0, a1, a2, a3, ... , an
. Dengan fungsi divided diference
Dengan memperluas ke polonimial pangkat n akan terbentuk persamaan interpolasi newton
.
Setelah mengetahui cara pembentukan interpolasi newton, sekarang saatnya untuk contoh soal. Misalnya suatu percobaan menghasilkan titik-titik (-1, 1), (0, 1), (1, 2), (2, 0). Bentuklah fungsi yang memetakkan titik-titik tersebut dengan interpolasi newton!
Dengan menggunakan fungsi divided difference /
hasilnya akhir dari interpolasi newton di atas akan menjadi
dapat disederhanakan menjadi
.
misalnya
maka persamaan tersebut dapat dituliskan sebagai berikut . Misalkan a1 dituliskan dalam bentuk fungsi maka akan menghasilkan persamaan fungsi . Fungsi a1 ini dalam interpolasi newton disebut dengan fungsi selisih terbagi (divided difference).Persamaan polinomial kuadrat akan memiliki persamaan
. Persamaan tersebut dapat di sederhanakan dengan menggabungkan persamaan polinomial liniear menghasilkan 
di mana 
, kemudian dilakukan subtitusi akan menjadi 
. Dengan persamaan aljabar maka akan dihasilkan 
. Jika kita teruskan persamaan diatas akan menjadi
Dengan memperluas ke polonimial pangkat n akan terbentuk persamaan interpolasi newton
.Setelah mengetahui cara pembentukan interpolasi newton, sekarang saatnya untuk contoh soal. Misalnya suatu percobaan menghasilkan titik-titik (-1, 1), (0, 1), (1, 2), (2, 0). Bentuklah fungsi yang memetakkan titik-titik tersebut dengan interpolasi newton!
Dengan menggunakan fungsi divided difference /
akan dihasilkan pyramid divided difference.
Pada pyramid tersebut hanya digunakan pada bagian atasnya saja dari 1 sampai terakhir. Sekarang saatnya untuk menggunakan interpolasi newton
hasilnya akhir dari interpolasi newton di atas akan menjadi
.Algoritma beda terbagi / divided difference
Implementasi dari algoritma diatas dan bentuk persamaannya ke python akan menjadi seperti ini
Interpolasi Polinomial Lagrange
Interpolasi lagrange pada dasarnya dilakukan untuk menghindari perhitungan beda terbagi dari interpolasi newton. Interpolasi lagrange dapat diturunkan dari interpolasi polinomial newton. Bentuk persamaan lagrange ber orde n akan menjadi persamaan 
dengan fungsi 
. Tanda pada fungsi L adalah perkalian dari j = 0 sampai j = n, kecuali j = i. Kenapa j = i dilewati? j = i dilewati karena jika j = i maka nilai x-nya akan sama sehingga akan membuat pembagian dengan nol yang menjadikan tidak terdefinisikan. Karena Interpolasi Lagrange ini diturunkan dari interpolasi newton, maka seharusnya hasilnya akan sama dengan hasil yang di dapatkan dengan interpolasi newton.
Contoh interpolasi lagrange. Diketahui titi-titik data (1, -1), (3, 1/2), dan (4, 0). Tentukan persamaan titik-titik tersebut dengan menggunakan interpolasi lagrange.
Fungsi L tersebut dimasukan ke persamaan interpolasi lagrange akan menghasilkan
.
Cobalah untuk menyelesaikan soal yang sama dengan interpolasi newton! Hasilnya pasti akan sama dengan hasil yang di dapatkan interpolasi lagrange.
Sekarang saatnya kita untuk mencoba mengimplementasikan interpolasi lagrange ke dalam python.
dengan fungsi . Tanda pada fungsi L adalah perkalian dari j = 0 sampai j = n, kecuali j = i. Kenapa j = i dilewati? j = i dilewati karena jika j = i maka nilai x-nya akan sama sehingga akan membuat pembagian dengan nol yang menjadikan tidak terdefinisikan. Karena Interpolasi Lagrange ini diturunkan dari interpolasi newton, maka seharusnya hasilnya akan sama dengan hasil yang di dapatkan dengan interpolasi newton.Contoh interpolasi lagrange. Diketahui titi-titik data (1, -1), (3, 1/2), dan (4, 0). Tentukan persamaan titik-titik tersebut dengan menggunakan interpolasi lagrange.
Fungsi L tersebut dimasukan ke persamaan interpolasi lagrange akan menghasilkan
.Cobalah untuk menyelesaikan soal yang sama dengan interpolasi newton! Hasilnya pasti akan sama dengan hasil yang di dapatkan interpolasi lagrange.
Sekarang saatnya kita untuk mencoba mengimplementasikan interpolasi lagrange ke dalam python.
Interpolasi Polinomial Lagrange dengan Python
Dari penjelasan diatas dapat dibentuk fungsi python seperti iniReferensi: