PAM 252 Metode Numerik Bab 4 Pencocokan Kurva

Pendahuluan Regresi Interpolasi/Ekstrapolasi

PAM 252 Metode Numerik Bab 4 Pencocokan Kurva Mahdhivan Syafwan Jurusan Matematika FMIPA Universitas Andalas

Semester Genap 2013/2014

1

Mahdhivan Syafwan

Metode Numerik: Pencocokan Kurva


Permasalahan dan Penyelesainnya Dua Macam Teknik Pencocokan Kurva

Permasalahan dan penyelesainnya Diberikan n buah titik dalam bidang (x1 , y1 ), (x2 , y2 ), ..., (xn , yn ) yang berasal dari sebuah fungsi atau data hasil pengamatan. Permasalahan: ingin diketahui nilai dari fungsi/data tersebut di suatu titik x yang tidak berada dalam data tersebut. Penyelesaian: pencocokan kurva, yaitu mengkonstruksi sebuah kurva yang menghampiri titik tersebut. Istilah menghampiri di sini berarti: (i) kurva yang dibangun diformulasikan sedemikian sehingga galat yang diperoleh seminimal mungkin. (ii) mengaproksimasi fungsi yang rumit dengan fungsi yang sederhana 2

Mahdhivan Syafwan




Dua macam teknik pencocokan kurva

1

Regresi digunakan apabila sumber data yang digunakan mempunyai ketelitian yang cukup rendah. kurva yang dibangun tidak perlu melalui semua titik data tersebut, tetapi cukup mengikuti kecendrungannya saja.

2

Interpolasi/Ekstrapolasi digunakan apabila sumber data yang digunakan mempunyai ketelitian yang sangat tinggi. kurva yang dibangun harus melalui semua titik data yang digunakan.

3

Mahdhivan Syafwan




Ilustrasi

4

Mahdhivan Syafwan



Regresi Linier Penerapan Regresi Linier pada Model Nonlinier Regresi Polinom

Regresi linier: bentuk umum Titik-titik data dihampiri oleh sebuah garis lurus (disebut garis/kurva regresi) yang dinyatakan sebagai y ≡ f (x) = a0 + a1 x.

Pertanyaan: berapa nilai a0 dan a1 agar garis regresi tersebut sedekat mungkin dengan titik-titik data yang diberikan (meminimumkan galat)? 5

Mahdhivan Syafwan




Regresi linier: galat

Galat dari garis regresi untuk setiap datum diberikan oleh ei = f (xi ) − yi ,

i = 1, 2, ..., n.

Tiga jenis galat dari garis regresi untuk keseluruhan data (i) Galat maksimum: E∞ (f ) = max {|f (xi ) − yi |} 1≤i ≤n 1 Pn (ii) Galat rata-rata: E1 (f ) = n i =1 |f (xi ) − yi | q P n (iii) Galat akar kuadrat rata-rata: E2 (f ) = n1 i =1 |f (xi ) − yi |2

Di antara ketiga galat di atas, galat akar kuadrat rata-rata paling mudah untuk dihitung nilai minimumnya. [mengapa?]

6

Mahdhivan Syafwan




Regresi linier: galat regresi kuadrat terkecil Pada regresi kuadrat terkecil, galat yang dipakai adalah galat akar kuadrat rata-rata, yaitu v u n u1 X (yi − (a0 + a1 xi ))2 . (1) E =t n i =1

Q: mengapa perlu dikuadratkan? Akan ditentukan nilai a0 dan a1 yang meminimumkan nilai galat E . Perhatikan bahwa E mencapai minimum jika ∂E = 0 dan ∂a0

∂E = 0. ∂a1

(2)

Untuk memudahkan perhitungan, masalah di atas diselesaikan dengan meminimumkan E 2 , bukan E . [mengapa?] 7

Mahdhivan Syafwan




Regresi linier: penentuan nilai koefisien a0 dan a1 Misalkan D = E 2 . Maka D=

n X

(yi − (a0 + a1 x1 ))2 ,

i =1

∂D = ∂a0 ∂D = ∂a1

... = 0,

(3)

... = 0.

(4)

Pers. (3)-(4) dapat ditulis (disebut persamaan normal): Pn Pn + P i =1 xi a1 = P i =1 yi , Pnna0 n n 2 i =1 xi a0 + i =1 xi a1 = i =1 xi yi . Solusi dari SPL di atas untuk a1 dan a0 adalah Pn Pn Pn Pn Pn n i =1 xi yi − i =1 xi i =1 yi i =1 xi i =1 yi − a1 . a1 = dan a0 = Pn P 2 n n n i =1 xi2 − i =1 xi 8

Mahdhivan Syafwan




Regresi linier: algoritma

9

Mahdhivan Syafwan




Model nonlinier

Dalam masalah nyata, seringkali dijumpai data dengan kecendrungan berbentuk fungsi nonlinier (bukan garis lurus), seperti fungsi eksponensial, fungsi pangkat, fungsi laju pertumbuhan jenuh, fungsi polinomial, dan lain-lain. Kurva regresi untuk model-model nonlinier tersebut dapat diselesaikan dengan bantuan regresi linier, asalkan kurva regresinya dapat ditransformasi ke bentuk regresi linier.

10

Mahdhivan Syafwan




Regresi eksponensial Bentuk umum: y = pe qx . Transformasi pelinieran: ln(y ) = ln(p) + qx.

[tunjukkan!]

Notasikan variabel baru sebagai berikut: y˜ = ln(y ),

a0 = ln(p),

a1 = q.

Dengan demikian diperoleh bentuk regresi linier: y˜ = a0 + a1 x.

11

Mahdhivan Syafwan




Regresi persamaan pangkat Bentuk umum: y = px q . Transformasi pelinieran: ln(y ) = ln(p) + q ln(x).

[tunjukkan!]

Notasikan variabel baru sebagai berikut: y˜ = ln(y ),

x˜ = ln(x),

a0 = ln(p),

a1 = q.

Dengan demikian diperoleh bentuk regresi linier: y˜ = a0 + a1 x˜.

12

Mahdhivan Syafwan




Regresi model laju pertumbuhan jenuh Bentuk umum: y=

px . q+x

Transformasi pelinieran: 1 1 q1 = + . [tunjukkan!] y p px Notasikan variabel baru sebagai berikut: y˜ =

1 , y

x˜ =

1 , x

a0 =

1 , p

a1 =

q . p

Dengan demikian diperoleh bentuk regresi linier: y˜ = a0 + a1 x˜. 13

Mahdhivan Syafwan




Transformasi pelinieran dari beberapa model nonlinier

14

Mahdhivan Syafwan




Koefisien determinasi Seberapa baik suatu regresi menghampiri data? Apa ukurannya? Untuk mengukurnya secara kuantitatif, dapat digunakan koefisien determinasi, R 2 , yang didefinisikan dengan Sres , R2 = 1 − Stot dimana n n X X 2 Sres = [yi − (a0 + a1 xi )] dan Stot = (yi − y¯ )2 , i =1

i =1

dengan y¯ =

n 1X yi . n i =1

Nilai R 2 berkisar dari 0 sampai 1. Jika R 2 mendekati nilai 1, maka kurva regresi tersebut dikatakan semakin baik dalam menghampiri data, dan sebaliknya. 15

Mahdhivan Syafwan




Regresi polinom: pendahuluan

Bagaimana jika kecendrungan pola data tidak dapat ditentukan atau sulit dicari transformasi pelinierannya? Langkah yang biasanya diambil adalah dengan menggunakan regresi berbentuk polinom. Alasan pemilihan regresi polinom adalah karena setiap fungsi kontinu selalu dapat dihampiri dengan fungsi polinom (dibuktikan pada kuliah Analisis Riil).

16

Mahdhivan Syafwan




Regresi polinom: konstruksi (1) Perhatikan kembali n buah titik data (x1 , y1 ), (x2 , y2 ), ..., (xn , yn ). Prosedur kuadrat terkecil pada regresi linier akan diperluas untuk membangun kurva regresi polinom berderajat m yang dinyatakan dengan y = a0 + a1 x + a2 x 2 + · · · + am x m . Catatan: nilai m dan n tidak ada hubungan tertentu. Terapkan rumus galat sebagai berikut: v u n uX 2 yi − (a0 + a1 xi + a2 xi2 + · · · + am xim ) . E =t i =1

17

Mahdhivan Syafwan




Regresi polinom: konstruksi (2) Akan ditentukan nilai a0 , a1 , ..., am yang meminimumkan nilai D = E 2 . Hal ini tercapai ketika ∂D ∂D ∂D = 0, = 0, · · · , = 0. ∂a0 ∂a1 ∂am Langkah di atas menghasilkan persamaan normal berupa SPL dalam a0 , a1 , ..., am sebagai berikut: na0 n X

+

n X

+

n X 2 xi a1

+

n X 3 xi a1

+

n X 2 xi a2

+

n X 3 xi a2

xi a0

+

n X 4 xi a2

. . .

n X m xi a0

. . .

+

n X m+1 xi a1 i =1

+

n X m xi am

+

n X m+1 xi am

+

n X m+2 xi am

+

···

+

···

i =1

Mahdhivan Syafwan

=

n X 2 xi yi

···

+

xi yi

i =1

i =1

n X m+m xi am i =1

SPL di atas dapat diselesaikan dengan salah satu teknik penyelesaian SPL yang sudah dibahas sebelumnya. 18

=

. . .

+

yi

i =1

i =1

n X m+2 xi a2

n X n X

i =1

. . .

+

=

i =1

i =1

i =1

i =1

···

i =1

i =1

i =1

+

i =1

i =1

n X 2 xi a0

i =1

xi a1


. . .

=

n X m xi yi i =1



Regresi polinom: algoritma

19

Mahdhivan Syafwan



Pendahuluan Polinom Interpolasi Lagrange Polinom Interpolasi (Beda Terbagi) Newton

Pendahuluan

Interpolasi/ekstrapolasi bertujuan untuk membangun suatu kurva yang melalui semua titik data. Pada kuliah ini hanya dibahas tentang interpolasi/ekstrapolasi berbentuk polinom. Interpolasi kurva yang dibangun dipakai untuk menaksir nilai f (x) dengan x berada di dalam interval titik-titik data yang diberikan. Ekstrapolasi kurva yang dibangun dipakai untuk menaksir nilai f (x) dengan x berada di luar interval titik-titik data yang diberikan.

20

Mahdhivan Syafwan




Konstruksi awal Diberikan n + 1 titik data (x0 , f (x0 )), (x1 , f (x1 )), ..., (xn , f (xn )), dengan xi 6= xj untuk i 6= j. Urutan nilai xi tidak diperlukan. Akan dikonstruksi sebuah polinom yang melalui semua titik data tersebut. Misalkan polinom tersebut berderajat m: y ≡ pm (x) = a0 + a1 x + a2 x 2 + · · · + am x m . Pertanyaan: Bagaimana hubungan antara m dan n agar diperoleh solusi tunggal untuk koefisien a0 , a1 , ..., am ? Sifat Diberikan n + 1 titik data dengan nilai absis yang berbeda. Maka terdapat secara tunggal polinom derajat m ≤ n yang melalui semua titik data tersebut. 21

Mahdhivan Syafwan




Ilustrasi

Misalkan untuk n + 1 titik data digunakan polinom dengan derajat maksimum n. Maka diperoleh SPL berikut: a0 + a1 x0 + a2 x02 + · · · + an x0n = f (x0 ) a0 + a1 x1 + a2 x12 + · · · + an x1n = f (x1 ) .. .. .. .. .. . . . . . a0 + a1 xn + a2 xn2 + · · · + an xnn = f (xn ) Nilai-nilai koefisien a0 , a1 , ..., an dapat dicari dengan salah satu metode penyelesaian SPL.

22

Mahdhivan Syafwan




Tetapi ... Matriks koefisien (disebut matriks Vandermode) bisa saja singular. Secara analitik, semakin tinggi derajat polinom yang digunakan, semakin akurat hasil yang diperoleh. Namun hal ini harus dibayar dengan beban komputasi yang semakin berat, mengingat ukuran SPL-nya semakin besar. Semakin tinggi derajat polinom yang digunakan, semakin banyak perhitungan komputasi yang harus dilakukan. Akibatnya galat pembulatan akan secara signifikan mempengaruhi hasilnya. Solusinya? 23

Mahdhivan Syafwan




Polinom interpolasi Lagrange - linier Diberikan dua buah titik data (x0 , f (x0 )), (x1 , f (x1 )). Polinom interpolasi yang melalui kedua titik tersebut adalah y ≡ p1 (x) = f (x0 ) +

f (x1 ) − f (x0 ) (x − x0 ). [mengapa?] x1 − x0

Joseph Louis Lagrange menyusun polinom interpolasi tersebut dengan cara lain: y ≡ p1 (x) = f (x0 )

x − x1 x − x0 + f (x1 ) . [justifikasi!] x0 − x1 x1 − x0

Contoh: Diberikan dua buah titik (1, ln(1)) dan (6, ln(6)). Gunakan polinom interpolasi Lagrange derajat satu untuk menaksir nilai ln(2). [Catatan: nilai eksak dari f (2) adalah 0,6931471806]. 24

Mahdhivan Syafwan




Polinom interpolasi Lagrange - kuadratik Diberikan tiga buah titik data (x0 , f (x0 )), (x1 , f (x1 )), dan (x2 , f (x2 )). Polinom interpolasi Lagrange berderajat ≤ 2 yang melalui ketiga titik tersebut mempunyai bentuk: (x − x0 )(x − x2 ) (x − x1 )(x − x2 ) + a1 (x0 − x1 )(x0 − x2 ) (x1 − x0 )(x1 − x2 ) (x − x0 )(x − x1 ) +a2 . (x2 − x0 )(x2 − x1 )

p2 (x) = a0

Dapat dibuktikan bahwa a0 = f (x0 ), a1 = f (x1 ), dan a2 = f (x2 ). [buktikan!] Contoh: Diberikan tiga buah titik (1, ln(1)), (4, ln(4)), dan (6, ln(6)). Gunakan polinom interpolasi Lagrange derajat dua untuk menaksir nilai ln(2). [Catatan: nilai eksak dari f (2) adalah 0,6931471806]. 25

Mahdhivan Syafwan




Polinom interpolasi Lagrange - kasus umum Bentuk umum polinom Lagrange derajat ≤ n yang menginterpolasi titik-titik (x0 , f (x0 )), (x1 , f (x1 )), ..., (xn , f (xn )) adalah (x − x1 )(x − x2 ) · · · (x − xn ) + (x0 − x1 )(x0 − x2 ) · · · (x0 − xn ) (x − x0 )(x − x2 ) · · · (x − xn ) + a1 (x1 − x0 )(x1 − x2 ) · · · (x1 − xn ) .. . (x − x0 )(x − x1 ) · · · (x − xn−1 ) an (xn − x0 )(xn − x1 ) · · · (xn − xn−1 )

pn (x) = a0

Dapat ditunjukkan bahwa a0 = f (x0 ), a1 = f (x1 ), ..., an = f (xn ). 26

Mahdhivan Syafwan




Polinom interpolasi Lagrange - notasi bentuk umum

Bentuk umum dari polinom interpolasi Lagrange diberikan oleh pn (x) =

n X

fi Li (x),

i =0

dimana fi = f (xi ) dan Li (x) =

n Y

j=0,j6=i

27

Mahdhivan Syafwan

x − xj . xi − xj




Polinom interpolasi Lagrange - algoritma

28

Mahdhivan Syafwan




Pendahuluan Seringkali kita memerlukan hampiran polinom yang derajatnya dibangun secara bertahap, yaitu p1 (x), p2 (x), ..., pn (x). Pada metode polinom interpolasi Lagrange, perhitungan seperti ini tidak bisa dilakukan karena tidak ada hubungan antara pi −1 (x) dengan pi (x). Hal ini mengakibatkan proses komputasinya menjadi sangat besar. Sebagai contoh, gunakan polinom Lagrange untuk menginterpolasi empat titik data (1, 1), (2, 2), (3, 3), (4, 4). Solusinya? Metode polinom interpolasi (beda terbagi) Newton.

29

Mahdhivan Syafwan




Polinom interpolasi Newton: konstruksi Polinom interpolasi Newton dibangun sebagai berikut: p1 (x) = a0 + a1 (x − x0 ), p2 (x) = a0 + a1 (x − x0 ) + a2 (x − x0)(x − x1 ), .. . pn (x) = a0 + a1 (x − x0 ) + a2 (x − x0)(x − x1 ) + · · · + an (x − x0)(x − x1 ) · · · (x − xn−1 ). Dari hubungan di atas terlihat hubungan rekursif: pi (x) = pi −1 (x) + ai (x − x0 )(x − x1 ) · · · (x − xi −1 ). Permasalahan: Bagaimana menentukan koefisien a0 , a1 , ..., an ? 30

Mahdhivan Syafwan




Polinom interpolasi Newton: penentuan koefisien (1) Bentuk polinom interpolasi Newton derajat ≤ 1 yang melalui dua titik data (x0 , f (x0 )) dan (x1 , f (x1 )) adalah p1 (x) = a0 + a1 (x − x0 ), f (x1 ) − f (x0 ) . [tunjukkan!] x1 − x0 Bentuk polinom interpolasi Newton derajat ≤ 2 yang melalui tiga titik data (x0 , f (x0 )), (x1 , f (x1 )), dan (x2 , f (x2 )) adalah

dimana a0 = f (x0 ) dan a1 =

p2 (x) = p1 (x) + a2 (x − x0 )(x − x1 ), dimana a2 = 31

f (x2 )−f (x1 ) x2 −x1

−

f (x1 )−f (x0 ) x1 −x0

x2 − x0 Mahdhivan Syafwan

. [tunjukkan!]




Polinom interpolasi Newton: penentuan koefisien (2) Rumusan koefisien polinom Newton melibatkan ekspresi: f (xi ) − f (xi −1 ) , xi − xi −1 yang dikenal dengan beda terbagi orde pertama antara xi −1 dan xi . Untuk perhitungan koefisien polinom Newton, secara umum diperlukan konsep beda terbagi orde ke-nol, pertama, kedua, sampai ke-j sebagai berikut: f [xk ]

=

f [xk , xk+1 ]

=

f (xk ), f [xk+1 ] − f [xk ] , xk+1 − xk

.. . f [xk , xk+1 , xk+2 , ..., xk+j ]

32

=

Mahdhivan Syafwan

f [xk+1 , ..., xk+j ] − f [xk , ..., xk+j−1 ] , xk+j − xk Metode Numerik: Pencocokan Kurva



Polinom interpolasi Newton: bentuk umum Bentuk umum polinom Newton derajat ≤ n yang melalui titik-titik data (xi , f (xi )), i = 0, 1, 2, ..., n adalah sebagai berikut: pn (x) = f [x0 ] + f [x0 , x1 ](x − x0 ) + f [x0 , x1 , x2 ](x − x0 )(x − x1 ) + .. . f [x0 , x1 , x2 , ..., xi ](x − x0 )(x − x1 ) · · · (x − xi −1 ) + .. . f [x0 , x1 , x2 , ..., xn ](x − x0 )(x − x1 ) · · · (x − xn−1 ).

33

Mahdhivan Syafwan




Polinom interpolasi Newton: contoh dan diskusi

34

1

Gunakan polinom Newton untuk menginterpolasi empat titik data (1, 1), (2, 2), (3, 3), (4, 4). Bandingkan dengan perhitungan polinom Lagrange. Apa kesimpulan Anda?

2

Aproksimasi nilai ln(2) dengan menggunakan polinom interpolasi Newton pada dua titik (1, ln(1)) dan (6, ln(6)) . Lakukan hal yang sama namun sekarang dengan menginterpolasi titik (1, ln(1)) dan (4, ln(4)). Bandingkan hasil yang Anda peroleh dengan nilai ’eksak’ dari ln(2). Apa kesimpulan Anda?

3

Lakukan hal yang sama dengan soal no.2, namun dengan menginterpolasi ketiga titik (1, ln(1)), (4, ln(4)), dan (6, ln(6)). Bandingkan dengan hasil pada soal no.2. Apa kesimpulan Anda? Mahdhivan Syafwan




Polinom interpolasi Newton: catatan Secara analitik, hasil hampiran semakin baik jika polinom yang dibangun derajatnya semakin tinggi. Namun secara numerik, konstruksi polinom derajat tinggi akan semakin sensitif terhadap galat pembulatan. Untuk mendapatkan hasil hampiran yang optimal, polinom interpolasi Newton mengkonstruksi hampiran secara bertahap yaitu p0 (x) = f (x0 ), p1 (x), p2 (x), .... Bila pada tahap ke-(k + 1) sudah memenuhi |pk+1 (x) − pk (x)| < ǫ, dimana ǫ galat yang ditetapkan, maka perhitungan dihentikan dan polinom hampirannya adalah pk+1 (x). 35

Mahdhivan Syafwan




Polinom interpolasi Newton: algoritma

Tugas: Diberikan data (xi , f (xi )), i = 1, 2, ..., n. Tuliskan algoritma polinom interpolasi Newton untuk menghampiri nilai f (z) dengan galat ǫ.

36

Mahdhivan Syafwan


PAM 252 Metode Numerik Bab 4 Pencocokan Kurva

Recommend Documents