Pertemuan 9 : Interpolasi 1 (P9) Interpolasi. Metode Newton Metode Spline

Pertemuan 9 : Interpolasi

1

(P9) Interpolasi • Metode Newton • Metode Spline

Semester Pendek 2011

Departemen Matematika FMIPA IPB


2

Interpolasi Newton • Polinomial Maclaurin dan polinomial Taylor menggunakan satu titik pusat, x0 untuk menghampiri suatu fungsi f(x). • Bila lebih dari satu titik pusat yang digunakan, misalnya : x0, x1, …, xn, maka hasilnya disebut polinomial Newton. Semester Pendek 2011



3

Teorema Polinomial Newton : • Andaikan dan untuk k = 0, 1, …, n mempunyai nilai-nilai yang berbeda, maka dengan adalah polinomial yang dapat dipakai untuk mendekati f(x) :




4

• Polinomial Newton melalui (n+1) titik

yaitu untuk k = 0, 1, …, n. • Sisaan

berbentuk :

untuk beberapa c yang terletak pada interval [a,b]. Koefisien ai dikonstruksi menggunakan beda bagi (divided difference). Semester Pendek 2011



5

• Kurva berikut memberikan ilustrasi suatu polinomial Newton derajat 3.




6

Beda bagi (Divided Difference) Orde I. • Bila diberikan sembarang fungsi f(x) dan 2 titik, x0 dan x1, Beda bagi orde pertama dari suatu fungsi f(x) didefinisikan sebagai berikut : • Menggunakan teorema nilai antara : untuk nilai c antara x0 dan x1,




7

• Lebih jauh dapat ditunjukkan bahwa

• Beda bagi orde dua untuk tiga titik yang berbeda, x0 , x1 dan x2 didefinisikan sebagai :




8

• Dari sini dapat ditunjukkan bahwa untuk nilai c antara x0 dan x2,

• Bila


maka



9

Contoh: Bila x0 =1.0, x1 =1.1 dan x2 =1.2, maka:




10

Sebagai perbandingan:

Contoh:

maka tabel beda bagi dapat dikonstruksi sbb: Semester Pendek 2011



11

dengan:




12

• Menggunakan pendekatan polinomial Newton, contoh di atas menghasilkan




13

Contoh: • Buat polinomial Newton derajat n = 1, 2, 3, 4, 5 untuk menghampiri fungsi f(x) = cos(x) pada interval [x0, xn] = [0, 1], dengan partisi yang sama.

x , y   0, f (0), 0.2, f (0.2), 0.4, f (0.4), k

5 k k 0


0.6, f (0.6) , 0.8, f (0.8) , 1, f (1) 



14

Jawab: Gunakan {{0, 1},{0.2, 0.980067}} untuk mengonstruksi polinomial interpolasi Newton derajat 1,




15

Bila digunakan {{0,1},{0.2, 0.980067},{0.4, 0.921061}} pada interval [0, 0.4]. Hasilnya adalah:




16

Bila digunakan 4 titik, {{0, 1},{0.2, 0.980067}, {0.4, 0.921061},{0.6, 0.825336}} pada interval [0, 0.6] diperoleh polinomial derajat 3 berikut :




17

Bila digunakan 5 titik, {{0, 1},{0.2, 0.980067}, {0.4, 0.921061},{0.6, 0.825336}, {0.8, 0.696707} } pada interval [0, 0.8] diperoleh polinomial derajat 4 berikut :





18



19

Lagrange vs. Newton (n=5)

melibatkan 30 perkalian, dan sampai 35 penjumlahan atau pengurangan

melibatkan 15 perkalian, dan sampai 20 penjumlahan atau pengurangan




20

• Secara umum, polinomial Lagrange derajat n memerlukan n(n+1) perkalian serta n(n+2) penjumlahan dan pengurangan, sedangkan polinomial Newton derajat n memerlukan n(n+1)/2 perkalian serta n(n+3)/2 penjumlahan dan pengurangan. • Jadi mana yang lebih efisien?




21

Teorema Batas Kesalahan • Andaikan f(x) didefinisikan pada [a, b] yang memuat partisi yang sama • Andaikan pula f dan turunan f sampai orde (n+1) kontinyu serta terbatas pada subinterval [x0, x1], [x0, x2], [x0, x3], [x0, x4], dan [x0, x5], yaitu | f(n+1)(x) | ≤ M(n+1) untuk x0 < x < xn dengan n = 1, 2, 3, 4, 5. Semester Pendek 2011



22

Faktor kesalahan yang bersesuaian dengan kasus-kasus tersebut memiliki batas atas berikut utk

utk

utk




23

untuk

untuk




24

Contoh: • Selidiki kesalahan yang timbul akibat penggunaan metode hampiran Newton orde n = 1, 2, 3, 4, dan 5 pada contoh di atas.

Jawab: untuk n=1, gunakan [0,0.2 ] Kesalahan yang terjadi : e1(x) = f(x) – P1(x),





25



26






27



28






29



30

Jawab: untuk n=4, gunakan [0,0.8] Kesalahan yang terjadi : e4(x) = f(x) – P4(x),





31



32

Jawab: untuk n=5, gunakan [0,1] Kesalahan yang terjadi : e5(x) = f(x) – P5(x),





33



34

Interpolasi Spline: • Apabila ingin dilakukan interpolasi pada data dalam tabel berikut :




35

• Salah satu cara adalah dengan membuat interpolasi linear pada setiap segmen data seperti berikut :

• Namun cara ini akan menimbulkan sudut pada setiap segmen garis, yang kurang dikehendaki. Semester Pendek 2011



36

• Cara lain adalah dengan pendekatan interpolasi kuadratik pada setiap segmen




37

• Atau dengan menggunakan interpolasi polinomial seperti berikut :




38

Interpolasi menggunakan Piecewise Polynomial • untuk fitting jumlah data yang banyak. • untuk menghindari penggunaan polinomial derajat tinggi • bermanfaat, al. fitting data dapat dilakukan dengan polinomial derajat rendah. • Menggunakan fungsi interpolant berbeda pada setiap sub-interval • Titik disebut knots atau breakpoints • Contoh: piecewise linear, Hermite interpolation Semester Pendek 2011



39

Contoh: Agar diperoleh solusi yang unik, jumlah parameter harus sama dengan jumlah persamaan. dengan n knots mempunyai 4(n-1) parameter yang harus ditentukan




40

• 2(n-1) persamaan dari plot data • (n-2) persamaan dari syarat kekontinuan turunan pertama • n persamaan lainnya bisa untuk persyaratan tambahan • 3(n-4) persamaan spt pada Interpolasi Hermite • (n-2) persamaan dari syarat kekontinuan turunan kedua • 2 persamaan lainnya bebas Semester Pendek 2011



Contoh

41

Tentukan interpolasi cubic spline dari titik

Delapan parameter yang akan ditentukan: di di

Delapan persamaan yang akan digunakan:





42



43

• Hermite Cubic mengutamakan kemonotonan




44

• Cubic Spline mengutamakan kemulusan




45

: Piecewise constant : Piecewise linear

: Piecewise quadratic : Piecewise polinomial derajat k Semester Pendek 2011




46




47




48


Pertemuan 9 : Interpolasi 1 (P9) Interpolasi. Metode Newton Metode Spline

Recommend Documents