Bentuk umum persamaan aljabar linear serentak :

BAB III. Pers. Aljabar Linear Serentak Oleh : Moch. Agus Choiron, ST., MT.

Bentuk umum persamaan aljabar linear serentak : a11 x1 + a 12 x2 + ........ + a 1n xn = b 1

 a11  a21  .  an1

a21 x1 + a 22 x2 + ........ + a 2n xn = b 2 . . an1 x1 + a n2 x 2 + ........ + ann xn = b n

a12 a22 an2

x  a1n   1  x a2n   2 

b   1 b 2  .........   . = .        .  .  ......... ann       xn  b n  .........

dimana a adalah koefisien-koefisien konstan ta, b adalah konstantakonstanta dan n adalah banyaknya persamaan. Penyelesaian persamaan linear serentak dapat dilakukan cara : 1. Eliminasi è Eliminasi Gauss, Gauss Jordan. 2. Iterasi è Iterasi Jacobi, Gauss siedel. 3. Dekomposisi è Dekomposisi lower-upper (LU), Cholesky.

1. Eliminasi Gauss è Eliminasi bilangan unknown dengan menggabungkan persamaanpersamaan. Strategi : mengalikan persamaan dengan konstanta agar salah satu bilangan unknown akan tereliminasi bilamana dua persamaan digabungkan. Kebutuhan : pemahaman Operasi Matrik Skema langkah eliminasi Gauss a11 a12  a 21 a 22 a 31 a 32

a13   x 1    a 23  x 2  = a 33  x 3 

b1    b 2  b   3

…… (E1) …… (E2) …… (E3)

Forward Elimination a11 a12   0 a'22  0 0

a13   x 1    a'23  x 2  = a' '33  x 3 

 b1    b '2  b''   3

Upper Triangular System

Back Substitution x3 x2

= b’’3 / a’’33

= (b’2- a’ 23 x3) / a’22

x1 = (b 1 - a 12 x2 - a13 x3) / a 11 Program Semi QUE IV Jurusan Teknik Mesin Unibraw

8


J Langkah eliminasi maju : 1. Eliminasikan x1 dari (E 2) dan (E 3), asumsi a11 ≠ 0 e

m21 = a21 ; m31 = a31

e

kurangkan (m21 x (E 1)) pada (E 2) dan kurangkan (m 31 x (E 1)) pada

a11

a11

(E 3), sehingga : a11 x 1

+ a 12 x 2

+ a 13 x3

= b1

a’22 x 2

+ a’23 x 3

= b’2

a’32 x 2

+ a’33 x 3

= b’3

NB : tanda petik satu berarti persamaan telah dimodifikasi satu kali. 2. Eliminasikan x2 dari (E 3), asumsi a22 ≠ 0 e

m32 = a'32

e

kurangkan (m32 x (E 2)) pada (E 3), sehingga :

a'22

a 11 x1

+ a 12 x 2 a’22 x2

+ a 13 x 3

= b1

+ a’23 x 3 = b’2 a’’33 x3 = b’’ 3

NB :

tanda petik dua berarti persamaan telah dimodifikasi dua kali.

J Langkah substitusi mundur : x3

=

b’’ 3 / a’’ 33

Sehingga dapat dirumuskan :

(n- 1) xn = bn - 1) a(n nn

Untuk menghitung x sisanya : x2 = (b’2 - a’ 23 x 3) / a’22 x1

=

(b 1 - a 12 x2 - a 13 x3) / a11 n

Sehingga dapat dirumuskan :

xi =

b(ii - 1) − ∑ a(iii - 1)x j j = i +1

a(iii - 1)

dengan i = n – 1, n – 2 , …. , 1 NB :

Persamaan (E 1) disebut Pivot Equation, a 11 disebut koefisien Pivot dan operasi perkalian baris pertama dengan a 21/a 11 disebut sebagai Normalisasi.

Program Semi QUE IV Jurusan Teknik Mesin Unibraw

9


Untuk kemudahan dapat dipakai matrik dalam bentuk kombinasi yang disebut dengan Augmented Matrix (matrik yang diperbesar). a  11 a21 a  31

Masalah è

a12 a13 b1  a22 a23 b2 a32 a33 b3

harus menghindari pembagian dengan nol, sehingga muncul sebutan untuk metode ini yaitu Eliminasi Gauss Naif.

Teknik untuk memperbaiki penyelesaian Eliminasi Gauss : 1. Pivoting Ø Sebelum tiap baris dinormalkan, maka dilakukan penentuan koefisien terbesar yang tersedia. Kemudian baris-baris tersebut dipertukarkan sehingga elemen terbesar tersebut merupakan elemen pivot. 2. Scaling Ø berguna dalam peminimalan galat pembulatan untuk kasus dimana beberapa persamaan mempunyai koefisien -koefisien yang jauh lebih besar dari lainnya. Contoh soal : Selesaikan persamaan simulta n berikut ini. 27 x1 + 6 x2 – x 3 = 85 ….. (1a) 6 x1 + 15 x 2 + 2 x3 = 72 ….. (1b) x1 + x2 + 54 x 3 = 110 ….. (1c) Penyelesaian : Pakai matrik dalam bentuk Augmented Matrix (matrik yang diperbesar). 27 6 - 1 85     6 15 2 72  E 2 - 6/27 E 1  1 1 54 110 E 3 - 1/27 E 1

6 -1 85  27    0 13,667 2,222 53,111   0 0,778 54,037 106,852

6 -1 85  27    0 13,667 2,222 53,111 0 53,911 103,829 E 3 – 0,778/13,667 E 2  0

dengan menggunakan substitusi mundur akan diperoleh x1, x 2, dan x3. Ü x3 = 103,829 / 53,911 = 1,926 Ü 13,667 x2 + 2,222 x 3 = 53,111 à x2 = 3,573 Ü 27 x 1 + 6 x2 - x3 = 85

à x1 = 2,425


10


2. Eliminasi Gauss-Jordan è Merupakan Variasi dari Eliminasi Gauss dengan kebutuhan untuk menghitung matrik invers. Strategi : Langkah eliminasi menghasilkan matrik satuan, sehingga tidak diperlukan proses substitusi mundur. Skema langkah eliminasi Gauss-Jordan a  11 a 21 a  31

a12 a13 b1   a22 a23 b 2  a32 a33 b 3 

…… (E1) …… (E2) …… (E3)

Elimination

Matrik Satuan

 1  0  0 

0

0

1

0

b 1*   b*

0

1

b *3 

2 



NO Back Substitution

x1 = b*1 x2 = b*2 x3 = b*3



Selesaikan soal yang sama pada metode Eliminasi Gauss : 27 6 - 1 85  1/27 E 1    6 15 2 72   1 1 54 110

 1 0,222 - 0,337 3,148   2 72  6 15  1 1 54 110 

 1 0,222 - 0,337 3,148  E 2 – 6 E 1 0 13,667 2,222 53,111 1/13,667 E 2 E 3 – E 1 0 0,778 54,037 106,852

E 1 – 0,222 E 2  1 0 - 0,073 E 3 – 0,778 E 2

2,285    3,886  0 1 0,163 0 0 53,911 103,828 1/53,911 E 3

E 1 –(- 0,073 E 3) E 2 – 0,163 E 3

 1 0 0 2,426   0 1 0 3,572 0 0 1 1,926


 1 0,222 - 0,337 3,148    1 0,163 3,886  0 0 0,778 54,037 106,852  1 0 - 0,073 2,285   0 1 0,163 3,886 0 0 1 1,926

x1 = 2,426 x2 = 3,572 x3 = 1,926

11


3. Iterasi Gauss-Siedel Bentuk umum persamaan linear serentak : a 11 x1 + a12 x 2 + a 13 x3 + ................... + a1n x n = b1 a 21 x1 + a 22 x 2 + a 23 x3 + ................... + a2n x n = b2 . . . a n1 x1 + a n2 x 2 + a n3 x 3 + .................. + ann x n = b n Dapat diubah bentuknya menjadi : 1 x1 = ( b1 - a12 x2 + a 13 x 3 - .................... - a1n x n) a11 1 x2 = ( b2 - a21 x 1 + a 23 x3 - .................... - a2n x n) a22 1 x3 = ( b3 - a31 x 1 + a 32 x2 - .................... - a3n x n) a 33 1 xn = ( bn - an1 x 1 - an2 x 2 - .................... - an(n- 1) x( n- 1)) ann Langkah-langkah Iterasi Gauss-Siedel 1. Asumsikan x2 = x3 = ….. = xn = 0, sehingga dapat diperoleh : b x1 = 1 a11 2. Hasil dari “x1” tersebut dimasukkan persamaan 2 untuk mendapatkan harga x2 (dimana x 3 = … = xn = 0), maka akan diperoleh : 1 x2 = ( b2 - a21 x 1 ) a 22 3. Langkah 1 dan 2 dilakukan terus sampai diperoleh nilai xn dan selesailah proses iterasi yang pertama. Kemudian h asil proses tersebut dimasukkan kembali pada persamaan untuk mendapatkan harga “unknown” dari x 1, x 2, x3. ….. xn pada proses iterasi kedua, ketiga dan seterusnya. 4. Proses iterasi berakhir bila hasil dari iterasi terakhir sama dengan atau hampir sama dengan iterasi sebelumnya. Ini merupakan kelemahan metode iterasi gauss-siedel yaitu proses akhir iterasi menjadi meragukan. Contoh soal : Selesaikan persamaan simultan berikut : 27 x + 6 y – z = 85 ….. (1a) 6 x + 15 y + 2 z = 72 ….. (1b) x + y + 54 z = 110 ….. (1c) Program Semi QUE IV Jurusan Teknik Mesin Unibraw

12


Penyelesaian : Persamaan di atas dapat diubah bentuknya menjadi : 1 x= ( 85 - 6 y + z ) …… (2a) 27 1 y= ( 72 - 6 x - 2 z ) …… (2a) 15 1 z= ( 110 - x - y ) …… (2a) 54 : Iterasi pertama 1. Asumsikan y = z = 0, sehingga dari persamaan (2a) akan diperoleh : 85 x1 = = 3,15 27 2. Hasil dari “x1” tersebut dimasukkan persamaan (2b) untuk mendapatkan harga y 1 (asumsi z = 0) 1 y1= ( 72 - 6 (3,15) ) = 3,54 15 3. Masukkan hasil “x 1” dan “y 1” ke dalam persamaan (2c) 1 z1 = ( 110 – 3,15 – 3,54) = 1,91 54 : Iterasi kedua 1 x2 = ( 85 - 6 (3,54) + 1,91 ) = 2,43 27 1 y2= ( 72 - 6 (2,43) – 2 (1 ,91) ) = 3,57 15 1 z2 = ( 110 – 2,43 – 3,57) = 1,926 54 : Iterasi selanjutnya dapat ditabelkan sebagi berikut : Iterasi ke 1 2 3 4 5

x 3,15 2,43 2,423 2,425 2,425

y 3,54 3,57 3,574 3,573 3,573

z 1,91 1,926 1,926 1,926 1,926

Jadi ha sil penyelesaiannya adalah : x = 2,425 ; y = 3,573 dan z = 1,926


13


4. Iterasi Jacobi è Melalui proses iterasi dengan menggunakan persamaan : n a b xi(n+1) = i - ∑ ij xj (n) ;j ≠ i aii j =1 aii Keuntungan metode ini adalah langkah penyelesaiannya yang sederhana, sedangkan kelemahannya adalah : 1. Proses iterasinya lambat. Terutama untuk persamaan linear serentak dengan ordo tinggi. 2. Hanya dapat digunakan menyelesaikan persamaan linear serentak yang memenuhi syarat berikut : aii >

n

∑ aij

; j ≠ i dan i = 1, 2, ….., N

j =1

5. Dekomposisi LU è Dengan cara membentuk matrik segitiga atas (Upper) dan matrik segitiga bawah (Lower) dari matrik koefisien A serta membentuk vektor matrik dari matrik hasil dengan aturan tertentu. Kelebihannya adalah sangat efektif untuk menyelesaikan persamaan linear serentak ordo tinggi, dengan hasil yang sangat mendekati nilai eksaknya. Tentu saja konsekuensinya metode ini memerlukan cara yang cukup kompleks. [A] {X} = {B} Dekomposisi [U]

[L] [L] {D} = {B} {D}

Maju Pensubtitusian

[U] {X} = {D} {X}

Mundur


14


Langkah -langkah Dekomposisi LU 1. Membentuk matrik koefisien [A], matrik variabel {X} dan matrik hasil {B} dari persamaan simultan. [A] {X} = {B} 2. Mencari matrik segitiga bawah [L] dan matrik segitiga atas [U] dari matrik koefisien [A] dengan aturan berikut : li1 = a i1 ; i = 1,2, … , n a a u 1j = 1j = 1j ; j = 2,3, … , n l11 a11 - untuk j = 2,3, … , n-1 lij = a ij -

j −1

∑ lik .ukj

; i = j, j+1, … , n

k =1 j −1

u jk =

a jk − ∑ l ji .u ik i =1

l jj

; k = j+1, j+2, … ,n dan lnn = ann -

3. Mencari matrik {B’} dengan aturan berikut :

n−1

∑ lnk .ukn

k =1

i −1

b i − ∑ lij .b' j

b1 j =1 ; b’i = untuk i = 2, 3, … , n l11 lii 4. Membentuk Augmented Matrix {UB’} dan penyelesaiannya diperoleh :

b’1 =

xn = b’n

dan

n

∑ u jk

x j = b’j -

k = j +1

xk

6. Dekomposisi Cholesky Didasarkan bahwa matrik simetrik yaitu matrik dengan aij = aji (untuk semua i dan j) dapat didekomposisi dalam bentuk : [A] = [L] [L] T yaitu faktor-faktor segitiga yang dihasilkan saling bertranspose. Dimana suku-suku persamaan tersebut dapat dikalikan dan ditetapkan satu sama dengan yang lain. Hasilnya dapat dinyatakan dalam hubungan berulang. i −1

aki − ∑ lij − ukj

Untuk baris ke-k :

lki =

j =1

lkk =

akk − ∑ lkj2

lii

; untuk i = 1,2, …, k-1

k −1 j =1


15

Bentuk umum persamaan aljabar linear serentak :

Recommend Documents