PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI

METODE KUASA DAN APLIKASINYA PADA MESIN PENCARI INTERNET

Skripsi

Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

Disusun oleh: Lina Meiliana NIM: 043114014

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2011


POWER METHOD AND ITS APPLICATION TO INTERNET SEARCH ENGINES

Thesis

Presented as Partial Fulfillment of the Requirements To Obtain SARJANA SAINS Degree In Mathematics

By: Lina Meiliana Student Number: 043114014

MATHEMATICS STUDY PROGRAM MATHEMATICS DEPARTMENT SCIENCE AND TECHNOLOGY FACULTY SANATA DHARMA UNIVERSITY YOGYAKARTA 2011

ii




Sang Till Friheten (Engkaulah yang Terbaik yang Aku Kenal)

Engkaulah yang terbaik yang aku kenal Engkaulah yang terkasih di dunia ini Engkau seperti bintang, seperti angin, seperti gelombang, seperti burung, seperti bunga di ladang. Engkaulah pembimbing dan sahabatku. Engkaulah kebenaranku, harapanku, kekasihku. Engkaulah darahku, nafasku, mataku, bahuku, tanganku, dan hatiku. Kebebasan adalah namamu yang indah. Persahabatan adalah ibumu yang bangga. Perhatian adalah saudaramu lelaki. Perdamaian adalah saudaramu perempuan. Keberanian adalah ayahmu. Masa depan adalah tanggung jawabmu. Engkaulah yang terbaik di dunia ini.

Karya sederhana ini kupersembahkan untuk:

Papa dan Mama Tercinta Cici, Koko, Adik, dan “Sang Jagoan Kecil” Romo Susilo, Teman-teman, dan Segenap Keluarga Besar Seseorang yang mengisi kisahku Sahabat-sahabat terbaikku

v




ABSTRAK

Metode Kuasa adalah metode hampiran yang menggunakan barisan pangkat untuk mendapatkan nilai eigen dan vektor eigen dominan suatu matriks. Pada aplikasinya, Metode Kuasa digunakan untuk mengembangkan suatu algoritma pencarian yang disebut algoritma PageRank. Algoritma tersebut digunakan dalam mesin pencari Google untuk mengonstruksikan matriks yang menggambarkan struktur perujukan halaman-halaman yang sesuai dengan pencarian. Kemudian dengan menggunakan vektor eigen dominan dari matriks itu disusun daftar situs-situs yang dicari dengan urutan tertentu untuk menentukan peringkat situs-situs tersebut dalam urutan kepentingannya sebagai otoritas dan hub.

viii


ABSTRACT

The Power Method is an approximation method using power sequence to obtain dominant eigenvalue and eigenvector of a matrix. In its application, the Power Method is used to develop a search algorithm called the PageRank algorithm. The algorithm in fact is used in Google search engine to construct a matrix which describes the structure of the referring pages that match the search. Then using the dominant eigenvector of the matrix, sites will be listed in importance order as an authority and hub.

ix


KATA PENGANTAR

Puji dan syukur penulis persembahkan kepada Tuhan Yesus Kristus, yang karena berkat-Nya penulis dapat menyelesaikan skripsi ini yang disusun untuk memenuhi syarat memperoleh gelar Sarjana Sains di Universitas Sanata Dharma Yogyakarta. Penulis merasa bahwa skripsi ini tidak akan terwujud tanpa bantuan, bimbingan, dukungan dan dorongan dari berbagai pihak yang sangat berarti bagi penulis. Karena itu, dengan rendah hati penulis ingin mengucapkan terima kasih yang sebesar-besarnya kepada: 1.

Ibu Lusia Krismiyati Budiasih, S.Si., M.Si., selaku Kaprodi Matematika Fakultas Sains dan Teknologi yang telah membantu dan membimbing penulis secara akademik baik di dalam maupun di luar kelas.

2.

Romo Prof. Dr. Frans Susilo, S.J., selaku dosen pembimbing skripsi yang telah banyak memberikan waktunya untuk memberikan bimbingan, pengarahan, masukan, kritik, saran dan dukungan sehingga penulis dapat menyelesaikan skripsi ini.

3.

Ibu Maria Vianney Anny Herawati, S.Si., M.Si., selaku dosen penguji yang pernah memberikan masukan untuk penulis.

4.

Bapak Herry Pribawanto Suryawan, S.Si., M.Si., selaku dosen pembimbing sementara. Terimakasih atas lelucon, ide, dan semangat yang diberikan.

5.

Bapak Ir. Ig. Aris Dwiatmoko, M.Sc., selaku dosen yang menginspirasiku secara tak langsung lewat canda tawa.

6.

Bapak/Ibu Dosen Prodi Matematika Fakultas Sains dan Teknologi yang telah mendidik penulis selama menjalani studi di Fakultas Sains dan Teknologi ini. Terima kasih atas bimbingan dan arahannya selama ini.

7.

Bapak Zaerilus Tukija, Ibu Erma Linda Santyas Rahayu, Ibu Chatarina Maria sri Wijayanti, Mas Dwiratno Susilo dan para staff lain yang telah banyak memberikan bantuan di sekretariat FST dan laboratorium atas pelayanan administrasi dan bantuan yang diberikan.

x


8.

Perpustakaan Universitas Sanata Dharma dan staff yang telah menyediakan fasilitas dan pelayanan kepada penulis selama masa perkuliahan.

9.

Mama dan Papa tercinta dan terkasih, terima kasih buat semua doa, didikan, bimbingan, nasehat, dukungan dan kepercayaan yang diberikan pada penulis untuk mengambil keputusan dan langkah dalam menjalani kehidupan ini.

10. Grace Dalinartha dan Esther Natalia, S.Sn., kedua kakakku yang cerewet tapi baik hati ini. Terima kasih untuk bantuan yang tak terhingga kalian untukku. 11. Kie Van Ivanky Saputra, S.Si., Ph.D., yang banyak membantu aku menjelaskan dan memecahkan persoalan-persoalan mata kuliah dan skripsi. 12. Untuk “Sang Pemberi Kisah” dalam hidupku yang tidak ingin disebutkan namanya, yang mengajariku untuk selalu tegar untuk setiap cobaan. 13. Teman-teman

Universitas

Kristen

Maranatha,

khususnya

Reymon

Marlisyuniardi dan Yohanes Daniel Pangaribuan yang bersedia membantu dalam penjelasan-penjelasan bidang IT yang dibahas dalam skripsi ini. 14. Teman-teman Kost Wisma Manunggal, Riko, Doddy, Qnoy, Pipin, Desy yang tidak pernah lelah memberikan semangat untukku. 15. Teman-teman Matematika, terima kasih untuk keceriaan, kebersamaan, dinamika, pertemuan, dan dukungan. 16. Semua pihak yang belum penulis sebutkan satu per satu di sini, terima kasih untuk semua dukungan dan perhatiannya.

Penulis juga menyadari bahwa tulisan ini jauh dari sempurna. Oleh karena itu, penulis mengharapkan adanya saran dan kritikan dari pembaca yang dapat membangun penulis untuk mengembangkan kemampuan penulis menjadi lebih baik. Penulis berharap agar skripsi ini dapat menjadi inspirasi bagi pembaca.

Penulis,

Lina Meiliana

xi


DAFTAR ISI

Halaman HALAMAN JUDUL........................................................................................

i

HALAMAN JUDUL DALAM BAHASA INGGRIS .....................................

ii

HALAMAN PERSETUJUAN PEMBIMBING ..............................................

iii

HALAMAN PENGESAHAN..........................................................................

iv

HALAMAN PERSEMBAHAN ......................................................................

v

HALAMAN PERNYATAAN KEASLIAN KARYA .....................................

vi

LEMBAR PERSETUJUAN PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS .......................................................................

vii

ABSTRAK .......................................................................................................

viii

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

ix

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

x

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

xii

BAB I PENDAHULUAN ................................................................................

1

A. Latar Belakang Masalah .......................................................................

1

B. Rumusan Masalah ................................................................................

6

C. Batasan Masalah ..................................................................................

7

D. Tujuan Penulisan ..................................................................................

7

E. Metode Penulisan .................................................................................

7

F. Manfaat Penulisan ................................................................................

7

G. Sistematika Penulisan ..........................................................................

8

BAB II NILAI EIGEN DAN VEKTOR EIGEN .............................................

9

A. Nilai Eigen dan Vektor Eigen ..............................................................

9

B. Nilai Eigen Matriks Segitiga ................................................................

14

C. Nilai Eigen Matriks Pangkat ................................................................

16

D. Nilai Eigen Kompleks ..........................................................................

17

E. Kegandaan Aljabar ...............................................................................

18

xii


F. Nilai Eigen Matriks 2×2 .......................................................................

20

G. Nilai Eigen Matriks Simetrik 2×2 ........................................................

23

H. Determinan dan Teras Dinyatakan dalam Nilai Eigen .........................

28

I. Diagonalisasi ........................................................................................

30

BAB III METODE KUASA ............................................................................

39

A. Metode Kuasa ......................................................................................

39

B. Metode Kuasa dengan Perskalaan Euclides .........................................

42

C. Metode Kuasa dengan Perskalaan Entri Maksimum ...........................

44

D. Laju Konvergensi Hasil Bagi Rayleigh................................................

48

E. Prosedur Penghentian Iterasi ................................................................

49

F. Aplikasi Metode Kuasa pada Mesin Pencari Internet ..........................

51

BAB IV PENUTUP .........................................................................................

60

DAfTAR PUSTAKA .......................................................................................

63

xiii


BAB I PENDAHULUAN

A. Latar Belakang Masalah Internet dapat diartikan sebagai jaringan komputer luas dan besar yang mendunia, yaitu menghubungkan pemakai komputer dari suatu negara ke negara lain di seluruh dunia, di mana di dalamnya terdapat berbagai sumber daya informasi dari mulai yang statis hingga yang dinamis dan interaktif. Sejarah internet dimulai pada 1969 ketika Departemen Pertahanan Amerika, melalui U.S. Defense Advanced Research Projects Agency (DARPA) memutuskan untuk mengadakan riset tentang bagaimana menghubungkan sejumlah komputer sehingga membentuk jaringan organik. Program riset ini dikenal dengan nama ARPANET. Pada 1970, sudah lebih dari 10 komputer yang berhasil dihubungkan satu sama lain sehingga mereka bisa saling berkomunikasi dan membentuk sebuah jaringan. Tahun 1972, Roy Tomlinson berhasil menyempurnakan program email yang ia ciptakan setahun yang lalu untuk ARPANET. Program e-mail ini begitu mudah sehingga langsung menjadi populer. Pada tahun yang sama, lambang @ juga diperkenalkan sebagai lambang penting yang menunjukkan "at" atau "pada". Tahun 1973, jaringan komputer ARPANET mulai dikembangkan ke luar Amerika Serikat. Komputer University College di London merupakan komputer pertama yang ada di luar Amerika yang menjadi anggota jaringan Arpanet. Pada tahun yang sama, dua orang ahli


2

komputer yakni Vinton Cerf dan Bob Kahn mempresentasikan sebuah gagasan yang lebih besar, yang menjadi cikal bakal pemikiran internet. Ide ini dipresentasikan untuk pertama kalinya di Universitas Sussex. Hari bersejarah berikutnya adalah tanggal 26 Maret 1976, ketika Ratu Inggris berhasil mengirimkan e-mail dari Royal Signals and Radar Establishment di Malvern. Setahun kemudian, sudah lebih dari 100 komputer yang bergabung di ARPANET membentuk sebuah jaringan. Pada 1979, Tom Truscott, Jim Ellis dan Steve Bellovin, menciptakan newsgroups pertama yang diberi nama USENET. Tahun 1981 France Telecom menciptakan gebrakan dengan meluncurkan telpon televisi pertama, dimana orang bisa saling menelpon sambil berhubungan dengan video link. Karena komputer yang membentuk jaringan semakin hari semakin banyak, maka dibutuhkan sebuah protokol resmi yang diakui oleh semua jaringan. Pada tahun 1982 dibentuk Transmission Control Protocol atau TCP dan Internet Protokol atau IP yang kita kenal semua. Sementara itu di Eropa muncul jaringan komputer tandingan yang dikenal dengan Eunet, yang menyediakan jasa jaringan komputer di negara-negara Belanda, Inggris, Denmark dan Swedia. Jaringan Eunet menyediakan jasa e-mail dan newsgroup USENET. Untuk menyeragamkan alamat di jaringan komputer yang ada, maka pada tahun 1984 diperkenalkan sistem nama domain, yang kini kita kenal dengan DNS atau Domain Name System. Komputer yang tersambung dengan jaringan yang ada sudah melebihi 1000 komputer lebih. Pada 1987 jumlah


3

komputer yang tersambung ke jaringan melonjak 10 kali lipat menjadi 10.000 lebih. Tahun 1988, Jarko Oikarinen dari Finland menemukan dan sekaligus memperkenalkan IRC atau Internet Relay Chat. Setahun kemudian, jumlah komputer yang saling berhubungan kembali melonjak 10 kali lipat dalam setahun. Tak kurang dari 100.000 komputer kini membentuk sebuah jaringan. Tahun 1990 adalah tahun yang paling bersejarah, ketika Tim Berners Lee menemukan program editor dan browser yang bisa menjelajah antara satu komputer dengan komputer yang lainnya, yang membentuk jaringan itu. Program inilah yang disebut www, atau World Wide Web. Tahun 1992, komputer yang saling tersambung membentuk jaringan sudah melampaui sejuta komputer, dan di tahun yang sama muncul istilah surfing the internet. Tahun 1994, situs internet telah tumbuh menjadi 3000 alamat halaman, dan untuk pertama kalinya virtual-shopping atau e-retail muncul di internet. Dunia langsung berubah. Di tahun yang sama Yahoo! didirikan, yang juga sekaligus kelahiran Netscape Navigator 1.0. Secara umum ada banyak manfaat yang dapat diperoleh apabila seseorang mempunyai akses ke internet. Berikut ini sebagian dari apa yang tersedia di internet : 1. Informasi

untuk

kehidupan

pribadi:

pengembangan pribadi, rohani, dan sosial.

kesehatan,

rekreasi,

hobi,


2. Informasi

untuk

kehidupan

profesional/pekerja:

sains,

4

teknologi,

perdagangan, saham, komoditas, berita bisnis, asosiasi profesi, asosiasi bisnis, berbagai forum komunikasi. Satu hal yang paling menarik adalah keanggotan internet tidak mengenal batas negara, ras, ekonomi, ideologi, atau faktor-faktor lain yang biasanya dapat menghambat pertukaran pikiran. Internet adalah suatu komunitas dunia yang sifatnya sangat demokratis serta memiliki kode etik yang dihormati segenap anggotanya. Manfaat internet terutama diperoleh melalu kerjasama antar pribadi atau kelompok yang tanpa mengenal batas jarak dan waktu. Keberadaan situs tidak ada gunanya dibangun tanpa dikunjungi atau dikenal oleh masyarakat atau pengguna internet. Karena efektif atau tidaknya situs sangat tergantung dari besarnya pengunjung dan komentar yang masuk. Untuk mengenalkan situs kepada masyarakat memerlukan apa yang disebut publikasi atau promosi. Publikasi situs di masyarakat dapat dilakukan dengan berbagai cara seperti dengan pamflet-pamflet, selebaran, baliho dan lain sebagainya tapi cara ini bisa dikatakan masih kurang efektif dan sangat terbatas. Cara yang biasanya dilakukan dan paling efektif dengan tak terbatas ruang atau waktu adalah publikasi langsung di internet melalui mesin pencari-mesin pencari (search engine, seperti : Yahoo, Google, Search Indonesia, dan sebagainya). Cara publikasi di mesin pencari ada yang gratis dan ada pula yang membayar. Yang gratis biasanya terbatas dan cukup lama untuk bisa masuk dan dikenali di mesin pencari terkenal seperti Yahoo atau Google. Cara efektif


5

publikasi adalah dengan membayar, walaupun harus sedikit mengeluarkan biaya, akan tetapi situs cepat masuk ke mesin pencari dan dikenal oleh pengguna. Teori yang mendasari cara kerja mesin pencari internet ini adalah Metode Kuasa yang berkaitan dengan nilai eigen dan vektor eigen. Banyak penerapan yang mengharuskan kita menemukan suatu matriks taknol

sedemikian sehingga

λ , dengan A adalah matriks n × n yang

diketahui dan λ adalah skalar. Masalah ini dinamakan masalah nilai eigen dan merupakan masalah matriks kedua yang paling sering dijumpai selain masalah pemecahan sistem persamaan linear. Nilai eigen matriks bujursangkar, secara teori dapat ditemukan dengan menentukan persamaan karakteristik. Namun, prosedur ini memiliki begitu banyak kesulitan perhitungan yang hampir tidak pernah digunakan dalam aplikasi. Metode Kuasa akan membahas sebuah algoritma yang dapat digunakan untuk mendekati nilai eigen dengan nilai mutlak terbesar dan vektor eigen yang sesuai. Nilai eigen dan vektor eigen yang sesuai sangat penting karena mereka muncul secara alami dalam berbagai proses iteratif. Metode yang akan dibahas dalam bagian ini telah diterapkan untuk menghasilkan mesin pencari internet yang sangat cepat, dan akan dijelaskan bagaimana hal tersebut dilakukan. Metode Kuasa adalah metode hampiran yang menggunakan barisan pangkat dari suatu matriks untuk mendapatkan nilai eigen dominan suatu matriks yang memenui sifat | | eigen dominan.

| | untuk

2, 3,

, , dengan

merupakan nilai


6

Pengurutan hasil pencarian pada mesin pencari saat ini menjadi titik fokus bagi mesin pencari untuk menampilkan hasil pencarian yang penting. Sistem pengurutan diharapkan memberikan hasil yang signifikan. PageRank merupakan sistem pengurutan yang digunakan Google dan merupakan salah satu sistem pengurutan yang bekerja berdasarkan analisa jalur. Perhitungan pengurutan dengan menggunakan algoritma PageRank saat ini menjadi banyak perbincangan para peneliti karena perhitungan tersebut menghabiskan waktu yang lama, dan berhari-hari sehingga jika ada halaman baru tiap detik, maka PageRank tidak secara langsung memperbaharui halaman tersebut tetapi menunggu waktu perhitungan PageRank selanjutnya yang akan dilakukan secara offline. Untuk mempercepat perhitungan PageRank, dalam penelitian digunakan Hasil Bagi Rayleigh. Hasil Bagi Rayleigh dapat mempercepat konvergensi dengan cara menentukan nilai eigen dominan sehingga perhitungan galat berdasarkan selisih nilai eigen dominan tersebut dengan nilai eigen dominan sebelumnya. Berdasarkan analisa dari hasil uji coba, didapatkan bahwa waktu perhitungan PageRank dengan menggunakan Hasil Bagi Rayleigh lebih cepat dibandingkan dengan tanpa menggunakan Hasil Bagi Rayleigh.

B. Rumusan Masalah 1. Apa yang dimaksud dengan Metode Kuasa? 2. Bagaimana aplikasi metode kuasa pada mesin pencari internet?


7

C. Batasan Masalah Dalam skripsi ini, penulis hanya membahas aplikasi pada mesin pencari internet berdasarkan operasi-operasi matriks.

D. Tujuan Penelitian Penulisan skripsi ini bertujuan untuk mengetahui prinsip dan landasan teori yang digunakan dan bagaimana mesin pencari internet bekerja sehingga menghasilkan kecepatan yang sangat tinggi dalam menyajikan suatu informasi.

E. Metode Penulisan Penulisan skripsi ini menggunakan metode studi pustaka, yaitu dengan menggunakan

buku-buku,

jurnal

ilmiah,

dan

makalah

yang

telah

dipublikasikan. Oleh karena itu dalam skripsi ini tidak disajikan hal baru dalam bidang matematika.

F. Manfaat Penulisan Memahami cara kerja mesin pencari internet dengan kecepatan yang sangat tinggi dalam penyajian suatu informasi.


8

G. Sistematika Penulisan BAB I PENDAHULUAN Bab ini berisi gambaran secara umum tentang isi skripsi yang meliputi latar belakang masalah, rumusan masalah, batasan masalah, tujuan penulisan, metode penulisan, manfaat penulisan, dan sistematika penulisan. BAB II NILAI EIGEN DAN VEKTOR EIGEN Bab ini berisi beberapa teori yang melandasi pembahasan, yaitu nilai eigen dan vektor eigen, nilai eigen

pada matriks segitiga, matriks

pangkat, nilai eigen kompleks, kegandaan aljabar, nilai eigen matriks 2

2, nilai eigen matriks simetris 2

2, dan nilai eigen dalam

determinan dan teras suatu matriks. BAB III METODE KUASA DAN APLIKASINYA PADA MESIN PENCARI INTERNET Bab ini membahas tentang metode kuasa, metode kuasa dengan perskalaan Euclides dan entri maksimum, dan

aplikasinya yang

digunakan pada mesin pencari internet. BAB IV PENUTUP Bab ini berisi kesimpulan dari keseluruhan materi yang telah dipaparkan.


BAB II NILAI EIGEN DAN VEKTOR EIGEN

A. Nilai Eigen dan Vektor Eigen Banyak aplikasi dari Aljabar Linear yang melibatkan sistem dengan n persamaan linear dan n variabel yang dinyatakan dalam bentuk ,

(2.1.1)

dengan λ adalah suatu skalar, x adalah suatu sebarang vektor taknol di

,

dan A adalah suatu matriks n × n. Sistem semacam ini sebenarnya merupakan sistem linear yang tersamar, karena persamaan (2.1.1) dapat ditulis kembali 0, atau dengan menyisipkan suatu matriks identitas dan

sebagai

memfaktorkannya menjadi –

.

(2.1.2)

Masalah utama yang harus diperhatikan untuk sistem linear yang terbentuk pada persamaan (2.1.2) adalah bagaimana menentukan nilai λ sehingga sistem tersebut memiliki penyelesaian taktrivial. Nilai λ yang demikian disebut nilai eigen (nilai karakteristik) dari matriks A, dan penyelesaian taktrivial dari persamaan (2.1.2) disebut vektor eigen dari A yang terkait dengan λ. Sistem (λI – A)x = 0 memiliki penyelesaian taktrivial jika dan hanya jika –

0

(2.1.3)

yang disebut persamaan karakteristik dari A. Nilai-nilai eigen dari A dapat dicari

dengan

menyelesaikan

λ

pada

persamaan

ini.

Determinan

PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI 10

–

0 adalah sebuah polinomial dalam variabel λ yang disebut po-

linomial karakteristik matriks A.

Definisi 2.1.1 Jika A adalah sebuah matriks n × n, maka skalar λ disebut nilai eigen dari A jika terdapat vektor taknol x sedemikian sehingga

. Jika λ

adalah nilai eigen dari A, maka vektor taknol x sedemikian hingga disebut vektor eigen dari A yang berkaitan dengan λ.

Cara untuk menentukan nilai eigen dari matriks A adalah dengan menulis kembali persamaan

menjadi –

.

Persamaan tersebut mempunyai penyelesaian taktrivial jika dan hanya jika –

0.

Skalar-skalar λ yang memenuhi persamaan ini adalah nilai-nilai eigen dari A.

Teorema 2.1.1 Jika matriks A adalah sebuah matriks n × n dan λ adalah skalar, maka pernyataan berikut adalah ekivalen : (a) λ adalah nilai eigen dari A. (b) λ adalah penyelesaian persamaan (c) Sistem linear

–

–

0.

mempunyai penyelesaian taktrivial.


Bukti : Berdasarkan definisi, λ adalah nilai eigen dari A jika dan hanya jika terdapat vektor taknol x sedemikian sehingga , yang ekivalen dengan –

.

yaitu sistem persamaan linear homogen ini mempunyai penyelesaian taktrivial, yang terjadi jika dan hanya jika –

0.

yaitu λ adalah penyelesaian dari persamaan tersebut.

Contoh 2.1.1 Akan dicari nilai eigen dan vektor eigen terkait dari matriks

1 3 4 2

Mencari nilai eigen dengan persamaan karakteristik 1 0

0 1

1 4

3 2

1 4

3 . 2

Persamaan karakteristik dari A adalah –

0

1 4 1

2 –

3

3

2

3 2

0,

4

0,

2– 12

0,

3 – 10

0,

5

0.

(2.1.4)


2 dan

Jadi nilai eigen dari A adalah

5.

Untuk menentukan vektor eigen yang berkaitan dengan nilai eigen tersebut, harus diselesaikan sistem penyelesaian 1 4 Untuk

0 . 0

3 2

(2.1.5)

2, persamaan (2.1.5) akan menjadi 2

1

2

0 , 0

3 4

0 . 0

3

4

2 3 4

Penyelesaian ini memberikan hasil ,

,

(2.1.6) 2 adalah vektor taknol

maka vektor eigen yang berkaitan dengan berbentuk

1 . 1

(2.1.7)

Periksa 1 3 4 2

2 2

2

2 .

5, penyelesaiannya memberikan hasil

Dengan cara yang sama untuk ,

,

(2.1.8) 5 adalah vektor taknol

dan vektor eigen yang berkaitan dengan berbentuk

1

.

(2.1.9)


Jika λ adalah nilai eigen dari A dan x adalah vektor eigen yang terkait, maka , sehingga perkalian dengan A memetakan lian skalar dengan dirinya sendiri. Pada

dan

ke dalam suatu perka-

, ini berarti bahwa perka-

lian dengan A memetakan setiap vektor eigen x ke suatu vektor yang terletak pada garis yang sama dengan . Operator linear dengan suatu faktor λ jika 0 tor λ jika

1. Jika

memperkecil

1 atau memperbesar

0, maka

dengan suatu fak-

membalik arah , dan memper-

kecil vektor yang telah diputar tersebut dengan suatu faktor |λ| jika 0 | |

1 atau memperbesar vektor yang telah diputar tersebut dengan suatu

faktor |λ| jika | |

1.

Contoh 2.1.2 0 0 4

Akan dicari nilai eigen dari matriks

1 0 17

0 1 . 8

Dari determinan det

1 0 4 17

didapatkan persamaan karakteristik

0 1 8

8 8

17

17

4

4 0.

(2.1.10) (2.1.11)

Untuk mencari penyelesaian persamaan ini, akan dimulai dengan mencari penyelesaian bilangan bulatnya. Penyelesaian bilangan bulat (jika memang ada) untuk sebuah persamaan polinomial dengan koefisien-koefisien bilangan bulat 0


haruslah merupakan faktor-faktor pembagi dari konstanta

. Sehingga,

penyelesaian bilangan bulat yang mungkin dari persamaan (2.1.11) hanyalah 4, yaitu

faktor-aktor pembagi dari bilangan

1,

2, dan

4. Dengan

mensubstitusi nilai tersebut secara berturut-turut ke dalam persamaan (2.1.11) 4 sebagai sebuah penyelesaian bilangan bulatnya.

akan menghasilkan

4 haruslah merupakan salah satu faktor dari

Sebagai konsekuensinya,

ruas kiri persamaan (2.1.11), sehingga persamaan (2.1.11) dapat ditulis kembali menjadi –4

4

1

0.

Maka, penyelesaian persamaan (2.1.11) adalah 4,

2

√3,

2

√3.

Definisi 2.1.2 Ruang penyelesaian sistem persamaan linear homogen

–

disebut ruang eigen dari matriks A yang berkaitan dengan nilai eigen λ. Vektor-vektor eigen yang terkait dengan nilai eigen λ adalah adalah vektor-vektor taknol dalam ruang eigen.

B. Nilai Eigen Matriks Segitiga Jika A adalah matriks segitiga n × n dengan entri diagonal ,

, ,

,

, maka ,

, –

–

adalah matriks segitiga dengan entri diagonal . Jadi polinomial karateristiknya adalah ,


yang secara tidak langsung menyatakan bahwa nilai eigen dari A adalah ,

,

,

Teorema 2.2.1 Jika A adalah matriks segitiga n × n (segitiga atas, segitiga bawah, atau diagonal), maka nilai-nilai eigennya adalah entri diagonal utama dari matriks A.

Bukti : Misalkan A adalah matriks segitiga atas 0 0

. 0

Telah diketahui bahwa nilai determinan sebuah matriks segitiga adalah hasil kali entri-entri yang terletak pada diagonal utamanya, maka

det

0

,

0

0 ,

sehingga diperoleh persamaan karakteristiknya 0, dan nilai-nilai eigennya adalah ,

,

,

,

yang merupakan entri-entri diagonal utama matriks A.


Dengan cara yang sama dapat dibuktikan pula untuk matriks segitiga bawah dan matriks diagonal. Jadi terbukti bahwa nilai eigen matriks segitiga adalah

entri-entri diagonal utamanya.

C. Nilai Eigen Matriks Pangkat Ketika nilai eigen dan vektor eigen dari suatu matriks A telah ditemukan, tidaklah sulit untuk menentukan nilai eigen dan vektor eigen dari pangkat bilangan bulat positif sebarang dari A. Sebagai contoh, jika λ merupakan nilai eigen dari A dan x merupakan vektor eigen terkaitnya, maka , yang menunjukkan bahwa

nilai eigen dari

dan x adalah vektor eigen

kaitannya.

Teorema 2.3.1 Jika λ adalah nilai eigen dari matriks A, x adalah vektor eigen kaitannya, dan k adalah sebarang bilangan bulat positif, maka eigen dari matriks

adalah nilai

dan x adalah vektor eigen yang terkait dengannya.

Bukti : Misalkan A adalah matriks persegi dan x adalah vektor eigen yang terkait dengan nilai eigen λ. Maka Andaikan

, yaitu Teorema benar untuk k = 1.

. Akan dibuktikan bahwa

.


Sehingga

. Jadi Teorema benar untuk setiap bilangan bulat

positf k.

D. Nilai Eigen Kompleks Bukanlah hal yang mustahil bahwa persamaan karakteristik sebuah matriks yang entri-entrinya bilangan real memiliki penyelesaian bilangan kompleks. Sebagai contoh, polinomial karakteristik dari matriks 2 5

1 2

(2.4.1)

adalah 2 5 sehingga

persamaan

1

1,

2

karakteristiknya

adalah

(2.4.2) 1

persamaan karakteristiknya merupakan bilangan kompleks

0.

Akar-akar dan

.

Dengan demikian, kita harus berurusan dengan nilai eigen bilangan kompleks, bahkan untuk matriks real sekalipun. Penyelesaian kompleks dari persamaan karakteristik disebut nilai eigen kompleks.


E. Kegandaan Aljabar Jika A adalah matriks n × n, maka suatu bentuk khusus dari –

determinan

adalah polinomial berderajat n di mana koefisien

adalah 1, yaitu –

,

(2.5.1)

bentuk polinomialnya adalah ,

(2.5.2)

yang disebut polinomial karakteristik dari A. Sebagai contoh, polinomial karakteristik dari matriks A2

× 2

dalam Contoh 2.1.1 adalah polinomial

3 – 10 (lihat persamaan (2.1.4)) dan polinomial

berderajat dua,

karakteristik matriks A3 × 3 dalam Contoh 2.1.2 adalah polinomial berderajat tiga,

8

17

4 (lihat persamaan (2.1.11)).

Salah satu dari ketiga hal di bawah ini dapat terjadi untuk faktorfaktor polinomial karakteristik , 1. Faktor-faktor polinomial akan menghasilkan akar-akar real yang berbeda, sebagai contoh 2

–2

–1

2 .

2. Faktor-faktor polinomial akan menghasilkan akar-akar real yang berbeda, namun terdapat pengulangan beberapa faktor, sebagai contoh 3

2

3

2

–1

2 .


3. Faktor-faktor polinomial akan menghasilkan akar-akar kompleks, sebagai contoh 1

–1

1

–1

1

–

.

Dapat dibuktikan bahwa jika nilai eigen kompleks dimungkinkan, maka polinomial karakteristik dari matriks An × n dapat difaktorkan menjadi 1

1

,

di mana

,…

–

–

1

2

…

(2.5.3)

–

adalah nilai-nilai eigen dari A. Hal ini disebut

pemfaktoran linear lengkap dari polinomial karakteristik. Jika k faktorfaktor pertama berbeda, dan sisanya merupakan pengulangan dari k faktorfaktor pertama, maka persamaan (2.5.3) dapat ditulis kembali menjadi 1

di mana

,

,…

1

–

1

1

–

2

2

…

(2.5.4)

–

adalah nilai-nilai eigen yang berbeda dari A. Pangkat

disebut kegandaan aljabar dari nilai eigen

yang menggambarkan berapa

kali pengulangan nilai eigen dalam pemfaktoran linear lengkap dari polinomial karaktersitik. Jumlahan dari kegandaan aljabar nilai eigen dalam persamaan (2.5.4) harus sama dengan n, karena polinomial karaktersitik berderajat n. Sebagai contoh, jika A matriks 6 × 6 dengan polinomial karakteristiknya adalah 3

2

3

maka nilai eigen berbeda dari A adalah

2

–1 0,

1, dan

2 2, dan ke-

gandaan aljabar nilai eigen ini berturut-turut adalah 3, 2, 1, yang jumlahannya sampai dengan 6.


Teorema 2.5.1 Jika A adalah matriks n × n, maka polinomial karakteristik dari A dapat dinyatakan sebagai – ,

di mana

,…

–

–

…

–

adalah nilai eigen yang berbeda dari A dan .

Bukti : Polinomial karakteristik dari A adalah : – – – di mana

,

,…,

–

… –

– …

–

,

adalah pengulangan faktor yang berbeda sedemikian

sehingga jumlahan

yang sama dengan pangkat ter-

tinggi dari λ.

F. Nilai Eigen Matriks 2 × 2 Definisi 2.6.1 Jika A adalah sebuah matrks bujursangkar, maka teras dari A, yang dinyatakan sebagai A.

, adalah jumlahan entri-entri pada diagonal utama


Selanjutnya, akan dibahas nilai-nilai eigen matriks 2 × 2 dalam Teorema berikut.

Teorema 2.6.1 Jika A adalah matriks 2 × 2 dengan entri bilangan real, maka persamaan karakteristik dari A adalah –

0,

dan (a) A mempunyai dua nilai eigen real yang berbeda bila (b) A

mempunyai

satu

–4

nilai

eigen

real

0;

–4

yang

berulang

–4

0.

bila

0;

(c) A mempunyai dua nilai eigen kompleks bila

Bukti : Misalkan

dengan , , ,

.

Polinomial karakteristik dari A adalah det . Karena teras dari matriks A adalah triks A adalah

, maka

dan determinan dari ma-


–

–

(2.6.1)

sehingga persamaan karakteristik dari matriks A adalah –

0

(2.6.2)

Akar-akar persamaan kuadrat tersebut adalah 4det ,

(a) Jika

2

–4

0, maka A mempunyai dua nilai eigen real ber–

beda, yaitu (b) Jika

–4

–

dan

0, maka

.

√

, yaitu A mem-

–4

merupakan bi-

,

punyai satu nilai eigen real yang berulang. (c) Jika

–4

0, maka

langan kompleks, sehingga A mempunyai dua nilai eigen kompleks, yaitu –

–

dan

.

Contoh 2.6.1 Dengan menggunakan persamaan karakteristik pada persamaan (2.6.2) akan dicari nilai eigen dari (a) Diketahui

2 1

2 , 5

0 1

(b)

7 dan

1 , 2

(c)

2 3

3 . 2

12, maka persamaaan karakteristik dari

A adalah 7

12

0,


hasil pemfaktorannya adalah dan

–4

–3

0, maka nilai eigennya

4

3. 1, dan ni-

Dengan cara yang sama, maka nilai eigen pada soal (b) adalah lai eigen pada soal (c) adalah

3.

2

G. Nilai Eigen Matriks Simetrik 2 × 2 Teorema 2.7.1 Matriks simetrik 2 × 2 dengan entri real mempunyai nilai eigen real. Jika A berbentuk 0

,

0

(2.7.1)

maka A mempunyai satu nilai eigen berulang, yakni

.

Bukti : Misalkan matriks simetrik 2 × 2 adalah , maka –4

–4

–

4

0,

sehingga dengan Teorema 2.6.1 (a) dan (b), A mempunyai nilai eigen real. Jika

0 0

, maka –4

4

4

sehingga A mempunyai satu nilai eigen berulang, yaitu

0, .


Teorema 2.7.2 (a) Jika sebuah matriks simetrik 2 × 2 dengan entri real mempunyai nilai .

eigen berulang, maka ruang eigen terkaitnya adalah

(b) Jika sebuah matriks simetrik 2 × 2 dengan entri real mempunyai dua nilai eigen berbeda, maka ruang eigen terkaitnya adalah dua garis tegak lurus yang melalui titik 0 pada

.

Bukti : (a) Misalkan matriks simetrik 2 × 2 adalah –4

nilai eigen berulang, maka 4

rena triks

0 0

. Jika A mempunyai 4

0 jika hanya jika

dan

0. Ka-

0, maka ma-

, sehingga nilai eigen berulangnya adalah λ

. Menu-

rut Definisi 2.1.2, ruang eigen yang terkait dengan nilai eigen λ

ada-

lah ruang penyelesaian dari sistem persamaan linear homogen

0

0 0

0 0 0 0

0 0

0

yaitu setiap titik

dalam

. Maka ruang eigen terkaitnya adalah

(b) Jika A mempunyai dua nilai eigen berbeda, maka 4

0. Kedua nilai eigen tersebut adalah

–4

.


–

dan –

.

Ruang eigennya adalah ruang penyelesaian sistem persamaan linear homogen

0 0 Untuk

, maka 0 . 0

Misalkan

dan

, maka 0 . 0

Selanjutnya dengan operasi baris elementer diperoleh 1 0

0

0 . 0

yang menghasilkan 2

dan

Penyelesaian tersebut merupakan garis melalui 0 di dengan

.

4

.

yang berkaitan


Dengan cara yang sama, untuk

akan diperoleh

penyelesaian 2

4

dan

.

yang berkaitan dengan

yang merupakan garis melalui 0 di

.

Kedua garis tersebut saling tegak lurus karena ·

·

4

4

4

—

4

—

4 4

— 0 Jadi terbukti bahwa ruang eigen terkaitnya adalah dua garis tegak lurus yang melalui titik 0 pada

.

Contoh 2.7.1 Tentukan ruang eigen dari matriks simetrik 3 2 Karena

6 dan

2 . 3

5, maka persamaan karakteristik dari A ada-

lah 6 –1

5 –5

0 0


1 dan

sehingga nilai eigen dari A adalah

5. Ruang eigennya adalah

ruang penyelesaian sistem persamaan linear homogen 3 2 Untuk

0 . 0

2 3

(2.7.2)

1, persamaan 2.7.2 menjadi 2 2

0 . 0

2 2

Penyelesaian ini menghasilkan ,

,

(2.7.3)

yang merupakan persamaan parameter dari garis

. Garis ini adalah

1. Dengan cara yang sama, untuk

ruang eigen yang terkait dengan 5 akan dihasilkan penyelesaian ,

,

(2.7.4)

yang merupakan persamaan parameter dari garis y

( λ = 1) y = −x

.

(λ = 5) y = x (1,1)

(-1, 1)

x 0

Gambar 2.1 Garis

dan

adalah dua garis tegak lurus yang melalui 0 di

,

seperti dikatakan dalam Teorema 2.7.2 (b). Vektor-vektor pada persamaan 2.7.3 dan 2.7.4 dapat ditulis dengan bentuk


1 1

1 , 1

dan

dengan vektor perentangnya adalah 1 1

1 1

dan

(2.7.5)

yaitu dua vektor eigen yang orthogonal.

H. Determinan dan Teras Matriks Dinyatakan dalam Nilai Eigen Teorema 2.8.1 ,

Jika A adalah matriks n × n dengan nilai eigen

,

,

(mungkin

ada yang berulang), maka (a) b

Bukti : (a) Dengan menulis polinomial karakteristik dalam bentuk faktorisasi: – dan dengan memasukkan

–

–

1

(2.8.1)

.

, maka .

(b) Misalkan

–

0, dihasilkan 1

Karena

…

(2.8.2)

, maka

–

(2.8.3)


Bila

dihitung dari determinan tersebut dengan membentuk jumlahan

dari perkalian elementer bertanda, maka perkalian elementer yang memuat entri yang tidak berada pada dari diagonal utama dari 2.8.3 sebagai faktor, 2 faktor yang melibatkan λ. Jadi koefi-

akan memuat paling banyak sien dari

dalam

sama dengan koefisien dari

dalam perka-

lian

Dengan mengembangkan perkalian tersebut, akan diperoleh (2.8.4) Dan dengan mengembangkan persamaan

pada 2.8.1, akan diperoleh

sehingga didapatkan

Contoh 2.8.1 Akan dicari determinan dan teras dari matriks 3 × 3 yang mempunyai karakteristik polinomial 3

2.

(2.8.5)

Polinomial tersebut dapat difaktorkan menjadi –1 maka nilai eigennya adalah

1, 2 dan

2 , 1, dan

2. Jadi, 0.


I. Diagonalisasi Definisi 2.9.1 Sebuah matriks bujursangkar A dikatakan dapat didiagonalkan jika terdapat sebuah matriks P yang yang taksingular sedemikian sehingga adalah sebuah matriks diagonal. Matriks P dikatakan mendiagonalkan matriks A.

Definisi 2.9.2 Matriks A dan B yang berukuran n × n dikatakan similar jika terdapat matriks P yang taksingular sedemikian sehingga .

(2.9.1)

Teorema 2.9.1 Jika A adalah sebuah matriks n × n, maka A dapat didiagonalkan jika hanya jika matriks A memiliki n vektor eigen yang bebas linear.

Bukti: Misalkan matriks A berukuran n × n dan memiliki n buah vektor eigen yang bebas linear, yaitu

,

,

,

. Vektor-vektor eigen tersebut dapat di-

susun sebagai kolom-kolom dari matriks P berukuran n × n | |

| |

| |

.


Matriks P tersebut taksingular karena mempunyai n vektor kolom di

yang

bebas linear. Maka |

|

|

|

|

|

|

|

| A

A |

|

|

| |

|

λ

λ |

karena

, dengan 1, 2,

eigen

,

|

(2.9.2) |

adalah nilai eigen yang berkaitan dengan vektor

.

Misalkan D matriks diagonal dengan elemen-elemen diagonal nilai eigen

. Maka |

|

|

|

|

|

|

λ 0

|

|

|

0 0

0 0

λ

(2.9.3)

| λ

λ

0 λ

. |

Maka . Karena P taksingular, maka: (2.9.4) Jadi matriks A dapat didiagonalkan. Selanjutnya, akan dibuktikan bahwa jika matriks A dapat didiagonalkan, maka A mempunyai n buah vektor eigen yang bebas linear. Misalkan matriks A similar dengan matriks diagonal D dengan


elemen-elemen diagonalnya

,

,

,

adalah

, dan

matriks taksingular sedemikian sehingga

. Maka

. Ka-

rena

(2.9.5) dan (2.9.6) maka

untuk

1, 2, … , . Hal ini berarti bahwa

triks A dengan

merupakan vektor eigen dari ma-

adalah nilai eigen yang berkaitan untuk

rena P adalah matriks yang taksingular, maka vektor-vektor

1, 2, … , . Ka,

,

bas linear. Jadi A mempunyai n buah vector eigen yang bebas linear.

,

be

Dari bukti di atas, didapatkan langkah-langkah untuk mendiagonalikan sebuah matriks A berukuran n × n, sebagai berikut : Langkah 1 : Tentukan vektor-vektor eigen yang bebas linear dari A. Langkah 2 : Susun vektor-vektor eigen tersebut sebagai kolom-kolom dari matriks P. Langkah 3 : Tentukan Langkah 4 : Tentukan

di mana D adalah matriks diagonal dengan

elemen-elemen diagonalnya adalah nilai-nilai eigen dari matriks A.


Contoh 2.9.1 Diketahui matriks

5 2

7 yang mempunyai nilai eigen 4

3 dan vektor eigen yang berkaitan adalah 7, 2 . Dengan mengambil

1 1

7 , maka 2

7 1

5 2

2 dan

1, 1 dan 2 1

7 , se1

hingga 1 2 5 1

7 4

1 1

7 2

2 0 0 3

Definisi 2.9.3 Sebuah matriks bujursangkar A disebut matriks ortogonal jika . Dengan kata lain untuk matriks A tersebut berlaku

.

Definisi 2.9.4 Matriks bujursangkar A dikatakan dapat didiagonalkan secara orthogonal jika terdapat matriks orthogonal P dan matriks diagonal D sedemikian sehingga

.

Teorema 2.9.2 Matriks bujur sangkar A dapat didiagonalkan secara orthogonal jika dan hanya jika A matriks simetrik.


Bukti: Misalkan A adalah matriks yang dapat didiagonalkan secara orthogonal. Maka terdapat matriks orthogonal P dan matriks diagonal D sedemikian sehingga , sehingga . Karena D adalah matriks diagonal, maka

(2.9.8) , sehingga

yaitu A adalah matriks simetrik. Sebaliknya, dengan induksi matematis, akan dibuktikan bahwa jika A matriks simetrik, maka A dapat didiagonalkan secara orthogonal. Untuk matriks berukuran 1 × 1, jelas bahwa A dapat didiagonalkan secara orthogonal. Untuk 2, asumsikan bahwa setiap matriks simetrik

1

1 dapat di-

diagonalkan secara orthogonal. Misalkan A matriks simetrik berukuran maka A selalu mempunyai nilai eigen real λ. Misalkan berkaitan dengan λ, dan

, sehingga | |

| |

vektor eigen yang

1. Selanjutnya dengan

menggunakan algoritma Gram-Schmidt ditentukan vektor-vektor sehingga kan

,

,

,

,

,

,

adalah himpunan vektor-vektor othonormal. Misal. Maka Q adalah matriks orthogonal, dan


dan

.

Karena

,

,

,

orthonomal, maka 0 0

dengan * adalah elemen yang mungkin taknol. Tetapi

Karena matriks A simetrik, maka matriks B juga simetrik. Oleh karena itu, baris pertama dari matriks B sama dengan kolom pertamanya. Jadi, bentuk B adalah 0

0 0

0

0

0

di mana C adalah matriks simetrik berukuran

1

asumsi, ada matriks orthogonal R dan matriks diagonal ga

. Dibentuk matriks

1 . Berdasarkan sedemikian sehing-


1 0

0

0

0 yang juga merupakan matriks orthogonal, karena vektor-vektor kolomnya orthonormal. Selanjutnya 1 0

0

0

1 0

0

0

0

0

0

0 0

0

0

0

0

0

0 0 0 0 . Jadi

yang merupakan matriks diagonal. Misalkan

merupakan matriks orthogonal karena

dan

, maka

matriks-matriks orthogonal,

dan

Jadi, matriks

dapat didiagonalkan secara orthogonal.


Teorema 2.9.3 Vektor-vektor eigen yang berkaitan dengan nilai-nilai eigen yang berbeda dari matriks simetrik adalah orthogonal

Bukti: Misalkan A matriks simetrik, ,

matriks A, dan bahwa

·

dan

adalah nilai-nilai eigen berbeda dari

vektor-vektor eigen yang berkaitan. Akan ditunjukkan

. Perhatikan bahwa ·

·

·

dan

·

(2.9.7)

Selanjutnya ·

· Dengan demikian, kedua ruas kanan dari persamaan (2.9.7) adalah sama, yaitu ·

·

· Karena

, maka

·

.


Contoh 2.9.2 Diketahui matriks simetrik 0,

6, dan 4,1,1 ,

1 2 2 2 6 2 2 2 6

yang mempunyai nilai eigen

9 dan vektor-vektor eigen yang berkaitan adalah 0, 1,1 , dan ·

1,2,2 , dengan ·

·

yaitu vektor-vektor eigen tersebut adalah orthogonal.


BAB III METODE KUASA

A. Metode Kuasa Dalam banyak aplikasi suatu vektor

dalam

seringkali dikalikan

secara berulang-ulang dengan matriks A berukuran n × n sehingga menghasilkan suatu barisan

,

,

,

,

,

. Bentuk seperti ini disebut

barisan kuasa yang dibangun oleh A. Dalam tulisan ini, akan dibahas kekonvergenan barisan kuasa tersebut dan hubungannya dengan nilai eigen dan vektor eigen.

Definisi 3.1.1 Jika nilai-nilai eigen yang berbeda dari sebuah matriks A adalah ,

,

, dan jika | | lebih besar dari | |,

,

,|

|, maka

disebut ni-

lai eigen dominan dari A. Vektor eigen yang berkaitan dengan nilai eigen dominan disebut vektor eigen dominan dari A.

Contoh 3.1.1 4,

Diketahui nilai-nilai eigen sebuah matriks adalah dan

3. Nilai

2,

4 merupakan nilai eigen dominan karena | |

1, 4

lebih besar dari nilai mutlak nilai eigen lainnya. Namun, jika diketahui nilainilai eigen sebuah matriks adalah maka | |

| |

7,

7,

2, dan

5,

7, sehingga tidak terdapat nilai eigen yang nilai mutlak-


nya lebih besar daripada semua nilai eigen lainnya, sehingga tidak terdapat nilai eigen dominan.

Teorema 3.1.1 Misalkan A adalah matriks simetrik n × n dengan nilai eigen dominan positif

. Jika

adalah vektor satuan dalam

dap ruang eigen yang terkait dengan ,

,

yang tidak ortogonal terha-

, maka barisan kuasa ternormalkan ,

,

,

(3.1.1)

konvergen ke vektor eigen dominan satuan dari matriks A, dan barisan ·

,

·

,

·

konvergen ke nilai eigen dominan

,

,

·

,

(3.1.2)

dari matriks A.

Bukti : Misalkan matriks A simetrik berukuran n × n, maka A dapat didiagonalkan secara orthogonal, sehingga A mempunyai n vektor eigen bebas linear ,

,

basis di

,

yang berkaitan dengan nilai eigen . Misalkan

,

dan membentuk

. Maka

yang tidak orthogonal terhadap ruang eigen merupakan kombinasi linear dari vektor-

vektor basis : , sehingga

,

adalah nilai eigen dominan positif dari A, dan

adalah vektor satuan dalam yang terkait dengan

,


dan

. karena | | lebih besar dari | |,

,|

|, maka untuk setiap i = 2, 3, …, n,

1. Jadi untuk setiap i = 2, 3, …, n,

0 bila

∞, sehingga

∞.

untuk

Barisan 3.1.1 dapat dinyatakan dengan ,

,

,

,

,

dan barisan tersebut konvergen ke vektor eigen dominan satuan karena , untuk

∞.

Terbukti barisan 3.1.1 konvergen ke vektor eigen dominan satuan dari A. Karena

konvergen ke

, maka ·

·

akan konvergen ke ·

yang merupakan nilai eigen dominan dari matriks A .


B. Metode Kuasa dengan Perskalaan Euclides Teorema 3.1.1 memberikan suatu algoritma untuk pendekatan nilai eigen dominan dan vektor eigen dominan satuan yang terkait dari sebuah matriks simetrik A, asalkan nilai eigen dominannya positif. Algoritma ini disebut metode kuasa dengan perskalaan Euclides, dengan langkah-langkah sebagai berikut: 1. Langkah 1 : Pilihlah sebarang vektor satuan 2. Langkah 2 : Tentukan pertama ·

·

untuk memperoleh pendekatan pertama ke nilai eigen dominan.

·

dan normalkan untuk mendapatkan pendekatan

terhadap vektor eigen dominan satuan. Kemudian tentukan untuk memperoleh pendekatan kedua ke nilai eigen dominan.

4. Langkah 4 : Tentukan ketiga


terhadap vektor eigen dominan satuan. Kemudian tentukan

3. Langkah 3 : Tentukan kedua

.


terhadap vektor eigen dominan satuan. Kemudian tentukan untuk memperoleh pendekatan ketiga ke nilai eigen dominan.

Lanjutkan langkah-langkah tersebut sampai menghasilkan barisan yang cukup untuk menghasilkan pendekatan yang terbaik untuk nilai eigen dominan dan vektor eigen dominan satuan yang terkait.


Contoh 3.2.1 Akan digunakan metode kuasa dengan perskalaan Euclides pada matriks 1 dan akan dibandingkan hasil penghitungan pada 0

3 2 dengan 2 3

x5 dengan nilai eigen dan vektor eigen dominan yang eksak. Pada Contoh 2.8.1, telah diketahui bahwa nilai eigen dari matriks A adalah 1 dan

5, maka nilai eigen dominan matriks A adalah

5. Ruang

5 juga telah ditunjukkan pada Contoh 2.8.1,

eigen yang terkait dengan

yang merupakan sebuah garis yang dsajikan oleh persamaan parameter x dan x

, yang dapat ditulis dalam bentuk vektor sebagai 1 1

Jadi dengan mengambil

√

dan

√

(3.2.1) akan diperoleh dua vektor eigen

satuan dominan, yaitu √

dan

√

√

(3.2.2)

√

Sekarang akan digunakan metode kuasa untuk memperoleh pendekatan terhadap nilai eigen dan vektor eigen dominan. 3 2 1 2 3 0

3 2

√

3 2

.

3 2

0.83205 0.55470

3 2 0.83205 2 3 0.55470

3.60555 3.32820

.

3.60555 3.32820

0.73480 0.67828

3 2 0.73480 2 3 0.67828

3.56097 3.50445

.

3.56097 3.50455

0.71274 0.70143

3 2 0.71274 2 3 0.70143

3.54108 3.52976

.

3.54108 3.52976

0.70824 0.70597

3 2 0.70824 2 3 0.70597

3.53666 3.53440

.

3.53666 3.53440

0.70733 0.70668


Jadi

·

3.60555

3.32820

0.83205 0.55470

4.84615

·

3.56097

3.50445

0.73480 0.67828

4.99361

·

3.54108

3.52976

0.71274 0.70143

4.99974

·

3.53666

3.53440

0.70824 0.70597

4.99999

·

3.53576

3.53531

0.70733 0.70668

5.00000

adalah pendekatan nilai eigen dominan dengan ketepatan lima angka

desimal dan x5 adalah pendekatan terhadap vektor eigen dominan 1 √2 1

0.707106781187 … 0.707106781187 …

√2 dengan ketepatan tiga angka desimal.

C. Metode Kuasa dengan Perskalaan Entri Maksimum Variasi dari metode kuasa adalah metode di mana setiap iterasinya diskalakan dengan entri maksimum. Akan digunakan notasi max

untuk

menyatakan nilai mutlak terbesar dari entri-entri dalam vektor .

Teorema 3.3.1 Misalkan A adalah matriks simetrik n × n dengan nilai eigen dominan positif

. Jika

adalah vektor taknol dalam

terhadap ruang eigen yang terkait dengan

,

,

,

yang tidak ortogonal

, maka barisan

,

,

(3.3.1)


konvergen ke vektor eigen yang berkaitan dengan · ·

konvergen ke

,

· ·

,

· ·

,

, dan barisan ·

,

·

,

(3.3.2)

.

Bukti : Misalkan matriks A simetrik berukuran n × n, maka A dapat didiagonalkan secara orthogonal, sehingga A mempunyai n vektor eigen bebas linear ,

,

basis di

,

yang berkaitan dengan nilai eigen . Misalkan

vektor satuan dalam terkait dengan

. Maka

,

,

,

dan membentuk

adalah nilai eigen dominan positif dari A, dan yang tidak orthogonal terhadap ruang eigen yang merupakan kombinasi linear dari vektor-vektor

basis: , sehingga

dan

.


karena | | lebih besar dari | |,

,|

|, maka untuk setiap i = 2, 3, …, n,

1. Jadi untuk setiap i = 2, 3, …, n,

0 bila

∞, sehingga

∞.

untuk

Barisan 3.3.1 dapat dinyatakan dengan ,

,

max

,

max

,

max

,

dan barisan tersebut konvergen ke vektor eigen yang berkaitan dengan nilai eigen dominan

, yaitu

, karena untuk

∞.

Terbukti barisan 3.3.1 konvergen ke vektor eigen dominan dari A. Karena konvergen ke

, maka

·

akan konvergen ke

· ·

·

·

· · ·

yang merupakan nilai eigen dominan dari matriks A .

Definisi 3.3.1 Hasil bagi Rayleigh dari vektor

terhadap matriks A didefinisikan sebagai · ·


Langkah-langkah Metode Kuasa dengan Perskalaan Entri Maksimum : 1. Langkah 1

: Pilihlah sebuah vektor taknol

2. Langkah 2

: Tentukan

.

dan kalikan dengan

untuk

menghasilkan pendekatan pertama

terhadap vektor eigen dominan.

Tentukan hasil bagi Rayleigh dari

untuk menghasilkan pendekatan

pertama terhadap nilai eigen dominan. 3. Langkah 3

: Tentukan

dan kalikan dengan

menghasilkan pendekatan kedua Tentukan hasil bagi Rayleigh dari

untuk

terhadap vektor eigen dominan. untuk menghasilkan pendekatan

kedua terhadap nilai eigen dominan. 4. Langkah 4

: Tentukan

dan kalikan dengan

menghasilkan pendekatan ketiga Tentukan hasil bagi Rayleigh dari

untuk

terhadap vektor eigen dominan. untuk menghasilkan pendekatan

ketiga terhadap nilai eigen dominan. Lanjutkan langkah-langkah tersebut sampai menghasilkan barisan yang cukup untuk pendekatan yang terbaik terhadap nilai eigen dominan dan vektor eigen yang berkaitan.

Contoh 3.3.1 Akan dihitung ulang Contoh 3.2.1 dengan metode ini. 3 2 1 2 1 0

3 2

3 2 1.00000 2 1 0.66667

3 2 4.33333 4.00000

.

1.00000 0.66667 4.33333 4.00000

1.00000 0.92308


3 2 1.00000 2 3 0.92308

4.84615 4.76923

.

4.84615 4.76923

1.00000 0.98413

3 2 1.00000 2 3 0.98413

4.96825 4.95238

.

4.96825 4.95238

1.00000 0.99681

3 2 1.00000 2 3 0.99681

4.99361 4.99042

.

4.99361 4.99042

1.00000 0.99936

.

.

.

. .

.

.

. .

.

.

. .

.

.

. .

.

.

Jadi

.

4.84615 4.99361 4.99974 4.99999 5.00000

adalah pendekatan terhadap nilai eigen dominan dengan ketelitian

lima angka desimal, dan

adalah pendekatan terhadap vektor eigen domi-

nan 1 1 dengan mengambil

1 dalam persamaan 3.2.1.

D. Laju Konvergensi Hasil Bagi Rayleigh Jika A adalah matriks simetrik yang nilai-nilai eigennya yang berbeda dapat disusun sebagai berikut : | |

| |

| |

|

|,


maka laju hasil bagi Rayleigh konvergen ke nilai eigen dominan tung pada nilai perbandingan

|

|

|

|

bergan-

, yaitu konvergensi tersebut lambat bila per-

bandingan itu mendekati 1 dan cepat bila perbandingan itu bernilai besar. Dengan kata lain, makin besar nilai perbandingan tersebut, makin cepat konvergensinya.

Contoh 3.4.1 Akan dibandingkan laju konvergensi Hasil Bagi Rayleigh pada matriks 3 2 2 3 2 2

dengan

nilai

2 dengan nilai eigen 5

Perbandingan

|

|

|

|

matriks B adalah

5

eigen

6 dan

pada matriks A adalah

1

dan

dan

matriks

1. 5, dan perbandingan

|

|

|

|

pada

6. Maka laju konvergensi pada matriks B berjalan lebih

cepat dibandingkan laju konvergensi pada matriks A.

E. Prosedur Penghentian Iterasi Jika λ adalah nilai eksak dari nilai eigen dominan, dan

adalah

hasil pendekatan metode kuasa pada iterasi ke-k, maka (3.5.1) disebut galat relatif dalam

. Jika nilai tersebut dinyatakan dalam

prosentase, maka disebut galat prosentase dalam

. Dalam aplikasi,

biasanya ditentukan galat relatif E yang dapat diterima terhadap nilai eigen


dominan, dan tujuannya adalah untuk menghentikan langkah-langkah iterasi setelah galat relatif dalam pendekatan terhadap nilai eigen kurang dari E. Namun,

terdapat

masalah

dalam

menghitung

galat

relatif

dengan

menggunakan persamaan 3.5.1, karena nilai eigen λ tidak diketahui. Untuk menghindari masalah ini, biasanya λ diestimasi dengan λk dan menghentikan iterasi ketika (3.5.2) 2. Ruas kiri ketaksamaan 3.5.2 disebut galat relatif estimasi

di mana

, dan bentuk prosentasenya disebut galat prosentase estimasi

dalam dalam

.

Contoh 3.5.1 Akan ditentukan nilai terkecil dari k pada Contoh 3.3.1 sedemikian sehingga galat prosentase estimasi dalam Pendekatan

Jadi

:

.

:

.

:

.

:

.

kurang dari 0.1% Galat Relatif Galat Prosentase

.

0.02953

2.953%

.

0.00123

0.123%

.

0.00005

0.005%

.

0.00000

0%

.

.

.

.

4.99999 adalah pendekaan pertama yang galat prosentase

estimasinya kurang dari 0.1%.


F. Aplikasi Metode Kuasa pada Mesin Pencari Internet Metode kuasa baru-baru ini telah digunakan untuk mengembangkan sebuah algoritma pencarian jenis baru yang didasarkan tidak pada isi halaman tetapi pada hipertaut (hyperlink) antara halaman-halaman. Algoritma itu, yang disebut algoritma PageRank, digunakan dalam mesin pencari Google dan dikembangkan pada tahun 1996 oleh Larry Page dan Sergey Brin di Universitas Stanford. Ide dasar di belakang metode tersebut adalah mengonstruksikan matriks-matriks yang sesuai yang menggambarkan struktur perujukan halaman-halaman yang sesuai dengan pencarian, dan kemudian menggunakan vektor eigen dominan matriks-matriks itu untuk menyusun daftar halaman-halaman tersebut dengan urutan menurun sesuai dengan kriteria terntentu. Cara kerja mesin pencari Google adalah sebagai berikut : 1. Bila pengguna meminta Google untuk mencari suatu kata atau frasa, langkah pertama adalah menggunakan mesin pencari standar berbasis teks untuk menemukan himpunan awal S0 dari situs-situs yang relevan, biasanya beberapa ratus atau lebih. 2. Karena kata-kata dapat memiliki beberapa makna, himpunan S0 biasanya juga memuat situs-situs yang tidak relevan, dan karena kata-kata dapat memiliki sinonim, himpunan S0 mungkin tidak memuat situs-situs penting yang menggunakan terminologi yang berbeda untuk kata-kata yang dicari. Oleh karena itu, Google kemudian mencari situs-situs yang merujuk ke situs-situs dalam S0 dan memperluas himpunan S0 menjadi himpunan S


yang lebih besar yang berisi situs-situs itu. Pengandaian yang melandasinya adalah bahwa himpunan S akan memuat situs-situs yang paling penting yang terkait dengan kata-kata yang dicari. Himpunan ini disebut himpunan pencarian. 3. Karena himpunan pencarian dapat memuat ribuan situs, tugas utama mesin pencari adalah mengurutkan situs-situs tersebut berdasarkan relevansinya dengan kata-kata yang dicari. Dalam bagian ini dari pencarian tersebut metode kuasa dan algoritma PageRank memainkan peranan. Untuk

menjelaskan

algoritma

PageRank,

misalnya

himpunan

pencarian S memuat n situs. Didefinisikan matriks damping dari S, yaitu matriks

di mana

1 jika situs i merujuk situs j dan

0

jika situs i tidak merujuk situs j. Dengan pengandaian bahwa tidak ada situs yang merujuk dirinya sendiri, maka entri diagonal dari A adalah nol.

Contoh 3.6.1 Matriks A di bawah ini adalah matriks damping dari himpunan pencarian S yang memuat empat situs internet : Situs yang dirujuk 1 2 3 4 0 0 1 1 1 0 0 0 1 0 0 1 1 1 1 0

1 2 Situs yang merujuk 3 4

(3.6.1)

1 berarti situs 1 merujuk situs 3 dan situs 4. Entri

1

berarti situs 2 merujuk situs 1, dan seterusnya. Secara umum, entri

1

Entri


berarti situs i merujuk situs j, dan entri

0 berarti situs i tidak merujuk

situs j. Ada dua peran dasar yang dapat dimainkan oleh suatu situs dalam proses pencarian, yaitu : 1. Situs tersebut memainkan peranan sebagai hub, artinya situs tersebut merujuk banyak situs lainnya. 2. Situs tersebut memainkan peranan sebagai otoritas, artinya situs tersebut dirujuk oleh banyak situs lainnya. Suatu situs biasanya berperan sebagai hub maupun sebagai otoritas, yang berarti bahwa situs tersebut merujuk maupun dirujuk. Pada umumnya, jika A adalah matriks damping dari himpunan n buah situs internet, maka jumlahan elemen-elemen pada kolom dari A merupakan ukuran aspek otoritas dari situs-situs itu dan jumlahan elemen-elemen pada baris dari A merupakan ukuran aspek hub dari situs-situs itu. Sebagai contoh, jumlahan elemen-elemen pada kolom dari matriks A pada Contoh 3.6.1 adalah 3, 1, 2, dan 2, yang berarti bahwa situs 1 dirujuk oleh tiga situs lainnya, situs 2 dirujuk oleh 1 situs lain, dan seterusnya. Begitu juga jumlahan elemen-elemen pada baris dari A adalah 2, 1, 2, dan 3, yang berarti bahwa situs 1 merujuk dua situs lain, situs 2 merujuk satu situs lain, dan seterusnya. Jika A adalah suatu matriks damping, maka vektor h0, yaitu vektor jumlahan elemen-elemen baris dari matriks A, disebut vektor hub awal dari matriks A, dan vektor a0, yaitu vektor jumlahan elemen-elemen kolom dari matriks A, disebut vektor otoritas awal dari matriks A. Dengan demikian, a0


dapat juga dipandang sebagai vektor jumlahan elemen-elemen baris dari matriks AT, yang ternyata dapat mempermudah dalam melakukan penghitungan. Entri-entri dalam vektor hub disebut bobot hub, dan entri-entri dalam vektor otoritas disebut bobot otoritas.

Contoh 3.6.2 Pada Contoh 3.6.1, vektor hub awal dari matriks damping A adalah jumlahan elemen-elemen baris dari A, yaitu 2 1 2 3

Situs 1 Situs 2 Situs 3 Situs 4

dan vektor otoritas awal dari matriks damping A adalah jumlahan elemenelemen baris dari AT (atau elemen-elemen kolom dari A), yaitu 3 1 2 2


Contoh 3.6.2 menunjukkan bahwa situs 4 adalah hub terbesar, dan situs 1 adalah otoritas terbesar. Namun, penghitungan tersebut tidak menjelaskan semuanya. Misalnya, tampaknya masuk akal bahwa jika situs 1 adalah otoritas terbesar, maka bobot lebih harus diberikan pada hub-hub yang merujuk situs tersebut, dan jika situs 4 adalah hub terbesar, maka bobot lebih harus diberikan pada situs-situs yang dirujuk oleh situs tersebut. Jadi, ada interaksi antara hub dan otoritas yang perlu diperhitungkan dalam proses pencarian itu. Oleh karena itu, setelah Google menghitung vektor otoritas


awal a0, informasi dalam vektor tersebut digunakannya untuk menyusun vektor-vektor hub dan otoritas baru h1 dan a1 dengan menggunakan rumus dan

(3.6.4)

Pembilang dalam rumus tersebut melakukan pembobotan, dan normalisasi berfungsi untuk mengontrol ukuran entri-entri. Untuk memahami bagaimana pembilang itu melakukan pembobotan, perkalian Aa0 dipandang sebagai kombinasi linear dari vektor-vektor kolom A dengan koefisienkoefisien dari a0. Misalnya, dengan matriks damping dalam Contoh 3.6.1, dan vektor otoritas yang dihitung dalam Contoh 3.6.2 didapatkan

A

Situs yang dirujuk 1 2 3 4 0 0 1 1 3 1 0 0 0 1 1 0 0 1 2 1 1 1 0 2

0 3 1 1 1

0 1 0 0 1

1 2 0 0 1

1 2 0 1 0

4 3 5 6


Dengan demikian masing-masing situs yang dirujuk terbobot oleh entri-entri dalam vektor a0. Untuk mengontrol ukuran entri-entri, Google menormalisir Aa0 untuk menghasilkan vektor hub yang baru:

√

4 3 5 6

0.43133 0.32350 0.53916 0.64700


Vektor hub h1 yang baru sekarang dapat digunakan untuk memperbarui vektor otoritas dengan menggunakan rumus 3.6.4. Perkalian A

melakukan pembobotan, dan normalisasi mengontrol ukuran:


Situs yang dirujuk 1 2 3 4 0 1 1 1 0.43133 0 0 0 1 0.32350 1 0 0 1 0.53916 1 0 1 0 0.64700 0 0.43133 0 1 1 1.50966 0.64700 1.07833 0.97049

1 0.32350 0 0 0

1 0.64700 1 1 0


0.68889 0.29524 0.49207 0.44286

1.50966 0.64700 1.07833 0.97049

.

0.53916

1 0 0 1


Setelah vektor-vektor hub h1 dan otoritas a1 yang baru diperoleh, mesin Google mengulangi proses itu dan menghitung barisan vektor-vektor hub dan otoritas yang saling terkait: ,

,

,

,

,

,

,

,

,

,

(3.6.5)

,

(3.6.6)

Masing-masing barisan sebenarnya adalah barisan kuasa. Misalnya, ekspresi untuk hk disubstitusikan ke dalam ekspresi untuk ak, maka akan diperoleh


yang berarti bahwa barisan 3.6.6 dapat ditulis sebagai: ,

,

,

,

,

,

(3.6.7)

Demikian pula, barisan 3.6.5 dapat ditulis sebagai: ,

,

,

,

,

(3.6.8)

Teorema 3.1.1 dapat diaplikasikan untuk matriks-matriks simetrik dan

, sehingga barisan kuasa 3.6.7 dan 3.6.8 konvergen ke vektor

eigen dominan satuan dari

dan

berturut-turut. Entri-entri dalam vek-

tor-vektor eigen tersebut adalah bobot otoritas dan bobot hub yang digunakan Google untuk menentukan peringkat situs-situs yang dicari dalam urutan kepentingannya sebagai otoritas dan hub.

Contoh 3.6.3 Misalnya mesin pencari Google menghasilkan himpunan pencarian yang memuat 10 situs internet dan matriks damping dari himpunan tersebut adalah 1 2 3 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 1 0 0 0 0

0 0 0 0 0 1 0 0 0 0

Situs yang dirujuk 4 5 6 7 8 9 10 0 0 0 0 0 1 0 0 0 0

1 1 1 0 0 1 0 1 0 0

0 0 0 1 0 0 0 0 1 1

0 0 0 1 0 0 0 0 0 0

1 0 0 0 1 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 1 1 0 0 0

1 2 3 4 5 6 7 8 9 10

Situs yang merujuk


Algoritma PageRank akan digunakan untuk menentukan peringkat situs-situs tersebut sebagai otoritas dalam urutan turun. Sebagai a0 diambil vektor otoritas awal yang telah ternormalisasi: 0 0.27217 0.13608 0.13608 0.68041 0.40825 0.13608 0.40825 0 0.27217

0 2 1 1 1 5 √54 3 1 3 0 2 Selanjutnya 0 0 0 0 0 0 0 0 0 0

0 2 1 1 2 0 0 2 0 1

0 1 1 1 1 0 0 1 0 1

0 1 1 1 1 0 0 1 0 1

0 2 1 1 5 0 0 2 0 1

0 0 0 1 0 3 1 0 0 0

0 0 0 0 0 1 1 0 0 0

0 2 1 1 2 0 0 3 0 1

0 0 0 0 0 0 0 0 0 0

0 1 1 1 1 0 0 1 0 2

0 0.27217 0.13608 0.13608 0.68041 0.40825 0.13608 0.40825 0 0.27217

0 3.26599 1.90516 1.90516 5.30723 1.36083 0.54433 3.67423 0 0.27732

dan 0 3.26599 1.90516 1.90516 1 5.30723 8.15362 1.36083 0.54433 3.67423 0 0.27732

0 0.40056 0.23366 0.23366 0.65090 0.16690 0.06676 0.45063 0 0.26704

Dilanjutkan dengan cara ini akan menghasilkan barisan vektor otoritas sebagai berikut:


,

,

0 1.27127 0.13608 0.13608 0.68041 0.40825 0.13608 0.40825 0 0.27217

0 0.40056 0.23366 0.23366 0.65090 0.16690 0.06676 0.45063 0 0.26704

, 0 0.41973 0.25309 0.25309 0.62665 0.00889 0.00368 0.47137 0 0.28416

, 0 0.41652 0.24917 0.24917 0.63407 0.06322 0.02603 0.46722 0 0.27892

,

0 0.41918 0.25233 0.25233 0.62836 0.02372 0.00981 0.47050 0 0.28300

, 0 0.41990 0.25337 0.25337 0.62597 0.00007 0.00003 0.47165 0 0.28460

, 0 0.41990 0.25337 0.25337 0.62597 0.00002 0.00001 0.47165 0 0.28460

Situs 1 Situs 2 Situs 3 Situs 4 Situs 5 Situs 6 Situs 7 Situs 8 Situs 9 Situs10

Perbedaan kecil antara a9 dan a10 memperlihatkan bahwa iterasi vektor otoritas itu telah stabil di dekat vektor eigen dominan dari matriks ATA. Dari entrientri dalam vektor otoritas a10 dapat disimpulkan bahwa situs 1, 6, 7, dan 9 mungkin tidak relevan sebagai situs otoritas dalam pencarian itu dan situssitus lainnya sebagai otoritas harus dicari dengan urutan sebagai berikut: situs 5, 8, 2, 10, 3 dan 4 (situs 3 dan 4 sama peringkatnya).


BAB IV PENUTUP

Internet banyak digunakan sekarang ini karena dapat memberi informasi penting dalam waktu singkat dan tanpa mengenal jarak dengan menggunakan mesin pencari yang memberikan informasi situs-situs yang dibutuhkan para pengguna. Mesin pencari Google menggunakan algoritma PageRank dengan mengonstruksikan matriks yang menggambarkan struktur perujukan halamanhalaman yang sesuai dengan pencarian, dan kemudian menggunakan vektor eigen dominan matriks itu untuk menyusun daftar halaman-halaman tersebut dengan urutan kepentingannya sesuai dengan kriteria tertentu. Teori yang melandasi cara kerja mesin pencari internet itu adalah Metode Kuasa. Pada mesin pencari internet, metode kuasa tersebut dilaksanakan dengan iterasi numerik untuk menghasilkan barisan vektor yang konvergen ke vektor eigen dominan dengan menggunakan metode perskalaan Euclides atau metode perskalaan entri maksimum. Dengan metode perskalaan Euclides, barisan vektorvektor tersebut adalah ,

,

,

,

,

yang konvergen ke vektor eigen dominan satuan dari matriks A, dan barisan ·

,

·

,

·

,

,

·

,

yang konvergen ke nilai eigen dominan dari matriks A. Iterasi tersebut dihentikan ketika galat relatif dalam pendekatan terhadap nilai eigen kurang dari galat relatif E yang ditentukan.


61

Pada aplikasinya, dengan Metode Kuasa dikembangkan suatu algoritma pencarian yang disebut algoritma PageRank yang digunakan dalam mesin pencari Google. Ide dasar di belakang algoritma tersebut adalah mengonstruksikan matriks yang menggambarkan struktur perujukan halaman-halaman yang sesuai dengan pencarian, dan kemudian menggunakan vektor eigen dominan dari matriks itu untuk menyusun daftar situs-situs yang dicari dengan urutan berdasarkan kriteria tertentu. Karena ada interaksi antara situs hub (merujuk) dan situs otoritas (dirujuk), Google menentukan vektor otoritas awal a0 dan vektor hub awal h0 untuk menyusun vektor-vektor hub dan otoritas baru h1 dan a1 dengan menggunakan rumus dan Kemudian Google mengulangi proses itu dan menghitung vektor-vektor hub dan otoritas yang saling terkait : , ,

, ,

,

,

,

, ,

,

,

Masing-masing barisan tersebut adalah barisan kuasa yang konvergen ke vektor eigen dominan matriks simetrik

dan

.

Urutan situs-situs hasil pencarian tersebut tercermin dalam entri-entri vektor-vektor eigen. Entri-entri dalam vektor-vektor eigen tersebut adalah bobot otoritas dan bobot hub yang digunakan Google untuk menentukan peringkat situssitus yang dicari dalam urutan kepentingannya sebagai otoritas dan hub. Peringkat


62

situs-situs ini ditentukan dengan urutan turun, yaitu dari entri yang bernilai paling besar ke entri yang bernilai paling kecil.


DAFTAR PUSTAKA

Ackleh, Azmy, et al. (2010). Classical and Modern Numerical Analysis: Theory, Methods and Practice. Boca Raton: CRC. Anton, Howard and R. C. Busby. (2003). Contemporary Linear Algebra. New York: John Wiley & Sons. Inc. Anton, Howard dan Chris Rorres. (2005). Aljabar Linear Elementer. Jakarta: Erlangga. Bradie, Brian. (2006). A Friendly to Numerical Analysis. Upper Saddle River: Pearson Education. Budhi, Wono Setya. (1995). Aljabar Linear. Jakarta: PT. Gramedia Pustaka Utama. Conte, S. D., dan Carl de Boor. (1980). Dasar-dasar Analisis Numerik: Suatu Pendekatan Algoritma. Jakarta: Erlangga. Cullen, Charles G. (1993). Aljabar Linear dan Penerapannya. Jakarta: PT. Gramedia Pustaka Utama. Hoffman, Joe D. (1993). Numerical Methods for Engineers and Scientist. New York: McGraw-Hill, Inc. Langville, Amy N. and Carl D. Meyer. (2006). Google’s PageRank and Beyond: The Science of Search Engine Rankings. Princeton: Princeton University Press.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Recommend Documents