TEORI PERRON-FROBENIUS UNTUK MATRIKS STOKASTIK
Diajukan sebagai syarat mengikuti sidang Sarjana Matematika Program Studi Matematika Institut Teknologi Bandung
disusun oleh:
Madona Yunita Wijaya 10103035
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
INSTITUT TEKNOLOGI BANDUNG 2007
TEORI PERRON-FROBENIUS UNTUK MATRIKS STOKASTIK Diajukan sebagai syarat mengikuti sidang Sarjana Matematika Program Studi Matematika Institut Teknologi Bandung
Bandung, Juni 2007 Telah diperiksa dan disetujui oleh Dosen Pembimbing
Dr. Irawati
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
INSTITUT TEKNOLOGI BANDUNG
ABSTRACT Perron-Frobenius Theory is one of the most elegant theory in algebra about the characteristic of nonnegative matrices based on its spectral property. Its application can be obtained for stochastic matrix. Through this theory, we can derive and proof some properties of the limiting distribution of stochastic matrix. Specifically, we will see the limiting distribution of transition matrix of Markov chain. Besides, we can also interpret its meaning of the limiting distribution.
ABSTRAK Teori Perron-Frobenius adalah salah satu teori yang paling terkenal dalam aljabar, yaitu teori mengenai matriks nonnegatif berdasarkan sifat spektralnya. Aplikasi dari teori ini bisa kita lihat pada matriks stokastik, karena matriks stokastik merupakan matriks nonnegatif. Melalui teori ini, kita bisa menurunkan dan membuktikan beberapa sifat dari matriks stokastik untuk mencari distribusi limit Lebih khususnya lagi, kita akan melihat bentuk dari distribusi limit matriks transisi rantai Markov. Selain itu, kita bisa menginterpretasikan arti dari bentuk distribusi limit tersebut.
PRAKATA Puji dan syukur penulis panjatkan kehadirat Allah SWT yang telah memberikan rahmat dan hidayah-Nya sehingga penulis dapat menyelesaikan tugas akhir ini tepat pada waktunya.
Tugas akhir yang berjudul “Teori Perron-Frobenius untuk Matriks Stokastik” ini disusun untuk memenuhi salah satu syarat dalam menyelesaikan pendidikan S1 Program Studi Matematika Institut Teknologi Bandung. Selain itu, pemilihan topik ini sebagai tugas akhir penulis adalah untuk menunjukkan keistimewaan salah satu teori yang ada dalam aljabar, yaitu Teori Perron-Frobenius. Keistimewaan ini ditunjang dengan sifat-sifatnya yang aplikatif dalam statistika, terutama dalam matriks transisi rantai Markov yang dikenal pula dengan matriks stokastik.
Dalam penyusunan tugas akhir ini, penulis memperoleh banyak bantuan serta bimbingan dari berbagai pihak. Oleh karena itu, penulis menyampaikan ucapan terima kasih kepada 1. Bu Ira selaku dosen pemimbing yang telah bersedia memberikan arahan dan bimbingan selama satu tahun terakhir ini. 2. Bu Ria yang telah meluangkan waktunya sebagai dosen penguji, memberikan banyak masukan dalam perbaikan tugas akhir penulis, dan pembelajaran materi statistika yang digunakan dalam tugas akhir ini. 3. Pak Muchlis dan Bu Hanni selaku dosen penguji yang telah memberikan kritik dan saran perbaikan untuk tugas akhir ini. 4. Pak Maman yang telah banyak memberikan petuah dan pembelajaran sehingga penulis bisa lebih termotivasi lagi, salah satunya adalah untuk menyenangi ilmu aljabar.
iv
5. Keluarga penulis, terutama kedua orangtua yang telah memberikan dukungan dan motivasi baik berupa material maupun spiritual untuk keberhasilan penulis dalam menyelesaikan tugas akhir. 6. Erma, Amru, Stefanus, Edi, dan Acung yang telah membantu penulis dalam arahan pembuktian beberapa teorema serta pemahaman beberapa teori dalam tugas akhir ini. 7. Wita, Uma, Anggun, Intan, Eka, Vonny, Rahma, Yo, Lido, Helni, Manes, Heti, Mega, Riswan, Cima, Onta, Opik, Andrew, Adan, Hendrik, serta teman-teman 2003 lainnya yang telah memberikan motivasi secara langsung maupun tidak langsung dan telah menjadi teman seperjuangan dari TPB. 8. Arie dan Dian yang telah memberikan dukungan sehingga penulis dapat menyelesaikan tugas akhir ini.
Penulis menyadari bahwa tulisan dalam tugas akhir ini masih jauh dari sempurna. Oleh karena itu, penulis sangat mengharapkan kritik dan saran dalam penyempurnaan tulisan ini di masa yang akan datang. Semoga tulisan ini dapat bermanfaat bagi teman sejawat maupun para pembaca.
Bandung, Juni 2007
Penulis
v
DAFTAR ISI Lembar Pengesahan ................................................................................................ i Abstract ................................................................................................................... ii Abstrak .................................................................................................................... iii Prakata..................................................................................................................... iv Daftar Isi ................................................................................................................. vi
BAB I : PENDAHULUAN 1.1 Latar Belakang ..................................................................................................1 1.2 Rumusan Masalah ............................................................................................. 2 1.3 Tujuan ...............................................................................................................2 1.4 Manfaat .............................................................................................................3 1.5 Sumber Data dan Teknik Penelitian.................................................................. 3 1.6 Sistematika Penulisan ....................................................................................... 3
BAB II : LANDASAN TEORI 2.1 Subruang Invarian dan Matriks Representasi ................................................... 5 2.2 Proyektor ...........................................................................................................9 2.3 Indeks Matriks...................................................................................................10 2.4 Dekomposisi Core-Nilpotent ............................................................................ 11 2.5 Norm dari Vektor dan Matriks .......................................................................... 13 2.6 Properti dari Nilai Karakteristik........................................................................18 2.7 Matriks Jordan...................................................................................................20 2.8 Limit dari Matriks ............................................................................................. 27 2.9 Cesaro Summable .............................................................................................29
vi
BAB III : TEORI PERRON-FROBENIUS 3.1 Matriks Positif................................................................................................... 36 3.2 Matriks Nonnegatif ........................................................................................... 42
BAB IV : APLIKASI PADA MATRIKS STOKASTIK 4.1 Matriks Stokastik dan Rantai Markov ..............................................................56 4.2 Vektor Distribusi Peluang .................................................................................58 4.3 Distribusi Limit dari Rantai Markov................................................................. 60 4.3.1 Distribusi Limit dari Matriks Stokastik Tak Tereduksi ...........................60 4.3.2 Distribusi Limit dari Matriks Stokastik Tereduksi .................................. 64 4.4 Contoh Kasus dalam Menghitung Distribusi Limit dari Rantai Markov..........70 4.4.1 Kasus 1 : Matriks Stokastik Tak Tereduksi ............................................. 71 4.4.2 Kasus 2 : Matriks Stokastik Tereduksi..................................................... 72
BAB V : KESIMPULAN DAN SARAN 4.1 Kesimpulan ....................................................................................................... 75 4.2 Saran..................................................................................................................76
Daftar Pustaka .........................................................................................................77 Lampiran ................................................................................................................. 78
vii