Metode Numerik
Catatan Kuliah
BAB 3 Interpolasi 1. Beda Hingga 2. Interpolasi Linear dan Kuadrat 3. Interpolasi Beda-Maju dan Beda-Mundur Newton 4. Polinom Interpolasi Beda Terbagi Newton 5. Polinom Interpolasi Lagrange
1
Metode Numerik
Catatan Kuliah
1. Beda Hingga Misalkan diberikan suatu tabel nilai-nilai numeris fj = f(xj) dari suatu fungsi f pada titik-titik yang berjarak sama, x0, x1 = x0 + h, x2 = x0 + 2h,
x3 = x0 + 3h, …
dengan h > 0 tetap. Fungsi f(xi) bisa berupa hasil suatu rumus atau nilai yang diperoleh secara empiris dari percobaan. Beda-beda pertama dari fungsi f diperoleh dengan mengurangkan tiap nilai fungsi f(x) untuk x berikutnya yang lebih besar dalam tabel. Beda-beda kedua dari fungsi f diperoleh dengan mengurangkan tiap nilai beda pertama dari fungsi f(x) untuk x berikutnya yang lebih besar dalam tabel. Seterusnya sehingga dalam tabel beda, setiap beda dimasukan ke dalam kolom yang sesuai, ditengah-tengah antara elemen-elemen kolom sebelumnya dari mana beda itu dibangun. Titik (koma) desimal dan nol pemula dari beda-beda itu boleh dihilangkan. 2
Metode Numerik
Catatan Kuliah
Terdapat tiga notasi untuk beda-beda yang terjadi dalam suatu tabel beda. A. Beda-beda Pusat Bentuk tabel beda-beda pusat sebagai berikut: x
f(x)
x− 2 x−1 x0
f −2
x1 x2
f1
Beda Pertama
Beda Kedua
Beda Ketiga
δf −3
f −1 f0
δ 2 f −1 δ 2 f0 δ 2 f1
2
δ f −1 2
δf1 2
δf 3
f2
δ 3 f −1 2 3
δ f1 2
2
Secara umum diperoleh,
δf
m+
1 2
= f m +1 − f m
δ 2 f m = δf
1 m+ 2
− δf
Indeks beda di kiri adalah rataan indeks beda di kanan m−
1 2
3
Metode Numerik
Catatan Kuliah
B. Beda-beda Maju Bentuk tabel beda-beda maju sebagai berikut: x
f(x)
x− 2 x−1 x0 x1 x2
f −2 f −1 f0 f1 f2
Beda Pertama
Beda Kedua
Beda Ketiga
∆ f−2 ∆ f −1
∆2 f −2
∆ f0 ∆ f1
∆ f −1
2
∆3 f −2
2
∆3 f −1
∆ f0
Secara umum diperoleh,
∆f m = f m +1 − f m
∆2 f m = ∆f m +1 − ∆f m
Beda-beda dengan indeks yang sama terletak pada garis yang miring ke bawah atau maju pada tabel
4
Metode Numerik
Catatan Kuliah
Algoritma Beda-beda maju Diberikan xj, ∆0 f j = f j = f ( x j ), j = 0, 1, 2, ..., n Untuk k = 1, 2, …, n lakukan untuk m = 0, 1, …, n – k, lakukan
∆k f m = ∆k −1 f m +1 − ∆k −1 f m C. Beda-beda Mundur Bentuk tabel beda-beda mundur sebagai berikut: x
f(x)
x− 2 x−1 x0
f −2
x1 x2
f1
f −1 f0 f2
Beda Pertama
∇ f −1 ∇ f0 ∇ f1 ∇ f2
Beda Kedua
∇2 f 0 2
∇ f1 ∇2 f 2
Beda Ketiga
∇3 f1 ∇3 f 2
5
Metode Numerik
Catatan Kuliah
Secara umum diperoleh, Beda-beda dengan indeks yang sama terletak pada garis yang miring ke atas atau mundur pada tabel
∇f m = f m−1 − f m
∇ 2 f m = ∇f m −1 − ∇f m
Kaitan dari ke tiga notasi beda-beda di atas adalah :
δ n f m = ∆n f
m−
n 2
= ∇n f
m+
n 2
Contoh 3.1 Nilai dan beda dari f(x) = 1/x, x = 1 (0.2) 2, 4D x
f(x)
1 .0
1.0000
1 .2 1 .4 1 .6
0.8333 0.7143 0.6250
1 .8 2 .0
0.5556 0.5000
Beda Beda Pertama Kedua − 1667 − 1190 − 893 − 694 − 556
477 297 199 138
Beda Ketiga − 180 − 98 − 61
Beda Keempat
82 37
Catatan, bila ditetapkan x0 = 1.6, maka diperoleh -0.0893 = δf −1 2
= ∆f −1 = ∇f 0 6
Metode Numerik
Catatan Kuliah
2. Interpolasi linear dan Kuadrat Diberikan tabel nilai suatu fungsi f(x), seringkali untuk mencari nilai-nilai f(x) untuk nilai x diantara nilai-nilai x yang muncul dalam tabel tersebut. Masalah untuk memperoleh nilai f(x) demikian disebut Interpolasi. Nilai-nilai f(x) yang ditabulasikan dan digunakan dalam proses ini disebut nilai-nilai pivotal. Metode interpolasi biasanya didasarkan pada asumsi bahwa disekitar nilai x yang dipertanyakan, fungsi f(x) dapat dihampiri oleh polinom p(x), yang nilainya pada x tersebut merupakan hampiran dari nilai fungsi f(x). Interpolasi linear Iterpolasi linear adalah metode interpolasi yang paling sederhana. Kurva fungsi f dihampiri dengan suatu tali busur pada dua nilai tabulasi yang berdekatan x0 dan x1.
f(x) f0
p1(x) h
f1
rh x0
x
x1
Hampiran f pada x = x0 + rh adalah
f ( x) ≈ p1 ( x) = f 0 + r ( f1 − f 0 ) = f 0 + r∆f 0
x − x0 Dimana : r = , 0 ≤ r ≤1 h
7
Metode Numerik
Catatan Kuliah
Interpolasi linear sering digunakan untuk menghitung tabel logaritma dan fungsi trigonometri. Interpolasi linear akan memberikan hasil yang baik selama nilai-nilai x dalam tabel sedemikian dekatnya sehingga talibusur-talibusur menyimpang dari kurva f(x) cukup kecil, katakanlah kurang dari ½ satuan angka terakhir dalam tabel untuk setiap x diantara x0 dan x1. Galat untuk iterpolasi linear adalah ε ( x) = p1 ( x) − f ( x) = f 0 + r ( f1 − f 0 ) − f ( x) 2 Taksiran galat tersebut adalah : ε ( x) ≤ 18 h M 2
Dimana f(x) mempunyai turunan kedua pada x0 ≤ x ≤ x1 dan f’’(x) terbatas dengan f ' ' ( x) ≤ M 2 Interpolasi kuadrat Pada interpolasi kuadrat, kurva fungsi f diantara x0 dan x2 = x0 + 2h dengan parabola kuadrat yang melalui titik-titik (x0, f0), (x1, f1), (x2, f2) sehingga mendapatkan rumus yang lebih teliti. r (r − 1) f ( x) ≈ p2 ( x) = f 0 + r ( f1 − f 0 ) + ( f 2 − 2 f1 + f 0 ) = f 0 + r∆f 0 + r (r − 1) ∆2 f 0 2 2 x − x0 dimana,
r=
h
, 0≤r ≤2
8
Metode Numerik
Catatan Kuliah
Contoh 3.2 Diketahui nilai ln 9.0 = 2.1972 dan nilai ln 9.5 = 2.2513. Tentukan nilai ln 9.2. Jawab Diperoleh r = 0.2 / 0.5 = 0.4, sehingga ln 9.2 = ln 9.0 + 0.4 ( ln 9.5 – ln 9.0) = 2.1972 + 0.4 ( 2.2513 – 2,1972) = 2.2188 (eksak sampai 3D)
Contoh 3.3 Diketahui nilai ln 9.0 = 2.1972, ln 9.5 = 2.2513 dan nilai ln 10.0 = 2.3026. Tentukan nilai ln 9.2. Jawab Diperoleh r = 0.2 / 0.5 = 0.4, sehingga ln 9.2 = ln 9.0 + 0.4 ( ln 9.5 – ln 9.0)+ (1/2)(0.4)(-0,6)(ln 10.0-(2)(ln 9.5)+ln 9.0) = 2.197 + 0.4 ( 2.251 – 2,197) +(-0.12)(2.3026 – (2)2.2513 + 2.1972) = 2.2192 (eksak sampai 4D) 9
Metode Numerik
Catatan Kuliah
3. Interpolasi Beda Maju dan Beda Mundur Newton Hampiran lebih teliti diperoleh bila menggunakan polinom yang derajatnya lebih tinggi. Polinom pn(x) berderajat n ditentukan secara tunggal oleh n+1 nilai xi, i = 0, 1, 2, …, n, yang berlainan, sedemikian sehingga diperoleh, pn(x0) = f0 , pn(x1) = f1, …, pn(xn) = fn dengan f(x0) = f0 , f(x1) = f1, …, f(xn) = fn Polinom ini diberikan dalam rumus interpolasi beda-maju Newton:
f ( x) ≈ pn ( x) = f 0 + r∆f 0 +
r (r − 1) 2 r (r − 1)...(r − n + 1) n ∆ f 0 + ... + ∆ f0 2! n!
r = ∑ ∆s f 0 s =0 s x − x0 Dimana : r = , 0≤r ≤n h r r (r − 1)(r − 2)...(r − s + 1) = s! s n
adalah koefisien-koefisien binomial dari pn(x) 10
Metode Numerik
Catatan Kuliah
Bukti. Akan ditunjukkan bahwa pn(xk) = fk untuk k = 0, 1, 2, …, n. Tetapkan terlebih dahulu r = k, sehingga diperoleh x = x0 + rh = x0 + kh = xk. k k dan f k = pn ( xk ) = ∑ ∆s f 0 s =0 s
k k f k = f 0 + k∆f 0 + ∆2 f 0 + ... + ∆k f 0 2 k
Pembuktian secara induksi, (i). Untuk k = 0 maka f0 = f0, sehingga rumus benar untuk k = 0. q
q
q
q
(ii). Misalkan rumus benar untuk k = q, yaitu f q = f 0 + ∆f 0 + ∆2 f 0 + ... + ∆q f 0 0 1 2 q maka akan ditunjukkan benar untuk k = q +1.
f q +1 = f q + ∆f q q q 2 q 3 q q+1 q q q 2 q q ∆ f 0 + ∆ f + ∆ f + ∆ f + ... + = f 0 + ∆f 0 + ∆ f 0 + ... + ∆ f 0 0 0 0 0 1 2 q 0 1 2 q q q q + 1 s = sehingga Pada rumus ini, ∆ f 0 mempunyai koefisien + s s − 1 s q + 1 q + 1 q + 1 2 q + 1 q +1 f 0 + ∆f 0 + ∆ f 0 + ... + ∆ f 0 f q +1 = 0 1 2 q + 1 11
Metode Numerik
Catatan Kuliah
Galat yang terlibat dalam interpolasi maju Newton adalah
ε ( x ) = pn ( x ) − f ( x ) =
1 ( x − x0 )...( x − xn ) f ( n +1) (t ) (n + 1)!
( n +1)
Dengan f adalah turunan ke-(n+1) dari fungsi f dan t terletak dalam interval yang titik-titik ujungnya adalah nilai terkecil dan terbesar dari nilai-nilai x0, x1, …, xn, x. Algoritma Rumus Interpolasi Beda-maju Newton Diberikan xj = x0 + jh, j = 0, 1, 2, … dan nilai-nilai fungsi yang berpadanan yaitu ∆0 f j = f j = f ( x j ) . Juga diberikan nilai xˆ Tetapkan Hitung
p0 ( xˆ ) = f 0
r=
xˆ − x0 h
Untuk k = 0, 1, 2, …, sampai penghentian, lakukan
r k +1 ∆ f 0 pk +1 ( xˆ ) = pk ( xˆ ) + k + 1 Periksa untuk penghentian 12
Metode Numerik
Catatan Kuliah
Contoh 3.4 Memakai nilai-nilai dari tabel berikut xi 2.0 2.1 2.2 2.3 2.4 f(xi) 1.414214 1.449138 1.483240 1.516575 1.549193 Terapkan rumus interpolasi beda maju Newton untuk mencari f(2.05) dan f(2.15). Jawab a. Untuk x = 2.05, tetapkan x0 = 2.0 sehingga r = 0.05 / 0.1 = 0.5 r (r − 1) r (r − 1)(r − 2) ( f 2 − 2 f1 + f 0 ) + ( f 3 − 3 f 2 + 3 f1 − f 0 ) 2! 3! r (r − 1)(r − 2)(r − 3) + ( f 4 − 4 f 3 + 6 f 2 − 4 f1 + f 0 ) 4! = 1.431782
f (2.05) ≈ p4 (2.05) = f 0 + r ( f1 − f 0 ) +
b. Untuk x = 2.15, tetapkan x0 = 2.1 sehingga r = 0.05 / 0.1 = 0.5 f (2.15) ≈ p3 (2.15) = f 0 + r ( f1 − f 0 ) +
r (r − 1) r (r − 1)(r − 2) ( f 2 − 2 f1 + f 0 ) + ( f 3 − 3 f 2 + 3 f1 − f 0 ) 2! 3!
= 1.466268 13
Metode Numerik
Catatan Kuliah
Sedangkan rumus untuk interpolasi beda mundur Newton adalah:
f ( x ) ≈ p n ( x ) = f 0 + r∇f 0 +
r (r − 1) 2 r (r − 1)...(r − n + 1) n ∇ f 0 + ... + ∇ f0 2! n!
r = ∑ ∇ s f 0 s =0 s x − x0 Dimana : r = , 0≤r ≤n h r r (r − 1)(r − 2)...(r − s + 1) = s! s n
adalah koefisien-koefisien binomial dari pn(x)
Rumus interpolasi lain yang menggunakan beda hingga adalah rumus Everett Rumus ini melibatkan beda-beda hingga tingkat genap. Rumus Everett yang paling sederhana adalah: (2 − r )(1 − r )(− r ) 2 (r + 1)r (r − 1) 2 f ( x) ≈ (1 − r ) f 0 + rf1 + δ f0 + δ f1 3! 3! x − x0 Dimana : r = , 0 ≤ r ≤1 h 14
Metode Numerik
Catatan Kuliah
Untuk membuat penerapannya mudah, tabel-tabel fungsi biasanya menyertakan beda-beda kedua yang diperlukan. Galatnya adalah
r + 1 ( 4 ) f (t ) ε ( x) = pn ( x) − f ( x) = −h 4 dimana x0 – h < t < x0 + 2h 4
Contoh 3.5 Memakai nilai-nilai dari tabel berikut xi f(xi) δ 2 fi 1.2 3.3201 333 1.3 3.6693 367 Terapkan rumus Everett untuk mencari f(1.24). Jawab Untuk x = 1.24, tetapkan x0 = 1.2 sehingga r = 0.04 / 0.1 = 0.4 (1.6)(0.6)(−0.4) f (1.24) ≈ (0.6)(3.3201) + (0.4)(3.6693) + (0.0333) 6 (1.4)(0.4)(−0.6) + (0.0367) 6 = 3.4598 − 0.0021 − 0.0021
= 3.4556 15
Metode Numerik
Catatan Kuliah
4. Polinom Interpolasi Beda terbagi Newton Misalkan diberikan x0, x1, x2 ,…, xn dengan jarak sembarang. Polinom pn(x) berderajat n melalui titik-titik (x0, f0), (x1, f1), …, (xn, fn) dengan fj = f(xj) diberikan oleh rumus interpolasi beda terbagi Newton:
f ( x) ≈ pn ( x) = f 0 + ( x − x0 ) f [ x0 , x1 ] + ( x − x0 )( x − x1 ) f [ x0 , x1 , x2 ] + ... + ( x − x0 )...( x − xn −1 ) f [ x0 , x1 ,..., xn ] Melibatkan beda-beda terbagi, yang secara iteratif didefinisikan sebagai, f ( x1 ) − f ( x0 ) Jika xk = x0 + kh berjarak sama, f [ x0 , x1 ] = maka bentuk rumus di atas sama x1 − x0 f [ x1 , x2 ] − f [ x0 , x1 ] dengan rumus interpolasi beda f [ x0 , x1 , x2 ] = maju Newton. x2 − x0
.................
f [ x0 , x1 ,..., xk ] =
f [ x1 , x2 ,..., xk ] − f [ x0 , x1 ,..., xk −1 ] xk − x0 16
Metode Numerik
Catatan Kuliah
Algoritma Polinom Beda terbagi Newton.
Masukan : n, xi, i = 0, 1, .., n ; f(xi), i = 0, 1, .., n x, Epsilon Langkah-langkah : b0 ← f ( x0 ) pbagi ← b0 ; faktor ← 1
Catatan: b0, b1, b2,… menyatakan f(x0), f[x0,x1], f[x0,x1,x2]
Untuk i ← 1, 2, ..., n, lakukan bi ← f ((xxi ) Untuk j ← i − 1, i − 2, ..., 0, lakukan b j +1 − b j bj ← xi − x j faktor ← faktor.( x − xi −1 ) suku ← b0 . faktor pbagi ← pbagi + suku
Jika suku ≤ Epsilon maka Selesai 17
Metode Numerik
Catatan Kuliah
Contoh 3.6 Diberikan pasangan nilai x0 = 1, f(x0) = 0; x1 = 4, f(x1) = 1.3862944; x2 = 6, f(x2) = 1.7917595; x3 = 5, f(x3) = 1.6094379; a. Buat tabel beda terbagi dari data tersebut. b. Gunakan tabel beda terbagi di atas dalam menerapkan rumus interpolasi beda terbagi Newton dengan x = 2 Jawab a. Tabel beda terbaginya adalah i
xi
f(xi)
0 1
1 4
0 1.3862944
2 3
6 5
1.7917595 1.6094379
f[ , ]
0.4620981 0.2027326 0.1823216
f[, ,]
f[, , ,]
− 0.0518731 − 0.0204109
0.007865
b. f (2) ≈ p2 (2) = 0 + (2 − 1)(0.4620981) + (2 − 1)(2 − 4)(−0.0518731) = 0.5658444
f (2) ≈ p3 (2) = p2 (2) + (2 − 1)(2 − 4)(2 − 6)(0.007865) = 0.6287687 18
Metode Numerik
Catatan Kuliah
5. Polinom Interpolasi Lagrange Metode interpolasi lain dalam kasus nilai pivotal x0 ini didasarkan kepada rumus interpolasi Lagrange n + 1 titik, n
li ( x) f ( x) ≈ Ln ( x) = ∑ fi i = 0 li ( xi ) dengan, l0 ( x) = ( x − x1 )( x − x2 )...( x − xn )
l1 ( x) = ( x − x0 )( x − x2 )...( x − xn ) ................. li ( x) = ( x − x0 )( x − x1 )...( x − xi −1 )( x − xi +1 )...( x − xn ) ................. ln ( x) = ( x − x0 )( x − x1 )...( x − xn −1 ) Dalam hal ini terlihat bahwa untuk x = xi, maka
f ( xi ) ≈ Ln ( xi ) = f i
Rumus Interpolasi Lagrange dapat juga ditulis dalam bentuk n
f ( x) ≈ Ln ( x) = ∑ l ( x, xi ) f i i =0
dengan
x − xj l ( x, xi ) = ∏ j ≠i x − x j i 19
Metode Numerik
Catatan Kuliah
Algoritma Polinom Interpolasi Lagrange
Masukan : n, xi, i = 0, 1, .., n ; f(xi), i = 0, 1, .., n ; x Langkah-langkah :
plag ← 0 Untuk i ← 1, 2, ..., n, lakukan faktor ← 1
Untuk j ← 0, 1, ..., n, lakukan
x − xj Jika j ≠ i maka faktor ← faktor. x −x j i plag ← plag + faktor . f ( xi )
Contoh 3.7 Diberikan pasangan nilai x dan f(x) berikut: X f(x)
9.0 2.19722
9.5 2.25129
10.0 2.30259
11.0 2.39790
Gunakan Interpolasi Lagrange untuk menghitung f(9.2). 20
Metode Numerik
Catatan Kuliah
Jawab Dalam hal ini diperoleh,
l0 ( x) = ( x − 9.5)( x − 10.0)( x − 11.0)
l1 ( x) = ( x − 9.0)( x − 10.0)( x − 11.0) l2 ( x) = ( x − 9.0)( x − 9.5)( x − 11.0)
l3 ( x) = ( x − 9.0)( x − 9.5)( x − 10.0) Sehingga
3
f (9.2) ≈ L3 (9.2) = ∑ i =0
li (9.2) fi li ( xi )
l0 (9.2) l1 (9.2) l2 (9.2) l3 (9.2) = f0 + f1 + f2 + f3 l0 ( x0 ) l1 ( x1 ) l 2 ( x2 ) l3 ( x3 ) =
− 0.43200 0.28800 0.10800 0.04800 2.19722 + 2.25129 + 2.30259 + 2.39790 − 1.0000 − 0.50000 0.37500 3.00000
= 2.21920 (Eksak sampai 5D)
21
Catatan Kuliah
Metode Numerik
Masalah pencarian x untuk f(x) yang diberikan dikenal sebagai interpolasi balikan / invers. Jika fungsi f terdiferensialkan dan df/dx tidak nol dekat titik dimana interpolasi balikan harus diperhitungkan, balikan x = F(y) dan y = f(x) ada secara lokal didekat nilai f yang diberikan dan mungkin terjadi bahwa F dapat dihampiri dalam lingkungan itu dengan suatu polinom yang derajatnya agak rendah. Kemudian jalankan interpolasi balikan dengan membuat tabulasi F sebagai suatu fungsi y dan menerapkan metodemetode interpolasi yang langsung pada F. Jika df/dx = 0 dekat atau pada titik yang diinginkan, kemungkinan berguna untuk memecahkan p(x) = f dengan iterasi. Dalam hal ini, p(x) adalah polinom yang menghampiri f(x) dan f adalah nilai yang diberikan.
22
