METODE KACZMARZ UNTUK MENYELESAIKAN SISTEM PERSAMAAN LINEAR RUHIYAT

METODE KACZMARZ UNTUK MENYELESAIKAN SISTEM PERSAMAAN LINEAR

RUHIYAT

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2011

ABSTRAK RUHIYAT. Metode Kaczmarz untuk Menyelesaikan Sistem Persamaan Linear. Dibimbing oleh SRI NURDIATI dan TEDUH WULANDARI. Sistem persamaan linear (SPL) banyak terlibat dalam masalah pada bidang sains dan teknik. Terdapat banyak metode untuk menyelesaikan SPL, baik secara analitik maupun numerik. Metode Kaczmarz merupakan salah satu metode iteratif untuk menyelesaikan SPL. Proyeksi ortogonal digunakan dalam metode ini. Barisan penyelesaian hampiran yang dibangun oleh algoritme untuk metode ini konvergen untuk sebarang penyelesaian hampiran awal. Bukti kekonvergenan diberikan. Apabila SPL konsisten, barisan penyelesaian hampiran konvergen ke penyelesaian eksaknya. Hal ini menunjukkan bahwa metode Kaczmarz merupakan suatu metode yang baik. Implementasi metode ini dilakukan menggunakan MATLAB R2008b. Beberapa SPL dibangkitkan, kemudian diselesaikan secara numerik melalui program yang telah dibuat. Hasilnya menunjukkan bahwa semakin banyak iterasi yang dilakukan dalam menghampiri penyelesaian, semakin kecil norm sisaan yang diperoleh. Kata kunci: sistem persamaan linear, metode Kaczmarz, proyeksi ortogonal, penyelesaian hampiran, konvergen.

ABSTRACT RUHIYAT. Kaczmarz Method for Solving System of Linear Equations. Under supervision of SRI NURDIATI and TEDUH WULANDARI. A system of linear equations is often involved in science and engineering problems. There are many methods available for solving system of linear equations, both analytically and numerically. Kaczmarz method is one of iterative methods for solving such system. Orthogonal projections are used in this method. The sequence of approximate solutions generated by algorithm for this method is convergent for an arbitrary initial solution. A proof of the convergence is given. If the system of linear equations is consistent, then the sequence of approximate solutions converges to the exact solution. This shows that Kaczmarz method is a good method. Implementation of this method is done using MATLAB R2008b. Some systems of linear equations are generated, and then solved numerically using the program. The results show that the more iteration used in the solution approximation, the smaller norm of residual obtained. Keywords: system of linear equations, Kaczmarz method, orthogonal projection, approximate solution, convergent.

METODE KACZMARZ UNTUK MENYELESAIKAN SISTEM PERSAMAAN LINEAR

RUHIYAT

Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2011

Judul Skripsi : Metode Kaczmarz untuk Menyelesaikan Sistem Persamaan Linear Nama : Ruhiyat NIM : G54070005

Disetujui Pembimbing I

Pembimbing II

Dr. Ir. Sri Nurdiati, M.Sc NIP. 19601126 198601 2 001

Teduh Wulandari Mas’oed, M.Si NIP. 19740915 199903 2 001

Diketahui

Ketua Departemen Matematika

Dr. Berlian Setiawaty, MS NIP. 19650505 198903 2 004

Tanggal Lulus : ………………………………

PRAKATA Puji dan syukur penulis panjatkan kepada Allah SWT atas segala karunia-Nya sehingga karya ilmiah ini berhasil diselesaikan. Judul karya ilmiah ini adalah Metode Kaczmarz untuk Menyelesaikan Sistem Persamaan Linear. Terima kasih penulis ucapkan kepada Dr. Ir. Sri Nurdiati, M.Sc selaku dosen pembimbing I dan Teduh Wulandari Mas’oed, M.Si selaku dosen pembimbing II atas semua ilmu, kesabaran, motivasi, dan bantuannya selama penulisan skripsi ini. Terima kasih juga penulis ucapkan kepada Ir. Ngakan Komang Kutha Ardana, M.Sc selaku dosen penguji yang telah banyak memberi saran. Di samping itu, penghargaan penulis sampaikan kepada Drs. Agah Drajat Garnadi, Grad Dipl Sc dan Mochamad Tito Julianto, S.Si, M.Kom yang telah membantu dalam penyusunan karya ilmiah ini. Ungkapan terima kasih juga disampaikan kepada orang tua dan keluarga atas segala doa, dukungan, kesabaran, kepercayaan, dan kasih sayangnya. Penulis juga ingin mengucapkan terima kasih kepada seluruh dosen, staf pegawai, dan teman-teman di Institut Pertanian Bogor, khususnya di Departemen Matematika. Semoga karya ilmiah ini dapat bermanfaat bagi dunia ilmu pengetahuan khususnya matematika dan menjadi inspirasi bagi penelitian-penelitian selanjutnya.

Bogor, Maret 2011

Ruhiyat

RIWAYAT HIDUP Penulis dilahirkan di Bogor pada tanggal 3 Maret 1989 dari bapak Kasmin dan ibu Jumi. Penulis merupakan putra kedua dari tiga bersaudara. Tahun 2007 penulis lulus dari SMA Negeri 1 Cibungbulang dan pada tahun yang sama diterima sebagai mahasiswa IPB melalui jalur Undangan Seleksi Masuk IPB (USMI). Penulis memilih mayor Matematika minor Statistika Terapan, Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis menjadi asisten mata kuliah Kalkulus II (S1), Pengantar Metode Komputasi (S1), dan Metode Komputasi (S2) pada semester ganjil tahun akademik 20092010, asisten mata kuliah Persamaan Diferensial Biasa (S1) pada semester genap tahun akademik 2009-2010, serta asisten mata kuliah Pemodelan Matematika (S1) pada semester genap tahun akademik 2010-2011. Pada tahun 2010 penulis meraih medali perunggu (juara 3) pada kegiatan Olimpiade Nasional Matematika dan Ilmu Pengetahuan Alam Perguruan Tinggi (ONMIPA PT) 2010 bidang Matematika yang diselenggarakan oleh DIKTI, mendapatkan dana untuk Program Kreativitas Mahasiswa bidang Penelitian (PKMP) dari DIKTI, serta menjadi mahasiswa berprestasi Departemen Matematika. Penulis mendapatkan beasiswa dari Persatuan Orang Tua Mahasiswa (POM) IPB pada semester genap tahun akademik 2007-2008 dan Tanoto Foundation pada semester ganjil tahun akademik 2008-2009 sampai semester genap tahun akademik 20102011. Penulis aktif di berbagai kegiatan kemahasiswaan. Penulis pernah memegang amanah sebagai Wakil Sekretaris Umum Badan Eksekutif Mahasiswa Tingkat Persiapan Bersama Institut Pertanian Bogor (Kabinet Oryza) dan Staf Departemen Pendidikan Politik dan Kajian Strategi Badan Eksekutif Mahasiswa Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor (Kabinet Ksatria Pembaharu).

DAFTAR ISI Halaman DAFTAR GAMBAR ................................................................................................................. viii DAFTAR LAMPIRAN .............................................................................................................. viii I

PENDAHULUAN ............................................................................................................. 1.1 Latar Belakang .......................................................................................................... 1.2 Tujuan ....................................................................................................................... 1.3 Ruang Lingkup ..........................................................................................................

1 1 1 1

II

TINJAUAN PUSTAKA .................................................................................................... 2.1 Sistem Persamaan Linear dan Matriks ...................................................................... 2.2 Ruang Vektor ............................................................................................................ 2.3 Transformasi Linear .................................................................................................. 2.4 Ortogonalitas ............................................................................................................. 2.5 Masalah Kuadrat Terkecil ......................................................................................... 2.6 Barisan dan Deret ......................................................................................................

2 2 3 3 3 5 5

III

METODE ........................................................................................................................... 3.1 Studi Pustaka ............................................................................................................. 3.2 Implementasi ............................................................................................................. 3.3 Pengujian dan Pengamatan ........................................................................................

6 6 6 6

IV

HASIL DAN PEMBAHASAN ......................................................................................... 4.1 Algoritme untuk Metode Kaczmarz .......................................................................... 4.2 Analisis Kekonvergenan ............................................................................................ 4.3 Hasil Komputasi ........................................................................................................

7 7 8 14

V

SIMPULAN DAN SARAN ............................................................................................... 5.1 Simpulan ................................................................................................................... 5.2 Saran ..........................................................................................................................

18 18 18

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

19

LAMPIRAN ...............................................................................................................................

20

vii

DAFTAR GAMBAR Halaman 1

Alur pembuktian kekonvergenan penyelesaian hampiran yang dihasilkan oleh metode Kaczmarz ..............................................................................................................

6

2

Ilustrasi proses proyeksi di ℝ2 ...........................................................................................

7

3

Pola sparsity dari matriks koefisien dari SPL ke-1 ............................................................

15

4


15

5


15

6

Hasil kekonvergenan untuk SPL ke-1 ................................................................................

16

7


16

8


16

DAFTAR LAMPIRAN Halaman 1

Pembuktian Teorema 2.4.15 (Rumus Proyeksi Ortogonal) ...............................................

21

2

Pembuktian Persamaan (6) ................................................................................................

22

3

Pembuktian Persamaan (9) ................................................................................................

23

4

Pembuktian Persamaan (10) ..............................................................................................

24

5


25

6


26

7

Program MATLAB dari algoritme untuk metode Kaczmarz .............................................

27

8

Program MATLAB untuk membangkitkan matriks koefisien dan vektor konstanta dari SPL ke-1 ............................................................................................................................

30


32


33

Norm sisaan dari penyelesaian hampiran atas ketiga SPL yang digunakan yang diperoleh pada iterasi ke-0 sampai iterasi ke-30 ................................................................

35

9 10 11

viii

I.

PENDAHULUAN

1.1. Latar Belakang Banyak masalah pada bidang sains dan teknik yang melibatkan sistem persamaan linear. Oleh karena itu, menyelesaikan sistem persamaan linear menjadi penting. Penyelesaian sistem persamaan linear menjadi lebih sulit seiring bertambah besarnya ukuran sistem persamaan linear. Hal ini tentu menyebabkan waktu yang dibutuhkan untuk menyelesaikannya akan semakin lama. Selain itu, terdapat sistem persamaan linear yang tidak mempunyai penyelesaian eksak atau mempunyai banyak penyelesaian. Apabila kebutuhan akan penyelesaian sistem persamaan linear seperti ini sangat penting, penyelesaian hampiran sangat diperlukan. Penyelesaian hampiran yang dipilih harus mempunyai tingkat kesalahan yang sekecil mungkin. Pemilihan penyelesaian hampiran ini dapat pula dipandang sebagai masalah kuadrat terkecil. Apabila matriks koefisien dari sistem persamaan linear adalah segi dan taksingular, diketahui dengan baik bahwa metode eliminasi Gauss akan memberikan penyelesaian yang akurat kecuali jika matriks koefisien tersebut berkondisi terlalu buruk. Kondisi ini ditandai dengan perubahan yang besar pada penyelesaian yang disebabkan oleh perubahan yang relatif kecil pada matriks koefisien. Namun, ketika matriks koefisiennya sparse (jarang) dan berorde besar, metode ini boleh jadi tidak lebih efisien daripada metode iteratif seperti metode Gauss-Seidel dan metode Jacobi. Metode-metode iteratif ini pun tidak selalu konvergen. Hal-hal demikian tentunya menjadi masalah tersendiri yang dapat menghambat penyelesaian masalah utama seorang ilmuwan ataupun teknisi. Oleh karena itu, diperlukan suatu metode yang tepat yang dapat menjawab semua tantangan ini. Suatu metode iteratif diperkenalkan oleh Kaczmarz (1937) dalam hasil karyanya yang berjudul “Angenäherte Auflösung von Systemen Linearer Gleichungen”. Metode ini disebut dengan metode Kaczmarz. Nama Kaczmarz digunakan untuk menghargai jasanya yang sangat besar yang membawa perubahan besar bagi perkembangan ilmu pengetahuan dan teknologi. Metode ini juga dikenal baik dengan nama teknik rekonstruksi aljabar. Metode ini mempunyai peranan penting terhadap perkembangan teknologi computed tomography yang sangat berguna bagi dunia

kedokteran. Masalah mendasar dari computed tomography adalah bagaimana membentuk gambar penampang melintang tubuh manusia dengan menggunakan data yang dikumpulkan dari sekumpulan berkas sinar X yang dilewatkan melalui suatu penampang melintang. Pembentukan suatu penampang melintang ini membutuhkan penyelesaian dari sistem persamaan linear dengan ukuran yang sangat besar. Tanabe (1971) kemudian menyelidiki metode Kaczmarz. Dia membuktikan bahwa metode Kaczmarz menghasilkan penyelesaian hampiran yang konvergen untuk setiap sistem persamaan linear yang baris-barisnya taknol. Hal ini memperlihatkan bahwa metode Kaczmarz merupakan metode yang baik. Implementasi metode Kaczmarz dilakukan menggunakan MATLAB. Alat ini dipilih karena ampuh untuk melakukan komputasi matriks. MATLAB juga merupakan alat yang standar yang digunakan oleh ilmuwan dan teknisi di seluruh dunia. 1.2. Tujuan Tujuan dari karya ilmiah ini adalah sebagai berikut: 1. Menjelaskan algoritme untuk metode Kaczmarz. 2. Menganalisis (mengonstruksi ulang bukti) kekonvergenan penyelesaian hampiran yang dihasilkan oleh metode Kaczmarz. 3. Mengimplementasikan algoritme untuk metode Kaczmarz dengan membuat program MATLAB, kemudian mengujinya dengan beberapa sistem persamaan linear yang matriks koefisien dan vektor konstantanya dibangkitkan, serta mengamati kekonvergenan penyelesaian hampiran yang dihasilkan melalui program tersebut. 1.3. Ruang Lingkup Entri-entri dari matriks koefisien dan vektor konstanta dari sistem persamaan linear yang dibahas pada karya ilmiah ini adalah bilangan-bilangan real. Banyaknya sistem persamaan linear yang akan digunakan untuk menguji program MATLAB yang telah dibuat dan mengamati kekonvergenan penyelesaian hampiran yang dihasilkan melalui program tersebut ada tiga buah. Ketiga sistem persamaan linear tersebut mempunyai ukuran yang sama.

II. TINJAUAN PUSTAKA 2.1. Sistem Persamaan Linear dan Matriks

Selain itu, SPL berukuran juga dapat ditulis dalam bentuk

tersebut

Definisi 2.1.1 (Persamaan Linear) Suatu persamaan linear dalam adalah persamaan dengan bentuk

dengan , , …, bilangan real dan variabel.

variabel

dengan matriks dan vektor kolom (masing-masing berturut-turut berorde dan 1) adalah

, dan adalah bilangan, , …, adalah

(Leon 1998) Persamaan linear tersebut disebut sebagai hiperbidang pada ruang Euclid berdimensi , . (Anton & Rorres 2005) Definisi 2.1.2 (Sistem Persamaan Linear) Suatu sistem persamaan linear (SPL) dari persamaan dalam variabel adalah suatu sistem berbentuk

,

.

Matriks disebut sebagai matriks koefisien, sedangkan vektor kolom disebut sebagai vektor konstanta. (Leon 1998) Definisi 2.1.3 (Kekonsistenan dari Suatu SPL)

dengan dan (1 , 1 ) adalah bilangan-bilangan real dan , , …, adalah variabel. SPL tersebut disebut sebagai SPL berukuran . Penyelesaian SPL berukuran adalah sebuah vektor kolom berorde 1, yaitu

Suatu SPL dikatakan konsisten jika mempunyai paling sedikit satu penyelesaian, sedangkan suatu SPL yang tidak mempunyai penyelesaian dikatakan takkonsisten. (Leon 1998) Definisi 2.1.4 (Matriks Identitas) Matriks identitas adalah matriks yang berorde , dengan 1, 0,

, . (Leon 1998)

yang memenuhi semua persamaan linear dalam sistem. Vektor yang demikian disebut sebagai vektor penyelesaian. (Leon 1998) SPL berukuran tersebut dapat ditulis dalam bentuk ,

1, 2, … ,

dengan vektor-vektor kolom dan (masing-masing berorde 1) adalah ,

,

1, 2, … ,

.

(Anton & Rorres 2005)

Definisi 2.1.5 (Invers dari Suatu Matriks) Suatu matriks yang berorde dikatakan taksingular jika terdapat matriks sehingga . Matriks dikatakan invers multiplikatif dari matriks . Invers multiplikatif dari matriks taksingular secara sederhana disebut juga sebagai invers dari . matriks dan dinotasikan dengan (Leon 1998) Definisi 2.1.6 Matriks)

(Transpos

dari

Suatu

Transpos dari suatu matriks yang berorde adalah matriks yang berorde yang didefinisikan oleh

3

untuk setiap dan dinotasikan oleh .

. Transpos dari (Leon 1998)

dikatakan sama (dinotasikan dengan jika

untuk setiap

)

. (Deskins 1964)

2.2. Ruang Vektor Ruang Vektor Euclid

Definisi 2.3.3 (Kernel Transformasi Matriks)

dari

dapat dipandang Ruang vektor Euclid sebagai himpunan semua vektor yang berorde 1 dengan entri-entrinya berupa bilangan real. (Leon 1998)

Misalkan adalah suatu transformasi ke . Kernel (ruang nol) matriks dari dari transformasi matriks dilambangkan dengan Ker dan didefinisikan oleh |

Ker

.

Ruang Vektor

(Leon 1998)

dapat dipandang Ruang vektor sebagai himpunan semua matriks yang berorde dengan entri-entrinya berupa bilangan real. (Leon 1998) Definisi 2.2.1 (Ruang Bagian dari

)

Jika adalah suatu himpunan bagian dan takkosong dari ruang vektor memenuhi 1. 2.

,

, ,

maka

Suatu

,

dan ,

dikatakan suatu ruang bagian dari . (Leon 1998)

Definisi 2.3.4 (Image Transformasi Matriks)

dari

Suatu

Misalkan adalah suatu transformasi ke . Image dari matriks dari transformasi matriks dilambangkan dengan Im dan didefinisikan oleh |

Im

. (Leon 1998)

2.4. Ortogonalitas )

Definisi 2.4.1 (Hasil Kali Skalar di Misalkan ,

dengan

2.3. Transformasi Linear ,

Definisi 2.3.1 (Transformasi Linear dari ) ke Jika adalah suatu matriks yang berorde dari , maka suatu transformasi linear ke dapat dinyatakan sebagai

,

maka hasil kali skalar dari

dan

adalah . (Leon 1998)

. Oleh karena itu, setiap untuk setiap matriks yang berorde dapat dipandang sebagai transformasi linear dari . ke (Leon 1998) juga dapat disebut Transformasi linear dengan transformasi matriks . (Anton & Rorres 2005)

Definisi 2.4.2 (Norm dari Suatu Vektor di ) Misalkan

dengan ,

maka norm dari vektor Definisi 2.3.2 (Kesamaan Transformasi Matriks) Misalkan dan adalah transformasike . dan transformasi matriks dari

di

adalah . (Leon 1998)

4

Definisi 2.4.3 (Norm dari Suatu Matriks di ) Norm dari suatu matriks yang berorde dapat didefinisikan sebagai ,

max

. (Leon 1998)

|

1.

(Leon 1998) Lema 2.4.10 Jika adalah suatu matriks berorde , maka

. Bukti dapat dilihat di Leon (1998).

.

)

Definisi 2.4.5 (Proyeksi vektor di dan Misalkan , vektor pada adalah vektor

Bukti dapat dilihat di Leon (1998).

Jika dan adalah ruang-ruang bagian dan setiap dapat ditulis secara dari unik sebagai jumlah dengan dan dikatakan jumlah langsung , maka dari dan , serta dinotasikan dengan

,

,

.

Definisi 2.4.11 (Jumlah Langsung)

,

dan 2.

Im

Ker

,

.

disebut komplemen ortogonal

Himpunan dari .

Lema 2.4.4 Norm vektor pada Definisi 2.4.2 dan norm matriks pada Definisi 2.4.3 memenuhi

0,

. Proyeksi

(Leon 1998) Lema 2.4.12

. (Leon 1998) )

Definisi 2.4.6 (Ortogonalitas di Vektor-vektor 0. jika

dan

Jika maka

,

adalah suatu ruang bagian dari .


disebut ortogonal )

Definisi 2.4.13 (Proyeksi Ortogonal di (Leon 1998)

Definisi 2.4.7 (Ruang Bagian Ortogonal)

Suatu proyeksi ortogonal di suatu transformasi matriks dari sedemikian sehingga

disebut Dua ruang bagian dan dari ortogonal jika untuk setiap dan setiap 0. Jika dan ortogonal, maka , ditulis

adalah ke

. (Rynne & Youngson 2008) Definisi 2.4.14 (Proyeksi Ortogonal pada Ruang Bagian)

. (Leon 1998) Lema 2.4.8 Jika dan adalah dua ruang bagian dari yang ortogonal, maka .

.

Misalkan adalah ruang bagian dari Proyeksi ortogonal pada ruang bagian di yang memenuhi dinotasikan dengan ,

,

dan

.

(Rynne & Youngson 2008)


Teorema 2.4.15 Ortogonal)

Definisi 2.4.9 (Komplemen Ortogonal)

Misalkan suatu hiperbidang di dan misalkan mempunyai persamaan adalah sebarang titik di , maka proyeksi , dari terhadap hiperbidang ortogonal, tersebut dinyatakan dengan

. Misalkan adalah ruang bagian dari yang Himpunan semua vektor-vektor di ortogonal dengan setiap vektor di dinotasikan dengan , yaitu

(Rumus

Proyeksi

5

lim

.

.

(Rynne & Youngson 2008) (Anton & Rorres 2005) Bukti dapat dilihat pada Lampiran 1. 2.5. Masalah Kuadrat Terkecil Misalkan adalah SPL berukuran . Untuk setiap didefinisikan sisaan sebagai

yang ,

.

Lema 2.6.3 dan adalah barisanJika barisan di sedemikian sehingga berturutdan , yaitu turut konvergen ke lim

,

lim

,

dan

Norm sisaan diberikan oleh . Penyelesaian dari SPL dapat dihampiri dengan suatu vektor . Vektor seperti ini disebut dengan penyelesaian hampiran. Salah satu cara untuk mendapatkan penyelesaian hampiran adalah dengan mencari sehingga norm sisaan suatu vektor minimum, yakni minimum. Meminimumkan sama dengan . Masalah ini disebut meminimumkan dengan masalah kuadrat terkecil. Suatu vektor yang menyelesaikan masalah ini disebut dengan suatu penyelesaian kuadrat terkecil atas SPL . (Leon 1998) Selanjutnya, himpunan semua vektor penyelesaian kuadrat terkecil atas SPL dinotasikan dengan , .

di , yaitu

maka barisan konvergen ke lim

dan .

Bukti dapat dilihat di Rynne & Youngson (2008). Definisi 2.6.4 (Kekonvergenan ) Takhingga di Misalkan Untuk setiap

Deret

adalah barisan di , misalkan

adalah jumlah parsial ketersebut. Deret

.

dari barisan

2.6. Barisan dan Deret Definisi 2.6.1 (Barisan di

)

dikatakan konvergen jika

adalah suatu fungsi dari Barisan di . Misalkan adalah suatu ke dengan barisan di , Barisan

.

lim ada di

dan

biasa dilambangkan dengan lim

. (Rynne & Youngson 2008) Definisi 2.6.2 (Kekonvergenan Barisan di ) Misalkan Barisan jika 0,

adalah barisan di disebut konvergen ke sehingga

.

.

(Rynne & Youngson 2008) Teorema 2.6.5 (Deret Neumann di

) 1, maka

dengan Jika taksingular dan .

, untuk dan dinotasikan sebagai

Bukti dapat dilihat di Rynne & Youngson (2008).

III. METODE Karya ilmiah ini disusun melalui tiga tahap. Pertama, dilakukan studi pustaka mengenai metode Kaczmarz, kekonvergenan penyelesaian hampiran yang dihasilkan oleh metode Kaczmarz, serta konsep-konsep yang mendasarinya. Kedua, dilakukan implementasi algoritme untuk metode Kaczmarz dengan membuat program MATLAB secara sekuensial. Ketiga, dilakukan pengujian terhadap program MATLAB tersebut dan pengamatan terhadap kekonvergenan penyelesaian hampiran yang diperoleh melalui program MATLAB tersebut.

membutuhkan pernyataan (proposisi, lema, teorema, dan akibat) lain. Alur pembuktian disajikan pada Gambar 1 berikut. Proposisi 4.2.1 Proposisi 4.2.2 Lema 4.2.3 Akibat 4.2.4

Akibat 4.2.5

Teorema 4.2.6 Teorema 4.2.7

3.1. Studi Pustaka Teorema 4.2.8

Studi diawali dengan mengkaji metode Kaczmarz. Literatur utama yang digunakan dalam mengkajinya adalah buku Anton dan Rorres (2005) yang berjudul “Elementary Linear Algebra”. Konsep-konsep dasar yang diperlukan untuk memahami metode Kaczmarz adalah persamaan linear, sistem persamaan linear, transpos dari suatu matriks, hasil kali skalar dari dua vektor, norm dari suatu vektor, serta rumus proyeksi ortogonal. Studi dilanjutkan dengan mengkaji kekonvergenan penyelesaian hampiran yang diperoleh dari algoritme untuk metode Kaczmarz. Literatur utama yang digunakan adalah artikel Tanabe (1971) yang berjudul “Projection Method for Solving a Singular System of Linear Equation and Its Applications”. Selain konsep-konsep dasar yang telah disebutkan untuk memahami metode Kaczmaz, diperlukan beberapa konsep dasar tambahan pula untuk membuktikan kekonvergenan ini. Konsep-konsep tersebut adalah kekonsistenan dari suatu SPL, matriks identitas, invers dari suatu matriks, ruang vektor dan ruang bagian, transformasi matriks, kesamaan transformasi matriks, kernel dan image dari suatu transformasi matriks, norm dari suatu matriks, proyeksi vektor, ortogonalitas, ruang bagian ortogonal, komplemen ortogonal, jumlah langsung, proyeksi ortogonal pada ruang bagian, masalah kuadrat terkecil, kekonvergenan barisan vektor, kekonvergenan deret vektor takhingga, deret Neumann, serta beberapa lema dan teorema yang terkait. Pernyataan kekonvergenan penyelesaian hampiran yang dihasilkan oleh metode Kaczmarz ini disajikan dalam bentuk suatu teorema. Pembuktian teorema ini

Gambar 1 Alur pembuktian kekonvergenan penyelesaian hampiran yang dihasilkan oleh metode Kaczmarz. 3.2. Implementasi Implementasi metode Kaczmarz dilakukan menggunakan MATLAB versi R2008b yang terdapat di laboratorium komputer Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Algoritme untuk metode Kaczmarz dikonversi ke dalam bentuk program yang ditulis pada m-file. 3.3. Pengujian dan Pengamatan Pengujian dilakukan untuk menunjukkan bahwa program MATLAB yang telah dibuat dapat berjalan dengan benar. Pengamatan dilakukan bersamaan dengan pengujian. Hal yang diamati adalah kekonvergenan penyelesaian hampiran yang dihasilkan melalui program MATLAB yang telah dibuat. Kekonvergenan dilihat dari norm sisaan dari penyelesaian hampiran tersebut. Pengujian dan pengamatan dilakukan menggunakan tiga sistem persamaan linear yang matriks koefisien dan vektor konstantanya dibangkitkan dengan cara yang berbeda-beda. Pembangkitan ini dilakukan dengan menggunakan tiga program pembangkit matriks koefisien dan vektor konstanta dari suatu sistem persamaan linear yang terdapat pada “Regularization Tools: A MATLAB Package for Analysis and Solution of Discrete Ill-Posed Problems” karya Hansen (1994).

IV. HASIL DAN PEMBAHASAN 4.1. Algoritme untuk Metode Kaczmarz Metode Kaczmarz merupakan salah satu metode iteratif untuk menyelesaikan SPL berbentuk 𝐴𝐱 = 𝐛

(1)

dengan matriks koefisien 𝐴 berorde 𝑀 × 𝑁, vektor penyelesaian 𝐱 berorde 𝑁 × 1, dan vektor konstanta 𝐛 berorde 𝑀 × 1. Metode ini mencari suatu titik di dalam ℝ𝑁 yang relatif “dekat” dengan seluruh hiperbidang. Titik semacam ini akan menjadi sebuah penyelesaian hampiran atas SPL. Proses iterasi pada algoritme untuk metode Kaczmarz menghasilkan siklus proyeksiproyeksi ortogonal yang berurutan pada 𝑀 hiperbidang yang dimulai dengan sebarang titik awal di ℝ𝑁 . Sebelumnya, diperkenalkan terlebih dahulu notasi-notasi untuk iterasiiterasi yang berurutan ini. Dimisalkan 𝐱 𝑘𝑛 adalah titik yang terletak pada hiperbidang ke𝑘 yang dihasilkan saat iterasi ke-𝑛. Langkahlangkah atau algoritme dalam mendapatkan penyelesaian hampiran dengan metode Kaczmarz adalah sebagai berikut: 1) Pilihlah titik sebarang di ℝ𝑁 dan tandai dengan 𝐱 0 . 2) Untuk iterasi pertama, tetapkan 𝑛 = 1 dan 𝐱 01 = 𝐱 0 . 3) Untuk 𝑘 = 1,2, … , 𝑀, hitunglah 𝑛 𝐱 𝑘𝑛 = 𝐱 𝑘−1 +

𝑛 𝑏𝑘 − 𝐚𝑇𝑘 𝐱 𝑘−1 𝐚𝑘 . 𝐚𝑘 2

4) Tetapkan 𝐱 0𝑛+1 = 𝐱 𝑀𝑛 . 5) Naikkan banyaknya iterasi 𝑛 sebanyak satu dan kembalilah ke Langkah 3.

diproyeksikan pada hiperbidang ke-𝑘 (2 ≤ 𝑘 ≤ 𝑀) adalah titik yang merupakan hasil proyeksi pada hiperbidang ke- 𝑘 − 1 pada iterasi yang sama. Untuk iterasi ke-2 dan seterusnya, titik yang akan diproyeksikan pada hiperbidang pertama adalah titik yang merupakan hasil proyeksi pada hiperbidang terakhir atau hiperbidang ke-𝑀 pada iterasi sebelumnya, sedangkan titik yang akan diproyeksikan pada hiperbidang ke-𝑘 (2 ≤ 𝑘 ≤ 𝑀) adalah titik yang merupakan hasil proyeksi pada hiperbidang ke- 𝑘 − 1 pada iterasi yang sama. Penyelesaian hampiran atas SPL diperoleh dari titik yang merupakan hasil proyeksi pada hiperbidang terakhir pada iterasi yang diinginkan. Sebagai ilustrasi, proses proyeksi dalam mendapatkan penyelesaian hampiran atas SPL yang berukuran 2 × 2 berikut 𝑥1 + 𝑥2 = 2 1 𝑥 − 𝑥2 = −1 5 1 dengan metode Kaczmarz dapat dilihat pada Gambar 2. Penyelesaian hampiran awal yang dipilih adalah 𝑥10 𝑥20

=

2 . 5

Hiperbidang di ℝ2 ini berupa garis lurus. Penyelesaian hampiran yang diperoleh setelah dua iterasi terlihat semakin mendekati penyelesaian eksaknya. Dapat dilihat dengan mudah pula bahwa untuk iterasi-iterasi selanjutnya pun, penyelesaian hampiran yang diperoleh akan semakin mendekati penyelesaian eksaknya. 𝑥1 + 𝑥2 = 2

𝐱

0

𝐱 𝑘𝑛

Titik pada langkah 3 merupakan 𝑛 proyeksi ortogonal dari titik 𝐱 𝑘−1 pada 𝑇 hiperbidang 𝐚𝑘 𝐱 = 𝑏𝑘 berdasarkan Teorema 2.4.15. Algoritme ini menentukan proyeksiproyeksi ortogonal yang berurutan dari satu hiperbidang ke hiperbidang berikutnya, mulai dari hiperbidang pertama sampai hiperbidang terakhir (dalam satu iterasi). Proyeksi akan kembali pada hiperbidang pertama setelah proyeksi pada hiperbidang terakhir dilakukan (pada iterasi sebelumnya). Untuk iterasi ke-1, titik yang akan diproyeksikan pada hiperbidang pertama adalah titik yang merupakan penyelesaian hampiran awal, sedangkan titik yang akan

1 𝑥 − 𝑥2 = −1 5 1

Gambar 2 Ilustrasi proses proyeksi di ℝ2 .

8

Persamaan (3) dapat dibentuk menjadi 𝑏𝑖 (6) 𝑓𝑖 𝐱 = 𝑃𝑖 𝐱 + 𝐚 𝐚𝑖 2 𝑖 untuk 𝑖 = 1, 2, … , 𝑀

4.2. Analisis Kekonvergenan SPL pada Persamaan (1) dapat juga ditulis sebagai 𝐚𝑇𝑖 𝐱 = 𝑏𝑖 untuk 𝑖 = 1, 2, … , 𝑀

(2)

dengan 𝐚𝑖 adalah vektor kolom ke- 𝑖 dari matriks 𝐴𝑇 , 𝑏𝑖 adalah entri pada baris ke- 𝑖 dari vektor kolom 𝐛, dan diasumsikan bahwa untuk setiap 𝑖, 𝐚𝑖 > 0, dengan kata lain vektor-vektor baris dari matriks 𝐴 taknol. Kemudian, dimisalkan transformasi 𝑓𝑖 dari ℝ𝑁 ke ℝ𝑁 didefinisikan sebagai 𝑏𝑖 − 𝐚𝑇𝑖 𝐱 𝐚𝑖 𝐚𝑖 2 untuk 𝑖 = 1, 2, … , 𝑀

(3)

𝑓𝑖 𝐱 = 𝐱 +

dan transformasi 𝐹 didefinisikan sebagai

dari

ℝ𝑁

𝐹 𝐱; 𝐛 = 𝑓1 ∘ 𝑓2 ∘ ⋯ ∘ 𝑓𝑀 𝐱 = 𝑓1 𝑓2 ⋯ 𝑓𝑀 𝐱 ⋯

ke

ℝ𝑁

1 𝐚𝑖

𝐚𝑖 𝐚𝑇𝑖 .

(7)

2

𝑄𝑖−1 𝐚𝑖 ,

maka 𝑅𝐛 =

.

𝑖=1

Algoritme ini lebih sederhana daripada algoritme sebelumnya, walaupun pada dasarnya sama. Hal ini ditujukan agar lebih mudah dalam membuktikan kekonvergenan algoritme untuk metode Kaczmarz. Proyeksi ortogonal yang dilakukan pada algoritme ini berbeda dengan algoritme sebelumnya karena dimulai dari hiperbidang ke-𝑀 dan berakhir di hiperbidang pertama, sehingga barisan penyelesaian hampiran yang dibangun terletak pada hiperbidang 𝐚1𝑇 𝐱 = 𝑏1 (hiperbidang ke1). Hal ini tidak akan mengubah penyelesaian hampiran atas SPL yang didapatkan dengan membalikkan urutan hiperbidang. Selanjutnya, akan dibuktikan bahwa barisan penyelesaian hampiran yang dibangun dengan metode Kaczmarz ini konvergen. Sebelumnya, bentuk Persamaan (3) yang merupakan proyeksi ortogonal dari suatu titik ke suatu hiperbidang diubah terlebih dahulu. Selain itu, dibentuk pula persamaanpersamaan yang akan digunakan dalam membuktikan kekonvergenan barisan penyelesaian hampiran yang dibangun dengan metode Kaczmarz.

2

Bukti Persamaan (6) dapat dilihat pada Lampiran 2. Kemudian dimisalkan 𝑄𝑖 = 𝑃1 𝑃2 … 𝑃𝑖 (𝑖 = 1, 2, … , 𝑀), 𝑄0 = 𝐼, dan 𝑅 sebagai suatu matriks berorde 𝑁 × 𝑀 dengan vektor kolom ke-𝑖 dari 𝑅 adalah

𝑀

(5)

1 𝐚𝑖

𝑃𝑖 = 𝐼 −

(4)

Tanabe (1971) meringkas algoritme untuk metode Kaczmarz menjadi dua langkah utama. Pertama, penyelesaian hampiran awal dipilih sebarang dan dimisalkan sebagai 𝐱 0 . Kedua, barisan 𝐱 𝑛 ditentukan dari relasi rekurensi 𝐱 𝑛+1 = 𝐹 𝐱 𝑛 ; 𝐛 untuk 𝑛 = 0,1,2, …

dengan

𝑏𝑖 𝐚𝑖

2

𝑄𝑖−1 𝐚𝑖 .

(8)

Jadi, didapatkan 𝐹 𝐱; 𝐛 = 𝑄𝐱 + 𝑅𝐛,

(9)

dengan matriks 𝑄 = 𝑄𝑀 yang berorde 𝑁 × 𝑁 dan matriks 𝑅 yang berorde 𝑁 × 𝑀 hanya bergantung pada matriks 𝐴. Bukti Persamaan (9) dapat dilihat pada Lampiran 3. Notasi-notasi yang didefinisikan pada persamaan-persamaan tersebut akan digunakan pada proposisi, lema, akibat, dan teorema berikutnya. Pembuktian kekonvergenan barisan penyelesaian hampiran yang dibangun dengan metode Kaczmarz diawali dengan proposisi berikut. Proposisi 4.2.1 𝑄 + 𝑅𝐴 = 𝐼. Bukti: Persamaan 𝑄 + 𝑅𝐴 = 𝐼 ekivalen dengan 𝑅𝐴 = 𝐼 − 𝑄 = 𝐼 − 𝑄𝑀 . Karena vektor kolom ke-𝑖 dari 𝑅 dan vektor baris ke-𝑖 dari 𝐴 berturut-turut adalah 1 𝑇 2 𝑄𝑖−1 𝐚𝑖 dan 𝐚𝑖 , maka didapatkan 𝐚𝑖

𝑅𝐴 =

1 𝐚1

2

1

𝑄0 𝐚1 𝐚1𝑇 +

1 𝐚2

2

𝑄1 𝐚2 𝐚𝑇2 + ⋯

𝑄 𝐚 𝐚𝑇 𝐚𝑀 2 𝑀−1 𝑀 𝑀 1 1 = 𝑄0 𝐚1 𝐚1𝑇 + 𝑄1 2 𝐚1 𝐚2 1 +𝑄𝑀−1 𝐚 𝐚𝑇 𝐚𝑀 2 𝑀 𝑀 +

2

𝐚2 𝐚𝑇2 + ⋯

9

1 𝐚𝑖 2

(karena

merupakan skalar untuk setiap

𝑖 = 1,2, … , 𝑀). Karena 𝑄0 = 𝐼 dan berdasarkan Persamaan (7), maka diperoleh 𝑅𝐴 = 𝐼 − 𝑃1 + 𝑄1 𝐼 − 𝑃2 + ⋯ +𝑄𝑀−1 𝐼 − 𝑃𝑀 = 𝐼 − 𝑃1 + 𝑄1 − 𝑄1 𝑃2 + ⋯ + 𝑄𝑀−1 −𝑄𝑀−1 𝑃𝑀 . Karena 𝑄0 = 𝐼 definisi), maka

dan

𝑄𝑖−1 𝑃𝑖 = 𝑄𝑖

(dari

𝑅𝐴 = 𝐼 − 𝑄1 + 𝑄1 − 𝑄2 + ⋯ + 𝑄𝑀−1 − 𝑄𝑀 = 𝐼 − 𝑄𝑀 . Bukti lengkap. ∎

sebarang, maka 𝑃𝑖 𝐱 = 𝐱 untuk setiap 𝑖 = 1, 2, … , 𝑀, yaitu 𝑃1 𝐱 = 𝐱, 𝑃2 𝐱 = 𝐱, …, 𝑃𝑀 𝐱 = 𝐱. Oleh karena itu, diperoleh 𝐱 = 𝑃1 𝐱 = 𝑃1 𝑃2 𝐱 = ⋯ = 𝑃1 𝑃2 ⋯ 𝑃𝑀 𝐱 → 𝐱 = 𝑄𝑀 𝐱 → 𝐱 − 𝑄𝑀 𝐱 = 𝟎 → 𝐼 − 𝑄𝑀 𝐱 = 𝟎. Karena 𝐼 − 𝑄𝑀 = 𝑅𝐴 (berdasarkan Proposisi 4.2.1), maka 𝑅𝐴𝐱 = 𝟎 → 𝐴𝐱 = 𝟎, sehingga diperoleh 𝐱 ∈ Ker 𝐴 . Jadi, terbukti bahwa 𝑀

Bedasarkan Proposisi 4.2.1, diperoleh proposisi berikut.

𝐱 ∈ ℝ𝑁 |𝑃𝑖 𝐱 = 𝐱 ⊆ Ker 𝐴 . 𝑖=1

Bukti lengkap. ∎

Proposisi 4.2.2 𝑀 𝑁

Ker 𝐴 =

𝐱 ∈ ℝ |𝑃𝑖 𝐱 = 𝐱 .

Berdasarkan Lema 2.4.4 dan Proposisi 4.2.2, diperoleh lema berikut.

𝑖=1

Bukti: Pertama, akan dibuktikan bahwa 𝑀

𝐱 ∈ ℝ𝑁 |𝑃𝑖 𝐱 = 𝐱 .

Ker 𝐴 ⊆ 𝑖=1

Dimisalkan 𝐱 ∈ Ker 𝐴 sebarang, maka 𝐴𝐱 = 𝟎 atau dapat dinyatakan dengan 𝐚𝑇𝑖 𝐱 = 0 untuk setiap 𝑖 = 1, 2, … , 𝑀. Oleh karena itu, berdasarkan Persamaan (7) diperoleh 1 𝐚 𝐚𝑇 𝐱 𝐚𝑖 2 𝑖 𝑖 1 = 𝐱− 𝐚 𝐚𝑇 𝐱 𝐚𝑖 2 𝑖 𝑖 = 𝐱−𝟎=𝐱

𝑃𝑖 𝐱 = 𝐼 −

untuk setiap 𝑖 = 1, 2, … , 𝑀. Jadi, terbukti bahwa 𝑀

𝐱 ∈ ℝ𝑁 |𝑃𝑖 𝐱 = 𝐱 .

Ker 𝐴 ⊆ 𝑖=1

Kedua, akan dibuktikan bahwa

Lema 4.2.3 𝑄𝐱 = 𝐱 jika dan hanya jika 𝐱 ∈ Ker 𝐴 . Bukti: Pertama, akan dibuktikan bahwa jika 𝑄𝐱 = 𝐱 maka 𝐱 ∈ Ker 𝐴 . Hal ini sama dengan membuktikan kontrapositifnya, yakni jika 𝐱 ∉ Ker 𝐴 , maka 𝑄𝐱 ≠ 𝐱 . Dimisalkan 𝐱 ∈ ℝ𝑁 sebarang sedemikian sehingga 𝐱 ∉ Ker 𝐴 , maka berdasarkan Proposisi 4.2.2, terdapat suatu bilangan 𝑖 (1 ≤ 𝑖 ≤ 𝑀) sehingga 𝑃𝑖 𝐱 ≠ 𝐱. Dimisalkan bilangan terbesar dari semua bilangan tersebut adalah 𝑖0 , maka 𝑃𝑖 𝐱 = 𝐱 untuk setiap 𝑖 > 𝑖0 yaitu untuk 𝑖 = 𝑖0 + 1, … , 𝑀. Oleh karena itu, diperoleh 𝑃𝑖0 𝑃𝑖0 +1 … 𝑃𝑀 𝐱 = 𝑃𝑖0 𝐱 → 𝑃𝑖0 𝑃𝑖0 +1 … 𝑃𝑀 𝐱 = 𝑃𝑖0 𝐱 . Berdasarkan Persamaan (7), 𝑃𝑖0 𝐱 = 𝐼 − =𝐱−

𝑀

𝐱 ∈ ℝ𝑁 |𝑃𝑖 𝐱 = 𝐱 ⊆ Ker 𝐴 . 𝑖=1

Dimisalkan 𝑀

𝐱 ∈ ℝ𝑁 |𝑃𝑖 𝐱 = 𝐱

𝐱∈ 𝑖=1

=𝐱−

1 2

𝐚𝑖 0 1 𝐚𝑖 0 𝐚𝑇𝑖0 𝐱 𝐚𝑖 0

𝐚𝑖0 𝐚𝑇𝑖0 𝐱

2

𝐚𝑖0 𝐚𝑇𝑖0 𝐱

2

𝐚𝑖 0

(karena 𝐚𝑇𝑖0 𝐱 adalah skalar). Karena 𝑃𝑖0 𝐱 merupakan vektor 𝐱 dikurangi proyeksi vektor 𝐱 pada 𝐚𝑖0 (berdasarkan

10

Definisi 2.4.5) dan 𝑃𝑖0 𝐱 ≠ 𝐱, maka 𝑃𝑖0 𝐱 < 𝐱 . Berdasarkan Definisi 2.4.3, maka untuk setiap 𝑖 = 1, 2, … , 𝑀, 𝑃𝑖 = max

𝑃𝑖 𝐲 𝐲

𝐲 ∈ ℝ𝑁 , 𝐲 ≠ 𝟎 .

Karena 𝑃𝑖 𝐲 ≤ 𝐲 saat 𝐲 ∉ Ker 𝐴 dan 𝑃𝑖 𝐲 = 𝐲 saat 𝐲 ∈ Ker 𝐴 , maka 𝑃𝑖 = 1 untuk setiap 𝑖 = 1,2, … , 𝑀 (artinya, setiap 𝑃𝑖 mempunyai norm satuan). Oleh karena itu, untuk setiap 𝑖 = 1,2, … , 𝑀 𝑄𝑖 = 𝑃1 𝑃2 … 𝑃𝑖 ≤ 𝑃1 𝑃2 … 𝑃𝑖 =1 (berdasarkan bagian kedua dari Lema 2.4.4), sehingga diperoleh 𝑄𝑀 𝐱 = 𝑄𝑖0 −1 𝑃𝑖0 𝑃𝑖0 +1 … 𝑃𝑀 𝐱 ≤ 𝑄𝑖0 −1 𝑃𝑖0 𝑃𝑖0 +1 … 𝑃𝑀 𝐱 <1 𝐱 (berdasarkan bagian pertama dari Lema 2.4.4). Jadi, terbukti bahwa 𝑄𝐱 ≠ 𝐱 . Kedua, akan dibuktikan bahwa jika 𝐱 ∈ Ker 𝐴 maka 𝑄𝐱 = 𝐱 . Dimisalkan 𝐱 ∈ Ker 𝐴 sebarang, maka berdasarkan Proposisi 4.2.2, 𝑃𝑖 𝐱 = 𝐱 untuk setiap 𝑖 = 1,2, … , 𝑀. Oleh karena itu, diperoleh 𝑄𝐱 = 𝑃1 𝑃2 … 𝑃𝑀 𝐱 = 𝐱 → 𝑄𝐱 = 𝐱 . Bukti lengkap. ∎ Berdasarkan Lema 4.2.3, diperoleh kedua akibat berikut. Akibat 4.2.4 𝑄 ≤ 1. Akibat 4.2.5 Jika 𝐱 ∈ Ker 𝐴 maka 𝑄𝐱 = 𝐱. Agar mempermudah beberapa penulisan tertentu, Ker 𝐴 dan Im 𝐴𝑇 berturut-turut hanya akan dituliskan dengan 𝒦 dan ℐ. Berdasarkan bagian pertama dari Lema 2.4.4, Lema 2.4.8, Lema 2.4.10, Lema 2.4.12, Lema 4.2.3, Akibat 4.2.4, dan Akibat 4.2.5, diperoleh teorema berikut. Teorema 4.2.6 1. 𝑄 = 𝑃𝒦 + 𝑄 dengan 𝑄 = 𝑄𝑃ℐ . 2. 𝑄 < 1.

Bukti: Berdasarkan Definisi 2.4.14, 𝑃𝒦 adalah proyeksi ortogonal pada Ker 𝐴 , dengan 𝑃𝒦 𝐱 = 𝐱, ∀𝐱 ∈ Ker 𝐴 dan ⊥ 𝑃𝒦 𝐲 = 𝟎, ∀𝐲 ∈ Ker 𝐴 = Im 𝐴𝑇 (berdasarkan Lema 2.4.10). Berdasarkan Definisi 2.4.14, 𝑃ℐ adalah proyeksi ortogonal pada Im 𝐴𝑇 dengan 𝑃ℐ 𝐲 = 𝐲, ∀𝐲 ∈ Im 𝐴𝑇 dan ⊥ 𝑃ℐ 𝐱 = 𝟎, ∀𝐱 ∈ Im 𝐴𝑇 = Ker 𝐴 (berdasarkan Lema 2.4.10). Berdasarkan Lema 2.4.10, Ker 𝐴 = 𝑇 ⊥ Im 𝐴 , sehingga berdasarkan Lema 2.4.12, diperoleh Ker 𝐴 ⊕ Im 𝐴𝑇 = ℝ𝑁 . Dimisalkan 𝐳 ∈ ℝ𝑁 sebarang, maka 𝐳 dapat dituliskan secara unik sebagai 𝐳 = 𝐱 + 𝐲 dengan 𝐱 ∈ Ker 𝐴 dan 𝐲 ∈ Im 𝐴𝑇 . Karena 𝑄 = 𝑄𝑃ℐ , maka 𝑃𝒦 + 𝑄 𝐳 = 𝑃𝒦 + 𝑄𝑃ℐ 𝐱 + 𝐲 = 𝑃𝒦 𝐱 + 𝐲 + 𝑄𝑃ℐ 𝐱 + 𝐲 = 𝑃𝒦 𝐱 + 𝑃𝒦 𝐲 + 𝑄𝑃ℐ 𝐱 + 𝑄𝑃ℐ 𝐲 = 𝐱 + 𝟎 + 𝑄𝟎 + 𝑄𝐲 = 𝑄𝐱 + 𝟎 + 𝟎 + 𝑄𝐲 = 𝑄 𝐱+𝐲 = 𝑄𝐳 (berdasarkan Akibat 4.2.5). Karena 𝑃𝒦 + 𝑄 𝐳 = 𝑄𝐳, ∀𝐳 ∈ ℝ𝑁 , maka berdasarkan Definisi 2.3.2, 𝑄 = 𝑃𝒦 + 𝑄 . Bagian pertama terbukti. Selanjutnya, berdasarkan Definisi 2.4.3, 𝑄 = max

𝑄𝐱 𝐱

𝐱 ∈ ℝ𝑁 , 𝐱 ≠ 𝟎 .

Dimisalkan 𝐱 ∈ ℝ𝑁 , 𝐱 ≠ 𝟎 sebarang. Karena 𝑄 = 𝑄𝑃ℐ , maka 𝑄 𝐱 = 𝑄𝑃ℐ 𝐱. Berdasarkan bagian pertama dari Lema 2.4.4, diperoleh 𝑄 𝐱 = 𝑄𝑃ℐ 𝐱 ≤ 𝑄

𝑃ℐ 𝐱 .

Karena 𝑃ℐ 𝐱 ≤ 𝐱 , maka 𝑄𝐱 ≤ 𝑄 𝑃ℐ 𝐱 ≤ 𝑄 𝐱 𝑄𝐱 𝑄 𝐱 → ≤ ≤ 𝑄 . 𝐱 𝐱 Jadi, 𝑄 ≤ 𝑄 . Berdasarkan Akibat 4.2.4, diperoleh 𝑄 ≤ 𝑄 ≤ 1. ⊥

Karena Ker 𝐴 = Im 𝐴𝑇 (berdasarkan Lema 2.4.10), maka Ker 𝐴 ⊥ Im 𝐴𝑇 . Oleh karena itu, berdasarkan Lema 2.4.8,

11

Ker 𝐴 ∩ Im 𝐴𝑇 = 𝟎 . Diketahui bahwa untuk setiap vektor 𝐱 ∈ ℝ𝑁 , 𝐱 ≠ 𝟎, berlaku 𝑃ℐ 𝐱 ∈ Im 𝐴𝑇 . Jika 𝑃ℐ 𝐱 ∈ Ker 𝐴 , maka 𝑃ℐ 𝐱 = 𝟎, sehingga 𝑄 𝐱 = 𝑄𝑃ℐ 𝐱 = 𝑄𝟎 = 𝟎 = 0 < 𝐱 . Jika 𝑃ℐ 𝐱 ∉ Ker 𝐴 , maka berdasarkan Lema 4.2.3, 𝑄 𝐱 = 𝑄𝑃ℐ 𝐱 < 𝑃ℐ 𝐱 ≤ 𝐱 . Oleh karena itu, untuk setiap vektor 𝐱 ∈ ℝ𝑁 , 𝐱 ≠ 𝟎, berlaku 𝑄𝐱 < 𝐱 . Jika 𝑄 = 1, maka berdasarkan definisi dari 𝑄 , terdapat suatu vektor 𝐱 0 ∈ ℝ𝑁 , 𝐱 0 ≠ 𝟎, sedemikian sehingga 𝑄 𝐱 0 = 𝐱 0 . Hal ini kontradiksi dengan hasil sebelumnya yang menyatakan bahwa untuk setiap vektor 𝐱 ∈ ℝ𝑁 , 𝐱 ≠ 𝟎, berlaku 𝑄 𝐱 < 𝐱 . Jadi, dapat disimpulkan bahwa 𝑄 < 1. Bagian kedua terbukti. Bukti lengkap. ∎ Berdasarkan Lema 2.4.4, Lema 2.4.10, Lema 2.6.3, Proposisi 4.2.2, dan Teorema 4.2.6, diperoleh teorema berikut. Teorema 4.2.7

𝑛+1

= 𝐹 𝐱 𝑛 ; 𝟎 = 𝑄𝐱 𝑛 = 0,1,2, …

𝑛

𝐱

𝑛

membangun suatu barisan konvergen ke 𝑃𝒦 𝐱 0 , yaitu lim 𝐱

𝑛→∞

𝑛

= lim 𝑄𝑛 𝐱

0

𝑛→∞

𝐱 𝑇 𝑄𝐲 = 𝑄𝑇 𝐱 𝑇 𝐲 = 𝐱 𝑇 𝐲 = 0 sehingga 𝑄𝐲 ∈ Im 𝐴𝑇 (berdasarkan Lema 2.4.10 juga). Karena 𝑃ℐ 𝑄 𝑛−1 𝐱 ∈ Im 𝐴𝑇 untuk setiap 𝐱 ∈ ℝ𝑁 dan setiap 𝑛 ∈ ℕ serta berdasarkan bagian pertama dari Teorema 4.2.6, maka 𝑄𝑛 𝐱 = 𝑄 𝑄 𝑛−1 𝐱 = 𝑄𝑃ℐ 𝑄 𝑛−1 𝐱 ∈ Im 𝐴𝑇 untuk setiap 𝐱 ∈ ℝ𝑁 . Berdasarkan Persamaan (5) dan (9) serta bagian pertama dari Teorema 4.2.6, untuk 𝐛 = 𝟎 diperoleh 𝐱

𝐱

1

= 𝑄𝐱 0 = 𝑃𝒦 + 𝑄 𝐱 0 = 𝑃𝒦 𝐱 0 + 𝑄 𝐱 = 𝑄𝐱

𝑃𝒦 𝐱 0 ∈ Ker 𝐴

= 𝑃𝒦 𝑃𝒦 𝐱

, yang = 0

1 2

= 𝑄𝐱 0 = 𝑄𝐱 1 = 𝑄𝑄𝐱 0 = 𝑄2 𝐱 0 .

Dengan cara serupa, diperoleh 𝐱 3 = 𝑄3 𝐱 0 𝐱 4 = 𝑄4 𝐱 0 dan seterusnya, sehingga diperoleh pola dengan bentuk

0

+ 𝑄𝐱

+ 𝑃𝒦 𝑄 𝐱

∈ Im 𝐴𝑇 0

∈ Im 𝐴𝑇 0

∈ Ker 𝐴 0

+ 𝑄 𝑄𝐱

∈ Im 𝐴𝑇 2 0

∈ Ker 𝐴 0

+ 𝟎 + 𝑄𝟎 + 𝑄 𝐱

∈ Ker 𝐴 𝑃𝒦 𝐱 0 ∈ Ker 𝐴

∈ Im 𝐴𝑇 2

0

+𝑄 𝐱

.

∈ Im 𝐴𝑇

Dengan cara serupa, diperoleh

dengan 𝐱 0 ∈ ℝ𝑁 adalah vektor penyelesaian hampiran awal sebarang.

𝐱 𝐱

0

+𝑄𝑃ℐ 𝑃𝒦 𝐱

Bukti: Berdasarkan Persamaan (5) dan (9), untuk 𝐛 = 𝟎 diperoleh

0

∈ Im 𝐴𝑇

∈ Ker 𝐴 1

2

= 𝑃𝒦 𝐱

= 𝑃𝒦 𝐱

(10)

(bukti dapat dilihat pada Lampiran 4). Diketahui untuk setiap 𝐱 ∈ ℝ𝑁 , 𝑃𝒦 𝐱 ∈ Ker 𝐴 dan untuk setiap 𝐲 ∈ ℝ𝑁 , 𝑃ℐ 𝐲 ∈ Im 𝐴𝑇 . Kemudian, berdasarkan Lema 2.4.10 dan Proposisi 4.2.2, untuk setiap 𝐱 ∈ Ker 𝐴 dan setiap 𝐲 ∈ Im 𝐴𝑇 berlaku

= 𝑃𝒦 + 𝑄

Untuk setiap matriks 𝐴 yang berorde 𝑀 × 𝑁 dengan baris-baris taknol dan vektor kolom 𝐛 = 𝟎 yang berorde 𝑀 × 1, algoritme (5) 𝐱

𝐱 𝑛 = 𝑄𝑛 𝐱 0 untuk setiap 𝑛 ∈ ℕ

𝐱

3

= 𝑃𝒦 𝐱

𝐱

4

= 𝑃𝒦 𝐱

0

∈ Ker 𝐴 0

+ 𝑄3 𝐱

0

∈ Im 𝐴𝑇 0

+ 𝑄4 𝐱

∈ Im 𝐴𝑇

∈ Ker 𝐴

dan seterusnya, sehingga diperoleh pola dengan bentuk 𝐱

𝑛

= 𝑃𝒦 𝐱

0

∈ Ker 𝐴

+ 𝑄𝑛 𝐱

0

(11)

∈ Im 𝐴𝑇

untuk setiap 𝑛 ∈ ℕ (bukti dapat dilihat pada Lampiran 5). Jadi, lim 𝐱

𝑛→∞

𝑛

= lim 𝑄𝑛 𝐱 𝑛→∞

= lim 𝑃𝒦 𝐱 𝑛→∞

0 0

+ 𝑄𝑛 𝐱

0

.

12

Karena 𝑃𝒦 𝐱

0

tidak bergantung pada 𝑛, maka 0

lim 𝑃𝒦 𝐱

0

= 𝑃𝒦 𝐱

𝑛→∞

lim 𝑄 𝑛 𝐱

.

0

lim 𝐱

0

Karena 𝑄 < 1 (berdasarkan bagian kedua dari Teorema 4.2.6), maka ln 𝑄 < 0. Kemudian dipilih 𝑛0 ∈ ℕ sedemikian sehingga 𝐱 0 +𝜖 ≥ 0. ln 𝑄

ln

→ 𝑛 ln 𝑄

< ln

→ ln 𝑄 → 𝑄

𝑛

𝐱

sedemikian

𝑛

< ln 𝐱0 𝜖 < . 𝐱 0 +𝜖

𝜖

𝑛+1

= 𝐹 𝐱 𝑛 ; 𝐛 = 𝑄𝐱 𝑛 = 0,1,2, …

𝑛

< → 𝑄𝑛

+𝜖 +𝜖

𝐱 𝐱

1 2

yang

+ 𝐻𝐛

= 𝑄𝐱 0 + 𝑅𝐛 = 𝑄𝐱 1 + 𝑅𝐛 = 𝑄 𝑄𝐱 0 + 𝑅𝐛 + 𝑅𝐛 = 𝑄2 𝐱 0 + 𝑄𝑅𝐛 + 𝑅𝐛 = 𝑄2 𝐱 0 + 𝑄𝑅 + 𝑅 𝐛 1 2

𝑄 ⋯ 𝑄

=𝑄 𝐱

0

𝑄𝑘 𝑅

+

𝑛 kali

𝐛.

𝑘=0

Dengan cara serupa, diperoleh

𝜖

𝐱 0 +𝜖 𝐱 0 + 𝜖 < 𝜖.

≤ 𝑄𝑛 𝐱 0 < 𝑄𝑛 𝐱0 <𝜖 → 𝑄 𝑛 𝐱 0 − 𝟎 < 𝜖.

𝑛

Bukti: Berdasarkan Persamaan (5) dan (9) diperoleh

2

𝐱

3

3

=𝑄 𝐱

0

+

𝐱

0

+𝜖

𝑄𝑘 𝑅

𝐛

𝑄𝑘 𝑅

𝐛

𝑘=0 3

Berdasarkan bagian pertama dari Lema 2.4.4, 𝑄𝑛 𝐱

0

= 𝑃𝒦 𝐱

𝑛 kali

𝑛

+ 𝑅𝐛,

dengan 𝐱 0 ∈ ℝ𝑁 adalah vektor penyelesaian hampiran awal sebarang dan matriks 𝐻 = −1 𝐼 − 𝑄 𝑅 (berorde 𝑁 × 𝑀).

𝑄 𝑛 = 𝑄𝑄 ⋯ 𝑄

= 𝑄

𝑛

membangun suatu barisan vektor 𝐱 konvergen ke 𝑃𝒦 𝐱 0 + 𝐻𝐛, yaitu

Berdasarkan bagian kedua dari Lema 2.4.4,

≤ 𝑄

.

Untuk setiap matriks 𝐴 yang berorde 𝑀 × 𝑁 dengan baris-baris taknol dan setiap vektor kolom 𝐛 yang berorde 𝑀 × 1, algoritme (5)

lim 𝐱

𝜖

0

+𝟎

0

Teorema 4.2.8

𝜖 𝐱 0 +𝜖 ln 𝑄

0

Bukti lengkap. ∎

𝑛→∞

𝑛 ≥ 𝑛0 >

0

= 𝑃𝒦 𝐱 = 𝑃𝒦 𝐱

𝐱

𝜖

Dimisalkan 𝑛 ∈ ℕ sebarang sehingga 𝑛 ≥ 𝑛0 , maka

𝑛→∞

Berdasarkan Lema 2.4.10, Lema 2.6.3, Teorema 2.6.5, Proposisi 4.2.2, bagian pertama dan kedua dari Teorema 4.2.6, dan Teorema 4.2.7 diperoleh teorema berikut yang menyatakan kekonvergenan barisan penyelesaian hampiran yang dibangun dengan metode Kaczmarz.

+𝜖 ≥0+𝜖 =𝜖 >0 𝜖 →0< ≤1 0 𝐱 +𝜖 𝜖 → ln ≤ 0. 𝐱 0 +𝜖

𝑛0 >

= lim 𝑄𝑛 𝐱

−

0

ln

𝑛

𝑛→∞

yaitu ∀𝜖 > 0, ∃𝑛0 ∈ ℕ sehingga 𝑄 𝑛 𝐱 𝟎 < 𝜖, untuk ∀𝑛 ≥ 𝑛0 . Dimisalkan 𝜖 > 0 sebarang. Karena 𝜖 > 0 dan 𝐱 0 ≥ 0, maka 𝐱

= 𝟎.

Jadi, berdasarkan Lema 2.6.3, diperoleh

= 𝟎.

𝑛→∞

0

𝑛→∞

Selanjutnya, akan dibuktikan bahwa lim 𝑄 𝑛 𝐱

Oleh karena itu, terbukti bahwa

4

= 𝑄4 𝐱

0

+ 𝑘=0

dan seterusnya, sehingga diperoleh pola dengan bentuk

13

𝑛−1

𝐱

𝑛

𝑛

=𝑄 𝐱

0

𝑘

+

𝑄 𝑅

𝐛

(12)

𝑘=0

untuk setiap 𝑛 ∈ ℕ

merupakan anggota dari Im 𝐴𝑇 , sehingga 𝑃ℐ 𝑄𝑅 = 𝑄𝑅. Jadi, diperoleh 𝑛

𝑄 𝑘 𝑅 = 𝑄 0 𝑅 + 𝑄1 𝑅 + 𝑄 2 𝑅 + ⋯ + 𝑄 𝑛 𝑅

(bukti dapat dilihat pada Lampiran 6). Jadi,

𝑘=0

𝑛−1

lim 𝐱

𝑛

= lim 𝑄𝑛 𝐱

𝑛→∞

0

𝑄𝑘 𝑅

+

𝑛→∞

𝑛

𝑛

𝑄 𝐱

Berdasarkan Teorema 4.2.7, konvergen ke 𝑃𝒦 𝐱 0 , artinya lim 𝑄𝑛 𝐱

0

= 𝑃𝒦 𝐱

𝑛→∞

sehingga bahwa

𝐛.

𝑘=0

selanjutnya

0

tinggal

0

𝑄𝑘 𝑅

= 𝑘=0

, dibuktikan

𝑛−1

𝑄𝑘 𝑅

= 𝐼𝑅 + 𝑄𝑃ℐ 𝑅 + 𝑄𝑃ℐ 2 𝑅 + ⋯ + 𝑄𝑃ℐ 𝑛 𝑅 = 𝑄0 𝑅 + 𝑄1 𝑅 + 𝑄2 𝑅 + ⋯ + 𝑄𝑛 𝑅

(berdasarkan bagian pertama dari Teorema 4.2.6). Karena 𝑄 < 1 (berdasarkan bagian kedua dari Teorema 4.2.6), maka berdasarkan Teorema 2.6.5 diperoleh ∞

𝐛

∞ 𝑘

𝑘=0

konvergen ke 𝐻𝐛, yaitu

𝑘=0

= 𝐼−𝑄 = 𝐻,

𝑛−1

𝑄𝑘 𝑅

lim

𝑛→∞

𝐛 = 𝐻𝐛.

𝑘=0

𝐱 𝑄𝑖−1 𝐚𝑖 =

𝑇 𝑄𝑖−1 𝐱 𝑇 𝐚𝑖

𝐱𝑇

1 𝐚𝑖

2

𝑄𝑖−1 𝐚𝑖 =

1 𝐚𝑖

2

𝑄𝑘 𝑅

= lim

𝑛→∞

𝐛

𝑘=0

∞

𝑇

𝐛

𝑘=0 𝑛−1

𝑄𝑘 𝑅

=

𝐛

𝑘=0

= 𝐱 𝐚𝑖 = 0

= 𝐻𝐛 (berdasarkan Definisi 2.6.4). Oleh karena itu,

2

𝐱 𝑇 𝑄𝑖−1 𝐚𝑖 = 0.

Jadi, berdasarkan Lema 2.4.10, vektor-vektor kolom 1 𝐚𝑖

𝑄𝑘 𝑅

lim

𝑛→∞

(berdasarkan

untuk setiap 𝑖 = 1,2, … , 𝑀. Oleh karena itu,

𝑅

𝑛−1

𝑇 𝑄𝑖−1 𝐱 = 𝑃𝑖−1 𝑃𝑖−2 … 𝑃2 𝑃1 𝐱 = 𝐱

untuk setiap 𝑖 = 1,2, … , 𝑀 Proposisi 4.2.2), sehingga

−1

sehingga

Karena 𝑄𝑖𝑇 = 𝑃𝑖 𝑃𝑖−1 … 𝑃2 𝑃1 untuk setiap 𝑖 = 1,2, … , 𝑀, maka untuk setiap 𝐱 ∈ Ker 𝐴 , berlaku

𝑇

𝑄𝑘 𝑅

𝑄 𝑅 =

𝑘=0

𝑄𝑖−1 𝐚𝑖

dari matriks 𝑅 merupakan anggota dari Im 𝐴𝑇 , sehingga 𝑃ℐ 𝑅 = 𝑅. Selanjutnya, berdasarkan Lema 2.4.10 dan Proposisi 4.2.2, untuk setiap 𝐱 ∈ Ker 𝐴 dan 𝐲 ∈ Im 𝐴𝑇 berlaku 𝐱 𝑇 𝑄𝐲 = 𝑄𝑇 𝐱 𝑇 𝐲 = 𝐱 𝑇 𝐲 = 0 sehingga 𝑄𝐲 ∈ Im 𝐴𝑇 (berdasarkan Lema 2.4.10 juga). Karena vektor-vektor kolom dari matriks 𝑅 merupakan anggota dari Im 𝐴𝑇 , maka vektor-vektor kolom dari matriks 𝑄𝑅 juga

𝑛−1

𝑄𝑘 𝑅

𝐛

𝑘=0

konvergen ke 𝐻𝐛. Jadi, berdasarkan Lema 2.6.3, terbukti bahwa 𝐱 𝑛 konvergen ke 𝑃𝒦 𝐱

0

+ 𝐻𝐛,

yaitu lim 𝐱

𝑛

𝑛→∞

= 𝑃𝒦 𝐱

0

+ 𝐻𝐛.

Bukti lengkap. ∎ Berdasarkan Teorema 4.2.8, apabila SPL pada Persamaan (1) konsisten, maka untuk sebarang penyelesaian hampiran awal 𝐱 0 , 𝑃𝒦 𝐱 0 + 𝐻𝐛 adalah penyelesaian eksaknya. Hal ini juga memberikan hasil bahwa

14

himpunan semua vektor penyelesaian kuadrat terkecil atas SPL pada Persamaan (1) adalah 𝐿𝑆𝑆 𝐴, 𝐛 = 𝑃𝒦 𝐱 0 + 𝐻𝐛 𝐱 = Ker 𝐴 + 𝐻𝐛. Jadi, barisan vektor 𝐱 konvergen ke 𝐿𝑆𝑆 𝐴, 𝐛 .

𝑛

0

ℎ 𝑥, 𝑦 =

∈ ℝ𝑁

1 𝑥 2 + 𝑦2 exp − . 2𝜎 2 2𝜎 2

Program pembangkit dengan cara ini terdapat pada Lampiran 8. Matriks koefisien yang dihasilkan adalah segi. Pembangkitan ini mempunyai batasan, yakni orde dari matriks koefisien disarankan tidak terlalu kecil dan direkomendasikan lebih besar dari atau sama dengan 256 × 256. SPL ke-2 dibangkitkan dari diskretisasi persamaan integral Fredholm jenis pertama berikut:

yang dibangun

4.3. Hasil Komputasi Algoritme untuk metode Kaczmarz diimplementasikan dengan membuat program MATLAB yang hasilnya terdapat pada Lampiran 7. Input dari program ini adalah matriks koefisien, vektor konstanta, dan sebarang vektor penyelesaian hampiran awal. Selain itu, terdapat input tambahan sebagai kriteria pemberhentian, yaitu banyaknya iterasi dan batas toleransi. Input tambahan ini dapat ditentukan sendiri (salah satu atau keduanya) atau disesuaikan dengan nilai default-nya. Nilai default dari banyaknya iterasi dan batas toleransi berturut-turut adalah 100 dan 10-6. Output dari program ini adalah vektor penyelesaian hampiran atas SPL. Sebagai tambahan, ditampilkan pula norm sisaan dari penyelesaian hampiran tersebut. Pengujian dan pengamatan terhadap program MATLAB dari algoritme untuk metode Kaczmarz ini dilakukan dengan menggunakan sistem persamaan linear yang matriks koefisien dan vektor konstantanya dibangkitkan. Ada tiga jenis SPL yang digunakan. Ketiganya dibangkitkan dengan cara yang berbeda. Setiap jenis diwakili oleh satu SPL. Jadi, ada tiga SPL yang digunakan. Pembangkitan sistem persamaan linear ini menggunakan program MATLAB yang telah disediakan oleh Hansen (1994). SPL ke-1 dibangkitkan dari masalah pemburaman gambar digital yang dimodelkan dengan fungsi pemancaran titik Gauss berikut:

6

𝜅 𝜏, 𝜎 𝑥 𝜎 𝑑𝜎 = 𝑏 𝜏 , −6 ≤ 𝜏 ≤ 6. −6

Diskretisasi dilakukan dengan metode Galerkin. Calvetti dan Reichel (2002) memberikan penyelesaian 𝑥, kernel 𝜅, dan ruas kanan 𝑏 sebagai berikut: 𝜋 1 + cos 𝜎 , 𝜎 < 3 𝑥 𝜎 = 3 0, 𝜎 ≥3 𝜅 𝜏, 𝜎 = 𝑥 𝜏 − 𝜎 1 𝜋 𝑏 𝜏 = 6 − 𝜏 1 + cos 𝜏 2 3 9 𝜋 + sin 𝜏 . 2𝜋 3 Program pembangkit dengan cara ini terdapat pada Lampiran 9. Matriks koefisien yang dihasilkan adalah segi. Pembangkitan ini juga mempunyai batasan, yakni orde dari matriks koefisien kelipatan dari empat, sehingga ukuran SPL yang dibangkitkannya pun kelipatan dari empat. SPL ke-3 dibangkitkan dari masalah tomografi dua dimensi. Program pembangkit dengan cara ini terdapat pada Lampiran 10. Matriks koefisien yang dihasilkan adalah segi. Pembangkitan ini mempunyai batasan yang sama dengan pembangkitan pertama.

Tabel 1 Karakteristik SPL yang digunakan untuk pengujian dan pengamatan Karakteristik Ukuran Konsisten Matriks koefisien sparse Nilai maksimum elemen matriks koefisien Nilai minimum elemen matriks koefisien Nilai maksimum elemen vektor konstanta Nilai minimum elemen vektor konstanta

SPL ke-1 256 × 256 Ya Ya

SPL ke-2 256 × 256 Ya Tidak

SPL ke-3 256 × 256 Ya Ya

0.3248

0.0937

1.4016

0

0

0

3.2062

1.9483

34.0352

0

8.1831 × 10-11

0

15

Karakteristik dari ketiga SPL yang digunakan tersebut disajikan pada Tabel 1. Ketiga SPL tersebut mempunyai ukuran yang sama, yaitu 256 × 256. Ketiga SPL tersebut bersifat konsisten, sehingga himpunan 𝐿𝑆𝑆 𝐴, 𝐛 = Ker 𝐴 + 𝐻𝐛 untuk ketiga SPL mempunyai minimal satu anggota yang merupakan penyelesaian kuadrat terkecil atas SPL. Penyelesaian ini juga merupakan penyelesaian eksak dari SPL. Matriks koefisien dari SPL ke-1 dan ke-3 sparse, sedangkan matriks koefisien dari SPL ke-2 tidak sparse. Hal ini juga dapat dilihat dari pola sparsity yang diperlihatkan oleh Gambar 3, 4, dan 5. Warna biru menunjukkan elemen taknol, sedangkan warna putih menunjukkan elemen nol. Banyaknya elemen taknol dari matriks koefisien dari SPL ke-1 ada 5 476 atau 8.36% dari banyaknya elemen. Semua elemen taknolnya adalah positif dengan nilai maksimum 0.3248. Semua elemen dari vektor konstanta dari SPL ke-1 adalah taknegatif dengan nilai minimum 0 dan nilai maksimum 3.2062.

Gambar 3

Pola sparsity dari koefisien dari SPL ke-1.

Gambar 4


matriks

Banyaknya elemen taknol dari matriks koefisien dari SPL ke-3 ada 5 409 atau 8.25% dari banyaknya elemen. Semua elemen taknolnya adalah positif dengan nilai maksimum 1.4016. Semua elemen dari vektor konstanta dari SPL ke-3 adalah taknegatif dengan nilai minimum 0 dan nilai maksimum 34.0352. Karakteristik SPL ke-3 ini mirip dengan SPL ke-1. Perbedaannya terlihat pada pola sparsity dari matriks koefisien keduanya.

matriks

Matriks koefisien dari SPL ke-2 mempunyai elemen taknol pada diagonal utama serta pada 64 diagonal di bawah dan 64 diagonal di atas diagonal utama. Matriks seperti ini disebut banded dengan bandwidth 129. Banyaknya elemen taknol ada 28 864 atau 44.04% dari banyaknya elemen. Semua elemen taknol adalah positif dengan nilai maksimum 0.0937. Semua elemen dari vektor konstanta dari SPL ke-2 adalah positif dengan nilai minimum 8.1831 × 10-11 dan nilai maksimum 1.9483.

Gambar 5


matriks

Penyelesaian hampiran awal yang digunakan adalah vektor kolom nol. Penyelesaian hampiran awal seperti ini menyebabkan norm sisaan awal yang berbedabeda untuk ketiga SPL (dapat dilihat pada Lampiran 11). Pengamatan terhadap kekonvergenan dilakukan dengan melihat norm sisaan dari penyelesaian hampiran atas ketiga SPL pada iterasi ke-0 sampai iterasi ke-30. Hasilnya diperlihatkan oleh Gambar 6, 7, dan 8. Selain itu, dapat juga dilihat pada Lampiran 11.

16

Gambar 6 Hasil kekonvergenan untuk SPL ke-1.



17

Pengamatan terhadap kekonvergenan memperlihatkan hasil yang sesuai dengan analisis pada subbab sebelumnya. Hasil menunjukkan bahwa untuk ketiga SPL yang digunakan, algoritme untuk metode Kaczmarz membangun barisan penyelesaian hampiran atas SPL yang konvergen. Hasil ini dapat dilihat dari norm sisaan yang semakin mengecil menuju nol. Norm sisaan yang semakin mendekati nol ini mempunyai arti bahwa penyelesaian hampiran yang dihasilkan semakin mendekati penyelesaian eksaknya. Norm sisaan untuk ketiga SPL menurun dengan laju yang cukup cepat sebelum iterasi

ke-10. Setelah itu, laju penurunannya melambat. Perlambatan ini juga dapat diamati dari peningkatan yang sangat tajam dari banyaknya iterasi yang diperlukan untuk memperoleh norm sisaan yang semakin kecil. Agar diperoleh norm sisaan yang lebih kecil dari atau sama dengan 10-1 untuk SPL ke-1 sampai ke-3, diperlukan berturut-turut 22, 10, dan 1 249 iterasi. Kemudian, agar diperoleh norm sisaan yang lebih kecil dari atau sama dengan 10-2 untuk SPL ke-1 sampai ke-3, diperlukan berturut-turut 122, 68, dan 50 771 iterasi.

V. SIMPULAN DAN SARAN 5.1. Simpulan Metode Kaczmarz merupakan metode iteratif untuk mendapatkan penyelesaian hampiran atas sistem persamaan linear. Proyeksi ortogonal digunakan dalam algoritme untuk metode ini. Proyeksi ortogonal dilakukan berurutan pada semua hiperbidang hingga didapatkan penyelesaian hampiran yang mempunyai norm sisaan sekecil yang diinginkan. Barisan penyelesaian hampiran atas sistem persamaan linear yang dibangun oleh algoritme untuk Metode Kaczmarz telah dibuktikan konvergen, apapun penyelesaian hampiran awal yang digunakan. Penyelesaian hampiran atas sistem persamaan linear ini konvergen ke penyelesaian kuadrat terkecil dari sistem persamaan linear tersebut. Apabila sistem persamaan linear tersebut konsisten, maka penyelesaian kuadrat terkecilnya juga merupakan penyelesaian eksaknya. Program MATLAB dari algoritme untuk metode Kaczmarz telah berhasil dibuat. Program ini berjalan dengan benar sesuai dengan algoritmenya. Pengamatan terhadap kekonvergenan barisan penyelesaian hampiran atas sistem persamaan linear yang dibangun melalui program tersebut dilakukan dengan menggunakan tiga sistem persamaan linear

yang dibangkitkan. Barisan penyelesaian hampiran atas ketiga sistem persamaan linear tersebut konvergen dengan melihat norm sisaan yang semakin mengecil menuju nol. 5.2. Saran Penelitian ini masih dapat dilanjutkan. Ada beberapa hal yang dapat dilakukan, yaitu menentukan orde galat dari penyelesaian hampiran yang dihasilkan oleh metode Kaczmarz, membuat program paralel dari algoritme untuk metode Kaczmarz, dan membandingkan metode Kaczmarz dengan metode iteratif (untuk menyelesaikan sistem persamaan linear) lain seperti metode Conjugate Gradient dalam hal banyaknya iterasi dan waktu eksekusi yang diperlukan untuk mendapatkan penyelesaian hampiran dengan tingkat kesalahan tertentu. Kemudian, dapat pula dipelajari metode-metode yang telah dikembangkan dari metode Kaczmarz, seperti metode Kaczmarz acak dengan kekonvergenan eksponensial, metode Kaczmarz terboboti, metode Kaczmarz yang diperluas dengan proyeksi taklangsung, dan metode Kaczmarz yang diperluas dengan parameter-parameter relaksasi. Selain itu, metode-metode tersebut dapat pula dibandingkan.

DAFTAR PUSTAKA Anton H, Rorres C. 2005. Elementary Linear Algebra. Ed ke-9. New Jersey: J Wiley. Calvetti D, Reichel L. 2002. Tikhonov Regularization of Large Linear Problems. BIT 43: 15-16. Deskins W E. 1964. Abstract Algebra. New York: Dover Publications. Hansen PC. 1994. Regularization Tools: A MATLAB Package for Analysis and Solution of Discrete Ill-posed Problems. Numerical Algorithms 6: 1-35.

Leon SJ. 1998. Linear Algebra with Applications. Ed ke-5. New Jersey: Prentice Hall. Rynne BP, Youngson MA. 2008. Linear Functional Analysis. Ed ke-2. London: Springer. Tanabe K. 1971. Projection Method for Solving a Singular System of Linear Equation and Its Applications. Numer Math 17: 203-214.

LAMPIRAN

21

Lampiran 1 Pembuktian Teorema 2.4.15 (Rumus Proyeksi Ortogonal) Misalkan suatu hiperbidang di ℝ𝑁 mempunyai persamaan 𝐚𝑇 𝐱 = 𝑏 dan misalkan 𝐱 ∗ adalah sebarang titik di ℝ𝑁 , maka proyeksi ortogonal, 𝐱 𝑝 , dari 𝐱 ∗ terhadap hiperbidang tersebut dinyatakan dengan 𝐱𝑝 = 𝐱∗ +

𝑏 − 𝐚𝑇 𝐱 ∗ 𝐚. 𝐚 𝟐

Bukti: Teorema ini dapat dibuktikan dengan membuktikan bahwa (i) titik 𝐱 𝑝 terletak pada hiperbidang 𝐚𝑇 𝐱 = 𝑏 (dalam hal ini, 𝐚𝑇 𝐱 𝑝 = 𝑏) dan (ii) vektor 𝐱 𝑝 − 𝐱 ∗ ortogonal terhadap hiperbidang 𝐚𝑇 𝐱 = 𝑏 (dalam hal ini, vektor 𝐱 𝑝 − 𝐱 ∗ sejajar dengan vektor 𝐚). Pertama, karena 𝐱𝑝 = 𝐱∗ +

𝑏 − 𝐚𝑇 𝐱 ∗ 𝐚, 𝐚 𝟐

maka 𝑏 − 𝐚𝑇 𝐱 ∗ 𝐚 𝐚 𝟐 𝑏 − 𝐚𝑇 𝐱 ∗ 𝑇 = 𝐚𝑇 𝐱 ∗ + 𝐚 𝐚 𝐚 𝟐 𝑇 ∗ 𝑏−𝐚 𝐱 = 𝐚𝑇 𝐱 ∗ + 𝐚 𝟐 𝐚 𝟐 = 𝐚𝑇 𝐱 ∗ + 𝑏 − 𝐚𝑇 𝐱 ∗ = 𝑏.

𝐚𝑇 𝐱 𝑝 = 𝐚𝑇 𝐱 ∗ +

Jadi, terbukti bahwa titik 𝐱 𝑝 terletak pada hiperbidang 𝐚𝑇 𝐱 = 𝑏. Kedua, karena 𝐱𝑝 = 𝐱∗ +

𝑏 − 𝐚𝑇 𝐱 ∗ 𝐚, 𝐚 𝟐

maka 𝑏 − 𝐚𝑇 𝐱 ∗ 𝐚. 𝐚 𝟐 ∗ Karena vektor 𝐱 𝑝 − 𝐱 merupakan merupakan vektor 𝐚 dikalikan dengan suatu skalar, maka vektor 𝐱 𝑝 − 𝐱 ∗ sejajar dengan vektor 𝐚. Jadi, terbukti bahwa vektor 𝐱 𝑝 − 𝐱 ∗ ortogonal terhadap hiperbidang 𝐚𝑇 𝐱 = 𝑏. Bukti lengkap. ∎ 𝐱𝑝 − 𝐱∗ =

22

Lampiran 2 Pembuktian Persamaan (6) Diketahui Persamaan (3), yaitu 𝑓𝑖 𝐱 = 𝐱 +

𝑏𝑖 − 𝐚𝑇𝑖 𝐱 𝐚𝑖 𝐚𝑖 2

untuk 𝑖 = 1, 2, … , 𝑀.

Akan dibuktikan bahwa Persamaan (3) ekivalen dengan Persamaan (6), yaitu 𝑓𝑖 𝐱 = 𝑃𝑖 𝐱 +

𝑏𝑖 𝐚𝑖

2

untuk 𝑖 = 1, 2, … , 𝑀

𝐚𝑖

dengan 𝑃𝑖 = 𝐼 − Bukti: 𝑏𝑖 − 𝐚𝑇𝑖 𝐱 𝐚𝑖 𝐚𝑖 2 𝐚𝑇𝑖 𝐱 𝑏𝑖 =𝐱− 𝐚 + 𝐚 𝐚𝑖 2 𝑖 𝐚𝑖 2 𝑖 1 𝑏𝑖 =𝐱− 𝐚𝑖 𝐚𝑇𝑖 𝐱 + 𝐚 2 𝐚𝑖 𝐚𝑖 2 𝑖 1 𝑏𝑖 = 𝐼𝐱 − 𝐚𝑖 𝐚𝑇𝑖 𝐱 + 𝐚 2 𝐚𝑖 𝐚𝑖 2 𝑖 1 𝑏𝑖 = 𝐼− 𝐚𝑖 𝐚𝑇𝑖 𝐱 + 𝐚. 2 𝐚𝑖 𝐚𝑖 2 𝑖

𝑓𝑖 𝐱 = 𝐱 + ↔ 𝑓𝑖 𝐱 ↔ 𝑓𝑖 𝐱 ↔ 𝑓𝑖 𝐱 ↔ 𝑓𝑖 𝐱

Bukti lengkap. ∎

1 𝐚𝑖

2

𝐚𝑖 𝐚𝑇𝑖 .

23

Lampiran 3 Pembuktian Persamaan (9) Diketahui Persamaan (4), yaitu 𝐹 𝐱; 𝐛 = 𝑓1 ∘ 𝑓2 ∘ ⋯ ∘ 𝑓𝑀 𝐱 = 𝑓1 𝑓2 ⋯ 𝑓𝑀 𝐱

⋯

,

Persamaan (6), yaitu 𝑓𝑖 𝐱 = 𝑃𝑖 𝐱 +

𝑏𝑖 𝐚𝑖

2

untuk 𝑖 = 1, 2, … , 𝑀,

𝐚𝑖

Persamaan (8), yaitu 𝑀

𝑅𝐛 = 𝑖=1

𝑏𝑖 𝐚𝑖

2

𝑄𝑖−1 𝐚𝑖 ,

dan 𝑄𝑖 = 𝑃1 𝑃2 … 𝑃𝑖 (𝑖 = 1, 2, … , 𝑀) dengan 𝑄0 = 𝐼. Akan dibuktikan bahwa Persamaan (4) ekivalen dengan Persamaan (9), yaitu 𝐹 𝐱; 𝐛 = 𝑄𝐱 + 𝑅𝐛 dengan matriks 𝑄 = 𝑄𝑀 . Bukti: 𝐹 𝐱; 𝐛 = 𝑄𝐱 + 𝑅𝐛 𝑀

𝑏𝑖 𝐚𝑖

↔ 𝐹 𝐱; 𝐛 = 𝑃1 𝑃2 … 𝑃𝑀 𝐱 + 𝑖=1

2

𝑄𝑖−1 𝐚𝑖

𝑏1 𝑏2 𝑏𝑀 𝑄0 𝐚1 + 𝑄1 𝐚2 + ⋯ + 𝑄 𝐚 2 2 𝐚1 𝐚2 𝐚𝑀 2 𝑀−1 𝑀 𝑏1 𝑏2 𝑏𝑀 = 𝑃1 𝑃2 … 𝑃𝑀 𝐱 + 𝐚 + 𝑃 𝐚 + ⋯+ 𝑃 𝑃 … 𝑃𝑀−1 𝐚𝑀 𝐚1 2 1 𝐚2 2 1 2 𝐚𝑀 2 1 2 𝑏2 𝑏𝑀 𝑏1 = 𝑃1 𝑃2 … 𝑃𝑀 𝐱 + 𝐚 + ⋯+ 𝑃 … 𝑃𝑀−1 𝐚𝑀 + 𝐚 𝐚2 2 2 𝐚𝑀 2 2 𝐚1 2 1 𝑏2 𝑏𝑀 = 𝑓1 𝑃2 … 𝑃𝑀 𝐱 + 𝐚2 + ⋯ + 𝑃 … 𝑃𝑀−1 𝐚𝑀 2 𝐚2 𝐚𝑀 2 2 𝑏𝑀 𝑏2 = 𝑓1 𝑃2 𝑃3 … 𝑃𝑀 𝐱 + ⋯ + 𝑃3 … 𝑃𝑀−1 𝐚𝑀 + 𝐚 2 𝐚𝑀 𝐚2 2 2 𝑏𝑀 = 𝑓1 𝑓2 𝑃3 … 𝑃𝑀 𝐱 + ⋯ + 𝑃 … 𝑃𝑀−1 𝐚𝑀 𝐚𝑀 2 3

↔ 𝐹 𝐱; 𝐛 = 𝑃1 𝑃2 … 𝑃𝑀 𝐱 + ↔ 𝐹 𝐱; 𝐛 ↔ 𝐹 𝐱; 𝐛 ↔ 𝐹 𝐱; 𝐛 ↔ 𝐹 𝐱; 𝐛 ↔ 𝐹 𝐱; 𝐛 ⋮

↔ 𝐹 𝐱; 𝐛 = 𝑓1 𝑓2 ⋯ 𝑃𝑀 𝐱 + ↔ 𝐹 𝐱; 𝐛 = 𝑓1 𝑓2 ⋯ 𝑓𝑀 𝐱 Bukti lengkap. ∎

𝑏𝑀 𝐚𝑀

⋯

.

2

𝐚𝑀 ⋯

24

Lampiran 4 Bukti Persamaan (10) Berdasarkan Persamaan (5) dan (9), untuk 𝐛 = 𝟎 diperoleh 𝐱

𝑛+1

=𝐹 𝐱

𝑛

; 𝟎 = 𝑄𝐱

𝑛

,

Akan dibuktikan (dengan menggunakan Induksi Matematika) bahwa 𝐱

𝑛

= 𝑄𝑛 𝐱

𝐱

1

0

,

untuk setiap 𝑛 ∈ ℕ. Bukti:  Untuk 𝑛 = 1, Ruas kiri: = 𝑄𝐱

0

.

Ruas kanan: 𝑄𝐱 0 . Ruas kiri sama dengan ruas kanan, berarti benar untuk 𝑛 = 1.  Anggap benar untuk 𝑛 = 𝑚, 𝑚 ∈ ℕ, yaitu 𝐱

𝑚

= 𝑄𝑚 𝐱

0

.

 Akan dibuktikan bahwa benar untuk 𝑛 = 𝑚 + 1, 𝑚 ∈ ℕ, yaitu 𝐱

𝑚 +1

= 𝑄𝑚 +1 𝐱

0

Bukti: 𝐱

𝑚 +1

Terbukti benar untuk 𝑛 = 𝑚 + 1, 𝑚 ∈ ℕ. Bukti lengkap. ∎

= 𝑄𝐱 𝑚 = 𝑄𝑄𝑚 𝐱 0 = 𝑄𝑚 +1 𝐱 0 .

.

25

Lampiran 5 Pembuktian Persamaan (11) Berdasarkan Persamaan (5) dan (9), untuk 𝐛 = 𝟎 diperoleh 𝑛+1

𝐱

𝑛

=𝐹 𝐱

; 𝟎 = 𝑄𝐱

𝑛

,

dan berdasarkan bagian pertama dari Teorema 4.3.6, diperoleh 𝑄 = 𝑃𝒦 + 𝑄 = 𝑃𝒦 + 𝑄𝑃ℐ . Akan dibuktikan (dengan menggunakan Induksi Matematika) bahwa 𝑛

𝐱

0

= 𝑃𝒦 𝐱

+ 𝑄𝑛 𝐱

0

,

∈ Im 𝐴𝑇

∈ Ker 𝐴

untuk setiap 𝑛 ∈ ℕ. Bukti:  Untuk 𝑛 = 1, Ruas kiri: 𝐱

1

= 𝑄𝐱

0

.

Ruas kanan: 𝑃𝒦 𝐱

0

+ 𝑄𝐱

0

= 𝑃𝒦 + 𝑄 𝐱

0

= 𝑄𝐱

0

.

∈ Im 𝐴𝑇

∈ Ker 𝐴

Ruas kiri sama dengan ruas kanan, berarti benar untuk 𝑛 = 1.  Anggap benar untuk 𝑛 = 𝑚, 𝑚 ∈ ℕ, yaitu 𝐱

𝑚

0

= 𝑃𝒦 𝐱

+ 𝑄𝑚 𝐱

0

.

∈ Im 𝐴𝑇

∈ Ker 𝐴

 Akan dibuktikan bahwa benar untuk 𝑛 = 𝑚 + 1, 𝑚 ∈ ℕ, yaitu 𝑚 +1

𝐱

0

= 𝑃𝒦 𝐱

+ 𝑄 𝑚 +1 𝐱

0

.

+ 𝑄𝑃ℐ 𝑃𝒦 𝐱

0

∈ Im 𝐴𝑇

∈ Ker 𝐴

Bukti: 𝐱

𝑚 +1

= 𝑄𝐱

𝑚

= 𝑃𝒦 + 𝑄

0

𝑃𝒦 𝐱

+ 𝑄𝑚 𝐱

∈ Ker 𝐴

= 𝑃𝒦 𝑃𝒦 𝐱

0

𝑚

+ 𝑃𝒦 𝑄 𝐱

= 𝑃𝒦 𝐱 =

∈ Ker 𝐴 𝑃𝒦 𝐱 0 ∈ Ker 𝐴

∈ Im 𝐴𝑇 0

∈ Im 𝐴𝑇 𝑚 +1

∈ Ker 𝐴 0

0

+ 𝟎 + 𝑄𝟎 + 𝑄

∈ Ker 𝐴

𝐱

∈ Im 𝐴𝑇

+ 𝑄 𝑚 +1 𝐱 ∈ Im 𝐴𝑇


0

.

0

+ 𝑄 𝑄𝑚 𝐱

0

∈ Im 𝐴𝑇

26

Lampiran 6 Pembuktian Persamaan (12) Berdasarkan Persamaan (5) dan (9), diperoleh 𝑛+1

𝐱

=𝐹 𝐱

𝑛

; 𝐛 = 𝑄𝐱

𝑛

+ 𝑅𝐛.

Akan dibuktikan (dengan menggunakan Induksi Matematika) bahwa 𝑛−1

𝐱

𝑛

= 𝑄𝑛 𝐱

0

𝑄𝑘 𝑅

+

𝐛,

𝑘=0

untuk setiap 𝑛 ∈ ℕ. Bukti:  Untuk 𝑛 = 1, Ruas kiri: 𝐱

1

0

= 𝑄𝐱

+ 𝑅𝐛.

Ruas kanan: 0

𝑄𝐱

0

𝑄𝑘 𝑅

+

𝐛 = 𝑄𝐱

0

+ 𝑄0 𝑅𝐛 = 𝑄𝐱

0

+ 𝑅𝐛.

𝑘=0

Ruas kiri sama dengan ruas kanan, berarti benar untuk 𝑛 = 1.  Anggap benar untuk 𝑛 = 𝑚, 𝑚 ∈ ℕ, yaitu 𝑚 −1

𝐱

𝑚

= 𝑄𝑚 𝐱

0

𝑄𝑘 𝑅

+

𝐛.

𝑘=0

 Akan dibuktikan bahwa benar untuk 𝑛 = 𝑚 + 1, 𝑚 ∈ ℕ, yaitu 𝑚

𝐱

𝑚 +1

=𝑄

𝑚 +1

𝐱

0

𝑄𝑘 𝑅

+

𝐛.

𝑘=0

Bukti: 𝐱

𝑚 +1

= 𝑄𝐱

𝑚

+ 𝑅𝐛 𝑚 −1 𝑚

=𝑄 𝑄 𝐱

0

𝑄𝑘 𝑅

+

𝐛 + 𝑅𝐛

𝑘=0 𝑚 −1

= 𝑄𝑚 +1 𝐱

0

𝑄𝑘 𝑅

𝐛 + 𝑅𝐛

𝑄𝑘 +1 𝑅

𝐛 + 𝑅𝐛

+𝑄 𝑘=0 𝑚 −1

= 𝑄𝑚 +1 𝐱

0

+ 𝑘=0 𝑚

= 𝑄𝑚 +1 𝐱

0

+

𝑄𝑘 𝑅

𝐛 + 𝑄0 𝑅𝐛

𝑄𝑘 𝑅

𝐛.

𝑘=1 𝑚

= 𝑄𝑚 +1 𝐱

0

+ 𝑘=0


27

Lampiran 7 Program MATLAB dari algoritme untuk metode Kaczmarz Fungsi kaczmarz function x = kaczmarz(A,b,x0) %--------------------------------------------------------------------------------% Fungsi kaczmarz menghasilkan penyelesaian hampiran atas sistem persamaan linear % (SPL) Ax=b : % a11*x1 + a12*x2 + ... + a1N*xN = b1 % a21*x1 + a22*x2 + ... + a2N*xN = b2 % : % aM1*x1 + aM2*x2 + ... + aMN*xN = b3 % menggunakan metode Kaczmarz. %--------------------------------------------------------------------------------% Input: % A = matriks berorde M x N (matriks koefisien dari SPL) % a11 a12 ... a1N % a21 a22 ... a2N % : % aM1 aM2 ... aMN % b = vektor kolom berorde M x 1 (vektor konstanta dari SPL) % b1 % b2 % : % bM % x0 = vektor kolom berorde N x 1 (penyelesaian hampiran awal) % % Input tambahan: % iter = banyaknya iterasi % harus berupa bilangan asli % default: 100 % atau % tol = batas toleransi % harus berupa bilangan real positif % default: 10^(-6) % % Output: % x = vektor kolom berorde Nx1 (penyelesaian hampiran) % x1 % x2 % : % xN %--------------------------------------------------------------------------------% Cek banyaknya input if (nargin < 3) error('Input terlalu sedikit.'); elseif (nargin > 3) error('Input terlalu banyak.'); end [M,N] = size(A); % Orde A, b, dan x0 harus cocok if (size(b,1) ~= M) error('Orde matriks A dan vektor b tidak cocok.'); elseif (size(b,2) ~= 1) error('b harus berbentuk vektor kolom.'); elseif (size(x0,1) ~= N || size(x0,2) ~= 1) error('Orde x0 tidak cocok dengan masalah.') end x = zeros(N,1); % Penentuan kriteria pemberhentian disp('Apakah kriteria pemberhentian akan ditentukan sendiri?'); disp('Pilih : 1 atau 0'); disp('1 : Ya'); disp('0 : Tidak'); jawab = input('Jawab : '); if (isempty(jawab)) error('Tidak ada jawaban.');

28

Lampiran 7 (lanjutan) elseif (jawab ~= 1 && jawab ~= 0) error('Jawaban harus berupa bilangan 1 atau 0.'); elseif (jawab == 0) disp('Kriteria pemberhentian:') disp('Banyaknya iterasi = 100 atau batas toleransi = 10^(-6).'); maksiter = 100; % Nilai default tol = 10^(-6); % Nilai default iter = 1; for k = 1:M x = x0+(b(k)-A(k,:)*x0)*A(k,:)'/(norm(A(k,:))^2); x0 = x; end d = norm(A*x-b); while (iter <= maksiter && d > tol) iter = iter+1; for i = 1:iter for k = 1:M x = x0+(b(k)-A(k,:)*x0)*A(k,:)'/(norm(A(k,:))^2); x0 = x; end end d = norm(A*x-b); end disp(['Pada iterasi ke-', num2str(iter)]); disp(['diperoleh penyelesaian hampiran dengan norm sisaan sebesar ', num2str(d)]); else disp('Pilih kriteria pemberhentian (1, 2, atau 3)'); disp('1 : Banyaknya iterasi'); disp('2 : Batas toleransi'); disp('3 : Keduanya'); itertol = input('Pilihan : '); if (isempty(itertol)) error('Tidak ada kriteria pemberhentian yang dipilih.'); elseif (itertol ~= 1 && itertol ~= 2 && itertol ~=3) error('Input harus berupa bilangan 1, 2 atau 3.'); elseif (itertol == 1) disp('Masukkan banyaknya iterasi!'); disp('Banyaknya iterasi harus berupa bilangan asli.'); iter = input('Banyaknya iterasi = '); if (isempty(iter)) error('Tidak ada input sebagai banyaknya iterasi.'); elseif (iter < 1 || (fix(iter)-iter) ~= 0) error('Banyaknya iterasi harus berupa bilangan asli.'); else for i = 1:iter for k = 1:M x = x0+(b(k)-A(k,:)*x0)*A(k,:)'/(norm(A(k,:))^2); x0 = x; end end d = norm(A*x-b); disp(['Pada iterasi ke-', num2str(iter)]); disp(['diperoleh penyelesaian hampiran dengan norm sisaan sebesar ', num2str(d)]); end elseif (itertol == 2) disp('Masukkan batas toleransi!'); disp('Batas toleransi harus berupa bilangan real positif.'); tol = input('Batas toleransi = '); if (isempty(tol)) error('Tidak ada input sebagai batas toleransi.'); elseif (tol <= 0) error('Batas toleransi harus berupa bilangan real positif.'); else iter = 1;

29

Lampiran 7 (lanjutan) for k = 1:M x = x0+(b(k)-A(k,:)*x0)*A(k,:)'/(norm(A(k,:))^2); x0 = x; end d = norm(A*x-b); while d > tol iter = iter+1; for k = 1:M x = x0+(b(k)-A(k,:)*x0)*A(k,:)'/(norm(A(k,:))^2); x0 = x; end d = norm(A*x-b); end disp(['Pada iterasi ke-', num2str(iter)]); disp(['diperoleh penyelesaian hampiran dengan norm sisaan sebesar ', num2str(d)]); end else disp('Pertama, masukkan banyaknya iterasi!'); disp('Banyaknya iterasi harus berupa bilangan asli.'); iter = input('Banyaknya iterasi = '); if (isempty(iter)) error('Tidak ada input sebagai banyaknya iterasi.'); elseif (iter < 1 || (fix(iter)-iter) ~= 0) error('Banyaknya iterasi harus berupa bilangan asli.'); else maksiter = iter; end disp('Kedua, masukkan batas toleransi!'); disp('Batas toleransi harus berupa bilangan real positif.'); tol = input('Batas toleransi = '); if (isempty(tol)) error('Tidak ada input sebagai batas toleransi.'); elseif (tol <= 0) error('Batas toleransi harus berupa bilangan real positif.'); end iter = 1; for k = 1:M x = x0+(b(k)-A(k,:)*x0)*A(k,:)'/(norm(A(k,:))^2); x0 = x; end d = norm(A*x-b); while (iter <= maksiter && d > tol) iter = iter+1; for i = 1:iter for k = 1:M x = x0+(b(k)-A(k,:)*x0)*A(k,:)'/(norm(A(k,:))^2); x0 = x; end end d = norm(A*x-b); end disp(['Pada iterasi ke-', num2str(iter)]); disp(['diperoleh penyelesaian hampiran dengan norm sisaan sebesar ', num2str(d)]); end end end

30

Lampiran 8 Program MATLAB untuk membangkitkan matriks koefisien dan vektor konstanta dari SPL ke-1 Fungsi blur function [A,b] = blur(N,band,sigma) %--------------------------------------------------------------------------------% Masalah uji BLUR: Memburamkan gambar digital. % % Matriks A adalah matriks simetrik berukuran (N^2)x(N^2), matriks Toeplitz blok % ganda yang memodelkan pemburaman suatu gambar berukuran NxN dengan suatu fungsi % pemancaran titik Gauss. Ini disimpan dalam format matriks sparse. % % Pada setiap blok Toeplitz, hanya elemen-elemen matriks dalam suatu jarak band-1 % dari diagonal yang merupakan taknol (band adalah setengah bandwidth). Jika band % tidak dirinci, digunakan band = 3. % % Parameter sigma mengontrol lebar dari fungsi pemancaran titik Gauss dan % akibatnya jumlah pemulusan. Jika sigma tidak dirinci, digunakan sigma = 0.7. % % Vektor x adalah suatu versi kolom yang ditumpuk dari suatu gambar uji sederhana, % sedangkan vektor b adalah suatu versi kolom yang ditumpuk dari gambar yang % diburamkan, yaitu b = A*x. %--------------------------------------------------------------------------------% Inisialisasi if (nargin < 2) band = 3; end band = min(band,N); if (nargin < 3) sigma = 0.7; end % z A A A

Mengonstruksi matriks koefisien A = [exp(-([0:band-1].^2)/(2*sigma^2)),zeros(1,N-band)]; = toeplitz(z); = sparse(A); = (1/(2*pi*sigma^2))*kron(A,A);

% Mengonstruksi vektor konstanta b x = zeros(N,N); N2 = round(N/2); N3 = round(N/3); N6 = round(N/6); N12 = round(N/12); T = zeros(N6,N3); for i = 1:N6 for j = 1:N3 if ((i/N6)^2 + (j/N3)^2 < 1) T(i,j) = 1; end end end T = [fliplr(T),T]; T = [flipud(T);T]; x(2+[1:2*N6],N3-1+[1:2*N3]) = T; T = zeros(N6,N3); for i = 1:N6 for j = 1:N3 if ((i/N6)^2 + (j/N3)^2 < 0.6) T(i,j) = 1; end end end T = [fliplr(T),T]; T = [flipud(T);T]; x(N6+[1:2*N6],N3-1+[1:2*N3]) = x(N6+[1:2*N6],N3-1+[1:2*N3]) + 2*T;

31

Lampiran 8 (lanjutan) f = find(x==3); x(f) = 2*ones(size(f)); T = triu(ones(N3,N3)); [mT,nT] = size(T); x(N3+N12+[1:nT],1+[1:mT]) = 3*T; T = zeros(2*N6+1,2*N6+1); [mT,nT] = size(T); T(N6+1,1:nT) = ones(1,nT); T(1:mT,N6+1) = ones(mT,1); x(N2+N12+[1:mT],N2+[1:nT]) = 4*T; x = reshape(x(1:N,1:N),N^2,1); b = A*x; end

32

Lampiran 9 Program MATLAB untuk membangkitkan matriks koefisien dan vektor konstanta dari SPL ke-2 Fungsi phillips function [A,b] = phillips(n) %--------------------------------------------------------------------------------% Diskretisasi persamaan Fredholm jenis pertama ditemukan oleh D. L. Phillips. % Didefinisikan fungsi % phi(x) = | 1 + cos(x*pi/3) , |x| < 3 . % | 0 , |x| >= 3 % maka kernel K, penyelesaian f, dan ruas kanan g diberikan oleh: % K(s,t) = phi(s-t) , % f(t) = phi(t) , % g(s) = (6-|s|)*(1+.5*cos(s*pi/3)) + 9/(2*pi)*sin(|s|*pi/3) . % Interval integrasi adalah [-6,6]. % % Didiskretisasi dengan metode Galerkin. % % Input : n harus kelipatan 4. %--------------------------------------------------------------------------------% Cek input if (rem(n,4)~=0) error('n harus kelipatan 4'); end % Mengonstruksi matriks koefisien A h = 12/n; n4 = n/4; r1 = zeros(1,n); c = cos((-1:n4)*4*pi/n); r1(1:n4) = h + 9/(h*pi^2)*(2*c(2:n4+1) - c(1:n4) - c(3:n4+2)); r1(n4+1) = h/2 + 9/(h*pi^2)*(cos(4*pi/n)-1); A = toeplitz(r1); % Mengonstruksi vektor konstanta b b = zeros(n,1); c = pi/3; for i = n/2+1:n t1 = -6 + i*h; t2 = t1 - h; b(i) = t1*(6-abs(t1)/2) ... + ((3-abs(t1)/2)*sin(c*t1) - 2/c*(cos(c*t1) - 1))/c ... - t2*(6-abs(t2)/2) ... - ((3-abs(t2)/2)*sin(c*t2) - 2/c*(cos(c*t2) - 1))/c; b(n-i+1) = b(i); end b = b/sqrt(h); end

33

Lampiran 10 Program MATLAB untuk membangkitkan matriks koefisien dan vektor konstanta dari SPL ke-3 Fungsi tomo function [A,b,x] = tomo(N,f) %--------------------------------------------------------------------------------% TOMO: Membuat suatu masalah uji tomografi 2D % % Fungsi ini membuat suatu masalah uji tomografi dua dimensi sederhana. Suatu % domain 2D [0,N]x[0,N] dibagi ke dalam N^2 sel dengan ukuran satuan dan sejumlah % round(f*N^2) sinar pada arah acak yang menembus domain ini. Nilai default % adalah f=1. % % Setiap sel bersesuaian dengan suatu nilai dalam vektor x dan setiap sinar % bersesuaian dengan elemen dalam vektor konstanta b, yaitu % sum_{cells in ray} x_{cell j} * length_{cell j} % dengan length_{cell j} adalah panjang sinar pada sel ke-j. % % Matriks A adalah sparse, dan setiap baris (bersesuaian dengan suatu sinar) % memegang nilai length_{cell j} pada posisi ke-j. Oleh karena itu: % b = A*x . % Apabila suatu penyelesaian x_reg telah dihitung, ini dapat divisualisasikan % dengan mengartikan imagesc(reshape(x_reg,N,N)). % % Penyelesaian eksak, reshape(x,N,N), identik dengan gambar eksak pada fungsi % blur. %--------------------------------------------------------------------------------% Nilai default if nargin==1 f = 1; end % Mengonstruksi matriks koefisien A A = spalloc(N,N,2*N); x = (0:N)'; y = x; for i = 1:round(f*N^2) x0 = N*rand; x1 = N*rand; y0 = N*rand; y1 = N*rand; a = (y1-y0)/(x1-x0); b = y0 - a*x0; yp = a*x + b; xp = (y - b)/a; xp = [x;xp]; yp = [yp;y]; [xp,I] = sort(xp); yp = yp(I); I = find(xp >= 0 & xp <= N & yp >= 0 & yp <= N); xp = xp(I); yp = yp(I); I = find(diff(xp)==0); xp(I) = []; yp(I) = []; d = sqrt( diff(xp).^2 + diff(yp).^2 ); xm = 0.5*(xp(1:end-1)+xp(2:end)); ym = 0.5*(yp(1:end-1)+yp(2:end)); j = ( floor(xm) )*N + floor(ym) + 1; A(i,j) = d'; end

34

Lampiran 10 (lanjutan) x = zeros(N,N); N2 = round(N/2); N3= round(N/3); N6 = round(N/6); N12 = round(N/12); T = zeros(N6,N3); for i = 1:N6 for j = 1:N3 if ((i/N6)^2 + (j/N3)^2 < 1) T(i,j) = 1; end end end T = [fliplr(T),T]; T = [flipud(T);T]; x(2+(1:2*N6),N3-1+(1:2*N3)) = T; T = zeros(N6,N3); for i = 1:N6 for j = 1:N3 if ((i/N6)^2 + (j/N3)^2 < 0.6) T(i,j) = 1; end end end T = [fliplr(T),T]; T = [flipud(T);T]; x(N6+(1:2*N6),N3-1+(1:2*N3)) = x(N6+(1:2*N6),N3-1+(1:2*N3)) + 2*T; f = find(x==3); x(f) = 2*ones(size(f)); T = triu(ones(N3,N3)); [mT,nT] = size(T); x(N3+N12+(1:nT),1+(1:mT)) = 3*T; T = zeros(2*N6+1,2*N6+1); [mT,nT] = size(T); T(N6+1,1:nT) = ones(1,nT); T(1:mT,N6+1) = ones(mT,1); x(N2+N12+(1:mT),N2+(1:nT)) = 4*T; x = reshape(x(1:N,1:N),N^2,1); % Mengonstruksi vektor konstanta b b = A*x; end

35

Lampiran 11 Norm sisaan dari penyelesaian hampiran atas ketiga SPL yang digunakan yang diperoleh pada iterasi ke-0 sampai iterasi ke-30 Iterasi ke0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

SPL ke-1 15.4392 10.6021 7.2495 4.7998 3.0725 2.0196 1.3670 0.9012 0.5614 0.3748 0.2860 0.2406 0.2104 0.1871 0.1685 0.1538 0.1420 0.1322 0.1237 0.1163 0.1097 0.1039 0.0986 0.0938 0.0894 0.0853 0.0816 0.0782 0.0750 0.0720 0.0693

Norm sisaan dari penyelesaian hampiran SPL ke-2 SPL ke-3 15.2906 207.3483 14.9492 31.1586 13.0457 14.0032 3.9800 8.8950 1.9818 6.6116 0.9924 5.5046 0.5148 4.8414 0.2770 4.3556 0.1597 3.9637 0.1062 3.6390 0.0859 3.3698 0.0798 3.1479 0.0782 2.9659 0.0775 2.8169 0.0766 2.6945 0.0754 2.5934 0.0737 2.5089 0.0717 2.4373 0.0695 2.3756 0.0671 2.3217 0.0646 2.2739 0.0621 2.2308 0.0595 2.1917 0.0570 2.1559 0.0545 2.1228 0.0520 2.0923 0.0497 2.0639 0.0474 2.0375 0.0452 2.0129 0.0430 1.9901 0.0410 1.9688

METODE KACZMARZ UNTUK MENYELESAIKAN SISTEM PERSAMAAN LINEAR RUHIYAT

Recommend Documents