aljabar

Oleh : Moch. Agus Choiron, ST., MT.
Bentuk umum persamaan aljabar linear serentak :
a11 x1 + a 12 x2 + ........ + a 1n xn = b 1 x  b 
 a11 a12 a1n   1   1
.........
x b 2 

a2n   2 
a21 x1 + a 22 x2 + ........ + a 2n xn = b 2 a21 a22 .........    
. = . 

 .
.  .   . 

an1 an2 ......... ann     
.    x  b 
 n   n
an1 x1 + a n2 x 2 + ........ + ann xn = b n
dimana a adalah koefisien-koefisien konstan ta, b adalah konstanta-
konstanta 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 persamaan-
persamaan.
Strategi : mengalikan persamaan dengan konstanta agar salah satu
bilangan unknown akan tereliminasi bilamana dua
persamaan digabungkan.
Kebutuhan : pemahaman Operasi Matrik
Skema langkah eliminasi Gauss
...... (E1)
a11 a12 a13   x 1  b1 
   
 ...... (E2)
a 23  x 2  =
a 21 a 22 b 2 
a 33  x 3  b  ...... (E3)
a 31 a 32
    3
Forward
Elimination
a11 a12 a13   x 1   b1 
Upper Triangular
   

a'23  x 2  =
 0 a'22 b '2  System
a' '33  x 3  b'' 
 0 0
    3
Back
Substitution
x3 = b’’3 / a’’33
x2 = (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
BAB III. Pers. Aljabar Linear Serentak
Oleh : Moch. Agus Choiron, ST., MT.
J Langkah eliminasi maju :
1. Eliminasikan x1 dari (E 2) dan (E 3), asumsi a11 ≠ 0
m21 = a21 ; m31 = a31
e
a11 a11
kurangkan (m21 x (E 1)) pada (E 2) dan kurangkan (m 31 x (E 1)) pada
e
(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
m32 = a'32
e
a'22
kurangkan (m32 x (E 2)) pada (E 3), sehingga :
e
a 11 x1 + a 12 x 2 + a 13 x 3 = b1
a’22 x2 + 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
(n- 1)
xn = bn
Sehingga dapat dirumuskan :
a(n- 1)
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
b(i - 1) − ∑ a(i - 1)x j
i ii
Sehingga dapat dirumuskan : xi = j = i +1
a(i - 1)
ii
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
BAB III. Pers. Aljabar Linear Serentak
Oleh : Moch. Agus Choiron, ST., MT.
Untuk kemudahan dapat dipakai matrik dalam bentuk kombinasi yang
disebut dengan Augmented Matrix (matrik yang diperbesar).
a a12 a13 b1
 11 
a21 a22 a23 b2
a a32 a33 b3
 31 
Masalah è 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  27 6 -1 85 
   
 6 15 2 72  E 2 - 6/27 E 1  0 13,667 2,222 53,111 
 1 1 54 110 E 3 - 1/27 E 1  0 0,778 54,037 106,852
   
27 6 -1 85 
 
 0 13,667 2,222 53,111 
E 3 – 0,778/13,667 E 2  0 
0 53,911 103,829
 
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
Program Semi QUE IV Jurusan Teknik Mesin Unibraw 10
BAB III. Pers. Aljabar Linear Serentak
Oleh : Moch. Agus Choiron, ST., MT.
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 a12 a13 b1  ...... (E1)
 11 
a 21 a22 a23 b 2  ...... (E2)
a a32 a33 b 3 
 31  ...... (E3)
Elimination
*

b1 
1 0 0 x1 = b*1
 NO Back
Matrik  * x2 = b*2
0 1 0 b 2  Substitution
Satuan
x3 = b*3
 
b*
0 0 1 3
 
Selesaikan soal yang sama pada metode Eliminasi Gauss :
27 6 - 1 85  1/27 E 1  1 0,222 - 0,337 3,148 
   
 6 15 2 72  6 15 2 72 
 1 1 54 110 1 110 
1 54
   
 1 0,222 - 0,337 3,148   1 0,222 - 0,337 3,148 
E 2 – 6 E 1 0 13,667 2,222 53,111 1/13,667 E 2
  
0 1 0,163 3,886 
 
E 3 – E 1 0 0,778 54,037 106,852  0 0,778 54,037 106,852 
   
E 1 – 0,222 E 2  1 0 - 0,073 2,285   1 0 - 0,073 2,285
   
0 1 0,163 3,886  0 1 0,163 3,886
0 0 53,911 103,828 1/53,911 E 3 0 0 1,926
1
E 3 – 0,778 E 2    
x1 = 2,426
 1 0 0 2,426 
E 1 –(- 0,073 E 3)
  x2 = 3,572
0 1 0 3,572
E 2 – 0,163 E 3  
x3 = 1,926
0 0 1 1,926 
 
Program Semi QUE IV Jurusan Teknik Mesin Unibraw 11
BAB III. Pers. Aljabar Linear Serentak
Oleh : Moch. Agus Choiron, ST., MT.
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
BAB III. Pers. Aljabar Linear Serentak
Oleh : Moch. Agus Choiron, ST., MT.
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 - x y z
1 3,15 3,54 1,91
2 2,43 3,57 1,926
3 2,423 3,574 1,926
4 2,425 3,573 1,926
5 2,425 3,573 1,926
Jadi ha sil penyelesaiannya adalah :
x = 2,425 ; y = 3,573 dan z = 1,926
Program Semi QUE IV Jurusan Teknik Mesin Unibraw 13
BAB III. Pers. Aljabar Linear Serentak
Oleh : Moch. Agus Choiron, ST., MT.
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 :
n
∑ aij ; j ≠ i dan i = 1, 2, ....., N
aii >
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}
Maju
{D}
Pensubtitusian
[U] {X} = {D}
Mundur
{X}
Program Semi QUE IV Jurusan Teknik Mesin Unibraw 14
BAB III. Pers. Aljabar Linear Serentak
Oleh : Moch. Agus Choiron, ST., MT.
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
j −1
∑ lik .ukj
lij = a ij - ; i = j, j+1, ... , n
k =1
j −1
a jk − ∑ l ji .u ik
n−1
∑ lnk .ukn
i =1
u jk = ; k = j+1, j+2, ... ,n dan lnn = ann -
l jj k =1
3. Mencari matrik {B’} dengan aturan berikut :
i −1
b i − ∑ lij .b' j
b1 j =1
b’1 = ; b’i = untuk i = 2, 3, ... , n
l11 lii
4. Membentuk Augmented Matrix {UB’} dan penyelesaiannya diperoleh :
n
∑ u jk
xn = b’n dan x j = b’j - xk
k = j +1
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
j =1
Untuk baris ke-k : lki = ; untuk i = 1,2, ..., k-1
lii
k −1
akk − ∑ lkj 2
lkk =
j =1
Program Semi QUE IV Jurusan Teknik Mesin Unibraw