DEKOMPOSISI FUNGSI MULTIVARIAT

DEKOMPOSISI FUNGSI MULTIVARIAT

TESIS

Oleh MARLAN 077021016/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009

Marlan : Dekomposisi Fungsi Mutivariat, 2009

DEKOMPOSISI FUNGSI MULTIVARIAT

TESIS

Diajukan Sebagai Salah Satu Syarat untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh MARLAN 077021016/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009


Judul Tesis Nama Mahasiswa Nomor Pokok Program Studi

: : : :

DEKOMPOSISI FUNGSI MULTIVARIAT Marlan 077021016 Matematika

Menyetujui, Komisi Pembimbing

(Prof. Dr. Herman Mawengkang) Ketua

(Prof. Dr. Opim Salim S. MSc) Anggota

Ketua Program Studi

Direktur

(Prof. Dr. Herman Mawengkang)

(Prof. Dr. Ir. T.Chairun Nisa. B ,M.Sc)

Tanggal lulus: 2 Juni 2009


Telah diuji pada Tanggal 2 Juni 2009

PANITIA PENGUJI TESIS Ketua

: Prof. Dr. Herman Mawengkang

Anggota

: 1. Prof. Dr. Opim Salim Sitompul, MSc 2. Dr. Tulus, M.Si 3. Drs. Sawaluddin, MIT


ABSTRAK

Tesis ini menyajikan suatu metode yang mampu mendekomposisi fungsi f dari d variabel menjadi penjumlahan 2d suku. Dekomposisi tergantung pada pilihan atas d proyeksi komutatif P1 , P2 , · · · , Pd , di mana Pj (f ) tidak tergantung pada variabel xj . Setiap suku pada dekomposisi hanya tergantung pada variabel indeks dengan himpunan bagian {1, 2, · · · , d}. Misalkan f dapat dinyatakan sebagai suatu penjumlahan untuk beberapa himpunan bagian u ⊆ {1, 2, · · · , d} di mana tidak terdapat suku yang simultan terhadap variabel indeks u. Pada dekomposisi (setiap pilihan dari P1 , P2 , · · · , Pd ) untuk semua suku di mana u adalah himpunan bagian yang bernilai sama dengan nol. Tujuan dari tesis ini adalah untuk mendapatkan metode yang sesuai dan mudah dalam melakukan dekomposisi terhadap fungsi multivariat. Dalam tesis ini diuraikan dekomposisi ANOVA dan dekomposisi anchored. Dari hasil pembahasan pada tesis ini menunjukkan, bahwa metode yang terbaik adalah dekomposisi anchored. Kata kunci: dekomposisi, dekomposisi ANOVA, dekomposisi anchored

i Marlan : Dekomposisi Fungsi Mutivariat, 2009

ABSTRACT

We present formulas that allow us to decompose a function f of d variables into a sum of 2d terms. The decomposition depends on the choice of d commuting projections P1 , P2 , · · · , Pd , where Pj (f ) does not depend on the variable xj . Each term in the decomposition depends only on the variables indexed by a particular subset of {1, 2, · · · , d}. These decomposition formulas are minimal in the following sense. Suppose that f is expressible as a sum in which, for some subset u ⊆ {f1 , f2 , · · · , d}, there is no term that depends simultaneously on all of the variables indexed by u. Then in our decomposition (for every choice of P1 , P2 , · · · , Pd ) all terms for which u is a subset are equal to zero. The aim of this thesis is to get appropriate and easy method in conducting decomposition of multivariate function. In this thesis we elaborated ANOVA decomposistion and anchored decompositions. From discussion result at this thesisi indicated that the best method is anchored decomposition. Keyword: decomposition, ANOVA decomposition, anchored decomposition

ii Marlan : Dekomposisi Fungsi Mutivariat, 2009

KATA PENGANTAR Puji dan syukur penulis panjatkan kehadirat Allah SWT, karena berkat rahmat dan karunia-Nya penulis dapat menyelesaikan tesis dengan judul ”Dekomposisi Fungsi Multivariat”. Tesis ini merupakan salah satu syarat untuk menyelesaikan kuliah di Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara. Dalam menyelesaikan tesis ini penulis banyak mendapat dukungan dari berbagai pihak, maka pada kesempatan ini penulis mengucapkan terima kasih, dan penghargaan yang sebesar-besarnya kepada: Prof. dr. Chairuddin P. Lubis, DTM&H, Sp.A(K) selaku Rektor Universitas Sumatera Utara. Drs. Ulung Napitu, M.Si selaku Rektor Universitas Simalungun yang telah memberi ijin kepada penulis untuk kuliah di Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara. Prof. Dr. Zainuddin, MPd selaku Koordinator KOPERTIS Wilayah-I (SUMUTNAD), yang telah memberi ijin kepada penulis untuk kuliah di program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara. Prof. Dr. Ir. T. Chairun Nisa, B. M.Sc selaku direktur Sekolah Pascasarjana Universitas Sumatera Utara yang telah memberi kesempatan kepada penulis untuk mengikuti perkuliahan di Program Studi Magister Matematika. Prof. Dr. Herman Mawengkang selaku Ketua Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara dan juga sebagai

iii Marlan : Dekomposisi Fungsi Mutivariat, 2009

Pembimbing I, yang telah memberikan bimbingan dan petunjuk kepada penulis sehingga tesis ini dapat diselesaikan. Prof. Dr. Opim Salim Sitompul, MSc sebagai dosen Pembimbing II yang telah memberikan bimbingan, masukan dan motivasi untuk perbaikan dan kesempurnaan tesis ini. Dr. Tulus, M.Si yang telah banyak memberikan koreksi, bimbingan, masukan dan motivasi untuk perbaikan dan kesempurnaan tesis ini. Drs. Sawaluddin, MIT yang telah banyak memberikan koreksi, bimbingan, masukan dan motivasi untuk perbaikan dan kesempurnaan tesis ini. Seluruh Staf Pengajar pada Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara yang telah membekali penulis ilmu pengetahuan selama perkuliahan hingga selesai. Sahabat-sahabat mahasiswa angkatan 2007 atas kerjasama, kekompakan dan kebersamaan yang telah terjalin dengan baik selama perkuliahan hingga selesai. Saudari Misiani, S.Si selaku Staf Administrasi pada Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara yang telah banyak membantu administrasi perkuliahan penulis. Secara khusus penulis menyampaikan rasa terima kasih kepada istri tercinta Tjatur Amperawati, anak-anak tersayang Alfathan Kurnia Mawardi, Hanifan Dwiputra Ilham, Nabila Fadia Alifia dan seluruh keluarga, berkat dorongan dan perhatiannya yang disertai doa, penulis dapat menyelesaikan pendidikan ini. Teman-teman Staf Pengajar di Universitas Simalungun Pematangsiantar

iv Marlan : Dekomposisi Fungsi Mutivariat, 2009

yang dengan penuh semangat memberi motivasi kepada penulis hingga selesainya pengerjaan ini. Hanya ucapan syukur dan terima kasih yang dapat penulis sampaikan kepada semua pihak yang telah memberi dukungan, doa, motivasi, bimbingan dan arahan selama perkuliahan hingga penyelesaian tesis ini. Semoga amal kebajikan yang telah diberikan kepada penulis menjadi amal ibadah dan mendapat ganjaran kebajikan dari Allah SWT, Amin. Semoga tesis ini bermanfaat bagi penulis, pembaca dan pihak-pihak yang memerlukannya.

Medan, Juni 2009 Penulis,

Marlan

v Marlan : Dekomposisi Fungsi Mutivariat, 2009

RIWAYAT HIDUP Marlan, dilahirkan di kota Pematangsiantar pada tanggal 15 Agustus 1958, merupakan anak ketujuh dari 9 (sembilan) bersaudara dari Ayah H. Sulaiman Wiro (Alm) dan ibunda Hj. Maimunah (Alm). Menamatkan Sekolah Dasar (SD) Negeri Latihan SGBI Pematangsiantar pada tahun 1970, Sekolah Lanjutan Tingkat Pertama (SLTP) Negeri 2 Pematangsiantar pada tahun 1973, Sekolah Menengah Atas (SMA) jurusan IPA di SMA Negeri 1 Pematangsiantar tahun 1976. Pada tahun 1977 memasuki perguruan tinggi Negeri FMIPA USU Medan Jurusan Matematika dan memperoleh gelar Sarjana Matematika pada tahun 1984. Pada tahun 2007 mengikuti Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara, dengan beasiswa BPPS. Sejak tahun 1987 hingga saat ini bertugas sebagai staf pengajar Kopertis Wilayah I SUMUT-NAD dpk pada Universitas Simalungun Pematangsiantar.

vi Marlan : Dekomposisi Fungsi Mutivariat, 2009

DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

iii

RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.5 Metodologi Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

BAB 3 DEKOMPOSISI DAN ORTOGONALITAS . . . . . . . . . . . . . . . .

8

3.1 Rumus Umum Dekomposisi . . . . . . . . . . . . . . . . . . . . . . . .

8

3.2 Ortogonalitas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

BAB 4 PEMBAHASAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

4.1 Dekomposisi ANOVA . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

4.2 Dekomposisi Anchored . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

vii Marlan : Dekomposisi Fungsi Mutivariat, 2009

4.3 Dekomposisi Minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

BAB 5 KESIMPULAN DAN SARAN . . . . . . . . . . . . . . . . . . . . . . . . .

28

5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

5.2 Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

viii Marlan : Dekomposisi Fungsi Mutivariat, 2009

BAB 1 PENDAHULUAN

1.1 Latar Belakang Integral dengan ratusan atau ribuan variabel sekarang ini muncul di bidang praktis seperti statistik dan matematik keuangan. Jumlah d variabel yang muncul dalam integran diketahui sebagai dimensi (nominal) masalah integrasi. Aproksimasi untuk integral berdimensi-tinggi ini biasanya diperoleh dengan mengambil sampel integran di banyak titik dalam daerah integrasi. Sayangnya, hasil-hasil klasik menunjukkan bahwa jumlah titik sampel yang dibutuhkan untuk mencapai batas kesalahan tertentu biasanya meningkat secara eksponensial dengan dimensi d, yang menjadikan pendekatan tidak layak jika d besar. Ini dikenal sebagai kesalahan dimensionalitas. Di samping kesalahan ini, hasil-hasil empiris terbaru ini menunjukkan bahwa algoritma quasi-Monte Carlo (QMC) bisa efektif mengatasi sebagian integral dimensi-tinggi yang timbul pada masalah pembiayaan. Metode Monte Carlo di bidang pembiayaan diperkenalkan oleh Boyle (1977). Paskov dan Traub (1995) mempublikasikan penggunaan metode quasi-Monte Carlo (QMC) untuk menaksir harga obligasi. Sejak itu, banyak peneliti berusaha menjelaskan keberhasilan QMC. Sekarang sudah umum diyakini bahwa integran yang bisa berhasil diatasi mempunyai dimensi efektif rendah. Ini berarti bahwa fungsi tergantung dengan cara yang semakin berkurang pada variabel berturut-turut, atau bahwa fungsi bisa diaproksimasi dengan baik dengan perjumlahan fungsi yang hanya melibatkan sejumlah kecil variabel. 1 Marlan : Dekomposisi Fungsi Mutivariat, 2009

2 Kasus yang disebut terakhir sangat penting di dalam praktek. Walaupun fungsi f tergantung pada d variabel, dikatakan bahwa f berorde q, q ≤ d, dapat dinyatakan f sebagai perjumlahan dari suku-suku yang masing-masing tergantung paling banyak pada q dari d variabel, dan q adalah bilangan terkecil dengan sifat ini. Secara intuitif, semakin kecil orde q, semakin mudahlah fungsi dikembangkan. Sebagai contoh, misalnya, fungsi f (x1 , x2, x3) = x1 + x22 + cos(x2 x3) adalah berorde 2. Contoh lainnya diberikan oleh polinomial multivariat, karena ordenya tidak lebih besar dari derajat aljabarnya. Sehingga suatu aljabar polinomial tingkat rendah mempunyai orde kecil tanpa memperhatikan jumlah d variabel. Rumus umum dekomposisi fungsi dari d variabel menjadi perjumlahan dari 2d suku, dengan masing-masing suku tergantung pada sekelompok variabel yang indeksnya disusun menurut himpunan bagian khusus dari {1, 2, · · · , d}. Karena dekomposisi sedemikian tidak unik, menimbulkan tanda tanya bahwa orde q dari f tergantung pada dekomposisi spesifik. Jika fungsi f mempunyai orde q maka semua suku dalam rumus dekomposisi yang tergantung pada lebih dari q variabel sama dengan nol. Sifat minimal dari rumus dekomposisi tetap lebih kuat daripada yang berusan dinyatakan. Andaikan bahwa f dapat direpresentasikan sebagai perjumlahan dengan cara sedemikian rupa sehingga untuk suatu himpunan bagian tertentu dari variabel (misalnya, katakanlah x1, x2 , x5) tidak ada suku yang tergantung secara simultan pada semua variabel ini. Kemudian dalam rumus dekomposisi setiap suku yang mencakup semua variabel ini sama dengan nol.


3 Juga dikaji rumus dekomposisi dalam penetapan reproduksi kernel ruang Hilbert. Dengan syarat-syarat biasa, ditunjukkan bahwa rumus dekomposisi ortogonal terhadap inner product ruang Hilbert. Rumus dekomposisi meliputi dekomposisi ANOVA dan dekomposisi anchored sebagai kasus khusus. Terminologi ANOVA dari f dinyatakan sebagai integral multivariat f yang sulit diselesaikan. Sementara dekomposisi anchored hanya didasarkan pada sampel-sampel dari fungsi. Rumus dekomposisi anchored mempunyai banyak aplikasi untuk menyelesaikan soal-soal dimensi-tinggi. Oleh karena itu, jika ingin mengintegrasikan, mengaproksimasi atau menyelesaikan problema linier untuk f dapat digantikan ke permasalahan linier O(dq ) dengan fungsi qvariasi. Jika kompleksitas pada masalah ini merupakan eksponensial pada q, maka tidak sulit untuk mendapatkan nilai q yang kecil, yang merupakan nilai total yang masih merupakan polinomial di d.

1.2 Perumusan Masalah Dekomposisi merupakan suatu proses yang dinamis dan sangat dipengaruhi oleh keberadaan pengurai. Multivariat timbul, karena tidak semua gejala itu didasarkan pada hubungan dua variabel saja, artinya multivariat mengkaitkan banyak variabel. Dekomposisi yang dilakukan terhadap fungsi multivariat diharapkan dapat menemukan adanya metode pengurai yang sesuai.

1.3 Tujuan Penelitian Tujuan dari penelitian ini adalah untuk mendapatkan sebuah metode dalam melakukan dekomposisi terhadap fungsi multivariat.


4 1.4 Kontribusi Penelitian Kontribusi dari penelitian ini adalah adanya metode untuk dekomposisi fungsi multivariat.

1.5 Metodologi Penelitian Metodologi penelitian yang digunakan dalam pembahasan tesis ini ini adalah bersifat literatur. Untuk menentukan dekomposisi pada fungsi multivariat dilakukan langkah-langkah sebagai berikut: a. Objek dari penelitian ini adalah fungsi f dengan d variabel. b. Menguraikan rumus umum dekomposisi. c. Menguraikan dekomposisi ANOVA. d. Menguraikan dekomposisi anchored.


BAB 2 TINJAUAN PUSTAKA

Fungsi dekomposisi merupakan masalah yang dibentuk fungsi polinomial f (x) sebagai sebuah fungsi komposisi g(h(x)) dari polinomial berderajat yang lebih kecil. Fungsi komposisi ini berguna dalam penyederhanaan kasus-kasus polinomial berderajat lebih tinggi dan disajikan secara primitif oleh mayor symbolic dari sistem aljabar. Masalah dekomposisi untuk fungsi multivariat, fungsi rasional dan fungsi aljabar juga sangat menarik perhatian peneliti Borwen dan Lewis (1992), Gutierrez et al. (2002), Kozen dan Landau (1996). Teori fungsi dekomposisi diperkenalkan oleh Ritt (1922) dan dikembangkan lebih lanjut oleh Fried dan MacRae (1969), dan Dorey dan Whaples (1974). Dekomposisi dari f (x) = F (x) berhubungan sangat erat dengan field antara F (f ) dan F (x) oleh Dorey dan Whaples (1974) serta Schinzel (1982) Permasalahan dekomposisi terbagi dalam dua, yaitu tame dan wild. Kasus tame jika karakteristik dari F tidak memisahkan derajat g, termasuk karakteristik 0. Dalam kasus tame ini, persoalan adalah rasional, jika f menguraikan perluasan dari F , kemudian keatas F . Schinzel (1982) dan dekomposisi maksimal adalah penempatan yang khas dari faktor dekomposisi linier dan komutatif dari x dan fungsi Chebyshev. Ritt (1922). Analisa algoritma untuk fungsi dekomposisi disajikan pertama sekali oleh Barton dan Zippel (1985), serta Alagar dan Thanh (1985), yang menyajikan fungsi pada field dari karakteristik nol. Kedua penyelesaian melibatkan faktorisasi fungsi

5 Marlan : Dekomposisi Fungsi Mutivariat, 2009

6 dan eksponensial waktu. Kozen dan Landau (1989) menemukan pertama sekali algoritma fungsi waktu dalam kasus tame yang tidak memerlukan faktorisasi. Batas waktu adalah O(n3 ), O(n2 ) jika F didukung FFT. Algoritma yang sama ditemukan oleh Gutierrez dan kawan-kawan (1989). Kozen dan Landau juga memberikan algoritma NC yang efisien dengan batas waktu O(log 2 n). Beberapa perluasan dan variasi telah diteliti Dickenson (1987) dan von zur Gathen (1990) meneliti dekomposisi fungsi multivariat. Gutierrez (1991) menyajikan suatu algoritma dekomposisi fungsi pada domain faktorial. von zur Gathen dan weiss (1995) menyajikan metode eksponensial untuk mendapatkan bentuk dekomposisi f (x) = g(h(x), k(x)) untuk g(y, z) yang homogen. Casperson dan kawan-kawan (1996) menyajikan satu algoritma bahwa, diberikan satu f (x) yang tak teredukasi, mendapatkan g(x) dan h(x) sedemikian hingga f (x) membagi g(h(x)). Binder (1995) menyajikan metode yang cepat untuk menghitung generator Lroth dari gabungan field dua buah fungsi. Hommes dan Kova’acs (1992) meneliti dan mendefinisikan masalah dekomposisi sin-cosin: menentukan apakah fungsi bivariat f (s, c) yang diberikan mempunyai dekomposisi berbentuk f (s, c) = g(h(s, c)) modulo s2 + c2 + 1. Permasalahan ini diaplikasikan dalam robot kinematika. Gutierrez dan Recio (1998) menyajikan algoritma massa-kubik yang tidak memerlukan faktorisasi. Ini didasarkan pada pendekatan akar dari f (s, c) modulo s2 + c2 + 1. Zippel (1991) memperkenalkan algoritma fungsi waktu untuk menguraikan fungsi rasional pada setiap field, yang membenarkan faktorisasi fungsi yang efisien. Pendekatannya menemukan relasi yang kuat untuk teorema Lroth. Alonso dan kawan-kawan (1995) memberikan dua algoritma fungsi waktu untuk dekomposisi


7 fungsi rasional itu sebanding dengan penelitian Zipple. Mereka juga menyajikan beberapa aplikasi: tetap reparametrization dari yang tidak tetap, kurva berparameter, menghitung field berikutnya secara sederhana semata-mata perluasan transcendental dari F , dan menyediakan tes birationality untuk subfield dari F (x). Kazen, Landau dan Zippel (1996) menunjukkan masalah dekomposisi fungsi aljabar. Mereka menemukan hubungan resultan univariat fungsi alajabar field dan ditunjukkan bahwa masalah utama dekomposisi apabila beberapa kuasa dari sebuah fungsi polinomial f (x, z) dapat dinyatakan sebagai resultan dengan condong ke y dari dua fungsi bivariat g(x, y), h(y, z). Mereka menetapkan syarat penting dan cukup untuk adanya dekomposisi nontrivial dan dikelompokkan sebagai dekomposisi ke isomorpisme. Mereka juga memberikan algoritma waktu eksponensial untuk mendapatkan dekomposisi nontrivial jika salah satu ada. Dekomposisi fungsi untuk polinomial Laurent diajukan oleh Watt (2004) yang memandang kasus f = g ◦ h dimana g univariat dan h multivariat. Ia menunjukkan suatu algoritma untuk menentukan dekomposisi. Algoritma ini diawali dengan pemberian bobot kepada suatu variabel untuk membuat bentuk bobot derajat nol dalam f konstan. Bagian derajat positip dan negatip dari h kemudian dibentuk kembali secara terpisah, cara yang sama dari Kozen dan Landau, tetapi dengan syarat-syarat tingkatan perlakuan kumpulan homogen dari pada monomial individu. Kemudian syarat-syarat polinomial univariat g dibentuk kembali derajat perderajat menggunakan proyeksi univariat yang umum dari h.


BAB 3 DEKOMPOSISI DAN ORTOGONALITAS

3.1 Rumus Umum Dekomposisi Misalkan F adalah ruang linier dari fungsi riil f (x) = f (x1, x2 , . . . , xd ) yang didefinisikan pada domain D ⊆ Rd . Misalkan [1 . . . d] adalah notasi untuk himpunan indeks {1, 2, . . . , d}, [I . . . d] = {1, 2, . . . , d} Untuk setiap j ∈ [1 . . . d], misalkan Pj : F → F adalah operator linier dengan sifat-sifat berikut:    Pj (f ) = f jika f tidak tergantung pada xj    Pj (f ) tidak tergantung pada xj , dan      Pi (Pj (f )) = Pj (Pi (f )) untuk i 6= j

(3.1)

Pada catatan bahwa Pj2 (f ) = Pj (f ), dengan demikian (Pj )dj=1 adalah perubahan proyeksi F sedemikian sehingga Pj (f ) tidak tergantung pada xj . Anggap Pj hanya mewakili variabel ke-j, xj , untuk menghasilkan suatu hasil yang tidak tergantung pada xj ; dan jika Pj suatu fungsi yang tidak tergantung pada xj , fungsi tetap tidak berubah. Untuk u ⊆ [1 . . . d], didefinisikan Pu (f ) =

Π Pj

(f )

(3.2)

j∈u

sebagai sebuah hasil komutatif dari operator-opeator linier pada f , yaitu: 8 Marlan : Dekomposisi Fungsi Mutivariat, 2009

9

P∅ (f ) = f dan Pu∪(j) (f ) = Pu (Pj (f ))

(3.3)

Khususnya, operator-operator linier dalam Pu dapat diterapkan pada f dalam setiap orde, dan Pu (Py (f )) := Pu∪v (f ) untuk semua u, v ⊆ [1 . . . d]

(3.4)

Secara formal, untuk setiap u ⊆ [1..d] didefinisikan: Fu := P[l..d]\u (F = P[1..d]\u (f ) : f ∈ F

(3.5)

Maka, Fu terdiri dari fungsi-fungsi yang hanya tergantung pada variabel yang ada dalam u, yaitu pada xu = (xj )j∈u , yang konstan atas variabel di luar u. Untuk gu ∈ Fu , kadang-kadang ada gunanya mengabaikan variabel yang tidak penting, dengan menulis gu (x) = gu (xu )

(3.6)

Diperoleh F[1..d] = F , F hanya memuat fungsi-fungsi konstanta. Selanjutnya Fv ⊆ Fu , jika v ⊆ u

(3.7)

Operator linier (Pj )dj=1 bisa sangat umum sepanjang masing-masing Pj memenuhi ketiga sifat (3.1). Berikut diperlihatkan dua contoh: a. Menetapkan xj pada cj : Pj (f )(x) = f (x1, . . . , xj−1 , cj , xj+1 , . . . , xd ) untuk x ∈ D

(3.8)

b. Mengintegralkan atas xj : Pj (f )(x) =

Z1 0


f(x1, . . . , xj−1 , t, xj+1 . . . , xd )dt untuk x ∈ D

(3.9)

10 Dengan tergantung pada pemilihan operator Pj , ada beberapa asumsi implisit atas domain D dan ruang linier F . Pada contoh pertama perlu mengasumsikan bahwa untuk semua j ∈ [1..d] dan semua x ∈ D diperoleh f (x1 , . . . , xj−1 , cj+1 , . . . , xd ) ∈ D. Pada contoh kedua diharuskan bahwa [0, 1]d termuat di dalam D, dan f dapat diintegralkan pada [0, 1]d . Pilihan Pj yang jelas lainnya meliputi, misalnya, penjumlahan berbobot Pj (f )(x) =

Mj X

wj,m f (x1, . . . , xj−1 , cj,m , xj+1 . . . , xd)

(3.10)

m=1

dengan

Mj P

wj,m = 1, atau integral berbobot

m=1

Pj (f )(x) =

Z1

f (x1 , . . . , xj−1 , t, xj+1 , . . . , xd )ρ(t)dt

(3.11)

0

dengan

Rb

ρ(t)dt = 1. Tidak ada persyaratan bahwa operator linier d harus mem-

a

punyai bentuk yang sama, yaitu dapat digabungkan dan dibandingkan. Didapat suatu rumus umum dekomposisi untuk f atas pilihan tertentu operator linier (Pj )dj=1 . Teorema 3.1 Misalkan (Pj )dj=1 adalah operator linier dari F ke F dengan sifatsifat yang diharuskan pada (3.1). (a) Setiap fungsi f ∈ F mempunyai representasi unik berbentuk f=

X

fu

(3.12)

u⊆[1..d]

dengan fu hanya tergantung pada variabel dalam u, dan memenuhi untuk semua u tak kosong, Pj (fu ) = 0 untuk semua j ∈ u


(3.13)

11 (b) Fungsi fu memenuhi keadaan f0 = P[1..d] (f ), fu = P[1..d]\u(f ) −

X

fu

(3.14)

v⊆u

(c) Fungsi fu diberikan secara eksplisit oleh fu =

X

(−1)|u|−|v| P[1..d]\u (f )

(3.15)

v⊆u

Bukti. Pertama dibuktikan adanya suatu representasi berbentuk (3.12) yang memenuhi (3.13). Oleh satu argumen induksi sederhana dengan meningkatkan |u|, sifat (3.14) menghasilkan fungsi fu yang hanya tergantung pada variabel di dalam u. Dengan mempatkan u = [1..d] dalam (3.14), dan P∅ (f ) = f , didapat: F[1..d] = f −

X

fv

(3.16)

v⊆[1..d]

Sehingga suatu dekomposisi dari bentuk (3.12) didapat. Untuk menunjukkan bahwa dekomposisi yang dibangun sedemikian rupa sehingga memenuhi (3.13), dilakukan induksi terhadap |u|. Untuk |u| = 1, diperoleh fu = P[1..d]\u (f ) − f∅ dengan f∅ = P[ 1..d](f). Maka untuk f ∈ u (dan karenanya u = {j}) diperoleh dari (3.14) Pj (fu ) = Pj (P[1..d]\u(f )) − Pj (f∅ ) = P[1..d] (f ) − f∅ = 0 Sekarang andaikan syarat (3.13) berlaku untuk semua himpunan bagian dengan kardinalitas |u| − 1. Maka untuk j ∈ u diperoleh Pj (fu ) = Pj (P[1..d]\u(f )) −

X

Pj fv

v⊆u

= P[1..d]\(u\{j})(f ) −

X v:j∈v⊆u


Pj fv −

X v:j6∈v⊆u

(3.17) Pj fv

12 di mana pada langkah terakhir penjumlahan atas himpunan v dipecah menjadi dua, yang pertama atas himpunan v yang mengandung j, dan yang kedua atas himpunan v yang tidak mengandung j. Karena v adalah himpunan bagian dari u, dengan hipotesa induksi diperoleh Pj (fv ) = 0 untuk j ∈ v, sementara Pj (fv ) = fv jika j 6∈ v, dengan demikian diperoleh: X

Pj (fu ) = P[1..d]\(u\{j})(f ) −

fv

v⊆u\(j)

X

= P[1..d]\(u\{j})(f ) −

(3.18) fv − fu\{j} = 0

v⊆u\{j}

di mana pada langkah terakhir digunakan (3.14) dengan u diganti dengan u\{j}. Diperlihatkan bahwa representasi (3.12) yang memenuhi (3.13) adalah unik. Untuk setiap u ⊆ [1..d], aplikasikan P[1..d]\u pada f dalam (3.12) (setelah dinotasikan u dengan v dalam (3.12)) untuk memperoleh P[1..d]\u (f ) =

X

P[1..d]\u(fv ) =

v⊆u

X

fv = fu +

v⊆u

X

fv

(3.19)

v⊆u

menghasilkan (3.14), yang mendefinisikan fu secara unik. Dengan demikian, eksistensi dan keunikan keduanya sudah terbukti. Untuk membuktikan bagian (c), pada persamaan (3.15), dilakukan induksi |u|, sehingga persamaan (3.15) berlaku untuk f∅ = P[1..d] (f ). Misalkan himpunan bagian u dengan |u| ≥ 1. Dengan hipotesa induksi diasumsikan bahwa (3.15) berlaku untuk semua himpunan bagian dengan kardinalitas paling banyak |u| − 1, maka (setelah mengganti v dengan w dan u dengan v dalam (3.15)) P

fv =

v⊆u

=

P P

(−1)|v|−|w| P[1..d]\w (f )

v⊆u w⊆v P |u|−1 P

P

w⊆u j=|w| w⊆v⊆u|v|=j


(−1)j−|w| P[1..d]\w (f )

13

=

=





 |u| |w|  (−1)j−|w|   P[1..d]\w (f ) w⊆u j=|w| j |w| P

|u|−1 P

P

|u|−1−|w|

X

w⊆u

`=|w|

|





P  |u| − |w|  (−1)`  (−1)|u|−|w| P[1..d]\w (f ) P[1..d]\w (f ) = − w⊆v ` {z } =−(−1)|u|−|w|

dimana digunakan identitas binomial:   L X  L  L (−1)`   = (1 − 1) = 0 untuk semua L ≥ 1 ` `=0

(3.20)

Dengan demikian, dari persamaan (3.14) diperoleh fu = P[1..d]\u(f ) −

X

fv

v⊆u

X X = P[1..d]\u(f ) + (−1)|u|−|v| P[1..d]\v (f ) = (−1)|u|−|v| P[1..d]\v (f ) v⊆u

(3.21)

v⊆u

3.2 Ortogonalitas Pada bagian sebelumnya telah tunjukkan bahwa rumus dekomposisi dari Teorema 3.1 bergantung pada dua gagasan dimensi dari f. Bahkan akan lebih memenuhi jika dekomposisi ortogonal dengan beberapa cara terhadap satu dengan lainnya. Dalam bagian ini identifikasi ketentuan dan syarat-syarat ruang fungsi untuk dekomposisi, merupakan dekomposisi ortogonal. Untuk teori kernel reproduksi, dapat merujuk kepada (Aronszajn, 1950), dan khususnya, pada bagian ”penjumlahan kernel-kernel reproduksi”. Bahwa kernel reproduksi K : D × D → R bersesuaian dengan ruang Hilbert H(K) yang


14 memenuhi K(x, ·) ∈ H(K) untuk semua x ∈ D dan K(x, y) = K(y, x) untuk semua x, y ∈ D, dan mempunyai sifat reproduksi

hf, K(x, ·)iH(K) = f (x) untuk semua f ∈ H(K) dan x ∈ D

di mana h·, · H(K) menotasikan inner product dalam H(K). Selain itu, H(K) adalah kelengkapan span {K(·, y) : y ∈ D}; karena itu, ruang semua kombinasi linier berhingga dari fungsi K(·, y) dalam H(K). Dengan (Wasilkowski, 2004), dikaji kernel reproduksi ruang Hilbert umum H(Kd ) dari fungsi riil pada D ⊆ Rd dengan kernel reproduksi berbentuk X

Kd (x, y) =

Kd,u (xu , yu ), Kd,∅ = 1

(3.22)

u⊆[1..d]

Untuk setiap u ⊆ [1..d], Kd,u adalah kernel reproduksi untuk ruang Hilbert H(Kd,u ) dari fungsi riil yang didefinisikan atas Du := {xu : x ∈ D}. Fungsi di dalam H(Kd,u ) hanya tergantung pada variabel dalam u. Khusus, ruang H(Kd,∅ ) = span {1} hanya memuat fungsi konstanta. Fungsi H(Kd ) adalah penjumlahan fungsi dari H(Kd,u ), f =

X

fu untuk fu ∈ H(Kd,u )

(3.23)

u⊆[1..d]

Representasi (3.23) umumnya tidak unik, karena sebagian fungsi taknol bisa termasuk ke dalam H(Kd,u ), untuk himpunan bagian u yang berbeda-beda. Jika k · kH(Kd ) menotasikan norm dalam H(Kd ) dan k · kH(Kd,u ) menotasikan norm dalam H(Kd,u ) untuk setiap u ⊆ [1..d], maka didapat    X  X 2 2 kfkH(Kd ) = inf kfu kH(Kd,u ) : fu ∈ H(Kd,u ) 3 f = fu   u⊆[1..d]


u⊆[1..d]

(3.24)

15 Representasi (3.23) unik, jika dan hanya jika H(Kd,u ∩ H(Kd,v ) = {0} untuk semua himpunan bagian u 6= v

(3.25)

Bila ini berlaku, ruang H(Kd ) adalah penjumlahan langsung dan ortogonal dari P P ruang H(Kd,u ), yaitu, untuk f = fu dan g = gu dengan u⊆[1..d]

u⊆[1..d]

fu , gu ∈ H(Kd,u ) maka diperoleh hf, giH(Kd ) =

X

hfu , gu iH(Kd,u

u⊆[1..d]

dan dengan norm yang memenuhi kfk2H(Kd ) =

X

kfu k2H(Kd,u

(3.26)

u⊆[1..d]

Bahwa kernel reproduksi ruang Hilbert yang dibentuk dengan cara di atas mempunyai kaitan dengan himpunan proyeksi (Pj )dj=1 yang memenuhi (3.1), dalam arti bahwa untuk semua u ⊆ [1..d] dan semua yu ∈ Du diperoleh Pj (Kd,u (·, yu )) = 0 untuk semua j ∈ u. Teorema berikut menyatakan bahwa dekomposisi (3.23) unik dan ortogonal, dan lebih tepatnya, bahwa hal itu bersesuaian dengan dekomposisi dalam Teorema 3.1. Teorema 3.2 Misalkan H(Kd ) adalah kernel reproduksi ruang Hilbert dari fungsi riil yang didefinisikan atas D ⊆ Rd yang dibentuk dari kernel reprodukis ruang Hilberti H(Kd,u ) untuk u ⊆ [1..d] seperti dalam (3.22) dan (3.24). Misalkan (Pj )dj=1 operator linier kontinu dari H(Kd ) untuk H(Kd ) dengan sifat-sifat (3.1), sehingga untuk semua u ⊆ [1..d] yang tak kosong dan semua yu ∈ Du diperoleh Pj (Kd,u (·, yu )) = 0 untuk semua j ∈ u


(3.27)

16 Maka representasi (3.23) unik dan merupakan dekomposisi ortogonal yang bersesuaian dengan dekomposisi dari Teorema 1. Bukti. Ambil representasi (3.23) dari f =

P

fu , dengan fu ∈ H(Kd,u ). Cukup

u⊆[1..d]

ditunjukkan bahwa untuk semua u ⊆ [1..d] yang tak kosong diperoleh Pj (fu ) = 0 untuk semua j ∈ u. Jika ini berlaku maka Teorema 3.1 mengimplikasikan keunikan dekomposisi, dimana (3.23) harus bersesuaian dengan (3.12). Span{Kd,u (·, yu ) : yu ∈ Du } padat dalam H(Kd,u ), untuk ε > 0 sebarang terdapat N(ε) > 0, y1 , . . . , yN (ε ∈ Du dan α1 , . . . , αN (ε) ∈ R sedemikian hingga N (g)

khu kH(K×d,u) < ε, dengan hu := fu −

X

αi Kd,u (·, yi)

(3.28)

i=1

Untuk operator (Pj )dj=1 . Karena Pj kontinu atas H(Kd ), Pj kontinu atas H(Kd,u ). Dari (3.27) dan (3.28) diperoleh, untuk j ∈ u, kPj (fu )kH(Kd,u ) = kPj (hu )kH(Kd,u ) ≤ kPj kk(hu )kH(Kd,u ) ≤ kPj kε Karena ε sebarang, maka diperoleh Pi (fu ) = 0. Kemudian Teorema 3.1 menyatakan bahwa representasi (3.23) bersesuaian dengan rumus eksplisit (3.15), dan karena keunikan, maka (3.25) memberikan ortogonalitas subruang H(Kd,u ) dalam H(Kd ).


BAB 4 PEMBAHASAN

4.1 Dekomposisi ANOVA Pada bagian ini akan dijelaskan sebuah fungsi f dengan d variabel. Sejumlah variabel d dikenal sebagai dimensi dari permasalahan integrasi. Perhitungan bentuk integral dimensi yang paling tinggi ditunjukkan dengan sampel integran pada sejumlah titik dalam domain integrasi. Walaupun fungsi f bergantung pada variabel d, f disebut orde q dengan q ≤ d, jikalau f dapat dijelaskan sebagai jumlah tiap-tiap bagian (partisi) yang bergantung kepada q dan q adalah bilangan yang paling kecil. Dengan demikian kecilnya orde q mengakibatkan fungsi lebih mudah dihubungkan. Kemudian fungsi polinomial dengan derajat aljabar yang rendah memiliki orde yang kecil tanpa memperhatikan variabel d. Ambil D = [0, 1]d dan F sebagai ruang dua dari fungsi yang diintegralkan, dan dengan memilih Pj menurut (3.9), diperoleh dekomposisi ANOVA (analisa variansi). Ini mempunyai bentuk 4.1 f=

X

fu,∗

(4.1)

u⊆[1,d]

dengan fu,∗ hanya tergantung pada variabel di dalam u dan memenuhi Z1

fu,∗ (xu )dxj = 0 untuk semua j ∈ u

(4.2)

0

Sehingga fφ,∗ =

Z

f(x)dx, fu,∗ (xu ) =

[0,1]d

Z [0,1]d−|u|

f (x)dx[1..d]\u −

X

fv,∗ (xv )

(4.3)

v⊆u


18 dimana dx[1..d]\u menotasikan

Q

j∈[1..d]\u dxj .

Walupun bentuk rekursif dari suku-

suku ANOVA sering muncul dalam literatur, namun bentuk eksplisit yang diperoleh di sini, baru: diperoleh fu,∗ (xu ) =

X

(−1)

Z

|u|−|v|

v⊆u

f (x)dx[1..d]\

(4.4)

[0,1]d−|u|

Dekomposisi ANOVA mungkin sulit digunakan di dalam praktek karena mengharuskan integral dari f yang biasanya tidak tersedia. Sekalipun demikian, itu memberikan dekomposisi variansi natural dari f . Telah diketahui, bahwa ANOVA ortogonal dalam L2 ([0, 1]d ), yaitu Z

fu,∗ (xu )fv,∗ (xv )dx = 0 untuk semua u 6= v

(4.5)

[0,1]d

Karena f dapat diintegralkan (demikian juga halnya dengan semua suku ANOVA), maka diperoleh dekomposisi variansi X

σ 2(f ) =

σ 2(fu,∗ )

u⊆[1..d]

dimana σ 2(f ) =

R

f 2 (x)dx −

[1,1]d

R

f (x)dx

!2

, σ 2(fθ,∗ ) = 0 dan untuk u 6= θ

[1,1]d

diperoleh 2

σ (fu,∗ ) =

Z

2 fu,∗ (xu )dxu

[1,1]|u|

4.2 Dekomposisi Anchored Misalkan c ∈ D, dan misalkan (x : c)u menyatakan d vektor dimensi yang komponen ke j adalah xj jika j ∈ u dan cj jika j 6∈ u. Anggap (x : c) ∈ D bilamana x ∈ D, dan dengan memilih Pj menurut (3.8), diperoleh dekomposisi


19 anchored tergantung ke c. Ini mempunyai bentuk f=

X

fu,c

(4.6)

u⊆[1..d]

dengan fu,c hanya tergantung pada variabel-variabel dalam u dan memenuhi fu,c (xu ) = 0 bilamana xj = cj untuk semua j ∈ u. Sehingga: f∅,c = f, fu,c (xu ) = f (x : c)u ) −

X

fv,c (xv )

(4.7)

v⊆u

Bentuk eksplisit diperoleh fu,c (xu ) =

X

(−1)|u|−|v| f ((x : c)v )

(4.8)

v⊆u

Ini menarik karena hanya melibatkan evaluasi fungsi f yang tergantung pada c. Ditambahkan bahwa, secara khusus, bentuk fu,c dari dekomposisi anchored juga bisa dinyatakan sebagai gabungan integral dari derivatif parsial pertama f. Sebagai ilustrasi sederhana, untuk d = 2 dan f (x1 , x2) = 1 + x1 + x2 + x1 x2. Diperoleh dekomposisi berikut: Anchored pada c = (0, 0) Anchored pada c = (1, 1) ANOVA

f∅ 1 4 9 4

f{1}(x1) x1 2x1 − 2 3x1 3 − 2 4

f{2}(x2) x2 2x2 − 2 x 1 x2 1 − + x1 x2 − 2 2 4

f{1,2}(x1, x2) x1 x2 x1 x2 − x1 − x2 + 1

(Untuk fungsi ini, dekomposisi ANOVA terjadi sama seperti dekomposisi anchored dengan c = ( 12 , 12 )). Jelas pilihan dari anchored memegang peranan penting. Catatan 4. Michael Griebel menyatakan hubungan khusus peneliti dari bidang perhitungan kimia yang telah diselesaikannya apa yang disebut representasi model dimensi-tinggi (HDMR), yang terkait erat dengan penelitian ini. Secara khusus, cut-HDMR sama dengan dekomposisi anchored


20 Catatan 5. Teorema 3.1 dan pembuktiannya tidak dapat menunjukkan asal dari mana rumus eksplisit (3.15). Dengan pengetahuan tentang rumus eksplisit, Michael Griebel, menemukan turunan sederhana berikutnya. Misalkan I adalah Q operator identitas. Dengan menggunakan identitas sederhana f ∈u(aj + bj ) = Q Q P sebanyak dua kali, dapat ditulis a b v⊆u j∈v j j∈\v j

j=1

u⊆[1..d]



! Y Y (i − Pj ) 

d X Y I= ((I − Pj ) + pj ) =

j∈u

j∈[1..d]\w

Pj 

  ! Y X Y X Y  I  (−Pj )  = 

u⊆[1..d]

v⊆u

X X

=

u⊆[1..d] v⊆u

j∈v



(−1)|v|−|w| 

j∈u\v

Y

j∈[1..d]\v



Pj 

j∈[1..d]\u



Pj  (4.9)

Dengan demikian f=

X X

(−1)|v|−|w| P[1..d]\v (f )

(4.10)

u⊆[1..d] v⊆u

merupakan rumus eksplisit yang diinginkan. (Ternyata, turunan dalam [3.13] berlaku sepanjang (3.28), lihat juga [(3.16), ekspresi dari (3.15) dan (3.16)]). Turunan ini, digunakan untuk membuktikan Teorema 3.1, untuk mengetahui apakah hasil dekomposisi f sama dengan yang diberikan (3.14), atau merupakan dekomposisi unik yang memenuhi (3.13).


21 4.3 Dekomposisi Minimal Dalam bagian ini dibuktikan bahwa setiap dekomposisi dari Teorema 3.1, untuk pilihan operator linier (Pj )dj=1 , adalah minimal artinya tidak memasukkan suku yang tidak perlu. Dimulai dengan mendefinisikan dua gagasan dimensi.

1. Dikatakan bahwa suatu fungsi dari d variabel mempunyai dimensi patokan k jika dan hanya jika fungsi tersebut hanya tergantung pada variabel k, dan k adalah bilangan terkecil. 2. Dikatakan bahwa suatu fungsi dari d variabel berorde q jika dan hanya jika fungsi tersebut dapat ditulis sebagai perjumlahan fungsi, di mana masingmasing fungsi tersebut tergantung pada paling banyak q dari d variabel, dan q adalah bilangan terkecil.

Kedua gagasan ini masing-masing bersesuaian dengan konsep truncution dimention dan superposition dimention. Pada umumnya terdapat tak berhingga banyaknya cara untuk menyatakan fungsi f dari variabel d, x = (x1, x2, · · · , xd ) dalam bentuk f=

X

gu

(4.11)

u⊆[1..d]

dengan gu hanya tergantung pada variabel dalam u, yaitu pada xu = (xj )j∈u . Yang P jelas dimensi patokan f adalah k, terkecil di mana dekomposisi f = u⊆[1..k] gu ada. Serupa halnya, orde dari f adalah q, terkecil untuk mana dekomposisi P gu berlaku. Bahwa dimensi patokan dan orde suatu fungsi tertentu, u⊆[1..k],|u|≤q

keduanya didefinisikan secara unik, dan bahwa definisi tidak terkait dengan suatu metode dekomposisi tertentu.


22 Berkenaan dengan dekomposisi tertentu (4.1), sudah umum menyebut sukusuku {gu : |u| = `} secara kolektif sebagai ”suku orde-`”. Serupa halnya, dalam ulasan di bawah ini disebut suku {gu : v ⊆ u ⊆ [1..d]} untuk v ⊆ [1..d] tertentu sebagai ”suku super-v”. Dengan kata lain, suku super-v adalah semua suku gu di mana u merupakan superset dari v. Sifat minimal dari dekomposisi dari Teorema 3.1 didasarkan pada teorema berikut. Teorema 4.1 Misalkan f adalah fungsi dari d variabel dan misalkan v adalah suatu himpunan bagian tertentu dari [1..d]. Asumsikan bahwa terdapat suatu dekomposisi (4.1) dari f di mana semua suku super-v sama dengan nol, yaitu gu = 0 untuk semua u yang memuat v, maka dekomposisi dari Teorema 3.1 juga mempunyai semua suku super-v sama dengan nol, yaitu fu = 0 untuk semua u yang memuat v Dari Teorema 4.1, jika untuk himpunan yang berbeda v, terdapat dekomposisi dari f yang berbeda dimana semua suku super-v sama dengan nol, maka dekomposisi dari Teorema 3.1 mampunyai semua suku super-v sama dengan nol, untuk semua himpunan v yang berbeda ini, yaitu terdapat banyak suku nol. Dengan kata lain, dekomposisi dari Teorema 3.1 menggunakan suku berorde lebih rendah. Selanjutnya, ini berlaku untuk semua pilihan operator linier (Pj )dj=1 yang mungkin yang memenuhi (3.1). Tentu saja, jika dekomposisi atas satu pilihan operator Pj mempunyai semua suku super-v sama dengan nol, maka dekomposisi atas semua pilihan operator Pj mempunyai semua suku super-v sama dengan nol.


23 Khusus, Teorema 4.1 mengimplikasikan bahwa dekomposisi dari Teorema 3.1, minimal atas dimensi patokan maupun orde:

1. Suatu fungsi f dari d variabel mempunyai dimensi patokan k < d jika dan hanya jika k adalah bilangan terkecil sedemikian sehingga fu = 0 untuk semua himpunan bagian u ⊆ [1..d] dimana u 6⊆ [1..k]. 2. Suatu fungsi f dari d variabel berorde q < d jika dan hanya jika q adalah bilangan terkecil sedemikian sehingga fu = 0 untuk semua himpunan bagian u ⊆ [1..d] dengan |u| > q.

Di sini fu diberikan oleh (3.15) dari Teorema 3.1. Kedua fakta terakhir dapat disimpulkan, dengan catatan bahwa:

1. f yang mempunyai dimensi patokan k mengimplikasikan eksistensi suatu dekomposisi dimana semua suku super-{j} sama dengan nol, jika semua j ∈ {k + 1, k + 2, . . . , d} dan 2. f yang berorde q mengimplikasikan eksistensi suatu dekomposisi dimana semua suku super-v sama dengan nol, untuk semua v dengan |v| > q.

Untuk membuktikan Teorema 4.1, dibutuhkan lemma berikut. Lemma 4.1 Misalkan f adalah fungsi dari variabel d dan misalkan u adalah himpunan bagian tertentu dari [1..d]. Selanjutnya, misalkan (Pj )dj=1 menyatakan operator linier yang memenuhi (3.1). Jika terdapat suatu dekomposisi dari f berbentuk f=

X w⊆u


gw

(4.12)

24 dengan w = u tidak tercakup dalam perjumlahan, dan dengan gw hanya tergantung pada variabel-variabel yang terdaftar di dalam w, maka f=

X

(−1)|u|−1−|v| Pu\v (f )

(4.13)

v⊆u

Bukti. Dibuktikan lemma ini dengan menunjukkan bahwa ruas kanan dari (4.13) disederhanakan menjadi ruas kiri f, tanpa mengandalkan bentuk spesifik dari fungsi gw dalam (4.12). Dengan mengunakan (12), dapat ditulis Pu\v (f ) =

X

Pu\v (gw )

w⊆u

dan diperoleh Pu\v (gw ) = Pu\(v∩w) (gw ) karena gw hanya tergantung pada variabel dalam w. Dengan demikian

RHS dari (4.13) = =

P

v ⊆ u(−1)|u|−1−|v|

P P P P w⊆u z⊆w

Pu\(v∩w) (gw )

w⊆u

P

Pu\z (gw )

w⊆u z⊆w

=

P

(−1)|u|−1−|v|

v⊆u,v∩w−g |u|−1

Pu\z (gw )

X

X

(−1)|u|−1−j

j=0

|

{z

v⊆u |v|=j,v∩w=z

=:κw,z

1 }

Kemudian jumlah himpunan v 6⊆ u yang memenuhi |v| = j dan v ∩ w = z dihitung, v harus memuat semua indeks dalam z, tambah j − |z| indeks yang akan dipilih dari |u| − |w| indeks  dalam u  |u| − |w| total dari himpunan v adalah  j = |z| untuk lainnya.


tetapi di luar w. Karena itu, jumlah    jika |u| − |w| ≥ j − |z| ≥ 0, dan 0

25 Hal ini menghasilkan 



 |u| − |w|  (−1)|u|−1−j   j=|z| j = |z|   min(|u|−1−|z|,|u|−|w|) P  |u| − |w|  = (−1)|u|−1−|z|−`   `=0 `

Kw,z =

min(|u|−1,|u|−|w|+|z|) P

Jika z = w maka 



 |u| − |w|  (−1)|u|−1−|w|−`   `=0 `   |u|−|w| X  |u| − |w|  =− (−1)|u|−|w|−`   −(−1) = 1 ` `=0 {z } |

Kw,w =

|u|−1−|w| P

=0

Jika z 6⊆ w maka

Kw,z

|u|−|w| P `=0





 |u| − |w|  (−1)|u|−1−|z|−`   ` |u|−|w|

= (−1)|w|−|z|−1 −

X `=0

|





 |u| − |w|  (−1)|u|−|w|−`   ` {z } =0

Pada kedua kasus di atas digunakan identitas binomial (3.16), sehingga

RHS dari (4.13) =

P

Pu\w (gw ) =

w⊆u

P

gw = LHS dari (4.13).

w⊆u

dengan gw hanya tergantung pada variabel dalam w. Karena itu P[1..d]\u(f ) =

X w⊆[1..d];w6=u


P[1..d]\u (gw )

26 Karena suku-suku dalam perjumlahan terakhir hanya tergantung pada variabel yang ada dalam u maupun w, dapat disusun kembali perjumlahan terakhir sebagai P[1..d]\u (f ) =

X

g¯w

w⊆u

dimana g¯w hanya tergantung pada variabel dalam w. Sekarang diaplikasikan Lemma 4.1 pada P[1..d]\u (f ) untuk memperoleh P[1..d]\u (f ) =

X

(−1)|u|−1−|z| Pu\z (P[1..d]\z (f )) =

z⊆u

X

(−1)|u|−1−|z| P[1..d]\z (f )

z⊆u

Maka rumus eksplisit (3.15) menghasilkan fu =

X

(−1)|u|−1−|z| P[1..d]\z (f ) = P[1..d]\u(f ) −

z⊆u

X (−1)|u|−1−|z| P[1..d]\z (f ) = 0 z⊆u

Telah dibuktikan bahwa kekuatan rumus dekomposisi: rumus dekomposisi tidak memasukkan suku taknol yang tidak perlu, jika salah mengasumsikan fungsi k-dimensi merupakan `-dimensi dimana ` > k. Terakhir, diperoleh rumus untuk perjumlahan atas semua suku dalam (3.12) dengan |u| ≤ q, yaitu untuk Fq :=

X

fu , 0 ≤ q ≤ d

u⊆[1..d];|u|≤q

Lemma 4.2 Andaikan bahwa f adalah suatu fungsi dari variabel d. Maka Fd = f, dan untuk setiap q < d diperoleh   q X X  d−1−j  (−1)q−j  P[1..d]\u (f ) Fq =  j=0 q−j u⊆[1..d];|u|=j Bukti. Dari rumus eksplisit untuk fu bahwa untuk 0 ≤ i ≤ d diperoleh


27 P

fu =

P P

(−1)i−|v| P[1..d]\v (f )

u⊆[1..d] v⊆u |u|=i

u⊆[1..d];|u|≤i

=

P

P

(−1)i−|v| P[1..d]\v (f )

v⊆[1..d] v⊆u⊆[1..d] |v|≤i |u|=i

=





 d − |v|  (−1)i−|v|   P[1..d]\v (f ) v⊆[1..d] i − |v| P

|v|≤i

dan ini menghasilkan

Fq =

P u⊆[1..d];|u|≤q

fu =

q P P i=0 u⊆[1..d] |u|=i





 d − |v|  (−1)i−|v|   P[1..d]\v (f ) i=0 v⊆[1..d] i − |v| |v|≤i   q P P  d − |v|  = (−1)i−|v|   P[1..d]\v (f ) v⊆[1..d] i=|v| i − |v|

fu =

q P P

|v|≤i







 



 n   n−1   n−1  Dengan menggunakan sifat   =  +  , dapat diperlihatk k k−1 kan melalui induksi atas q bahwa untuk q < d, maka     q X d − 1 − |v|   d − |v|  q−|v|  (−1)i−|v|   = (−1)   i − |v| q − |v| i=|v| Kuantitas Fq mempunyai hubungan erat dengan orde dari f . Orde dari f bisa didefinisikan sebagai nilai terkecil dari q ≤ d untuk mana Fq = f .


BAB 5 KESIMPULAN DAN SARAN

5.1 Kesimpulan Dari hasil pembahasan dapat disimpulkan bahwa, dekomposisi anchored dalam praktek lebih mudah digunakan karena hanya mengharuskan evaluasi fungsi f atas anchor c yang dipilih. Dalam tesis ini diperoleh suatu metode dekomposisi fungsi multivariate, dengan memisalkan x ∈ D diberikan dan tetap. Dari 4.2 (Dekomposisi anchored) diketahui, bahwa: fu,c (xu ) =

X

(−1)|u|−|v| f ((x; c)v )

v⊆u

Dari rumus eksplisit ini tampak jelas bahwa untuk setiap u, fu,c (xu ) dapat dihitung dengan menggunakan 2|u| 1 perjumlahan dan pengurangan dan 2|u| sampel dari f .

5.2 Saran Perlu dilakukan penelitai lebih lanjut, sehingga didapatkan metode yang lebih sederhana.


DAFTAR PUSTAKA

Alagar, V.S.and Thanh, M. Fast polynomial decomposition algoritm. In Proc. EUROCAL85, pages 150-153. Springer-Verlag Lect. Notes in Comput. Sci.2004, 1985. Alonso, C. Gutierrez, J. and Recio, T. A rational function decomposition algorithm by nearseparated polynomials. J. Symbolic Computation,19:527-544, 1995. Aronszajn, N. Theory of reproducing kernels, Trans. AMS, 68, 337-404, 1950 Barton, D. R. and Zippel, R. E. Polynomial decomposition algoritm. J. Symb. Comp., 1:159-168, 1985. Binder, F. Fast computations in the lattice of polynomial rational function fields. I Proc. ISSAC96.ACM Press, 1995. Borwen, J, M and Lewis, A. S. Decomposition of Multivariate Function, Can. J. Math. Vol. 44, pp 463-482, 1992. Boyle, P. Options: a Monte Carlo approach, Journal of Financial Economics, 4:323 - 338, 1977. Casperson, D. Ford, D. and MacKay, J. An ideal decomposition algorithm. J. Symbolic Computation, 21(2):133-137, 1996. Dickerson, M. Polynomial decomposition algorithm for multivariate polynomials. Technical Report TR87-826, Comput. Sci., Cornell Univ., April 1987. Dorey, F. and Whaples, G. Prime and composite polynomials. J. Algebra, 28:88101, 1974. Fried, M. D. and MacRae, R.E. On curves with separated variables. Math. Ann., 180:202-226, 1969. Gathen, von zur. J. Functional decomposition of polynomials: the tame case. J. Symb. Comput., 10: 281-299, 1990. Gathen, von zur. J. Functional decomposition of polynomials: the wild case. J. Symb. Comput., 10: 281-299, 1990. Gathen, von zur. J. and Weiss, J. Homogeneous bivariate decomposition. J.Symbolic Compututation, 26: 31-70, 1998. Griebel, M. Sporse grids and related approximation schemes for higher dimensional problems, Fondation of Computational Mathematics, Santander 2005 (Pardo, L. M. Pinkus, A. Sli, M. Todd, M.J. eds), Cambridge University Press, London, pp. 106-161, 2006. Gutierrez, J. Rosario, R. and David, S, On Multivariate Rasional Function Decomposition, J. Symbolic Computation 33, 545-562, 2002. 29 Marlan : Dekomposisi Fungsi Mutivariat, 2009

30 Gutierrez, J. and Recio, T. Advance on the simplification of sine-cosine equation. J. Symbolic Computation, 26:31-70, 1998. Gutierrez, J. A polynomial decomposition algorithm over factorial domain, Computes Rendus Mathematiques de lAcademie des Sciences, 13(2-3):81-86, AprilJune 1991. Gutierrez, J. and Recio, T. and Ruiz de Velasco, C. A polynomial decomposition algorithma of almost quadratic complexity. In proc. AABCC-6/88, volume 357 of Lect. Notes in Comput. Sci., pages 471-476. Springer-Verlag, 1998. Hommel, G. and Kovacs, P. Simplication of symbolic invers kinematic transformation through functional decomposition. In Proc. Of the Conference Adv. In Robotics, pages 88-95, 1992. Kozen, D. and Landau, S. Polynomial decomposition of algebraic function. Journal of Symbolic Computation, 22(3):235-246, September 1996. Paskov, S. and Traub, J. Faster valuation of financial derivatives, Journal of Portofolio Management, 22:113-120, 1995. Ritt, J. F. Prime ang composite polynomials. Trans. Amer. Math. Soc.,23:51-66, 1992. Schinzel, A. Selected Topic on polynomials. University of Michigan Press, 1982. Wasilkowski, G. W. and Wazniakowski, H. Finite-order weights imply tractability of linear multivariate problems, J. Approx. Theory 130, 57-77, 2004. Watt, S. M, On the Functional Decomposition of Multivariate Laurent Polynomial, Ontario Research Centre for Computer Algebra University of Western Ontario, London Ontario, Canada, 2004. Zippel, R. E. Rational function decomposition, In Stephen Watt, editor, International Symposium on Symbolic and Algebraic Computation, pages16, New York, July 1991. ACM.


DEKOMPOSISI FUNGSI MULTIVARIAT

Recommend Documents