Mengenal Apa itu Interpolasi Polinomial

Prodi : Teknik Informatika

Lembaga : UIN Maulana Malik Ibrahim Malang

Interpolasi Polinomial

Interpolasi polinomial merupakan teknik interpolasi dengan mengasumsikan pola data yang kita miliki mengikuti pola polinomial baik berderajat satu (linier) maupun berderajat tinggi. Interpolasi dengan metode ini dilakukan dengan terlebih dahulu membentuk persamaan polinomial. Persamaan polinomial yang terbentuk selanjutnya digunakan untuk melakukan interpolasi dari nilai yang diketahui atau ekstrapolasi (prediksi) dari nilai diluar rentang data yang diketahui.

Pada Chapter 8.1 pembahasan akan dibagi menjadi 3 bagian. Bagian pertama kita akan mengulang kembali teknik evaluasi polinomial, sedangkan dua bagian selanjutnya akan membahas teknik interpolasi linier dan polinomial orde tinggi dengan menjadikan pembahasan bagian pertama sebagai dasar pada dua bagian berikutnya.

1. Mengevaluasi Polinomial

Pada Chapter ini pembaca akan mempelajari teknik untuk melakukan substitusi nilai \(x\) pada persamaan polinomial untuk memperoleh nilai \(y\). Terdapat berbagai pendekatan dalam melakukan proses tersebut, mulai dari metode naive maupun metode Horner. Kedua metode akan menghasilkan hasil yang sama namun dengan proses komputasi yang berbeda. Metode naive cenderung lambat dalam proses komputasi karena jumlah proses yang dilakukan dalam sekali proses lebih banyak dari pada metode Horner.

Untuk memahami metode-metode evaluasi polinomial yang telah disebutkan tersebut, secara umum persamaan polinomial disajikan pada Persamaan (8.1).

dimana \(a\) merupakan koefisien polinomial, \(x\) merupakan variabel, dan \(n\) merupakan indeks dan pangkat polinomial.

Pada metode naive kita melakukan evaluasi polinomial sama dengan cara kita melakukan evaluasi polinomial saat kita SMA. Nilai \(x\) akan disubstitusikan pada masing-masing elemen persamaan polinomial. Masing-masing elemen polinomial selanjutnya dijumkahkan untuk menghitung \(y\).

Pada R kita dapat menuliskan sebuah fungsi untuk melakukan evaluasi polinomial menggunakan metode naive tersebut. Pada fungsi tersebut, koefisien polinomial akan disimpan kedalam sebuah vektor dengan urutan pengisian mulai dari koefisien dengan pangkat \(x\) terendah ke tertinggi.

naive_poly <- function(x, coeff){
  n <- length(x)
  y <- rep(0, n)
  
  for(i in 1:length(coeff)){
    y <- y + coeff[i]*(x^(i-1))
  }
  
  return(y)
}

Contoh 8.1 Hitung nilai \(y\) pada persamaan \(f(x)=x4+3x3−15x2−19x+30\), jika diketahui nilai \(x\) adalah -1, 0, dan 1!

Jawab:

Untuk dapat menghitung nilai \(y\) menggunakan fungsi naive_poly() pada persamaan tersebut dengan nilai $x$ diketahui, kita perlu merubah koefisien persamaan tersebut dan nilai \(x\) yang diketahui menjadi vektor:

x <- c(-1,0,1)
coeff <- c(30,-19,-15,3,1)

Masukkan vektor-vektor yang telah terbentuk tersebut kedalam fungsi naive_poly().

naive_poly(x, coeff)

## [1] 32 30  0

Berdasarkan hasil perhitungan diperoleh nilai \(y\) masing-masing sebesar 32, 30, dan 0. Pembaca dapat mengeceknya sendiri hasil perhitungan tersebut menggunakan cara manual.

Kita dapat meningkatkan efisiensi proses perhitungan pada fungsi naive_poly() tersebut. Sebagai contoh, setiap kali kita melakukan loop untuk menghitung nilai \(y\) pada polinomial, kita dapat memperoleh eksponensial dari \(x\). Namun untuk setiap koefisien \(ai\), nilai eksponensial yang terkait \(xi\) merupakan seri produk.

Untuk \(x^i\), terdapat sebanyak \(i\) koefisien \(x\) dikalikan bersamaan. Namun, untuk setiap xi−1xi−1 terdapat lebih sedikit 1 perkalian dibanding koefisien xx dengan pangkat yang lebih besar dan seterusnya.

Berdasarkan ilustrasi tersebut, kita dapat membentuk fungsi better_poly() sebagai perbaikan dari fungsi naive_poly(). Berikut adalah sintaks yang digunakan:

better_poly <- function(x, coeff){
  n <- length(x)
  y <- rep(0, n)
  cached_x <- 1
  
  for(i in 1:length(coeff)){
    y <- y + coeff[i]*cached_x
    cached_x <- cached_x * x
  }
  return(y)
}

Contoh 8.2 Hitung nilai \(y\) pada persamaan yang disajikan pada Contoh 8.1 menggunakan nilai \(x\) yang telah diketahui pada soal tersebut menggunakan fungsi better_poly()?

Jawab:

better_poly(x, coeff)

## [1] 32 30  0

Sejauh ini kita telah membentuk 2 fungsi yaitu naive_poly() dan better_poly(). Kedua fungsi tersebut memiliki perbedaan proses menghitung yang mempengaruhi efisiensinya masing-masing. Sebagai contoh jika diberikan polinomial berderajat 10, fungsi naive_poly() akan mengejakan perkalian dalam proses loop sebanyak 55 kali, sedangkan fungsi better_poly() akan melakukannya sebanyak 20 kali ($ perkalian).

Metode lain yang lebih efisien dalam melakukan evaluasi polinomial adalah metode Horner. Metode ini oleh William Horner pada abad ke-18. Dalam metode Horner, bentuk polinomial pada Persamaan (8.1) akan ditransformasi menjadi Persamaan (8.3).

Berdasarkan Persamaan (8.3), jika kita melakukan perhitungan pada persamaan polinomial berderajat 10, kita dapat mereduksi perhitungan menjadi 10 perkalian dan 10 penjumlahan. Jumlah tersebut sangat kecil dibandingkan kedua metode sebelumnya dan dapat dikatakan lebih efisien dibandingkan metode lainnya.

FUngsi horner_poly() merupakan fungsi yang dibentuk bedasarkan Persamaan (8.3). Sintaks fungsi tersebut adalah sebagai berikut:

horner_poly <- function(x, coeff){
  n <- length(x)
  y <- rep(0, n)
  
  for(i in length(coeff):1){
    y <- coeff[i] + x * y
  }
  return(y)
}

Contoh 8.3 Kerjakan kembali Contoh 8.2 fungsi horner_poly()?

Jawab:

horner_poly(x, coeff)

## [1] 32 30  0

2. Interpolasi Linier

Misalkan kita memiliki 3 buah data dengan dua buah variabel kita misalkan variabel \(x\) dan variabel \(y\). Pada salah satu data terdapat data yang hilang pada. Agar ketiga data tersebut tetap dapat digunakan dalam iterasi diperlukan interpolasi untuk “menebak” nilai dari data yang hilang.

Berdasarkan pengukuran yang sebelumnya pernah dilakukan diketahui bahwa pola data yang terbentuk variabel \(x\) dan \(y\) divisualisasikan menggunakan scatterplot adalah pola linier. Berdasarkan hal tersebut interpolasi dilakukan dengan menggunakan metode linier.

Interpolasi linier dilakukan dengan terlebih dahulu membentuk fungsi linier. Dengan kata lain kita perlu mencari nilai slope \(m\) dan intercept \(b\). Nilai \(m\) dihitung sebagai rasio selisih jarak dua titik pada sumbu \(y\) dan sumbu \(x\) yang dapat dituliskan melalui Persamaan (8.4).

Nilai intercept (titik potong pada sumbu \(y\)) dihitung menggunakan Persamaan (8.5).

---

Algoritma Interpolasi Linier

1. Tentukan dua buah titik \((x,y)\) sebagai dasar pembentukan persaman linier.

2. Hitung \(m\) menggunakan Persamaan (8.4)

3. Hitung \(b\) menggunakan Persamaan (8.5)

4. Definiskan fungsi linier berdasarkan nilai \(m\) dan \(b\)

5. Hitung \(y\) dengan cara substitusi nilai \(x\) pada persamaan linier untuk melakukan interpolasi atau ekstrapolasi nilai \(y\) yang ingin dicari.

---

Algoritma poin 1 sampai 4 tersebut, kita dapat membentuk fungsi pembentuk persamaan linier dari 2 titik yang diketahui. Fungsi tersebut disajikan pada sintaks berikut:

linear_inter <- function(x, y){
  m <- (y[2]-y[1]) / (x[2]-x[1])
  b <- y[2] - m*x[2]
  
  return(c(b, m))
}

Contoh 8.4 Diketahui koordinat 2 buah titik yaitu (0,-1) dan (2,3). Jika diketahui titik ketiga memiliki koordinat sumbu xx sebesar 1. Lakukan interpolasi untuk menentukan koordinat sumbu \(y\) titik ketiga tersebut!

Jawab:

Berdasarkan data-data yang terdapat pada soal terserbut, kita dapat menghitung nilai \(m\) dan \(b\). Nilai \(m\) dapat dihitung sebagai berikut:

Dengan menggunakan nilai \(m\) tersebut kita dapat menghitung nilai \(b\).

Berdasarkan hasil perhitungan diperoleh persamaan linier yang terbentuk adalah sebagai berikut:

Berdasarkan persamaan linier tersebut nilai \(y\) dapat dihitung.

Kita dapat pula membentuk persamaan linier menggunakan fungsi linear_inter(). Berikut adalah sintaks yang digunakan:

x <- c(0,2)
y <- c(-1,3)

(coeff <- linear_inter(x,y))

## [1] -1  2

Setelah diperoleh koefisien persamaan linier berdasarkan dua titik tersebut, kita akan menggunakan fungsi horner_poly() untuk memperoleh nilai \(y\). Berikut adalah sintaks yang digunakan:

horner_poly(1, coeff)

## [1] 1

Hasil interpolasi yang diperoleh dapat dikatakan sesuai dengan lokasi kedua titik data yang ditunjukkan pada Gambar 8.1. Berdasarkan hal tersebut, kita dapat yakin bahwa hasil interpolasi yang telah kita lakukan telah sesuai.

Metode interpolasi linier dapat dibilang merupakan metode interpolasi yang sangat sederhana. Disamping kemudahannya, metode ini memiliki potensi error numerik jika jarak antara kedua titik cukup berdekatan terlebih lagi jika selisih penyebut ($x2−x1) sangat kecil sehingga akan menghasilkan nilai yy yang sangat besar.

Disamping adanya potensi error numerik tersebut, metode ini menjadi dasar bagi metode interpolasi lain yang lebih kompleks. Metode selanjutnya merupakan pengembangan dari metode interpolasi ini.

3. Interpolasi Polinomial Orde Tinggi

Dengan menggunakan dua titik, kita dapat membentuk garis lurus (linier) yang tepat pada dua titik tersebut. Masalah timbul jika selisih nilai \(x\) kedua titik tersebut sangat kecil atau kedua titik tersebut memiliki nilai \(x\) yang sama. Hal ini akan menyebabkan slope yang dihasilkan menjadi tidak terhingga atau garis yang terbentuk adalah garis vertikal tegak lurus.

Bagaimana jika terdapat tiga buah titik? apakah kita masih bisa menggunakan interpolasi linie?. Ya, asalkan ketiga titik tersebut membentuk pola linier atau terletak pada satu garis yang sama. Pada kenyatannya kondisi tersebut jarang terjadi, sehingga pendekatan menggunakan polinomial orde lebih tinggi diperlukan. Persamaan kuadratik (polinomial orde dua) dapat digunakan untuk membentuk persamaan polinomial pada ketiga titik tersebut, sehingga iterasi dapat dilakukan. Untuk 4 buah titik data, polinomial orde tiga dapat digunakan untuk melakukan interpolasi. Secara umum berdasarkan penjelasan tersebut, untuk nn titik data interpolasi dapat dilakukan menggunakan persamaan polinomial orde \(n−1\).

Diberikan set data berpasangan yang telah diurutkan \((xi,yi)\), fungsi interpolasi harus memenuhi persyaratan berikut:

Untuk setiap \(i\). Sebagai tambahan, fungsi interpolasi berupa fungsi polinomial dengan bentuk umum sebagai berikut:

Persamaan (8.7) dapat dituliskan kedalam bentuk matriks yang ditampilkan pada Persamaan (8.8).

Persamaan matrik tersebut dapat dituliskan sebagai \(Xβ=y\). Untuk menyelesaikan persamaan tersebut (memperoleh nilai \(β\)), pembaca dapat membaca kembali Chapter 6. Matriks \(X\) disebut sebagai matriks Vandemonde dan matriks tersebut mengandung sejumlah nilai \(x\) dengan pangkat sampai dengan \(n\).

---

Algoritma Interpolasi Polinomial Orde Tinggi

1. Tentukan set titik berpasangan \((x,y)\) yang telah diurutkan.

2. Bentuk matriks Vandermonde sesuai dengan Persamaan (8.8).

3. Definiskan persamaan matriks \(Xβ\)

4. Selesaikan persamaan matriks pada poin 3 untuk memperoleh nilai \(β\)

5. Definisikan persamaan polinomial berdasarkan koefisien \(β\) yang diperoleh

6. Lakukan substitusi \(x\) persamaan polinomial pada poin 5 untuk memperoleh nilai \(y\)

---

Berdasarkan algoritma poin 1 sampai 5, kita dapat membentuk suatu fungsi untuk membentuk persamaan polinomial berdasarkan Persamaan (8.8). Berikut adalah sintaks fungsi tersebut:

poly_inter <- function(x, y){
  if(length(x) != length(y))
    stop("Lenght of x and y vectors must be the same")
  
  n <- length(x)-1
  vandermonde <- rep(1, length(x))
  for(i in 1:n){
    xi <- x^i
    vandermonde <- cbind(vandermonde, xi)
  }
  beta <- solve(vandermonde, y)
  
  names(beta) <- NULL
  return(beta)
}

Contoh 8.5 Diketahui koordinat 3 buah titik yaitu (-1,-2), (1,2) dan (0,1). Jika diketahui titik keempat memiliki koordinat sumbu xx sebesar -2. Lakukan interpolasi untuk menentukan koordinat sumbu yy titik keempat tersebut!

Jawab:

Untuk menyelesaiakn contoh soal tersebut, kita perlu terlebih dahulu membentuk matriks sesuai dengan Persamaan (8.8). Berdasarkan soal tersebut, terdapat tiga buah titik data yang diketahui, sehingga polinomial yang hendak dibentuk selanjutnya adalah polinomial berderajat 2.

Setelah matriks tersebut terbentuk, pembaca dapat menyelesaikannya menggunakan berbagai metode yang telah penulis jelaskan pada Chapter 6 untuk memperoleh nilai \(β\).

Untuk menyelesaikan contoh soal tersebut pada R, kiat perlu membentuk matriks \(x\) dan \(y\) terlebih dahulu.

x <- c(-1, 1, 0)
y <- c(-2, 2, -1)

Koefisien persamaan polinomial dihitung menggunakan fungsi poly_inter().

(coeff <- poly_inter(x, y))

## [1] -1  2  1

Berdasarkan hasil perhitungan, diperoleh nilai \(β\). Nilai tersebut selanjutnya digunakan untuk membentuk persamaan polinomial. Berikut merupakan persamaan polinomial yang terbentuk:

Fungsi horner_poly() selanjutnya digunakan untuk mengevaluasi polinomial tersebut. Berikut adalah hasil substitusi \(x\) pada persamaan tersebut:

horner_poly(-2, coeff)

## [1] -1

Hasil yang diperoleh terlihat cukup sesuai jika kita perhatikan visualisasi ketiga titik tersebut pada Gambar 8.2.

Contoh 8.6 Dengan menggunakan data pada Contoh 8.4, lakukan proses perhitungan untuk membentuk persamaan polinomial menggunakan fungsi poly_inter()

Jawab:

Berdasarkan data pada Contoh 8.4, polinomial yang terbentuk merupakan polinomial derajat 1 (linier). Berikut adalah nilai koefisien yang dihasilkan dari perhitungan menggunakan fungsi poly_inter().

x <- c(2, 0)
y <- c(3, -1)
poly_inter(x, y)

## [1] -1  2

Meskipun proses perhitungan menggunakan fungsi poly_inter() lebih rumit dibandingkan dengan fungsi linear_poly(), hasil perhitungan keduanya menggunakan data pada Contoh 8.4 menghasilkan hasil yang sama.

REFERENSI:

https://bookdown.org/moh_rosidi2610/Metode_Numerik/interpolation.html#poliinterpolation