ANALISIS NUMERIK Inter polasi
SPL simultan
Akar Persama an Non linear
INTERPOLASI
Tujuan • Interpolasi berguna untuk menaksir harga-harga tengah antara titik data yang sudah tepat. • Interpolasi mempunyai orde atau derajat.
Macam Interpolasi Interpolasi Beda Terbagi Newton Interpolasi Lagrange Interpolasi Spline
Interpolasi Beda Terbagi Newton •Interpolasi Linier Derajat/orde 1 memerlukan 2 titik x 1 2 3 4
f(x) 4,5 7.6 9.8 11.2
Berapa f(x = 1,325) = ? Memerlukan 2 titik awal : x=1 x=2
Interpolasi Beda Terbagi Newton •Interpolasi Kuadratik Derajat/orde 2 memerlukan 3 titik x = 1 f(x = 1) = . . . . x = 2 f(x = 2) = . . . . f (x = 1,325) = ? x = 3 f(x = 3) = . . . .
Interpolasi Beda Terbagi Newton • Interpolasi Kubik Derajat/orde 3 memerlukan 4 titik …
• Interpolasi derajat/orde ke-n memerlukan n+1 titik
• “Semakin tinggi orde yang digunakan untuk interpolasi hasilnya akan semakin baik (teliti).”
Interpolasi Linier
• Cara: menghubungkan 2 titik dengan sebuah garis lurus • Pendekatan formulasi interpolasi linier sama dengan persamaan garis lurus.
Interpolasi Linier • Prosentase kesalahan pola interpolasi linier : Harga_hasil_perhitungan Harga_sebenarnya εt Harga_sebenarnya
Contoh : Interpolasi Linier (1) • Diketahui suatu nilai tabel distribusi ‘Student t’ sebagai berikut : t5% = 2,015 t2,5% = 2,571 Berapa t4% = ?
Contoh : Interpolasi Linier (1) • Penyelesaian x0 = 5 f(x0) = 2,015 x1 = 2,5 f(x1) = 2,571 x = 4 f(x) = ? Dilakukan pendekatan dengan orde 1 : f x1 f x0 x x0 f1 x f x0 x1 x0
2,571 2,015 4 5 2,015 2,5 5 2,2374 2,237
Contoh : Interpolasi Linier (2) • Diketahui: log 3 = 0,4771213 log 5 = 0,698700 • Harga sebenarnya: log (4,5) = 0,6532125 (kalkulator). • Harga yang dihitung dengan interpolasi: log (4,5) = 0,6435078
0,6435078 0,6532125 t 100% 1,49% 0,6532125
Interpolasi Linier • Pendekatan interpolasi dengan derajat 1, pada kenyataannya sama dengan mendekati suatu harga tertentu melalui garis lurus. • Untuk memperbaiki kondisi tersebut dilakukan sebuah interpolasi dengan membuat garis yang menghubungkan titik yaitu melalui orde 2, orde 3, orde 4, dst, yang sering juga disebut interpolasi kuadratik, kubik, dst.
Interpolasi Kuadratik • Interpolasi orde 2 sering disebut sebagai interpolasi kuadratik, memerlukan 3 titik data. • Bentuk polinomial orde ini adalah : f2(x) = a0 + a1x + a2x2 dengan mengambil: a0 = b0 – b1x0 + b2x0x1 a1 = b1 – b2x0 + b2x1 a2 = b2
Interpolasi Kuadratik •Sehingga f2(x) = b0 + b1(x-x0) + b2(x-x0)(x-x1) Pendekatan dengan Pendekatan dengan garis linier kelengkungan
dengan
b0 f x0 b1
f x1 f x0 f x 1 , x0 x1 x0
f x2 f x1 f x1 f x0 x2 x1 x1 x0 f x , x , x b2 2 1 0 x2 x0
Interpolasi Kubik • f3(x) = b0 + b1(x-x0) + b2(x-x0)(x-x1) + b3(x-x0)(x-x1)(x-x2) dengan: b0 f x0 b1
f x1 f x0 f x 1 , x0 x1 x0
f x2 f x1 f x1 f x0 f [x2 , x1 ] f [x1 , x0 ] x2 x1 x1 x0 b2 f x2 , x1 , x0 x2 x0 x2 x0 b3
f [x3 , x2 , x1 ] f [x2 , x1 , x0 ] f x3 , x2 , x1 , x0 x3 x0
Interpolasi Beda Terbagi Newton • Secara umum: f1(x) = b0 + b1(x-x0) f2(x) = b0 + b1(x-x0) + b2(x-x0)(x-x1) f3(x) = b0 + b1(x-x0) + b2(x-x0)(x-x1) + b3(x-x0)(x-x1)(x-x2) … fn(x) = b0 + b1(x-x0) + b2(x-x0)(x-x1) + b3(x-x0)(x-x1)(x-x2) + … + bn(x-x1)(x-x2)…(x-xn-1)
Interpolasi Beda Terbagi Newton Dengan: • b0 = f(x0) • b1 = f[x1, x0] • b2 = f[x2, x1, x0] … • bn = f[xn, xn-1, xn-2, . . . ., x0]
Contoh : Interpolasi Beda Terbagi Newton • Hitung nilai tabel distribusi ‘Student t’ pada derajat bebas dengan = 4%, jika diketahui: t10% = 1,476 t2,5% = 2,571 t5% = 2,015 t1% = 3,365 dengan interpolasi Newton orde 2 dan orde 3!
Contoh : Interpolasi Beda Terbagi Newton Penyelesaian: Interpolasi Newton Orde 2: butuh 3 titik • x0 = 5 f(x0) = 2,015 x1 = 2,5 f(x1) = 2,571 x2 = 1 f(x2) = 3,365 • b0 = f(x0) = 2,015 f x1 f x0 2,571 2,015 b1 0,222 x1 x0 2,5 5
f x2 f x1 f x1 f x0 x2 x1 x1 x0 b2 x2 x0 3,365 2,571 2,571 2,015 1 2,5 2,5 5 0,077 15
Contoh : Interpolasi Beda Terbagi Newton •f2(x) = b0 + b1(x-x0) + b2(x-x0)(x-x1) = 2,015 + (-0,222) (4-5) + 0,077 (4-5)(4-2,5) = 2,121
Contoh : Interpolasi Beda Terbagi Newton Interpolasi Newton Orde 3: butuh 4 titik • x0 = 5 f(x0) = 2,015 x1 = 2,5 f(x1) = 2,571 x2 = 1 f(x2) = 3,365 x3 = 10 f(x3) = 1,476
Contoh : Interpolasi Beda Terbagi Newton • b0 = f(x0) = 2,015 b1 = -0,222 f[x1,x0] b2 = 0,077 f[x2,x1,x0] 1,476 3,365 3,365 2,571 10 1 1 2,5 0,077 10 2,5 b3 10 5 0,043 0,077 5 0,007
Contoh : Interpolasi Beda Terbagi Newton • f3(x) = b0 + b1(x-x0) + b2(x-x0)(x-x1) + b3(x-x0)(x-x1)(x-x2) = 2,015 + (-0,222)(4-5) + 0,077 (4-5)(4-2,5) + (-0,007)(4-5)(4-2,5)(4-1) = 2,015 + 0,222 + 0,1155 + 0,0315 = 2,153
Kesalahan Interpolasi Beda Terbagi Newton •Rn = |f[xn+1,xn,xn-1,…,x0](x-x0)(x-x1)…(x-xn)| •Menghitung R1 Perlu 3 titik (karena ada xn+1) R1 = |f[x2,x1,x0](x-x0)(x-x1)| •Menghitung R2 Perlu 4 titik sebagai harga awal R2 = |f[x3,x2,x1,x0](x-x0)(x-x1)(x-x2)|
Contoh : Kesalahan Interpolasi Beda Terbagi Newton • Berdasarkan contoh diatas: R1 = |f[x2,x1,x0](x-x0)(x-x1)| = |0.077 (4-5)(4-2.5)| = 0.1155 R2 = |f[x3,x2,x1,x0](x-x0)(x-x1)(x-x2)| = |-0.007 (4-5)(4-2.5)(4-1)| = 0.0315
Interpolasi Lagrange • Interpolasi Lagrange pada dasarnya dilakukan untuk menghindari perhitungan dari differensiasi terbagi hingga (Interpolasi Newton) • Rumus: n
fn x Li x .f x i i 0
dengan
Li x
n
j 0 j i
x xj xi x j
Interpolasi Lagrange •Pendekatan orde ke-1 f1(x) = L0(x)f(x0) + L1(x)f(x1) x x1 L0 x x0 x1
x x0 L1 x x1 x0
x x0 x x1 f1 x f x0 f x1 x0 x1 x1 x0
Interpolasi Lagrange •Pendekatan orde ke-2 f2(x) = L0(x)f(x0) + L1(x)f(x1) + L2(x)f(x2) x x1 x x2 L0 x x0 x1 x0 x2 i 0 n 2 j i
x x0 x x2 L1 x x1 x0 x1 x2 i 1 n 2 j i
x x0 x x1 x2 x0 x2 x1
L2 x
i 2 n 2 j i
x x1 x x2 x x0 x x2 x x0 x x1 f x0 f2 x f x x x x x x x 1 x x x x f x2 x x 1 0 2 0 1 2 0 2 1 0 1 2
Interpolasi Lagrange • Pendekatan orde ke-3
f3(x) = L0(x)f(x0) + L1(x)f(x1) + L2(x)f(x2) + L3(x)f(x3) x x1 x x2 x x3 x x0 x x2 x x3 f x1 f2 x f x0 x0 x1 x0 x2 x0 x3 x1 x0 x1 x2 x1 x3
x x0 x x1 x x3 x x0 x x1 x x2 f x2 x x x x x x x x x x x x f x3 0 2 1 2 3 0 3 1 3 2 2 3
Contoh : Interpolasi Lagrange • Berapa nilai distribusi t pada = 4 %? = 2,5 % x0 = 2,5 f(x0) = 2,571 =5% x1 = 5 f(x1) = 2,015 = 10 % x2 = 10 f(x2) = 1,476
Contoh : Interpolasi Lagrange • Penyelesaian • Pendekatan orde ke-1 f1(x) = L0(x)f(x0) + L1(x)f(x1) x x0 x x1 f1 x f x0 f x1 x0 x1 x1 x0 45 4 2,5 2,571 2,015 2,5 5 5 2,5 2,237
Contoh : Interpolasi Lagrange • Pendekatan orde ke-2 f2(x) = L0(x)f(x0) + L1(x)f(x1) + L2(x)f(x2) x x1 x x2 x x0 x x2 x x0 x x1 f x0 f x2 f2 x f x 1 x0 x1 x0 x2 x1 x0 x1 x2 x2 x0 x2 x1
4 5 4 10 4 2,5 4 10 4 2,5 4 5 2,571 2,015 1,476 2 , 5 5 2 , 5 10 5 2 , 5 5 10 10 2 , 5 10 5 2,214
Interpolasi Spline •Metode numeric yang dapat digunakan untuk pencarian interpolasi. •Interpolasi spline merupakan polinom sepotong-potong.
Interpolasi Spline linear
-xi
Contoh :diberikan table berisi 5 himpunan data algoritma natural • Cari nilai interpolasi saat x = [1.11 1.22 1.33 1.44
i 1 2 3 4 5
xi 1.1 1.2 1.3 1.4 1.5
F(xi) 0.0953 0,1823 0.2624 0.3365 0.4055
1.49]
Penyelesaian:
x 1.11 1.22 1.33 1.44 1.49
F(x) 0.104 0.1983 0.2846 0.3641 0.3986
Interpolasi Spline kuadratik
Contoh :diberikan table berisi 5 himpunan data algoritma natural • Cari nilai interpolasi saat x = [1.11 1.22 1.33 1.44
i 1 2 3 4 5
xi 1.1 1.2 1.3 1.4 1.5
F(xi) 0.0953 0,1823 0.2624 0.3365 0.4055
1.49]
Penyelesaian : • Persamaan 1 menghasilkan 1.21a1+1.1b1+c1=0.0953 1.44a2+1.2b2+c2=0.1823 1.69a3+1.3b3+c3=0.2624 1.961a4+1.4b4+c4=0.3365
• Persamaan 3 menghasilkan 2.4a1+b1=2.4a2+b2 2.6a2+b2=2.6a3+b3 2.8a3+b3=2.8a4+b4
• Persamaan 2 menghasilkan : 1.44a1+1.2b1+c1=0.1823 1.69a2+1.3b2+c2=0.2624 1.96a3+1.4b3+c3=0.3365 2.2a4+1.5b4+c4=0.4055
• Persamaan 4 Menghasilkan : a1=0
x 1.11 1.22 1.33 1.44 1.49
F(x) 0.104 0.1994 0.2844 0.3655 0.3991
Polinom Newton • Polinom Lagrange kurang disukai dalam praktek karena : • Jumlah komputasi yang dibutuhkan untuk satu kali interpolasi adalah besar. Interpolasi untuk nilai x yang lain memerlukan jumlah komputasi yang sama karena tidak ada bagian komputasi sebelumnya yang dapat digunakan. • Bila jumlah titik data meningkat atau menurun, hasil komputasi sebelumnya tidak dapat digunakan. Karena tidak ada hubungannya antara pn-1(x) dan pn(x) pada polinom Lagrange
• Polinom yang dibentuk sebelumnya dapat digunakan untuk membentuk polinom derajat yang lebih tinggi.
Polinom Newton • Persamaan Polinom Linier
( y1 y 0 ) p1 ( x) y 0 ( x x0 ) ( x1 x0 )
• Bentuk pers ini dapat ditulis : p1 ( x) a0 a1 ( x x0 )
a0 y 0 f ( x0 ) • Yang dalam hal ini (1) • Dan ( y1 y 0 ) f ( x1 ) f(2)( x0 ) a1 ( x1 x0 ) ( x1 x0 ) • Pers ini mrpk bentuk selish terbagi (divided-difference) a1 f [ x1 , x0 ]
Polinom Newton • Polinom kuadratik • Atau
p 2 ( x) a0 a1 ( x x0 ) a 2 ( x x0 )( x x1 )
p 2 ( x) p1 ( x) a 2 ( x x0 )( x x1 )
• Dari pers ini menunjukkan bahwa p2(x) dapat dibentuk dari pers sebelumnya p1(x). Nilai a2 dapat ditemukan dengan mengganti x=x2 untuk mendapatkan (3)
f ( x2 ) a0 a1 ( x2 x0 ) a2 ( x2 x0 )( x2 x1 )
• Nilai a0 dan a1 pada pers 1 dan 2 dimasukkan pada pers 3
f ( x 2 ) f ( x0 ) f ( x1 ) f ( x0 ) x 2 x0 x1 x0 a2 x 2 x1
Polinom Newton • Dengan melakukan utak-atik aljabar, pers ini lebih disukai f ( x 2 ) f ( x0 ) f ( x1 ) f ( x0 ) x 2 x1 x1 x0 f [ x 2 , x1 ] f [ x1 , x0 ] a2 x2 x0 x 2 x0
Polinom Newton • Jadi tahapan pembentukan polinom Newton : p1 ( x) p0 ( x) a1 ( x x0 )
p1 ( x) a0 a1 ( x x0 )
p 2 ( x) p1 ( x) a 2 ( x x0 )( x x1 ) p 2 ( x) a0 a1 ( x x0 ) a 2 ( x x0 )( x x1 )
p3 ( x) p 2 ( x) a3 ( x x0 )( x x1 )( x x 2 )
p3 ( x) a0 a1 ( x x0 ) a2 ( x x0 )( x x1 ) a3 ( x x0 )( x x1 )( x x2 )
Polinom Newton • Nilai konstanta a0, a1, a2,…, an, merupakan nilai selisih terbagi , dg nilai
a0 f ( x0 ) a1 f [ x1 , x0 ] a 2 f [ x 2 , x1 , x0 ]
• Yang dalam hal ini f [ xi , x j ]
a n f [ x n , x n 1 ,..., x1 , x0 ] f ( xi ) f ( x j )
f [ xi , x j , x k ]
xi x j f [ xi , x j ] f [ x j , x k ]
f [ x n , x n 1 ,..., x1 , x0 ]
xi x k f [ x n , x n 1 ,..., x1 ] f [ x n 1 , x n 2 ,..., x1 , x0 ) x n x0
Polinom Newton • Dengan demikian polinom Newton dapat ditulis dalam hub rekursif sebagai : • Rekurens
p n ( x) p n1 ( x) ( x x0 )( x x1 )...(x xn1 ) f [ xn , xn1 ,..., x1 , x0 ] • basis
p 0 ( x) f ( x0 ) • Atau dalam bentuk polinom yang lengkap sbb : p n ( x) f ( x0 ) ( x x0 ) f [ x1 , x0 ] ( x x0 )( x x1 ) f [ x 2 , x1 , x0 ] ( x x0 )( x x1 )...(x x n 1 ) f [ x n , x n 1 ,..., x1 , x0 ]
Contoh Soal :
• Bentuklah polinom Newton derajat satu, dua, tiga dan empat yang menghampiri f(x)=cos(x) dalam range[0.0, 4] dan jarak antar titik adalah 1.0. Lalu taksirlah f(x) dengan x=2.5 dengan Polinom Newton derajat 3.
xi
yi
ST-1
ST-2
ST-3
ST-4
0.0
1
-0.4597
-0.2484
0.1466
-0.0147
1.0
0.5403
-0.9564
0.1913
0.0880
2.0
-0.4161
-0.5739
0.4551
3.0
-0.99
0.3363
4.0
-0.6536
Contoh Soal : • Contoh cara menghitung nilai selisih terbagi pada tabel : f ( x1 ) f ( x0 ) 0.5403 1 f [ x1 , x0 ] 0.4597 ( x1 x0 ) 1 0 f [ x 2 , x1 ]
f ( x 2 ) f ( x1 ) 0.4161 0.5403 0.9564 ( x 2 x1 ) 2 1
f [ x 2 , x1 ] f [ x1 , x0 ] 0.9564 0.4597 f [ x 2 , x1 , x0 ] 0.2484 ( x 2 x0 ) 20
Contoh Soal : • Maka polinom Newton derajat 1,2 dan 3 dengan x0 = 0 sebagai titik pertama : cos(x) p1 ( x) 1.0 0.4597 ( x 0.0) cos(x) p 2 ( x) 1.0 0.4597 ( x 0.0) 0.2484 ( x 0.0)( x 1.0) cos(x) p3 ( x) 1.0 0.4597 ( x 0.0) 0.2484 ( x 0.0)( x 1.0) 0.1466 ( x 0.0)( x 1.0)( x 2.0) cos(x) p 4 ( x) 1.0 0.4597 ( x 0.0) 0.2484 ( x 0.0)( x 1.0) 0.1466 ( x 0.0)( x 1.0)( x 2.0) 0.0147 ( x 0.0)( x 1.0)( x 2.0)( x 3.0)
• Nilai sejati f(2.5) adalah • F(2.5) = cos(2.5)=-0.8011
The end….