Sistem Persamaan Linear

Sistem Persamaan Linear

Muhtadin, ST. MT.

Metode Numerik & Komputasi. By : Muhtadin

Persamaan Aljabar Linear Simultan


9

Menyelesaikan SPL sederhana • Graphical Method

dari kedua persamaan tersebut dapat dicari nilai 𝑥2 :

Sehingga diperoleh garis lurus dengan fungsi 𝑥2 berdasarkan 𝑥1 Metode Numerik & Komputasi. By : Muhtadin

10

Menyelesaikan SPL sederhana - Contoh Permasalahan : Gunakan metode grafik untuk menyelesaikan persamaan

dengan menggunakan 𝑥1 sebagai absis, 𝑥2 dicari dengan dan


11

Menyelesaikan SPL sederhana - Contoh

dan


12

Penggunaan Matriks untuk Sistem Persamaan Linear


13

Contoh Persamaan x  2y  z  8 3x  y  z  2 x  y  2z   3 Untuk memudahkan dalam pemrograman, gunakan indeks, sehingga dapat ditulis ulang :

x1  2 x2 3x1  x2 x1  x2

 x3  x3  2 x3


 8  2  3

Menggunakan Matriks

Dalam Bentuk Matriks :  1 2 1   x1     3 1  1   x2  1 1  2  x    3 


=

 8     2    3  

Eleminasi Gauss • Memerlukan dua Tahap : – Forward elimination, untuk mengurangi matriks sedemikian hingga hanya segitiga bagian atas

       0    0 0   

 adalah angka yang tidak sama & diagonal tidak nol

– Back substitution untuk menemukan bagian yang belum diketahui


Tahap 1 • Eleminasi elemen baris matriks dengan mengalikan menggunakan scaling factor dan menambahkan ke baris yang lain, dilakukan pada LHS dan RHS


Tahap 1 • Jika menyelesaikan persamaan sederhana menggunakan perhitung dapat memilih baris sesuka kita. • Dengan menggunakan pemrograman, harus sistematik – Artinya, kita harus menginstruksikan komputer untuk melakukan perhitungan dengan urutan yang jelas

• Oleh karena itu, kita menggunakan baris 1 (R1) sebagai “pivot equation” untuk membuat nol pada sisa elemen Kolom 1 (C1) • Menggunakan R2 as “pivot equation” untuk membuat nol pada sisa elemen Kolom 1 (C2) • Dst..


Contoh pivot element

R1 R2

R3 R2 – (3/1) *R1

R1 R2 R3

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

pivot equation

 8     2    3  

(R2 adalah baris yang kita rubah)

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

 8      22   3   

Perthatikan bahwa biru untuk pivot element dan merah untuk pivot equation.


R1 R2

R3 R3 - (1/1)*R1

R1 R2

R3

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

 8      22   3   

(R3 adalah baris yang kita rubah)

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


 8      22    11   

R1

R2 R3

new pivot element

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

R3 - (-1/-5)*R2

 8      22    11   

new pivot equation (R3 adalah baris yang kita rubah)

R1 R2 R3

1  1 2   0  5  4   0 0  2.2   


 8      22    6.6   

Hasil Akhir

1   x1  1 2     0  5  4   x2   0 0  2.2   x    3

=

 8      22    6.6   

Tahap 2: Diselesaiakan dengan menggunakan back substitution -2.2 x3 = -6.6 -> x3 = 3 -5x2 + ( -4 * 3 ) = -22 -> x2 = 2 x1 + (2*2) + (3) = 8 -> x1 = 1


Problems • Permasalahan muncul ketika pivot adalah nol – DIVISION BY ZERO – Solusi : Mengubah urutan baris • Muncul error dari pembulatan


Catatan Eleminasi Gauss Dapat menyelesaiakn Sistem Persamaan Linear, • Namun proses back substitution masih memerlukan ketelitian • Kita dapat menyelesaikan permasalahan dengan lebih mudah menggunakan eleminasi lanjutan untuk mengurangi koefisien matriks menggunakan identity matrix • Metode ini disebut : – Gauss-Jordan Elimination


Contoh Kasus The upward velocity of a rocket is given at three different times Time, t

Velocity, v

s

m/s

5

106.8

8

177.2

12

279.2

The velocity data is approximated by a polynomial as:

vt   a1t 2  a2 t  a3 ,

5  t  12.

Find: The Velocity at t=6,7.5,9, and 11 seconds.

Example: Rocket Velocity

Assume Results in a matrix template of the form:

vt   a1t 2  a2t  a3 , 5  t  12.

t12  2 t 2 t32 

t1 t2 t3

1  1 1 

 a1   v1   a   v   2  2   a3    v3  

Using date from the time / velocity table, the matrix becomes:

 25 5 1  a1  106 .8   64 8 1 a   177 .2     2   144 12 1 a3  279 .2 Metode Numerik & Komputasi. By : Muhtadin


Forward Elimination: Step 1

 Row1 Row2    (64)    25  Yields

5 1   a 1   106.81   25  0  4.8  1.56 a    96.21    2   144 12 1  a 3   279.2 




 Row1 Row3    (144 )    25  Yields

5 1   a 1   106.8  25  0  4.8  1.56  a     96.21    2    0  16.8  4.76 a 3   336.0




 Row2  Row3    (16.8)     4.8  Yields

5 1   a 1   106.8  25  0  4.8  1.56 a    96.21    2    0 0 0.7  a 3   0.735  This is now ready for Back Substitution



Back Substitution: Solve for a3 using the third equation

0.7a3  0.735

0.735 a3  0.7 a3  1.050



Back Substitution: Solve for a2 using the second equation

 4.8a2  1.56a3  96.21  96.21  1.56a3 a2   4.8

-96.21  1.561.050  a2  -4.8

a2  19.70 Metode Numerik & Komputasi. By : Muhtadin


Back Substitution: Solve for a1 using the first equation

25a1  5a2  a3  106.8 106 .8  5a 2  a3 a1  25

106.8  519.70   1.050 a1  25

a1  0.2900 Metode Numerik & Komputasi. By : Muhtadin


Solution: The solution vector is

 a1  0.2900  a    19.70   2   a3   1.050 

The polynomial that passes through the three data points is then:

vt   a1t 2  a2 t  a3  0.2900 t 2  19.70t  1.050, 5  t  12



Solution: Substitute each value of t to find the corresponding velocity

v6  0.2900 6  19.706  1.050  129.69 m / s. 2

v7.5  0.2900 7.5  19.707.5  1.050  165.1 m / s. 2

v9  0.2900 9  19.709  1.050  201.8 m / s. 2 v11  0.2900 11  19.7011  1.050 2

 252 .8 m / s. Metode Numerik & Komputasi. By : Muhtadin

Permasalahan yang muncul pada Eleminasi Gauss Permasalahan utama pada Eleminasi gauss adalah : • Pembagian dengan 0 • Error akibat Pembulatan yang besar


35

Pembagian dengan nol

10 x2  7 x3  3 6 x1  2 x2  3x3  11 5 x1  x2  5 x3  9 0 10  7  x1   3  6 2 3   x2   11      5  1 5   x3   9 


36

Pembagian dengan Nol

12 x1  10 x2  7 x3  15 6 x1  5 x2  3x3  14 24 x1  x2  5x3  28 12 10  7  x1  15  6 5 3   x2   14       24  1 5   x3  28


12 10  7  x1   15  0 0 6.5  x2   6.5      12  21 19   x3   2

37

Error akibat pembulatan yang besar Dari persamaan SPL berikut :

15 10  x1   45   20  3  2.249 7   x   1.751    2   1 3   x3   9   5 Nilai Exactnya :

 x1  1  x   1  2    x3  1


38

Error akibat pembulatan yang besar Dari persamaan SPL berikut :

15 10  x1   45   20  3  2.249 7   x   1.751    2   1 3   x3   9   5 Hasil dari eleminasi gauss :

 x1   0.9625   x    1.05   2    x3  0.999995  Dengan Pembulatan 6 Digit


 x1   0.625   x    1.5   2    x3  0.99995  Dengan pembulatan 5 Digit

39

Solusi • Menambah digit significan – Mengurangi besarnya error – Tetap memiliki kemungkinan pembagian dengan Nol • Partial Pivoting – Menghindari Pembagian dengan Nol – Mengurangi galat akibat pembulatan


40

Partial Pivoting

Disetiap awal iterasi ke k pada eleminasi maju, tentukan nilai maksimum

akk , ak 1,k ,................, ank Jika nilai maksimumnya adalah

a pk

Pada baris p, dimana k  p  n, Tukar baris p dengan k.


41

Contoh partial pivoting Contoh dari persamaan berikut :

6 14 5.1 3.7 6   x1   5    0  7 6    1 2 x2 6      12 1 11  x3    8  0 4      x 0 9 23 6 8 9 4      0  17 12 11 43  x5   3  Baris mana yang ditukar ?


42

Contoh partial pivoting

6 14 5.1 3.7 6   x1   5  0  17 12 11 43  x   3    2    12 1 11  x3    8  0 4      x 0 9 23 6 8 9 4       0  7 6 1 2   x5   6


43

Kemungkinan Solusi SPL • Mempunyai solusi yang unik, • Mempunyai banyak solusi • Tidak ada solusi sama sekali.


44

Kemungkinan Solusi SPL

Rinaldi Munir, 2007


45

Kemungkinan Solusi SPL

Rinaldi Munir, 2007


46

Eleminasi Gauss Jordan


47

Background Rangkuman Gaussian Elimination • Dapat menyelesaikan / memberikan solusi dari sistem persamaan linear • Namun masih memerlukan back substitution • Dapat digantikan dengan menggunakan elminasi lanjutan untuk menghasilkan menemukan koefisien matriks – Matriks Identitas • Metode tersebut dinamakan : Gauss-Jordan Elimination


48

Hasil Akhir yang Diharapkan

 1 0 0   x1     0 1 0   x2  0 0 1  x     3

Didapatkan vector hasil berupa

a   b c  

=

a   b c  

yang merupakan solusi SPL!


49

Gauss-Jordan Elimination Misalkan diketahui sebuah sistem persamaan linear :

 2 x  4 y  5z  36    3x  5 y  7 z  7 5 x  3 y  8 z  31  Augmented matriks dari persamaan tersebut adalah :

36   2 4 5  3 5 7 7    3  8  31  5 50

Gauss-Jordan Elimination Langkah 1: Eleminasi koef. x pada persamaan 2 dan 3.

36   2 4 5  3 5 7 7    3  8  31  5

5 36  2  4 0  1 14.5 61    0 13  20.5  121

 2 x  4 y  5z  36    3x  5 y  7 z  7 5x  3 y  8 z  31 

 2 x  4 y  5z  36    y  14.5z  61 13 y  20.5z  121  51

Gauss-Jordan

Elimination

Langkah 2: Eleminasi koef. y pada persamaan ketiga.

13R’2+R’3

R’’3

36  2  4 5 0  1 14.5 61    0 0 168 672 

2 x  4 y  5z  36    y  14.5z  61  168 z  672 

Langkah 3: 0.5R’1

R’1

-R’2

R’’2

(1/168)R’’3

R’’’3

1  2 2.5 18  0 1  14.5  61   1 4  0 0

 x  2 y  2.5z  18   y  14.5z  61  z4 

52

Gauss-Jordan Elimination Langkah 4: Eleminasi z pada persamaan kedua

1  2 2.5 18  0 1  14.5  61   1 4  0 0

 x  2 y  2.5z  18   y  14.5z  61  z4 

row2  ( Row 3)  (14.5)  ( Row 2)

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

 x  2 y  2.5 z  18  y  3   z4  53

Gauss-Jordan Elimination Langkah 5-1: Eleminasi y pada persamaan kesatu

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

 x  2 y  2.5 z  18  y  3   z4 

( Row 2)  (2)  ( Row 1)  New Row1

1 0 2.5 12  0 1 0  3   0 0 1 4 

 x  2.5 z  12   y  3  z4  54

Gauss-Jordan Elimination Langkah 5-2: Eleminasi z pada persamaan pertama

1 0 2.5 12  0 1 0  3   0 0 1 4 

 x  2.5 z  12   y  3  z4 

( Row 3)  (2.5)  ( Row 1)  New Row1

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

 x2   y  3  z4  55

Hasil Lain yang Dicapai Cara tersebut dapat juga digunakan untuk menemukan inverse dari sebuah matriks

• Dari perkalian matiks, kita tahu bahwa : – CC-1 = I • Jadi, jika kita merubah – C menjadi matriks I (Menggunakan operasi baris) • Saat yang bersamaan kita akan melakukan operasi – I menjadi C –1 (menggunakan operasi baris yang sama)


56

Invers Method


57

Invers Matriks

A  a11 a  21  ...  a n1



J I  G  I

a12 a 22 ... an 2

... a1n ... a2 n ... ... ... a nn

A 1



1 0 ... 0

0 1 ... 0

... ... ... ...

0 1 0   0   ... ...   1 0

0 1 ... 0

... ... .... ...

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


0 p11 0 p21 ... ... 1 p n1

p12 p 22 ... pn 2

... p1n  ... p2 n  ... ...   ... p nn 

2 1 0 0 0  1 0 1  5  3 1 0 0 0 0 0.4  0.2 1 0 1 0 1  0 1 0  0.2 0.6  58

Iterative Method

Gauss - Seidel


59

Iterative Method

• Gauss (dan Gauss-Jordan) memunculkan banyak error akibat pembulatan. • Iterasi diawali dengan memberikan nilai perkiraan untuk semua variabel. • Iterasi berhenti jika :

x

( k 1) (k ) i i ( k 1) i

x

x

  , i


 x1( 0)   x ( 0)  x0   2  ...   x ( 0)   n 

Gauss-Seidel Method a11 x1  a12 x2  ...  a1n xn  b1 a21 x1  a22 x2  ...  a2 n xn  b2 ... an1 x1  an 2 x2  ...  ann xn  bn x1( k 1)

b1  a12 x2( k )  ...  a1n xn( k )  a11

x2( k 1)

b2  a21x1( k 1)  a23 x3( k )  ...  a2 n xn( k )  a22

xn( k 1)

bn  an1 x1( k 1)  an 2 x2( k 1)  ...  ann1 xn( k1)  ann


Contoh

4 x1  x2  x3  7 4 x1  8 x2  x3  21  2 x1  x2  5 x3  15 (0) 1

x

 1; x

( 0) 2

 2; x

(0) 3

 2; x ( k 1) 1

x

( k 1) 2

x

( k 1) 3


7  x 2( k )  x3( k )  4 21  4 x1( k 1)  x3( k )  8 15  2 x1( k 1)  x 2( k 1)  5

SELESAI


63

Sistem Persamaan Linear

Recommend Documents