METODE NUMERIK SISTEM PERSAMAAN ALJABAR LINIER (SPL) SIMULTAN

METODE NUMERIK SISTEM PERSAMAAN ALJABAR LINIER (SPL) SIMULTAN

http://maulana.lecture.ub.ac.id/lecture/metode-numerik/ 1

Sistem Persamaan Linier 

Misal terdapat SPL dengan n buah variabel bebas a11 x1  a12 x 2  a13 x 3    a1n x n  C 1 a21 x 1  a22 x 2  a23 x 3    a2 n x n  C 2

 am1 x1  am 2 x 2  am3 x 3    amn x n  C n

Matriks:

 a11  a21 a31    a  n1

a12 a22 a32  an2

    

a1n   x1  C1      a2n   x2  C2  a3n   x3   C3             ann   x n  C n 

2

Penyelesaian Sistem Persamaan Linier (SPL)   

Algoritma Gauss Naif Algoritma Gauss Jordan Algoritma Gauss Seidel

3

Algoritma Gauss Naif 1.

2.

3.

Membagi persamaan pertama dengan koefisien a11. Langkah tersebut disebut normalisasi. Tujuan normalisasi ini adalah agar koefisien dari x1 berubah menjadi 1. Kalikan persamaan yang telah dinormalisasi (dalam hal ini persamaan pertama) dengan koefisien pertama dari persamaan kedua (yaitu a21). Mengurangkan baris kedua dan ketiga dengan baris pertama. 4


5.

6.

Kalikan persamaan pertama yang sudah dinormalisasi dengan koefisien tertentu sehingga a11 = a31. Kurangkan persamaan ketiga dengan hasil dari yang didapat dari langkah 4. Baris kedua dibagi dengan koefisien a22. Langkah ini disebut NORMALISASI untuk persamaan kedua. Tujuannya adalah agar koefisien x2 berubah menjadi 1. 5


8.

Kalikan persamaan kedua yang sudah dinormalisasi pada langkah ke-6 dengan suatu koefisien tertentu sehingga a22 = a32. Kurangkan persamaan ketiga dengan persamaan kedua hasil dari langkah ke-7.

6

Algoritma Gauss Naif (Ex.) 



Diketahui SPL: 2x1 + 2x2 + x3 = 4 3x1 - x2 + x3 = 1 x1 + 4x2 - x3 = 2 Bagaimana penyelesaiannya?

7


Matriks yang terbentuk: 1   x1  4 2 2      3  1 1    x2   1 1 4  1  x3  2



Langkah: 1 1 1.

1   x1  2 2      1 b1  3  1 1   x2   1 2 1 4  1  x  2   2    8

Algoritma Gauss Naif (Ex.) 2. dan 3.

1  1 1 2   x1   2       b2  3b1  0  4  1   x2    5 2   1   x3   2  1 4 

4. dan 5.

1  1 1 2   x1   2       b3  b1  0  4  1   x2    5 2  0 3  3   x3   0  2  9

Algoritma Gauss Naif (Ex.) 6.

1 1 1  2   x1   2   1      b2  0 1 1   x2   5  8  4 4  0 3  3   x3   0  2 

7. dan 8.

1 1 1   2  x   2  1      1  x  5  b3  3b2  0 1 8  2   4   0 0  15   x3   15  4 8  

10


Hasil:  15  x3   15 8 4 x3  2 x1  x2  1 x3  2 2

x2  1 x3  5 8 4 x2  5  1 2  1 4 8





x1  2  1  1  2  0 2

11

Algoritma Gauss Jordan 

Dengan metode Gauss Jordan matriks A diubah sedemikian rupa sampai terbentuk identitas dengan cara : A | I X  C diubah menjadi I | A1 X  C  C* merupakan matriks C yang sudah mengalami beberapa kali transformasi, sehingga:



1  0 0   0

0 1 0  0

0 0 1  0

    

0   x1  C1  x     0   2  C2  0 A 1   x3   C3                x n  C   1    n 



x1  C 1



x2  C 2



xn  Cn



12

Algoritma Gauss Jordan (Ex.) 



Diketahui SPL: 2x1 + 2x2 + x3 = 4 3x1 - x2 + x3 = 1 x1 + 4x2 - x3 = 2 Bagaimana penyelesaiannya?

13

Algoritma Gauss Jordan (Ex.) 

Langkah: 1. 2 2

1 1 0 0  x1  4      3  1 1 0 1 0    x2   1  1 4  1 0 0 1  x3  2      

2.

1 1 1 1 0 0  x1  2 2 2     1  b1 3  1 1 0 1 0  x2   1 2    x  2 1 4  1 0 0 1    3    14

Algoritma Gauss Jordan (Ex.) 3.

  1 1 0 0 2 2 1 1   x1   2  b2  3b1      0 4 1 3 1 0  x2    5 2 2  b3  b1  0 3  3  1 0 1  x3   0  2 2  

4.

  1 1 0 0 2 2 1 1   x1   2  1      3  b2 0 1 1 1 0  x2   5  8 8 4 4  4  0 3  3  1 0 1  x3   0  2 2   15


b1  b2 b3  3b2

6.

  3 1 1  3  0 1 0 x   8 4 8   1  4    3 1 0 1 1 0  x2    5  8 8 4    4  3 0 0  15  13 1  x3   15  4 8 8 4   

 3 1 1 0   x  3  1 0 8 4 8   1  4 8   3  b3 0 1 1 1 0   x2   5  8 8 4  15   4 0 0 1 13 6  8   x3   2  15 15 15    16


b1  3 b3 8 b2  1 b3 8

 21 2 1  1 0 0 5 5 5   x1  0  1 0 1 0 4   x2   1 1 15 5 15       0 0 1 13 6  8   x3  2 15 15 15 

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

17

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. 18

Algoritma Gauss Seidel 1. 2.

Beri harga awal x1 = x2 = x3 = ... = xn = 0 Hitung x  C1  a12 x2  a13 x3  a14 x 4    a1n x n  1

a11

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

C1 a11

19

Algoritma Gauss Seidel 3.

x1 baru yang didapat dari tahap 2 digunakan untuk menghitung x2. Baris 2  a21x1 + a22x2 + a23x3 + ... + a2nxn = C2 x2 

C 2  a21 x1  a23 x3    a2n x n a22

x2 

C2  a21 x1 a22

20


Menghitung x3 Baris 3  a31x1 + a32x2 + a33x3 + ... + a3nxn = C3 a33x3 = C3 – a31x1 – a32x2 – … – a3nxn x3 

C3  a31 x1  a32 x2  a34 x 4    a3n x n a33

C3  a31 x1  a32 x2 x3  a33 21

Algoritma Gauss Seidel 5. 6.

Cara ini diteruskan sampai ditemukan xn. Lakukan iterasi ke-2 untuk menghitung x1, x2, x3, ..., xn baru x1 

C1  a12 x2  a13 x3    a1n x n a11

C 2  a21 x1  a23 x3    a2n x n x2  a22  xn 

C n  a11 x1  a12 x2  a13 x3    a1n 1 x n 1 ann

22


Mencari kesalahan iterasi |a| dengan cara: xi   a 

x i baru   x i(lama) x i baru 

 100%

 xn   a 

8.

x nbaru   x n(lama) x nbaru 

 100%

Iterasi diteruskan sampai didapat |a| < |s| 23

Algoritma Gauss Seidel (Ex.) 

Diketahui SPL: x1 + 7x2 – 3x3 = –51 4x1 – 4x2 + 9x3 = 61  12x1 – x2 + 3x3 = 8 dan a = 5 %

7  3  x1   51 1      4  4 9 x  61   2    12  1 3   x3   8 

24




Iterasi ke-0 x1 = x2 = x3 = 0 Iterasi ke-1 51 x1   51 1

x2 

61  4 x1 61  4 51   66,25 4 4

8  12 x1  x2 8   51   66,25 x3    184,58 3 3

25


Iterasi ke-2

 51  7 x2  3x3  51  7 66,25  3184,58 x1    966,49 1 1 61  4 x1  9 x3 61  4966,49  9184,58 x2    1366,55 4 4 8  12 x1  x2 8  12966,49   1366,55 x3    3407,78 3 3

26


Iterasi ke-3

 51  7 x2  3x3  51  71366,55  3 3407,78    19840,19 1 1 61  4 x1  9 x3 61  4 19840,19  9 3407,78 x2    27522,94 4 4 8  12 x1  x2 8  12 19840,19   27522,94  x3    70189,11 3 3 x1 



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

Algoritma Gauss Seidel (Ex.) Iterasi ke-

Nilai x

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 %

a

28

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. 29

Koefisien Relaksasi () 

Rumus (nilai SPL) dengan menggunakan 

xi    xi

baru

 1     xi

lama

0<<2 1 30

Solusi perbaikan dengan Koefisien Relaksasi () pada metode Gauss Seidel x2

x2

v

u

u

Konvergen lambat

Divergen

v

x2`(target)

x2 (target)

x1(target)

x1

x1(target)

1<<2

0<<1

Over relaxation

Under relaxation

Mempercepat konvergensi

Divergen menjadi konvergen

Solusi:

x1

31

Koefisien Relaksasi () (Ex.) Iterasi ke0 1 2 3

Nilai x

dengan  (1,5)

x1 = 0 x2 = 0 x1 = 10 x2 = 15 x1 = 6 x1 baru = 4 x2 = 7,5 x2 baru = 3,75 x1 = 4 x2 = 3,75

Contoh perhitungan : x1 baru = 1,5 . 6 + (1 – 1,5) . 10 = 9 + (–0,5) . 10 =4

32

METODE NUMERIK SISTEM PERSAMAAN ALJABAR LINIER (SPL) SIMULTAN

Recommend Documents