Prof. Drs. T. Basaruddin, Ph.D.

Video ini membahas konsep Interpolasi Newton dalam Analisis Numerik. Basis Newton digunakan sebagai alternatif terhadap basis Lagrange karena lebih efisien dalam komputasi. Basis Newton memiliki pola rekursif yang memudahkan konstruksi sistem persamaan linear. Dalam penghitungan nilai polinomial, Interpolasi Newton lebih efisien dibandingkan dengan Lagrange karena jumlah perkaliannya lebih sedikit. Meskipun konstruksi awalnya membutuhkan biaya, namun dalam penggunaan praktisnya untuk interpolasi titik-titik data, Interpolasi Newton cenderung lebih efisien dan lebih menguntungkan.

Sekarang kita akan lihat basis yang ketiga, yaitu basis Newton.

Ada dua masalah ataupun komplikasi dengan basis lagang, meskipun sekilas tadi itu begitu

Straightforward, begitu gampangnya karena koefisiennya langsung kita temukan, tapi ternyata ada dua.

Pertama, tadi seperti saya sudah sebutkan sebelumnya bahwa secara komputasi dia lebih mahal

karena masing-masing L itu membutuhkan n multiplication atau perkalian dan basisnya itu ada n plus 1

berarti ada n plus 1 kali n atau n kuadrat perkalian, ini yang membuat dia menjadi mahal.

Pada saat komputasi, bukan pada saat konstruksi.

Pada persoalan yang berikutnya adalah, apabila ada data sisi pen baru, kita tambahkan data baru

misalnya, eh ternyata ada informasi baru untuk data ke n plus 2, jadi tadinya X0 sampai Xn saja

ternyata ada Xn plus 1 baru menyusul. Apa yang harus kita lakukan?

Untuk basis lagang maka semua basis itu harus dihitung ulang, tidak ada yang tidak berubah

jadi semuanya akan berubah akibat dari kehadiran data baru ini.

Kenapa demikian? Karena kalau kita lihat rumus dari basis lagang tadi, dia akan tergantung pada seluruh titik data.

Kan yang di atas tadi, X dikurang XI kecuali dirinya sendiri.

Tapi dirinya sendiri itu akan menentukan yang di bawah sebagai pembagi tadi.

Jadi artinya secara keseluruhan nilai X dari X0 sampai ke X yang terakhir, itu akan menentukan basis.

Memang basis tidak tergantung pada Y, tapi dia bergantung pada X.

Nah ini dicoba untuk di handle ataupun ditangani dengan basis Newton.

Nah basis Newton adalah sebagai berikut, basis pertamanya itu adalah 1.

Jadi kayak model basis standar bahwa basis pertamanya adalah 1.

Basis yang kedua itu adalah X dikurangi dengan X yang pertama, X0.

Basis yang ketiga, ini indeks saya berbeda 1 dengan ini, adalah X dikurang X0 dikalikan dengan X dikurang X1.

Nah perhatikan bahwa dari tiga ini kita sudah melihat pola, oh ternyata basis yang ke I

itu akan sama dengan basis yang ke I-1 dikalikan dengan X dikurang XI-1.

Jadi kalau di sini 1, disini 2 misalnya, maka ini kan N1 dikalikan X dikurang X1, indeks ini berbeda 1.

Jadi kalau di sini basis ke I, berarti N ke I-1 dikalikan X dikurang XI-1.

Nah recursive atau rumus recursive ini berlaku mulai dari N1,

N1 berarti N0 dikalikan X dikurang X0, benar karena N0 nya adalah 1.

N2 berarti N1 dikalikan X dikurang X1, benar karena N1 nya X dikurang X0, dan seterusnya.

Nah sekarang seperti apa jadinya sistem persamaan linear nya kalau kita menggunakan Newton.

Jadi ini adalah koefisiennya A0, A1 sampai dengan AN sama dan ini adalah ruas kanannya sama, Y0, Y1 sampai YN.

Nah karena basis pertamanya adalah 1, maka di sini pasti akan 1 semua kolom pertamanya.

Basis kedua atau kolom kedua itu adalah X dikurang X0.

Ingat bahwa baris itu akan menentukan X yang mana yang kita pakai.

Jadi pada saat di baris pertama, ini kan X0 yang kita pakai,

karena baris kedua X1 dan baris terakhir adalah XN.

Berarti ini akan sama dengan 0, kenapa? Ini akan X0 dikurang X0.

Basis keduanya karena ada X dikurang X0 di sini juga akan 0.

Nah di bawah sini pasti memang kita akan punya X1 dikurang X0,

karena basis pertama kan N1, basis kedua adalah X dikurang X0.

Berarti pada saat baris kedua dia X1 dikurang X0.

Di baris ketiganya nanti adalah X2 dikurang X0, di sini adalah XN dikurang X0.

Nah sekarang bagaimana dengan kolom ke I?

Jadi ini kalau ada kolom ke I, maka hanya akan survive itu di baris ke I.

Karena di baris yang atasnya dia akan 0, pasti akan memuat X dikurang XI.

Jadi kita akan mendapati harga yang tidak 0 itu hanya dari diagonal ke bawah.

Perhatikan kalau NI, ini kan seperti ini bentuknya.

Berarti kita akan dapatkan ini adalah NI XI.

Lihat pola, di sini adalah N0, ini adalah N1 semua.

Oke, pada kolom ke 0 dia adalah N0, pada kolom ke 1 adalah N1, pada kolom ke I adalah NI.

Lihat pola, N1 di kolom kedua, masukkan X0 0, masukkan X1, X1 kurang X0, masukkan XN, XN kurang X0.

Jadi kolom-kolom ini adalah basis sebetulnya.

Jadi yang terakhir ini di bawah adalah NI XN.

Kolom terakhir yang hanya tidak 0 itu adalah di sini aja, yaitu NN XN.

Jadi basis ke N, masukkan, substitusikan XN.

Berarti kalau Anda ingin mengkonstruksikan matrix coefficient untuk Newton,

maka Anda membutuhkan tool atau fungsi mengkonstruksikan basisnya.

Jadi basisnya ini dikonstruksikan menggunakan suatu fungsi, kemudian inilah yang akan kita jadikan sebagai kolomnya.

Jadi kolom pertama, basis pertama, kolom kedua, basis kedua, dan sampai terakhir.

Kemudian baris itu akan menentukan substitusi X yang mana, yang akan kita substitusikan.

Nah, perhatikan bahwa matrix ini berupa segitiga bawah.

Kalau dia segitiga bawah, maka kita sudah tahu bagaimana mencari ini dan kosnya hanya N kuadrat per dua.

Jadi memang dia tidak semahal yang basis standar,

tapi dia lebih mahal dari lagrang untuk konstruksi.

Tapi kalau untuk komputasi, perhatikan bahwa Pnx nanti akan sama dengan N0.

Ini ada A0 N0X yaitu 1 ditambah A1 N1X dan AN NNX.

Nah, perhatikan bahwa kalau saya ingin melakukan substitusi X tertentu di sini,

komputasinya atau kalkulasi dari nilai P, maka ini tidak ada perkalian di sini karena satu,

di sini hanya ada X yang masuk di sini dikurang X0 dan seterusnya.

Jadi jumlah perkaliannya hanya N kuadrat per dua, yaitu satu tambah dua tambah tiga dan seterusnya sampai yang terakhir itu adalah N.

Jadi dari sisi kalkulasi nilai polinomialnya ini lebih murah, yang Newton setengah dari lagrang.

Tapi pada saat kita mengkonstruksikan, karena saya harus mencari A0 sampai AN,

memang ada cost di sini. Tapi dalam kebutuhan interpolasi, biasanya ini cuma sekali kita hitung,

sedangkan menginterpolasi di titik-titik yang lain itu bisa berkali-kali kita butuhkan.

Misalnya dalam bentuk fitting, jadi kita akan refine datanya tadi to course, jaraknya cukup lebar,

saya ingin mencari berapa titik-titik di antaranya gitu. Jadi berkali-kali ini harus dilakukan kalkulasi.

Jadi yang bagian mahalnya lagrang tadi itu bisa ditekan oleh Newton dalam konteks ini.

Jadi secara overall Newton akan lebih menarik untuk diterapkan atau digunakan.