MASALAH INTERPOLASI 1-D DAN 2-D

Masalah Interpolasi 1-D Masalah Interpolasi 2-D Rujukan

MASALAH INTERPOLASI 1-D DAN 2-D Hendra Gunawan ITB Bandung http://personal.fmipa.itb.ac.id/hgunawan/ Analysis and Geometry Group Bandung Institute of Technology Bandung, Indonesia

Seminar Nasional Analisis Matematika IV 16 April 2011

Hendra Gunawan ITB Bandung http://personal.fmipa.itb.ac.id/hgunawan/ MASALAH Analysis INTERPOLASI and Geometry 1-DGroup DAN Bandung 2-D Institute of Techn


Outline

1

Masalah Interpolasi 1-D Masalah Interpolasi k Titik Bentuk Umum Masalah Interpolasi

2

Masalah Interpolasi 2-D Interpolasi Polinomial Hasil Kali Tensor Dua Sistem Chebyshev

3

Rujukan



Masalah Interpolasi k Titik Bentuk Umum Masalah Interpolasi

Interpolasi Linear

Diberikan dua titik x0 dan x1 di R dengan x0 < x1 , dan dua bilangan c0 , c1 ∈ R, terdapat tepat sebuah garis lurus y = mx + k = f (x) sehingga f (xi ) = ci ,

i = 0, 1.




.




.




Interpolasi Linear Bagian demi Bagian Diberikan n titik xi ∈ R dan n bilangan ci ∈ R, i = 1, . . . , n, interpolan yang paling trivial adalah fungsi linear bagian demi bagian yang menghubungkan titik-titik (xi , ci ) tersebut.




Interpolasi Polinomial

Diberikan tiga titik berbeda x0 , x1 dan x2 di R, dan tiga bilangan c0 , c1 , c2 ∈ R, terdapat tepat sebuah parabola y = f (x) = ax2 + bx + c sehingga f (xi ) = ci ,

i = 0, 1, 2.




Secara umum, diberikan n + 1 titik berbeda xi ∈ R dan n + 1 bilangan real ci , terdapat tepat sebuah polinom berderajat n f (x) = a0 + a1 x + · · · + an xn yang grafiknya melalui titik-titik (xi , ci ), i = 1, . . . , n.




Keluarga fungsi {1, x, . . . , xn } dapat dipakai untuk menyelesaikan masalah interpolasi f (xi ) = ci ,

i = 0, 1, . . . , n,

dengan x0 < x1 < · · · < xn dan ci ∈ R sembarang. Apa kuncinya? Apakah karena {1, x, . . . , xn } bebas linear (selain banyak fungsinya sama dengan banyak data yang diberikan)?




Bagaimana bila kita gunakan {1, x2 } untuk menyelesaikan masalah interpolasi f (−1) = c0 , f (1) = c1 . Jika c0 = c1 , maka terdapat banyak solusi, yakni semua fungsi f yang berbentuk f (x) = c0 [λ + (1 − λ)x2 ]. Jika c0 6= c1 , maka berapapun λ, µ ∈ R, fungsi f (x) = λ + µx2 tidak akan menginterpolasi data tersebut.




Mengapa {1, x2 } gagal? Secara umum, misalkan kita ingin mencari f (x) = λ + µx2 sehingga f (xi ) = ci ,

i = 0, 1.

Maka, kita berhadapan dengan sistem persamaan λ + µx2i = ci ,

i = 0, 1.

Eksistensi solusi sistem ini tergantung pada nilai determinan 1 x20 2 2 1 x2 = x1 − x0 . 1 Karena determinan mungkin bernilai nol, eksistensi solusi tidak dijamin. Kalaupun eksis, ketunggalan tidak dipenuhi.




Determinan Vandermonde Jadi kunci yang membuat {1, x, . . . , xn } dapat selalu menyelesaikan masalah interpolasi f (xi ) = ci , bukan karena mereka 1 x0 1 x1 .. .. . . 1 xn

i = 0, 1, . . . , n,

bebas linear, tapi karena · · · xn0 · · · xn1 Y (xi − xj ) 6= 0. . = .. . .. j
Determinan ini dikenal sebagai determinan Vandermonde.




Sistem Chebyshev

Keluarga fungsi {φ1 , . . . , φn } disebut sistem Chebyshev pada A ⊆ R apabila det[φj (xi )] 6= 0 untuk sembarang x1 < · · · < xn di A. Contoh. {1, x, . . . , xn } merupakan sistem Chebyshev pada R.




Contoh lainnya Keluarga fungsi {sin πx, . . . , sin nπx} merupakan sistem Chebyshev pada (0, 1), sementara {1, cos πx, . . . , cos nπx} merupakan sistem Chebyshev pada [0, 1], dengan

det[sin jπxi ] = 2n(n−1)/2

n Y

sin πxi

j
i=1

det[cos jπxi ] = 2n(n−1)/2

Y (cos πxi − cos πxj ).

Y (cos πxi − cos πxj ). j
[Fajar Yuliawan (ITB)]




Akibat. Jika {φ1 , . . . , φn } adalah sistem Chebyshev pada A, maka untuk setiap x1 < · · · < xn di A dan sembarang bilangan c1 , . . . , cn ∈ R masalah interpolasi f (xi ) = ci , mempunyai solusi tunggal f (x) =

i = 1, . . . , n, n P

αi φi (x).

i=1




Polinom Lagrange Dengan menggunakan {1, x, . . . , xn } sebagai sistem Chebyshev, masalah interpolasi f (xi ) = ci , i = 0, 1, . . . , n mempunyai solusi n P αi xi . tunggal f (x) = i=0

Lagrange menemukan bahwa f dapat dinyatakan sebagai f (x) =

n X

ci φi (x)

i=0

dengan φi (x) :=

Y x − xj . xi − xj j6=i

Perhatikan bahwa φi (xi ) = 1 dan φi (xj ) = 0 untuk j 6= i.




Masalah interpolasi secara umum dapat dinyatakan sebagai Li f = ci ,

i = 1, . . . , n,

dengan Li menyatakan fungsional linear (yang memetakan fungsi f secara linear ke suatu bilangan Li f ) dan ci ∈ R. Contoh. Li f = f (xi ) = nilai f di xi . Rb Li f = a xi f (x) dx = momen ke-i dari f pada [a, b]. Li f = f (i) (c) = turunan ke-i dari f di c.




Bila kita gunakan {v1 , . . . , vn } sebagai basis untuk ruang interpolannya, maka sistem persamaan Li f =

n X

aj Li vj = cj ,

i = 1, . . . , n,

j=1

akan mempunyai solusi tunggal f =

n P

aj vj jika dan hanya jika

j=1

det[Li vj ] 6= 0.




Contoh. Masalah interpolasi momen Z 1 Li f = xi f (x) dx = ci ,

i = 0, 1, . . . , n,

0

mempunyai solusi tunggal f (x) =

n P

ai xi jika dan hanya jika

i=0

R1 R1 ··· 0 x dx R 10 dx R 1 2 x dx ··· 0 x dx det[Li vj ] = 0 . . .. . . . . R . R 1 n+1 1 xn dx dx · · · 0 0 x

R1 n x dx R 10 n+1 dx 0 x .. . R 1 2n 0 x dx

6= 0.

(Di sini kita menggunakan vi (x) = xi , i = 0, 1, . . . , n sebagai basis untuk ruang interpolannya.)




Perhatikan bahwa hv0 , v0 i hv0 , v1 i · · · hv1 , v0 i hv1 , v1 i · · · det[Li vj ] = .. .. .. . . . hvn , v0 i hvn , v1 i · · · dengan hvi , vj i :=

R1 0

, hvn , vn i hv0 , vn i hv1 , vn i .. .

vi (x)vj (x) dx.




Determinan Gram

Determinan tadi merupakan determinan Gram, yang dijamin tidak nol karena {v0 , v1 , . . . , vn } = {1, x, . . . , xn } bebas linear. (Secara geometris, determinan Gram di atas menyatakan kuadrat volume paralelpipedium yang direntang oleh v0 , v1 , . . . , vn .) Jadi masalah interpolasi momen Z 1 Li f = xi f (x) dx = ci ,

i = 0, 1, . . . , n,

0

dijamin mempunyai solusi tunggal berbentuk f (x) =

P

ai xi .




Who’s who..

Masalah interpolasi telah dipelajari cukup lama, setidaknya sejak Newton (1675) dan Taylor (17xx), yang diikuti oleh Lagrange (1795), Legendre (17xx), Gauss, (18xx), Chebyshev (18xx), Lebesgue (18xx), Erd¨os (19xx), dst. Masalah interpolasi 2-D dipelajari antara lain oleh Zakhor pada akhir 1980-an [8, 9]. Pada 2005, Alghofari [1] mempelajari masalah interpolasi yang meminimumkan energi fungsional tertentu. Hasil Alghofari diperluas oleh Gunawan dkk dalam 3 tahun terakhir [2, 3, 7].




Sebagai ilustrasi, fungsi f : [0, 1] → R yang mengenterpolasi (xi , ci ), i = 1, . . . , n, pada pita [0, 1] × R, dan meminimumkan energi potensial beban aksial Z 1 E1 := |f 0 (x)|2 dx 0

adalah fungsi linear bagian demi bagian yang menghubungkan n titik tersebut. Bila fungsinya harus meminimumkan kurvatur Z 1 E2 := |f 00 (x)|2 dx, 0

maka interpolannya merupakan fungsi kubik bagian demi bagian (lihat [2]).



Interpolasi Polinomial Hasil Kali Tensor Dua Sistem Chebyshev

Interpolasi 2-D

Diberikan data berupa nilai ci di titik-titik pi = (xi , yi ), i = 1, . . . , N , pada D ⊆ R2 , ingin dicari fungsi u = f (x, y) sehingga f (pi ) = ci , i = 1, . . . , N.




Interpolasi Polinomial 2-D

Sebagai contoh, diberikan tiga titik (x1 , y1 ), (x2 , y2 ), (x3 , y3 ) di R2 dan tiga bilangan c1 , c2 , c3 ∈ R, kita ingin tahu apakah terdapat tepat sebuah polinom dua peubah u = a + bx + cy sehingga u(xi , yi ) = ci ,

i = 1, 2, 3.

Jawabannya TIDAK SELALU.



Perhatikan determinan 1 x1 y1 1 x2 y2 1 x3 y3


1 x1 y1 = 0 x2 − x1 y2 − y1 0 x3 − x1 y3 − y1

.

Bila (x1 , y1 ), (x2 , y2 ) dan (x3 , y3 ) segaris, maka determinan di atas bernilai nol (karena (x3 − x1 )/(x2 − x1 ) = (y3 − y1 )/(y2 − y1 )). Jadi eksistensi polinom u = a + bx + cy yang menginterpolasi ketiga titik tersebut tidak dijamin. Kalaupun eksis, tidak tunggal.




Sistem Chebyshev pada R2 ? Bila kita mempunyai dua sistem Chebyshev, sebutlah Φ := {φ1 , . . . , φm } dan Ψ := {ψ1 , . . . , ψn }, apakah hasilkali tensornya, yakni {φi (x)ψj (y) : i = 1, . . . , m; j = 1, . . . , n}, membentuk sistem Chebyshev pada R2 ? Dalam perkataan lain, diberikan mn titik di R2 , apakah senantiasa P P terdapat u = i j aij φi (x)ψj (y) yang menginterpolasi data pada mn titik tersebut? Jawabannya NEGATIF. Hasil kali tensor dari dua buah sistem Chebyshev pada R secara umum bukan merupakan sistem Chebyshev pada R2 .




Sebagai contoh, {φ1 (x) := 1, φ2 (x) := x} merupakan sistem Chebyshev pada R, namun {φi (x)φj (y) : i, j = 1, 2} = {1, x, y, xy} 2 bukan merupakan sistem Chebyshev pada PRP: Diberikan empat titik sembarang, tidak dijamin ada u = i j aij φi (x)φj (y) yang menginterpolasi data pada empat titik tersebut.




Walau Demikian ..[3] Teorema. Misal P := {pi = (xi , yi ) : i = 1, . . . , N } membentuk grid persegipanjang m × n pada R2 , yakni P dapat dituliskan ulang sebagai {(xi , yj ) : i = 1, . . . , m; j = 1, . . . , n} dengan m × n = N , a ≤ x1 < · · · < xm ≤ b, dan c ≤ y1 < · · · < yn ≤ d. Misal Φ := {φ1 , . . . , φm } dan Ψ := {ψ1 , . . . , ψn } berturut-turut adalah sistem Chebyshev pada [a, b] dan [c, d]. Maka, masalah interpolasi f (xi , yj ) = cij ,

i = 1, . . . , m; j = 1, . . . , n,

mempunyai solusi tunggal u =

m P n P

aij φi (x)ψj (y).

i=1 j=1




Ide Pembuktian Sistem persamaan yang terkait dengan masalah interpolasi tadi adalah M a = c dengan M = [φk (xi )] ⊗ [ψl (yj )], yang merupakan hasil kali Kronecker dari matriks pertama yang terkait dengan sistem Chebyshev Φ dan matriks kedua yang terkait dengan sistem Chebyshev Ψ. n m Karena det M = det[φk (xi )] det[ψl (yj )] dan kedua determinan di ruas kanan tidak nol, maka det M 6= 0, sehingga sistem persamaan di atas pasti mempunyai solusi tunggal.




Hasil Kali Kronecker

Hasil kali Kronecker dari dua matriks M1 := [aij ]m×m and M2 := [bkl ]n×n didefinisikan sebagai   a11 M2 a12 M2 · · · a1m M2  a21 M2 a22 M2 · · · a2m M2    M1 ⊗ M2 :=   .. .. .. ..   . . . . am1 M2 am2 M2 · · ·

amm M2

p×p

dengan p = mn. Fakta [6]. det M1 ⊗ M2 = (det M1 )n (det M2 )m .




Contoh. Misal kita ingin menginterpolasi data ( 14 , 14 , 12 ), ( 41 , 12 , 1), ( 41 , 34 , 2), ( 21 , 41 , 1), ( 21 , 12 , 2), ( 21 , 34 , 1), ( 34 , 41 , 21 ), ( 34 , 12 , 1), ( 34 , 43 , 1). Perhatikan bahwa titik-titik yang terkait dengan data tersebut membentuk grid persegi 3 × 3 pada (0, 1) × (0, 1):

.




Jika kita menggunakan sistem Chebyshev {sin πx, sin 2πx, sin 3πx} dan {1, cos πy, cos 2πy}, maka interpolan-nya berbentuk u(x, y) =a11 sin πx + a12 sin πx cos πy + a13 sin πx cos 2πy + a21 sin 2πx + a22 sin 2πx cos πy + a23 sin 2πx cos 2πy + a31 sin 3πx + a32 sin 3πx cos πy + a33 sin 3πx cos 2πy.




Sistem persamaannya dapat disederhanakan dengan OBE menjadi               

√

1 0 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0

0 0 0 0 1 0 0 0 0

0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 0 1

2 2 + −1 2 −1 2 3 4 √ − 2 4 1 √ 4 2 2 − −1 2 1 2

1 2

1 2

        .      




Kita peroleh √ u(x, y) =

2 1 + 2 2

! sin πx −

1 1 sin πx cos πy − sin πx cos 2πy 2 2

√ 1 2 1 + sin 2πx − sin 2πx cos πy + sin 2πx cos 2πy 4 4 4 ! √ 2 1 1 1 + − sin 3πx − sin 3πx cos πy + sin 3πx cos 2πy 2 2 2 2 sebagai interpolan yang dikehendaki.




Lebih Jauh .. Misal G = {(ai , bi , ci ) : i = 1, 2, . . . , N } himpunan titik di A1 × A2 × R, dan H = {(xi , yj ) : i = 1, . . . , m; j = 1, . . . , n} adalah grid persegipanjang ’minimal’ yang memuat {(ai , bi ) : i = 1, . . . , N }. Di sini kita asumsikan bahwa {(ai , bi ) : i = 1, . . . , N } sendiri bukan grid persegipanjang, sehingga N < mn. Misal {φ1 , . . . , φm } dan {ψ1 , . . . , ψn } adalah sistem Chebyshev pada A1 dan A2 berturut-turut. Maka kita dapat menggunakan u(x, y) =

m X n X

aij φi (x)ψj (y)

(1)

i=1 j=1

sebagai interpolan G.




Substitusikan titik-titik pada G ke persamaan (1), kita peroleh sistem persamaan dengan N persamaan dan mn variabel. Karena rank matriksnya sama dengan N < mn, maka sistem mempunyai banyak solusi. Dalam hal ini terdapat banyak nilai aij yang akan menjadikan fungsi u pada (1) sebagai interpolan G.




Contoh. Misalkan kita ingin menginterpolasi data ( 14 , 12 , 2), ( 41 , 34 , 1), ( 21 , 14 , 2), ( 21 , 12 , 3), ( 12 , 43 , 2), ( 43 , 14 , 1), ( 43 , 12 , 2). Titik-titik yang terkait dengan data di atas termuat dalam grid persegi 3 × 3 pada (0, 1) × (0, 1):




Jika kita gunakan {sin πx, sin 2πx, sin 3πx} dan {1, cos πy, cos 2πy} sebagai sistem Chebyshev, maka interpolan-nya berbentuk u(x, y) =a11 sin πx + a12 sin πx cos πy + a13 sin πx cos 2πy + a21 sin 2πx + a22 sin 2πx cos πy + a23 sin 2πx cos 2πy + a31 sin 3πx + a32 sin 3πx cos πy + a33 sin 3πx cos 2πy.



Substitusikan  1  0   0   0    0   0 0


data dan sederhanakan sistemnya dengan OBE:  √ −1 0 0 0 0 0 0 0 2 + 12 2  0 1 0 0 0 0 0 −1 0  0 1 0 0 0 0 0 −1 −1    0 0 0 1 0 0 0 −1 0 . √  0 0 0 1 0 0 0 −1 2 − 1  √  − 2  0 0 0 0 1 0 −1 0 2 √ 3 −1 0 0 0 0 0 1 0 2 − 2 2




Salah satu interpolan yang memenuhi sistem persamaan ini adalah: √ 1 −1 √ 2+ 2 − 1 sin 2πx u(x, y) = sin πx − sin πx cos 2πy + 2 2 √ 3 + 2− 0.25 sin 2πx cos 2πy. 2




Catatan

Sebagian hasil yang disajikan merupakan hasil penelitian bersama dengan E. Rusyaman (Unpad). Hasil-hasil tersebut telah pula diperumum ke dimensi N oleh L. Ambarwati (Mhs S3 MA-ITB). Selain itu, ditemukan pula bahwa polinom dua peubah berderajat n selalu dapat menginterpolasi data pada 21 (n + 1)(n + 2) titik yang membentuk grid segitiga. Sebagian hasil penelitian ini telah dikirim ke beberapa jurnal di dalam dan luar negeri, dan sebagian lainnya masih sedang dalam proses penulisan.




Ucapan Terimakasih

Penelitian ini didanai oleh Program Penguatan Riset Institusi Tahun 2010/2011.



A.R. Alghofari (2005), Problem in Analysis Related to Satellites, Ph.D. Thesis, UNSW, Sydney, Australia. H. Gunawan, F. Pranolo, E. Rusyaman (2008), “An interpolation method that minimizes an energy integral of fractional order”, in D. Kapur (Ed.): Asian Symposium on Computer Mathematics 2007, LNAI 5081, 151-162, Springer-Verlag, Berlin Heidelberg. H. Gunawan, E. Rusyaman, L. Ambarwati (2009), “Surfaces with prescribed nodes and minimum energy integral of fractional order”, submitted. G.B. Lorenz (1966), Approximation of Functions, AMS Chelsea Publishing, USA. C.W. Patty (1993), Foundation of Topology, PWS Publishing Company, USA.



C.R. Rao and M.B. Rao (1998), Matrix Algebra and Its Applications to Statistics and Econometric, World Scientific, Singapore. E. Rusyaman, H. Gunawan, A.K. Supriatna, R.E. Siregar (2010), “Eksistensi interpolan sinusoida berdimensi dua” (in Indonesian), J. Mat. Sains. A. Zakhor (1987), Reconstruction of Multidimensional Signals from Multiple Level Threshold Crossings, Ph.D. Dissertation, MIT, USA. A. Zakhor and G. Alvstad (1992), “Two-dimensional polynomial interpolation from nonuniform samples”, IEEE Trans. Signal Processing 40, 169–180.


MASALAH INTERPOLASI 1-D DAN 2-D

Recommend Documents