APP - Penyelesaian Sistem Linier 1/5

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 x = b, A matriks n × n, x, b vektor n × 1

ii. Elemen matriks A baris ke-i kolom ke-j : a ij atau a[i, j]

Elemen vektor x baris ke- i : x i atau x[i]

Elemen vektor b baris ke- i : bi atau b[i]

iii. Matriks A adalah segitiga atas (upper triangular) jika : a ij = 0 ∀ i > j

iv. Matriks A adalah segitiga bawah (lower triangular) jika : 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 iji j≠∑ ∀ 1 ≤ i ≤ n

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 2/5

1 2 30 4 50 0 6

1 2 34 5

6

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

= 1 0 02 3 04 5 6

12 34 5 6

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

=

Matriks segitiga atas Matriks segitiga bawah

1 2 03 4 50 6 7

1 23 4 5

6 7

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

= −

−

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

5 2 13 9 41 0 6

Matriks tridiagonal Matriks diagonal dominan

1 2 32 4 53 5 6

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

8 2 32 9 53 5 10

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

Matriks simetri Matriks definit positif

II. SUBSTITUSI MUNDUR

2.1. Algoritma Sequensial

Contoh 9.1

Selesaikan sistem persamaan berikut :

1 x1 + 1 x 2 − 1 x 3 + 4 x 4 = 8

− 2 x 2 − 1 x 3 + 1 x 4 = 5

2 x 3 − 3 x 4 = 0

2 x 4 = 4

Jawab :

Vektor x = [ x1 x 2 x 3 x 4 ] T diperoleh melalui prosedur berikut :

1. hitung : x 4 = 4/2 = 2

2. substitusikan nilai x 4 ke semua persamaan di atasnya, koreksi ruas kanannya

persamaan; hasilnya adalah : 1 x1 + 1 x 2 − 1 x 3 = 0

−2 x 2 − 1 x 3 = 3

2 x 3 = 6

Selengkapnya di hendroagungs.blogspot.com