Sistem Persamaan Linear

•Misal terdapat SPL dengan n buah variabel bebas

Matriks:

nnnnnn

n

n

n

C

C

C

C

x

x

x

x

aaa

aaa

aaa

aaa

3

2

1

3

2

1

21

33231

22221

11211

nnmnmmm

nn

nn

Cxaxaxaxa

Cxaxaxaxa

Cxaxaxaxa

332211

22323222121

11313212111

Penyelesaian Sistem Persamaan Linear (SPL)

Algoritma Gauss Naif

Algoritma Gauss Jordan

Algoritma Gauss Seidel

Aturan Cramer

Algoritma Gauss Naif

Contoh Algortima Gauss Naif

•Diketahui SPL:

2x1 + 2x2 + x3 = 4

3x1 - x2 + x3 = 1

x1 + 4x2 - x3 = 2

•Bagaimana penyelesaiannya?

Penyelesaian:

• Matriks yang terbentuk:

• Langkah:

1.

2

1

4

141

113

122

3

2

1

x

x

x

2

1

2

141

1132111

2

1

2

2

1

1

x

x

x

b

Penyelesaian (lanjutan)

2. dan 3.

4. dan 5.

2

5

2

14121402111

3

3

2

1

12

x

x

x

bb

0

5

2

2330

21402111

3

2

1

13

x

x

x

bb

6.

7. dan 8.

045

2

2330

81102111

4

1

3

2

1

2

x

x

x

b

41545

2

81500

81102111

3

3

2

1

23

x

x

x

bb

Penyelesaian (lanjutan)

• Hasil:

2

415

815

3

3

x

x

1281

45

45

81

2

32

x

xx

022112

221

1

321

x

xxx

Penyelesaian (lanjutan)

Algoritma Gauss Jordan

•Dengan metode Gauss Jordan matriks A diubah sedemikian rupa sampai terbentuk identitas dengan cara :

diubah menjadi

C* merupakan matriks C yang sudah mengalami beberapa kali transformasi, sehingga:

CXIA | CXAI 1|

nn C

C

C

C

x

x

x

x

A

3

2

1

3

2

1

1

1000

0100

0010

0001

nn Cx

Cx

Cx

22

11

Algoritma Gauss Jordan

Contoh Algoritma Gauss Jordan:

•Diketahui SPL:

2x1 + 2x2 + x3 = 4

3x1 - x2 + x3 = 1

x1 + 4x2 - x3 = 2

•Bagaimana penyelesaiannya?

Penyelesian

• Langkah:

1.

2.

2

1

4

100

010

001

1

1

1

4

1

2

1

3

2

3

2

1

x

x

x

2

1

2

100

010

0021

1

121

4

1

1

1

3

1

2

1

3

2

1

1

x

x

x

b

Penyelesaian (lanjutan)

3.

4.

13

12 3

bb

bb

0

5

2

1021

0123

0021

232121

3

4

1

0

0

1

3

2

1

x

x

x

045

2

1021

041

83

0021

238121

3

1

1

0

0

1

4

1

3

2

1

2

x

x

x

b

Penyelesaian (lanjutan)

5.

6.

23

21

3bb

bb

4

154543

143

813

041

83

041

81

8158183

0

1

0

0

0

1

3

2

1

x

x

x

24543

158

156

1513

041

83

041

81

18183

0

1

0

0

0

1

15

8

3

2

1

3

x

x

x

b

Penyelesaian (lanjutan)

7.

Jadi: x1 = 0, x2 = 1, x3 = 2

32

31

81

83

bb

bb

2

1

0

158

156

1513

151

51

154

51

52

521

1

0

0

0

1

0

0

0

1

3

2

1

x

x

x

Algoritma Gauss Seidel

• Sering dipakai untuk menyelesaikan persamaan yang berjumlah besar.

•Dilakukan dengan suatu iterasi yang memberikan harga awal untuk x1 = x2 = x3 = ... = xn = 0.

•Metode ini berlainan dengan metode Gauss Jordan dan Gauss Naif karena metode ini menggunakan iterasi dalam menentukan harga x1, x2, x3, ..., xn.

• Kelemahan metode eliminasi dibandingkan metode iterasi adalah metode eliminasi sulit untuk digunakan dalam menyelesaikan SPL berukuran besar.

Algoritma Gauss Seidel

1. Beri harga awal x1 = x2 = x3 = ... = xn = 0

2. Hitung

Karena x2 = x3 = x4 = ... = xn = 0, maka

11

141431321211

a

xaxaxaxaCx nn

11

11a

Cx

Algoritma Gauss Seidel

3. x1 baru yang didapat dari tahap 2 digunakan untuk menghitung x2.

Baris 2 a21x1 + a22x2 + a23x3 + ... + a2nxn = C2

22

232312122

a

xaxaxaCx nn

22

12122

a

xaCx

Algoritma Gauss Seidel

4. Menghitung x3

Baris 3 a31x1 + a32x2 + a33x3 + ... + a3nxn = C3

a33x3 = C3 – a31x1 – a32x2 – … – a3nxn

33

343423213133

a

xaxaxaxaCx nn

33

23213133

a

xaxaCx

Algoritma Gauss Seidel

5. Cara ini diteruskan sampai ditemukan xn.

6. Lakukan iterasi ke-2 untuk menghitung x1, x2, x3, ..., xn baru

nn

nnn

n

nn

nn

a

xaxaxaxaCx

a

xaxaxaCx

a

xaxaxaCx

111313212111

22

232312122

11

131321211

Algoritma Gauss Seidel

7. Mencari kesalahan iterasi |a| dengan cara:

8. Iterasi diteruskan sampai didapat |a| < |s|

%100

%100

)(

)(

barun

lamanbarun

an

barui

lamaibarui

ai

x

xxx

x

xxx

Contoh Algoritma Gauss Seidel

•Diketahui SPL:

x1 + 7x2 – 3x3 = –51

4x1 – 4x2 + 9x3 = 61

12x1 – x2 + 3x3 = 8

dan a = 5 %

8

61

51

3112

944

371

3

2

1

x

x

x

Penyelesaian:

•Iterasi ke-0

x1 = x2 = x3 = 0

•Iterasi ke-1

511

511

x

25,66

4

51461

4

461 12

xx

58,184

3

25,66518

3

128 213

xxx

Penyelesaian (lanjutan)

•Iterasi ke-2

78,3407

3

55,136649,966128

3

128

55,13664

58,184949,966461

4

9461

49,9661

58,184325,66751

1

3751

213

312

321

xxx

xxx

xxx

Penyelesaian (lanjutan)

•Iterasi ke-3

•Perhitungan x1, x2, x3 diteruskan sampai semua |a| < |s|

11,70189

3

94,2752219,19840128

3

128

94,275224

78,3407919,19840461

4

9461

19,198401

78,3407355,1366751

1

3751

213

312

321

xxx

xxx

xxx

Penyelesaian (lanjutan)

Iterasi ke- Nilai x a

0

x1 = 0

x2 = 0

x3 = 0

1

x1 = 51

x2 = 66,25

x3 = 184,58

2

x1 = 966,49

x2 = 1366,55

x3 = 3407,78

a = 105,28 %

a = 104,85 %

a = 105,42 %

3

x1 = 19840,19

x2 = 27522,94

x3 = 70189,11

a = 104,87 %

a = 104,97 %

a = 104,86 %

Koefisien Relaksasi ()

•Tujuan:Perbaikan konvergensi dalam Gauss Seidel. •Biasanya koefisien relaksasi dipilih sendiri

berdasarkan masalah yang dihadapi. • Jika SPL tidak konvergen, yang bernilai antara

0 s/d 1 disebut Under Relaksasi.• antara 1 dan 2 biasanya digunakan untuk

mempercepat konvergensi suatu sistem persamaan yang konvergen, disebut Over Relaksasi.

Koefisien Relaksasi ()

•Rumus (nilai SPL) dengan menggunakan

lama

i

baru

i

baru

i xxx 1

Contoh Koefisien Relaksasi ()

Iterasi

ke-Nilai x

dengan

(1,5)

0x1 = 0

x2 = 0

1x1 = 10

x2 = 15

2x1 = 6

x2 = 7,5

x1 baru = 4

x2 baru = 3,75

3x1 = 4

x2 = 3,75

Contoh perhitungan :

x1 baru

= 1,5 . 6 + (1 – 1,5) . 10

= 9 + (–0,5) . 10

= 4