PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI RESTORASI GAMBAR DIGITAL MENGGUNAKAN INVERSE PROBLEM

Skripsi

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

Disusun Oleh : Pandu Arya Wijaya NIM: 103114012

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

PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI RESTORASI GAMBAR DIGITAL MENGGUNAKAN INVERSE PROBLEM

Skripsi

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

Disusun Oleh : Pandu Arya Wijaya NIM: 103114012

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

PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI DIGITAL IMAGE RESTORATION USING INVERSE PROBLEM

Thesis

Presented as Partial Fulfillment of the Requirements to Obtain the Sarjana Sains Degree in Mathematics Study Program

Written By : Pandu Arya Wijaya Student Number: 103114012

MATHEMATICS STUDY PROGRAM MATHEMATICS DEPARTMENT FACULTY OF SCIENCE AND TECHNOLOGY SANATA DHARMA UNIVERSITY YOGYAKARTA 2015 ii

a PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI

SKRIPSI

RESTORASI GAMBAR DIGITAL

MENGGI'NAKAN INVERSE PROBLEM

Disusutr Oleh: Pandu Arya Wijaya

NIM: 103114012

Telah disetujui oleh:

Dosen Pembimbing Slripsi,

Taneeal -

(Hadono, S.Si., M.Sc-, Ph.D)

lll

/3/d/ /2ol <'

PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI

SKRIPSI

RESTORASI GAMBAR DIGITAL MENGGTJNAKAI\I NTVERSE PROBLEM Dipersiapkan dan ditutis oleh :

Patdu Arya Wiiaya

NIM: l03l l,l0l2

Telab dipe alErkan di depan Paoitia P€nguji

psda rugal

17 Des€oDber

2014

dan dinyatakan telah m€metruhi syaiat

Susuan Panitia Penguji Nama I engkef

Ketua

:

h. Ig. Ads Ilwiahoko, M.Sc.

Sekretaris : Dr. rer-nat Horry Pdbar.,aoto Surlawa!. M.Si.

Anggota : Harto.o,

S.Si., M.Sc., Ph.D.

Y os$klirt,- ...P-....

| L?.2!.?:....? 5

Fakultas Sains dan Teknologi


HALAMAN PERSEMBAHAN

Karya ini adalah hadiah terindah Yesus Kristus untuk kado Natal 2014.

“Terpujilah TUHAN, karena Ia telah mendengar suara permohonanku. TUHAN adalah kekuatanku dan perisaiku; kepada-Nya hatiku percaya. Aku tertolong sebab itu beria-ria hatiku, dan dengan nyanyianku aku bersyukur kepada-Nya”. (Mazmur 28:6-7)

Karya ini aku persembahkan untuk: Allah Bapa, Putra dan Roh Kudus, Papa, Mama dan Adikku tercinta, Kekasih hatiku tersayang, Teman-teman matematika angkatan 2010, Serta orang-orang yang selalu berada di sisi saya.

v

1 PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI

PER}TYATAAN KEASLIAN KARYA

Saya menyatakan dengan sesungguhnya bahwa skipsi yang saya tulis

memuat karya atau bagian

kfiya ora[g lain, kecuali yang

ini tidak

disebutkan dalam

kutipan dan daffar pustaka, sebagaimana layaknya kaxya ilmiah.

Yogyakart4 Desember Penulis

v

Pardu Arya Wijaya

20 I 4


ABSTRAK

Pandu Arya Wijaya. 2014. Restorasi Gambar Digital Menggunakan Inverse Problem. Skripsi. Program Studi Matematika, Jurusan Matematika, Fakultas Sains dan Teknologi, Universitas Sanata Dharma, Yogyakarta. Topik yang dibahas dalam skripsi ini adalah aplikasi inverse problem dalam restorasi gambar, terutama restorasi gambar digital. Inverse Problem merupakan suatu metode penyelesaian masalah menggunakan invers dari permasalahan yang diselesaikan. Tulisan ini akan membahas bagaimana mengurangi efek kabur pada gambar digital dengan meminimalkan galat yang terjadi, sehingga diperoleh hasil restorasi yang memuat galat terkecil. Untuk itu, diperlukan suatu kontrol galat dengan cara menghitung besarnya norma pada gambar hasil restorasi. Dalam hal ini, teori matematika yang digunakan adalah Singular Value Decomposition (SVD) dan model permasalahan inversnya adalah model gambar kabur. Model gambar kabur merupakan transformasi gambar asli berdasarkan operator pengaburan. Model gambar kabur akan ditransformasi menjadi gambar yang lebih baik (noise minimum) dengan metode Truncated Singular Value Decomposition (TSVD) dan metode Regularisasi Tikhonov.

Kata Kunci: restorasi gambar, inverse problem, norma, gambar kabur, Singular Value Decomposition, Truncated Singular Value Decomposition, Regularisasi Tikhonov.

vii


ABSTRACT

Pandu Arya Wijaya. 2014. Digital Image Restoration Using Inverse Problem. Thesis. Mathematics Study Program, Department of Mathematics, Faculty of Science and Technology, Sanata Dharma University, Yogyakarta. The topic of this thesis is the application of inverse problems in image restoration, especially in digital image restoration. Inverse Problem is a problem solving method using inverse of problem being solved. This paper discuss how to reduce the blurring effect on digital image by minimizing the error, such that the restoration results obtained has a minimum error. For this purpose, we need to control the error by calculate the norm of image restoration. In this case, we need a mathematical theory so called Singular Value Decomposition (SVD) and the model of inverse problem is blurred image model. Blurred image model is an original image transformed by blurring operator. The blurred image model will be transformed into a clearer image (with minimum noise) using Truncated Singular Value Decomposition (TSVD) method and Tikhonov regularization method.

Keywords: images restoration, inverse problem, norm, blurred image, Singular Value Decomposition, Truncated Singular Value Decomposition, Tikhonov regularization.

viii


LEMBAR PER}TYATAAN PERSf, TUJUAN PUBLIKASI KARYA ILMIAII I]NTUK KEPENTINGAII AKADEMIS

Yang bertandatangan di bawah ini, saya mahasiswa Universitas Sanata Dharna:

Nama

: Pandu

NIM

:103114012

Arya Wijaya

demi pengembangan ilmu pengetahuan, saya memberikan karya ilmiah

saya

kepada Perpustakaan Univemitas Sanata Dharma yang bedudul:

RESTORASI GAMBAR DIGITAL

MENGGIJNAKAN IN\'ERSE PROBLEM beserta perangkal yang diperlukao (bila ada). Dengan demikian saya memberikan

kepada Perpustakaan Uriversitas Sanata Dhaxma hak untuk menyimpan, mengalihkan dalam bentuk media lain, mengelolanya dalam bentuk pangkalan

dat4 mendistribusikannya

secara terbatas, dan mempublikasikannya

di internet

atau media lain untuk kepentingan akad€mis tanpa meminta izin dari saya maupun

memberikan royalti kepada saya selama tetap mencal-up nama saya sebagai penulis.

Demikian pemyataan ini saya buat dengan sebenaxnya.

Dibuat di Yogyakarta Pada

tarygal: 7 Januari 2015

Yang menyatakan,

A

W

(Pandu Arya Wijaya)


KATA PENGANTAR

Puji dan syukur penulis panjatkan kepada Tuhan Yesus Kristus yang telah melimpahkan berkat dan kasihNya sehingga penulis dapat menyelesaikan skripsi ini dengan baik. Dalam penulisan skripsi ini penulis mendapatkan bantuan baik moril maupun materiil dari berbagai pihak. Oleh karena itu, penulis ingin mengucapkan terima kasih kepada: 1. Ibu Paulina Heruningsih Prima Rosa, S.Si., M.Sc., selaku Dekan Fakultas Sains dan Teknologi, Universitas Sanata Dharma. 2. YG. Hartono, S.Si., M.Sc., Ph.D, selaku dosen pembimbing skripsi dan Ketua Program Studi Matematika yang telah meluangkan banyak waktu dan membimbing penulis dengan penuh kesabaran. 3. Ir. Ig. Aris Dwiatmoko, M.Sc., selaku dosen pembimbing akademik. 4. Bapak, Ibu, dan Romo, dosen-dosen yang telah memberikan ilmu yang berguna kepada penulis. 5. Kedua orang tua, Bapak Bambang Wijaya dan Ibu Tri Endang Hidrayani, yang selalu mendukung penulis dengan doa, semangat, dan materi. 6. Teman-temanku: Arga, Ratri, Ayu, Tika, Astri, Sari, Dini, Celly, Leni, Agnes, Yohan, Roy, Marsel, dan Yosi, terima kasih untuk canda tawa, kebersamaan, dan semangat yang selalu diberikan pada penulis.

x


7. Teman-teman 2009, 2011 dan 2012: Jojo, Indra, Bayu, Rian, Budi, Ega, Happy, Tika terima kasih untuk doa, semangat, dan keceriaan yang selalu diberikan kepada penulis. 8. Semua pihak yang telah ikut membantu penulis dalam menyelesaikan skripsi ini.

Penulis menyadari bahwa skripsi ini masih jauh dari sempurna. Oleh karena itu, penulis mengharapkan kritik dan saran yang dapat membangun serta menyempurnakan skripsi ini. Akhirnya, penulis berharap semoga skripsi ini dapat memberikan wawasan dan pengetahuan bagi pembaca.

Yogyakarta, Desember 2014

Penulis

xi


DAFTAR ISI

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

i

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

ii

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

iii

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

iv

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

v

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

vi

ABSTRAK ...................................................................................................... vii ABSTRACT .................................................................................................... viii PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH ............

ix

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

x

DAFTAR ISI ................................................................................................... xii DAFTAR GAMBAR ...................................................................................... xv DAFTAR TABEL ........................................................................................... xvii DAFTAR PROGRAM .................................................................................... xviii BAB I PENDAHULUAN ...............................................................................

1

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

1

B. Perumusan Masalah ............................................................................

7

C. Pembatasan Masalah ...........................................................................

8

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

8

E. Manfaat Penulisan ...............................................................................

9

xii


F. Metode Penulisan ................................................................................

9

G. Sistematika Penulisan ......................................................................... 10 BAB II LANDASAN TEORI ......................................................................... 12 A. Aljabar Linier ...................................................................................... 12 2.1 Sistem Persamaan Linier Homogen ...................................... 12 2.2 Ruang Vektor ........................................................................ 13 2.3 Ortogonalitas ......................................................................... 22 2.4 Nilai Eigen dan Vektor Eigen ............................................... 34 2.5 Dekomposisi Nilai Singular .................................................. 36 2.6 Norma Matriks dan Bilangan Kondisi .................................. 49 B. Kalkulus .............................................................................................. 65 2.7 Big-O ..................................................................................... 65 2.8 Fungsi Bernilai Vektor .......................................................... 66 BAB III INVERSE PROBLEM ...................................................................... 70 A. Prinsip Dasar Inverse Problem ............................................................ 70 3.1 Kestabilan Algoritma pada Sistem ........................................ 71 3.2 Eksistensi dan Ketunggalan Penyelesaian ............................ 75 B. Metode Regularisasi ............................................................................ 85 3.3 Regularisasi ........................................................................... 85 3.4 Regularisasi Tikhonov .......................................................... 91 BAB IV APLIKASI ........................................................................................ 94 A. Gambar Digital .................................................................................... 94 4.1 Representasi Gambar Digital ................................................ 94

xiii


4.2 Model Degradasi Gambar Digital ......................................... 96 B. Restorasi Gambar menggunakan TSVD ............................................. 98 C. Restorasi Gambar menggunakan Regularisasi Tikhonov ................... 107 BAB V PENUTUP ........................................................................................... 117 A. Kesimpulan .......................................................................................... 117 B. Saran .................................................................................................... 118 DAFTAR PUSTAKA ..................................................................................... 119 LAMPIRAN .................................................................................................... 120

xiv


DAFTAR GAMBAR

Halaman Gambar 1.1 Contoh Gambar Sebelum dan Sesudah Restorasi ......................

3

Gambar 1.2 Contoh Gambar Sebelum dan Sesudah Restorasi .......................

3

Gambar 1.3 Contoh Gambar Sebelum dan Sesudah Restorasi .......................

3

Gambar 1.4 Koordinat Spasial ........................................................................

4

Gambar 1.5 Algoritma Inverse Problem .........................................................

7

Gambar 2.1 Hubungan geometris di antara 𝐱 dan 𝐴𝐱 ..................................... 34 Gambar 3.1 Prosedur metode Inverse Problem .............................................. 70 Gambar 4.1 Gambar Asli dan Gambar kabur .................................................. 97 Gambar 4.2 Gambar Asli ................................................................................ 101 Gambar 4.3 Gambar terkena efek motion ....................................................... 101 Gambar 4.4 Visualisasi Matriks Pengaburan .................................................. 102 Gambar 4.5 Gambar Asli hasil Restorasi TSVD dengan 𝑘 = 200 ................. 103 Gambar 4.6 Grafik TSVD ............................................................................... 104 Gambar 4.7 Grafik TSVD dengan axis([50 100 0 10]) ..................... 105 Gambar 4.8 Grafik TSVD dengan axis([70 75 5 6]).......................... 105 Gambar 4.9 Grafik TSVD dengan axis([70 75 5.7 5.8]) ................ 106 Gambar 4.10 Gambar hasil Restorasi TSVD dengan 𝑘 = 74.......................... 106 Gambar 4.11 Gambar hasil restorasi Tikhonov dengan 𝛼 = 0.01 .................. 111 Gambar 4.12 Grafik Regularisasi Tikhonov ................................................... 112 Gambar 4.13 Gambar Regularisasi Tikhonov dengan 𝛼 ∈ 0,0.2

xv


dan axis([0 0.2 0 20]) .................................................. 112 Gambar 4.14 Gambar Regularisasi Tikhonov dengan 𝛼 ∈ 0.06 , 0.12 dan axis([0.06 0.12 6 8]) ........................................... 113 Gambar 4.15 Gambar hasil restorasi regularisasi Tikhonov dengan 𝛼 = 0,0874 .................................................................... 113 Gambar 4.16 Hasil restorasi metode TSVD dan regularisasi Tikhonov ......... 115

xvi


DAFTAR TABEL

Halaman Tabel 3.1 Hasil Numerik Faktor Perbesaran Galat ......................................... 89

xvii


DAFTAR PROGRAM

Halaman Program 4.1a ................................................................................................... 120 Program 4.1b ................................................................................................... 121 Program 4.2a .................................................................................................... 122 Program 4.2b ................................................................................................... 123

xviii


BAB I PENDAHULUAN

A. Latar Belakang Masalah Dewasa ini, perkembangan teknologi dapat dikatakan sangat berkembang pesat. Banyak peralatan elektronik yang diciptakan untuk memenuhi kebutuhan manusia, baik dari membantu pekerjaan sampai memenuhi kebutuhan gaya hidup. Salah satu yang cukup berkembang adalah perkembangan gambar digital. Istilah digital merujuk pada sinyal atau data yang dinyatakan sebagai rangkaian angka 0 dan 1. Gambar digital, merupakan bentuk perwakilan visual dari sesuatu, karena gambar digital dapat digunakan sebagai sarana untuk memberikan penjelasan mengenai sesuatu. Makna visual

yang diberikan gambar dapat

memberikan informasi dengan jelas, tanpa perlu ada penyampaian informasi detail secara lisan. Karena alasan tersebut maka banyak peralatan elektronik dikembangkan guna menghasilkan ketajaman gambar yang lebih baik. Gambar dengan kualitas yang baik dapat memberikan makna visual yang jelas, sehingga tidak memberikan kesalahan persepsi bagi yang melihat. Memanipulasi gambar tentunya bukan merupakan sesuatu yang aneh lagi pada era modern seperti saat ini. Banyak gambar, seperti poster, spanduk, foto dan sebagainya dapat memiliki kualitas ketajaman gambar yang lebih bagus dari aslinya. Selain itu, dapat disaksikan juga animasi-


2

animasi menarik dari video dengan kualitas grafis yang mengagumkan. Dan itu semua, tidak lain merupakan hasil dari perkembangan teknologi yang sangat cepat dalam pemrosesan gambar digital. Salah satu bidang dalam pemrosesan gambar digital yang cukup populer adalah mengenai restorasi gambar. Restorasi berasal dari kata restore yang artinya memperbaiki. Restorasi gambar adalah cara untuk memperoleh kembali gambar asli dari gambar yang telah terdegradasi berdasarkan informasi dari model degradasi yang masuk akal. Kata degradasi dalam tulisan ini, berasal dari istilah degradation yang artinya bentuk asli yang telah turun kualitasnya karena suatu penyebab tertentu. Restorasi gambar mengambil peranan yang sangat penting dalam era gambar digital, sebab telah diketahui bahwa peralatan optik digital seperti kamera juga memiliki keterbatasan dalam menangkap gambar. Akibatnya, gambar yang dihasilkan menjadi kabur atau dalam pemrosesan signal disebut sebagai derau (noise). Adapun penyebab dari derau tersebut dapat disebabkan oleh keterbatasan alat maupun manusia. Gambar yang mengandung derau sering kali membatasi informasi yang akan disampaikan. Itu sebabnya, derau tersebut harus dihilangkan. Sebagai contoh, di bawah ini terdapat beberapa gambar yang menunjukkan perbandingan antara gambar sebelum dan sesudah dilakukan proses restorasi.


Sebelum

Sesudah

Sumber: image-restore.co.uk Gambar 1.1.

Sebelum

Sesudah

Sumber: carlmason-liebenberg.com Gambar 1.2.

Sebelum

Sesudah

Sumber: retouchphoto.net Gambar 1.3.

3


4

Dari beberapa contoh di atas, terlihat bahwa proses restorasi dapat merubah penampilan gambar menjadi lebih bagus dibandingkan dengan gambar aslinya. Kemudian, dengan melakukan restorasi ternyata dapat menghilangkan efek derau yang mengganggu kualitas gambar asli, sehingga dapat dihasilkan gambar yang lebih jelas. Untuk lebih memudahkan dalam melakukan proses restorasi, terlebih dahulu pastikan gambar yang akan direstorasi sudah dalam bentuk digital, jika belum dapat digunakan scanner untuk mengubah gambar kasar menjadi gambar digital. Gambar kasar merupakan gambar hasil karya tangan manusia misalnya lukisan. Ketika sebuah gambar sudah diubah ke dalam bentuk digital barulah proses restorasi dapat dimulai. Gambar digital dapat didefinisikan sebagai fungsi dua variabel, 𝑓(𝑥, 𝑦), dimana 𝑥 dan 𝑦 adalah koordinat spasial dan nilai 𝑓(𝑥, 𝑦) adalah intensitas (warna) gambar pada koordinat tersebut. Koordinat spasial merupakan koordinat yang digunakan untuk merepresentasikan fakta dari dunia nyata. Hal tersebut dapat diilustrasikan seperti pada gambar 1.4. f(x,y)

f(0,y)

f(0,0)

Sumber: anezblog.com Gambar 1.4.

f(x,0)


5

Namun dalam kondisi riil, terkadang didapatkan gambar yang mengalami efek derau. Hal ini menyebabkan intensitas (warna) gambar pada setiap koordinat spasial menjadi terganggu. Akibatnya, gambar yang dihasilkan menjadi kabur. Dalam usaha mengatasi kendala inilah, penulis menggunakan teknik restorasi gambar digital menggunakan Inverse Problem. Untuk definisi Inverse Problem sebenarnya belum diketahui secara pasti. Namun, penulis mencoba untuk memaparkan beberapa pendapat dari matematikawan mengenai Inverse Problem. Menurut Julia Robinson (dalam C. W. Groetsch, 1999), Inverse Problem adalah “Here you were given a solution and you had to find the equation”, artinya situasi dimana penyelesaian suatu masalah telah diberikan dan harus ditemukan bagaimana persamaannya. Menurut Per Christian Hansen (2010), “The inverse problem is to compute either the input or the system, given the other two quantities”, artinya inverse problem adalah proses mendapatkan inputatau sistem, saat diketahui dua kuantitas (dalam kasus ini adalah sistem dan output). Dari uraian di atas, secara umum Inverse Problem diartikan sebagai suatu metode penyelesaikan masalah secara tidak langsung, artinya penyelesaian masalah menggunakan invers dari permasalahan yang akan diselesaikan. Pertama kali inverse problem diperkenalkan oleh Hadamard sekitar awal abad ke-20 (seseorang yang bekerja dalam bidang matematikafisika). Hadamard mengatakan bahwa suatu permasalahan adalah well-


6

posed jika memenuhi tiga persyaratan. Pertama, existence yaitu suatu masalah harus memiliki penyelesaian. Kedua, uniqueness bahwa hanya akan ada tepat satu penyelesaian pada suatu masalah. Ketiga, stability adalah penyelesaian yang didapat bergantung pada data, sehingga jika data diberi gangguan sedikit maka tidak akan menimbulkan galat yang sangat besar pada hasil. Jika terdapat satu dari tiga persyaratan yang tidak dipenuhi, maka masalah dikatakan ill-posed. Metode Inverse Problem bertujuan untuk mendapatkan suatu input yang tidak diketahui, berdasarkan informasi sistem dan output dari masalah. Prinsip dariinverse problem ini

sebenarnya merupakan

pengembangan dari invers matriks yang dikenal dalam aljabar linier. Dengan cara memandang permasalahan yang akan diselesaikan sebagai bentuk matriks, misalkan matriks 𝐴𝐱 = 𝐛, dimana 𝐱 merupakan input dari masalah, 𝐴 merupakan sistem dari masalah, dan 𝐛 merupakan output yang didapat dari masalah. Dari persamaan matriks tersebut, dapat ditentukan matriks 𝐱 = 𝐴−1 𝐛, dimana 𝐴−1 merupakan invers dari matriks 𝐴. Dengan menggunakan konsep tersebut maka inverse problem dapat juga diterapkan pada restorasi gambar digital, sehingga dapat diperoleh kembali gambar asli yang kabur atau terdegradasi karena efek derau. Secara umum,proses restorasi dapat dipandang sebagai persamaan 𝐱 = 𝐀−1 𝐛, dimana 𝐛 adalah gambar yang telah terdegradasi, 𝐀−1 adalah model transformasi untuk mengurangi efek derau pada 𝐛, dan 𝐱 adalah gambar hasil restorasi. Kemudian agar mendapatkan hasil optimal dalam


7

restorasi maka harus didapatkan 𝐀−1 terbaik yang mampu meredam efek derau dari 𝐛. Untuk mengatasi masalah itu, penulis menggunakan metode Truncated Singular Value Decomposition (TSVD) dan metode regularisasi Tikhonov. Skema berikut ini akan menjelaskan bagaimana alur algoritma dari invers problem,

Inverse Problem Sistem

Input

Output

Gambar 1.5. Inverse problem adalah proses mendapatkan input, saat diketahui dua kuantitas (sistem dan output).

B. Perumusan Masalah Permasalahan yang akan dibahas dalam tulisan ini akan dirumuskan sebagai berikut: 1. Apakah yang dimaksud dengan metode Inverse Problem dan bagaimana landasan teoritiknya? 2. Bagaimana penerapan metode Inverse Problem pada proses restorasi gambar digital?


8

3. Bagaimana algoritma dan pemrograman MATLAB pada proses restorasi gambar digital?

C. Pembatasan Masalah Penulis akan membatasi beberapa hal untuk uraian masalah yang akan dibahas, yaitu: 1. Tulisan ini dibatasi pada proses editing dengan restorasi untuk menghilangkan efek derau pada gambar. 2. Data yang digunakan berupa foto atau gambar yang mengalami derau. 3. Metode dalam Inverse Problem yang digunakan adalah metode Truncated Singular Value Decomposition (TSVD) dan Regularisasi Tikhonov untuk menghilangkan efek derau dan meningkatkan ketajaman gambar pada data yang disediakan. 4. Gambar yang direstorasi berupa gambar grayscale.

D. Tujuan Penulisan Tulisan ini disusun dengan tujuan agar dapat lebih memahami salah satu teknik restorasi yang sering digunakan dalam restorasi gambar digital. Terlebih lagi, akan dipelajari juga prinsip Truncated Singular Value Decomposition (TSVD) dan Regularisasi Tikhonov untuk restorasi gambar digital. Selain itu, akan dipelajari juga bagaimana penerapan prinsip-


9

prinsip restorasi gambar digital tersebut dalam pemrograman MATLAB. Tulisan ini juga disusun sebagai pemenuhan tugas akhir dalam Program Studi Matematika Universitas Sanata Dharma.

E. Manfaat Penelitian Dengan mempelajari topik ini kita dapat mempelajari kegunaan Inverse Problem dalam proses restorasi gambar digital. Kita juga dapat mempelajari prinsip Truncated Singular Value Decomposition (TSVD) dan Regularisasi Tikhonov dalam restorasi gambar digital. Terlebih lagi, kita juga dapat menerapkan metode tersebut dalam algoritma dan pemrograman MATLAB sehingga proses restorasi dapat lebih mudah dilakukan.

F. Metode Penulisan Penulisan menggunakan metode studi pustaka, yaitu dengan mempelajari buku dan jurnal yang berkaitan dengan topik Inverse Problem, teknik Truncated Singular Value Decomposition (TSVD) dan Regularisasi Tikonov dalam proses restorasi gambar digital.


G. Sistematika Penulisan BAB I. PENDAHULUAN A. Latar Belakang Masalah B. Perumusan Masalah C. Pembatasan Masalah D. Tujuan Penulisan E.

Manfaat Penulisan

F.

Metode Penulisan

G. Sistematika Penulisan

BAB II. LANDASAN TEORI A. Aljabar Linier B. Kalkulus

BAB III. INVERSE PROBLEM A. Prinsip Dasar Inverse Problem B. Metode Regularisasi

BAB IV. APLIKASI A. Gambar Digital B. Restorasi Gambar menggunakan TSVD C. Restorasi Gambar menggunakan Regularisasi Tikhonov

10


BAB V. PENUTUP A. Kesimpulan B. Saran

DAFTAR PUSTAKA

LAMPIRAN

11


BAB II LANDASAN TEORI

A. Aljabar Linier Pada subbab ini akan dijelaskan mengenai teori-teori aljabar linier yang akan digunakan sebagai landasan pembahasan pada bab-bab berikutnya.

2.1 Sistem Persamaan Linier Homogen Sebuah himpunan berhingga dari persamaan-persamaan linier dalam peubah 𝑥1 , 𝑥2 , … , 𝑥𝑛 dinamakan sistem persamaan linier (SPL). Sebuah sistem persamaan-persamaan linier dikatakan homogen jika ruas kanan pada sistem persamaan tersebut adalah sama dengan nol, yakni sistem yang mempunyai bentuk

𝑎11 𝑥1 𝑎21 𝑥1 ⋮ 𝑎𝑚1 𝑥1

+ + +

𝑎12 𝑥2 𝑎22 𝑥2 ⋮ 𝑎𝑚2 𝑥2

dan ditulis sebagai 𝐴𝐱 = 𝟎.

+ +

⋯ ⋯

+ +

+

⋯

+

𝑎1𝑛 𝑥𝑛 𝑎2𝑛 𝑥𝑛 ⋮ 𝑎𝑚𝑛 𝑥𝑛

= = =

0 0 ⋮ 0


13

Teorema 2.1.1 Misalkan 𝐴 matriks 𝑛 × 𝑛 dan 𝐴 adalah taksingular jika dan hanya jika 𝐴𝐱 = 𝟎 mempunyai penyelesaian trivial 0. Bukti: → Jika 𝐴 taksingular dan 𝐱 ′ adalah penyelesaian dari 𝐴𝐱 = 𝟎, maka 𝐱 ′ = 𝐼𝐱 ′ = 𝐴−1 𝐴 𝐱 ′ = 𝐴−1 𝐴𝐱 ′ = 𝐴−1 𝟎 = 𝟎. ← Jika 𝐴𝐱 = 𝟎 mempunyai penyelesaian 𝐱 ′ = 𝟎, maka 𝐱 ′ = 𝐴−1 𝟎 = 𝟎. Sehingga 𝐴 haruslah matriks taksingular.

2.2 Ruang Vektor Himpunan 𝑉 yang dilengkapi dengan operasi penjumlahan dan perkalian dengan skalar disebut sebagai ruang vektor, jika memenuhi aksioma-aksioma berikut dipenuhi. A1. 𝐱 + 𝐲 = 𝐲 + 𝐱 untuk setiap 𝐱 dan y di 𝑉. A2. 𝐱 + 𝐲 + 𝐳 = 𝐱 + 𝐲 + 𝐳 untuk setiap 𝐱, 𝐲, 𝐳 di 𝑉. A3. Terdapat elemen 𝟎 di 𝑉 sehingga 𝐱 + 𝟎 = 𝐱 untuk setiap 𝐱 ∈ 𝑉. A4. Untuk setiap 𝐱 ∈ 𝑉 terdapat −𝐱 elemen di 𝑉, sehingga 𝐱 + −𝐱 = 𝟎. A5. 𝛼 𝐱 + 𝐲 = 𝛼𝐱 + 𝛼𝐲 untuk setiap 𝛼 ∈ ℝ dan setiap 𝐱 dan y di 𝑉. A6. 𝛼 + 𝛽 𝐱 = 𝛼𝐱 + 𝛽𝐱 untuk setiap skalar 𝛼 dan 𝛽 dan setiap 𝐱 ∈ 𝑉. A7. 𝛼𝛽 𝐱 = 𝛼 𝛽𝐱 untuk setiap skalar 𝛼 dan 𝛽 dan setiap 𝐱 ∈ 𝑉. A8. 1. 𝐱 = 𝐱 untuk setiap 𝐱 ∈ 𝑉.


14

A9. Jika 𝐱 ∈ 𝑉 dan 𝛼 ∈ ℝ, maka 𝛼𝐱 ∈ 𝑉. A10. Jika 𝐱, 𝐲 ∈ 𝑉, maka 𝐱 + 𝐲 ∈ 𝑉.

Contoh 2.2.1 Himpunan matriks berukuran 𝑚 × 𝑛, dinotasikan 𝑀𝑚 ×𝑛 merupakan ruang vektor terhadap operasi penjumlahan matriks biasa serta perkalian dengan skalar.

2.2.1 Ruang bagian Definisi 2.2.1.1 𝑆 disebut ruang bagian dari 𝑉, jika 𝑆 adalah subhimpunan tak kosong dari suatu ruang vektor 𝑉 dan 𝑆 memenuhi 𝑖 𝛼𝐱 ∈ 𝑆 jika 𝐱 ∈ 𝑆 untuk sembarang skalar 𝛼 ∈ ℝ 𝑖𝑖 𝐱 + 𝐲 ∈ 𝑆 jika 𝐱 ∈ 𝑆 dan 𝐲 ∈ 𝑆.

Contoh 2.2.1.2 Misalkan 𝑆 =

𝑥1 𝑥2 𝑥3

𝑥1 = 𝑥2 . Maka 𝑆 adalah ruang bagian dari ℝ3 ,

sebab 𝑥2 i Jika 𝐱 ∈ 𝑆, maka 𝐱 harus berbentuk 𝐱 = 𝑥2 , sehingga 𝑥3


15

𝑥2 𝛼𝑥2 𝑥 𝛼𝑥 𝛼𝐱 = 𝛼 2 = 2 . Karena 𝛼𝑥1 = 𝛼𝑥2 , berarti 𝛼𝐱 ∈ 𝑆. 𝑥3 𝛼𝑥3

ii Jika 𝐱, 𝐲 ∈ 𝑆, maka 𝐱 dan 𝐲 harus berbentuk 𝑥2 𝑦2 𝑥 𝐱 = 2 dan 𝐲 = 𝑦2 𝑥3 𝑦3 sehingga 𝑥2 𝑦2 𝑥2 + 𝑦2 𝑥 𝑦 𝐱 + 𝐲 = 2 + 2 = 𝑥2 + 𝑦2 . 𝑥3 𝑦3 𝑥3 + 𝑦3 Karena 𝑥1 + 𝑦1 = 𝑥2 + 𝑦2 , berarti 𝐱 + 𝐲 ∈ 𝑆.

2.2.1.3 Kernel dari matriks Misalkan 𝐴 adalah matriks 𝑚 × 𝑛 dan 𝑁 𝐴 merupakan himpunan semua penyelesaian sistem 𝐴𝐱 = 𝟎 yang membentuk ruang bagian dari ℝ𝑛 . Ruang bagian 𝑁 𝐴 disebut kernel (ruang nol), yang ditulis sebagai 𝑁 𝐴 = 𝐱 ∈ ℝ𝑛 𝐴𝐱 = 𝟎 .

Teorema 2.2.1.4 𝑁 𝐴 adalah ruang bagian dari ℝ𝑛 . Bukti: Jika 𝐱 ∈ 𝑁 𝐴 dan 𝛼 suatu skalar, maka 𝐴 𝛼𝐱 = 𝛼𝐴𝐱 = 𝟎


16

sehingga 𝛼𝐱 ∈ 𝑁 𝐴 . Jika 𝐱 dan 𝐲 adalah elemen-elemen dari 𝑁 𝐴 , maka 𝐴 𝐱 + 𝐲 = 𝐴𝐱 + 𝐴𝐲 = 𝟎 + 𝟎 = 𝟎 akibatnya 𝐱 + 𝐲 ∈ 𝑁 𝐴 . Karena 𝛼𝐱 ∈ 𝑁 𝐴 dan 𝐱 + 𝐲 ∈ 𝑁 𝐴 , berarti 𝑁 𝐴 adalah ruang bagian dari ℝ𝑛 .

2.2.2 Kebebasan Linier Sebuah vektor 𝐰 disebut sebagai kombinasi linier dari vektor-vektor 𝐯1 , 𝐯2 , … 𝐯𝑛 jika vektor tersebut dapat dituliskan dalam bentuk 𝐰 = 𝑐1 𝐯1 + 𝑐2 𝐯2 + ⋯ + 𝑐𝑛 𝐯𝑛 dimana 𝑐1 , 𝑐2 , … , 𝑐𝑛 adalah skalar. Himpunan semua kombinasi linier dari 𝐯1 , 𝐯2 , … 𝐯𝑛 disebut rentang dari 𝐯1 , 𝐯2 , … 𝐯𝑛 .

Definisi 2.2.2.1 Himpunan 𝐯1 , 𝐯2 , … 𝐯𝑛 disebut himpunan perentang untuk 𝑉 jika dan hanya jika setiap vektor dalam 𝑉 dapat ditulis sebagai kombinasi linier dari 𝐯1 , 𝐯2 , … 𝐯𝑛 .

Definisi 2.2.2.2 Himpunan 𝐯1 , 𝐯2 , … 𝐯𝑛 dikatakan bebas linier jika kombinasi linier 𝑐1 𝐯1 + 𝑐2 𝐯2 + ⋯ + 𝑐𝑛 𝐯𝑛 = 0 mengakibatkan 𝑐1 = 𝑐2 = ⋯ = 𝑐𝑛 = 0.


17

2.2.3 Basis dan Dimensi Definisi 2.2.3.1 Vektor-vektor 𝐯1 , 𝐯2 , … , 𝐯𝑛 yang bebas linear dan merentang pada ruang vektor 𝑉 disebut sebagai basis dan banyaknya vektor dalam basis pada ruang vektor 𝑉 dikatakan sebagai dimensi.

Contoh 2.2.3.2 Tentukan 𝑁 𝐴 dari matriks 𝐴=

1 1 2 1

1 0 0 1

dan kemudian tentukan basis dan dimensi dari 𝑁 𝐴 yang diperoleh.

Penyelesaian: Dengan menggunakan proses eliminasi Gauss untuk menyelesaikan 𝐴𝐱 = 𝟎, diperoleh 1 1 2 1

1 00 0 10

𝑅2 + −2 𝑅1

1 0

1 1 00 −1 −2 1 0

1 1 1 00 0 −1 −2 1 0

𝑅1 +𝑅2

1 0 −1 1 0 0 −1 −2 1 0

1 0

−1 𝑅2

1 0 0 1

sehingga 0 −1 1 0 −1 −2 1 0

−1 1 0 2 −1 0

Bentuk eselon baris tersebut melibatkan dua peubah bebas, 𝑥3 dan 𝑥4 sehingga


18

𝑥1 = 𝑥3 − 𝑥4 𝑥2 = −2𝑥3 + 𝑥4

kemudian jika didefinisikan 𝑥3 = 𝛼 dan 𝑥4 = 𝛽, maka

𝐱=

𝛼−𝛽 −2𝛼 + 𝛽 𝛼 𝛽

1 −1 −2 1 =𝛼 +𝛽 1 0 0 1

adalah penyelesaian dari 𝐴𝐱 = 𝟎. Jadi, 𝑁 𝐴 adalah semua vektor yang berbentuk 1 −1 −2 1 𝛼 +𝛽 1 0 0 1 dimana 𝛼, 𝛽 ∈ ℝ.

Dari hasil tersebut terlihat bahwa 𝑁 𝐴 adalah ruang bagian dari ℝ4 yang direntang vektor-vektor 1 −2 dan 1 0

−1 1 . 0 1

Selain itu kedua vektor tersebut juga bebas linear, akibatnya vektor-vektor tersebut membentuk basis untuk 𝑁 𝐴 . Dan karena 𝑁 𝐴 mempunyai 2 vektor dalam basis 𝑁 𝐴 , berarti dimensi dari 𝑁 𝐴 = 2.


19

2.2.4 Ruang Baris dan Ruang Kolom Definisi 2.2.4.1 Jika 𝐴 adalah matriks 𝑚 × 𝑛, maka ruang bagian dari ℝ𝑛 yang direntang oleh vektor-vektor baris dari 𝐴 disebut ruang baris dari 𝐴, sedangkan ruang bagian dari ℝ𝑚 yang direntang oleh vektor-vektor kolom dari 𝐴 disebut ruang kolom dari 𝐴.

Contoh 2.2.4.2 Misalkan 𝐴 =

1 0

0 0 , maka tentukan ruang baris dan ruang kolom 1 0

dari 𝐴.

Penyelesaian: Ruang baris dari 𝐴 adalah himpunan semua vektor yang berbentuk 𝛼 1,0,0 + 𝛽 0,1,0 = 𝛼, 𝛽, 0 dan ruang kolom dari 𝐴 adalah himpunan semua vektor yang berbentuk 𝛼

𝛼 1 0 0 +𝛽 +𝛾 = 𝛽 . 0 0 1

Misalkan 𝐴 adalah matriks 𝑚 × 𝑛, vektor 𝐛 ∈ ℝ𝑚 berada di dalam ruang kolom dari 𝐴 jika dan hanya jika 𝐛 = 𝐴𝐱 untuk 𝐱 ∈ ℝ𝑛 . Maka, ruang kolom dari 𝐴 dapat dinyatakan sebagai 𝑅 𝐴 , 𝑅 𝐴 = 𝐛 ∈ ℝ𝑚 𝐛 = 𝐴𝐱 untuk 𝐱 ∈ ℝ𝑛 ,

dan ruang kolom dari 𝐴𝑇 dinyatakan sebagai 𝑅 𝐴𝑇


20

𝑅 𝐴𝑇 = 𝐲 ∈ ℝ𝑛 𝐲 = 𝐴𝑇 𝐱 untuk 𝐱 ∈ ℝ𝑛 .

Ruang kolom dari 𝑅 𝐴𝑇 sesungguhnya sama dengan ruang baris dari 𝐴. Jadi 𝐲 ∈ 𝑅 𝐴𝑇 jika dan hanya jika 𝐲 𝑇 berada di dalam ruang baris dari 𝐴. Selanjutnya akan diperlihatkan bahwa 𝑅 𝐴 dan 𝑅 𝐴𝑇

adalah ruang

bagian dari ℝ𝑛 . (i) Jika 𝐛 ∈ 𝑅 𝐴 dan 𝛼 suatu skalar, maka untuk 𝛼𝐱 ∈ ℝ𝑛 𝛼𝐛 = 𝛼 𝐴𝐱 = 𝐴𝛼𝐱 sehingga 𝛼𝐛 ∈ 𝑅 𝐴 . Jika 𝐛1 dan 𝐛2 adalah elemen-elemen dari 𝑅 𝐴 , maka untuk 𝐱1 + 𝐱 2 ∈ ℝ𝑛 𝐛1 + 𝐛2 = 𝐴𝐱1 + 𝐴𝐱 2 = 𝐴 𝐱1 + 𝐱 2 akibatnya 𝐛1 + 𝐛2 ∈ 𝑅 𝐴 . Karena 𝛼𝐛 ∈ 𝑅 𝐴

dan 𝐛1 + 𝐛2 ∈

𝑅 𝐴 , berarti 𝑅 𝐴 adalah ruang bagian dari ℝ𝑛 .

(ii) Jika 𝐲 ∈ 𝑅 𝐴𝑇 dan 𝛼 suatu skalar, maka untuk 𝛼𝐱 ∈ ℝ𝑛 𝛼𝐲 = 𝛼 𝐴𝑇 𝐱 = 𝐴𝑇 𝛼𝐱

sehingga 𝛼𝐲 ∈ 𝑅 𝐴𝑇 . Jika 𝐲1 dan 𝐲2 adalah elemen-elemen dari 𝑅 𝐴𝑇 , maka untuk 𝐱1 + 𝐱 2 ∈ ℝ𝑛 𝐲1 + 𝐲2 = 𝐴𝑇 𝐱1 + 𝐴𝑇 𝐱 2 = 𝐴𝑇 𝐱1 + 𝐱 2 akibatnya 𝐲1 + 𝐲2 ∈ 𝑅 𝐴𝑇 . Karena 𝛼𝐲 ∈ 𝑅 𝐴 𝑅 𝐴𝑇 , berarti 𝑅 𝐴𝑇 adalah ruang bagian dari ℝ𝑛 .

dan 𝐲1 + 𝐲2 ∈


21

Teorema 2.2.4.3 Dua matriks yang ekivalen baris memiliki ruang baris yang sama.

Bukti: Jika matriks 𝐵 ekivalen baris dengan matriks 𝐴, maka 𝐵 dapat dibentuk dari 𝐴 dengan operasi baris yang berhingga banyaknya. Ini berarti vektorvektor baris dari 𝐵 harus merupakan kombinasi linear dari vektor-vektor baris dari 𝐴. Akibatnya, ruang baris dari 𝐵 harus merupakan ruang bagian dari ruang baris 𝐴. Karena matriks 𝐴 ekivalen baris dengan matriks 𝐵, maka dengan alasan yang sama, ruang baris dari 𝐴 adalah ruang bagian dari ruang baris 𝐵.

Definisi 2.2.4.4 Rank dari suatu matriks 𝐴 adalah dimensi dari ruang baris 𝐴.

Contoh 2.2.4.5 Misalkan 1 −2 3 𝐴 = 2 −5 1 1 −4 −7 Dengan mereduksi 𝐴 menjadi bentuk eselon baris, diperoleh 1 𝑈= 0 0

−2 3 1 5 0 0


22

sehingga 1, −2,3 dan 0,1,5 membentuk basis untuk ruang baris 𝑈. Karena 𝑈 dan 𝐴 ekivalen baris, maka menurut Teorema 2.2.4.3 matriks memiliki ruang baris yang sama sehingga rank dari 𝐴 adalah 2.

2.3 Ortogonalitas 2.3.1 Ruang Hasil Kali Dalam Definisi 2.3.1.1 Hasil kali dalam pada ruang vektor riil 𝑉 adalah fungsi yang mengasosiasikan bilangan riil 𝐱, 𝐲 dengan vektor 𝐱 dan 𝐲 pada 𝑉, sedemikian sehingga aksioma-aksioma berikut terpenuhi untuk semua 𝐱, 𝐲, 𝐳 di 𝑉 dan semua skalar 𝛼, 𝛽 di ℝ: 𝐱, 𝐱 ≥ 0; dan 𝐱, 𝐱 = 0 jika dan hanya jika 𝐱 = 0.

(i)

(ii) 𝐱, 𝐲 = 𝐲, 𝐱 untuk setiap 𝐱 dan 𝐲 di dalam 𝑉. (iii)

𝛼𝐱 + 𝛽𝐲 , 𝐳 = 𝛼 𝐱, 𝐳 + 𝛽 𝐲, 𝐳 untuk setiap 𝐱, 𝐲, 𝐳 di dalam 𝑉 dan setiap skalar 𝛼, 𝛽.

Sebuah ruang vektor 𝑉 yang dilengkapi dengan sebuah hasil kali dalam disebut ruang hasil kali dalam. Salah satu contoh dari ruang hasil kali dalam adalah ruang vektor ℝ𝑛 , dimana hasil kali dalam baku untuk ℝ𝑛 dihitung sebagai hasil kali skalar 𝐱, 𝐲 = 𝐱 𝑇 𝐲.


23

Definisi 2.3.1.2 Dua vektor 𝐱 dan 𝐲 dikatakan ortogonal jika 𝐱, 𝐲 = 0, yang dinotasikan sebagai 𝐱 ⊥ 𝐲.

Definisi 2.3.1.3 Sebuah ruang vektor 𝑉 dikatakan ruang linier bernorma jika untuk setiap vektor 𝐯 ∈ 𝑉 dikaitkan dengan sebuah bilangan riil 𝐯 yang disebut norma dari 𝐯 yang memenuhi: (i)

𝐯 ≥ 0.

(ii) 𝐯 = 0 jika dan hanya jika 𝐯 = 𝟎. (iii) 𝛼𝐯 = 𝜶 v untuk setiap 𝛼 ∈ ℝ. (iv) 𝐯 + 𝐰 ≤ 𝐯 + 𝐰 untuk setiap 𝐯 dan 𝐰 di 𝑉.

Teorema 2.3.1.4 Jika 𝑉 sebuah ruang hasil kali dalam, maka 𝐯 =

𝐯, 𝐯

untuk setiap 𝐯 ∈ 𝑉

mendefinisikan sebuah norma pada 𝑉.

Bukti: (i) Karena nilai dari

𝐯 =

mungkin hanyalah 𝐯 = 𝟎.

𝐯, 𝐯 ≥ 0, berarti nilai terkecil yang


(ii) Jika 𝐯 = 𝟎, maka 𝐯

2

= 𝐯, 𝐯 = 𝟎, 𝟎 = 0. Jadi 𝐯 = 0.

Kemudian jika 𝐯 =

(iii) 𝛼𝐯

2

𝐯, 𝐯 =

𝟎, 𝟎 = 0, berarti haruslah 𝐯 = 𝟎.

= 𝛼𝐯, 𝛼𝐯 = 𝛼 2 𝐯, 𝐯 =

(iv) 𝐮 + 𝐯

2

24

𝛼 𝐯

2

. Jadi, 𝛼𝐯 = 𝛼 𝐯 .

= 𝐮 + 𝐯, 𝐮 + 𝐯 = 𝐮, 𝐮 + 2 𝐮, 𝐯 + 𝐯, 𝐯 ≤ 𝐮 2+2 𝐮 𝐯 + 𝐯 =

𝐮 + 𝐯

2

(ketaksamaan Cauchy-Schwarz)

2

Jadi, 𝐮 + 𝐯 ≤ 𝐮 + 𝐯

Kemudian dapat didefinisikan beberapa norma yang berbeda pada ruang vektor yang diberikan. Seperti, di ℝ𝑛 kita dapat mendefinisikan 1 2

𝑛

𝐱

2

=

𝑥𝑖

2

=

𝐱, 𝐱 =

𝐱𝑇 𝐱

𝑖=1

disebut sebagai norma-2 vektor. Selain itu, norma lainnya yang penting pada ℝ𝑛 adalah 𝐱

∞

= max 𝑥𝑖 1≤𝑖≤𝑛


25

Bukti: (i) Untuk 1 ≤ 𝑖 ≤ 𝑛, max1≤𝑖≤𝑛 𝑥𝑖 = 𝐱

(ii) Jika 𝐱

∞

𝑥𝑖 ≥ 0 sehingga max1≤𝑖≤𝑛 𝑥𝑖 . Akibatnya, ∞

≥ 0.

= 0, maka max1≤𝑖≤𝑛 𝑥𝑖 = 0. Karena maksimal dari

𝑥𝑖 = 0, 𝑖 = 1,2, … , 𝑛 berarti 𝑥1 = 𝑥2 = ⋯ = 𝑥𝑛 = 0, akibatnya

𝐱=

0 0 ⋮ 0

sehingga 𝐱 = 𝟎. Oleh karena itu 𝐱 haruslah suatu vektor nol. 𝐱 = 𝟎,

Jika

𝑥1 = 𝑥2 = ⋯ = 𝑥𝑛 = 0.

berarti

max1≤𝑖≤𝑛 𝑥𝑖 = 0 sehingga 𝐱

(iii) 𝛼𝐱

∞

(iv) 𝐱 + 𝐲

∞

= 0.

= max1≤𝑖≤𝑛 𝛼𝑥𝑖 = 𝛼 max1≤𝑖≤𝑛 𝑥𝑖 = 𝛼 𝐱

∞

Akibatnya

∞.

= max1≤𝑖≤𝑛 𝑥𝑖 + 𝑦𝑖 ≤ max 𝑥𝑖 + max 𝑦𝑖 1≤𝑖≤𝑛

≤ 𝐱

∞

1≤𝑖≤𝑛

+ 𝐲

Berdasarkan bukti di atas 𝐱 𝐱

∞

∞.

∞

memenuhi definisi sebagai norma, maka

disebut sebagai norma-∞ vektor.


26

Contoh 2.3.1.5 Misalkan 𝐱 adalah vektor 4, −5,3 𝐱

2

𝐱

∞

𝑇

di ℝ3 . Hitunglah 𝐱

2

dan 𝐱

∞.

= 16 + 25 + 9 = 50 = 5 2. = max 4 , −5 , 3

= 5.

Teorema 2.3.1.6 (Ketaksamaan Cauchy-Schwarz) Jika 𝐮 dan 𝐯 adalah vektor-vektor di dalam sebuah ruang hasil kali dalam 𝑉, maka 𝐮, 𝐯 ≤ 𝐮 𝐯 Bukti: Jika 𝐯 = 𝟎 maka

𝐮, 𝐯 = 𝐮 𝐯 = 0, sehingga ketaksamaan berlaku.

Jika 𝐯 ≠ 𝟎, untuk setiap bilangan 𝑡 ∈ ℝ nilai 𝑡𝐮 + 𝐯 𝑡𝐮 + 𝐯 ≥ 0 𝐮, 𝐮 𝑡 2 + 2 𝐮, 𝐯 𝑡 + 𝐯, 𝐯 ≥ 0 merupakan fungsi kuadrat dalam 𝑡 sehingga haruslah 𝑡 ≥ 0. Ini berarti fungsi kuadrat tersebut tidak mempunyai akar berbeda. Oleh karena ini, diskriminannya tidak mungkin positif, sehingga 4 𝐮, 𝐯

2

− 4 𝐮, 𝐮 𝐯, 𝐯 ≤ 0

atau 4 𝐮, 𝐯

2

≤ 4 𝐮, 𝐮 𝐯, 𝐯

𝐮, 𝐯

2

≤ 𝐮, 𝐮 𝐯, 𝐯


𝐮, 𝐯

2

≤ 𝐮

2

𝐯

27

2

dengan mengambil akar dari kedua ruas diperoleh 𝐮, 𝐯 ≤ 𝐮 𝐯 .

2.3.2 Ruang Bagian Ortogonal Vektor 𝐱 dan himpunan 𝑌 = 𝐲1 , 𝐲2 , . . , 𝐲𝑛

adalah ortogonal jika

terdapat 𝐱 ∈ 𝑋 dan untuk setiap 𝐲 ∈ 𝑌 berlaku 𝐱, 𝐲 = 0. Dan apabila 𝐱 dan 𝑌 ortogonal, dinotasikan sebagai 𝐱 ⊥ 𝑌.

Definisi 2.3.2.1 Dua ruang bagian 𝑋 dan 𝑌 dari ℝ𝑛 dikatakan ortogonal jika 𝐱, 𝐲 = 0 untuk setiap 𝐱 ∈ 𝑋 dan setiap 𝐲 ∈ 𝑌, dan apabila 𝑋 dan 𝑌 ortogonal ditulis 𝑋 ⊥ 𝑌.

Misalkan 𝐴 adalah matriks 𝑚 × 𝑛 dan misalkan 𝐱 ∈ 𝑁(𝐴). Karena 𝐴𝐱 = 𝟎 sehingga 𝑎𝑖1 𝑥1 + 𝑎𝑖2 𝑥2 + ⋯ + 𝑎𝑖𝑛 𝑥𝑛 = 0 untuk 𝑖 = 1,2, … , 𝑚. Persamaan tersebut menunjukkan bahwa 𝐱 ortogonal pada setiap vektor kolom dari 𝐴𝑇 , maka 𝐱 ortogonal ke setiap kombinasi linier dari vektor-vektor kolom 𝐴𝑇 . Sehingga jika 𝐲 adalah vektor kolom dalam ruang vektor 𝐴𝑇 , maka 𝐱 𝑇 𝐲 = 0. Jadi setiap vektor di dalam 𝑁 𝐴


28

ortogonal terhadap setiap vektor di dalam ruang kolom 𝐴𝑇 , yang ditulis sebagai 𝑁 𝐴 ⊥ 𝑅 𝐴𝑇 . Jika dua ruang bagian memiliki sifat ini, maka dapat dikatakan bahwa ruang bagian tersebut adalah ortogonal.

Definisi 2.3.2.2 Misalkan 𝐯1 , 𝐯2 , … , 𝐯𝑛 adalah vektor-vektor di dalam sebuah ruang hasil kali dalam 𝑉. Jika semua pasangan vektor 𝐯𝑖 , 𝐯𝑗 = 0, dimana 𝑖 ≠ 𝑗, maka 𝐯1 , 𝐯2 , … , 𝐯𝑛 disebut sebagai himpunan ortogonal.

Definisi 2.3.2.3 Misalkan 𝑌 adalah ruang bagian dari ℝ𝑛 . Himpunan semua vektor-vektor di dalam ℝ𝑛 yang ortogonal pada setiap vektor di 𝑌 akan dinotasikan dengan 𝑌 ⊥ , 𝑌 ⊥ = 𝐱 ∈ ℝ𝑛 𝐱, 𝐲 = 0 untuk setiap 𝐲 ∈ 𝑌 .

Himpunan 𝑌 ⊥ disebut komplemen ortogonal dari 𝑌.

2.3.2.4 Ruang-Ruang Bagian Pokok (Fundamental Subspaces) Telah dijelaskan bahwa 𝑅 𝐴𝑇 ⊥ 𝑁 𝐴 , selanjutnya akan diperlihatkan bahwa 𝑁 𝐴 sebenarnya merupakan komplemen ortogonal dari 𝑅 𝐴𝑇 .


29

Teorema 2.3.2.5 Jika 𝐴 adalah sebuah matriks 𝑚 × 𝑛, maka 𝑁 𝐴 = 𝑅 𝐴𝑇 𝑅 𝐴

⊥

⊥

dan 𝑁 𝐴𝑇 =

.

Bukti: Diketahui bahwa 𝑁 𝐴 ⊥ 𝑅 𝐴𝑇 , sehingga 𝑁 𝐴 ⊂ 𝑅 𝐴𝑇 ⊥ . Ambil sebarang vektor 𝐱 di 𝑅 𝐴𝑇 ⊥ . Berdasarkan definisi komplemen ortogonal maka 𝐱 ortogonal pada setiap vektor kolom dari 𝐴𝑇 , akibatnya 𝐴𝐱 = 𝟎. Padahal 𝑁 𝐴 = 𝐱 ∈ ℝ𝑛 𝐴𝐱 = 𝟎 . Jadi 𝐱 haruslah menjadi sebuah elemen dari 𝑁 𝐴 , yaitu 𝑁 𝐴 = 𝑅 𝐴𝑇 ⊥ . Secara khusus, hasil ini juga berlaku untuk matriks 𝐵 = 𝐴𝑇 . Jadi 𝑁 𝐴𝑇 = 𝑁 𝐵 = 𝑅 𝐵𝑇

⊥

= 𝑅 𝐴 ⊥.

2.3.3 Masalah Kuadrat Terkecil Masalah kuadrat terkecil pada umumnya dapat dirumuskan sebagai sebuah sistem kelebihan persamaan linier, yaitu sistem yang memiliki lebih banyak persamaan daripada peubah. Sistem yang seperti ini biasanya tidak mempunyai penyelesaian. Misalkan diberikan sebuah sistem 𝑚 × 𝑛 yaitu 𝐴𝐱 = 𝐛 dengan 𝑚 > 𝑛, kemudian penyelesaian dari sistem tersebut adalah mencari sebuah vektor 𝐱 ∈ ℝ𝑛 sehingga 𝐴𝐱 sama dengan 𝐛. Berarti vektor 𝐱 yang didapat untuk 𝐴𝐱 harus sedekat mungkin dengan 𝐛. Diberikan sistem 𝐴𝐱 = 𝐛. Untuk setiap 𝐱 ∈ ℝ𝑛 dapat dihitung sebuah selisih antara 𝐛 dan 𝐴𝐱 sebagai


30

𝑟 𝐱 = 𝐛 − 𝐴𝐱 dan jarak antara 𝐛 dan 𝐴𝐱 diberikan sebagai 𝐛 − 𝐴𝐱 = 𝑟 𝐱 . Untuk mendapatkan vektor 𝐱 ∈ ℝ𝑛 yang terbaik dalam mendekati 𝐛, maka harus dicari nilai 𝑟 𝐱

yang paling minimum. Sebuah vektor 𝐱 yang

memenuhi ini disebut sebagai penyelesaian kuadrat terkecil untuk sistem 𝐴𝐱 = 𝐛.

Teorema 2.3.3.1 Jika 𝐴 adalah matriks 𝑚 × 𝑛 yang memiliki rank 𝑛, maka persamaan normal 𝐴𝑇 𝐴𝐱 = 𝐴𝑇 𝐛 mempunyai sebuah penyelesaian tunggal 𝐱 ′ = 𝐴𝑇 𝐴

−1

𝐛

dimana 𝐱 ′ adalah penyelesaian kuadrat terkecil yang tunggal dari sistem 𝐴𝐱 = 𝐛.

Bukti: Akan ditunjukkan bahwa 𝐴𝑇 𝐴 adalah taksingular. Misalkan 𝐳 adalah penyelesaian untuk 𝐴𝑇 𝐴𝐱 = 𝟎, berarti 𝐴𝐳 ∈ 𝑁 𝐴𝑇 . Sehingga 𝑎1𝑗 𝑧1 + 𝑎2𝑗 𝑧2 + ⋯ + 𝑎𝑛𝑗 𝑧𝑛 = 0 menunjukkan bahwa 𝐳 ortogonal pada setiap vektor kolom dari 𝐴, maka 𝐳 ortogonal ke setiap kombinasi linier dari vektor-vektor kolom 𝐴.


Akibatnya 𝑁 𝐴𝑇 ortogonal terhadap 𝑅(𝐴), maka 𝐴𝐳 ∈ 𝑅 𝐴 = 𝑁 𝐴𝑇 Karena 𝑁 𝐴𝑇 dan 𝑁 𝐴𝑇 𝐴𝐳 ∈ 𝑁 𝐴𝑇 ∩ 𝑁 𝐴𝑇

⊥

⊥

31

⊥

.

adalah ruang bagian yang ortogonal, berarti

dan

𝑁 𝐴𝑇 ⊥ 𝑁 𝐴𝑇

⊥

,

maka

𝐴𝐳 𝑇 𝐴𝐳 = 0

sehingga 𝐴𝐳 = 𝟎. Jika 𝐴 mempunyai rank 𝑛 maka vektor-vektor kolom dari 𝐴 adalah bebas linear, sehingga 𝐴𝐱 = 𝟎 akan mempunyai penyelesaian trivial. Jadi 𝐳 = 𝟎 dan 𝐴𝑇 𝐴𝐱 = 𝟎 juga mempunyai penyelesaian trivial. Berdasarkan Teorema 2.1.1, 𝐴𝑇 𝐴 adalah taksingular. Ini mengakibatkan bahwa 𝐱 ′ = 𝐴𝑇 𝐴

−1 𝑇

𝐴 𝐛 adalah penyelesaian tunggal

untuk persamaan 𝐴𝑇 𝐴𝐱 = 𝐴𝑇 𝐛, sehingga 𝐱 ′ merupakan penyelesaian kuadrat terkecil yang tunggal untuk sistem 𝐴𝐱 = 𝐛.

2.3.4 Himpunan Ortonormal Definisi 2.3.4.1 Himpunan ortogonal yang setiap vektornya mempunyai norma 1 disebut sebagai himpunan ortonormal. Himpunan 𝐮1 , 𝐮2 , … , 𝐮𝑛 akan menjadi ortonormal jika dan hanya jika 𝐮𝑖 , 𝐮𝑗 = 𝛿𝑖𝑗 , dimana𝛿𝑖𝑗 =

1 jika 𝑖 = 𝑗 . 0 jika 𝑖 ≠ 𝑗


32

Untuk membentuk sebuah himpunan ortonormal dari himpunan ortogonal vektor-vektor

taknol

𝐯1 , 𝐯2 , … , 𝐯𝑛

dapat

dilakukan

dengan

mendefinisikan 1 𝐯𝑖

𝐮𝑖 =

𝐯𝑖 =

1 . 𝐯𝑖 = 1 𝐯𝑖

untuk 𝑖 = 1,2, … 𝑛

Proses pengalian vektor 𝐯𝑖 taknol ini dengan kebalikan panjangnya untuk mendapatkan vektor yang normanya 1 dinamakan menormalisasikan 𝐯𝑖 .

Definisi 2.3.4.2 Suatu basis yang anggota-anggotanya saling ortogonal dan masing-masing memiliki norma 1 disebut basis ortonormal.

Definisi 2.3.4.3 Matriks 𝑍 yang berukuran 𝑛 × 𝑛 disebut sebagai matriks ortogonal, jika vektor-vektor kolom dari 𝑍 membentuk sebuah himpunan ortonormal di dalam ℝ𝑛 .

2.3.4.4 Sifat-sifat Matriks Ortogonal Jika 𝑍 adalah matriks ortogonal 𝑛 × 𝑛, maka (i) 𝑍 𝑇 𝑍 = 𝐼 (ii) 𝑍 𝑇 = 𝑍 −1 (iii) 𝑍𝐱, 𝑍𝐲 = 𝐱, 𝐲 (iv) 𝑍𝐱

2

= 𝐱

2


33

Bukti: (i) Berdasarkan definisi 2.3.4.1, sebuah matriks 𝑍 yang berukuran 𝑛 × 𝑛 adalah ortogonal jika dan hanya jika vektor-vektor kolom dari 𝑍 membentuk sebuah himpunan ortonormal, yaitu 𝐳𝑖 , 𝐳𝑗 = 𝐳𝑖 𝑇 𝐳𝑗 = 𝛿𝑖𝑗 dimana 𝛿𝑖𝑗 =

1 jika 𝑖 = 𝑗 . 0 jika 𝑖 ≠ 𝑗

Dan dari perhitungan 𝐳𝑖 , 𝐳𝑗 akan menghasilkan nilai-nilai untuk entri 𝑖, 𝑗 , ( 𝑖 = 1,2, . . 𝑛 dan 𝑗 = 1,2, … , 𝑛) dari 𝑍 𝑇 𝑍 sehingga 1 0 0 ⋮ 0

𝑍𝑇 𝑍 =

0 1 0 ⋮ 0

0 0 1 ⋮ 0

0 0 0 ⋱ ⋯

0 0 0 ⋮ 1

=𝐼.

(ii) Berdasarkan sifat (i) 𝑍 𝑇 𝑍 = 𝐼 maka 𝑍 𝑇 = 𝐼𝑍 −1 , sehingga 𝑍 𝑇 = 𝑍 −1 .

(iii) 𝑍𝐱, 𝑍𝐲 = 𝑍𝐱 𝑇 𝑍𝐲 = 𝐱 𝑇 𝑍 𝑇 𝑍𝐲 = 𝐱 𝑇 𝐼 𝐲 = 𝐱 𝑇 𝐲 = 𝐱, 𝐲 .

(iv) 𝑍𝐱 =

2

=

𝐱𝑇 𝐱 =

𝑍𝐱, 𝑍𝐱 =

𝑍𝐱 𝑇 𝑍𝐱 = 𝐱 𝑇 𝑍 𝑇 𝑍𝐱 = 𝐱 𝑇 𝐼 𝐱

𝐱, 𝐱 = 𝐱 2 .


34

2.4 Nilai Eigen dan Vektor Eigen Apabila sebuah matriks 𝐴 berukuran 𝑛 × 𝑛 dan sebuah vektor 𝐱 ∈ ℝ𝑛 , maka biasanya tidak ada hubungan geometris di antara vektor 𝐱 dan vektor 𝐴𝐱 (Gambar 2.1a). Akan tetapi, ada beberapa vektor taknol 𝐱, sehingga 𝐱 dan 𝐴𝐱 merupakan kelipatan satu sama lainnya (Gambar 2.1b). Vektorvektor tersebut muncul secara alami dalam telaah getaran, sistem elektris, genetik, reaksi kimia, mekanika kuanturm, tekanan mekanis, ekonomi dan geometris. Pada bagian ini akan ditunjukkan bagaimana mencari vektorvektor ini.

Ax x

Ax

(a)

x

(b)

Gambar 2.1. Hubungan geometris di antara 𝐱 dan 𝐴𝐱

Definisi 2.4.1 Misalkan 𝐴 adalah matriks berukuran 𝑛 × 𝑛. Skalar 𝜆 disebut sebagai nilai eigen dari 𝐴, jika terdapat vektor tak nol 𝐱 sehingga 𝐴𝐱 = 𝜆𝐱. Vektor 𝐱 disebut vektor eigen yang bersesuaian dengan 𝜆.


35

Contoh 2.4.2 Diberikan matriks 𝐴 =

3 8

0 1 , maka 𝐱 = merupakan vektor eigen −1 2

dari matriks 𝐴. Sebab 𝐴𝐱 merupakan kelipatan dari 𝐱, yaitu 𝐴𝐱 =

3 0 8 −1

3 1 1 = =3 = 3𝐱 6 2 2

Dari persamaan ini terlihat bahwa 𝜆 = 3 merupakan nilai eigen dari matriks 𝐴. Untuk dapat mencari nilai eigen dari matriks persegi 𝐴, perlu diperhatikan kembali definisi nilai eigen dan vektor eigen, bahwa bentuk 𝐴𝐱 = 𝜆𝐱 dapat ditulis sebagai 𝐴𝐱 = 𝜆𝐼𝐱 𝐴𝐱 − 𝜆𝐼𝐱 = 𝟎 𝐴 − 𝜆𝐼 𝐱 = 𝟎, dimana 𝐼 adalah matriks identitas yang mempunyai bentuk

𝐼=

1 0 0 ⋮ 0

0 1 0 ⋮ 0

0 ⋯ 0 ⋯ 1 ⋯ ⋮ ⋱ 0 0

0 0 0 . ⋮ 1

Agar 𝜆 menjadi nilai eigen, maka harus ada penyelesaian tak nol dari persamaan 𝐴 − 𝜆𝐼 𝐱 = 𝟎. Sehingga persamaan tersebut akan mempunyai penyelesaian tak nol jika dan hanya jika det 𝐴 − 𝜆𝐼 = 0. Jika det 𝐴 − 𝜆𝐼 = 0 diuraikan, akan didapatkan suatu polinomial berderajat ke-𝑛 dalam peubah 𝜆,


36

𝑝 𝜆 = det 𝐴 − 𝜆𝐼 . Polinomial ini disebut polinomial karakteristik dan 𝑝 𝜆 = det 𝐴 − 𝜆𝐼 tersebut disebut sebagai persamaan karakteristik dari matriks 𝐴.

Contoh 2.4.3 Carilah nilai-nilai eigen dari matriks 𝐴=

1 4

1 1

Penyelesaian: Polinomial karakteristik dari matriks 𝐴 adalah det 𝐴 − 𝜆𝐼 = det

1 4

= 1−𝜆

1 𝜆 − 1 0 2

0 𝜆

= det

1−𝜆 4

1 1−𝜆

− 4.

Dan persamaan karakteristik dari matriks 𝐴 adalah 𝜆2 − 2𝜆 − 3 = 0, dengan memfaktorkan 𝜆2 − 2𝜆 − 3 = 0, diperoleh 𝜆−3 𝜆+1 =0 sehingga penyelesaian dari persamaan ini adalah 𝜆1 = 3 dan 𝜆2 = −1. Jadi, nilai-nilai eigen dari matriks 𝐴 tersebut adalah 𝜆1 = 3 dan 𝜆2 = −1.

2.5 Dekomposisi Nilai Singular (Singular Value Decomposition) Dekomposisi nilai singular merupakan suatu teknik pemfaktoran matriks yang berkaitan erat dengan nilai singular dari sebuah matriks yang merupakan karakteristik dari matriks tersebut.


37

Teorema 2.5.1 Misalkan 𝐴 adalah matriks 𝑚 × 𝑛 dan 𝑝 = min 𝑚, 𝑛 . Maka terdapat basis ortonormal 𝐮1 , 𝐮2 , … , 𝐮𝑚 untuk ℝ𝑚 , 𝐯1 , 𝐯2 , … , 𝐯𝑛 untuk ℝ𝑛 dan skalar-skalar 𝜎1 ≥ 𝜎2 ≥ ⋯ ≥ 𝜎𝑝 > 0, sehingga 𝐴 mempunyai suatu dekomposisi nilai singular, 𝐴 = 𝑈Λ𝑉 𝑇 , dengan Λ adalah matriks 𝑚 × 𝑛 yang berbentuk σ1 ⋮ 0 0 ⋮ 0

⋯ 0 ⋱ ⋮ ⋯ σ𝑛 ⋯ 0 ⋱ ⋮ ⋯ 0

jika 𝑚 > 𝑛 = 𝑝, atau

σ1 Λ= ⋮ 0

⋯ 0 ⋱ ⋮ ⋯ σ𝑚

0 ⋮ 0

Λ=

⋯ 0 ⋱ ⋮ ⋯ 0

jika 𝑝 = 𝑚 < 𝑛,

atau

Λ=

𝑈 = 𝐮1 , 𝐮2 , … , 𝐮𝑚 𝑉 = 𝐯1 , 𝐯2 , … , 𝐯𝑛

σ1 0 ⋮ 0

0 σ2 ⋮ 0

0 0 0 0 ⋱ ⋮ 0 σ𝑝

jika 𝑚 = 𝑛 = 𝑝,

adalah matriks ortogonal 𝑚 × 𝑚, dan

adalah matriks ortogonal 𝑛 × 𝑛 dan Λ merupakan

matriks diagonal yang entrinya nilai-nilai singular.

Bukti: 𝐴𝑇 𝐴 adalah matriks simetris berukuran 𝑛 × 𝑛, yaitu matriks persegi yang elemen-elemennya simetri terhadap diagonal utama. Misalkan 𝜆 adalah nilai eigen dari 𝐴𝑇 𝐴 dan 𝐱 adalah vektor eigen yang bersesuaian dengan 𝜆.


Dengan menggunakan Teorema 2.3.1.4, 𝐱 𝐴𝐱

2

2

=

𝐱𝑇 𝐱

2

38

= 𝐱𝑇 𝐱

= 𝐴𝐱 𝑇 𝐴𝐱 = 𝐱 𝑇 𝐴𝑇 𝐴𝐱 = 𝐱 𝑇 𝜆𝐱

karena 𝜆 merupakan suatu skalar, berlaku 𝐴𝐱

2

= 𝐱 𝑇 𝜆𝐱 = 𝜆𝐱 𝑇 𝐱 = 𝜆 𝐱

2

akibatnya 𝐴𝐱 2 𝜆= ≥ 0. 𝐱2 Asumsikan bahwa kolom-kolom dari 𝑉 tersusun terurut sehingga nilai-nilai eigen yang bersesuaian memenuhi 𝜆1 ≥ 𝜆2 ≥ ⋯ ≥ 𝜆𝑛 ≥ 0. dan nilai-nilai singular dari matriks 𝐴 diberikan oleh 𝜎𝑗 =

𝜆𝑗 ,

𝑗 = 1,2, … , 𝑛.

Misalkan 𝑝 merupakan rank dari 𝐴. Karena matriks 𝐴𝑇 𝐴 simetris maka ranknya ditentukan dari banyaknya nilai eigen taknol dari 𝐴𝑇 𝐴. Jadi 𝜆1 ≥ 𝜆2 ≥ ⋯ ≥ 𝜆𝑝 > 0 dan 𝜆𝑝+1 = 𝜆𝑝+2 = ⋯ = 𝜆𝑛 = 0 sehingga matriks 𝐴𝑇 𝐴 juga mempunyai rank 𝑝. Dan hubungan yang sama juga berlaku bagi nilai-nilai singularnya 𝜎1 ≥ 𝜎2 ≥ ⋯ ≥ 𝜎𝑝 > 0 dan 𝜎𝑝+1 = 𝜎𝑝+2 = ⋯ = 𝜎𝑛 = 0 Sekarang, misalkan 𝑉1 = 𝐯1 , 𝐯2 , … , 𝐯𝑝 dan 𝑉2 = 𝐯𝑝+1 , 𝐯𝑝+2 , … , 𝐯𝑛 dan

Λ1 =

σ1 0 0 0

0 σ2 0 0

0 0 ⋱ 0

0 0 0 σ𝑝


39

Jadi Λ1 adalah matriks diagonal 𝑝 × 𝑝 yang entri-entri diagonalnya adalah nilai-nilai singular taknol σ1 , … , σ𝑝 . Selanjutnya matriks Λ 𝑚 × 𝑛 dapat dinyatakan oleh Λ=

Λ1 𝑂

𝑂 . 𝑂

Vektor-vektor dari 𝑉2 adalah vektor-vektor eigen dari 𝐴𝑇 𝐴 untuk 𝜆 = 0, sehingga 𝐴𝑇 𝐴𝐯𝑗 = 𝟎,

𝑗 = 𝑝 + 1, … , 𝑛

dan akibatnya, vektor-vektor kolom dari 𝑉2 membentuk basis ortonormal untuk 𝑁 𝐴𝑇 𝐴 = 𝑁 𝐴 . Dengan demikian, 𝐴𝑉2 = 𝑂 dan karena 𝑉 adalah matriks ortogonal, maka 𝐼 = 𝑉𝑉 𝑇 = 𝑉1 𝑉1 𝑇 + 𝑉2 𝑉2 𝑇 𝐴 = 𝐴𝐼 = 𝐴𝑉1 𝑉1 𝑇 + 𝐴𝑉2 𝑉2 𝑇 = 𝐴𝑉1 𝑉1 𝑇 .

2.1

Kemudian akan dibuktikan bahwa matriks ortogonal 𝑈 berorde 𝑚 × 𝑚 memenuhi 𝐴 = 𝑈Λ𝑉 𝑇 ↔ 𝐴𝑉 = 𝑈Λ

2.2

dan dengan membandingkan 𝑝 kolom-kolom pertama dari setiap ruas dari 2.2 , diperoleh 𝐴𝐯𝑗 = 𝜎𝑗 𝐮𝑗 , 𝑗 = 1, … , 𝑝 sehingga 𝐮𝑗 =

1 𝐴𝐯 , 𝑗 = 1, … , 𝑝 𝜎𝑗 𝑗

2.3


40

akibatnya 𝑈1 = 𝐮1 , … , 𝐮𝑝 dan berdasarkan hal itu, maka 𝐴𝑉1 = 𝑈1 Λ1 .

2.4

Vektor-vektor kolom dari 𝑈1 akan membentuk suatu himpunan ortonormal karena 𝐮𝑖 𝑇 𝐮𝑗 =

1 𝑇 𝑇 𝐯 𝐴 𝜎𝑖 𝑖

1 𝐴𝐯 𝜎𝑗 𝑗

1 ≤ 𝑖 ≤ 𝑝, 1 ≤ 𝑗 ≤ 𝑝

=

1 𝐯 𝑇 𝐴𝑇 𝐴𝐯𝑗 𝜎𝑖 𝜎𝑗 𝑖

=

1 𝐯 𝑇 𝜎 𝐮 𝐯 𝑇𝜎 𝐯 𝐮 𝑇 𝐯 𝜎𝑖 𝜎𝑗 𝑖 𝑗 𝑗 𝑗 𝑗 𝑗 𝑗 𝑗

=

1 𝐯 𝑇 𝜎 2 𝐮 𝐯 𝑇 𝐯 𝐮 𝑇 𝐯𝑗 𝜎𝑖 𝜎𝑗 𝑖 𝑗 𝑗 𝑗 𝑗 𝑗

=

𝜎𝑗 2 𝑇 𝐯 𝐮𝑗 𝐯𝑗 𝑇 𝐯𝑗 𝐮𝑗 𝑇 𝐯𝑗 𝜎𝑖 𝜎𝑗 𝑖

=

𝜎𝑗 𝑇 𝐯 𝐯 = 𝛿𝑖𝑗 𝜎𝑖 𝑖 𝑗

Dari persamaan 2.3 maka setiap 𝐮𝑗 , 1 ≤ 𝑗 ≤ 𝑝 berada dalam ruang kolom 𝐴 dan dimensi dari ruang kolom tersebut adalah 𝑝, sehingga 𝐮1 , … , 𝐮𝑝 membentuk basis ortonormal untuk 𝑅 𝐴 . Berarti ruang vektor 𝑅 𝐴𝑇 = 𝑁 𝐴

⊥

mempunyai dimensi 𝑚 − 𝑝. Misalkan

adalah basis ortonormal untuk 𝑁 𝐴𝑇 dan 𝑈2 = 𝐮𝑝+1 , … , 𝐮𝑚 𝑈 = 𝑈1 𝑈2

𝐮𝑝+1 , … , 𝐮𝑚


Karena

𝐮1 , … , 𝐮𝑝

𝐮𝑝+1 , … , 𝐮𝑚

dan

41

membentuk basis ortonormal,

berarti kita dapat menuliskan 𝐮1 , … , 𝐮𝑝 , 𝐮𝑝+1 , … , 𝐮𝑚 sebagai kombinasi linear 𝑐1 𝐮1 + ⋯ + 𝑐𝑝 𝐮𝑝 + 𝑐𝑝+1 𝐮𝑝+1 + ⋯ + 𝑐𝑚 𝐮𝑚 = 0 sehingga 𝐮1 , … , 𝐮𝑚 akan membentuk basis ortonormal untuk ℝ𝑚 . Akibatnya 𝑈 adalah matriks ortogonal, dan dari persamaan 2.1 dan 2.4 diperoleh 𝑈Λ𝑉 𝑇 = 𝑈1 𝑈2 =

Λ1 𝑂

𝑂 𝑂

𝑉1 𝑇 𝑉2 𝑇

= 𝑈Λ1 𝑉1 𝑇 = 𝐴𝑉1 𝑉1 𝑇 = 𝐴.

Contoh 2.5.2 Tentukan dekomposisi nilai singular dari matriks 1 𝐴= 1 0

1 1 0

Penyelesaian: Langkah 1: akan dihitung 𝐴𝑇 𝐴 =

1 1

1 0 1 0

1 1 2 2 . 1 1 = 2 2 1 0

Langkah 2: mencari nilai-nilai eigen dan nila-nilai singular dari 𝐴𝑇 𝐴. Dengan menerapkan persamaan karakteristik,


𝑝 𝜆 = det

2−𝜆 2

2 = 2−𝜆 2−𝜆

2

42

− 4 = 4 − 4𝜆 + 𝜆2 − 4 = 0

𝜆2 − 4𝜆 = 𝜆 𝜆 − 4 = 0 didapatkan nilai-nilai eigen 𝜆1 = 4 dan 𝜆2 = 0. Akibatnya nilai-nilai singular dari 𝐴, adalah 𝜎1 =

𝜆1 = 2 dan 𝜎2 =

𝜆2 = 0.

Langkah 3:mencari vektor-vektor eigen dari 𝐴𝑇 𝐴 dan kemudiaan membentuk matriks 𝑉. Dari nilai-nilai eigen yang telah diperoleh, dapat dicari vektor eigen yang bersesuaian dengan 𝜆.

Untuk 𝜆1 = 4, dengan mensubstitusikan nilai 𝜆1 ke 𝐴 − 𝜆𝐼, diperoleh 2−4 2

𝐴 − 4𝐼 =

2 −2 2 = . 2−4 2 −2

Kemudian agar mendapatkan vektor eigen dari 𝜆1 , harus dihitung bahwa 𝐴 − 𝜆1 𝐼 𝐱 = 𝟎, −2 2 2 −2

𝑥𝟏 0 𝑥2 = 0

dan bentuk matriks diperbesar sistem tersebut dapat dinyatakan sebagai −2 2 0 . 2 −2 0 kemudian dengan menggunakan eliminasi Gauss diperoleh −2 2 0 2 −2 0

1 2

− 𝑅1

1 2

−1 0 −2 0

−2 𝑅1 +𝑅2

1 0

−1 0 . 0 0


43

Dari bentuk eselon baris didapat bahwa 𝑥𝟏 − 𝑥2 = 0 atau 𝑥𝟏 = 𝑥2 , sehingga 𝑥𝟏 𝑥2 1 𝐱 = 𝑥 = 𝑥 = 𝑥2 2 2 1 Jadi, vektor-vektor eigen dari 𝜆1 mempunyai bentuk 𝑥2

1 , 𝑥2 ∈ ℝ. 1

Dengan proses normalisasi dapat dibentuk 𝐯1 sebagai

𝐯1 =

𝑥𝟏 𝑥2

𝐱 = 𝐱

𝑥𝟏

𝑥𝟏 𝑥2

𝑥2

1 1 1 = 1 = = 2 2 1

1 2

1 2 1

=

2

2 2 2 2

Untuk 𝜆2 = 0, dengan mensubstitusikan nilai 𝜆2 ke 𝐴 − 𝜆𝐼, diperoleh 2−0 2

𝐴 − 0𝐼 =

2 2 2 = . 2−0 2 2

Kemudian agar mendapatkan vektor eigen dari 𝜆2 , harus dihitung bahwa 𝐴 − 𝜆2 𝐼 𝐱 = 𝟎, 2 2

2 2

𝑥𝟏 0 𝑥2 = 0

dan bentuk matriks diperbesar sistem tersebut dapat dinyatakan sebagai 2 2

20 20

kemudian dengan menggunakan proses eliminasi Gauss diperoleh 2 20 2 20

1 2

𝑅1

1 10 2 20

𝑅2 + −2 𝑅1

1 10 . 0 00


44

Dari bentuk eselon baris didapat bahwa 𝑥𝟏 + 𝑥2 = 0 atau 𝑥𝟐 = −𝑥𝟏 , sehingga 𝑥𝟏 𝑥1 1 𝐱 = 𝑥 = −𝑥 = 𝑥1 2 1 −1 Jadi, vektor-vektor eigen dari 𝜆2 mempunyai bentuk 𝑥1

1 , 𝑥 ∈ ℝ. −1 1

Dengan proses normalisasi dapat dibentuk 𝐯2 sebagai

𝐯2 =

𝐱 = 𝐱

=

𝑥𝟏 𝑥2 𝑥𝟏

𝑥2

𝑥𝟏 𝑥2

1 2

1 1 1 = −1 = = 2 2 −1

1 −

2 1 2

2 2 . 2 − 2

Dari vektor 𝐯1 dan 𝐯2 yang diperoleh dapat dibentuk matriks

𝑉 = 𝐯1 , 𝐯2 =

2 2 2 2 2 2 − 2 2

Langkah 4: menentukan ruang baris dari 𝐴 1 𝐴= 1 0

1 1 0

Dengan mereduksi 𝐴 menjadi bentuk eselon baris, maka didapatkan matriks


1 𝑆= 0 0

45

1 0 0

sehingga 1,1 membentuk basis untuk ruang baris dari 𝑆. Karena 𝑆 dan 𝐴 ekivalen baris, maka matriks memiliki ruang baris yang sama sehingga rank dari 𝐴 adalah 1.

Langkah 5: menentukan matriks 𝑈 Dari langkah 4, diketahui bahwa matriks 𝐴 mempunyai rank 1 sehingga dapat dibentuk basis ortonormal untuk 𝑅 𝐴 . Dengan menggunakan persamaan 2.3 , diperoleh

𝐮1 =

2 2 2 2

1 1 1 1 𝐴𝐯1 = 1 1 𝜎1 2 0 0

=

1 2

2 2 = 0

2 2 2 . 2 0

Untuk mencari vektor-vektor kolom yang lain, maka harus dibentuk suatu basis ortonormal untuk 𝑁 𝐴𝑇 . Karena itu perlu ditunjukkan bahwa vektor-vektor kolom dari 𝐴𝑇 =

1 1

1 0 , 1 0

membentuk basis untuk 𝑁 𝐴𝑇 , sehingga 1 1 00 1 1 00

−1 𝑅1 +𝑅2

1 1 0 0

00 . 00

Bentuk eselon baris tersebut melibatkan dua peubah bebas 𝑥1 dan 𝑥3 𝑥2 = −𝑥1 − 0𝑥3 ,


46

misalkan 𝑥1 = 𝛼 dan 𝑥3 = 𝛽, maka 𝑥1 1 1 0 𝑥 𝐱 = 2 = −𝛼 − 0𝛽 = 𝛼 −1 + 𝛽 0 𝑥3 1 0 1

𝛼, 𝛽 ∈ ℝ

Sehingga diperoleh basis dari 𝑁 𝐴𝑇 adalah 𝐱 2 = 1, −1,0

𝑇

dan 𝐱 3 =

0,0,1 𝑇 , dan vektor 𝐱 2 dan 𝐱 3 saling ortogonal. Selanjutnya akan dilakukan proses normalisasi sehingga

𝐮2 =

𝐱2 𝐱2

1 −1 1 1 2 1 0 = = −1 = −1 = 2 2 2 0 0

2 2 2 − 2 0

0 𝐮3 = 0 1

Akibatnya,

𝑈 = 𝐮1 , 𝐮2 , 𝐮3 =

2 2 0 2 2 . 2 2 − 0 2 2 0 0 1

Berdasarkan hasil yang diperoleh bahwa 𝑈 = 𝐮1 , 𝐮2 , 𝐮3

dan

𝑉 = 𝐯1 , 𝐯2 , maka didapat 𝑚 = 3 > 𝑛 = 2 dan 𝑝 = min 3,2 = 2. Kemudian dapat dibentuk matriks diagonal Λ dengan entrinya adalah nilainilai singular yang diperoleh pada langkah 2,


47

2 0 Λ= 0 0 . 0 0 Dari hasil 𝑈, Λ, dan 𝑉 dapat dibentuk dekomposisi nilai singular dari matriks 𝐴 sebagai 𝐴 = 𝑈Λ𝑉 𝑇 ,dengan

𝑈=

2 2 0 2 2 2 ; Λ = 0 2 2 − 0 0 2 2 0 0 1

𝐴 = 𝑈Λ𝑉 𝑇 =

2 2 2 2 0

2 0 2 2 − 0 2 0 1

0 0 ; dan𝑉 𝑇 = 0

2 0 0 0 0 0

2 2 2 2 , 2 2 − 2 2

2 2 2 2 . 2 2 − 2 2

Apabila 𝐴 adalah matriks yang ortogonal, maka invers dari 𝐴 dapat dihitung sebagai 𝐴−1 = 𝑉Λ−1 𝑈 𝑇 , 1 σ1

dengan Λ−1 =

0 ⋮ 0

0 1 σ2

⋮ 0

0

0

0

0

⋱ 0

1

.

⋮

σ𝑛

Contoh 2.5.3 Diberikan matriks 𝐴 = 𝐴−1 untuk matriks 𝐴.

2 2 , carilah dekomposisi nilai singular untuk −1 1


48

Penyelesaian: Dari matriks 𝐴𝑇 𝐴 =

2 2

−1 1

2 2 5 = −1 1 3

3 diperoleh nilai eigen 5

𝜆1 = 8 dan 𝜆2 = 2. Dengan nilai eigen tersebut dapat dihasilkan vektorvektor eigen yang bersesuaian dengan 𝜆1 dan 𝜆2 sebagai − 𝑣1 = −

1 2 1

1

− dan 𝑣2 =

2

.

1

2

2

Selain itu, diperoleh juga nilai singular dari matriks 𝐴 sebagai 𝜎1 = 2 2 dan 𝜎2 = 2. Akibatnya,

𝐮1 =

𝐮2 =

1 1 2 2 𝐴𝑣1 = −1 1 𝜎1 2 2

1 1 2 2 𝐴𝑣2 = 𝜎2 2 −1 1

1

−

2 1

−

−

=

−1 0

2 1 2

1

=

0 1

2

Jadi, SVD dari matriks 𝐴 adalah

𝐴 = 𝑈Λ𝑉 𝑇 =

−1 0 0 1

2 2 0

0 2

− −

1 2 1 2

−

1 2 1 2

.


49

Dengan SVD matriks 𝐴 dapat ditentukan invers matriks 𝐴 sebagai − −1

𝐴

−1

𝑇

= 𝑉Λ 𝑈 = −

=

1 2 1

−

2

1 2 1 2

1 2 2 0

0 1

−1 0 0 1

2

1 1 − 4 2 . 1 1 4 2

2.6 Norma Matriks dan Bilangan Kondisi Dalam menyelesaikan masalah sistem linier, akurasi dari penyelesaian menjadi sesuatu yang perlu diperhatikan. Sebab, semakin akurat penyelesaian yang didapat maka semakin kecil pula galat yang terjadi. Keakuratan penyelesaian sangat bergantung pada seberapa sensitif matriks koefisien dari sistem terhadap adanya perubahan kecil yang terjadi. Sensitifitas dari matriks dapat diukur dengan bilangan kondisi (condition number) matriks tersebut. Bilangan

kondisi suatu matriks taksingular

didefinisikan dari sudut pandang norma matriks dan norma inversnya. Sebelum membahas bilangan kondisi, perlu dipelajari tipe-tipe dari normanorma matriks. 2.6.1 Norma Matriks Berdasarkan penjelasan dalam subbab sebelumnya, kita telah membahas mengenai perhitungan norma pada ruang vektor di ℝ𝑛 .


50

Selanjutnya pada subbab ini akan dijelaskan perhitungan norma pada ruang vektor di 𝑀𝑚 ×𝑛 . Suatu fungsi

. : 𝑀𝑚 ×𝑛 → ℝ disebut norma

matriks, jika untuk sebarang 𝐴, 𝐵 ∈ 𝑀𝑚 ×𝑛 dan 𝛼 ∈ ℝ, memenuhi: (i)

𝐴 ≥0

(ii)

𝐴 = 0 jika dan hanya jika 𝐴 = 𝟎

(iii) 𝛼𝐴 = 𝛼 𝐴 (iv) 𝐴 + 𝐵 ≤ 𝐴 + 𝐵

Teorema 2.6.1.1 Andaikan . adalah norma vektor pada ℝ𝑛 , maka 𝐴 = max 𝐴𝐱 𝐱 =1

adalah norma matriks.

Bukti: Akan dibuktikan bahwa 𝐴 = max 𝐴𝐱 𝐱 =1

memenuhi definisi norma. (i) Untuk setiap 𝐱 = 1, 𝐴𝐱 ≥ 0 max 𝐴𝐱 ≥ 0 𝐱 =1

akibatnya,


51

max 𝐴𝐱 = 𝐴 ≥ 0 𝐱 =1

(ii) Jika 𝐴 = 0, maka max 𝐱 =1 𝐴𝐱 = 0. Berarti 𝐴𝐱 = 𝟎 untuk setiap 𝐱 ∈ ℝ𝑛 , dan

𝐞𝑗 =

0 0 ⋮ 1

sehingga 𝐴𝐞𝑗 = 𝟎 untuk 𝑗 = 1,2, … , 𝑛. Oleh karena itu 𝐴 haruslah suatu matriks nol. Jika 𝐴 = 𝟎 dan 𝐱 ∈ ℝ𝑛 , maka 𝐴𝐱 = 𝟎. Berarti max 𝐱 =1 𝐴𝐱 = 0 sehingga 𝐴 = 0.

(iii) 𝛼𝐴 = max 𝛼 𝐴𝐱 = 𝛼 max 𝐴𝐱 = 𝛼 𝐴 𝐱 =1

𝐱 =1

(iv) 𝐴 + 𝐵 = max 𝐴 + 𝐵 𝐱 𝐱 =1

≤ max 𝐴𝐱 + 𝐵𝐱 𝐱 =1

≤ max 𝐴𝐱 + max 𝐵𝐱 𝐱 =1

𝐱 =1

≤ 𝐴 + 𝐵

Akibat 2.6.1.2 Untuk setiap 𝐳 ≠ 0, 𝐱 dapat ditulis sebagai vektor tak nol 𝐱= sehingga

𝐳 𝐳


𝐴 = max 𝐴𝐱 = max 𝐴. 𝐱 =1

𝐳≠0

𝐳 𝐳

= max 𝐳≠0

52

𝐴𝐳 𝐴𝐳 = max . 𝐳≠0 𝐳 𝐳

Akibat 2.6.1.3 Untuk setiap matriks 𝐴 dan 𝐳 ≠ 𝟎, maka terdapat norma natural

. ,

sehingga 𝐴𝐳 ≤ 𝐴 𝐳

Bukti: 𝐴𝐳 ≤ max 𝐴𝐳 . 𝐳 = 𝐴 . 𝐳 . 𝐳 =1

Dengan mengganti definisi norma vektor pada Teorema 2.6.1.1 dapat diturunkan beberapa norma matriks. Apabila norma vektor . digunakan dalam definisi adalah norma vektor . 𝐴

∞

= max 𝐴𝐱 𝐱 ∞ =1

∞

yang

, maka

∞.

disebut sebagai norma-∞ matriks. Sedangkan, jika digunakan norma vektor .

2

, maka 𝐴

2

disebut sebagai norma-2 matriks.

= max 𝐴𝐱 2 . 𝐱 2 =1


53

Teorema 2.6.1.4 Jika 𝐴 adalah matriks 𝑚 × 𝑛 dengan 𝐴 = 𝑎𝑖𝑗 , maka 𝑛

𝐴

∞

= max

𝑎𝑖𝑗 .

1≤𝑖≤𝑚

𝑗 =1

Bukti: i Akan ditunjukkan bahwa 𝑛

𝐴

∞

≤ max

1≤𝑖≤𝑚

𝑎𝑖𝑗 𝑗 =1

Misalkan 𝐱 adalah matriks berukuran 𝑛 × 1, dengan max1≤𝑖≤𝑚 𝑥𝑖 = 1.

Diberikan matriks 𝐴𝐱 berukuran 𝑚 × 𝑛, sehingga 𝑛

𝐴𝐱

∞

= max 𝐴𝐱 1≤𝑖≤𝑚

𝑖

= max

1≤𝑖≤𝑚

𝑎𝑖𝑗 𝑥𝑗 𝑗 =1

𝑛

≤ max

1≤𝑖≤𝑚

𝑎𝑖𝑗 max 𝑥𝑗 . 1≤𝑗 ≤𝑛

𝑗 =1

Karena max1≤𝑗 ≤𝑚 𝑥𝑗 = 𝐱

∞

= 1, maka 𝑛

𝐴𝐱

∞

≤ max

1≤𝑖≤𝑚


dan akibatnya, 𝑛

𝐴

∞


∞

≤ max

1≤𝑖≤𝑚

𝑎𝑖𝑗 . 𝑗 =1

𝐱

∞

=


54

(ii) Sekarang akan ditunjukkan bahwa 𝑛

𝐴

∞

≥ max

1≤𝑖≤𝑚


Misalkan 𝑝 adalah suatu bilangan bulat dengan 𝑛

𝑛

𝑎𝑝𝑗 = max

1≤𝑖≤𝑚

𝑗 =1


dan vektor 𝐱, dengan koordinat 𝑥𝑗 =

Diberikan 𝐱

∞

1 jika 𝑎𝑝𝑗 ≥ 0 −1 jika 𝑎𝑝𝑗 < 0

= 1 dan 𝑎𝑝𝑗 𝑥𝑗 = 𝑎𝑝𝑗 , untuk setiap 𝑗 = 1,2, … , 𝑛.

Sehingga 𝑛

𝐴𝐱

∞

𝑛

= max

1≤𝑖≤𝑚

𝑎𝑖𝑗 𝑥𝑗 ≥

𝑛

𝑎𝑝𝑗 𝑥𝑗 =

𝑗 =1

𝑗 =1

𝑎𝑝𝑗 𝑗 =1

𝑛

= max

1≤𝑖≤𝑚


maka, 𝑛

𝐴

∞


∞

≥ max

1≤𝑖≤𝑚


Berdasar (i) dan (ii) diperoleh 𝑛

𝐴

∞

= max

1≤𝑖≤𝑚



55

Teorema 2.6.1.5 Jika 𝐴 adalah matriks 𝑚 × 𝑛 dengan dekomposisi nilai singular 𝑈Λ𝑉 𝑇 , maka 𝐴

2

= 𝜎1

dimana, 𝜎1 adalah nilai singular terbesar dari matriks 𝐴.

Bukti: Karena 𝑈 dan 𝑉 adalah ortogonal, 𝐴

2

= 𝑈Λ𝑉 𝑇

Λ

2

= max 𝐱=1

= max

(sifat matriks ortogonal (iv))

𝑥1 2 + 𝑥2 2 + ⋯ +𝑥𝑛 2 𝜎1 2 𝑥1 2 + 𝜎1 2 𝑥2 2 + ⋯ + 𝜎1 2 𝑥𝑛 2 𝑥1 2 + 𝑥2 2 + ⋯ +𝑥𝑛 2 𝜎1 2 𝑥1 2 + 𝑥2 2 + ⋯ +𝑥𝑛 2

𝐱=1

= max 𝜎1 𝐱=1

2

𝜎1 2 𝑥1 2 + 𝜎2 2 𝑥2 2 + ⋯ + 𝜎𝑛 2 𝑥𝑛 2

𝐱=1

≤ max

= Λ

Λ𝐱 2 𝐱2

𝐱=1

≤ max

2

𝑥1 2 + 𝑥2 2 + ⋯ +𝑥𝑛 2 𝑥1 2 + 𝑥2 2 + ⋯ +𝑥𝑛 2 𝑥1 2 + 𝑥2 2 + ⋯ +𝑥𝑛 2

≤ 𝜎1 .

Jika dipilih 𝐱 = 𝐞1 , maka Λ𝐱 2 = 𝜎1 𝐱2


56

sehingga 𝐴

= Λ

2

2

= 𝜎1 .

Contoh 2.6.1.6 Hitunglah 𝐴

∞

dan 𝐴

2

dari matriks 𝐴=

1 1 −1 2

Penyelesaian: 1. Untuk dapat menghitung

𝐴

∞

maka diperlukan menghitung nilai

maksimum yang ada pada setiap baris dari matriks 𝐴, sehingga 3

𝑎1𝑗 = 1 + 1 = 2 𝑗 =1 3

𝑎2𝑗 = −1 + 2 = 3 𝑗 =1

Jadi, 𝐴

∞

= max 2,3 = 3.

2. Untuk menghitung 𝐴

2

maka diperlukan mencari nilai-nilai eigen

dari matriks 𝐴𝑇 𝐴 kemudian menentukan nilai singularnya. 𝐴𝑇 𝐴 =

𝑝 𝜆 = det

1 −1 1 2

2−𝜆 −1

2 −1 1 1 = −1 5 −1 2

−1 = 2−𝜆 5−𝜆 −1 = 0 5−𝜆

= 10 − 2𝜆 − 5𝜆 + 𝜆2 − 1 = 𝜆2 − 7𝜆 + 9 = 0.


57

Untuk mencari nilai eigennya digunakan

𝜆1,2 =

7 ± 49 − 4.1.9 7 ± 13 = 2 2

sehingga

𝜆1 =

7 13 + dan 2 2

𝜆2 =

7 13 − , 2 2

dari hasil tersebut diperoleh 𝜎1 =

𝜆1 = 2,3028

dan

𝜎2 =

𝜆2 = 1,3028.

Berdasarkan nilai singular yang diperoleh, maka

𝐴

2

= 𝜎1 = 2,3028.

2.6.2 Bilangan Kondisi Norma matriks dapat digunakan untuk memperkirakan sensitivitas sistem linier terhadap perubahan yang terjadi pada matriks koefisiennya.

Definisi 2.6.2.1 Suatu matriks 𝐴 disebut berkondisi buruk (ill-condition) apabila perubahan yang relatif kecil dalam entri-entri menyebabkan perubahan yang relatif besar pada penyelesaian 𝐴𝐱 = 𝐛. Sedangkan, matriks 𝐴 dikatakan


58

berkondisi baik (well-condition) jika perubahan yang relatif kecil dalam entri-entri mengakibatkan perubahan yang relatif kecil dalam penyelesaian 𝐴𝐱 = 𝐛.

Jika matriks 𝐴 adalah matriks berkondisi buruk, maka perhitungan terhadap 𝐴𝐱 = 𝐛 memberikan hasil penyelesaian yang kurang begitu akurat. Hal ini disebabkan karena galat-galat kecil yang terjadi dalam proses perhitungan memberikan efek yang sangat drastis terhadap hasil penyelesaian sehingga menyebabkan galat yang sangat besar. Sebaliknya, apabila matriks tersebut berkondisi baik maka akan didapat perhitungan yang memberikan hasil penyelesaian akurat untuk meyelesaikan sistem 𝐴𝐱 = 𝐛. Secara umum, akurasi dari penyelesaian bergantung pada kondisi matriks yang bersangkutan. Misalkan 𝐴 adalah matriks taksingular 𝑛 × 𝑛 yang memenuhi sistem 𝐴𝐱 = 𝐛. Jika 𝐱 adalah penyelesaian eksak terhadap sistem 𝐴𝐱 = 𝐛 dan 𝐱 ′ adalah penyelesaian yang menghampiri penyelesaian eksak dari sistem 𝐴𝐱 = 𝐛, maka selisih di antara 𝐱 dan 𝐱 ′ menghasilkan galat perhitungan yang ditulis sebagai 𝐞 = 𝐱 − 𝐱′ . Untuk menguji keakuratan dari 𝐱 ′ dilakukan dengan cara mensubstitusikan kembali 𝐱 ′ ke dalam sistem 𝐴𝐱 = 𝐛 sehingga diperoleh 𝐴𝐱 ′ = 𝐛′ . Kemudian akan dihitung selisih dari 𝐛′ dengan 𝐛 sehingga diperoleh 𝐫 = 𝐛 − 𝐛′ = 𝐛 − 𝐴𝐱 ′ ,


59

dimana vektor r ini adalah vektor sisa. Dengan menggunakan norma . diperoleh

𝐛−𝐴𝐱 ′ 𝐛

=

𝐫

, dimana 𝐛

𝐫 𝐛

disebut sebagai sisa relatif. Sisa relatif

memberikan nilai perkiraan dari galat relatif, dan nilai perkiraan tersebut bergantung pada kondisi matriks 𝐴. Secara umum, jika matriks 𝐴 berkondisi buruk maka sisa relatif akan lebih kecil dari galat relatifnya. Sebaliknya, untuk matriks berkondisi baik maka sisa relatif dan galat relatif akan saling berdekatan. Karena 𝐫 = 𝐛 − 𝐴𝐱 ′ = 𝐴𝐱 − 𝐴𝐱 ′ = 𝐴𝐞 dan 𝐴 adalah matrik taksingular 𝑛 × 𝑛, maka 𝐞 = 𝐴−1 𝐫, sehingga dengan menggunakan Akibat 2.6.1.3 diperoleh 𝐞 ≤ 𝐴−1 𝐫

2.5

dan 𝐫 = 𝐴𝐞 ≤ 𝐴 𝐞

2.6

dari ketaksamaan 2.5 dan 2.6 diperoleh 𝐫 ≤ 𝐞 ≤ 𝐴−1 𝐫 𝐴

2.7

Karena nilai 𝐱 merupakan penyelesaian eksak terhadap 𝐴𝐱 = 𝐛, dan 𝐴 adalah matrik taksingular maka 𝐱 = 𝐴−1 𝐛. Sehingga dengan menggunakan ketaksamaan 2.7 , didapatkan 𝐛 ≤ 𝐱 ≤ 𝐴−1 𝐛 𝐴

2.8


60

Dari ketaksamaan 2.7 dan 2.8 diperoleh 1 𝐴 𝐴−1

Bilangan 𝐴

𝐫 𝐞 ≤ ≤ 𝐴 𝐛 𝐱

𝐴−1

𝐫 𝐛

𝐴−1 disebut sebagai bilangan kondisi dari matriks 𝐴 yang

diberikan dengan lambang cond(𝐴), sehingga 1 𝐫 𝐞 𝐫 ≤ ≤ cond 𝐴 cond(𝐴) 𝐛 𝐱 𝐛

Ketaksamaan

2.9

terhadap sisa relatif

2.9

tersebut menunjukkan hubungan galat relatif 𝐫 𝐛

𝐞 𝐱

, bahwa semakin bilangan kondisi mendekati nilai 1,

maka galat relatif dan sisa relatif akan berdekatan. Namun jika bilangan kondisi besar, maka galat relatif akan beberapa kali lebih besar dari sisa relatif. Bilangan kondisi dari 𝐴 sesungguhnya memberikan informasi penting mengenai kondisi matriks 𝐴. Misalkan 𝐴′ adalah matriks baru yang dibentuk dengan mengganti sejumlah kecil entri-entri dari 𝐴. Maka, kita dapat membentuk matriks 𝐸 = 𝐴′ − 𝐴 sehingga 𝐴′ = 𝐴 + 𝐸, dimana entrientri dari 𝐸 relatif lebih kecil daripada entri-entri pada 𝐴. Matriks 𝐴 akan berkondisi buruk jika untuk suatu matriks seperti 𝐸 memberikan pengaruh buruk pada perhitungan penyelesaian terhadap 𝐴′ 𝐱 ′ = 𝐛 dan 𝐴𝐱 = 𝐛. Hal tersebut mengakibatkan selisih dari kedua hasil penyelesaian tersebut menjadi sangat besar bedanya. Bilangan kondisi dapat digunakan untuk


61

membandingkan perubahan penyelesaian relatif terhadap 𝐱 ′ , dengan perubahan relatif dalam matriks 𝐴.

Dari 𝐱 = 𝐴−1 𝐛 = 𝐴−1 𝐴′ 𝐱 ′ = 𝐴−1 𝐴 + 𝐸 𝐱 ′ = 𝐴−1 𝐴𝐱 ′ + 𝐴−1 𝐸𝐱 ′ = 𝐱 ′ + 𝐴−1 𝐸𝐱 ′ diperoleh, 𝐱 − 𝐱 ′ = 𝐴−1 𝐸𝐱 ′

Dengan menggunakan Akibat 2.6.1.3, maka 𝐱 − 𝐱 ′ ≤ 𝐴−1

𝐸 𝐱′

atau 𝐱 − 𝐱′ ≤ 𝐴−1 𝐱′

𝐸

Jika ruas kanan pada ketaksamaan 2.10 dikali 𝐱 − 𝐱′ ≤ 𝐴 𝐱′

𝐴−1

2.10

𝐴 𝐴

, diperoleh

𝐸 = cond 𝐴 𝐴

𝐸 𝐴

2.11

Untuk lebih memahami maksud dan perhitungan dari ketaksamaan 2.11 akan digunakan

.

∞.

Perhatikan contoh berikut.


62

Contoh 2.6.2.1 Diberikan sistem (a) 2,0000𝑥1 + 2,0000𝑥2 = 6,0000 2,0000𝑥1 + 2,0005𝑥2 = 6,0010 yang mempunyai penyelesaian eksak 𝐱 =

1 . Dan dengan melakukan 2

sedikit perubahan diperoleh sistem baru, sebagai sistem (b) 2,000𝑥1 + 2,000𝑥2 = 6,000 2,000𝑥1 + 2,001𝑥2 = 6,001 yang memiliki penyelesaian 𝐱 ′ =

2 . Hitunglah perbandingan perubahan 1

penyelesaian relatif terhadap 𝐱 ′ dengan perubahan relatif dalam matriks 𝐴.

Penyelesaian: Dari sistem (a) dan sistem (b) dapat diperoleh matriks koefisien 𝐴 dan 𝐴′ , sehingga 𝐴= 𝐴−1 =

2 2 2 ; 𝐴′ = 2 2,0005 2

1 2,0005 0,001 −2

2000,5 −2000 −2 = 2 −2000 2000

Kemudian dibentuk matriks 𝐸 = 𝐴′ − 𝐴, 𝐸=

2 dan 2,001

0 0

0 0,0005


63

dan galat relatif dalam matriks 𝐴 adalah 𝐸 𝐴

∞

=

∞

0,0005 ≈ 0,0001 4,0005

Sedangkan bilangan kondisi dari matriks 𝐴 sebagai cond∞ 𝐴 = 𝐴

∞

𝐴−1

∞

= 4,0005 4000,5 ≈ 16004.

Dengan menggunakan ketaksamaan 2.10 dapat ditentukan batas dari galat relatif sebagai cond∞ 𝐴

𝐸 𝐴

∞

= 16004 0,0001 = 1,6004

∞

dan galat relatif sesungguhnya bagi sistem adalah 1 2 − 2 1 2 1 ∞

𝐱 − 𝐱′ ∞ = 𝐱′ ∞

∞

=

−1 1 2 1

∞

=

1 2

∞

Jadi, perbandingan perubahan penyelesaian relatif terhadap 𝐱 ′ dengan perubahan relatif dalam matriks 𝐴 adalah 1 < 1,6004. 2 Selain menggunakan

.

∞,

perhitungan bilangan kondisi dari matriks

𝐴, yang dinotasikan sebagai cond 𝐴 dapat juga dihitung menggunakan .

2

.


64

Teorema 2.6.2.2 Jika 𝐴 = 𝑈Λ𝑉 𝑇 adalah taksingular, maka cond2 𝐴 =

𝜎1 . 𝜎𝑛

Bukti: Karena 𝐴 adalah taksingular berarti 𝐴 memiliki invers, yaitu 𝐴−1 dan nilainilai singular dari 𝐴−1 = 𝑉Λ−1 𝑈 𝑇 tersusun dalam urutan menurun sebagai 1 1 1 ≥ ≥⋯≥ . 𝜎𝑛 𝜎𝑛−1 𝜎1 Akibatnya 𝐴−1

2

=

1 𝜎𝑛

sehingga cond2 𝐴 = 𝐴 2 . 𝐴−1

2

= 𝜎1 .

1 𝜎1 = . 𝜎𝑛 𝜎𝑛

Contoh 2.6.2.3 Dengan menggunakan matriks pada contoh 2.6.1.6, 𝐴=

Hitunglah bilangan kondisi dari 𝐴.

1 1 −1 2


65

Penyelesaian: Berdasarkan pembahasan pada contoh 2.6.1.6 didapatkan bahwa nilainilai singular dari 𝐴 adalah 𝜎1 = 2,3028 dan 𝜎2 = 1,3028. Dari hasil tersebut dapat dihitung

cond2 𝐴 =

𝜎1 2,3028 = = 1,768. 𝜎2 1,3028

B. Kalkulus Pada subbab ini akan dijelaskan mengenai teori-teori kalkulus yang akan digunakan sebagai landasan pembahasan pada bab-bab berikutnya.

2.7 Big-O Andaikan 𝐠 adalah fungsi bernilai riil yang didefinisikan pada kitar-𝛿 dengan pusat 𝐱 ∈ ℝ𝑛 , yang ditulis 𝐲 ∈ ℝ𝑛 | 𝐲 − 𝑥 < 𝛿 , dengan 𝐲 ≠ 𝐱. Misal 𝐡: Ω ↦ ℝ𝑚 adalah fungsi yang didefinisikan dalam suatu domain (daerah asal) Ω ⊂ ℝ𝑛 yang memuat 𝐲, maka 𝐡 𝐲 = 𝛰(𝐠 𝐲 ), diartikan bahwa 𝐡(𝐲) 𝐠(𝐲) terbatas. Jadi, terdapat bilangan 𝑀 > 0 dan 𝛿 > 0, sehingga jika 𝐲 − 𝐱 < 𝛿, 𝐲 ∈ Ω berakibat 𝐡(𝐲) ≤𝑀 𝐠(𝐲)


66

Contoh 2.7.1 Tunjukkan bahwa ℎ 𝑦 = 𝑦 2 + 2𝑦 + 1 adalah 𝛰 𝑦 2 .

Penyelesaian: Akan ditentukan bilangan bulat positif 𝑀 dan 𝛿 sehingga untuk setiap 𝑦 ≥ 𝛿, berlaku 𝑦 2 + 2𝑦 + 1 ≤ 𝑀 𝑦 𝟐

Ambil 𝑦 > 1, maka didapat 0 ≤ 𝑦 2 + 2𝑦 + 1 ≤ 𝑦 2 + 2𝑦 2 + 𝑦 2 = 4 𝑦 4

Dengan demikian, dari persamaan di atas diperoleh nilai 𝑀 = 4 dengan 𝛿 = 1.

2.8 Fungsi bernilai vektor Teorema 2.8.1 1

Misalkan 𝐴 adalah matriks invertibel dan 𝑓 𝐱 = 2 𝐴𝐱 − 𝐛 2 . Maka, (i) 𝐱 ∗ adalah titik minimum untuk 𝑓 jika dan hanya jika 𝐱 ∗ adalah penyelesaian persamaan 𝐴𝐱 = 𝐛. (ii) Persamaan titik kritis pada 𝑓 adalah 𝐴𝑇 𝐾𝐱 = 𝐴𝑇 𝐛. (iii) Persamaan titik kritis dari 𝑓 ekuivalen dengan persamaan 𝐴𝐱 = 𝐛.


67

Bukti : ←

(i) 1 2

Andaikan 𝐱 ∗ memenuhi 𝐴𝐱 ∗ = 𝐛, sehingga 𝑓 𝐱 ∗ =

𝐴𝐱 ∗ − 𝐛

2

1

=2 0

2

= 0. Padahal 𝑓 𝐱 ∗ ≥ 0, sehingga 𝐱 ∗ titik

minimum dari 𝑓. Karena 𝐱 ∗ memenuhi 𝐴𝐱 ∗ = 𝐛 maka didapat 𝐱 ∗ = 𝐴−1 𝐛, akibatnya 𝐱 ∗ adalah satu-satunya titik minimum dari 𝑓.

→

Andaikan 𝐱 ∗ titik minimum dari 𝑓 sehingga 𝑓 𝐱 ∗ = 0.

Berarti

1

𝑓 𝐱 ∗ = 2 𝐴𝐱 ∗ − 𝐛

2

= 0,

akibatnya

𝐴𝐱 ∗ − 𝐛 = 0

sehingga 𝐴𝐱 ∗ = 𝐛. Hal ini menunjukkan bahwa 𝐱 ∗ satu-satunya penyelesaian yang memenuhi 𝐴𝐱 ∗ = 𝐛.

(ii)

Turunan 𝑓 di 𝐱, pada arah 𝐡, diberikan oleh 𝑓 𝐱 + 𝜖𝐡 − 𝑓(𝐱) 𝜖→0 𝜖

𝑑𝑓𝑥 𝐡 = lim

1 𝐴 𝐱 + 𝜖𝐡 − 𝐛 2 − 𝐴𝐱 − 𝐛 𝜖→0 2𝜖

= lim

dengan aturan hasil kali dalam 𝐱

2

2

= 𝐱, 𝐱 , didapat

1 𝐴 𝐱 + 𝜖𝐡 − 𝐛, 𝐴 𝐱 + 𝜖𝐡 − 𝐛 − 𝐴𝐱 − 𝐛, 𝐴𝐱 − 𝐛 𝜖→0 2𝜖


1 𝜖→0 2𝜖

= lim

𝐴𝐱 + 𝜖𝐴𝐡 − 𝐛, 𝐴𝐱 + 𝜖𝐴𝐡 − 𝐛 − 𝐴𝐱 − 𝐛, 𝐴𝐱 − 𝐛

1 𝐴𝐱 − 𝐛 + 𝜖𝐾𝐡, 𝐴𝐱 − 𝐛 + 𝜖𝐴𝐡 − 𝐴𝐱 − 𝐛, 𝐴𝐱 − 𝐛 𝜖→0 2𝜖

= lim


68

1 𝐴𝐱 − 𝐛, 𝐴𝐱 − 𝐛 + 𝐴𝐱 − 𝐛, 𝜖𝐴𝐡 + 𝜖𝐴𝐡, 𝐴𝐱 − 𝐛 𝜖→0 2𝜖

= lim

− 𝐾𝐱 − 𝐲, 𝐾𝐱 − 𝐲

dengan aturan 𝐱, 𝐲 = 𝐲, 𝐱 dan 𝐱, 𝛽𝐲 = 𝛽 𝐱, 𝐲 menjadi 1 2𝜖 𝐴𝐱 − 𝐛, 𝐴𝐡 𝜖→0 2𝜖


= 𝐴𝐱 − 𝐲, 𝐴𝐡

kemudian dengan aturan hasil kali dalam 𝒙, 𝐲 = 𝐱 𝑇 𝐲, diperoleh 𝑑𝑓𝑥 𝐡 = 𝐴𝐱 − 𝐲, 𝐴𝐡 = 𝐴𝐱 − 𝐛 𝑇 𝐴𝐡 =

𝐴𝐱 − 𝐛 𝑇 𝑎 𝐡

= 𝐴𝑇 𝐴𝐱 − 𝐛 , 𝐡 .

Sehingga 𝑑𝑓𝑥 𝐡 untuk setiap 𝐡 ∈ ℝ𝑛 , ∇𝑓 𝐱 = 𝐴𝑇 𝐴𝐱 − 𝐛 . dimana ∇𝑓 𝐱 adalah vektor gradien dari 𝑓.

Kemudian agar mendapatkan persamaan titik kritisnya maka nilai dari ∇𝑓 𝐱 = 0, sehingga 𝐴𝑇 𝐾𝐱 = 𝐴𝑇 𝐛. Persamaan

2.12

persamaan normal.

2.12

yang diperoleh ini sebelumnya dikenal sebagai


69

(iii) Diketahui bahwa 𝐴 adalah matriks invertibel jika dan hanya jika transposenya, yaitu 𝐴𝑇 juga invertibel dan

𝐴𝑇

−1

= 𝐴−1 𝑇 .

Kemudian dengan mengalikan kedua sisi pada persamaan dengan 𝐴𝑇

−1

, diperoleh 𝐴𝑇

−1 𝑇

𝐴 𝐴𝐱 = 𝐴𝑇

−1 𝑇

𝐴 𝐛

𝐼𝐴𝐱 = 𝐼𝐛, maka 𝐴𝐱 = 𝐛.

2.12


70

BAB III INVERSE PROBLEM

A. Prinsip Dasar Inverse Problem Dalam

matematika,

permasalahan,

yaitu

terdapat

metode

dua

cara

penyelesaian

untuk

langsung

meyelesaikan dan

metode

penyelesaian tidak langsung. Metode penyelesaian langsung adalah cara penyelesaian dengan mengoperasikan input dalam sistem kemudian diperoleh output. Metode penyelesaian tidak langsung adalah cara penyelesaian dengan menduga input, berdasar informasi sistem dan output yang diberikan. Pada kesempatan ini, penulis akan membahas mengenai metode penyelesaian secara tidak langsung. Metode penyelesaian tidak langsung pada prinsipnya untuk menduga input berdasar dua informasi penting, yaitu sistem dan output. Menduga input berarti menyelesaikan permasalahan dengan menggunakan invers dari permasalahan, sehingga metode penyelesaian ini dinamakan sebagai Inverse Problem. Agar dapat lebih memahami metode invers problem, perhatikan gambar berikut.

Inverse Problem Sistem

Input

Output

Gambar 3.1. Prosedur metode Inverse Problem


71

Dalam melakukan perhitungan untuk mendapatkan penyelesaian berupa input terkadang tidak mudah. Terlebih, apabila sistem yang ada pada masalah sulit untuk diselesaikan, sehingga tidaklah mungkin menyelesaikannya

secara manual.

Karena

alasan tersebut,

maka

digunakanlah perhitungan dengan komputer. Sebab, komputer dapat membantu menyelesaikan perhitungan secara lebih akurat dan cepat. Ada beberapa faktor yang dapat mempengaruhi keakuratan penyelesaian. Pertama, sistem yang kurang stabil. Kedua, algoritma yang digunakan untuk menyelesaikan masalah invers tersebut. Dengan mengetahui faktorfaktor tersebut, maka mengontrol penyelesaian agar menghasilkan galat yang terkecil adalah tujuan dari metode invers problem ini. Karena semakin kecil galat, maka nilai dari penyelesaian yang didapat akan semakin mendekati nilai penyelesaian eksaknya.

3.1 Kestabilan Algoritma pada Sistem Seperti yang telah dijelaskan bahwa ada beberapa faktor yang dapat mempengaruhi

keakuratan

penyelesaian,

salah

satunya

mengenai

kestabilan algoritma. Sebuah algoritma dikatakan stabil, apabila perubahan galat kecil yang terjadi dalam data awal memberikan perubahan galat kecil pada hasil akhir. Sebaliknya, apabila perubahan galat kecil dalam data awal menghasilkan perubahan galat yang besar pada hasil akhir, algoritma dikatakan tidak stabil. Gagasan mengenai kondisi dan kestabilan sistem penting untuk dipahami. Sebab, hal ini dapat mempengaruhi besarnya


72

galat pada perhitungan untuk mendapatkan input. Karena tidak mungkin mendapatkan input optimal, apabila sebelumnya belum diketahui bagaimana kondisi dan kestabilan sistem yang digunakan pada perhitungan masalah invers. Dalam melakukan perhitungan terdapat beberapa pilihan algoritma yang dapat digunakan untuk menyelesaikan masalah invers. Dari beberapa kemungkinan itu harus dipilih algoritma terbaik, yang menghasilkan galat terkecil pada penyelesaian. Perhatikan contoh berikut

Contoh 3.1.1

Algoritma yang digunakan:

Selesaikan sistem 𝑥 + 2𝑦 = 3 1,001𝑥 + 2𝑦 = 3,001 dan tentukan kestabilan dari sistem tersebut.

1. Eliminasi nilai 𝑦 2. Substitusikan nilai 𝑦 ke salah satu persamaan 3. Tentukan nilai 𝑥

Penyelesaian: Dengan menjumlahkan persamaan pertama dan kedua, diperoleh 𝑥1 + 2𝑥2 = 3 1,001𝑥1 + 2𝑥2 = 3,001 −0,001𝑥1 + 0 = −0,001 dari −0,001𝑥1 = −0,001, didapat nilai 𝑥1 = 1. Kemudian substitusikan 𝑥1 = 1 ke persamaan 𝑥1 + 2𝑥2 = 3, sehingga didapatkan nilai 𝑦 = 1. Jadi, penyelesaian dari sistem ini adalah 𝑥1 = 1 dan 𝑥2 = 1.


73

Selanjutnya untuk melihat kestabilan sistem, bilangan di ruas kanan pada persamaan kedua akan diberi perubahan kecil sebesar 𝛿 = 0,002, sehingga 𝑥1 + 2𝑥2 = 3 1,001𝑥1 + 2𝑥2 = 3,003

dengan mengurangkan persamaan pertama dan kedua, diperoleh 𝑥1 + 2𝑥2 = 3 1,001𝑥1 + 2𝑥2 = 3,003 −0,001𝑥1 + 0 = −0,003

dari −0,001𝑥1 = −0,003, didapat nilai 𝑥1 = 3. Kemudian substitusikan 𝑥1 = 3 ke persamaan 𝑥1 + 2𝑥2 = 3, sehingga 2𝑥2 = 3 − 3 = 0 dan diperoleh nilai 𝑥2 = 0. Jadi, penyelesaian dari sistem setelah dipengaruhi 𝛿 adalah 𝑥1′ = 3 dan 𝑥2′ = 0. Dari perhitungan tersebut didapatkan bahwa penyelesaian eksaknya adalah 𝐱 =

3 1 dan penyelesaian hampirannya 𝐱 ′ = . Maka galat dari 0 1

perhitungan tersebut ditulis sebagai 𝐞 = 𝐱 − 𝐱 ′ =

−2 dan galat relatif 1

diberikan oleh 𝐞 𝐱

∞ ∞

=

2 = 2. 1

Selanjutnya akan dihitung vektor sisa sebagai 𝐫 = 𝐛 − 𝐛′ =

3 3 0 − = 3,001 3,003 0,002


74

kemudian dengan menggunakan norma-∞ diperoleh sisa relatif sebagai 𝐫∞ 𝐛 − 𝐛′ = 𝐛∞ 𝐛∞

∞

=

0,002 ≈ 0,000666. 3,001

Setelah itu, akan dilihat bagaimana bilangan kondisi dari 𝐴=

1 1,001

2 2

dan diperoleh bahwa

𝐴−1 = −

=

1 2 0,002 −1,001

−1000 500,5

−2 = 1

2 2 0,002 0,002 1,001 1 − 0,002 0,002

−

1000 500

Dari perhitungan tersebut didapatkan bahwa 𝐴−1

∞

= 2000, sehingga cond∞ 𝐴 = 𝐴

∞

. 𝐴−1

𝐴 ∞

∞

= 3,001 dan

= 6002.

Berdasarkan perhitungan di atas didapat bahwa galat relatif dari sistem sebesar 2 dan sisa relatif sebesar 0,000666, sehingga galat relatif besarnya 3003 kali sisa relatifnya. Ini tidak mengherankan, jika diperoleh cond∞ 𝐴 = 6002. Karena diperoleh nilai cond∞ 𝐴 = 6002, hal tersebut menunjukkan bahwa kondisi dari matriks 𝐴 adalah buruk. Sehingga apabila dilakukan perubahan sebesar 𝛿 akan menyebabkan perubahan besar pada penyelesaian sistem. Akibatnya, algoritma yang digunakan untuk menyelesaikan sistem tersebut adalah tidak stabil.


75

Masalah kestabilan dalam menentukan penyelesaian sangat perlu diperhatikan, sebab tidak semua permasalahan mempunyai penyelesaian eksak. Sehingga untuk menyakinkan keakuratan dari perhitungan yang dilakukan perlu untuk menunjukkan seberapa akurat penyelesaian yang didapat tersebut. Agar meyakinkan bahwa penyelesaian yang diperoleh memang stabil dan akurat untuk dijadikan penyelesaian dari masalah. Setelah memahami masalah kestabilan algoritma, selanjutnya perlu dipahami mengenai eksistensi dan ketunggalan suatu penyelesaian ketika menyelesaikan permasalahan dengan metode inverse problem.

3.2 Eksistensi dan Ketunggalan Penyelesaian Dalam menyelesaikan masalah dengan metode inverse problem muncul kesulitan ketika menghubungkan informasi yang diperoleh dari output permasalahan dengan informasi yang sebenarnya dibutuhkan ketika menentukan penyelesaian. Hal tersebut tentunya cukup rumit dilakukan, sebab harus diketahui secara pasti bagaimana informasi yang ada pada output memberikan pengaruh terhadap masalah yang akan diselesaikan. Perhatikan contoh di bawah ini.

Contoh 3.2.1 Carilah persamaan garis, jika diketahui data 0,3 , 1,6 , 2,9 dan 3,15 .


76

Penyelesaian: 0,3 , 1,6 , 2,9

Diasumsikan bahwa data

dan

3,15

memenuhi

persamaan garis 𝑦 = 𝑎𝑥 + 𝑏, dengan 𝑎 dan 𝑏 adalah konstanta yang berubah-ubah. Sehingga, didapatkan sistem persamaan dengan variabel yang tidak diketahui 𝑎 dan 𝑏, 0𝑎 + 𝑏 = 3 𝑎+𝑏 =6 2𝑎 + 𝑏 = 9 3𝑎 + 𝑏 = 15

Sistem persamaan linier di atas dapat ditulis sebagai 𝐴𝐱 = 𝐛, dengan 0 1 2 3

𝑎 𝐱= ,𝐴 = 𝑏

1 1 ,𝐛 = 1 1

3 6 9 15

sehingga didapat 𝐴𝐱 = 𝐛, 0 1 2 3

1 1 1 1

𝑎 = 𝑏

3 6 . 9 15

Kemudian dari persamaan tersebut diperoleh persamaan normal 𝐴𝑇 𝐴𝐱 = 𝐴𝑇 𝐛 sebagai 0 1 1 1

2 3 1 1

0 1 2 3 14 6

1 1 1 1 6 4

𝑎 0 1 = 𝑏 1 1 𝑎 69 = 𝑏 33

2 3 1 1

3 6 9 15


Dari persamaan normal di atas didapat matriks 𝐱 = 𝐴𝑇 𝐴 1 4 −6 𝑎 = 𝑏 20 −6 14

−𝟏 𝑇

𝐴 𝐛, sebagai

69 33

78 20 48 20

𝑎 = 𝑏 78

77

39

48

24

Sehingga, diperoleh nilai 𝑎 = 20 = 10 = 3,9 dan 𝑏 = 20 = 10 = 2,4. Jadi, persamaan

garis

0,3 , 1,6 , 2,9

yang

digunakan 3,15

dan

untuk

adalah

menghampiri

𝑦 = 3,9𝑥 + 2,4.

data Dengan

menggunakan persamaan 𝑦 = 3,9𝑥 + 2,4 dapat diperoleh nilai 𝐛 baru 0 1 yang ditulis sebagai 𝐛′ = 3,9 + 2,4 2 3 Untuk

menguji

menghampiri data

keakuratan

1 1 1 1

2,4 6,3 . 10,2 14,1

=

𝑦 = 3,9𝑥 + 2,4

persamaan

0,3 , 1,6 , 2,9

dan

dalam

3,15 . Akan ditunjukkan

dengan menghitung besar galat relatif yang terjadi antara 𝐛 dan 𝐛′ , sehingga

𝐛 − 𝐛′ =

2,4 3 6,3 6 − 10,2 9 14,1 15

=

0,6 −0,3 −1,2 0,9

=

1,2 = 0,08. 15

dan 𝐛 =

diperoleh sisa relatif sebagai 𝐛 − 𝐛′ 𝐛∞

∞

3 6 9 15


78

Berdasarkan hasil di atas persamaan 𝑦 = 3,9𝑥 + 2,4 mempunyai sisa relatif pada perhitungan sebesar 0,08, sehingga persamaan tersebut merupakan persamaan yang akurat untuk digunakan sebagai penyelesaian. Ketika menyelesaikan suatu sistem persamaan terkadang mendapatkan sistem yang tidak memiliki penyelesaian. Hal ini menyebabkan eksistensi dan ketunggalan dari penyelesaian menjadi tidak terpenuhi. Untuk itu masalah yang akan diselesaikan perlu dimodifikasi ulang, sehingga dapat ditentukan suatu nilai yang memberikan penyelesaian dari masalah.

Contoh 3.2.2 Diberikan sistem 𝑥1 + 𝑥2 = 1 𝑥1 − 𝑥2 = 3 −𝑥1 − 2𝑥2 = −2 Carilah 𝑥1 dan 𝑥2 yang menyelesaikan persamaan tersebut.

Penyelesaian: Sistem persamaan linier di atas dapat ditulis sebagai 𝐴𝐱 = 𝐛, dengan 𝑥1 𝐱 = 𝑥 ,𝐴 = 2

1 1 1 , 𝐛 = 1 −1 3 −1 −2 −2

sehingga didapat 𝐴𝐱 = 𝐛, 1 1 1 −1 −1 −2

𝑥1 𝑥2 =

1 3 . −2


79

Sistem tersebut dapat dinyatakan sebagai matriks diperbesar 1 1 1 1 −1 3 −1 −2 −2 sehingga menggunakan eliminasi Gauss didapatkan 1 1 1 1 1 −1 3 ⟶ 0 −1 −2 −2 0

1 1 1 −1 . 0 1

Dari baris terakhir dari matriks yang sudah dieliminasi tersebut menunjukkan bahwa sistem adalah tak konsisten, sehingga menyebabkan penyelesaian dari sistem menjadi tidak ada. Namun, nilai 𝐛 tersebut dapat dihampiri dengan suatu 𝐴𝐱 tertentu sehingga galat di antara 𝐛′ dan 𝐛 dapat sekecil mungkin. Dengan menggunakan metode kuadrat terkecil akan dicari sebuah vektor 𝐱, sehingga dapat ditentukan 𝐴𝐱 yang terdekat dengan 𝐛. Metode kuadrat terkecil ini akan meminimumkan galat dari perhitungan 𝐛 − 𝐛′ . Untuk menyelesaikan 𝐴𝐱 = 𝐛 dengan metode kuadrat terkecil, maka kita harus menggunakan persamaan normal 𝐴𝑇 𝐴𝐱 = 𝐴𝑇 𝐛, sehingga diperoleh 1 1 −1 1 −1 −2

1 1 1 −1 −1 −2

𝑥1 1 𝑥2 = 1

3 −2 −2 6

𝑥1 6 𝑥2 = −6

selanjutnya akan diselesaikan 𝐱 = 𝐴𝑇 𝐴

1 −1 −1 −2

−𝟏 𝑇

𝐴 𝐛, sehingga didapat

penyelesaian tunggal untuk 𝐱, sebagai 1 6 2 𝑥1 𝐱= 𝑥 = 2 12 2 3

1 3 −2

2 6 = . −0,5 −6


80

Dari 𝐱 yang diperoleh dapat dibentuk 1 1 𝐛 = 𝐴𝐱 = 1 −1 −1 −2 ′

1,5 2 = 2,5 , −0,5 −1

maka 1 1,5 0,5 𝐛 − 𝐛 = 3 − 2,5 = 0,5 −2 −1 1 ′

dan sisa relatif 𝐛′ terhadap 𝐛 sebesar 𝐛 − 𝐛′ 𝐛∞

∞

=

1 ≈ 0,333 3

sehingga selisih antara 𝐛′ terhadap 𝐛 relatif cukup kecil. Berdasarkan perhitungan di atas diperoleh penyelesaian 𝐱=

2 . −0,5

Dalam menyelesaikan suatu sistem terkadang diperoleh lebih dari satu penyelesaian, bahkan mungkin sampai takhingga banyak penyelesaian. Tentunya ini menjadikan ketunggalan penyelesaian menjadi tidak terpenuhi. Untuk itu perlu ditambahkan suatu syarat tambahan agar membatasi penyelesaian sehingga diperoleh penyelesaian tunggal.

Contoh 3.2.3 Diberikan sistem 𝑥1 + 𝑥2 + 3𝑥3 = −2 −𝑥1 + 3𝑥2 + 𝑥3 = 0 𝑥1 + 2𝑥2 + 4𝑥3 = 8


81

Carilah penyelesaian untuk SPL di atas dan memenuhi 𝐱 = 1 dan 𝑥1 , 𝑥2 , 𝑥3 > 0. Penyelesaian: Sistem persamaan linier dapat ditulis sebagai 𝐴𝐱 = 𝐛, dengan 𝑥1 1 1 3 −2 𝑥 𝐱 = 2 , 𝐴 = −1 3 1 , 𝐛 = 0 𝑥3 1 2 4 8 sehingga didapat 𝐴𝐱 = 𝐛, 1 1 3 −1 3 1 1 2 4

𝑥1 −2 𝑥2 = 0 . 𝑥3 8

Sistem tersebut dapat dinyatakan sebagai matriks diperbesar 1 1 −1 3 1 2

3 −2 1 0 4 8

sehingga menggunakan eliminasi Gauss didapatkan 1 1 3 −2 −1 3 1 0 1 2 4 8

1 1 0 4 0 1

3 −2 4 −2 1 10

𝑅3 + −1 𝑅1

1 𝑅 4 2

1 1 0 1 0 0

1 0 0

−2 3 1 1 −2 0 21 2

1 1 3 −2 −1 3 1 0 0 1 1 10

1 3 −2 1 1 1 −2 1 1 10

1 0 0

𝑅2 +𝑅1

𝑅3 + −1 𝑅2

−2 1 1 3 1 0 1 1 −2 0 0 0 21 2

3

𝑅1 + −1 𝑅2

1 3 −2 4 4 −2 1 1 10

−2

1 0 2 1 0 1 1 −2 0 0 0 21 2


82

sehingga diperoleh bentuk eselon baris 3

1 0 0 1 0 0

−2

2 1 1 −2 . 0 21 2

Dari baris terakhir yang diperoleh terlihat bahwa sistem tidak konsisten, sehingga menyebabkan penyelesaian dari sistem menjadi tidak ada. Karena itu, sistem tersebut perlu dimodifikasi menggunakan persamaan normal 𝐴𝑇 𝐴𝐱 = 𝐴𝑇 𝐛, sehingga diperoleh 1 1 3

−1 1 3 2 1 4

1 1 3 −1 3 1 1 2 4

𝑥1 1 −1 1 𝑥2 = 1 3 2 𝑥3 3 1 4

3 0 6

𝑥1 6 𝑥2 = 14 𝑥3 26

0 14 14

6 14 26

−2 0 8

dan sistem baru tersebut dapat dinyatakan sebagai matriks diperbesar 3 0 0 14 6 14

6 6 14 14 . 26 26

Dengan menggunakan proses eliminasi Gauss didapatkan 3 0 0 14 6 14

6 6 14 14 26 26

3 0 0 14 0 14

6 6 14 14 14 14

3 0 0 14 0 0

6 6 14 14 0 0

𝑅3 + −2 𝑅1

𝑅3 + −1 𝑅2

3 0 0 14 0 14

6 6 14 14 14 14

3 0 0 14 0 0

6 6 14 14 0 0

1 1 𝑅 dan 𝑅 3 1 14 2

1 0 0 1 0 0

22 11 00


83

dan diperoleh bentuk eselon baris 1 0 22 0 1 11 . 0 0 00 Dari bentuk eselon baris tersebut dapat dilihat bahwa sistem konsisten, dan mempunyai satu peubah bebas. Jika peubah bebas tersebut dipindahkan ke ruas kanan, akan diperoleh 𝑥1 = 2 − 2𝑥3 𝑥2 = 1 − 𝑥3

Misalkan 𝑥3 = 𝛼, dengan 𝛼 ∈ ℝ 𝑥1 2 − 2𝛼 sehingga didapatkan penyelesaian 𝐱 = 𝑥2 = 1 − 𝛼 . 𝑥3 𝛼 Penyelesaian 𝐱 tersebut akan mempunyai takhingga banyak penyelesaian yang mungkin terjadi untuk menyelesaikan sistem. Namun, kita cukup memilih sebuah penyelesaian untuk 𝐱, yang memenuhi 𝐱 = 1 dan 𝑥1 , 𝑥2 , 𝑥3 > 0, sehingga 𝐱 =

2 − 2𝛼 2 − 2𝛼

2

2

+ 1−𝛼

+ 1−𝛼

2

2

+ 𝛼

+ 𝛼

2

2

=1

=1

4 − 8𝛼 + 4𝛼 2 + 1 − 2𝛼 + 𝛼 2 + 𝛼 2 = 1 6𝛼 2 − 10𝛼 + 5 = 1 6𝛼 2 − 10𝛼 + 4 = 0


84

Dengan menerapkan rumus 𝛼1,2

−𝑏 ± 𝑏 2 − 4𝑎𝑐 10 ± = = 2𝑎 =

𝛼1,2 =

−10 2 − 4 6 4 2 6

10 ± 100 − 96 12 10 ± 4 10 ± 2 = 12 12

akan diperoleh 𝛼1 =

10 + 2 12 10 − 2 8 2 = = 1 ; 𝛼2 = = = . 12 12 12 12 3

sehingga penyelesaian untuk 𝛼1 = 1 adalah 𝐱=

2 − 2𝛼 2−2 1 1−𝛼 = 1− 1 𝛼 1

0 = 0 1

dan penyelesaian untuk 𝛼2 = 2 3 2 − 2𝛼 𝐱= 1−𝛼 = 𝛼

2 3 2 1− 3

2

2−2

2

3

=

1 2

3 3 . 3

Jadi, penyelesaian untuk sistem yang memenuhi 𝐱 = 1 dan 𝑥1 , 𝑥2 , 𝑥3 > 0 adalah 2 𝐱=

1 2

3 3 3

Dengan demikian, diperoleh penyelesaian tunggal untuk menyelesaikan sistem tersebut.


85

Sifat kestabilan, eksistensi dan ketunggalan dari penyelesaian memberikan gambaran umum mengenai bagaimana metode inverse problem digunakan dalam menyelesaikan suatu permasalahan.

B. Metode Regularisasi 3.3 Regularisasi Dalam menyelesaikan inverse problem umumnya akan memunculkan masalah ill-posed. Hal ini biasanya disebabkan karena adanya galat pada perhitungan atau kesalahan dalam melakukan pemodelan masalah, sehingga stabilitas dari penyelesaian menjadi tidak stabil. Kestabilan ini dapat terlihat ketika sistem diberikan gangguan. Jika gangguan menyebabkan galat yang besar pada perhitungan penyelesaian maka sistem tidak stabil. Untuk mengatasi situasi ini maka digunakanlah regularisasi. Ketika meregularisasi masalah akan didapatkan banyak penyelesaian yang bersesuaian dengan pemilihan parameter regularisasi. Dari parameter regularisasi ini akan didapatkan penyelesaian dari masalah regularisasi, dan dapat diketahui pula besar galat dan faktor perbesaran galat yang terjadi pada setiap penyelesaian. Setelah itu, akan dipilih penyelesaian masalah regularisasi yang memiliki galat terkecil. Agar dapat memahami penjelasan tersebut maka perhatikan contoh berikut.


86

Contoh 3.3.1 Diberikan matriks 1 𝐴= 0 dengan 𝐛 = 1, 2−10

𝑇

0

1 1024

dan jelas 𝐱 = 1,1

𝑇

adalah penyelesaian eksak

dari sistem 𝐴𝐱 = 𝐛

3.1 .

Selain dapat menentukan penyelesaian dari suatu sistem, harus juga ditentukan bagaimana kestabilan dari sistem tersebut. Untuk itu akan diberikan gangguan di 𝐛 dan melihat faktor perbesaran galat yang terjadi pada sistem 3.1 . Agar dapat lebih memahami efek yang terjadi, maka permasalahan ini akan ditinjau melalui dua kasus. Kasus I jika 𝐛 diberikan gangguan sebesar 𝐩 = 0, 2−10

𝑇

dan kasus II jika 𝐛 diberikan gangguan

sebesar 𝐬 = 2−10 , 0 𝑇 . Pada kasus I, misalkan 𝐛 diberikan gangguan sebesar 𝐩 = 0, 2−10 𝑇 , sehingga sistem (3.1) akan berubah menjadi 𝐴𝐱 = 𝐛 + 𝐩 =

1 2−10

+

0 2−10

dan didapat penyelesaian 𝐱 ′ = 𝐴−1 𝐛 + 𝐩 =

1 = 2 210 1 . Dari hasil 𝐱 ′ dapat 2

dihitung selisih absolut penyelesaian 𝐱 ′ dan 𝐱 sebagai 𝐫 = 𝐱 ′ − 𝐱 =

1 − 2

1 0 = . Setelah mendapatkan 𝐫, kemudian akan dihitung faktor 1 1


87

perbesaran galat yang terjadi pada sistem ketika diberikan gangguan sebesar 𝐩 sebagai 𝐫2 1 = −10 = 1024. 𝐩2 2 Sedangkan pada kasus II, 𝐛 diberikan gangguan sebesar 𝐬 = 2−10 , 0 𝑇 , sehingga sistem (3.1) menjadi 1

𝐴𝐱 = 𝐛 + 𝐬 =

2−10

1025 −10 2 + = 1024 0 2−10 1025

′

−1

dan didapat penyelesaian 𝐱 = 𝐴

𝐛+𝐬 =

1024

1

. Dari hasil 𝐱 ′ ini

dapat dihitung selisih absolut penyelesaian 𝐱 ′ dan 𝐱 sebagai 𝐫 = 𝐱 ′ − 𝐱 = 1025 1024

1

−

1 1

2−10 . Setelah mendapatkan 𝐫, kemudian dihitung faktor 0

perbesaran galat yang terjadi pada sistem ketika diberikan gangguan sebesar 𝐬, yaitu 𝐫 𝐬

2 2

=

2−10 = 1. 2−10

Berdasarkan kasus I dan kasus II terlihat bahwa penyebab selisih yang sangat besar pada faktor perbesaran galat dalam kasus I dan kasus II terletak pada perhitungan 𝐴−1 . Dari perhitungan yang telah dilakukan bahwa 𝐴−1 sangat sensitif terhadap perubahan galat yang diberikan, sehingga

menyebabkan

ketidakstabilan

pada

sistem.

Hal

ini

mengakibatkan penyelesaian yang didapat menjadi tidak akurat. Situasi seperti ini dapat dihindari dengan meregularisasi bentuk 3.1 menjadi sistem


𝐴𝛼 𝐱 = 𝐛𝛼 ,

88

𝛼 > 0.

3.2

Tujuan dari regularisasi ini adalah untuk menekan galat yang terjadi pada perhitungan 𝐴−1 sehingga sistem menjadi lebih stabil. Bentuk regularisasi sistem 3.1 diberikan dengan memilih 1 𝐴𝛼 = 0

0 1 1 1−𝛼 10 2 10

dan 𝐛𝛼 = 𝐛, 0 < 𝛼 < 1

3.3

3.2 , maka selanjutnya masalah

Setelah mendapatkan sistem

regularisasi pada 3.2 dapat diselesaikan. Seperti kasus I, pada sistem akan diberikan gangguan sebesar 𝐩 = 0, 2−10 𝑇 . Misalkan 𝐱 𝛼

3.2

3.2

adalah penyelesaian sistem

pada pemilihan 𝐴𝛼 dan 𝐛𝛼 dalam 1

persamaan 3.3 . Dan ditentukan nilai 𝛼 sebagai 𝛼 = 2𝑛 , 𝑛 = 1,2, … ,9. Dari parameter 𝛼 ini, akan dihitung galat dari perhitungan 𝐱 𝛼 yang bersesuaian dengan faktor perbesaran galatnya.

Sebagai contoh pilih

1

𝛼 = 2 , diperoleh 1 𝐴1 = 0 2

0 1 1 1 10 2 10 1− 2

=

1 0 1 dan 𝐛1 = −10 . 2 0 1 2

Karena sistem tersebut diberikan gangguan sebesar 𝐩 maka sistem menjadi 1

𝐴1 𝐱 = 𝐛1 + 𝐩, dengan 𝐛1 + 𝐩 = 2

2

2−10

2

+

0 2−10

1

=

2

210

sehingga 𝐱 1 = 𝐴1 2

2

−1

. 𝐛1 + 𝐩 = 2

1 0

0 . 1

1 2

210

=

1 2

210

.

,


89

Setelah mendapat 𝐱 1 kemudian akan dihitung besar galat yang terjadi pada 2

penyelesaian masalah regularisasi, galat tersebut dihitung dengan 1

menghitung norma dari selisih 𝐱 2 dan 𝐱 yang dinotasikan sebagai 𝐫

2

= 𝐱1 − 𝐱 2

= 2

1 2 − 1 1 210

= 2

0 511 − 512

= 0.998 2

dan faktor perbesaran galat dihitung sebagai 𝐫 2 0.998 = −10 = 1022. 𝐩2 2 Tabel 3.1 di bawah ini merupakan hasil numerik perhitungan galat dan faktor perbesaran galat yang dihasilkan pada setiap pemilihan parameter regularisasi 𝛼 dengan gangguan sebesar 𝐩 = 0, 2−10 𝑇 . 𝛼 𝐫 𝐫

𝐩

½ 0.998 1022

1/4 0.887 909

1/8 0.474 485

1/16 0.049 50

1/32 0.456 467

1/64 0.709 726

1/128 0.849 869

1/256 0.923 945

1/512 0.961 984

Tabel 3.1. Hasil Numerik Faktor Perbesaran Galat

Dari tabel 3.1 terlihat bahwa penyelesaian terbaik dari sistem 3.2 yaitu saat memilih 𝛼 = 1/16. Karena penyelesaian yang dihasilkan memuat galat sebesar 0.049 dan mempunyai faktor perbesaran galat sebesar 50. Pada contoh 3.3.1 telah dijelaskan mengenai bagaimana teknik regularisasi diterapkan untuk menyelesaikan masalah linier 𝐴𝐱 = 𝐛. Dari contoh tersebut teknik regularisasi digunakan untuk menekan pembesaran galat pada perhitungan

𝐴−1 . Berdasarkan Teorema 2.6.2.2 bahwa


90

perhitungan 𝐴−1 akan bergantung pada nilai singular terkecil matriks 𝐴 sehingga

𝐴−1 = 𝜎1 𝐴−1 =

1 𝜎𝑛 𝐴

dimana nilai 𝜎1 𝐴 merupakan nilai singular yang terbesar dari matriks 𝐴, sedangkan 𝜎𝑛 𝐴 merupakan nilai singular terkecilnya. Sehingga untuk mencari 𝐴−1 akan dipilih nilai singular terkecil dari 𝐴 dan kemudian mensubstitusikannya ke 1 𝜎 𝐴 . Hal ini menyebabkan apabila 𝐴 𝑛 memiliki nilai singular terkecil 𝜎𝑛 𝐴

yang mendekati nol, maka nilai

𝐴−1 akan besar, sehingga penyelesaian menjadi tidak akurat. Dengan meregularisasi masalah diharapkan akan memperoleh nilai singular yang dapat membuat perhitungan 𝐴−1 kecil. Untuk itu, bentuk regularisasi dari matriks 𝐴 akan ditulis sebagai 𝐴𝛼 , dimana 𝐴𝛼 adalah matriks regularisasi. Sehingga dengan mempertimbangkan ketentuan tersebut dalam menyelesaikan sistem 3.1 diperoleh masalah regularisasi sebagai 𝐴𝛼 𝐱 = 𝐛,

3.4

dan penyelesaian dari persamaan 3.4 tersebut adalah 𝑛 𝐱 𝛼 = 𝐴−1 𝛼 𝐛∈ℝ .

3.5


91

3.4 Regularisasi Tikhonov Pada bagian ini akan dijelaskan mengenai cara meregularisasi masalah dengan menggunakan metode regularisasi Tikhonov. Metode regularisasi ini digunakan untuk menyelesaikan masalah sistem 𝐴𝐱 = 𝐛. Penyelesaian dari sistem adalah mencari 𝐱 sehingga 𝐴𝐱 = 𝐛 dan penyelesian dari sistem 3.1 tersebut dihitung dengan meminimalkan 𝑓 𝐱 = 𝐴𝐱 − 𝐛

2

3.6

Kemudian untuk menghindari perbesaran galat ketika meminimalkan 3.6 maka digunakan regularisasi Tikhonov. Dalam metode Tikhonov proses regularisasi dilakukan untuk mendapatkan 𝐱 𝛼 yang memuat galat paling minimum. Agar dapat memperoleh hasil tersebut, maka pada perhitungan 𝐴𝐱 − 𝐛

2

digunakanlah

2.

Dan bentuk regulasisasinya

diberikan sebagai masalah fungsional 𝑓𝛼 𝐱 = 𝐴𝐱 − 𝐛 22 + 𝛼 2 𝐱

2 2

3.7

dengan 𝛼 > 0 adalah parameter regularisasi. Peran dari 𝛼 2 𝐱 untuk menekan galat yang terjadi pada 𝐴𝐱 − 𝐛 kecil. Sehingga apabila perhitungan 𝛼 2 𝐱

2 2

2 2

2 2

adalah

supaya menjadi lebih

mendekati nol maka dapat

diperoleh hasil penyelesaian yang optimal. Untuk mendapatkan penyelesaian 𝐱 𝛼 yang minimum maka harus dihitung turunan untuk 𝑓𝛼 𝐱 sebagai ∇𝑓𝛼 𝐱 = 0.


Dari definisi hasil kali dalam pada 𝐱 ∇𝑓𝛼 𝐱 =

𝜕 𝐴𝐱 − 𝐛 22 + 𝛼 2 𝐱 𝜕𝐱

2

=

92

𝐱, 𝐱 diperoleh

2 2

=

𝜕 𝜕 𝐴𝐱 − 𝐛, 𝐴𝐱 − 𝐛 + 𝛼 2 . 𝐱, 𝐱 𝜕𝐱 𝜕𝐱

=

𝜕 𝜕 𝐴𝐱, 𝐴𝐱 − 2 𝐴𝐱, 𝐛 + 𝐛, 𝐛 + 𝛼 2 . 𝐱, 𝐱 . 𝜕𝐱 𝜕𝐱

≤

𝜕 𝜕 𝐴𝐱, 𝐴𝐱 − 𝐴𝐱, 𝐛 + 𝐛, 𝐛 + 𝛼 2 . 𝐱, 𝐱 . 𝜕𝐱 𝜕𝐱

dengan menggunakan 𝐱, 𝐲 = 𝐱 𝑇 𝐲 dan 𝐱, 𝐱 = 𝐱 𝑇 𝐱 diperoleh =

𝜕 𝜕 𝑇 𝐴𝐱 𝑇 𝐴𝐱 − 𝐴𝐱 𝑇 𝐛 + 𝐛𝑇 𝐛 + 𝐱 𝐱 𝜕𝐱 𝜕𝐱

=

𝜕 𝑇 𝑇 𝜕 𝑇 𝐱 𝐴 𝐴𝐱 − 𝐱 𝑇 𝐴𝑇 𝐛 + 𝐛𝑇 𝐛 + 𝛼 2 . 𝐱 𝐱 𝜕𝐱 𝜕𝐱

= 𝐴𝑇 𝐴𝐱 − 𝐴𝑇 𝐛 + 𝛼 2 𝐱

Karena ∇𝑓𝛼 𝐱 = 0 maka 𝐴𝑇 𝐴𝐱 − 𝐴𝑇 𝐛 + 𝛼 2 𝐱 𝛼 = 0, karena nilai minimum 𝐱 adalah 𝐱 𝛼 , maka 𝐴𝑇 𝐴𝐱 𝛼 + 𝛼 2 𝐱 𝛼 − 𝐴𝑇 𝐛 = 0 𝐴𝑇 𝐴𝐱 𝛼 + 𝛼 2 𝐱 𝛼 = 𝐴𝑇 𝐛 𝐴𝑇 𝐴𝐱 𝛼 + 𝛼 2 𝐱 𝛼 = 𝐴𝑇 𝐛 𝐴𝑇 𝐴 + 𝛼 2 𝐼 𝐱 𝛼 = 𝐴𝑇 𝐛,

3.8


93

dan penyelesaian dari persamaan 3.8 tersebut adalah 𝐱 𝛼 = 𝐴𝑇 𝐴 + 𝛼 2 𝐼

−1 𝑇

𝐴 𝐛.

Dengan demikian, untuk mendapatkan penyelesaian inverse problem dengan kualitas terbaik maka harus dapat ditentukan parameter 𝛼 yang tepat, sehingga galat yang terjadi dapat minimum.


BAB IV APLIKASI

Pada bab ini akan dibahas bagaimana aplikasi inverse problem untuk restorasi gambar digital dengan metode TSVD dan Regularisasi Tikhonov. Adapun data yang digunakan dalam aplikasi ini adalah gambar grayscale, yaitu setiap piksel gambar memiliki nilai antara 0 dan 1. Proses restorasi yang dilakukan adalah untuk memperoleh gambar yang lebih baik dari gambar input.

A. Gambar Digital 4.1 Representasi Gambar Digital Image adalah gambar yang terletak pada bidang dua-dimensi. Ditinjau dari sudut pandang matematis, gambar merupakan fungsi kontinu dari intensitas cahaya pada bidang dua-dimensi. Sumber cahaya menerangi objek, lalu objek memantulkan kembali sebagian dari berkas cahaya tersebut. Kemudian pemantulan cahaya ini ditangkap oleh alat-alat optik, seperti kamera, scanner dan sebagainya sehingga bayangan dari objek dapat terekam dalam format digital maupun analog. Agar memudahkan proses pengolahan maka digunakan gambar dalam bentuk digital yang disebut sebagai gambar digital. Namun apabila terdapat gambar dalam bentuk analog, terlebih dahulu gambar tersebut


95

harus diubah menjadi format digital melalui proses scanning. Proses scanning memerlukan perangkat keras khusus yang disebut scanner. Gambar digital hitam putih dapat dipandang sebagai suatu larik (array) dua-dimensi

atau suatu matriks

yang elemen-elemennya

menyatakan tingkat keabuan gambar. Dan setiap tingkat keabuan gambar akan direpresentasikan dengan bilangan riil antara 0 (hitam pekat) dan 1 (putih pekat). Sehingga informasi yang terkandung didalamnya bersifat diskrit. Untuk mengubah gambar kontinu menjadi gambar digital diperlukan pembuatan kisi-kisi arah horizontal dan vertikal, sehingga diperoleh gambar dalam bentuk larik dua-dimensi. Proses ini disebut sebagai proses digitalisasi atau sampling. Setiap elemen pada larik dikenal sebagai elemen gambar atau piksel. Pembagian sebuah gambar menjadi sejumlah piksel dengan ukuran tertentu ini akan menentukan resolusi spasial yang diperoleh. Semakin tinggi resolusi yang diperoleh berarti semakin kecil ukuran pikselnya sehingga semakin halus gambar yang diperoleh karena informasi yang hilang akibat pengelompokan tingkat keabuan pada proses pembuatan kisi-kisi akan semakin kecil. Pengolahan gambar digital yang akan dibahas sebatas pada gambar grayscale, dimana secara umum gambar diberikan sebagai 𝐼 𝑖, 𝑗 yang merupakan intensitas tingkat keabuan dari hitam ke putih pada piksel, 𝑖 menyatakan variabel baris 𝑖 = 1,2, … , 𝑚 , 𝑗 menyatakan variabel kolom, 𝑗 = 1,2, … , 𝑛

dan

𝑖, 𝑗

menyatakan posisi piksel. Sebagai contoh,


96

gambar yang mempunyai ukuran 256 × 512, berarti jumlah piksel vertikal adalah 512 piksel sedangkan jumlah piksel horizontal adalah 256 piksel, sehingga jumlah piksel keseluruhan yang terdapat dalam gambar tersebut adalah 131.072 piksel. Pada saat mengambil gambar dengan menggunakan kamera terkadang muncul efek derau dalam rekaman gambar digital. Hal ini disebabkan karena saat merekam gambar sistem optik lensa kamera mungkin kurang fokus, sehingga cahaya yang masuk memberikan efek derau pada gambar. Untuk memulihkan gambar kabur tersebut digunakanlah proses restorasi. Tujuan dari proses restorasi ini adalah menghilangkan atau mengurangi pengaruh kabur maupun degradasi yang terjadi pada gambar asli karena proses akuisisi.

4.2 Model Degradasi Gambar Digital Untuk memperoleh gambar yang lebih baik dalam proses restorasi maka perlu diberikan model yang menjelaskan proses kabur dari gambar asli. Dengan melakukan itu maka dapat diperoleh informasi untuk memulihkan gambar kabur, namun pemulihan gambar yang diperoleh tidak mirip seperti aslinya. Hal ini disebabkan berbagai galat yang terjadi tidak dapat dhindarkan dalam gambar yang direkam, seperti fluktuasi dalam proses pendekatan galat ketika mewakili gambar dengan sebuah digit. Sehingga model yang dibentuk sebaiknya memuat dua informasi, yaitu derau dan proses kabur yang terjadi pada gambar asli. Perhatikan


97

contoh yang ditunjukkan pada Gambar 4.1. Gambar kiri merupakan gambar asli dan kanan adalah versi kabur dari gambar yang sama.

Gambar 4.1. Sebuah gambar asli (kiri) dan gambar kabur yang bersesuaian (kanan).

Sehingga gambar grayscale pada Gambar 4.1 dapat dituliskan sebagai matriks 𝑚 × 𝑛, dimana notasi 𝐱 ∈ ℝ𝑚 ×𝑛 merepresentasikan gambar asli dan 𝐛 ∈ ℝ𝑚 ×𝑛 dinotasikan sebagai gambar kabur. Kemudian terdapat operator pengaburan (blurring) yang memetakan gambar asli menjadi gambar kabur yang dinotasikan sebagai matriks 𝐀 ∈ ℝ𝑚 ×𝑛 , sehingga relasi di antara gambar asli dan gambar kabur ditulis sebagai 𝐀𝐱 = 𝐛. yang merupakan model dari gambar kabur.


98

B. Restorasi Gambar menggunakan TSVD Bentuk kompak dari singular value decomposition (SVD) matriks 𝐀 banyak digunakan dalam berbagai aplikasi terutama dalam restorasi gambar. Selain itu, algoritma restorasi gambar dengan SVD dilakukan dengan membuang unsur-unsur yang mewakili nilai singular kecil. Untuk menunjukkan bagaimana SVD digunakan, misalkan 𝐀 mewakili matriks pengaburan yang digunakan untuk mendekati derau yang terjadi pada gambar, dan 𝐀 = 𝑈Λ𝑉 𝑇 maka 𝐀 dapat ditulis sebagai 𝐀 = σ1 𝐮1 𝐯1𝑇 + σ2 𝐮2 𝐯2𝑇 + ⋯ + σ𝑛 𝐮𝑛 𝐯𝑖𝑇 karena σ1 ≥ σ2 ≥ ⋯ ≥ σ𝑛 > 0 maka semua nilai singular adalah positif dan 𝐀 adalah matriks persegi, dimana invers dari matriks 𝐀 diberikan sebagai 𝐀−1 = 𝑉Λ−1 𝑈 𝑇 . Karena Λ adalah matriks diagonal maka inversnya Λ−1 juga diagonal, dengan entri 1 σ𝑖 untuk 𝑖 = 1,2, … , 𝑛, sehingga 𝑛 −1

𝐀

= 𝑖=1

1 𝐯 𝐮𝑇 . σ𝑖 𝑖 𝑖

4.1

Seperti telah dijelaskan pada bab sebelumnya bahwa model gambar kabur diberikan sebagai persamaan 𝐀𝐱 = 𝐛 dan penyelesaiannya adalah 𝐱 = 𝐀−1 𝐛. Sehingga apabila 𝐀−1 di persamaan 4.1 disubstitusikan pada penyelesaian akan diperoleh


𝑛 −1

−1

1 𝐯 𝐮 𝑇𝐛 = σ𝑖 𝑖 𝑖

𝑇

𝐱 = 𝐀 𝐛 = 𝑉Λ 𝑈 𝐛 = 𝑖=1

𝑛

𝑖=1

99

𝐮𝑖 𝑇 𝐛 𝐯𝑖 . σ𝑖

Pada kasus ini derau yang terjadi pada gambar direkonstruksikan dengan bentuk 𝐀−1 𝐛. Pendekatan SVD dapat digunakan untuk meredam efek yang disebabkan oleh pembagian nilai-nilai singular kecil, khususnya nilai singular yang mendekati nilai nol. Sementara itu, penyebab dari perubahan nilai-nilai singular dan vektor singular terjadi karena pengaruh derau. Untuk mengurangi efek derau tersebut yang perlu dilakukan adalah membuang nilai-nilai singular kecil dengan sebuah parameter pemotongan 𝑘. Karena informasi mengenai galat yang besar terjadi ketika dilakukan pembagian dengan nilai singular kecil σ𝑛 , maka komponen yang menyebabkan galat besar tersebut dapat dibuang. Untuk itu digunakanlah Truncated Singular Value Decomposition (TSVD) yang didefinisikan sebagai 𝑘

σi 𝐮𝑖 𝐯𝑖𝑇

𝐀 𝑘 = 𝑈Λ 𝑘 𝑉 𝑇 = 𝑖=1

dimana Λ 𝑘 = diag σ1 , σ2 , … , σ𝑘 , 0, … ,0 ∈ ℝ𝑚 ×𝑛 atau

Λ𝑘 =

σ1 0 0 ⋮ 0

0 ⋱ 0 ⋮ 0

0 0 σ𝑘 ⋮ 0

0 0 0 ⋮ 0

0 0 0 . ⋮ 0

4.2


100

Matriks Λ 𝑘 sama seperti Λ namun perbedaanya terletak pada nilai singular terkecil 𝑛 − 𝑘 yang diganti oleh nol, dengan 𝑘 ≤ 𝑛. Pemotongan nilai singular ini dimaksudkan untuk mendapatkan bilangan kondisi yang kecil dengan cara memilih 𝑘. Apabila 𝑘 yang dipilih tepat, maka perhitungan bilangan kondisi

σ1

σ𝑘 dari 𝐀 𝑘 akan menjadi kecil. Dari 𝐀 𝑘 yang

diperoleh dapat dibentuk 𝐀 𝑘 + sebagai pseudo-invers dari 𝐀 𝑘 ; 𝑘 +

𝐀 𝑘 = 𝑉Λ 𝑘

−1

𝑇

𝑈 = 𝑖=1

1 𝐯𝐮𝑇 σ𝑖 𝑖 𝑖

dimana Λ 𝑘 −1 = diag σ1 −1 , σ2 −1 , … , σ𝑘 −1 , 0, … ,0 ∈ ℝ𝑛 ×𝑚 atau

Λ 𝑘 −1 =

σ1 −1 0 0 ⋮ 0

0 0 ⋱ 0 0 σ𝑘 −1 ⋮ ⋮ 0 0

0 0 0 ⋮ 0

0 0 0 . ⋮ 0

sehingga penyelesaian dari TSVD didefinisikan sebagai 𝑘 +

𝐱 𝑘 = 𝐀 𝑘 𝐛 = 𝑉Λ 𝑘

−1

𝑇

𝑈 𝐛= 𝑖=1

𝐮𝑖 𝑇 𝐛 𝐯 σ𝑖 𝑖

4.3

Setelah memahami bagaimana metode TSVD digunakan dalam menyelesaikan masalah 𝐀𝐱 = 𝐛. Selanjutnya metode tersebut akan diaplikasikan untuk restorasi gambar digital. Seperti dijelaskan pada bab


101

sebelumnya bahwa untuk input dari proses restorasi ini diberikan sebagai 𝐀 dan 𝐛, dimana 𝐀 adalah matriks pengaburan yang digunakan sebagai pendekatan model gambar blur sedangkan 𝐛 adalah gambar yang mengalami efek derau. Untuk itu akan digunakan gambar digital ‘cameraman.tif’

Gambar 4.2. Gambar Asli ‘cameraman.tif’

yang ditambahkan derau berupa efek motion dengan sudut sebesar 110° dan tingkat motion sebesar 10 sehingga diperoleh gambar blur sebagai berikut

Gambar 4.3. Gambar ‘cameraman.tif’ terkena efek motion


102

Selanjutnya untuk memulihkan kembali gambar yang mengalami efek derau dapat dilakukan restorasi gambar. Langkah awal yang perlu dilakukan dalam proses restorasi adalah membentuk matriks pengaburan. Pembentukkan matriks pengaburan ini dimaksudkan untuk memodelkan efek derau yang terjadi, sehingga saat melakukan proses restorasi dapat dihasilkan penyelesaian optimal. Dalam proses restorasi ini akan digunakan matriks pengaburan yang dibentuk dengan a=zeros(r,1); a(1:5)=[5:-1:1]'/25; A=toeplitz(a);

Gambar 4.4. Visualisasi matriks pengaburan dimana toeplitz adalah matriks yang mempunyai entri konstan pada setiap diagonalnya.

Gambar

4.4

menunjukkan

visualisasi

dari

matriks

pengaburan yang dibentuk dengan menggunakan toeplitz. Notasikan matriks pengaburan yang dibentuk sebagai matriks 𝐀, dimana matriks tersebut memliki ukuran piksel seperti gambar 4.3.


103

Setelah mendapatkan model dari matriks pengaburan selanjutnya akan dihitung SVD dari matriks 𝐀. Dari perhitungan SVD tersebut didapatkan nilai-nilai singular 𝐀 sebagai matriks Λ. Dengan memilih suatu parameter 𝑘 dapat dibentuk suatu matriks singular yang banyaknya nilai singularnya akan sama dengan 𝑘 yang dipilih. Matriks yang demikian disebut sebagai Λ 𝑘 . Dengan Λ 𝑘 yang diperoleh dapat dibentuk sebuah matriks Λ 𝑘 −1 . Dan hasil restorasi gambar digital dengan metode TSVD dituliskan dalam bentuk 𝐱 𝑘 = 𝑉Λ 𝑘 −1 𝑈 𝑇 𝐛. Gambar di bawah ini menunjukkan hasil restorasi gambar dengan pemilihan 𝑘 = 200,

Gambar 4.5. Gambar hasil restorasi TSVD dengan 𝑘 = 200 kemudian untuk mengetahui besar galat yang terjadi pada perhitungan restorasi, maka perlu dihitung norma antara gambar asli dengan gambar hasil restorasi. Semakin kecil norma yang didapat maka hasil restorasi yang diperoleh akan semakin baik, sebab hasil yang diperoleh semakin


104

mendekati gambar aslinya. Pada gambar 4.5 hasil restorasi TSVD dengan 𝑘 = 200 memiliki norma sebesar 25,3104, tentunya hasil tersebut masih kurang optimal. Untuk mendapatkan hasil restorasi terbaik, maka harus dicari parameter 𝑘 yang mengoptimalkan proses restorasi. Berikut adalah hasil perhitungan norma yang bersesuaian dengan pemilihan parameter 𝑘.

Gambar 4.6. Grafik TSVD Dari gambar 4.6 di atas dapat dilihat besar norma yang terjadi pada setiap pemilihan parameter 𝑘. Berdasarkan hasil tersebut nilai norma terkecil berada pada interval parameter 𝑘 ∈ 50,100 dengan norma di antara nilai 0 sampai 10. Dengan mempertimbangkan hal ini maka diperoleh grafik TSVD sebagai berikut


105

Gambar 4.7. Grafik TSVD dengan axis([50 100 0 10])

kemudian dengan mengubah axis([70 75 5 6]) diperoleh

Gambar 4.8. Grafik TSVD dengan axis([70 75 5 6])

Dari gambar 4.8 terlihat bahwa nilai norma terkecil terletak di antara nilai 5,7 dan 5,8 yang berada pada 𝑘 = 73 dan 𝑘 = 74. Untuk mengetahui letak norma terkecil tersebut, maka dipilihlah axis([70 75 5.7 5.8]) sehingga diperoleh


106

Gambar 4.9. Grafik TSVD dengan axis([70 75 5.7 5.8])

Berdasarkan hasil grafik TSVD pada gambar 4.9 didapatkan bahwa nilai norma terkecil diperoleh ketika dipilih parameter 𝑘 = 74. Dengan memilih parameter 𝑘 = 74 didapatkan hasil restorasi TSVD sebagai berikut

Gambar 4.10. Gambar hasil restorasi TSVD dengan 𝑘 = 74 memiliki norma sebesar 5,7171 Dari hasil tersebut dapat dikatakan bahwa parameter 𝑘 = 74 memberikan nilai norma yang mengoptimalkan hasil restorasi gambar dengan metode TSVD. Bila dijelaskan dalam bentuk algoritma dan diagram alir, maka metode TSVD dapat digambarkan sebagai berikut:


107

1. Bentuk matriks pengaburan yang berukuran sama seperti gambar yang akan direstorasi. 2. Hitunglah SVD dari matriks pengaburan dengan menggunakan fungsi svd Matlab, dan plot nilai-nilai singularnya. 3. Tentukan parameter pemotongan 𝑘 untuk nilai-nilai singular yang diperoleh pada langkah 2, kemudian bentuk matriks Λ 𝑘 . 4. Dari Λ 𝑘 yang diperoleh bentuklah matriks Λ 𝑘 −1 . 5. Hitunglah 𝐱 𝑘 = 𝑉Λ 𝑘 −1 𝑈 𝑇 𝐛. 6. Ulangi langkah 3 sampai 5 sampai mendapatkan parameter 𝑘 yang mengoptimalkan hasil restorasi. Kode sintaks dalam program MATLAB akan dilampirkan pada program 4.1a dan program 4.1b.

C. Restorasi Gambar menggunakan Regularisasi Tikhonov Dalam melakukan proses restorasi gambar digital tentunya tidak hanya berhenti dengan menggunakan satu metode saja. Selain dengan metode TSVD di tulisan ini juga akan dibahas metode restorasi dengan menggunakan regularisasi Tikhonov. Regularisasi Tikhonov berbasis pada meminimalkan suatu fungsional min𝐱 𝐛 − 𝐀𝐱 22 + 𝛼 2 𝐱

2 2

4.4


dengan 𝛼 adalah parameter regularisasi. Kemudian

4.4

108

dapat

diformulasikan menjadi 𝐀 𝐛 min − 𝐱 𝐱 𝛼𝐼 𝟎

2 2

dan penyelesaian dari masalah tersebut diberikan oleh 𝐀𝑇 𝐀 + 𝛼 2 𝐼 𝐱 = 𝐀𝑇 𝐛 𝑉Λ𝑇 𝑈 𝑇 𝑈Λ𝑉 𝑇 + 𝛼 2 𝐼 𝐱 = 𝑉Λ𝑇 𝑈 𝑇 𝐛 𝑉Λ𝑇 Λ𝑉 𝑇 + 𝛼 2 𝐼 𝐱 = 𝑉Λ𝑇 𝑈 𝑇 𝐛

sehingga didapatkan hasil akhir 𝑛

𝐱= 𝑖=1

𝜎𝑖2 𝐯𝑖 𝐮𝑇𝑖 𝐛 . = 𝜎𝑖2 + 𝛼 2 𝜎𝑖

𝑛

𝑖=1

𝜎𝑖2 𝐮𝑇𝑖 𝐛 𝐯. 𝜎𝑖2 + 𝛼 2 𝜎𝑖 𝑖

Jika 𝜎𝑖2 𝜑𝑖 = 2 , 𝑖 = 1,2, … , 𝑛 𝜎𝑖 + 𝛼 2

maka dapat dibentuk

Φα =

𝜑1 0 0 0

0 𝜑2 0 0

0 0 ⋱ 0

0 0 , 0 𝜑𝑛

sehingga penyelesaian dari metode regularisasi Tikhonov didefinisikan sebagai


𝑛 −1

𝑇

𝐱 𝛼 = 𝑉Φα Λ 𝑈 𝐛 = 𝑖=1

𝐮𝑇𝑖 𝐛 𝜑𝑖 𝐯 𝜎𝑖 𝑖

109

4.5

Masalah meminimumkan fungsi persamaan 4.4 didasari pada fakta bahwa perhitungan 𝐛 − 𝐀𝐱

2 2

harus memuat galat yang relatif kecil.

Tetapi, jika karena alasan tersebut dipilih 𝐱 = 𝐀−1 𝐛 maka perhitungan galat 𝐱

2 2

akan relatif besar. Sehingga dengan masalah meminimumkan

fungsi di 4.4 diharapkan bahwa norma dari perhitungan 𝐛 − 𝐀𝐱 𝛼 dan norma penyelesaian 𝐱 𝛂 memiliki galat yang relatif kecil. Sekarang akan dipertimbangkan efek dari pemilihan parameter regularisasi 𝛼. Kasus pertama untuk faktor filter 𝜑𝑖 dimana 𝜎𝑖 > 𝛼, dengan menggunakan ekspansi Taylor 1 + 𝜖

−1

1

= 1 − 𝜖 + 2 𝜖2 + 𝑂 𝜖3

diperoleh 𝜑𝑖 =

𝜎𝑖2 1 𝛼2 1 𝛼4 = = 1 − + +⋯. 𝜎𝑖2 + 𝛼 2 1 + 𝛼 22 𝜎𝑖2 2 𝜎𝑖4 𝜎 𝑖

Selanjutnya kasus kedua untuk faktor filter 𝜑𝑖 dimana 𝜎𝑖 < 𝛼. Dengan menggunakan ekspansi Taylor 1 + 𝜖

−1

diperoleh

𝜎𝑖2 𝜎𝑖2 1 𝜎𝑖2 𝜎2 1 𝜎4 𝜑𝑖 = 2 = = 1− 2+ +⋯ . 𝜎𝑖 + 𝛼 2 𝛼 2 1 + 𝜎 22 𝛼 2 𝛼𝑖 2 𝛼𝑖4 𝛼𝑖

Kemudian dapat dituliskan bahwa faktor filter Tikhonov memenuhi 1− 𝜑𝑖 =

𝜎𝑖 2 𝛼

𝛼 2 𝜎𝑖

+𝑂

+𝑂 𝜎𝑖 4 𝛼

𝛼 4 𝜎𝑖

,

, 𝜎𝑖 ≫ 𝛼 4.6 𝜎𝑖 ≪ 𝛼.


110

Ini berarti apabila dipilih 𝛼 ∈ 𝜎𝑛 , 𝜎1 maka 𝜑𝑖 ≈ 1 untuk indeks kecil 𝑖, sedangkan 𝜑𝑖 ≈

𝜎𝑖2

𝛼 2 untuk indeks 𝑖 yang besar.

Dengan menggunakan konsep di atas, selanjutnya akan dilihat hasil restorasi dari gambar 4.3 dengan metode regularisasi Tikhonov. Langkah awal proses restorasi ini adalah membentuk matriks pengaburan seperti terlihat pada gambar 4.4. Selanjutnya akan dihitung SVD dari matriks 𝐀, sehingga didapatkan nilai-nilai singular 𝐀 sebagai matriks Λ. Kemudian dari nilai singular yang ada dipilih 𝜎𝑛 dan 𝜎1 . Hal ini dilakukan untuk menentukan parameter regularisasi 𝛼, sebab nilai parameter regularisasi harus berada pada 𝜎𝑛 , 𝜎1 . Dari parameter 𝛼 yang dipilih dapat dibentuk sebuah matriks diagonal Φα yang elemen diagonalnya adalah 𝜑𝑖 . Hasil restorasi gambar digital dengan metode regularisasi Tikhonov dituliskan dalam bentuk 𝐱 𝛼 = 𝑉Φα Λ−1 𝑈 𝑇 𝐛

dimana Φα diperoleh dari 𝜑𝑖 pada persamaan 4.6 .


111

Gambar berikut menunjukkan hasil restorasi gambar 4.3 dengan menggunakan 𝛼 = 0.01,

Gambar 4.11. Gambar hasil restorasi Tikhonov dengan 𝛼 = 0.01

Berdasarkan pengamatan, hasil restorasi pada gambar 4.11 ternyata masih memuat efek derau yang memiliki norma sebesar 22,89089. Akibatnya, hasil restorasi dengan 𝛼 = 0.01 belum menghasilkan penyelesaian yang optimal. Agar memperoleh penyelesaian terbaik harus dapat dicari nilai 𝛼 yang menghasilkan norma terkecil. Grafik di bawah ini menunjukkan hasil perhitungan norma pada setiap pemilihan parameter regularisasi 𝛼 ∈ 𝜎𝑛 , 𝜎1 dengan mengambil panjang langkah 0.01,


112

Gambar 4.12. Grafik Regularisasi Tikhonov

Berdasarkan gambar 4.12 di atas terlihat bahwa norma terkecil berada pada 0 ≤ 𝛼 ≤ 0.2 dengan norma di antara nilai 0 sampai 20. Dengan mempertimbangkan hal tersebut maka selanjutnya akan dipilih 𝛼 ∈ 0,0.2 dengan mengambil panjang langkah 0.01 sehingga diperoleh grafik

Gambar 4.13.

Grafik Regularisasi Tikhonov dengan 𝛼 ∈ 0,0.2 dan axis([0 0.2 0 20])


113

kemudian dengan mengubah 𝛼 ∈ 0.06 , 0.12 dan axis([0.06 0.12 6 8])diperoleh

Gambar 4.14. Grafik Regularisasi Tikhonov dengan 𝛼 ∈ 0.06 , 0.12 dan axis([0.06 0.12 6 8])

Berdasarkan hasil grafik regularisasi Tikhonov pada gambar 4.14 didapatkan bahwa nilai norma terkecil diperoleh ketika 𝛼 = 0,0874. Dengan memilih parameter regularisasi 𝛼 = 0,0874 didapatkan hasil restorasi regularisasi Tikhonov sebagai berikut

Gambar 4.15. Gambar hasil restorasi regularisasi Tikhonov dengan 𝛼 = 0,0874 memiliki norma sebesar 6,59414


114

Dari hasil tersebut parameter 𝛼 = 0,0874 memberikan nilai norma yang mengoptimalkan hasil restorasi gambar dengan metode regularisasi Tikhonov. Bentuk algoritma dan diagram alir metode regularisasi Tikhonov dapat dijelaskan sebagai berikut: 1. Bentuk matriks pengaburan yang berukuran sama seperti gambar yang akan direstorasi. 2. Hitunglah SVD dari matriks pengaburan dengan menggunakan fungsi svd Matlab, dan plot nilai-nilai singularnya. 3. Tentukan parameter regularisasi 𝛼 yang dipilih pada interval 𝜎𝑛 , 𝜎1 . 4. Hitung faktor filter Tikhonov 𝜑𝑖 berdasarkan pemilihan nilai 𝛼 yang diperoleh pada langkah 3, kemudian bentuk matriksΦα . 5. Hitunglah 𝐱 𝛼 = 𝑉Φα Λ−1 𝑈 𝑇 𝐛. 6. Ulangi langkah 3 sampai 5 sampai menemukan parameter 𝛼 yang mengoptimalkan hasil restorasi. Kode sintaks program MATLAB dari metode regularisasi Tikhonov ini akan dilampirkan pada program 4.2a dan program 4.2b.


115

Dalam subbab sebelumnya telah dijelaskan mengenai aplikasi restorasi gambar digital menggunakan metode TSVD dan regularisasi Tikhonov. Berdasarkan pada persamaan 4.3 dan 4.5 diperoleh bahwa persamaan untuk metode TSVD ditulis sebagai 𝑘

𝐱 𝑘 = 𝑉Λ 𝑘

−1

𝑇

𝑈 𝐛= 𝑖=1

𝐮𝑖 𝑇 𝐛 𝐯 σ𝑖 𝑖

dan metode regularisasi Tikhonov ditulis sebagai 𝑛 −1

𝑇

𝐱 𝛼 = 𝑉Φα Λ 𝑈 𝐛 = 𝑖=1

𝐮𝑇𝑖 𝐛 𝜑𝑖 𝐯. 𝜎𝑖 𝑖

Dari persamaan di atas perbedaan antara metode TSVD dan regularisasi Tikhonov adalah pada TSVD kita hanya mengamati sebagian dari nilai singular tertentu sejumlah 𝑘. Sedangkan pada regularisasi Tikhonov semua nilai singular dimasukkan dalam perhitungan, tetapi dengan menambahkan faktor filter 𝜑𝑖 . Dibawah ini akan ditampilkan perbedaan hasil restorasi menggunakan metode TSVD dan regularisasi Tikhonov.

a) Hasil restorasi TSVD

b) Hasil restorasi Tikhonov

Gambar 4.16. Hasil restorasi metode TSVD dan regularisasi Tikhonov


116

Gambar 4.16 menunjukkan perbandingan hasil restorasi dengan menggunakan metode TSVD dan regularisasi Tikhonov. Dari hasil yang telah diperoleh pada Gambar 4.10 menunjukkan bahwa hasil restorasi terbaik dari metode TSVD tercapai ketika memilih parameter 𝑘 = 74 dengan selisih nilai norma antara gambar hasil restorasi dan gambar asli sebesar 5,7171. Selanjutnya dilihat dari regularisasi Tikhonov (Gambar 4.15) hasil restorasi terbaik tercapai ketika dipilih parameter regularisasi 𝛼 = 0,0874 dengan selisih nilai norma antara gambar hasil restorasi dan gambar asli sebesar 6,59414. Dengan demikian, berdasarkan hasil restorasi yang telah diperoleh bahwa hasil restorasi dengan TSVD memberikan hasil yang lebih baik dibandingkan dengan regularisasi Tikhonov


BAB V PENUTUP

A. Kesimpulan Regularisasi inverse problem dengan menggunakan metode Truncated Singular Value Decomposition (TSVD) dan regularisasi Tikhonov memberikan peluang untuk tetap memberikan hasil restorasi yang relatif mendekati gambar asli. Metode TSVD mensyaratkan pemotongan jumlah nilai singular yang mendekati nilai nol sedangkan regularisasi Tikhonov mensyaratkan nilai parameter 𝛼 yang tepat. Pemotongan nilai singular pada metode TSVD dimaksudkan untuk membuang nilai-nilai singular kecil yang mendekati nilai nol. Sedangkan pada metode regularisasi Tikhonov semua nilai singular dimasukkan dalam perhitungan tetapi dengan menggunakan faktor filter 𝜑𝑖 , dengan nilai 𝜑𝑖 ≈ 1 jika 𝜎𝑖 > 𝛼 dan 𝜑𝑖 ≈

𝜎𝑖2

𝛼 2 jika 𝜎𝑖 < 𝛼. Kedua metode

tersebut bertujuan untuk mengurangi bahkan menghindari perbesaran galat yang terjadi pada perhitungan penyelesaian. Berdasarkan aplikasi pada bab sebelumnya didapatkan bahwa hasil restorasi gambar digital dengan menggunakan TSVD memberikan penyelesaian yang lebih baik dibandingkan dengan regularisasi Tikhonov. Hal tersebut terlihat dari perhitungan nilai norma pada metode TSVD jauh lebih kecil bila dibandingkan dengan metode regularisasi Tikhonov. Selain


118

itu, kedua metode tersebut sama-sama memberikan hasil restorasi yang cukup baik untuk mendapatkan kembali gambar asli yang mengalami efek derau.

B. Saran Aplikasi metode TSVD dan regularisasi Tikhonov yang dibahas adalah restorasi gambar digital untuk menghilangkan efek derau pada gambar grayscale. Dalam tulisan ini baru digunakan satu model matriks pengaburan yang digunakan untuk proses restorasi. Dengan demikian, disarankan agar pembaca dapat menemukan algoritma yang lebih baik mengenai cara membentuk matriks pengaburan lainnya. Selain itu, pembaca juga dapat memberikan pembahasan mengenai cara menentukan parameter regularisasi 𝛼 menggunakan metode kurva L (L-curve).


DAFTAR PUSTAKA

Atkinson, K. E. 1989. An Introduction to Numerical Analysis (Second Edition). John Wiley & Sons, Inc. Bertero, M. & Boccacci, P. (1998). Introduction to Inverse Problems in Imaging. Philadelphia, PA: IOP Publishing, Ltd Budhi, W. S. (1995). Aljabar linear. Jakarta: Gramedia. Burden, R. L. & Faires, J. D. 2010. Numerical Analysis (Nineth Edition). USA: Brooks/Cole, Cengage Learning. Chong, E. K. P. & Zak, S. H. 2008. An Introduction to Optimization (Third Edition). Hoboken, NJ: John Wiley & Sons, Inc. Groetsch, C. W. (1999). Inverse Problems Activities for Undergraduates. Washington, DC: MAA Hansen, P. C. (2010). Discrete Inverse Problems Insight and Algorithms. Philadelphia, PA: SIAM. Leon, S. J. (1998). Aljabar Linear dan Aplikasinya (Edisi ke-5). Terjemahkan oleh: Alit Bondan. 2001. Jakarta: Erlangga. Moura Neto, F. D.&Silva Neto, A. J. (2013). An Introduction to Inverse Problems with Applications. New York: Springer. Peressini, A. L. dkk. (1988). The Mathematics of Nonlinear Programming. New York: Springer.Solomon, C. & Breckon, T. (2011). Fundamental of Digital Image Processing (First Edition). Hoboken, NJ: John Wiley and Sons, Ltd.


LAMPIRAN

PROGRAM PADA BAB IV Program 4.1a. %PROGRAM 4.1a %Program Restorasi Gambar Digital Dengan Metode TSVD % Keterangan: % X=gambar asli grayscale % A=blurring matrix % PSF=point spread function pemberi efek blur % SVD=nilai-nilai singular matriks A % k=pemotongan nilai singular pada SVD % B=gambar asli yang terpengaruh efek PSF tic X=im2double(imread('cameraman.tif'));%Membaca gambar grayscale lalu %mengkonversikannya ke bentuk double [r,c]=size(X);%Menentukan ukuran matriks X %Membentuk Blurring Matriks (A) a=zeros(r,1); a(1:5)=[5:-1:1]'/25; A=toeplitz(a); %Membentuk Gambar Blur dengan pemberian efek PSF pada X PSF=fspecial('motion',10,110); B=conv2(X,PSF,'same'); %Program TSVD untuk mendapatkan xk [m,n]=size(A);%Ukuran matriks A [U,S,V]=svd(A); %Metode TSVD sesuai dengan pemilihan k k=200; SK=S(1:k,1:k); SKc=[inv(SK) zeros(k,m-k);zeros(n-k,k) zeros(n-k,m-k)]; xk=V*SKc*U'*B; norm_X_B=norm(X-B) norm_X_xk=norm(X-xk) subplot(131), imshow(X), title('Gambar Asli'); subplot(132), imshow(B), title('Gambar Blur'); subplot(133), imshow(xk), title('Gambar hasil Restorasi'); toc

120


Program 4.1b. %PROGRAM 4.1b %Program Restorasi Gambar Digital Dengan Metode TSVD % Keterangan: % X=gambar asli grayscale % A=blurring matrix % PSF=point spread function pemberi efek blur % SVD=nilai-nilai singular matriks A % k=pemotongan nilai singular pada SVD % B=gambar asli yang terpengaruh efek PSF tic X=im2double(imread('cameraman.tif'));%Membaca gambar grayscale lalu %mengkonversikannya ke bentuk double [r,c]=size(X);%Menentukan ukuran matriks X % Membentuk Blurring Matriks (A) a=zeros(r,1); a(1:5)=[5:-1:1]'/25; A=toeplitz(a); % Membentuk Gambar Blur dengan pemberian efek PSF pada X PSF=fspecial('motion',10,110); B=conv2(X,PSF,'same'); % Program TSVD untuk mendapatkan xk [m,n]=size(A);%Ukuran matriks A [U,S,V]=svd(A); % Metode TSVD untuk restorasi Gambar Digital z0=100; for i=1:r; k(i)=i; r=k(i); SK=S(1:r,1:r); SKc=[inv(SK) zeros(r,m-r);zeros(n-r,r) zeros(n-r,m-r)]; xk=V*SKc*U'*B; y(i)=norm(X-xk); if y(i)
121


% % % %

xlabel('parameter k'); ylabel('nilai norma antara X dan xk'); axis([72 75 5.7 5.8]); grid on;

subplot(131), imshow(X), title('Gambar Asli'); subplot(132), imshow(B), title('Gambar Blur'); subplot(133), imshow(XK), title('Gambar hasil Restorasi'); toc

Program 4.2a. %PROGRAM 4.2a %Program Restorasi Gambar Digital Dengan Regularisasi Tikhonov % Keterangan: % X=gambar asli grayscale % A=blurring matrix % PSF=point spread function pemberi efek blur % SVD=nilai-nilai singular matriks A % alfa=parameter regularisasi % B=gambar asli yang terpengaruh efek PSF tic X=im2double(imread('cameraman.tif'));%Membaca gambar grayscale lalu %mengkonversikannya ke bentuk double [r,c]=size(X);%Menentukan ukuran matriks X %Membentuk Blurring Matriks (A) a=zeros(r,1); a(1:5)=[5:-1:1]'/25; A=toeplitz(a); %Membentuk Gambar Blur dengan pemberian efek PSF pada X PSF=fspecial('motion',10,110); B=conv2(X,PSF,'same'); %Program Tikhonov untuk mendapatkan xk [m,n]=size(A);%Ukuran matriks A [U,s,V]=svd(A); [S]=svd(A);%Nilai singular [m,n]=size(S); %Menentukan parameter regularisasi alfa S(76) alfa=0.01; for i=1:m; if S(i)>=alfa; q(i)=1-(alfa/S(i))^2;

122


123

elseif S(i)
Program 4.2b. %PROGRAM 4.2b %Program Restorasi Gambar Digital Dengan Regularisasi Tikhonov % Keterangan: % X=gambar asli grayscale % A=blurring matrix % PSF=point spread function pemberi efek blur % SVD=nilai-nilai singular matriks A % alfa=parameter regularisasi % B=gambar asli yang terpengaruh efek PSF tic X=im2double(imread('cameraman.tif'));%Membaca gambar grayscale lalu %mengkonversikannya ke bentuk double [r,c]=size(X);%Menentukan ukuran matriks X %Membentuk Blurring Matriks (A) a=zeros(r,1); a(1:5)=[5:-1:1]'/25; A=toeplitz(a); %Membentuk Gambar Blur dengan pemberian efek PSF pada X PSF=fspecial('motion',10,110);


124

B=conv2(X,PSF,'same'); %Program Tikhonov untuk mendapatkan xk [m,n]=size(A);%Ukuran matriks A [U,s,V]=svd(A); [S]=svd(A);%Nilai singular [m,n]=size(S); %Menentukan parameter regularisasi alfa z0=100; % alfa=S(1):-0.01:S(m); % alfa=0:0.01:0.2; alfa=0.06:0.0001:0.12; for j=1:length(alfa); alfa_1=alfa(j); for i=1:m; if S(i)>=alfa_1; q1(i)=1-(alfa_1/S(i))^2; elseif S(i)

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Recommend Documents