PENYELESAIAN SISTEM LINIER I. PENDAHULUAN 1.1. Topik-topik Yang Dibahas : 1.
Substitusi mundur (back substitution)
2.
Reduksi ganjil-genap (odd-even reduction) atau reduksi siklis (cyclic reduction)
1.2. Metoda Pembahasan 1.
Algoritma sequensial
2.
Potensi paralelisasi
3.
Algoritma paralel
4.
Speedup
1.3. Terminologi : i. Bentuk umum sistem linier : A matriks n × n,
A x = b,
x, b vektor n × 1
ii. Elemen matriks A baris ke-i kolom ke-j : Elemen vektor x baris ke- i :
xi
atau x[i]
Elemen vektor b baris ke- i :
bi
atau b[i]
a ij
atau a[i, j]
iii. Matriks A adalah segitiga atas (upper triangular) jika :
a ij
iv. Matriks A adalah segitiga bawah (lower triangular) jika :
=0∀i>j
a ij
=0∀i<j
v. Matriks A adalah tridiagonal jika dan hanya jika :
a ij
= 0 ∀ ⎪ i − j⎪ > 1
vi. Matriks A adalah diagonal dominan (diagonally dominant) jika : ⎪ a ii ⎪ > ∑ |a | ∀ 1 ≤ i ≤ n i ≠ j ij vii. Matriks A adalah simetri (symmetric) jika :
a ij
=
a ji
∀ 1 ≤ i, j ≤ n
viii.Matriks A adalah definit positif (positive definite) jika ia simetri, diagonal dominan, dan
a ii
>0∀1≤i≤n
ix. Berikut ini adalah contoh matriks-matriks di atas :
APP - Penyelesaian Sistem Linier
1/5
⎡1 ⎢ ⎢0 ⎢ ⎢0 ⎣
2 3⎤
⎡1 ⎥ ⎢ 5⎥ = ⎢ ⎥ ⎢ 6⎥⎦ ⎢⎣
2 3⎤
4 0
4
⎡1 ⎢ ⎢2 ⎢ ⎢4 ⎣
⎥ 5⎥ ⎥ 6⎥⎦
Matriks segitiga atas ⎡1 ⎢ ⎢3 ⎢ ⎢0 ⎣
2 0⎤
2
4 6
4 6
⎡1 ⎥ ⎢ 5⎥ = ⎢3 ⎥ ⎢ 7⎥⎦ ⎢⎣
3 5
⎡− 5 ⎢ ⎢ 3 ⎢ ⎢⎣ − 1
⎤ ⎥ 5⎥ ⎥ 7⎥⎦
3 5
⎤ ⎥ ⎥ ⎥ 6⎥⎦
2 1⎤ ⎥
9 4⎥ ⎥ 0 6⎥⎦
Matriks diagonal dominan ⎡8 ⎢ ⎢2 ⎢ ⎢3 ⎣
2 3⎤ 4 5
⎡1 ⎥ ⎢ 0⎥ = ⎢2 ⎥ ⎢ 6⎥⎦ ⎢⎣4
Matriks segitiga bawah
Matriks tridiagonal ⎡1 ⎢ ⎢2 ⎢ ⎢⎣ 3
0 0⎤
⎥ 5⎥ ⎥ 6⎥⎦
Matriks simetri
3⎤
2
⎥
9 5⎥ ⎥ 5 10⎥⎦
Matriks definit positif
II. SUBSTITUSI MUNDUR 2.1. Algoritma Sequensial Contoh 9.1 Selesaikan sistem persamaan berikut : 1x
1
+1x
2
−1x
3
+ 4x
= 8
4
−2x −1x + 1x 4 2 3 −3x 2x 4 3 2x 4
= 5 = 0 = 4
Jawab : Vektor x = [ x 1. hitung :
1
x4
x2 x 3 x4 ]T
diperoleh melalui prosedur berikut :
= 4/2 = 2
2. substitusikan nilai
x4
ke semua persamaan di atasnya, koreksi ruas kanannya
persamaan; hasilnya adalah :
APP - Penyelesaian Sistem Linier
1x
1
+1x
2
−1x
3
=0
−2 x
2
−1x
3
=3
2x
3
=6 2/5
3. ulangi langkah (1) dan (2) berturut-turut untuk 4. ulangi langkah (1) untuk
x3
dan
x2
x1
Dengan cara ini maka diperoleh : x=[x
1
x2 x 3 x4 ]T
= [9 -6 3 2] T
Sistem di atas dapat dituliskan sebagai A x = b, dimana :
⎡1 ⎢ ⎢ A= ⎢ ⎢ ⎢ ⎢ ⎣
1
−1
−2 −3 2
⎤ ⎥ 1⎥ ⎥ = matriks segitiga atas, b = − 3⎥ ⎥ 2 ⎥⎦
4
⎡8⎤ ⎢ ⎥ ⎢5⎥ ⎢ ⎥ ⎢0⎥ ⎢ ⎥ ⎢4⎥ ⎣ ⎦
Untuk sistem segitiga atas berukuran n prosedur di atas dapat digeneralisasi menjadi algoritma sekuensial berikut : Algoritma 9.1. BACK.SUBSTITUTION (SISD) : Global n {ukuran sistem} a[1.. n][ 1.. n] {elemen-elemen matriks A} b[1.. n] {elemen-elemen vektor b} x[1.. n] {elemen-elemen vektor x} i {indeks kolom} j {indeks baris} 1. begin 2. for i ← n downto 1 do x[i] ← b[i]/a[i][i] 3. 4. for j ← 1 to i −1 do 5. b[j] ← b[j] − x[i] × a[j][i] 6. a[j][i] ← 0 {statement ini bersifat opsional} 7. endfor 8. endfor 9. end Algoritma 9.1. melakukan operasi pembagian, perkalian, dan pengurangan. Banyaknya operasi pembagian adalah n (baris 3) sedangkan banyaknya operasi pengurangan dan perkalian (baris 5) adalah : (n −1) + (n −2) + ... + 2 + 1 = ½ n(n −1)
(9.1)
sehingga kompleksitas algoritma 9.1. adalah Θ(n 2 ).
Instruksi pada baris 6 bersifat opsional, di antaranya untuk menayangkan matriks pada setiap iterasi.
APP - Penyelesaian Sistem Linier
3/5
2.2. Potensi Paralelisasi
Proses substitusi nilai
x4
ke tiga persamaan di atasnya pada penyelesaian contoh 9.1 di atas
dapat dilakukan secara serempak.
2.3. Algoritma Paralel
Berdasarkan potensi paralelisasi maka algoritma paralel dapat disusun sebagai berikut : Algoritma 9.2. BACK.SUBSTITUTION (UMA MULTIPROSESOR) : Global n {ukuran sistem} p {banyaknya proses} a[1.. n][ 1.. n] {elemen-elemen matriks A} b[1.. n] {elemen-elemen vektor b} x[1.. n] {elemen-elemen vektor x} i {indeks kolom} j {indeks indetifier proses} Lokal k {indeks baris} 1. begin 2. for i ← n downto 1 do 3. x[i]← b[i]/ a[i][i] 4. forall P[j] where 1 ≤ j ≤ p do 5. for k ← j to i −1 step p do 6. b[k]← b[k] − x[i] × a[k][i] 7. a[k][i] ← 0 {statement ini bersifat opsional} endfor 8. endforall 9. 10. endfor 11. end
Algoritma 9.2. melakukan n operasi pembagian. Banyak-nya operasi pengurangan dan perkalian adalah : ⎡(n−1)/p⎤ + ⎡(n−2)/p⎤ + ... + ⎡2/p⎤ + ⎡1/p⎤ =
1
2
⎡n(n-1)/p⎤ (9.2)
sehingga kompleksitas algoritma 9.2. adalah Θ(n 2 / p). Berikut ini adalah tracing penerapan algoritma 9.2. terhadap sistem persamaan pada contoh 9.1. untuk p = 2 :
i = 4 : x[4] = b[4]/a[4][4] = 4/2 = 2
∴ x[4] = 2
P[1] : k = 1 : b[1] = b[1] - x[4] × a[1][4] = 8 - 2 × 4 = 0 a[1][4] = 0 k = 3 : b[3] = b[3] - x[4] × a[3][4] = 0 - 2 × (-3) = 6 a[3][4] = 0
APP - Penyelesaian Sistem Linier
4/5
P[2] : k = 2 : b[2] = b[2] - x[4] × a[2][4] = 5 - 2 × 1 = 3 a[2][4] = 0
∴ x[3] = 3
i = 3 : x[3] = b[3]/a[3][3] = 6/2 = 3
P[1] : k = 1 : b[1] = b[1] - x[3] × a[1][3] = 0 - 3 × (-1) = 3 a[1][3] = 0 P[2] : k = 2 : b[2] = b[2] - x[3] × a[2][3] = 3 - 3 × (-3) = 12 a[2][3] = 0
∴ x[2] = -6
i = 2 : x[2] = b[2]/a[2][2] = 12/(-2) = -6
P[1] : k = 1 : b[1] = b[1] - x[2] × a[1][2] = 3 - (-6) × 1 = 9 a[1][2] = 0
∴ x[1] = 9
i = 1 : x[1] = b[1]/a[1][1] = 9/(1) = 9
2.4. Speedup Speedup algoritma 9.2. ini adalah : S=
n+n(n−1)/2 , n+ ⎡n(n−1)/2 p ⎤
lim n→∞
S =p
(9.3)
Menurut Amhdal, untuk jumlah prosesor tertentu nilai S akan meningkat menurut kenaikan ukuran matriks n. Gambar berikut adalah data akibat fenomena ini.
8 7 6 5 4 3 2 1 0 0
1
2
3
4
5
6
7
8
Gambar 9.1. Speedup paralelisasi algoritma substitusi mundur untuk berbagai ukuran matriks tridiagonal. APP - Penyelesaian Sistem Linier
5/5
