II.
2.1
TEORI DASAR
Persamaan dan Pertidaksamaan
Persamaan didefinisikan sebagai suatu pernyataan matematika dalam bentuk simbol yang menyatakan bahwa dua hal adalah persis sama. Dimana persamaanya ditulis dengan tanda sama dengan. Misalnya :
2 35 ( x 1) x x 2 x 2x 3y 8 Pertidaksamaan didefinisikan sebagai kalimat matematika yang menunjukkan perbandingan ukuran dua objek atau lebih. Dimana persamaan menggunakan 2 tanda dasar yaitu kurang dari (<) dan tanda lebih dari (>). Misalnya :
2 1 5 x2 x 4 0 2x 3y 8 (Wikipedia, 16 Januari 2010).
6
Definisi 2.1.1 Persamaan Linear Persmaan linear dengan n varibel x , x , x x sebagai pesamaan yang 1
2
3
n
dapat dinyatakan dalam bentuk a x a x a x a x b 1
1
2
2
3
3
n
n
Dimana a1, a2, a3,.....an dan b merupakan konstanta real. Variabel-variabel dalam persamaan linier seringkali disebut sebagai faktor yang tidak diketahui (Anton-Rorres, 2004) .
2.2
Sistem Persamaan Linear
Sistem persamaan linear atau disebut juga sebagai sistem linear merupakan persamaan linear dengan jumlah tertentu dalam variabel x , x , x x 1
2
3
n
(Anton-Rorres, ). Dimana sistem persamaan linear dengan n-variabel dinyatakan sebagai :
a11 x1 a12 x 2 a13 x3 a1n x n b1 a 21 x1 a 22 x 2 a 23 x3 a 2 n x n b2 a31 x1 a32 x 2 a33 x3 a3n x n b3 a n1 x1 a n 2 x 2 a n 3 x3 a nn x n bn (Munir, 2006) .
7
2.3
Matriks Persegi
Matriks persegi yaitu himpunan unsur-unsur yang disusun berdasarkan penggolongan terhadap dua sifat yang disebut sebagai baris dan lajur (kolom) yang sama atau dilambangkan dengan M nxn . Suatu matrik juga merupakan himpunan beberapa vektor baris atau vektor kolom. Suatu matriks ditulis dengan menggunakan tanda kurung siku dan disimbolkan dengan huruf besar abjad Latin.
Anxn
a11 a12 a 21 a 22 a31 a32 a n1 a n 2
a13 a1n a23 a2n a33 a n3 a nn
baris
kolom
Penulisan matriks persegi dapat disederhanakan yaitu A (aij ) nxn
nn
(Triatmojo, 1992)
Definisi 2.3.1 Matriks Segitiga Atas Suatu matriks persegi n x n dikatakan matriks segi tiga atas (uppertriangular) U (u ij ) jika unsur pada u ij 0 untuk i j 1, j 2, .....n
8
Contoh matriks segitiga atas : 1 0 A 0 0
3 2 0 0
5 0 3 0
7 6 6 9
(Nasution, 1980).
Definisi 2.3.2 Matriks Segitiga Bawah Suatu matriks persegi n x n dikatakan matriks segitiga bawah (lowertriangular) L (l ij ) jika unsur pada l ij 0 untuk i 1,.2, 3 j 1 Contoh matriks segitiga bawah :
1 2 A 0 3
0 4 3 7
0 0 5 8
0 0 0 3
(Nasution, 1980 ).
Definisi 2.3.3 Matriks Diagonal Suatu matriks persegi n x n dikatakan matriks diagonal D (d ij ) dimana d ij 0 untuk i j , tau dapat dinyatakan dengan skema berikut :
d ij
0 min imal satu unsur 0
jika i j jika i j
9
Bentuk umum matriks diagonal :
d11 0 A 0 0
0 0 0 d 22 0 0 0 0 0 0 d nn
(Burden, 1997).
Definisi 2.3.4 Matriks Tridiagonal Matriks tridiagonal yaitu sutu matriks bujursangkar yang memiliki 3 jalur diagonal. Bentuk umum : a22 a12 a a 21 22 0 a32 A 0 0 0 0
0 0 0 a23 0 0 a33 a34 0 a n 1n 2 a n 1n 1 a n 1n 0 ann 1 ann
(Triatmojo, 1992).
Definisi 2.3.5 Matriks Jarang Suatu matriks persegi n x n dikatakan matriks jarang jika elemen-elemennya didominasi oleh elemen nol.
10
Contoh matriks jarang : 1 0 A 0 2 0
0 3 0 0 1
0 1 0 0 2 1 5 0 0 0 4 0 0 0 2
(Conte & Boor, 1993).
Definisi 2.3.6 Minor Matriks Persegi Jika A adalah matriks bujur sangkar, maka minor dari A dinyatakan sebagai M ij dan didefinisikan sebagai determinan dari submatriks yang tersisa
setelah baris ke-i dan kolom ke-j dihilangkan dari A. Bilangan (1) i j M ij dinyatakan sebagai C ij dan disebut sebagai kofaktor dari entri a ij . Misalkan pada :
A3 x 3
a11 a 21 a31
a12 a 22 a32
a13 a 23 a33
Maka matriks minornya adalah :
a M 11 22 a32
(Anton-Rorres, 2004)
a23 a33
a M 12 21 a31
a23 a M 13 21 a33 a31
a22 a32
11
Definisi 2.3.7 Kofaktor Matriks Persegi Dengan menggunakan aturan papan catur maka akan diperoleh
Cij (1) i j M ij sebagai berikut :
maka diperoleh : C11 M 11 C12 M 12 C13 M 13 C14 M 14 Misalkan pada :
A3 x 3
a11 a 21 a31
a12 a 22 a32
a13 a 23 a33
Maka matriks kofaktornya adalah :
a23 a C11 22 a32 a33
a a a a C12 21 23 C13 21 22 a31 a33 a31 a32
(Anton-Rorres, 2004)
Definisi 2.3.8 Determinan Matriks Determinan matriks persegi n x n didefinisikan sebagai berikut : 1. Jika A a adalah matriks yang berukuran 1 x 1 maka det A a . 2. Jika A adalah matriks berukuran n x n, dengan matriks minor Mij adalah determinan matriks berukuran (n-1) x (n-1) yang merupakan submatrik A yang diperleh dengan menghapus baris ke-i dan kolom ke-j .
12
3. Kofaktor Aij merupakan persekutuan dari Mij yang didefinisikan dengan
Aij (1) i j M ij . 4. Determinan dari matriks A yang berukuran n x n dimana n>1 dinyatakan dengan n
det A aij Aij j 1
n
(1) i j aij M ij j 1
Untuk i=1, 2, 3 ....n (Burden, 1997).
Jika sebarang matriks A aij berukuran n x n , maka determinan dari A adalah sebagai berikut :
a11 a 21 det( A) a31 a n1
a12 a 22 a32 an2
a13 a 23 a33 an3
a1n a 2 n a3n a nn
a11C11 a120 C12 a13 C13 a1n C1n Misal :
a11 det( A) a 21 a31 a11
a 22 a32
a12 a 22 a32
a13 a 23 a33
a 23 a a12 21 a33 a31
a 23 a a13 21 a33 a31
a 22 a32
a11 (a 22 a33 a32 a 23 ) a 23 (a 21 a33 a31 a 23 ) a13 (a 21 a32 a31 a 22 )
(Anton-Rorres, 2004)
13
Misalkan A merupakan sebuah matriks persegi berukuran n x n maka berlaku : 1. Jika terdapat baris atau kolom yang semua unsurnya adalah nol maka
det A 0 . ~
2. Jika A adalah matriks yang diperoleh dengan menukar baris atau kolom ~
matriks A ( Ei E j ) dengan i j , maka det A det A . 3. Jika A memiliki dua baris atau kolom yang sama atau sebanding, maka det A = 0. ~
4. Jika A adalah matriks yang diperoleh dengan mengalikan salah satu ~
baris dengan konstanta yaitu (Ei Ei ) , maka det A det A . ~
5. Jika A adalah matriks yang diperoleh dengan cara menembakan kolom atau baris dengan kolom atau baris yang lain yaitu Ei E i E j maka determinannya sama. (Burden, 1997)
Definisi 2.3.9 Matriks Dominan Diagonal Suatu matriks persegi A yang berukuran n x n dikatakan dominan diagonal jika : n
a ii aij j 1 j i
untuk i = 1, 2, 3, ...n
14
Contoh matriks dominan diagonal :
7 2 0 A 3 5 1 0 5 6
Karena :
720 5 3 1 6 0 5
(Gerald & Wheatley, 1997)
Definisi 2.3.10 Invers Matriks Apabila A didefinisikan sebagai matriks maka matriks inversnya adalah A-1, sedemikian sehingga : A 1
1 Adjoin( A) det A
Invers matriks diagonal dituliskan dengan : D 1 aii1
atau
D 1 d i1
Bentuk umum :
d1 0 D 0 0
0 d2 0 0
0 0 d3 0
0 0 0 maka D 1 d n
0 1 / d1 0 0 1/ d 0 2 0 0 1/ d3 0 0 0
0 0 0 1 / d n
15
Berlaku jika dan hanya jika semua entri pada diagonalnya merupakan bilangan tak nol. (Triatmojo, 1992).
Definisi 2.3.11 Nilai Eigen Suatu sekalar yang dilambangkan dengan yang merupakan nilai karakteristik dari suatu matriks dimana nilai ini yang menentukan suatu matriks memiliki solusi yang nontrivial (solusi selain nol) Persamaan karakteristik didefinisikan sebagai :
det (I A) 0 Dan kita dapat mencari nilai dari persamaan ini. (Anton-Rorres, 2004 ) .
Definisi 2.3.12 Jari-jari Spectral Jari-jari spectral (A) dari suatu matriks A didefinisikan dengan :
( A) max , dimana adalah nilai eigen dari A. (Untuk nilai eigen berupa bilangan kompleks i maka kita memiliki
( 2 2 )1/ 2 )
2.4
(Burden, 1997).
Sistem Persamaan dalam Bentuk Matriks
Sistem persamaan linear (SPL) dapat ditulis dalam bentuk mariks yaitu : Misal terdapat SPL
16
a11 x1 a12 x2 a13 x3 a1n xn b1 a21 x1 a22 x2 a23 x3 a2 n xn b2 a31 x1 a32 x2 a33 x3 a3 n xn b3 an1 x1 an 2 x2 an 3 x3 ann xn bn
Maka sistem persamaan di atas dapat ditulis dalam bentuk :
a11 a 21 a31 a n1
a12 a 22 a32 an2
a13 a1n x1 b1 a 23 a 2 n x 2 b1 a33 a3n x3 b3 a n 3 a nn x n bn
Atau
Ax b Dimana : A : Matriks koefisien nxn x : vektor kolom nx1 variable B : vektor kolom nx1 dari kostanta (Triatmojo, 1992)
Jika A adalah sebuah matriks berukuran n x n maka pernyataan beikut ekuivalen : 1. Persamaan Ax 0 memiliki solusi tunggal x = 0
17
2. Suatu sistem persamaan Ax 0 memiliki solusi tunggal untuk vektor kolom b berdimensi n. 3. Matriks A dikatakan matriks nonsingular jika A-1 ada dan det A 0 .
Suatu matriks koefisien
a11 a12 a 21 a 22 A a31 a32 a n1 a n 2
a13 a1n a 23 a 2 n a33 a3n a n3 a nn
dapat diubah menjadi : a11 a 21 A a31 an1
a12 a13 a1n a22 a23 a2 n a32 a33 a3n an 2 an3 ann 0 a1n 0 a 0 a2 n 21 0 an 1 n an 11 an 1 2 0 an1 an 2
a11 0 0 0
0 a22 0 0
0 0 a33 0
0 0 0 0 0 0 ann 0
a11 0 0 0
0 a22 0 0
0 0 a33 0
0 0 a12 a13 0 0 0 a23 0 0 0 0 ann 0 0 0
D L U
(Faires-Burden, 1998).
a12 0 0 0
a13 a23 0 0
0 0 0 an n 1
0 a1n 0 a 0 a2 n 21 0 an 1 n an 11 an 1 2 0 an1 an 2
0 0 0 0 0 0 0 an n 1
0 0 0 0
18
2.5
Metode Iterative
Metode iterative merupakan teknik penghitungan secara numerik untuk menyelesaikan suatu sistem persamaan linear n x n yang dinyatakan dengan
Ax b . Pada metode iterative ini, proses dimulai dari sebarang nilai awal
x(o) yang dipenuhi dengan X ( k )
k 1
yang akan konvergen ke suatu nilai x.
Metode iterative menggunakan proses konvers sistem Ax b ke dalam sistem yang ekuivalen x Tx c dengan T adalah suatu matriks berukuran n x n dan c merupakan suatu vektor solusi. Setelah itu nilai awal x(o) yang dipilih disubstitusikan ke dalam persamaan iterative x ( k ) Tx ( k 1) c
Untuk k= 1, 2, 3, ... Dan dilakukan berulang-ulang sampai mendapat hasil yang konvergen ( Faires - Burden, 1998).
a. Metode Jacobi
Metode Jacobi merupakan salah satu metode iterative dimana pada proses iterasinya menggunakan algoritma yang sangat sederhana. Pada iterasi Jacobi, unsur- unsur dari x(m) hanya digunakan dalam perhitungan dari iterasi berikutnya (Conte & Boor, 1993).
19
Misal diberikan suatu sistem persamaan linear :
a11 x1 a12 x 2 a13 x3 a1n x n b1 a 21 x1 a 22 x 2 a 23 x3 a 2 n x n b2 a31 x1 a32 x 2 a33 x3 a3n x n b3 a n1 x1 a n 2 x 2 a n3 x3 a nn x n bn Dan diberikan nilai awal x
x1(0) , x2(0) ,, xn(0)
( 0)
Maka konsideran yang dapat dibentuk dengan metode Jacobi adalah : x1
( k 1)
( k 1)
x2
b1 (a12 x 2
(k )
b2 (a 21 x1
(k )
a13 x3 a11
(k )
a 23 x3 a 22
(k )
a1n x n
(k )
a2n xn
)
(k )
)
x n( k 1)
bn (a n1 x1
(k )
an 2 x2 a nn
(k )
a nn x n
(k )
)
Dengan k= 0, 1, 2, 3.... Atau dapat disingkat dengan : n
xi
( k 1)
n
bi aij x j aii xi i 1 j 1
aii
(Munir, 2006). Metode Jacobi juga sama artinya dengan metode iterasi titik tetap dimana untuk suatu sistem persamaan dapat dibentuk suatu konsideran dalam bentuk
xi(i1) G( x (i) ) b' Bx(i)
dimana i = 1, 2, 3, ....n
20
Yang identik dengan bentuk iterasi titik tetap xi 1 g ( i )
Dengan menggunakan definisi A D L U
Maka sistem persamaan linear Ax b dapat dinyatakan dengan : Ax ( D L U ) x b Dx ( L U ) x b D 1 Dx D 1 (( L U ) x b) x
D 1 ( L U ) x D 1b
Dari bentuk di atas maka proses itersi Jacobi dapat dinyatakan dengan x (i 1) D 1 ( L U ) x (i ) D 1b
(Gerald & Wheatley, 1997)
b. Metode Gauss-Seidel
Jika diketahui sistem persamaan linier Ax b berordo n dengan matriks koofisien A (aij ) mempunyai elemen-elemen diagonal yang semuanya tidak nol, maka berlaku algoritma Gauss-Seidel sebagai berikut : n
xi( k 1)
bi aij x (jk 1) j 1
aii
n
a x
j i 1
ij
(k ) j
21
Atau dalam matriks formulasi ( L D) x Ux b ( L D) 1 ( L D) x ( L D) 1Ux ( L U ) 1 b x ( L D) 1Ux ( L D) 1 b
Dalam bentuk iterasi dapat di tulis : x (i 1) ( L D) 1Ux (i ) ( L D) 1 b
Misal diberikan sistem persamaan linear sebagai berikut :
3x1 x2 x3 1 2 x1 4 x2 x3 5 x1 5 x2 8 x3 5 Maka konsideran Gauss-Seidel adalah sebagai berikut : 1) iterasi -1
x1(1) 1 x2
(0)
x3( 0 )
x2(1) 5 2 x1(1) x3( 0 ) x3(1) 5 x1(1) 5 x2(1)
2) iterasi-2
x1( 2 ) 1 x2 x3(1) (1)
x2( 2 ) 5 2 x1( 2 ) x3(1) x3( 2 ) 5 x1( 2 ) 5 x2( 2 ) Sampai iterasi konvergen (Conte & Boor, 1993).
22
c. Metode SOR (Successive Over-Relaxation)
Metode SOR merupakan metode iterative yang merupakan metode yang dikembangkan menggunakan prinsip kerja yang sama dengan metode Jacobi dan Metode Gauss-Seidel. Dimana pada Metode SOR menggunkan iterasi sebagai berikut : i 1
aii xi( k ) aij x (jk ) (1 )aii xi( k 1) j 1
n
aij x (jk 1) bi
j i 1 i 1
(1 )aii xi( k 1) aij x (jk ) j 1
xi( k )
xi( k )
(1 ) xi( k 1)
n
aij x (jk 1) bi
j i 1
aii
aii
i 1
( aij x (jk ) j 1
n
aij x (jk 1) bi )
j i 1
Dengan k = 1, 2, 3, .... dimana 1 Atau dapat dinyatakan dalam bentuk vektor :
( D L) x ( k ) (1 ) D U x ( k 1) b x ( k ) ( D L) 1 (1 ) D U x ( k 1) ( D L) 1 b Atau dapat ditulis : x ( k ) T x ( k 1) c
Dimana : T
= ( D L)1(1 ) D U
c
= ( D L) 1b
= faktor skalar
23
Contoh iterasi dengan metode SOR : Misal diberikan sistem persamaan linear dengan memisalkan 1,2 sebagai berikut :
3x1 x2 x3 1 2 x1 4 x2 x3 5 x1 5 x2 8 x3 5 Maka, 1).
Iterasi-1
x1(1) (1 1,2) x1( 0) (1,2)(1 x2
(0)
x3( 0) )
x 2(1) (1 1,2) x 2( 0) (1,2)(5 2 x1(1) x3( 0) ) x3(1) (1 1,2) x3( 0) (1,2)(5 x1(1) 5 x 2(1) )
2)
Iterasi-2
x1( 2) (1 1,2) x1(1) (1,2)(1 x 2
(1)
x3(1) )
x 2( 2) (1 1,2) x 2(1) (1,2)(5 2 x1( 2) x3(1) ) x3( 2) (1 1,2) x3(1) (1,2)(5 x1( 2) 5 x 2( 2) ) Sampai iterasi konvergen (Faires-Burden, 1998) .
2.6
Tata Ancang Pivoting
Ada dua macam tata ancang pivoting yaitu : 1.
Pivoting Sebagian (partial pivoting)
24
Pada tata ancang pivoting sebagian, pivot dipilih dari semua elemen pada kolom p yang memiliki nilai mutlak nterbesar.
2.
Pivoting Lengkap Pada tata ancang pivoting lengkap baris juga diikut sertakan dalam pencarian elemen terbesar kemudian dipertukarkan . pada tata ancang pivoting lengkap, pivot dipilih dari semua elemen baris dan kolom dimana nilai diagonal harus memiliki mutlak terbesar dari mutlak jumlah elemen barisnya (Munir, 2006).
2.7
Galat/Error ( )
Penyelesaian numerik dari suatu persamaan matematika hanya memberikan nilai perkiraan yang mendekati nilai eksak dari sustu penyelesaian analitik. Hal ini akan menyebabkan adanya selisih antara nilai dari penyelesaian analitik dengan nilai dalam penyelesaian secara numerik yang biasa disebut sebagai galat (error). Error yang dihasilaknan dari sustu penyelesaian secara numerik dapat disebabkan karena beberapa hal yaitu : 1. Kesalahan Bawaan Adalah kesalahan dari nilai data yang biasanya disebabkan karena kesalahan penyalinan data , salah dalam membaca skala, atau kurangnya pengetian dalam mengenal hukum-hukum fisika (terutama dalam masalah pengukuran).
25
2. Kesalahan Pembulatan Adalah kesalahan yang terjadi karena tidak diperhitungkanya beberapa angka terakhir dari suatu bilangan. Hal ini terjadi apabila bilangan perkiraan digunakan untuk menggantikan bilangan eksak.
Contoh : 8632574
dapat dibulatkan menjadi 8633000
3.1415926 dapat dibulatkan menjadi 3.14
3. Kesalahan Pemotongan Yaitu kesalahan yang terjadi akibat tidak dilakukannya perhitungan sesuai dengan prosedur matematika yang benar. Misalnya pada suatu proses perhitungan tak hingga yang diganti dengan proses terhingga. Contoh :
e x 1 x
x 2 x3 x 4 2! 3! 4!
Nilai eksak diperoleh apabila semua suku diperhitungkan namun dalam prakteknya sangat sulit memperhitungkan bilangan tak hingga. (Triatmojo,2002)
Terdapat 2 jenis kesalahan (error) yaitu : 1.
Kesahan Absolut (absoluth error) Didefinisikan sebagai berikut : abs nilai perkiraan nilai eksak
26
2.
Kesalahan Relatif Didefinisikan sebagai berikut :
rel
nilai perkiraan nilai eksak nilai eksak
Dengan presentase kesalahan yaitu :
prc abs / rel x 100% (Purcell & Verberg, 1998)
Namun pada pendekatan numerik secara ietratif, perkiraan sekarang berdasar pada perkiraan sebelumnya. Maka error merupakan selisih antara perkiraan sebelumnya dan perkiraan sekarang sehingga error relatif yang digunakan didefinisikan sebagai berikut :
rel
Pn 1 Pn x100% Pn 1
Dengan : Pn 1 : perkiraan dari iterasi ke n 1 Pn : perkiraan dari iterasi ke n (Munir, 2006)
2.8
Syarat Konvergensi Metode Iterative
1. Kovergensi Metode Jacobi
Iterasi Metode Jacobi akan konvergen ke suatu nilai x jika memenuhi karakteristik berikut : a. Koefisien A adalah matriks nonsingular
27
b. Diagonalnya tidak ada unsur nol, atau aii 0 c. Matriks koefisien sistem persamaan linearnya dominan diagonal Suatu matriks dikatakan dominan diagonal (baris) jika : n
d1 aij j 1 j i
d.
Iterasi dikatakan konvergen pada suatu nilai x jika x ( k ) x ( k 1) x (k )
2. Konvergensi Metode Gauss-Seidel
a. Metode Gauss-Seidel konvergen jika sistem persamaan linear konvergen pada Metode Jacobi b. Jika radius spektral (T ) 1
Teorema 1 : Untuk sebarang nilai awal x ( 0) R n pada x ( k ) k 0
Didefinisikan dengan x ( k ) T ( k 1) c
untuk k 1
akan konvergen pada solusi tunggal jika dan hanya jika (T ) 1 .
Bukti : Diasumsikan bahwa (T ) 1
28
x ( k ) Tx ( k 1) c T (Tx ( k 1) c) c T (T (Tx ( k 1) c) c) c T k x ( 0) (T ( k 1) T 1)c
Selama (T ) 1 matriks T konvergen dan l im T k x (0) 0 k
3. Konvergensi Metode SOR
a. Metode SOR akan konvergen jika sistem persamaan linear(SPL) konvergen pada metode Jacobi dan metode Gauss-Seidel b. Jika matriks koefisien memenuhi aii 0 untuk i=1, 2, 3, ...n dan (T ) 1 maka SPL akan konvergen untuk 0 2 .
c. Jika A adalah matriks koefisien yang definit positif dan 0 2 maka metode SOR akan konvergen untuk berapapun nilai awal x(0). d. Jika A adalah matrik koefisien yang definit positif dan merupakan matriks tridiagonal maka (T )2 1 maka optimal yang dapat dipilih agar iterasi konvergen yaitu :
(Burden, 1997).
2
1 1 (T j )
2
