INTERPOLASI LAGRANGE DAN NEWTON PDF

Preview

Summary

INTERPOLASI LAGRANGE DAN NEWTON ANNISA PUSPA KIRANA, S.KOM, M.KOM INTERPOLASI LAGRANGE INTERPOLASI LAGRANGE  Interpolasi Lagrange pada dasarnya dilakukan untuk menghindari perhitungan dari differensiasi terbagi hingga fn x    Li x .f x i  (Interpolasi Newton)  Rumus: n i 0 Li x   x  x...

Description

INTERPOLASI LAGRANGE DAN NEWTON ANNISA PUSPA KIRANA, S.KOM, M.KOM

INTERPOLASI LAGRANGE

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

Bentuk umum interpolasi polinomial Lagrange order n adalah: (1.1) dimana, (1.2)

Nb=Simbol  merupakan tanda perkalian.

Dengan menggunakan persamaan (1.1) dan persamaan (1.2) maka dapat dihitung rumus orde interpolasi Lagrange. Misal mencari ORDE 1: 1

f1(x) = Li (x) f (xi) = L0(x) f (x0) + L1(x) f (x1) i0

Dengan, x  x1 L0(x)= x 0  x1

;

x  x0 L1(x) = x1  x 0

jadi,rumus orde satu interpolasi lagrange adalah= x  x1 x  x0 f1(x)= f (x0) + f (x1) x 0  x1 x1  x 0

Dengan melakukan hal yang sama dapat diperoleh rumus untuk orde orde berikutnya. Orde 2 f2(x) =

x  x0 x  x2 x  x1 x  x 2 f (x0) + f (x1) + x1  x 0 x1  x 2 x0  x1 x 0  x 2 x  x 0 x  x1 f (x2) x 2  x 0 x 2  x1

Orde 3 x  x0 x  x 2 x  x3 x  x1 x  x 2 x  x 3 f3(x) = f (x0) + f (x1) + x 0  x1 x 0  x 2 x 0  x 3 x1  x 0 x1  x 2 x1  x 3 x  x 0 x  x1 x  x 3 x  x 0 x  x1 x  x 2 f (x2) + f (x3) x 2  x 0 x 2  x1 x 2  x 3 x 3  x 0 x 3  x1 x 3  x 2

Orde 4

f4(x) =

x  x1 x  x 2 x  x 3 x  x 4 f (x0) + x 0  x1 x 0  x 2 x 0  x 3 x 0  x 4 x  x0 x  x 2 x  x3 x  x 4 x1  x 0 x1  x 2 x1  x 3 x1  x 4 f (x1) + x  x 0 x  x1 x  x 3 x  x 4 x 2  x 0 x 2  x1 x 2  x 3 x 2  x 4 f (x2) + x  x 0 x  x1 x  x 2 x  x 4 x 3  x 0 x 3  x1 x 3  x 2 x 3  x 4 f (x3) + x  x 0 x  x1 x  x 2 x  x 3 x 4  x 0 x 4  x1 x 4  x 2 x 4  x 3 f (x4)

INTERPRETASI GRAFIS POLYNOMIALS LAGRANGE f 2 x   L0 f x 0   L1 f x1   L2 f x 2  L2f(x2)

L0f(x0)

L1f(x1)

9

Carilah nilai dari ln 2 dengan metode interpolasi polinomial Lagrange Orde dua berdasar data sebagai berikut ln 1 = 0, ln 4 = 1,3862944 dan ln 6 = 1,7917595. Untuk membandingkan hasil yang diperoleh, hitung pula besar kesalahan (diketahui nilai eksak dari ln 2 = 0,69314718).

Jawab : Dari soal di atas dapat diperoleh data sbg brkt.. x0 = 1  f (x0) = 0 x1 = 4  f (x1) = 1,3862944 x2 = 6  f (x2) = 1,7917595

Dari data yg diketahui masukkan ke persamaan interpolasi lagrange orde 2.. x  x0 x  x2 x  x1 x  x 2 f (x0) + f (x1) + x1  x 0 x1  x 2 x0  x1 x 0  x 2

f2(x) =

x  x 0 x  x1 f (x2) x 2  x 0 x 2  x1

F2(2)=

24 1 4

26 (0) + 2  1 1 6 4 1

2 1 6 1

2  4 (1,7917595) 64

F2(2)= 0,56584437

2  6 (1,3862944) + 46

Besar kesalahan adalah:

0,69314718  0,56584437 Et =  100 % = 18,4 %. 0,69314718

CONTOH :  Hampiri fungsi f(x) = cos(x) dengan polinom interpolasi derajat

tiga pada range [0.0, 1.2]. Gunakan empat titik  x0 = 0.0, x1 = 0.4, x2 = 0.8, x3 = 1.2  Perkirakan nilai p3(0.5) dan bandingkan dengan nilai sebenarnya.

Xi yi

0.0 1

0.4 0.8 1.2 0.921061 0.696707 0.362358

 Polinom Lagrange derajat 3 yang menginterpolasi keempat titik tsb.

CONTOH :

p3 ( x)  a 0 L0 ( x)  a1 L1 ( x)  a 2 L2 ( x)  a3 L3 ( x) ( x  x1 )( x  x 2 )( x  x3 ) ( x  x0 )( x  x 2 )( x  x3 ) p3 ( x)  y 0  y1  ( x0  x1 )( x0  x 2 )( x0  x3 ) ( x1  x0 )( x1  x 2 )( x1  x3 ) ( x  x0 )( x  x1 )( x  x3 ) ( x  x0 )( x  x1 )( x  x 2 ) y2  y3 ( x 2  x0 )( x 2  x1 )( x 2  x3 ) ( x3  x0 )( x3  x1 )( x3  x 2 )

( x  0.4)( x  0.8)( x  1.2) ( x  0.0)( x  0.8)( x  1.2) p3 ( X )  1  0.921061 (0.0  0.4)(0.0  0.8)(0.0  1.2) (0.4  0.0)(0.4  0.8)(0.4  1.2) ( x  0.0)( x  0.4)( x  1.2) ( x  0.0)( x  0.4)( x  0.8) 0.696707  0.362358 (0.8  0.0)(0.8  0.4)(0.8  1.2) (1.2  0.0)(1.2  0.4)(1.2  0.8)

p3 (0.5)  0.877221

y  cos(0.5)  0.877583

INTERPOLASI NEWTON

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 )  Yang dalam hal ini  Dan

a 0  y 0  f ( x0 )

( y1  y 0 ) f ( x1 )  f ( x0 ) a1   ( x1  x0 ) ( x1  x0 )

 Pers ini merupaka bentuk selisih terbagi (divided-difference)

a1  f [ x1 , x0 ]

POLINOM NEWTON  Polinom kuadratik

p2 ( x)  a0  a1 ( x  x0 )  a2 ( x  x0 )( x  x1 )

 Atau

p2 ( x)  p1 ( x)  a2 ( 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 f ( x2 )  a0  a1 ( x2  x0 ) a2  ( x 2  x0 )( x 2  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   x 2  x0 x 2  x0

 Jadi tahapan pembentukan polinom Newton : POLINOM NEWTON p1 ( x)  p0 ( x)  a1 ( x  x0 )

p1 ( x)  a0  a1 ( x  x0 )

p2 ( x)  p1 ( x)  a2 ( x  x0 )( x  x1 ) p2 ( x)  a0  a1 ( x  x0 )  a2 ( x  x0 )( x  x1 )

p3 ( x)  p 2 ( x)  a3 ( x  x0 )( x  x1 )( x  x2 )

p3 ( x)  a0  a1 ( x  x0 )  a2 ( x  x0 )( x  x1 )  a3 ( x  x0 )( x  x1 )( x  x2 )

 Nilai konstanta a0, a1, a2,…, an, merupakan nilai selisih terbagi , dengan nilai

POLINOM NEWTON

a0  f ( x0 ) a1  f [ x1 , x 0 ] a 2  f [ x 2 , x1 , x 0 ] a n  f [ x n , x n 1 ,..., x1 , x 0 ]

 Yang dalam hal ini f [ xi , x j ] 

f ( xi )  f ( x j )

f [ xi , x j , x k ] 

xi  x j f [ xi , x j ]  f [ x j , x k ] xi  x k

f [ x n , x n 1 ,..., x1 ]  f [ x n 1 , x n  2 ,..., x1 , x0 ) f [ x n , x n 1 ,..., x1 , x0 ]  x n  x0

POLINOM NEWTON  Dengan demikian polinom Newton dapat ditulis dalam hub rekursif sebagai :  Rekurens

pn ( x)  pn1 ( x)  ( x  x0 )( x  x1 )...(x  xn1 ) f [ xn , xn1 ,..., 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 [ x2 , x1 , x0 ]  ( x  x0 )( x  x1 )...(x  xn 1 ) f [ xn , xn 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 , x0 ] 

f ( x1 )  f ( x0 ) 0.5403  1   0.4597 ( x1  x0 ) 1 0

f ( x 2 )  f ( x1 )  0.4161  0.5403 f [ x 2 , x1 ]    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 ) 20

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

INTERPOLASI BEDA TERBAGI NEWTON...