Interpolasi dan Turunan Numerik (Rabu, 2 Maret 2016) Hidayatul Mayyani G551150351 Outline:
Interpolasi Linear - Polinomial Lagrange - Polinomial Newton - Vandermonde Matriks - Invers Interpolasi - Interpolasi Neville Galat Interpolasi Turunan Numerik Ekstrapolasi Richardson
1. Interpolasi Linear a. Polinomial Lagrange Suatu polinomial P(t) derajat n-1 yang unik dapat dikonstruksi yang melalui n titik t yang berbeda. Interpolasi Polinomial digunakan untuk mencari titik-titik antara dari n buah titik ( , ), ( , ), ( , ), . . . , ( , ) dengan menggunakan pendekatan fungsi polynomial pangkat n-1; = + + +⋯+ Suatu fungsi dapat di interpolasikan ke dalam bentuk interpolasi polynomial lagrange. Bentuk umum polinom Lagrange derajat ≤ ( )=
( )=
( )
Dalam hal ini =
,
= 0, 1, 2, . . . ,
dan − ( −
( )=
)
Interpolasi dari dua buah titik ( , ) dan ( , ) akan menghasilkan polynomial berderajat 1 (interpolasi linear), yaitu: ( − ) ( − ) ( )= + ( − ) ( − ) ( − ) +( − ) = ( − ) ( − ) = + ( − ) ( − ) Interpolasi dari tiga titik ( , ) dan ( , ) dan ( , ) akan menghasilkan polinomial berderajat 2, yaitu: ( )=
( )
+ ( )
+ ( )
Dengan ( )=
( (
)( )(
) )
( )=
( (
)( )(
) )
( )=
( (
)( )(
) )
Contoh : Dari fungsi x y
= ( ), diberikan tiga buah titik data dalam bentuk tabel: 1 1.5709
4 1.5727
6 1.5751
Tentukan (3,5) dengan polinom Lagrange derajat 2. Gunakan lima angka bena. Penyelesaian: Polinom derajat 2 n = 2 (perlu tiga buah titik) ( )= ( ) + ( ) + ( ) ( )= ( )= ( )=
(
)(
)
( (
)( )(
) )
( (
)( )(
) )
(
)(
)
( 3.5) =
( .
)( .
(
( 3.5) =
( .
)( )( .
( 3.5) =
( .
( (
) ) )
)( ) )( . ) )(
)
= 0.083333 = 1.0417 = −0.12500
Jadi, ( 3.5) = (0.083333)(1.5709)+(1.0417)(1.5727)+(−0.12500)(1.5751) = 1.5723 b. Polinomial Newton Interpolasi polinom Newton dapat ditulis: n
i 1
pn x ai ( x x j )
n
i 1
pn x ai ( x x j ) Koefisien an dikonstruksi menggunakan beda bagi: i 0 j 0 i 0
j 0
an f [x0 , x1,..., xn ] Dengan notasi yang baru, interpolasi polinom bentuk Newton dapat dituliskan dalam bentuk: n i 1 pn ( x) f [ x0 , x1,..., xi ]( x x j ) i 0 j 0 Jika diberikan sebarang fungsi f(x) dan 2 titik x 0 dan x 1 . Beda bagi orde pertama dari fungsi f adalah: f ( x1 ) f ( x0 ) f [ x0 , x1 ] x1 x0 Beda bagi orde dua untuk 3 titik yang berbeda x 0 , x1 , x 2 f [ x1, x2 ] f [ x0 , x1] f [ x0 , x1, x2 ] x2 x0 Dan seterusnya,
f [ x0 , x1,..., xn ]
f [ x1, x2 ,..., xn ] f [ x0 , x1,..., xn1] xn x0
Jadi, koefisien a0 , a2 , ..., an diperoleh dari: a 0 f [ x0 ] f ( x1 ) f ( x0 ) a1 f [ x0 , x1 ] x1 x0 a2 f [ x0 , x1 , x2 ]
f [ x1, x2 ] f [ x0 , x1 ] x2 x0
an f [ x0 , x1 ,..., xn ]
f [ x1, x2 ,..., xn ] f [ x0 , x1,..., xn 1 ] xn x0
Secara umum, k 1
i 1
f ( xk ) ai ( xk x j ) ak
i 0 k 1
(x
j 0
k
xj )
j 0
k 1
i 1
f ( xk ) f [ x0 , x1 ,..., xi ] ( xk x j ) f [ x0 , x1,..., xk ]
i 0
j 0
k 1
(x
k
xj)
j 0
Contoh: Diketahui: (1, 0), (4, 1.386294), (6, 1.791759), (5, 1.609438) (dari fungsi ln x) Ditanya: Perkirakan ln 2 dengan interpolasi Newton orde ke-3 Penyelesaian: p3 x a0 a1 x x0 a2 x x0 x x1 a3 x x0 x x1 x x2
1.386294 0 0.462 4 1 1.609438 1.791759 f x3 , x2 0.182 56 0.203 0.462 f x2 , x1 , x0 0.052 6 1
f x1 , x0
f x 3 , x2 , x1
0 .182 0.203 0. 020 54
f x3 , x2 , x1 , x0
0.020 ( 0.052) 0.008 5 1
i
xi
f(xi)
First
Second
Third
0
1
0
0.465
-0.052
0.008
1
4
1.386294
0.203
-0.020
2
6
1.791759
0.182
3
5
1.609438
p3 x a0 a1 x x0 a2 x x0 x x1 a3 x x0 x x1 x x2 p3 (x) = 0+ 0.465(x-1)-0.053(x-1)(x-4)+0.008(x-1)(x-4)(x-6) p3 (2) = 0.629 Gambar grafik perbandingan antara fungsi ln x dan hampirannya menggunakan interpolasi Newton
c. Vandermonde M atriks Bentuk umum dari polinomial yang menginterpolasi n+1 titik adalah ( )= + + +⋯+
Sistem persamaan linear: ( )= ( )= ( )=
⇒ ⇒ ⇒
+ + +
+ + + ⋮ ( )= ⇒ + + Bentuk matriks dari persamaan linear di atas
+⋯+ + ⋯+ +⋯+
= = =
+⋯+ . ⃗ = ⃗:
=
Matriks V disebut sebagai matriks Vandermonde. Matriks tersebut merupakan matriks nonsingular sehingga memiliki solusi tunggal. Untuk mencari penyelesaiannya dapat digunakan eliminasi Gauss. Contoh: Cari interpolasi polinomial pada data (-1,0),(0,0),(1,0),(2,6) menggunakan Sistem Vandermonde. Penyelesaian: Sistem Vandermonde dari titik-titik (-1,0),(0,0),(1,0),(2,6) adalah ( )= ⇒ + + + = ( )= ⇒ + + + = ( )= ⇒ + + + = ( )= ⇒ + + + = Matriks Vandermonde:
Untuk mendapatkan solusinya, digunakan Gaussian Elimination
Maka diperoleh persamaan linear dari matriks di atas adalah − + − =0 ⟺ =0 −
+
−
=0 ⟺
= −1 =0 =1
Sehingga polinomialnya berbentuk: ( )= + + ( )= − +
+
d. Invers Interpolasi Sebuah proses inverse interpolation sering digunakan untuk menghampiri suatu invers fungsi. Seandainya nilai = ( ) telah dihitung pada , , , …, . Menggunakan table berikut y … x … Bentuk polinomialnya adalah:
= ( ) memiliki invers pada kondisi tertentu. Invers tersebut dihampiri oleh = ( ).
a. Contoh grafik fungsi
= ( )
b. Contoh grafik fungsi x = ( )
e. Interpolasi Neville ( ) adalah nilai di titik x dari persamaan polynomial orde nol (konstan) Misal yang melalui titik ( , ), sehingga ( )= . Demikian juga ( ), ( ), … ( ) yang melalui ( , ) , ( , ) , . . . ( , ). Selanjutnya misal ( , nilai di x dari persamaan orde satu yang melalui titik ( , ),
,
( ) adalah ).
Dengan cara yang sama , ,…, ( ) adalah nilai di x yang melalui titik ( , ), ( , ), . . . ( , ) seluruh s titik. Dimulai dengan polinomial konstan ( ) = ( ). Dengan memilih dan , > + , didefinisikan fungsi rekursif: ,
( )=
,…,
=
( −
)
,
,… ,
,
. . .,
)(
(
)+
,
( ) −( −
)
,
. . .,
,…,
(
( ) )(
)
−
Diperoleh untuk n = 4 ( ) ( ) , ( ) ( )
,
( )
, ,
( )
( )
,
( )
, ,
( )
, , ,
( )
( ) , ( ) , , ( ) , , , ( ) Selanjutnya dilakukan peyederhanaan notasi ( )= , ( ) , untuk i ≥
Dimana node
,
, ..., ( )= =
Diperoleh ( )= ( )= ( )= ( )= ( )= ( )=
( ( ( ( (
) ) ) ) ) , , , ,
( ( ( (
, , , ,
( )
, . . .,
,
( )
menunjukkan polinomial interpolasi derajat pada j+1
, . − − ( − )
)= )= )= )= ( )
, , , ,
( ( ( (
,
) ) ) )
− − ( )− ( − −
( )+
,
( )= ( )= ( )=
, , , , , ,
,
)
( ) ( ) ( )
,
( ) ( )
( )= ( )=
( ) ( )
, , , , , ,
Contoh ( )=
Diberikan fungsi:
( ) 0
2
0,5
1
2,5
0,4
2
4
0,25
Kita akan mengaproksimasikan nilai (3) ( 3) ≈ ( 3) = ( ) = 0.5 ( 3) ≈ ( 3) = ( ) = 0.4 ( 3) ≈ ( 3) = ( ) = 0.25 Dengan menggunakan rumus Neville kita akan menentukan nilai dan ( 3 − ) ( 3) − ( 3 − ) (3) ( 3) ≈ ( 3) = − =
(
, ) ,
(
( 3) ≈ =
) ,
,
(
( 3) =
) ,
(
(3 −
, ) ,
,
= 0,3 )
( 3) − ( 3 − −
)
(3)
= 0,35
Selanjutnya hasil yang kita peroleh, kita masukan ke dalam tabel berikut:
0
2
0,5
1
2,5
0,4
0,3
2
4
0,25
0,35
Selanjutnya kita dapat menghitung ( 3) ≈ =
(
) ,
dengan menggunakan ( 3 − ) ( 3) − ( 3 − ) ( 3) = − (
) ,
= 0.325
(3)
Diperoleh :
0
2
0,5
1
2,5
0,4
0,3
2
4
0,25
0,35
0,325
(3)menggunakan rumus Neville derajat 2 adalah
Dengan demikian nilai hampiran 0,325
2. Galat Interpolasi Teorema I Jika p adalah polinomial berderajat tertinggi n yang menginterpolasi f pada n+1 titik yaitu , ,…, [ , ] dan jika ( ) kontinu,maka ∀ [ , ] , ( ) ( )− ( ) = ( )∏ ( − ) (
)!
Galat Rata-Rata Interpolasi Karena nilai c tidak diketahui, maka hampiri dengan c =
=
sehingga rumus
menjadi ( )−
( )=
1 ( + 1)!
(
)
( )
( −
Lemma I (Lemma Batas Atas) Definisikan = + ℎ untuk i=0, 1, …, n, maka untuk suatu | −
|≤
1 ℎ 4
)
[ , ],
!
dengan h=(b-a)/n adalah jarak antartitik Teorema II Misalkan f fungsi yang memenuhi ( ) kontinu pada [a,b] dan | ( ) ( )| ≤ . Misalkan p adalah polinomial berderajat ≤n yang menginterpolasi f pada n+1 titik di [ , ] termasuk titik akhirnya ,maka di [ , ] , 1 | ( ) − ( )| ≤ ℎ( ) 4( + 1) dengan h=(b-a)/n adalah jarak antartitik.
Keterangan :
= max
|
(
)
( )|
Contoh Diberikan empat buah titik berikut, hampiri nilai cos(1.5) dengan metode Lagrange dan Newton sampai derajat 3 serta identifikasi galatnya. ( ) 0.0
1.0000000
1.0
0.5403023
2.0
-0.4161468
3.0
-0.9899925
Nilai sejati cos(1.5)=0.071339183 Dari metode Lagrange diperoleh cos(1.5)≈ 0.069211999 Dari metode Polinomial Newton diperoleh cos(1.5)≈ 0.069212000 Batas atas kesalahan yaitu 1 | ( )| ≤ . 1 . 1 = 0.0416667 24 Galat absolut Lagrange = 0.002127184199 < | ( ) | Galat absolut Newton = 0.002127183199 < | ( ) | Sehingga polinomial derajat 3 sudah cukup teliti untuk menghampiri nilai cos(1.5) Teorema III Jika p adalah polinomial berderajat n yang menginterpolasi f pada titik [ , ] maka untuk suatu bukan titik interpolasi, , ,…, ( ) − ( ) = [ , ,… , , ] ∏ ( − ) Dengan [ , , … , , ] disebut selisih terbagi yang digunakan dalam interpolasi polinom Newton, sehingga teorema III dapat digunakan untuk mencari galat polinom Newton
Teorema IV Jika ( ) kontinu pada [a,b] dan [a,b], maka untuk di (a,b), [
, ,
,…,
,… ,
]=
adalah n+1 titik yang berada di interval 1 !
( )
( )
Corollary I (Selisih Terbagi) Jika f adalah polinomial berderajat n, maka semua selisih terbagi [ nol untuk ≥ + 1
,
, …,
] adalah
Galat Lain dalam Interpolasi Polinomial Fungsi Runge: ( ) = (1 + ) pada interval [-5,5] Misalkan polinomial yang menginterpolasi fungsi ini pada n+1 titik pada interval [5,5] maka, lim max | ( ) − ( ) | = ∞ →
Akibatnya, semakin banyak titik interpolasi maka semakin besar galatnya.
Pilihan lain yang lebih baik yaitu dengan menggunakan titik Chebyshev dengan interval standar [-1,1], 2 +1 = cos (0 ≤ ≤ ) 2 +2 Untuk titik yang berada di suatu interval [a,b], menjadi 1 1 2 +1 = ( + )+ ( − ) 2 2 2 +2
(0 ≤ ≤ )
Interpolasi polinomial dengan titik Chebyshev menghampiri fungsi Runge lebih baik dibanding dengan interpolasi polinomial dengan titik data.
3. Turunan Numerik Proses mencari hampiran nilai numerik suatu turunan dari fungsi yang diberikan pada suatu titik. Biasanya digunakan ketika : Fungsi ( ) tidak diketahui secara eksplisit, hanya diketahui data empirisnya saja, yaitu {( , ) ; = 0, 1, 2, … , }, Fungsi
( ) diketahui secara eksplisit tetapi bentuknya rumit..
Pendekatan turunan numerik
Hampiran selisih maju (beda maju) Hampiran selisih mundur (beda mundur) Hampiran selisih pusat (beda pusat)
Rumus untuk ketiga hampiran diatas diperoleh dari ekspansi deret Taylor di sekitar = : ( )= Misalkan
=
( )+
(
+ ℎ, maka didapatkan :
)( −
)+
( ) ( − 2!
) +⋯
(
+ ℎ) =
(
)+
(
( ) ℎ +⋯ 2!
)ℎ +
Rumus selisih maju untuk turunan pertama : (
)= ≈
Dengan
( (
+ ℎ) − ( ) − ℎ + ℎ) − ( ) ℎ
( ) ℎ−⋯ 2!
(ℎ) adalah galat dari hampiran fungsi.
y y0
h
y = f(x) x0
x
Rumus selisih maju untuk turunan kedua : (
+ ℎ) − ( ) ℎ ( + ℎ) − ( + 2ℎ ) − ( + ℎ) − ℎ ℎ ℎ + 2ℎ ) − 2 ( + ℎ) + ( ) ℎ
( )≈ ( ≈ (
≈ Dengan Misalkan
(ℎ) adalah galat dari hampiran fungsi. =
− ℎ, maka didapatkan : (
− ℎ) = (
)−
(
)ℎ +
( ) ℎ −⋯ 2!
Rumus selisih mundur untuk turunan pertama : ( ≈ Dengan
)
)= (
(
)− ( ℎ
)− ( ℎ − ℎ)
(ℎ) adalah galat dari hampiran fungsi.
− ℎ)
+
( 2!
)
ℎ−⋯
y0
y-1
h y = f(x) x0
x -1
Rumus selisih mundur untuk turunan kedua : (
Dengan
(
(
)− ( ℎ
(
)− 2 (
≈ ≈
)≈
)− ℎ − ℎ)
( −
− ℎ) (
− ℎ) − ( ℎ
ℎ ) −ℎ + (
− 2ℎ )
− 2ℎ)
ℎ
(ℎ) adalah galat dari hampiran fungsi.
Bila kedua persamaan berikut saling dikurangkan : (
+ ℎ) =
(
)+
(
)ℎ +
( ) ℎ +⋯ 2!
(
− ℎ) = (
)−
(
)ℎ +
( ) ℎ −⋯ 2!
Diperoleh rumus selisih pusat untuk turunan pertama: + ℎ) − ( 2ℎ + ℎ) − ( − ℎ) 2ℎ
( )= ≈ Dengan
(
(
(ℎ ) adalah galat dari hampiran fungsi.
− ℎ)
−
( ) ℎ −⋯ 3!
y1
y0
y-1
2h y = f(x) x0
x-1
x1
Bila kedua persamaan berikut saling ditambahkan : (
+ ℎ) =
(
)+
(
)ℎ +
( ) ℎ +⋯ 2!
(
− ℎ) = (
)−
(
)ℎ +
( ) ℎ −⋯ 2!
Diperoleh rumus selisih pusat untuk turunan kedua : (
+ ℎ) − 2 ( ) + ( ( )= ℎ ( + ℎ) − 2 ( ) + ( − ℎ) ≈ ℎ
− ℎ)
−
( )(
)
12
ℎ −⋯
(ℎ ) adalah galat dari hampiran fungsi.
Dengan Contoh:
Diketahui fungsi ( ) = √ . Tentukan hampiran (1) dan (1) untuk ℎ = 0.1 dan ℎ = 0.05 dengan menggunakan hampiran selisih maju, selisih mundur, selisih pusat, dan hitung galatnya. Jawaban : ( )= √ →
( )=
1 2√
→
( )= −
1 4
4. Ekstrapolasi Richardson Metode untuk memperoleh rumus hampiran turunan dengan orde yang lebih tinggi dari hampiran dengan orde yang lebih rendah disebut dengan ekstrapolasi. Metode tersebut dikembangkan oleh Lewis Fry Richardson di awal abad 20, sehingga metode tersebut kemudian dikenal dengan ekstrapolasi Richardson. Diterapkan pada turunan numerik untuk memperoleh solusi yang lebih teliti. Hampiran turunan beda pusat dengan orde (ℎ )
1 ( ℎ) = ℎ( − ) + (ℎ ) 2 = + ℎ + ⋯.
( 2ℎ) =
1 ) + ((2ℎ) ) ℎ( − 2(2ℎ) = + (2ℎ) + ⋯. = + 4 ℎ + ⋯.
( ℎ) − ( 2ℎ ) = −3 ℎ ( ℎ) − (2ℎ) = −3ℎ Dengan [ ( ℎ) − ( 2ℎ )] = ( ℎ) + 3
= (ℎ) +
[ ( )
(
)]
; n adalah orde galat yang dipakai
Subtitusi: [ (ℎ) − ( 2ℎ)] ℎ 3ℎ [ ( ℎ) − (2ℎ )] ( ℎ) = − 3 Setiap perluasan ekstrapolasi Richardson akan menaikan orde galat dari (ℎ ) ( ℎ) =
−
(ℎ ) menjadi
