INTERPOLASI INTERPOLASI LINIER INTERPOLASI KUADRATIK
1
INTERPOLASI POLINOMIAL Dua titik data
: Garis
Tiga g titik data
: Kuadratik
Empat titik data :Polinomial tingkat-3 … n titik data
:Polinomial tingkat-n
Diketahui:n titik data (x1, y1), (x2, y2), … (xn, yn) Di Ditanya :a0, a1, …, an sehingga hi
x1a1 + x12a2 + ... + x1n an = y1 − a0 x2a1 + x22a2 + ... + x2n an = y2 − a0 L
f ( x) = a0 + a1 x + a2 x2 + L+ an xn
xn a1 + xn2a2 + ... + xnn an = yn − a0 Adakah cara yang lebih baik untuk menyelesaikan persamaan diatas?
2
INTERPOLASI LINEAR Diketahui
: Dua titik(x1, y1), (x2, y2)
Ditanya
: Garis yang melewati 2 titik tersebut
f ( x1 ) − f ( x0 ) ( x − x0 ) f1 ( x ) = f ( x0 ) + x1 − x0
f ( xn+1 ) − f ( xn ) ( f n+1 ( x ) = f ( xn ) + x p − xn ) xn+1 − xn
Semakin kecil intervalnya semakin baik hasil interpolasi!
3
Contoh: Diket f(x) = ln x, dengan x1 = 1 dan x2 = 6 dan x1 = 1 dan x2 = 4. Tentukan nilai y untuk x = 2 !!!
Jawab : f1(2) = 0.3583519 f1(2) = 0.4620981
ln 2 = 0.6931472
5
INTERPOLASI KUADRATIS Diketahui : Tiga titik (x1, y1), (x2, y2), (x3,y3) Ditanya :
Kuadratis f2(x) = a0 + a1x + a2x2 yang melewati ke-3 titik diatas
f 2 ( x ) = b0 + b1 ( x − x0 ) + b2 ( x − x0 )( x − x1 )
b0 = f ( x0 )
b1 =
f ( x1 ) − f ( x0 ) x1 − x0
f ( x2 ) − f ( x1 ) f ( x1 ) − f ( x0 ) − x2 − x1 x1 − x0 b2 = x 2 − x0
6
Contoh: Diketahui ln 2 = 0.6931472
f(x) = ln x
Titik data d t : (1, 0), (4, 1.386294), (6, 1.791759) Tentukan nilai untuk x = 2 !!!
b0 = 0 b1 = (1.386294 – 0)/(4 – 1) = 0.4620981 b2 = [(1.791759 – 1.386294)/(6-4) – 0.4620981]/(6-1) = -0.0518731 Jawab : f2(2) = 0.5658444 7
Algoritma Interpolasi Kuadratik Kuadratik:: 1. Tentukan 3 titik input P1(x1,y1), P2(x2,y2) dan P3(x3,y3) 2. Tentukan nilai x dari titik yang akan dicari 3 Hitung 3. Hit nilai il i y ddarii titik yang dicari di i menggunakan k rumus dari d i interpolasi kuadratik:
4. Tampilkan nilai x dan y
8
INTERPOLASI POLYNOMIAL NEWTON Diketahui: n titik (x1, y1), ) (x2, y2), ) …, (xn, yn) Ditanya:
(yi = f(xi), ) i=1,2,…,n) i=1 2 n)
fn(x) = a0 + a1x + a2x2 + … + anxn yang melewati n titik tersebut.
f n ( x ) = b0 + b1 ( x − x0 ) + b2 ( x − x0 )( x − x1 ) + ... + bn ( x − x0 )( x − x1 )L( x − xn−1 ) b0 = f ( x0 )
b1 = f [ x1 , x0 ] M bn = f [ xn , xn−1 ,L x1 , x0 ]
dengan
[
]
f xi , x j =
[
]
f xi , x j , xk =
[
f ( xi ) − f ( x j ) xi − x j
] [
f xi , x j − f x j , xk
f [ xn , xn−1 ,..., x1 , x0 ] =
]
xi − xk
f [ xn , x n−1 ,..., x1 ] − f [ xn−1 , xn− 2 ,..., x0 ] x n − x0
9
Contoh Interpolasi Polynomial Newton Diketahui k h : ((1, 0) 0), ((4, 1.386294), 38629 ) (6 (6, 1.791759), 9 9) ((5, 1.609438) 609 38) (dari fungsi ln x) Ditanya :
Perkirakan ln 2 dengan interpolasi Newton orde ke-3 ke 3
f n ( x ) = b0 + b1 ( x − x0 ) + b2 ( x − x0 )( x − x1 ) + b2 ( x − x0 )( x − x1 ) + b3 ( x − x0 )( x − x1 )( x − x2 )
10
1.386294 − 0 f [ x1 , x0 ] = = 0.462 4 −1
1.791759 − 1.386294 f [ x2 , x1 ] = = 0.203 6−4
1 .609438 − 1 .791759 f [x3 , x 2 ] = = 0 .182 5−6 f [ x2 , x1 , x0 ] =
0.203 − 0.462 = −0.052 6 −1 f [ x 3 , x 2 , x1 , x 0 ] =
f [ x3 , x2 , x1 ] =
0.182 − 0.203 = −0.020 5− 4
− 0.020 − ( − 0.052 ) = 0.008 5 −1
f3(2) = 0.629 11
Contoh Interpolasi Polynomial Newton Contoh Interpolasi Polynomial Newton
x0
x1
x2 x3
12
Perkiraan Error Polynomial Newton f n (x ) = b0 + b1 (x − x 0 ) + b2 (x − x 0 )(x − x1 ) + ... + bn (x − x 0 )(x − x1 )L (x − x n −1 )
Jika f(x) dinyatakan oleh deret Taylor , error setelah terms ke-n adalah: f (n +1) (ξ ) (xi +1 − xi )n+1 Rn = (n + 1)!
Untuk suatui polinomial Newton orde ke-n, ke-n Hubungan untuk error scr analogi: f (n +1) (ξ ) (x − x 0 )(x − x1 )(x − x 2 )L (x − x n ) Rn = (n + 1)!
Tapi kita tidak tahu apakah itu f(x)! Sebagai suatu perkiraan untuk error, bisa kita gunakan R n ≅ f [x n +1 , x n , x n −1 ,L , x 0 ](x − x 0 )(x − x1 )(x − x 2 )L (x − x n ) (Ingat: fn+1(x) = fn(x) + Rn)
13
Perkiraan Error, Orde, dan Titik data x 1 4 6 5 3 1.5 2.5 3.5
f(x) = ln x 0 1.386 1 792 1.792 1.609 1.099 0.405 0.916 1.253
x 35 3.5 2.5 1.5 3 5 6 4 1
f(x) = ln x 1 253 1.253 0.916 0.405 1.099 1.609 1.792 1.386 0
Perkiraan Error polynomial Newton fk(x) pada ln 2: k = 1,2,…,7
14
POLINOMIAL INTERPOLASI LAGRANGE Pn ( x ) = ∑ Li ( x ) f ( xi ) n
i =0 =0
dengan n
Li ( x ) = ∏ j =0
Contoh:
j≠i
x − xi xi − x j
x − x1 x − x0 linear : P1 ( x ) = f ( x0 ) + f ( x1 ) x0 − x1 x1 − x0 ( ( x − x1 )( x − x2 ) x − x0 )( x − x2 ) f ( x1 ) 2ndd - order d : P2 ( x ) = f ( x0 ) + ( x0 − x1 )( x0 − x 2) ( x1 − x0 )( x1 − x 2 ) ( x − x0 )( x − x1 ) + f ( x2 ) ( x2 − x0 )( x2 − x1 ) 15
3rd - order :
( x − x1 )( x − x 2 )( x − x 3 ) P2 ( x ) = f ( x0 ) ( x 0 − x1 )( x 0 − x 2 )( x − x 3 ) ( x − x 0 )( x − x 2 )( x − x 3 ) + f ( x1 ) ( x1 − x 0 )( x1 − x 2 )( x − x 3 ) ( x − x 0 )( x − x1 )( x − x 3 ) + f (x2 ) ( x 2 − x 0 )( x 2 − x1 )( x − x 3 ) P2 ( x ) = L0 f ( x 0 ) + L1 f ( x1 ) + L2 f ( x 2 )
16
Interpretasi Grafis Polynomials Lagrange f 2 (x ) = L0 f (x 0 ) + L1 f (x1 ) + L2 f (x 2 ) L2f(x2)
L0f(x0)
L1f(x1)
17
y
Interpolasi Inverse p x Interpolated curve
Interpolated point of (xc, f(xc))
true curve
x
fn(x) = a0 + a1x + a2x2 + … + anxn
interpolasi p yc = fn(xc)
Bagimana inverse-nya: fn(y) = a0 + a1y + a2y2 + … + anyn
interpolasi xc = fn(yc)
Keduanya tidak ekuivalen dalam hal keakuratan interpolasi! 18
Extrapolasi p
Hasil interpolasi yang paling akurat bisanya diperoleh ketika yang tidak diketahui berada dekat di tengah-tengah titik basis! Untuk ekstrapolasi, yang tidak diketahui berada di luar jangkauan titik basis; jadi perlu perhatian lebih! 19
Masalah‐2 dalam Interpolasi Polinomial p •
Derajat interpolasi polinomial sama dengan jumlah-n titik data. Jadi jikan=1000 titik data, maka kita akan mempunyai polinomial orde-1000
•
Polinomial berorde tinggi (saat n > 5) dapat menampakkan ciri erratik dan sangat rentan dengan instabilitas numerik.
•
Polinomial berorde tinggi seringkali menginterpolasi titik diluar jangkauan titik data yang tepat karena adanya overshoot. overshoot
20
Interpolasi Spline Ide: Gunakan polinomial orde rendah (k ≤ 3) untuk menginterpolasi sekumpulan data titik dan hubungkan polinomial interolsai ini dengan halus
Papan Drafting: menggunakan tali yang tipis dan fleksibel (disebut spline)untuk menggambarkan kurva yang halus melalui sekumpulan titik.Tiap bagian interpolasi akhir melengkung antar 2 titik yang berdekatan Titik data adalah polinomial derajat 3
Contoh 21
Interpolasi Spline Kuadratis Diketahui:
n+1 Titik data (xi, yi) untuk i=0,1,…,n
Ditanya: polynomials derajat-2 n fi(x) = aix2 + bix + ci sedemikian sehingga 1. fi(x) menginterpolasi dua titik (xi-1, yi-1) dan (xi, yi), dan 2. fi(x) dan fi-1(x) punya turunan yang sama pada xi-1.
22
Turunan Quadratic Spline 1.
fi-1(xi-1) = ai-1xi-12 + bi-1xi-1 + ci-1 = yi-1 2
fi(xi-1) = aixi-1 + bixi-1 + ci = yi-1 2.
f1(x0) = a1x02 + b1x0 + c1 = y0
2n – 2 persamaan
2 persamaan
fn(xn) = anxn2 + bnxn + cn = yn
3.
(the 1st derivative at the interior knots must be equal) fi-1’(xi-1) = 2ai-1xi-1 + bi-1 = 2aixi-1 + bi = fi’(xi-1)
n 1 persamaan n–
23
Contoh of Quadratic Spline
24
