Bab 3. Penyelesaian Sistem Persamaan Linier (SPL)

Metode Numerik

Bab 3. Penyelesaian Sistem Persamaan Linier (SPL) Yuliana Setiowati Politeknik Elektronika Negeri Surabaya 2007

PENS-ITS

1

Metode Numerik

Topik • • • • • • • • •

Definisi SPL Bentuk Matrik SPL Augmented Matrik Penyelesaian SPL Operasi-operasi Dasar (Elementary Operations) Sistem equivalent Operasi Baris Elementer 3 Kemungkinan Penyelesaian SPL Penyelesaian dengan Metode Numerik • Strategy Pivoting • Jenis pivoting PENS-ITS

2

Metode Numerik

Definisi SPL • Suatu sistem yang merupakan gabungan dari beberapa persamaan linier dengan variabel x1 , x2 ,..., xn a11 x1  a12 x2  ...  a1n xn  b1

a21 x1  a22 x2  ...  a2 n xn  b2 



  am1 x1  am 2 x2  ...  amn xn  bm

• SPL diatas mempunyai m persamaan dan n variabel • SPL mempunyai minimal sebuah solusi, disebut konsisten, jika tidak mempunyai solusi disebut tidak konsisten PENS-ITS

3

Metode Numerik

SPL • Bentuk persamaan linier simultan dengan n persamaan dan n variabel bebas  a11 a12 a  21 a22  ... ...  an1 an 2

... a1n   x1   b1  ... a2 n   x2  b2   ... ...   ...   ...      ... ann   xn  bn 

PENS-ITS

4

Metode Numerik

Bentuk Matrik SPL • SPL dengan m persamaan dan n variabel a11 x1  a12 x2  ...  a1n xn  b1 a21 x1  a22 x2  ...  a2 n xn  b2 



  am1 x1  am 2 x2  ...  amn xn  bm

• Bentuk SPL dapat ditulis dengan a11 a12 ... a1n a a ... a 2n  21 22      am1 am 2 ... amn

     

b1  b   2     bm 

=

 x1  x   2      xm 

• Dapat ditulis Ax = B PENS-ITS

5

Metode Numerik

Bentuk Matrik SPL • Dimana A =

a11 a  21   am1

a12 ... a1n  a22 ... a2 n      am 2 ... amn 

x =  x1 

x   2      xm 

B= b1 

b   2     bm 

• A adalah matrik koefisien dari SPL (matrik Jacobian). • Vektor x disebut vektor variabel • Vektor B disebut vektor konstanta

PENS-ITS

6

Augmented Matrik

Metode Numerik

• Matrik yang merupakan perluasan matrik A dengan dengan menambahkan vektor B pada kolom terakhirnya a11 a12 ... a1n a a ... a 2n  21 22      am1 am 2 ... amn

b1  b2     bm 

PENS-ITS

7

Metode Numerik

Contoh x + 3y + 2z = 44 x + 4y + z = 49 2x + 5y + 5z = 83 • Bentuk matrik SPL 1 3 2   x  1 4 1       y 2 5 5  z 

=

• Augmented Matrik

 44   49    83 

1 3 2 44 1 4 1 49   2 5 5 83

PENS-ITS

8

Penyelesaian SPL

Metode Numerik

• Berdasarkan penyelesaiannya, SPL dibedakan menjadu 3 macam: – Tidak mempunyai penyelesaian (no solutions) – Tepat satu penyelesaian (exactly one solution) – Banyak penyelesaian(infinitely many solutions)

PENS-ITS

9

Metode Numerik

Penyelesaian SPL • Secara geometri penyelesaian sist pers linier untuk 2 var bebas dapat digambarkan: l 1

y

l1

y

l2

x

l2

x

Mempunyai 1 penyelesaian

Tidak mempunyai penyelesaian PENS-ITS

10

Metode Numerik

Penyelesaian SPL • Secara geometri penyelesaian sist pers linier untuk 2 var bebas dapat digambarkan: y l1=l2

Mempunyai banyak penyelesaian

x

PENS-ITS

11

Metode Numerik

Contoh 1 • Seorang pembuat boneka ingin membuat dua macam boneka yaitu boneka A dan boneka B. Kedua boneka tersebut dibuat dengan menggunakan dua macam bahan yaitu potongan kain dan kancing. Boneka A membutuhkan 10 potongan kain dan 6 kancing, sedangkan boneka B membutuhkan 8 potongan kain dan 8 kancing. • Permasalahannya adalah berapa buah boneka A dan boneka B yang dapat dibuat dari 82 potongan kain dan 62 kancing ?

PENS-ITS

12

Metode Numerik

Contoh 1 •

Permasalahan ini dapat dimodelkan dengan menyatakan : – –

•

x = jumlah boneka A y = jumlah boneka B

Untuk setiap bahan dapat dinyatakan bahwa: – –

Potongan kain 10 untuk boneka A + 8 untuk boneka B = 82 Kancing 6 untuk boneka A + 8 untuk boneka B = 62

•

Atau dapat dituliskan dengan : 10 x + 8 y = 82 6 x + 8 y = 62

•

Penyelesaian dari permasalahan di atas adalah penentuan nilai x dan y yang memenuhi kedua persamaan di atas.

PENS-ITS

13

Metode Numerik

Contoh 2 •

Perhatikan potongan peta yang sudah diperbesar (zoom) sebagai berikut : 3 4

2

1

• • •

Perhatikan bahwa pada ke-4 titik tersebut dihubungkan dengan garis lurus, sehingga tampak kasar. Untuk menghaluskannya dilakukan pendekatan garis dengan kurva yang dibentuk dengan fungsi pendekatan polinomial. Dari fungsi polinomial yang dihasilkan kurva dapat digambarkan dengan lebih halus. PENS-ITS

14

Metode Numerik

Contoh 2 •

4 titik yang ditunjuk adalah (2,3), (7,6), (8,14) dan (12,10). 4 titik ini dapat didekati dengan fungsi polinom pangkat 3 yaitu :

y  ax 3  bx 2  cx  d •

Bila nilai x dan y dari 4 titik dimasukkan ke dalam persamaan di atas akan diperoleh model persamaan simultan sebagai berikut : Titik 1  3 = 8 a + 4 b + 2 c + d Titik 2  6 = 343 a + 49 b + 7 c + d Titik 3  14 = 512 a + 64 b + 8 c + d Titik 4  10 = 1728 a + 144 b + 12 c + d

•

Nilai a, b, c dan d adalah penyelesaian dari permasalahan di atas.

PENS-ITS

15

Metode Numerik

Contoh 2 • Setelah nilai a, b, c dan d diperoleh maka persamaan polinomialnya didapatkan dan dengan menggunakan step x yang lebih kecil dapat digambarkan grafiknya dengan lebih halus.

PENS-ITS

16

Metode Numerik

Operasi-operasi Dasar (Elementary Operations)

• Terdapat dua tahap untuk menyelesaikan SPL yaitu: – Reduksi sistem (mengeliminasi variabel) – Mendeskripsikan himpunan penyelesaian

• Tujuan dari reduksi sistem adalah untuk menyederhanakan SPL dengan mengeliminasi variabel-variabel, sehingga sistem yang dihasilkan mempunyai himpunan penyelesaian yang sama dengan sistem aslinya.

PENS-ITS

17

Metode Numerik

Sistem equivalent • Definisi Dua SPL dengan n variabel disebut equivalent jika SPL tersebut mempunyai himpunan penyelesaian yang sama

PENS-ITS

18

Metode Numerik

Operasi Baris Elementer • Untuk reduksi sistem, SPL menggunakan operasi baris elementer (elementary row operations). Terdapat 3 operasi : – Menukar dua baris (Ri ↔ Rj) – Mengalikan sebuah baris dengan sebuah skalar (k Ri) – Menambah perkalian k dengan sebuah baris dengan baris lainnya. (Ri + kRj) PENS-ITS

19

Metode Numerik

Operasi Baris Elementer • Menambah perkalian k dengan sebuah baris dengan baris lainnya. (Ri + kRj) 1 1 2 9  2 4  3 1   3 6  5 0

B2 – 2B1

9  1 1 2 0 2  7  17   3 6  5 0 

• B2 – 2B1 artinya elemen-elemen pada baris kedua dikurangi dengan dua kali elemen pada baris ke satu • -2B1 B2 B2 – 2B1

: -2 -2 -4 18 : 2 4 -3 1 : 0 2 -7 19 (menjadi elemen baris ke-2) PENS-ITS

20

Metode Numerik

Contoh Penggunaan Operasi Baris Elementer x  y  2z  9 2 x  4 y  3z  1

B2 – 2B1

3x  6 y  5 z  0

1 1 2 9  2 4  3 1   3 6  5 0

B2 – 2B1

x  y  2z  9 2 y  7 z  1 7 3x  6 y  5 z  0

9  1 1 2 0 2  7  17   3 6  5 0 

PENS-ITS

B3 – 3B1

B3 – 3B1

21

Metode Numerik

Contoh Penggunaan Operasi Baris Elementer x  y  2z  9 2 y  7 z  17 3 y  11z  27

9  1 1 2 0 2  7  17    0 3  11  27

x  y  2z 

9

y  72 z   172

1/2B2

3 y  11z 

1/2B2

PENS-ITS

B3 – 3B2

0

9  B – 3B 1 1 2 2 0 1  7  17  3 2 2   0 3  11  27 22

Metode Numerik

Contoh Penggunaan Operasi Baris Elementer x  y  2z 

x  y  2z 

9

y  72 z   172

y  72 z   172

-2B3

9   172   32 

-2B3

B1 – B2

z 3

 12 z   32

1 1 2 0 1  7 2  0 0  12

9

1 1 2 0 1  7 2  0 0 1 PENS-ITS

9   172  3 

B1 – B2

23

Metode Numerik

Contoh Penggunaan Operasi Baris Elementer x

 112 z 

35 2

y z  7 2

z 1 0 112 0 1  7 2  0 0 1

17 2

3    3  35 2 17 2

B1 – 11/2 B3 B2 + 7/2 B3 B1 – 11/2 B3 B2 + 7/2 B3

x y

1  2 z 3

1 0 0 1 0 1 0 2    0 0 1 3

SPL diatas mempunyai penyelesaian tunggal x=1,y=2,z=3 Proses reduksi pada contoh diatas disebut Eliminasi Gauss-

Jordan

PENS-ITS

24

Metode Numerik

Contoh 2x2 + x3 = -2 3x1 + 5x2 - 5x3 = 1 2x1 + 4x2 - 2x3 = 2 0 2 1  2 3 5  5 1    2 4  2 2  1 2  1 1  3 5  5 1    0 2 1  2

B1

↔

B3

B2 - 3B1

PENS-ITS

2 4  2 2  3 5  5 1    0 2 1  2

1 2  1 1  0  1  2  2    0 2 1  2

1/2B1

-B2

25

Metode Numerik

Contoh 1 2  1 1  0 1 2 2   0 2 1  2

B1 - 2B2

1 0  5  3 0 1 2  2   0 0  3  6

-1/3B3

1 0 0 7 0 1 2 2    0 0 1 2

B2 - 2B3

1 0  5  3 0 1 2  2   0 2 1  2

1 0  5  3 0 1 2  2   0 0 1 2 

B3 - 2B2

B1 + 5B3

1 0 0 7  0 1 0  2    0 0 1 2 

• SPL diatas mempunyai penyelesaian tunggal yaitu x1=7, x2=-2 dan x3=-2

PENS-ITS

26

Metode Numerik

3 Kemungkinan Penyelesaian SPL(a) Dari matrik augmented SPL direduksi dengan operasi baris elementer diperoleh bentuk reduced echelon form. Terdapat 4 kemungkinan penyelesaian seperti berikut :

1 0 0 5  (a) 0 1 0  2 0 0 1 4  Penyelesaian (a)

x y

PENS-ITS

 5  -2 z 4

27

Metode Numerik

3 Kemungkinan Penyelesaian SPL(b1) 2 4 1 1 (b) 0  3  3  6 0 0 0 0  Penyelesaian (b) x1  x2  2 x3  4

Variabel bebas (free variables)

- 3x2 - 3x3  - 6 Variabel depan (leading variables)

PENS-ITS

28

Metode Numerik

3 Kemungkinan Penyelesaian SPL(b2) x1  4 - x2  2 x3 x2  2 - x3

x1  2 - x3

Variabel bebas dapat diisi dengan sembarang nilai k, selanjutnya dapat ditentukan variabel depan

x2  2 - x3 Terdapat banyak penyelesaian, penyelesaian secara umum diberikan dengan menggunakan formula

PENS-ITS

x1  4 - x2  2 x3 x2  2 - x3

29

Metode Numerik

3 Kemungkinan Penyelesaian SPL(c) 2 4 1 1 0  3  3  6    0 0 0 1 

Penyelesaian (c) 1. Persamaan yang bersesuai dengan baris terakhir tsb adalah 2. Tidak ada nilai xi yang memenuhi persamaan tersebut

0 x1  0 x2  0 x3  1

PENS-ITS

30

Metode Numerik

Contoh • Matrik di bawah ini adalah matrik reduced echelon form. Jelaskan SPL yang berhubungan dengan matrik tersebut dan bagaimana penyelesaiannya? 1 0 A 0  0

0 1 0 0

0 3 0  2 1 7   0 0 

1 0  1 0 B  0 1 3 0 0 0 0 1 1 2 0 5 D  0 0 1 0 0 0 0 0

1  3 0 4 2 C  0 0 1  5 1 0 0 0 0 0 PENS-ITS

31

Metode Numerik

Contoh • Matrik A adalah matrik augmented dengan SPL sbb: x1  3 x2  - 2 x3  7 SPL mempunyai penyelesaian tunggal yaitu x1  3 x2  - 2 x3  7 • Matrik B adalah matrik augmented dengan SPL sbb: x1 - x3  0 x2  3x3  0 0 x1  0 x2  0 x3  1

SPL tidak mempunyai penyelesaian karena pada persamaan ke-3, SPL tidak konsisten PENS-ITS

32

Metode Numerik

Contoh •

Matrik C adalah matrik augmented dengan SPL :

x1 - 3x2  4 x4  2 x3 - 5 x4  1 Matrik C adalah matrik augmented dengan SPL :

x1  2  3x2  4 x4 x3  1  5 x4 Variabel depan adalah x1 dan x3, variabel bebas adalah x2 dan x4. SPL mempunyai penyelesaian banyak dapat dinyatakan dengan formula :

x1  2  3s  4t x2  s x3  1  5t x4  t PENS-ITS

33

Metode Numerik

Contoh • Matrik D adalah matrik augmented dengan SPL : x1  2 x2  5 x3  0

Matrik D adalah matrik augmented dengan SPL : x1  5 - 2 x2 x3  0

• Variabel depan adalah x1 dan x3, variabel bebas adalah x2. SPL mempunyai penyelesaian banyak dinyatakan dengan formula : x  5 - 2s 1

x2  s x3  0 PENS-ITS

34

Metode Numerik

Metode Analitik • metode grafis • aturan Crammer • invers matrik

PENS-ITS

35

Penyelesaian dengan Metode Numerik • • •

Metode Numerik

Metode Eliminasi Gauss Metode Eliminasi Gauss-Jordan Metode Iterasi Gauss-Seidel

PENS-ITS

36

Metode Numerik

Metode Eliminasi Gauss • Metode Eliminasi Gauss merupakan metode yang dikembangkan dari metode eliminasi, yaitu menghilangkan atau mengurangi jumlah variable sehingga dapat diperoleh nilai dari suatu variable bebas • matrik diubah menjadi augmented matrik :

 a11 a12  a 21 a 22  ... ...  a n1 a n 2

... a1n ... a 2 n ... ... ... a nn PENS-ITS

b1   b2  ...   bn  37

Metode Numerik

Metode Eliminasi Gauss • ubah matrik menjadi matrik segitiga atas atau segitiga bawah dengan menggunakan OBE (Operasi Baris Elementer).

 a11 a  21 a31   ... a n1

a12 a 22

a13 ... a1n a 23 ... a 2 n

a32 ...

a33 ... a3n ... ... ...

an2

a n 3 ... a nn

c11 c12 0 c 22  0 0   ... ...  0 0

b1  b2  b3   ...  bn 

PENS-ITS

d1  d 2  d3   ...  d n 

c13 ... c1n c 23 ... c 2 n c33 ... c3n ... ... ... 0

... c nn 38

Metode Numerik

Metode Eliminasi Gauss • Sehingga penyelesaian dapat diperoleh dengan: d xn 

n

c nn

x n 1 

1 c n 1,n 1

 c

n 1, n

x n  d n 1 

..................................... 1 d 2  c23 x3  c24 x4  ...  c2 n xn  x2  c 22 1 d1  c12 x2  c13 x3  ...  c1n xn  x1  c11 PENS-ITS

39

Metode Numerik

Contoh : • Selesaikan sistem persamaan berikut:

x1  x 2  x3  6 x1  2 x 2  x3  2 2 x1  x 2  2 x3  10 • Augmented matrik dari persamaan linier simultan tersebut :

1 1 1 6  1 2  1 2    2 1 2 10 PENS-ITS

40

Metode Numerik

Contoh : • Lakukan operasi baris elementer B2  B1 B3  2B1

B3  B2

1 6  1 1    0 1  2  4  0 1 0  2  

6 1 1 1 0 1  2  4    0 0  2  6 PENS-ITS

41

Metode Numerik

Contoh : • Penyelesaian : 6 x3  3 2 1 x 2   4  (2)3  2 1 1 x1  6  2  3  1 1 PENS-ITS

42

Metode Numerik

Algoritma Metode Eliminasi Gauss Naif (Biasa) • Masukkan ukuran matrik N, matrik A dan vektor B • Buat matrik augmented [A|B] namakan dengan a • Untuk baris ke-i=0 s/d i
ai , i

Untuk kolom k=0 s/d n Hitung a j ,k  a j ,k  c * ai ,k • Hitung akar untuk i=n s/d 1 1 bi  ai,i1xi1  ai,i2 xi2  ...  ai,n xn  xi  ai ,i PENS-ITS

43

Metode Numerik

Contoh • Selesaikan SPL berikut ini dengan metode Eliminasi Gauss x  2x  x  2 1

2

3

3x1  6 x2

9

2 x1  8 x2  4 x3  6

 1 2 1 2    3 6 0 9  2 8 4 6  

B2  3B1 B3  2 B1

1 2 1 2   0 0  3 3 0 4 2 2  

PENS-ITS

B2  B3

1 2 1 2   0 4 2 2 0 0  3 3  

44

Metode Numerik

Contoh • Elemen a22 yang akan menjadi pivot pada operasi baris 2 ternyata sama dengan nol. Karena itu, pada operasi baris 2, elemen baris 2 dipertukarkan dengan elemen baris 3. • Proses pertukaran baris terjadi akibat proses pivoting. Sekarang elemen a22 = 4 ≠ 0 sehingga operasi baris elementer dapat diteruskan. PENS-ITS

45

Metode Numerik

Masalah Pivoting • Melakukan pertukaran baris untuk menghindari pivot yang bernilai nol adalah cara pivoting yang sederhana (simple pivoting) • Masalah lain yang dapat timbul bila elemen pivot sangat dekat ke nol.

PENS-ITS

46

Metode Numerik

Strategy Pivoting • Prinsip strategy pivoting adalah jika ap,p(p-1) =0, cari baris k dengan ak,p ≠ 0 dan k > p, lalu pertukarkan baris p dan baris k.

PENS-ITS

47

Metode Numerik

Jenis pivoting (1) • Partial pivoting (pivoting sebagian) – Pivot dipilih dari semua elemen pada kolom p yang mempunyai nilai mutlak terbesar. |ak,p| = max{|ap,p|, |ap+1,p|, …, |an-1,p|, |an,p|} – Lalu pertukarkan baris ke-k dengan baris ke-p. – Misal setelah operasi baris pertama diperoleh matrik sbb: x 0  0  0

x x x x

x x x x

x x x x

x x  x  x

– Untuk operasi baris kedua, carilah elemen x pada kolom ke-2 mulai baris ke-2 s/d kolom ke-4 yang nilai mutlaknya terbesar, lalu pertukarkan barisnya dengan baris ke-2. – Elemen x yang nilai mutlaknya terbesar itu sekarang menjadi pivot untuk operasi baris selanjutnya.

PENS-ITS

48

Metode Numerik

Jenis pivoting (2) • Complete pivoting (pivoting lengkap) – Disamping baris, kolom juga diikutkan dalam pencarian elemen terbesar dan kemudian dipertukarkan, maka strategi ini disebut pivoting lengkap. – Pivoting lengkap jarang dipakai dalam program sederhana karena pertukaran kolom mengubah urutan suku x dan akibatnya menambah kerumitan program secara berarti PENS-ITS

49

Metode Numerik

Contoh • Selesaikan SPL dengan metode Eliminasi Gauss tanpa strategi pivoting 0.0003x1  1.566 x2  1.569 0.3454 x1  2.436 x2  1.018

• Penyelesaian

0.0003 1.566 1.569 0.3454 - 2.436 1.018  

R2 

0.3454 R 1  R 2  1151R 1 0.0003

0.0003 1.566 1.569   0  1804 1805  

PENS-ITS

50

Metode Numerik

Contoh • Dengan backward subtitusi diperoleh x 2   1805

 1.001  1804 1.569  1.566 *1.001 1.569  1.568 x1    3.333 0.0003 0.0003

x1  3.333 x 2  1.001

• Solusi ini sangat jauh berbeda dari solusi sebenarnya. • Kegagalan ini terjadi karena |a11| sangat kecil dibandingkan |a12| PENS-ITS

51

Metode Numerik

Contoh • Selesaikan SPL dengan metode Eliminasi Gauss dengan strategi pivoting 0.0003x1  1.566 x2  1.569

0.3454 x1  2.436 x2  1.018

• Penyelesaian • Baris pertama dipertukarkan dengan baris ke-2 sehingga 0.3454 menjadi pivot 0.0003 1.566 1.569 0.3454 - 2.436 1.018   R2 

0.0003 R1 0.3454

R 2  R1

0.3454 - 2.436 1.018 0.0003 1.566 1.569  

0.3454 - 2.436 1.018  0  1.568 1.568   PENS-ITS

52

Metode Numerik

Contoh • Dengan backward subtitusi diperoleh x 2  1.568 1 1.568 1.018  (2.436)(1.000) x1   10.02 0.3454

PENS-ITS

53

Metode Numerik

Algoritma Metode Eliminasi Gauss dengan strategi pivoting • Masukkan ukuran matrik N, matrik A dan vektor B • Buat matrik augmented [A|B] namakan dengan a • Untuk baris ke-i=0 s/d i
a j ,k  a j ,k  c * ai ,k



• Hitung akar untuk i=n s/d 1 x  1 b  a x  a i i i ,i 1 i 1 i ,i  2 xi  2  ...  ai , n xn

ai ,i

PENS-ITS

54



Metode Numerik

Metode Eliminasi Gauss Jordan • Metode ini merupakan pengembangan metode eliminasi Gauss, hanya saja augmented matrik, pada sebelah kiri diubah menjadi matrik diagonal  a11 a  21 a31   ... a n1

a12 a 22

a13 ... a1n a 23 ... a 2 n

a32 ...

a33 ... a3n ... ... ...

an2

a n 3 ... a nn

b1  b2  b3   ...  bn 

1 0  0  ...  0

d1  d 2  0 1 ... 0 d 3   ... ... ... ... ...  0 0 ... 1 d n  0 1

0 ... 0 0 ... 0

• Penyelesaian dari persamaan linier simultan diatas adalah nilai d1,d2,d3,…,dn dan atau:

x1  d1 , x2  d 2 , x3  d 3 ,...., xn  d n PENS-ITS

55

Metode Numerik

Contoh Eliminasi Gauss Jordan (1/1) • Selesaikan persamaan linier simultan:

• Augmented matrik dari persamaan linier simultan

x1  x 2  3 2 x1  4 x 2  8

1 1 3 B2  2b1 1 1 3 2 4 8 0 2 2   

• Lakukan operasi baris elementer Penyelesaian persamaan linier simultan : x1 = 2 dan x2 = 1

PENS-ITS

1 1 B 2 / 2 0 1 1 B1  B2  0

3 1

0 2 1 1  56

Metode Numerik

Contoh Eliminasi Gauss Jordan (1/4) x  y  2z  9 2 x  4 y  3z  1

B2-2B1

3x  6 y  5 z  0

1 1 2 9  2 4  3 1   3 6  5 0

B2-2B1

x  y  2z  9 2 y  7 z  1 7 3x  6 y  5 z  0

9  1 1 2 0 2  7  17   3 6  5 0  PENS-ITS

B3-3B1

B3-3B1

57

Metode Numerik

Contoh Eliminasi Gauss Jordan (2/4) x  y  2z  9 2 y  7 z  17 3 y  11z  27

9  1 1 2 0 2  7  17    0 3  11  27

½ B2

x  y  2z 

y  72 z   172 3 y  11z 

½ B2

9 0

9  1 1 2 0 1  7  17  2 2   0 3  11  27 PENS-ITS

B3-3B2

B3-3B2

58

Metode Numerik

Contoh Eliminasi Gauss Jordan (3/4) x  y  2z 

y  72 z   172  12 z   32

1 1 2 0 1  7 2  0 0  12

9   172   32 

x  y  2z 

9 -2 B3

9

y  72 z   172

B1 - B2

z 3

-2 B3

1 1 2 0 1  7 2  0 0 1 PENS-ITS

9   172  3 

B1 - B2

59

Metode Numerik

Contoh Eliminasi Gauss Jordan (4/4) x



11 2

z

35 2

y z  7 2

z

1 0 112 0 1  7 2  0 0 1

B2 + 7/2 B3

17 2

3

B1 - 11/2 B3

   3 

B2 + 7/2 B3

35 2 17 2

B1 - 11/2 B3

x y

1  2 z 3

1 0 0 1 0 1 0 2    0 0 1 3

 Solusi x = 1, y=2 dan z=3 PENS-ITS

60

Metode Numerik

Algoritma Metode Eliminasi Gauss Jordan dengan strategi pivoting • Masukkan ukuran matrik N, matrik A dan vektor B • Buat matrik augmented [A|B] namakan dengan a • Untuk baris ke-i=0 s/d i
ai ,k pembagi

Untuk baris ke-j=i+1 s/d j
61

Metode Numerik

Metode Iterasi Gauss Seidel • Metode untuk menyelesaikan SPL yang menggunakan proses iterasi. • Baik untuk menyelesaikan SPL yang besar • Bila diketahui SPL seperti di bawah ini a11 a 21 a31 ... a n1

x1  a12 x1  a 22 x1  a32 ... ... ... x1  a n 2

x 2  a13 x 2  a 23 x 2  a33 ... ... ... x2  a n3

x3  ... x3  ... x3  ... ... ... ... x3  ...

PENS-ITS

   ... 

a1n a2n a3n ... a nn

x n  b1 x n  b2 x n  b3 ... ... ... x n  bn

62

Metode Numerik

Metode Iterasi Gauss-Seidel • Berikan nilai awal dari setiap xi (i=1 s/d n) x1 

1 b1  a12 x 2  a13 x3  ....  a1n x n  a11

1 b2  a 21 x1  a 23 x3  ....  a 2 n x n  x2  a 22 ............................................................... 1 bn  a n1 x1  a n 2 x 2  ....  a nn1 x n 1  xn  a nn

PENS-ITS

63

Metode Numerik

Metode Iterasi Gauss-Seidel • Dengan menghitung nilai-nilai xi (i=1 s/d n) menggunakan persamaan-persamaan di atas secara terus-menerus hingga nilai untuk setiap xi (i=1 s/d n) sudah sama dengan nilai xi pada iterasi sebelumnya maka diperoleh penyelesaian dari SPL tersebut. • Atau dengan kata lain proses iterasi dihentikan bila selisih nilai xi (i=1 s/d n) dengan nilai xi pada iterasi sebelumnya kurang dari nilai tolerasi error yang ditentukan. • Untuk mengecek kekonvergenan

PENS-ITS

64

Metode Numerik

Syarat Konvergen • Syarat agar konvergen adalah sistem dominan secara diagonal

aii  • Contoh SPL berikut:

n

a

j 1, j  i

ij

3 x1  x2  x3  1 2 x1  4 x2  x3  5  x1  5 x2  8 x3  5

• Dominan secara diagonal karena | 3 | > | 1 | + | -1 | |4|>|2| +|1| | 8 | > | -1 | + | 5 | Sehingga pasti konvergen PENS-ITS

65

Metode Numerik

Algoritma Metode Iterasi Gauss-Seidel

PENS-ITS

66

Metode Numerik

Contoh • Selesaikan SPL di bawah ini menggunakan metode iterasi Gauss-Seidel x1  x2  5 2 x1  4 x 2  14 • Berikan nilai awal : x1 = 0 dan x2 = 0 • Susun persamaan menjadi:

x1  5  x 2 (5,0)

x2 

1 14  2 x1  4

(5,1)

(4,1) (4,3/2)

(7/2,3/2)

(7/2,7/4) PENS-ITS

67

Metode Numerik

Contoh (13/4,7/4)

(13/4, 15/8)

(25/8, 15/8)

(25/8, 31/16)

(49/16, 31/16)

(49/16, 63/32) (97/32, 63/32) (97/32, 127/64)

PENS-ITS

68

Metode Numerik

Contoh : • Selesaikan sistem persamaan berikut:

x1  x 2  x3  6 x1  2 x 2  x3  2 2 x1  x 2  2 x3  10 • Augmented matrik dari persamaan linier simultan tersebut :

1 1 1 6  1 2  1 2    2 1 2 10 PENS-ITS

69

Metode Numerik

Hasil Divergen

PENS-ITS

70

Metode Numerik

Hasil Konvergen

2 x1  x 2  2 x3  10 x1  2 x 2  x3  2 x1  x 2  x3  6

PENS-ITS

71

Metode Numerik

Contoh Penyelesaian Permasalahan Persamaan Linier Simultan •

Mr.X membuat 2 macam boneka A dan B. Boneka A memerlukan bahan 10 blok B1 dan 2 blok B2, sedangkan boneka B memerlukan bahan 5 blok B1 dan 6 blok B2. Berapa jumlah boneka yang dapat dihasilkan bila tersedia 80 blok bahan B1 dan 36 blok bahan B2.

• •

Model Sistem Persamaan Linier : Variabel yang dicari adalah jumlah boneka, anggap: x1 adalah jumlah boneka A x2 adalah jumlah boneka B Perhatikan dari pemakaian bahan : B1: 10 bahan untuk boneka A + 5 bahan untuk boneka B = 80 B2: 2 bahan untuk boneka A + 6 bahan untuk boneka B = 36

•

•

Diperoleh model sistem persamaan linier 10 x1 + 5 x2 = 80 2 x1 + 6 x2 = 36

PENS-ITS

72

Metode Numerik

Contoh •

metode eliminasi Gauss-Jordan

•

Diperoleh x1 = 6 dan x2 = 4, artinya bahan yang tersedia dapat dibuat 6 boneka A dan 4 boneka B. PENS-ITS

73

Metode Numerik

Contoh :Penghalusan Kurva Dengan Fungsi Pendekatan Polinomial • Perhatikan bahwa pada ke-4 titik tersebut dihubungkan dengan garis lurus, sehingga tampak kasar. Untuk menghaluskannya dilakukan pendekatan garis dengan kurva yang dibentuk dengan fungsi pendekatan polinomial. Dari fungsi polinomial yang dihasilkan kurva dapat digambarkan dengan lebih halus. 3

4

2 1

PENS-ITS

74

Metode Numerik

Contoh 2 : • Misalkan pada contoh diatas, 4 titik yang ditunjuk adalah (2,3), (7,6), (8,14) dan (12,10). 4 titik ini dapat didekati dengan fungsi polinom pangkat 3 yaitu : • Bila nilai x dan y dari 4 titik dimasukkan ke dalam persamaan di atas akan diperoleh model persamaan simultan sebagai berikut : • Titik 1  3=8a+4b+2c+d • Titik 2  6 = 343 a + 49 b + 7 c + d • Titik 3  14 = 512 a + 64 b + 8 c + d • Titik 4  10 = 1728 a + 144 b + 12 c + d PENS-ITS

75

Metode Numerik

•

Dengan menggunakan Metode Eliminasi Gauss-Jordan

a = -0,303 b = 6,39 c = -36,59 d = 53,04 y = -0,303 x3 + 6,39 x2 – 36,59 x + 53,04

PENS-ITS

76

Metode Numerik

Latihan Soal • Selesaikan dg Eliminasi Gauss, Eliminasi Gauss Jordan dan Iterasi Gauss Seidel 1.0001x1  1.5 x2  0

6.122 x1  1500.5 x2  1506.622

2 x1  3x2  1

2000 x1  3x2  2003

x1  x2  2 x3  8  x1  2 x2  3x3  1 3 x1  7 x2  4 x3  10

2.51x1  1.48 x2  4.53x3  0.05

8 x1  x2  3x3  2 x4  0

1.48 x1  0.93x2  1.3x3  1.03

2 x1  9 x2  x3  2 x4  1

2.68 x1  3.04 x2  1.48 x3  0.53

x1  3x2  2 x3  x4  2 x1  6 x3  4 x4  3 PENS-ITS

77