PERBANDINGAN METODE ITERASI JACOBI DAN ITERASI GAUSS-SEIDEL DALAM PENYELESAIAN SISTEM PERSAMAAN LINIER DENGAN MENGGUNAKAN SIMULASI KOMPUTASI
(Skripsi)
Oleh Shella Niyyaka
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS LAMPUNG LAMPUNG 2016
ABSTRACT
ITERATION METHOD COMPARISON JACOBI AND GAUSS-SEIDEL ITERATION IN SETTLEMENT SYSTEM USING LINEAR EQUATION SIMULATION COMPUTATION
System of linear equations is a set of linear equations has a solution (or do not have a solution) are the same for all equations. Settlement of linear equation system is divided into two methods, methods of direct and indirect methods (iterative). Iterative method consists of iterations of Jacobi and Gauss-Seidel iteration. Jacobi iteration method is iterative method that calculates the value approximations current or latest by reference to the previous approximation. Jacobi iteration common forms are: ( )
=
1
(
−
)
, = 1,2, … , ;
= 1,2,3, …,
Gauss-Seidel iteration method is iterative method that calculates the value approximations present by reference to the latest approximations. The general form of Gauss-Seidel iteration is: ( )
=
1
−
( )
−
(
)
, = 1,2, … , ;
= 1,2,3, …,
Keywords: Systems of linear equations, iteration method, Jacobi iteration, GaussSeidel iterations, computational simulation.
ABSTRAK
PERBANDINGAN METODE ITERASI JACOBI DAN ITERASI GAUSSSEIDEL DALAM PENYELESAIAN SISTEM PERSAMAAN LINIER DENGAN MENGGUNAKAN SIMULASI KOMPUTASI
Oleh SHELLA NIYYAKA
Sistem persamaan linier merupakan kumpulan persamaan linier yang mempunyai solusi (atau tidak mempunyai solusi) yang sama untuk semua persamaan. Penyelesaian sistem persamaan linier terbagi menjadi dua metode, metode langsung dan metode tak langsung (iteratif). Metode iteratif terdiri dari iterasi Jacobi dan iterasi Gauss-Seidel. Metode iterasi jacobi adalah metode iterasi yang menghitung nilai hampiran sekarang atau terbaru dengan mengacu pada nilai hampiran sebelumnya. Bentuk umum iterasi Jacobi adalah : ( )
=
1
(
−
)
, = 1,2, … , ;
= 1,2,3, …,
Metode iterasi Gauss-Seidel adalah metode iterasi yang menghitung nilai hampiran sekarang dengan mengacu pada nilai hampiran terbaru. Bentuk umum iterasi Gauss-Seidel adalah : ( )
=
Kata kunci
1
−
( )
−
(
)
, = 1,2, … , ;
= 1,2,3, …,
: Sistem persamaan linier, metode iterasi, iterasi Jacobi, Iterasi Gauss-Seidel, simulasi komputasi.
PERBANDINGAN METODE ITERASI JACOBI DAN ITERASI GAUSS-SEIDEL DALAM PENYELESAIAN SISTEM PERSAMAAN LINIER DENGAN MENGGUNAKAN SIMULASI KOMPUTASI
Oleh
Shella Niyyaka Skripsi Sebagai Salah Satu Syarat untuk Memperoleh Gelar SARJANA SAINS Pada Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS LAMPUNG BANDAR LAMPUNG 2016
RIWAYAT HIDUP
Penulis dilahirkan di Sukosari, Kecamatan Adiluwih, Kabupaten Pringsewu pada tanggal 23 Mei 1995, dan merupakan anak pertama dari 2 bersaudara, anugerah cinta dari pasangan Ayah Widodo dan Mama Janatun.
Penulis menyelesaikan pendidikan di Sekolah Dasar Negeri 6 Poncokresno pada tahun 2006/2007, Madrasah Tsanawiyah Negeri 1 Pringsewu pada tahun 2009/2010, Sekolah Menengah Atas Negeri 2 Pringsewu pada tahun 2012/2013. Selanjutnya pada tahun 2012 penulis mengikuti Seleksi Ujian Mandiri (UM) dan berhasil diterima sebagai mahasiswi di Universitas Lampung Jurusan Maematika Fakultas Matematika dan Ilmu Pengetahuan Alam.
Selama menjadi mahasiswi penulis aktif di organisasi kampus yaitu pernah menjadi anggota muda HIMATIKA tahun 2012-2013 dan Anggota Bidang Dana dan Usaha HIMATIKA tahun 2013-2014.
Pada tanggal 1 Juli sampai dengan 30 Juli 2015, penulis melaksanakan kegiatan Kerja Praktek (KP) di Dinas Peternakan dan Kesehatan Hewan Provinsi Lampung guna mengaplikasikan ilmu yang telah di dapatkan sewaktu kuliah. Pada tanggal 19 Januari 2016 sampai dengan tanggal 18 Maret 2016 penulis telah mengikuti Kuliah Kerja Nyata (KKN) di Desa Trikarya Kecamatan Penawartama, Kabupaten Tulang Bawang.
KATA INSPIRASI
Sebuah tantangan akan selalu menjadi beban, jika itu hanya difikirkan. Sebuah cita-cita juga adalah beban, jika itu hanya anganangan
Kesuksesan hanya dapat diraih dengan segala upaya dan usaha yang disertai dengan doa, karena sesungguhnya nasib seorang manusia tidak akan berubah dengan sendirinya tanpa berusaha
Tidak ada masalah yang tidak bisa diselesaikan selama ada komitmen bersama untuk menyelesaikannya. Berangkat dengan penuh keyakinan, berjalan dengan penuh keikhlasan, istiqomah dalam menghadapi cobaan.
SEMANGATKU... Ketika aku mulai merasa lelah, aku selalu ingat pesan dan raut wajah beliau ketika memberiku semangat dan tersenyum menenangkanku.
PERSEMBAHAN
Alhamdulillahirabbil’alamin, syukur yang indah kuucapkan kepada ALLAH Rabbul Ta’ala, atas ridhoNya skripsi ini dapat terselesaikan, atas ridhoNya diberikan segala kemudahan, dan atas ridhoNya pula akan didatangkan suatu kemanfaatan.
Dengan segala kerendahan hati, kupersembahkan sebuah karya kecil ini untuk orang-orang yang kusayangi, orang-orang yang menyemangati tanpa henti, menemani serta mendoakan dengan ikhlas tanpa pamrih.
Untukmu AYAH (Widodo) dan MAMA (Janatun) tersayang yang menjadi kebahagiaan serta motivasi terbesar dalam menyelesaikan studiku. Kepada Mamasku Dafid Sela Anggara dan Adikku Sahrul Arsyaddana, bentuk perhatian, pengertian, doa, semangat dan bantuannya, terimakasih untuk segalanya. Kepada teman-teman Matematika 2012, serta Almamater tercinta Universitas Lampung, semangat serta keceriaan kalian semuanya menjadi penambah kekuatan semangat dalam hidup dan tujuan hidupku untuk tetap bangkit.
“kupersembahkan untuk kalian, inspirasiku...”
SANWACANA
Alhamdulillahirabbil’alamin dengan rasa syukur kehadirat Allah SWT serta rahmat dan karunia Nya skripsi ini dapat diselesaikan. Skripsi dengan judul “Perbandingan Metode Iterasi Jacobi dan Iterasi Gauss-Seidel dalam Penyelesaian Sistem Persamaan Linier” disusun sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains (S.Si) di Universitas Lampung. Selesainya skripsi ini, adalah juga berkat motivasi dan pengarahan serta bimbingan dari berbagai pihak. Oleh karena itu, dengan segala kerendahan hati penulis ingin menyampaikan banyak terima kasih kepada: 1.
Ibu Dra. Dorrah Aziz, M.Si, selaku Dosen Pembimbing 1 yang telah meluangkan waktu dan membimbing penulis selama menyusun skripsi.
2.
Bapak Subian Saidi, S.Si., M.Si, selaku Dosen Pembimbing 2 yang telah memberi banyak masukan dan arahan kepada penulis selama menyusun skripsi.
3.
Bapak Agus Sutrisno, M.Si, selaku Dosen Pembahas yang memberi masukan dan evaluasi kepada penulis selama menyusun skripsi.
4.
Bapak Warsono, Ph. D, selaku Pembimbing Akademik yang telah mengarahkan penulis dari awal sampai lulus kuliah.
5.
Bapak Drs. Tiryono Rubby, M.Sc., Ph.D, selaku Ketua Jurusan Matematika
FMIPA Universitas Lampung. 6.
Bapak Prof. Suharso, Ph.D, selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas lampung.
7.
Dosen, staf, dan karyawan Jurusan Matematika FMIPA Universitas Lampung yang telah memberikan ilmu serta bantuan kepada penulis.
8.
Ayah dan Mama ku tersayang yang telah memberikan motivasi, do’a, dan kasih sayang yang begitu besar serta dukungan moril maupun materil kepada penulis.
9.
Kakak dan adikku tersayang yang selalu memberi motivasi kepada penulis.
10. Sahabat yang kini menjadi Saudaraku Ira, Sri, Tika, Azizah, Astuti, Siti, Desi, Fahmi, Putri dan Resti yang menjadi pendengar keluh kesah penulis saat menempuh pendidikan di Universitas Lampung. 11. Teman-teman angkatan 2012 yang selalu memberikan motivasi dan dukungan dalam menyelesaikan skripsi ini. 12. Seluruh pihak yang telah membantu penulis yang tidak dapat disebutkan satu persatu, atas peran dan dukungannya dalam menyusun skripsi ini.
Penulis menyadari bahwa skripsi ini masih jauh dari kata sempurna, sehingga kritik dan saran yang membangun sangat penulis harapkan. Akhir kata, semoga skripsi ini dapat berguna bagi pembaca sebagai acuan di penelitian selanjutnya.
Bandarlampung, 3 Oktober 2016 Penulis
Shella Niyyaka
DAFTAR ISI
Halaman DAFTAR ISI.................................................................................................. i DAFTAR TABEL .......................................................................................iii DAFTAR GAMBAR................................................................................... iv I.
PENDAHULUAN 1.1 1.2 1.3
II.
Latar Belakang dan Masalah.................................................... 1 Tujuan Penelitian ..................................................................... 2 Manfaat Penelitian ................................................................... 2
TINJAUAN PUSTAKA 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8
Persamaan Linier ......................................................................... 4 Persamaan Aljabar (Polinomial Berderajat n) ............................. 4 Persamaan Transendental ............................................................ 4 Sistem Persamaan Linear............................................................. 5 Sistem Persamaan Linier Homogen ............................................ 6 Sistem Persamaan Linier Tak Homogen ..................................... 6 Matriks......................................................................................... 6 Macam-Macam Matriks............................................................... 7 2.8.1 Matriks Kuadrat Berorde n ............................................. 7 2.8.2 Matriks Identitas ............................................................. 7 2.8.3 Matriks Bujursangkar...................................................... 7 2.8.4 Matriks Diagonal ............................................................ 8 2.8.5 Matriks Upper Triangular .............................................. 8 2.8.6 Matriks Lower Triangular .............................................. 8 2.8.7 Matriks Tridiagonal ........................................................ 9 2.9 Vektor Baris dan Vektor Kolom................................................. 9 2.10 Metode Iterasi Jacobi................................................................ 10 2.11 Metode Iterasi Gauss-Seidel ..................................................... 15 2.12 Stasioner ................................................................................... 18 2.13 Kekonvergenan Iterasi Matriks................................................. 19 2.14 M-File Sebagai Skrip Program ................................................. 20 2.15 Variabel-Variabel yang Digunakan .......................................... 21
ii
Halaman 2.16 2.17 2.18 2.19 2.20 III
Galat dalam Penyelesaian Sistem Persamaan Linier ................ Definisi Galat............................................................................ Konsep Norm dan Bilangan Kondisi Suatu Matriks ................ Ukuran Besar Vektor dan Matriks............................................ Kekonvergenan Iterasi Jacobi dan Gauss-Seidel......................
22 23 23 24 26
METODOLOGI PENELITIAN 3.1 Waktu Penelitian........................................................................ 28 3.2 Metode Penelitian 3.2.1 Iterasi Jacobi .................................................................. 28 3.2.2 Iterasi Gauss-Seidel ....................................................... 30
IV
HASIL DAN PEMBAHASAN 4.1 4.2 4.3 4.4 4.5 4.6
V
Kondisi Matriks err < tol, dengan tol = 0.001 ........................... Kondisi Matriks 2 x 2 pada err < tol, dengan tol = 0.001.......... Kondisi Matriks 3 x 3 pada err < tol, dengan tol = 0.001.......... Kondisi Matriks 4 x 4 pada err < tol, dengan tol = 0.001.......... Kondisi Matriks 5 x 5 pada err < tol, dengan tol = 0.001.......... Kondisi Matriks 10 x 10 pada err < tol, dengan tol = 0.001......
SIMPULAN
DAFTAR PUSTAKA LAMPIRAN
32 33 36 39 43 46
DAFTAR GAMBAR
Gambar 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.
Halaman
Tampilan Awal MATLAB R2014a................................................ 20 Flow Chart Metode Iterasi Jacobi .................................................. 29 Flow Chart Metode Iterasi Gauss-Seidel ....................................... 31 Cara Save and Load pada Command Window Matriks 2 x 2 di dalam MATLAB R2014a........................................................... 34 Rumus Iterasi Jacobi Matriks 2 x 2 ................................................ 34 Rumus Iterasi Gauss-Seidel Matriks 2 x 2 ..................................... 35 Cara Save and Load pada Command Window Matriks 3 x 3 di dalam MATLAB R2014a........................................................... 37 Rumus Iterasi Jacobi Matriks 3 x 3 ................................................ 38 Rumus Iterasi Gauss-Seidel Matriks 3 x 3 ..................................... 39 Cara Save and Load pada Command Window Matriks 4 x 4 di dalam MATLAB R2014a........................................................... 41 Rumus Iterasi Jacobi Matriks 4 x 4 ................................................ 42 Rumus Iterasi Gauss-Seidel Matriks 4 x 4 ...................................... 42 Rumus Iterasi Jacobi Matriks 5 x 5 ................................................ 45 Rumus Iterasi Gauss-Seidel Matriks 5 x 5 ..................................... 45 Rumus Iterasi Jacobi Matriks 10 x 10 ............................................ 48 Rumus Iterasi Gauss-Seidel Matriks 10 x 10 .................................. 49
DAFTAR TABEL
Tabel 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
Halaman Hasil Iterasi Jacobi .......................................................................... 15 Hasil Iterasi Gauss-Seidel ............................................................... 18 Kondisi Matriks err < tol, dengan tol = 0.001 ................................. 32 Kondisi Matriks 2 x 2 pada err < tol, dengan tol = 0.001 ............... 33 Matriks 2 x 2 dari Masing-Masing Percobaan ................................ 33 Kondisi Matriks 3 x 3 pada err < tol, dengan tol = 0.001 ............... 36 Matriks 3 x 3 dari Masing-Masing Percobaan ................................ 36 Kondisi Matriks 4 x 4 pada err < tol, dengan tol = 0.001 ................ 39 Matriks 4 x 4 dari Masing-Masing Percobaan ................................ 40 Kondisi Matriks 5 x 5 pada err < tol, dengan tol = 0.001 ............... 43 Matriks 5 x 5 dari Masing-Masing Percobaan ................................ 44 Kondisi Matriks 10 x 10 pada err < tol, dengan tol = 0.001 ........... 46 Matriks 10 x 10 dari Masing-Masing Percobaan ............................ 47
1
I.
1.1
PENDAHULUAN
Latar Belakang dan Masalah
Sistem persamaan linear merupakan salah satu model dan masalah matematika yang banyak diterapkan dalam berbagai ilmu. Suatu sistem persamaan linear terdiri atas sejumlah berhingga persamaan linear dalam sejumlah berhingga variabel. Sistem Persamaan Linear dalam bentuk persamaan perkalian matriks dapat ditulis Ax = b. Di dalam penyelesaian sistem persamaan akan dicari nilai x1, x2, ..., xn yang memenuhi sistem persamaan berikut :
⋮
+ +
+
⋮
+ +
+
⋯ + ⋯ +
⋯ +
⋮
= = =
Dengan a adalah koefisien konstan, b adalah konstan, n adalah jumlah persamaan, dan x1, x2, ..., xn adalah bilangan tak diketahui. Menyelesaikan suatu sistem persamaan linier adalah mencari nilai-nilai variabelvariabel tersebut yang memenuhi semua persamaan linier yang diberikan. Terdapat dua kelompok yang dapat digunakan untuk menyelesaikan sistem persamaan linier. Metode pertama yaitu metode langsung, yakni metode yang
2
mencari sistem persamaan linier dalam langkah berhingga. Contohnya seperti metode eliminasi gauss dan metode eliminasi gauss jordan. Kelompok kedua dikenal sebagai metode tak langsung atau metode iterasi, yang bermula dari suatu hampiran awal dan kemudian berusaha memperbaiki hampiran penyelesaian awal dan kemudian berusaha memperbaiki hampiran dalam tak berhingga namun menggunakan langkah konvergen. Metode iterasi digunakan untuk menyelesaikan sistem persamaan linier berukuran besar dan proporsi koefisien nolnya besar. Metode iterasi yang akan dibahas yaitu metode iterasi Jacobi dan metode iterasi Gauss-Seidel. Pada metode iterasi Jacobi, nilai hampiran dikoreksi secara serentak. Artinya nilai hampiran mengacu pada nilai hampiran sebelumnya. Sedangkan pada metode Gauss-Seidel, nilai hampiran dihitung berdasarkan nilai hampiran terbaru atau terakhir. Menyelesaikan metode iterasi Jacobi dan iterasi Gauss-Seidel menggunakan simulasi komputasi dengan software MATLAB R2014a.
1.2
Tujuan Penelitian
Berdasarkan latar belakang di atas, penelitian ini bertujuan untuk mengetahui kecepatan dan keakuratan antara metode iterasi Jacobi dan iterasi Gauss-Seidel dalam menyelesaikan sistem persamaan linier dengan simulasi komputasi.
1.3
1.
Manfaat Penelitian
Dapat memberikan sumbangan pemikiran untuk menyelesaikan persamaan linier dengan menggunakan metode iterasi.
3
2.
Meningkatkan kemampuan penggunaan konsep sistem persamaaan linier dengan metode iterasi Jacobi dan iterasi Gauss-Seidel dalam simulasi komputasi.
3.
Mengetahui tingkat kecepatan dan keakuratan metode iterasi Jacobi dan iterasi Gauss-Seidel pada masing-masing matriks.
4.
Mengetahui kelebihan dan kelemahan dari masing-masing metode iterasi Jacobi dan iterasi Gauss-Seidel yang dilihat dari kecepatan dan keakuratan solusi SPL menggunakan simulasi komputasi.
II. TINJAUAN PUSTAKA
2.1 Persamaan Linear Suatu Persamaan Linear dengan n peubah x1, x2, . . . , xn adalah persamaan yang dapat ditulis dalam bentuk : +
+⋯+
=
(2.1)
Dengan a1, a2, . . . , an dan b adalah konstanta-konstanta riil, n adalah jumlah persamaan, dan x1, x2, . . . , xn adalah bilangan tak diketahui (Anton, 1987).
2.2 Persamaan Aljabar (Polinomial Berderajat n) Suatu persamaan aljabar dalam variabel x adalah suku banyak (polinomial) berderajat n ≥ 1 dalam x, yang dapat dituliskan secara umum dalam bentuk : anxn+an-1xn-1+ ... +a1x+a0 = 0
(2.2)
dengan an, an-1, ..., a1, dan a0 adalah konstanta-konstanta yang diketahui. Apabila a0 = 0, maka persamaan tersebut dikatakan homogen (Sahid, 2005).
2.3 Persamaan Transendental Suatu persamaan transendental dalam x memuat suku dalam x yang tidak dapat dinyatakan sebagai berhingga operasi aljabar (penjumlahan atau pengurangan dan perkalian atau pembagian). Sebagai contoh : sin (x), ln (x), ex adalah bentuk berhingga penjumlahan (Sahid, 2005).
5
2.4 Sistem Persamaan Linear Penyelesaian dari persamaan linier a1x1 + a2x2 + ... + anxn = b adalah urutan dari bilangan s1, s2, ... , sn sedemikian sehingga persamaan tersebut bernilai benar bila bilangan s1, s2, ... , sn masing-masing disubstitusikan ke x1, x2, . . . , xn. Suatu sistem sebarang yang terdiri dari n persamaan linear dengan peubah n ditulis sebagai : +
+
⋮
+
+⋯+ ⋮
+⋯+ + ⋯+
=
=
⋮
=
⋮
(2.3)
Kuantitas-kuantitas aij (untuk i, j = 1, 2, ..., n) disebut koefisien. Nilai koefisienkoefisien aij dan ruas kanan bi pada setiap persamaan diketahui. Kuantitaskuantitas xij disebut variabel, yang nilainya belum diketahui dan hendak dicari. Sistem persamaan di atas dapat ditulis dalam bentuk matriks sebagai : AX = B Dengan A adalah sebuah matriks n x n :
⎛ =⎜ ⎝
⋮
⋮
⋯ ⋯ ⋯ ⋮ …
dan X dan B adalah vektor-vektor n-komponen : =( ,
,
,…,
)
=( ,
⋮
⎞ ⎟
(2.4)
⎠ ,
,…,
)
Dengan pangkat T menyatakan operasi transpose matriks, yakni mengubah baris menjadi kolom dan kolom menjadi baris. Matriks A disebut matriks koefisien, vektor kolom B sering disebut vektor konstanta.
6
Sistem persamaan linier dapat diklasifikasikan, menurut penyelesaiannya, menjadi tiga kelompok : 1.
SPL yang mempunyai penyelesaian tunggal.
2.
SPL yang tidak mempunyai penyelesaian.
3.
SPL mempunyai tak berhingga penyelesaian (Sahid, 2005).
2.5 Sistem Persamaan Linier Homogen Apabila semua nilai bi = 0 untuk i = 1, 2, ..., n, maka SPL (2.4) disebut sistem persamaan linier homogen (Sahid, 2005).
2.6 Sistem Persamaan Linier Tak Homogen Apabila terdapat bk ≠ 0 untuk suatu 1 ≤ k ≤ n, maka SPL (2.4) disebut sistem persamaan linier tak homogen (Sahid, 2005).
2.7 Matriks Suatu matriks adalah susunan bilangan real berbentuk empat persegi panjang yang diatur dalam baris dan kolom.
Secara umum matriks A =
⋮
⋮
⋯ ⋯ ⋱ ⋯
⋮
Di dalam bentuk di atas, A adalah notasi matriks sedang aij adalah elemen matriks. Deretan horisontal elemen-elemen disebut baris dan deretan vertikal disebut kolom. Subskrip i menunjukkan nomor baris dimana elemen berada. Subskrip kedua j menunjukkan kolom. Matriks di atas mempunyai m baris dan n kolom, dan disebut mempunyai dimensi m kali n (m x n) (Anton, 1987).
7
1 2 −2 1 5 7 Contoh : 2 3 4 5 dan −1 2 0 3 3 1 −1 0 2.8 Macam-Macam Matriks 2.8.1 Matriks kuadrat berorde n Sebuah matriks dengan n baris dan n kolom dinamakan matriks kuadrat berorde n (square matrix of order n), dan elemen-elemen a11, a22, ... , ann diletakkan pada diagonal utama (Anton, 1987).
Misalkan A =
⋮
6 2 7 Contoh : 2 3 4 3 1 2
⋮
⋯ ⋯ ⋱ ⋯
1 1 5 dan 3 9
⋮ 2 4
2.8.2 Matriks Identitas Matriks identitas adalah matriks diagonal yang semua elemen pada diagonal utama adalah 1 (Anton, 1987). 1 = 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
2.8.3 Matriks Bujursangkar Matriks bujursangkar adalah matriks yang jumlah baris dan jumlah kolomnya sama (Anton, 1987). Contoh :
8
Matriks bujursangkar berukuran 3 x 3 atau sering juga disebut matriks bujursangkar orde 3. 1 3 = 5 9 2 4
8 7 6
2.8.4 Matriks Diagonal Matriks diagonal adalah matriks bujursangkar yang seluruh elemennya bernilai 0 (nol), kecuali elemen-elemen diagonalnya (Anton, 1987). Contoh : Matrik diagonal orde 3. 11 0 = 0 29 0 0
0 0 61
2.8.5 Matriks Upper Triangular Matriks upper triangular adalah matriks bujursangkar yang seluruh elemen di bawah elemen diagonal bernilai 0 (nol) (Anton, 1987). Contoh : 3 = 0 0 0
6 4 0 0
2 1 8 0
1 5 7 9
2.8.6 Matriks Lower Triangular Matriks lower triangular adalah matriks bujursangkar yang seluruh elemen di atas elemen diagonal bernilai 0 (nol) (Anton, 1987). Contoh :
9
12 0 0 0 = 32 −2 0 0 8 7 11 0 −5 10 6 9 2.8.7 Matriks Tridiagonal Matriks tridiagonal adalah matriks bujursangkar yang seluruh elemen bukan 0 (nol) berada disekitar elemen diagonal, sementara elemen lainnya bernilai 0 (nol) (Anton, 1987). Contoh : 3 6 0 = 2 −4 1 0 7 8 0 0 6
0 0 7 9
2.9 Vektor Baris dan Vektor Kolom Notasi vektor biasanya dinyatakan dengan huruf kecil dan dicetak tebal. Suatu matriks dinamakan vektor baris berukuran m, bila hanya memiliki satu baris dan m kolom, yang dinyatakan sebagai berikut : =[
⋯
⋯
]=[
]
Sedangkan suatu matriks dinamakan vektor kolom berukuran n, bila hanya memiliki satu kolom dan n baris, yang dinyatakan sebagai berikut :
=
⋮
=
⋮
10
2.10 Metode Iterasi Jacobi Metode iterasi Jacobi merupakan salah satu bidang analisis numerik yang digunakan untuk menyelesaikan permasalahan persamaan linier dan sering Dijumpai dalam berbagai disiplin ilmu. Metode iterasi Jacobi merupakan salah satu metode tak langsung, yang bermula dari suatu hampiran penyelesaian awal dan kemudian berusaha memperbaiki hampiran dalam tak berhingga namun langkah konvergen. Metode iterasi Jacobi ini digunakan untuk menyelesaikan persamaan linier yang proporsi koefisien nol nya besar. Metode ini ditemukan olek matematikawan yang berasal dari Jerman, Carl Gustav Jakob Jacobi. Penemuan ini diperkirakan pada tahun 1800-an. Iterasi dapat diartikan sebagai suatu proses atau metode yang digunakan secara berulang-ulang (pengulangan) dalam menyelesaikan suatu permasalahan matematika. Jika diubah dari persamaan linier, maka akan menjadi : =
Kemudian diketahui bahwa A = D + (L + U), dimana D merupakan matriks diagonal, L merupakan matriks segitiga bawah, dan U merupakan matriks segitiga atas. Lalu persamaan tersebut diubah menjadi
=
+( + ) =
[ −( + ) ]
Jika ditulis dalam aturan iteratif, maka metode iterasi Jacobi dapat ditulis sebagai berikut : ( )
=
( −( + )
(
)
)
(2.5)
11
Dimana k merupakan banyaknya iterasi. Jika x(k) menyatakan hampiran ke –k penyelesaian SPL, maka x(0) adalah hampiran awal. ( )
(
−∑
=
)
, = 1,2, … , ;
= 1,2,3, …,
(2.6)
Suatu matriks A berukuran n x n dikatakan dominan secara diagonal apabila : |aii| > |ai,1| + ...+|ai,i-1| + |ai,i+1| + ...+ |ai,n| untuk i = 1, 2, ... , n. Berikut adalah gambaran bagaimana menggunakan metode iterasi Jacobi dengan sebuah contoh. Misalkan ingin menyelesaikan SPL : 10x1 − x2 + 2x3
=6
(P1)
-x1 + 11x2 – x3 + 3x4 = 25
(P2)
2x1 – x2 + 10 x3 – x4 = -11
(P3)
3x2 – x3 + 8x4 = 15
(P4)
Jawab : Nyatakan terlebih dahulu setiap variabel dalam ketiga variabel yang lain : 1.
Nyatakan x1 dari persamaan (P1) dalam x2, x3, dan x4.
2.
Nyatakan x2 dari persamaan (P2) dalam x1, x3, dan x4.
3.
Nyatakan x3 dari persamaan (P3) dalam x1, x2, dan x4.
4.
Nyatakan x4 dari persamaan (P4) dalam x1, x2, dan x3.
Hasilnya adalah SPL : =
=
=− =−
− +
+ +
+
− +
(P5)
+
+
(P6) −
(P7) (P8)
12
Nyatakan bahwa nilai x1, x2, x3, dan x4 yang berada di ruas kiri = (baca : sama dengan) sebagai x(baru). Sementara nilai x1, x2, x3, dan x4 yang berada di ruas kanan tanda = (baca : sama dengan) sebagai x(lama). Sehingga sistem persamaan tersebut dapat ditulis seperti : (
)
(
)
(
)
(
)
=
=
(
)
(
) (
=−
(
=−
− + )
)
+
+
(
)
(
)
+
( (
(
− )
)
+
) (
+
+ )
−
yang secara umum dapat diformulasikan sebagai persamaan matrik berikut ini : (
)
dimana
⎡ ⎢ ⎢ ⎢ ⎢ ⎣
⎡ 0 ) ⎢ ⎤ ⎢ 1 )⎥ ⎢ ⎥ = ⎢ 11 ) 2 ⎥ ⎢ − ⎥ ) 10 ⎦ ⎢ ⎢ ⎣0
( ( ( (
=
1 10
(
)
+
(2.7)
2 − 0 ⎤ 10 ⎥ 1 3 ⎥⎡ − ⎢ 11 11 ⎥ ⎢ 1 ⎥⎢ ⎥ 0 10⎥ ⎢ ⎣ 1 ⎥ 0 ⎦ 8
0
1 10 3 − 8
6 ⎡ ⎤ ) 10 ⎥ ⎢ ⎤ 25 ⎢ ⎥ )⎥ 11 ⎢ ⎥ ⎥ + ) ⎥ ⎢ 11⎥ ⎥ ⎢− 10⎥ ) ⎦ ⎢ 15 ⎥ ⎣ 8 ⎦
( ( ( (
atau dapat pula di tulis : =
+
(2.8)
dimana k = 1, 2, 3, ..., n. Sehingga persamaan matriks dapat dinyatakan sebagai : ⎡ ⎢ ⎢ ⎢ ⎢ ⎣
0 ⎤ ⎡ ⎢ )⎥ ⎥ = ⎢⎢ ) ⎥ ⎢− ⎥ ⎢ ) ⎦ ⎣0
( ) ( ( (
0 −
− 0
0⎤ ⎡ − ⎥⎥ ⎢ ⎥ ⎢⎢ ⎥⎢ ⎥ 0 ⎦⎣
( ( ( (
)
⎤ ⎡ ⎢ )⎥ ⎥+⎢ ) ⎥ ⎢− ⎥ ⎢ ) ⎦ ⎣
⎤ ⎥ ⎥ ⎥ ⎥ ⎦
(2.9)
13
Pada persamaan (2.9), indeks k menunjukan jumlah perhitungan iterasi. Pada k = 1, dapat ditulis persamaan linier sebagai berikut : ( ) ( ) ( ) ( )
=
=
=− =−
( ) ( )
( )
− +
( ) ( )
( )
+
+
+ −
( ) ( )
+
( )
+
( )
+
−
Jika diberikan nilai-nilai awal x(0) adalah x1(0) = 0, x2(0) = 0, x3(0) = 0, dan x4(0) = 0, atau dinyatakan sebagai hampiran awal x(0) = (0;0;0;0)T, maka hampiran pertama pada penyelesaian tersebut adalah : ( ) ( ) ( ) ( )
=
6 = 0.6 10
=
25 = 2.2727 11
=
15 = 1.8750 8
=−
11 = −1.1 10
Atau x(1)= [0.6000;2.2727;-1.1000;1.8750] T. Setelah nilai x(1) diperoleh, perhitungan tersebut diulang kembali untuk mendapatkan hasil iterasi kedua, yaitu ketika k = 2. Caranya adalah dengan memasukan nilai-nilai x(1)= (0.6000;2.2727;-1.1000;1.8750)T ke suku-suku pada ruas kanan tanda sama dengan, ( ) ( ) ( )
=
=
=−
( ) ( )
( )
− +
( )
( )
+
+ −
( )
( )
+
+
( )
−
14
( )
=−
( )
( )
+
+
Maka nilai-nilai x(2) yang didapat adalah x(2) = (1.0473; 1.7159; -0.8052; 0.8852)T. Setelah diperoleh nilai-nilai x(2), perhitungan tersebut diulang kembali agar mendapatkan iterasi ketiga, dimana nilai k = 3. Caranya adalah dengan memasukan nilai-nilai x(2) = (1.0473; 1.7159; -0.8052; 0.8852)T ke ruas kanan kembali, ( ) ( ) ( ) ( )
( )
=
( )
=
=− =−
( )
− +
( ) ( )
( )
+
+
+ −
( ) ( )
+
( )
+
( )
+
−
Maka diperoleh nilai-nilai x(3) = (0.9326; 2.0530; -1.0493; 1.1309)T. Lalu proses perhitungan diulangi lagi dengan k = 4. Begitulah seterusnya. Proses ini diulangi berkali-kali untuk nilai-nilai k berikutnya. Proses yang berulang ini disebut proses iterasi. Sampai dengan x(3) di atas, telah dilakukan tiga kali proses iterasi. Proses iterasi akan terus berlanjut sampai x(baru) mendekati solusi yang tepat, yaitu : x = (1; 2; -1; 1)T dengan kata lain, proses iterasi harus dihentikan bila x(baru) sudah mendekati solusi. Berikut adalah hasil proses iterasi dengan menggunakan MATLAB R2014a. n
x1
x2
x3
x4
Waktu (s)
err
1
0.6000
2.2727
-1.1000
1.8750
0.0011
3.2017
2
1.0473
1.7159
-0.8052
0.8852
1.6287e-04
1.2556
3
0.9326
2.0533
-1.0493
1.1309
8.9244e-05
0.4969
15
4
1.0152
1.9537
-0.9681
0.9738
1.0308e-04
0.2191
5
0.9890
2.0114
-1.0103
1.0214
8.3443e-05
0.0897
6
1.0032
1.9922
-0.9945
0.9944
1.2762e-04
0.0393
7
0.9981
2.0023
-1.0020
1.0036
1.3476e-04
0.0163
8
1.0006
1.9987
-0.9990
0.9989
8.4782e-05
0.0071
9
0.9997
2.0004
-1.0004
1.0006
8.3443e-05
0.0030
10 1.0001
1.9998
-0.9998
0.9998
1.1780e-04
0.0013
Tabel 1. Hasil Iterasi Jacobi. Setelah iterasi ke-10 diperoleh hampiran penyelesaian x = (1.0001; 1.9998; -0.9998; 0.9998)T bandingkan dengan penyelesaian eksaknya, yakni x = (1; 2; -1; 1)T (Sahid, 2007).
2.11 Metode Iterasi Gauss-Seidel Metode Gauss-Seidel digunakan untuk menyelesaikan sistem persamaan linier (SPL) berukuran besar dan proporsi koefisien nolnya besar, seperti sistem-sistem yang banyak ditemukan dalam sistem persamaan diferensial. Teknik iterasi jarang digunakan untuk menyelesaikan SPL berukuran kecil karena metode-metode langsung seperti metode eliminasi Gauss lebih efisien daripada metode iteratif. Akan tetapi, untuk SPL berukuran besar dengan persentase elemen nol pada matriks koefisien besar, teknik iterasi lebih efisien daripada metode langsung dalam hal penggunaan memori komputer maupun waktu komputasi. Dengan metode iterasi Gauss-Seidel hampiran pembulatan dapat diperkecil karena dapat meneruskan iterasi sampai solusinya seteliti mungkin sesuai dengan batas hampiran yang diperbolehkan. Pada metode iterasi Gauss-Seidel, nilai-nilai yang paling akhir dihitung digunakan di dalam semua perhitungan. Jelasnya, di dalam iterasi Jacobi, menghitung
16
( )
( )
=
,
( )
,
(
,…,
( )
,
( )
sedangkan pada iterasi Gauss-Seidel menghitung (
)
(
=
)
)
,…,
(
)
,…,
( )
( )
,…,
,
(2.10)
( )
(2.11)
.
rumus untuk hampiran ke-k pada metode iterasi Gauss-Seidel adalah sebagai berikut : ( )
( )
−∑
=
dengan syarat aii ≠ 0 dan k = 1, 2, ...
−∑
(
)
(2.12)
Metode iterasi Gauss-Seidel dapat dinyatakan dalam bentuk matriks. Nyatakan matriks koefisien A sebagai A = D + (L + U), dengan L dan U berturut-turut adalah matriks segitiga bawah dan atas dengan diagonal nol dan D matriks diagonal. Rumus iterasi Gauss-Seidel dapat ditulis dalam bentuk : X(k) = D-1(b-LX(k)-UX(k-1))
(2.13)
(D + L)X(k) = b – UX(k-1)
(2.14)
X(k) = (D + L)-1(b-UX(k-1)),
(2.15)
yang menghasilkan X(k) = - (D + L)-1UX(k-1) + (D + L)-1b.
(2.16)
Metode iterasi Gauss-Seidel hampir sama dengan metode iterasi Jacobi. Perbedaannya hanya terletak pada penggunaan nilai elemen vektor xbaru yang langsung digunakan pada persamaan di bawahnya. Untuk lebih jelasnya, perhatikan sistem persamaan linier berikut, yang diturunkan dari contoh terdahulu (
)
=
(
)
−
(
)
+
17
(
)
(
)
(
)
(
=
) (
=−
(
=−
+ )
)
(
) (
+
(
+
− )
)
+
(
) (
+
+ )
−
Pada baris pertama, x1baru dihitung berdasarkan x2lama dan x3lama. Kemudian x1baru tersebut langsung dipakai pada baris kedua untuk menghitung x2baru. Selanjutnya x1baru dan x2baru digunakan pada baris ketiga untuk mendapatkan x3baru. Begitu seterusnya hingga x4baru pun diperoleh pada baris keempat. Sistem persamaan tersebut dapat dinyatakan dalam indeks k seperti di bawah ini dimana k adalah jumlah iterasi. ( ) ( ) ( ) ( )
=
=
=− =−
(
)
( )
+
( ) ( )
− +
+
( (
) )
( ) ( )
+
−
+
+
(
)
(
)
+
−
Jika diberikan nilai-nilai awal x(0) adalah x1(0) = 0, x2(0) = 0, x3(0) = 0, dan x4(0) = 0, atau dinyatakan sebagai hampiran awal x(0) = (0;0;0;0)T, maka pada k = 1 akan memperoleh hampiran pertama sebagai berikut : ( ) ( ) ( ) ( )
= 0.6000 = 2.3272
= −0.9873 = 0.8789
18
Lalu proses perhitungan diulangi lagi dengan k = 2. Begitu seterusnya proses ini diulang-ulang lagi untuk nilai-nilai k berikutnya sampai x(k) mendekati solusi yang sesungguhnya, yaitu x = (1; 2; -1; 1)T Berikut adalah hasil proses iterasi dengan menggunakan MATLAB R2014a : n
x1
x2
x3
x4
Waktu (s)
err
1
0.6000
2.3273
-0.9873
0.8789
0.0011
2.7429
2
1.0302
2.0369
-1.0145
0.9843
0.0023
0.5303
3
1.0066
2.0036
-1.0025
0.9984
0.0033
0.0448
4
1.0009
2.0003
-1.0003
0.9998
0.0042
0.0071
5
1.0001
2.0000
-1.0000
1.0000
0.0052
8.7436e-04
Tabel 2 Hasil Iterasi Gauss-Seidel Setelah iterasi ke-5 diperoleh hampiran penyelesaian x = (1.0001; 2.0000; -1.0000; 1.0000)T bandingkan dengan penyelesaian eksaknya, yakni x = (1; 2; -1; 1)T (Sahid, 2007).
2.12 Stasioner Suatu iterasi matriks X(k) = MkX(k-1) + Ckb
(2.17)
dikatakan stasioner jika Mk dan Ck tidak tergantung pada k, sehingga iterasinya dapat ditulis dalam bentuk : X(k) = MX(k-1) + Cb Jelas bahwa metode iterasi Gauss-Seidel bersifat stasioner dengan M = - (D +L)-1U dan C = (D + L)-1 (Sahid, 2007).
(2.18)
19
2.13 Kekonvergenan Iterasi Matriks Penyelesaian SPL AX = b merupakan titik tetap iterasi matriks 2.17 ini artinya, X = A-1b dapat digunakan untuk mengganti masukan maupun keluaran pada persamaan 2.17, yakni : X = A-1b = MkA-1b + Ckb = MkX + Ckb.
(2.19)
Dari kesamaan ini didapatkan (2.20)
MkX = X – Ckb. Dimisalkan e(k) adalah galat hampiran ke-k. e(k) = X – X(k)
(2.21)
dengan menggunakan 2.17 dan 2.20 diperoleh : e(k) = X – (MkX(k-1) + Ckb) = MkX – MkX(k-1) = Mk(X – X(k-1)) = Mke(k-1). ⋮
= MkMk-1 ... M1e(0), dengan e(0) adalah galat hampiran awal. Untuk iterasi matriks stasioner (termasuk iterasi Gauss-Seidel) matriks galat hampiran ke-k adalah e(k) = M ke(0).
(2.22)
Dengan menggunakan sifat norm, didapat : |e(k)| ≤ || M k|.|e(0)||. Iterasi matriks (2.17) dikatakan konvergen jika lim
(2.23) →
( )
= . Dari
pertidaksamaan terakhir jelas bahwa hal ini akan dipenuhi jika ||M|| < 1 (Sahid, 2005).
20
2.14 M-File Sebagai Skrip Program Penulisan skrip rumus iterasi menggunakan M-File, deretan command dapat disimpan dalam bentuk skrip teks. Kapan pun dibutuhkan, skrips tersebut dapat dijalankan secara otomatis dengan cara mengetikan rumus output M-File dalam command window. Untuk menuliskan skrip rumus iterasi, dapat dimulai dengan membuka file baru. Caranya ialah melalui menu di main window dengan mengklik ikon new script yang terdapat pada jendela utama.
Gambar 1. Tampilan Awal MATLAB R2014a. Dengan editor ini, dapat membuka sejumlah M-File, melakukan editing, ataupun mencoba menjalankannya dan melakukan debuging (mencari kesalahan dalam skrip). Sementara itu untuk menyimpan M-File, dapat dilakukan dengan mengklik ikon save workspace pada menu. Teks yang diawali dengan “%” menunjukan komentar dan tidak akan dijalankan oleh MATLAB R2014a. Perhatikan bahwa :
21
Di dalam M-File, setiap command diakhiri dengan titik koma agar hasil perhitungan di tiap baris tidak ditampilkan di command window. Kecuali pada hasil perhitungan yang ingin ditampilkan, tidak diakhiri titik koma.
Variabel yang didefinisikan di dalam M-File akan disimpan oleh MATLAB R2014a ketika M-File telah dieksekusi atau dijalankan.
Di dalam editor, skrip yang dituliskan akan memiliki warna tertentu, yaitu :
Hijau untuk komentar.
Hitam untuk variabel dan comand.
Biru untuk statement pemrograman.
Sebagai skrip program, jika ingin mengubah atau mengatur parameter masukan program, maka harus dilakukan di dalam editor.
2.15 Variabel-Variabel yang Digunakan Abs
= menghitung nilai absolut.
Break
= keluar dari suatu loop.
Clc
= membersihkan tampilan command window.
Clear
= membersihkan variabel.
Eps
= bilangan yang sangat kecil mendekati nol yang merupakan batas akurasi perhitungan.
Length
= untuk mengetahui ukuran atau dimensi dari matriks.
Load
= mengeluarkan kembali pekerjaan dari dalam file.
N
= berisi bilangan asli yaitu {0, 1, 2, ...}.
Norm
= fungsi distribusi normal gaussian.
Operasi ( : )
= sampai dengan.
22
Operasi ( ; )
= perhitungan tetap dilakukan tanpa menuliskan hasilnya.
Operasi ( ‘ )
= operasi transposisi untuk matriks berisi bilangan riil atau transposisi dan konjugasi untuk matriks kompleks.
Operasi ( * ) = perkalian. Save
= menyimpan pekerjaan ke dalam file.
Tic toc
= menghitung waktu dari suatu operasi dalam second.
Zeros
= membuat matrik atau vektor nol (semua elemennya berisi angka nol) yang berukuran n x n.
2.16 Galat dalam Penyelesaian Sistem Persamaan Linier Perhitungan yang dilakukan dengan MATLAB khususnya MATLAB R2014a ini memiliki perhitungan yang mungkin hampir sama dengan penyelesaian eksak. Hal ini dikarenakan MATLAB menggunakan tingkat keakuratan dengan presisi ganda (sampai 15 atau 16 angka signifikan) dalam operasi-operasi aritmatika. MATLAB menggunakan besaran eps untuk menyatakan galat setiap bilangan yang dapat disajikan olehnya. Artinya, eps adalah harga mutlak penyelesaian terkecil dari relasi 1 +
≠ 1. Jadi untuk setiap perhitungan ̅ , galat relatifnya, | ̅ ⁄ |, tidak
akan pernah kurang daripada eps. Jelas bahwa proses penyelesaian suatu SPL akan menghasilkan akumulasi dari galat-galat minimum tersebut. Pembagian
dengan suatu bilangan yang sangat kecil, atau pengurangan dua buah bilangan yang hampir sama dapat menghasilkan efek penurunan tingkat keakuratan hasil secara dramatis. Konsep norm dan bilangan kondisi suatu matriks, merupakan alat yang berguna untuk mengestimasi akumulasi galat yang terjadi dalam penyelesaian SPL AX = b (Sahid, 2007).
23
2.17 Definisi Galat Misalkan ̅ adalah suatu nilai hampiran numerik untuk nilai numerik eksak x, yang tidak diketahui. Nilai
=
̅
− ̅
(2.24)
disebut galat, | ̅ | disebut galat mutlak, dan nilai ̅
=
|
̅|
(2.25)
asalkan x ≠ 0 disebut galat relatif. Oleh karena nilai x biasanya tidak diketahui, dalam perhitungan, penyebut pada galat relatif sering menggunakan nilai hampiran, yakni : ̅
dengan kata lain,
≈
| ̅
̅|
.
(2.26)
Nilai eksak = nilai hampiran + galat, dan
Nilai-nilai
∗ ̅
dan
∗ ̅
=
yang sudah diketahui, dan memenuhi | ̅| ≤
∗ ̅
dan
| ̅| ≤
.
∗ ̅,
Disebut berturut-turut batas galat mutlak dan batas galat relatif, dan jika x ≠ 0, hubungan keduanya didefinisikan sebagai : (Sahid, 2007). ∗ ̅
= | |.
2.18 Konsep Norm dan Bilangan Kondisi Suatu Matriks Dimulai dengan memisalkan
adalah hampiran penyelesaian atau hasil
perhitungan SPL AX = b dan x adalah penyelesaian eksaknya.
(2.27)
24
Galat hampiran
adalah =
− ̅
Selanjutnya definisikan =
−
Besaran ini disebut residu di dalam penghampiran b oleh = , maka r = 0. Oleh karena
= .
maka diperoleh hubungan Jadi galat
= ( − )=
−
. Jelaslah apabila =
−
= ,
memenuhi suatu SPL dengan matriks koefisien A, dan vektor residu,
r sebagai vektor konstanta (Sahid, 2007).
2.19 Ukuran Besar Vektor dan Matriks Ukuran besar (panjang) suatu vektor xn x 1 ditulis dengan notasi |x|, dan matriks An x n ditulis dengan ||A|| didefinisikan sebagai | |=
‖ ‖=
∑
| |,
(2.28) .
Teorema. Jika A matriks nonsingular, maka penyelesaian-penyelesaian Ax = b dan memenuhi ‖
Bukti :
| |
‖
≤ ‖ ‖. ‖
‖
Dengan mengurangkan kedua SPL Ax = b dan ( − )=
| |
=
−
.
(2.29)
diperoleh :
=
25
−
=
−
Dengan menggunakan sifat norm, dipenuhi hubungan : | − |≤
Pembagian dengan |x| menghasilkan ‖ − ‖ ‖ ≤ | |
( − ‖ − | |
≤‖ = ‖ ‖‖
. ‖.
− ‖
.
− . ‖ ‖| |
Mengingat ||A|| ≠ 0. Dari persamaan Ax = b diperoleh ||A||.|x| ≥ |b|, sehingga dengan memasukan pertidaksamaan ini ke dalam pertidaksamaan sebelumnya akan diperoleh hasil pada teorema di atas.
Hasil dari (2.28) memberikan hubungan antara galat relatif hampiran
.
Dari rumus tersebut terlihat bahwa, apabila nilai ||A||.||A-1|| sangat besar, maka galat relatif hampiran
menjadi sangat besar dari galat relatif
.
Bilangan =‖ ‖×‖
‖
(2.30)
Disebut bilangan kondisi matriks A. Jika nilai kondisi matriks A sangat besar, penyelesaian SPL Ax = b sangat sensitif terhadap perubahan kecil pada vektor b. Dengan kata lain, residu yang relatif kecil menghasilkan galat hampiran
yang
relatif besar. Sistem demikian dikatakan dalam kondisi sakit (ill-conditioned). Sistem yang memiliki matriks koefisien dengan bilangan kondisi kecil dikatakan dalam kondisi baik (well-conditioned) (Sahid, 2007).
26
2.20 Kekonvergenan Iterasi Jacobi dan Gauss-Seidel Teorema. Iterasi Jacobi dan Gauss-Seidel konvergen untuk setiap SPL yang memenuhi matriks koefisien bersifat dominan secara diagonal. Bukti : Pada persamaan (2.5) dan (2.18) terlihat bahwa iterasi matriks untuk mencari hampiran penyelesaian SPL Ax = b, dengan An x n dan bn x 1, dapat ditulis dalam bentuk X(k) = MX(k-1) + Cb =−
1.
Untuk iterasi Jacobi,
2.
Untuk iterasi Gauss-Seidel,
( + )
= −( + )
=
.
=( + ) .
Dengan A = L + D + U, L matriks segitiga bawah dari A, D matriks diagonal dari A, dan U matriks segitiga atas dari A. Dengan mendefinisikan e(k) sebagai galat hampiran ke-k, seperti persamaan (2.21) . selanjutnya hubungkan dengan persamaan (2.23). dan akhirnya diketahui bahwa syarat iterasi tersebut konvergen adalah ‖ ‖<1
Sekarang kekonvergenan kedua iterasi dapat ditinjau secara terpisah. Untuk iterasi Jacobi, =−
( + )
27
−1
⎛ ⎜ ⎜ 0 ⎜ =⎜ ⎜ 0 ⎜ ⎜ 0 ⎝
0
−1 0 0
0
⋯ 0
⎞ ⎟ 0 ⋯ 0⎟ 0 ⎟⎛ ⎟⎜ −1 ⋮ ⋯ 0⎟ ⎟ ⋮ ⋱ ⋮ ⎟⎝ −1 0 ⋯ ⎠
0
0
… … … ⋱ …
⎞ ⎟
⋮ 0 ⎠
Dari persamaan 2.27 diperoleh
‖ ‖=
,
Sehingga syarat ||M|| < 1 mengharuskan
,
<|
|,
,
1≤ ≤ ,
yang tidak lain adalah sifat dominan secara diagonal matriks A (Sahid, 2007).
III. METODOLOGI PENELITIAN
3.1 Waktu Penelitian Penelitian ini mulai dilakukan pada semester ganjil tahun ajaran 2016/2017 bertempat di Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung.
3.2 Metode Penelitian Pada penelitian ini metode yang digunakan adalah studi literatur dan penerapan simulasi komputasi MATLAB R2014a. Adapun algoritma dari masing-masing iterasi sebagai berikut :
3.2.1 Iterasi Jacobi Untuk menyelesaikan sistem persamaan linier AX = b dengan A adalah matriks koefisien n x n, b vektor konstanta n x 1, dan X vektor n x 1 yang perlu dicari. Input : X = (x1 x2 x3 ... xn)T atau pesan “gagal”. Langkah-langkah : 1) Set penghitung iterasi k = 1 2) WHILE k ≤ N DO a) FOR i = 1, 2, 3, ... , n, Hitung b) Set X = (x1 x2 x3 ... xn)T.
=
∑
.
29
c) IF ||X-Y|| < T THEN STOP. d) Tambah penghitung iterasi, k = k + 1. e) FOR i = 1, 2, 3, ..., n, Set yi = xi. f)
Set Y = (y1 y2 y3 ... yn)T.
3) Tulis pesan “Metode gagal setelah N iterasi”. 4) STOP. Berikut ini adalah diagram alir yang menjelaskan tentang iterasi Jacobi : Start
Input A Input b
For p = 1:n
U(p,1)=b(p,1)/A(p,p)
For k = 1:n
J(p,k)= -A(p,k)/A(p,p)
For k = 1:itermaks
Xbaru=J*xlama+u Xselisih=xbaru-xlama Err=norm(xselisih)
tic
Iterasi = o
If (err < epsilon)
Iterasi = iterasi + 1
end
Waktu = toc
STOP
Gambar 2. Flow Chart Metode Iterasi Jacobi.
30
3.2.2 Iterasi Gauss-Seidel Untuk menyelesaikan sistem persamaan linier AX = b dengan A adalah matriks koefisien n x n, b vektor konstanta n x 1, dan X vektor n x 1 yang perlu dicari. Input : n, A, b, dan hampiran awal Y = (y1 y2 y3 ...yn)T, batas toleransi T, dan maksimum iterasi N. Output : X = (x1 x2 x3 ... xn)T atau pesan “gagal”. Langkah-langkah : 1) Set penghitung iterasi k = 1. 2) WHILE k ≤ N DO : a) FOR i = 1, 2, 3, ..., n, Hitung b) Set X = (x1 x2 x3 ... xn)T.
=
∑
∑
.
c) IF ||X – Y|| < T THEN STOP. d) Tambah penghitung iterasi, k = k + 1. e) FOR i = 1, 2, 3, ..., n, Set yi = xi. f)
Set Y = (y1 y2 y3 ... yn)T.
3) Tulis Pesan “Metode gagal setelah N iterasi”. 4) STOP. Berikut ini adalah diagram alir yang menjelaskan tentang iterasi Gauss-Seidel :
31
Start
Input A Input b Input xlama
tic
For i = 1 : itermaks
1
−
( )
−
(
)
For i = 1 : n
S = s + (xbaru(i,1) – xlama(i,1))^2 Epsilon = sqrt(s)
If Epsilon < sc
break
Waktu = toc
STOP
Gambar 3. Flow Chart Metode Iterasi Gauss-Seidel.
V. SIMPULAN
Dari hasil pembahasan pada bab sebelumnya dapat disimpulkan bahwa : 1.
Pemrosesan hasil output iterasi Gauss-Seidel lebih sedikit dibandingkan iterasi Jacobi, karena terlihat jelas pada tabel 3 bahwa masing-masing matriks menunjukkan iterasi Gauss-Seidel lebih sedikit di bandingkan iterasi Jacobi.
2.
Waktu pemrosesan hasil output iterasi Jacobi lebih cepat dibandingkan iterasi Gauss-Seidel, karena terlihat jelas pada tabel 3 bahwa masing-masing matriks menunjukkan waktu pemrosesan hasil output iterasi Jacobi lebih cepat di bandingkan waktu pemrosesan iterasi Gauss-Seidel.
3.
Hasil output iterasi Jacobi lebih akurat dibandingkan iterasi Gauss-Seidel, karena jumlah iterasi Jacobi yang lebih banyak menyebabkan proses pengulangan dan hasil dari setiap iterasinya lebih jelas.
DAFTAR PUSTAKA
Anton, H. 1987. Aljabar Linier Elementer. Diterjemahkan oleh Pantur Silaban. Erlangga, Jakarta.
Gilbert, J. Dan Gilbert, L. 1995. Linier Algebra and Matrix Theory. University of South Carolina at Spartanburg, South Carolina.
Leon, S.J. 1998. Aljabar Linear dan Aplikasinya. Diterjemahkan oleh Alit Bondan. Erlangga, Jakarta.
Munir, R. 2008. Metode Numerik Revisi Kedua. Informatika Bandung, Bandung.
Sahid. 2005. Pengantar Komputasi Numerik dengan MATLAB. Andi, Yogyakarta.
Suparno, S. 2011. Komputasi untuk Sains dan Teknik Menggunakan Matlab. Depok, Universitas Indonesia.
