-
24/05/2007
1
PENYELESAIAN PERSAMAAN LINIER SIMULTAN Modul 3
Persamaan Linier Simultan
Persamaan linier simultan adalah suatu bentuk persamaan-persamaan yang secara bersama-sama menyajikan banyak variabel bebas
Bentuk persamaan linier simultan dengan m persamaan dan n variabel bebas
aij untuk i=1 s/d m dan j=1 s/d n adalah koefisien atau persamaan simultan
xi untuk i=1 s/d n adalah variabel bebas pada persamaan simultan
-
24/05/2007
2
Persamaan Linier Simultan Penyelesaian persamaan linier simultan adalah
penentuan nilai xi untuk semua i=1 s/d n yang memenuhi semua persamaan yang diberikan.
AX = B Matrik A = Matrik Koefisien/ Jacobian. Vektor x = vektor variabel vektor B = vektor konstanta.
=
nnmnmm
n
n
b
bb
x
xx
aaa
aaaaaa
.........
..................
2
1
2
1
21
22221
11211
Augmented Matrix matrik yang merupakan perluasan matrik A dengan
menambahkan vector B pada kolom terakhirnya, dan dituliskan:
Augmented (A) = [A B]
mmnmmm
n
n
baaaa
baaaabaaaa
.....................
...
...
321
22232221
11131211
-
24/05/2007
3
Kemungkinan Solusi PL Persamaan Linier Simultan atau Sistem Persamaan Linier
mempunyai kemungkinan solusi :
310
300110
111lim
110
213132111
GaussinasiE
06
4
000330
211lim
624
321112211
GaussinasiE
y
x 1
-1
1. Solusi banyak
y
x 1
-1
2. Tidak ada solusi
y
x 1
-1
3. Solusi tunggal
16
4
000330
211lim
724
321112211
GaussinasiE
Penyelesaian Persamaan Simultan Eliminasi
Gauss Gauss Jordan
Dekomposisi Lower-Upper (LU)
Iterasi Jacobi Gauss Siedel
-
24/05/2007
4
Theorema 4.1. Suatu persamaan linier simultan mempunyai penyelesaian tunggal bila memenuhi syarat-syarat sebagai berikut. Ukuran persamaan linier simultan bujursangkar, dimana
jumlah persamaan sama dengan jumlah variable bebas. Persamaan linier simultan non-homogen dimana
minimal ada satu nilai vector konstanta B tidak nol atau ada bn 0.
Determinan dari matrik koefisien persamaan linier simultan tidak sama dengan nol.
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 :
nnnn
n
n
b
bb
aaa
aaaaaa
...
...............
...
...
2
1
2n1
22221
11211
-
24/05/2007
5
Metode Eliminasi Gauss ubah matrik menjadi matrik segitiga atas atau segitiga
bawah dengan menggunakan OBE (Operasi Baris Elementer).
nnnnnn
n
n
n
baaaa
baaaabaaaabaaaa
.....................
...
...
...
321
33333231
22232221
11131211
nnn
n
n
n
dc
dccdcccdcccc
...000..................
...00
...0
...
3333
222322
11131211
Operasi Baris Elementer Metode dasar untuk menyelesaikan Sistem Persamaan
Linier adalah mengganti sistem yang ada dengan sistem yang baru yang mempunyai himp solusi yang sama dan lebih mudah untuk diselesaikan
Sistem yang baru diperoleh dengan serangkaian step yang menerapkan 3 tipe operasi. Operasi ini disebut Operasi Baris Elementer
-
24/05/2007
6
Metode Eliminasi Gauss Sehingga penyelesaian dapat diperoleh dengan:
( )
( )( )nn
nn
nnnnnn
n
nn
nn
xcxcxcdc
x
xcxcxcdc
x
dxcc
x
cdx
113212111
1
2424323222
2
1,11,1
1
...31
...1.....................................
1
=
=
+=
=
Contoh : Selesaikan sistem persamaan berikut:
Augmented matrik dari persamaan linier simultan tersebut :
102222
6
321
321
321
=++=+=++
xxxxxxxxx
1021221216111
-
24/05/2007
7
Contoh : Lakukan operasi baris elementer
13
12
2BBBB
20104210
6111
23 BB +
62004210
6111
Contoh : Penyelesaian :
( )( ) 1326
11
23)2(411
326
1
2
3
==
==
==
x
x
x
-
24/05/2007
8
Algoritma Metode Eliminasi Gauss
Metode Eliminasi Gauss Jordan
Metode ini merupakan pengembangan metode eliminasi Gauss, hanya saja augmented matrik, pada sebelah kiri diubah menjadi matrik diagonal
Penyelesaian dari persamaan linier simultan diatas adalah nilai d1,d2,d3,,dn dan atau:
nnnnnn
n
n
n
baaaa
baaaabaaaabaaaa
.....................
...
...
...
321
33333231
22232221
11131211
nd
ddd
1...000..................
0...1000...0100...001
3
2
1
nn dxdxdxdx ==== ,....,,, 332211
-
24/05/2007
9
Contoh :
Selesaikan persamaan linier simultan:
Augmented matrik dari persamaan linier simultan
Lakukan operasi baris elementer
8423
21
21
=+=+xx
xx
842311
110201
110311
2/2
220311
2
21
12
BB
B
bB
Penyelesaian persamaan linier simultan : x1 = 2 dan x2 = 1
Contoh :
0 563 7 172
9 2
=+=
=++
zyxzyzyx
0563 134292
=+=+=++
zyxzyxzyx
056313429211
0563177209211
B2-2B1
B2-2B1
B3-3B1
B3-3B1
-
24/05/2007
10
Example 3 Using Elementary row Operations(2/4)
0 113
9 2
217
27
==
=++
zyzyzyx
27113 177 2
9 2
==
=++
zyzyzyx
271130177209211
27113010
9211
217
27
B2
B2 B3-3B2
B3-3B2
Example 3 Using Elementary row Operations(3/4)
3
9 2
217
27
==
=++
zzyzyx
23
21
217
27
9 2
==
=++
zzyzyx
23
21
217
27
0010
9211
3100
109211
21727
-2 B3
-2 B3
B1- B2
B1- B2
-
24/05/2007
11
Example 3 Using Elementary row Operations(4/4)
3 2
1
===
zy
x
3
217
27
235
211
==
=+
zzyzx
3100
1001
217272
352
11
310020101001
Solusi x = 1, y=2 dan z=3
B2 + 7/2 B3
B1 - 11/2 B3
B2 + 7/2 B3
B1 - 11/2 B3
Algoritma Metode Eliminasi Gauss-Jordan
-
24/05/2007
12
METODE DEKOMPOSISI LU
Metode Dekomposisi L-U
-
24/05/2007
13
Langkah-langkah Dekomposisi L-U 1) Membentuk matrik koefisien A, matrik variabel x,dan
matrik hasil B dari persamaan serentak/simultan 2) Mencari matrik segitiga bawah(matrik L) dan matrik
segitiga atas (Matrik U) dari matrik koefisien dengan aturan
ii
i
kkjikij
ij
j
kkjikijij
jjj
ii
l
ulau
ulal
aa
la
u
al
=
=
=
=
===
1
1
1
1
11
1
11
11
11
.
.
njni
ana
,..,4,3,2,..,3,2,1:dim
==
Langkah-langkah Dekomposisi L-U 3) Kemudian mencari vektor matriks hasil (matrik D)
dengan aturan
4) Membentuk augmented matrik (UD) dan mencari penyelesaian dengan aturan
jj
j
kkdjkj
jl
lbd
lbd
=
=
=1
1'.
'
11
11'
+=
==
n
jkkjkjj
nn
xudx
dx
1
.'
'
-
24/05/2007
14
Contoh Carilah persamaan serentak/simultan di bawah ini dengan
metode dekomposisi L-U
36941432
6
321
321
321
=++=++
=++
xxxxxx
xxx
Contoh
Langkah 1
Membentuk matrik koefisien, matrik variabel dan matrik hasil
Langkah 2
Mencari matrik L dan Matrik U dari matrik koefisien A sbb
=
36146
941321111
3
2
1
xxx
=
10010
1000
23
1312
333231
2221
11
333231
232221
131211
uuu
lllll
l
aaaaaaaaa
-
24/05/2007
15
Langkah 2
Diagonal utama matrik U, semuanya bernilai 1 pada j=1, didapatkan:
Pada i=1 didapatkan
111
3131
2121
1211
======
alalal ( )
( )
( )
( )
=
=
=
=
===
==
=
===
===
==
==
2
12321333333
22
132123
22
1
123
23
1
11231323232
1
11221222222
11
1313
11
1212
2..
2..
3..
1..
1
1
kkjik
kkjik
kkjik
kkjik
ulaulal
lula
l
ulau
ulaulal
ulaulal
aau
aau
Langkah 2 Jadi Matriks L dan U adalah
Kemudian mencari matriks D sebagai berikut
=
=
100210111
231011001
udanl
32
30362
)8.36.1(36)''('
81
6141
)6.1(14''
616'
33
2'321'3133
22
1'2122
11
11
==+=+=
====
===
ldldlbd
ldlbd
lbd
Jadi Matriks D adalah
386
-
24/05/2007
16
Langkah 3 Menyusun augmented matriks [UD], yaitu :
Dan penyelesaian adalah :
=
310082106111
'UD
1)..('2.'
3'
31321211
32322
33
=+===
==
xuxudxxudx
dx
METODE ITERASI JAKOBI
-
24/05/2007
17
Tujuan Metode iterasi Jacobi adalah metode penyelesaian SPL
melalui proses iterasi dengan menggunakan persamaan
Keuntungan: Langkah penyelesaian lebih sederhana dibandingkan metode
invers, determinan atau metode dekomposisi L-U
Keterbatasan: Proses iterasi lambat, terutama untuk SPL orde tinggi Metode ini hanya dapat digunakan untuk menyelesaikan SPL yg
memenuhi syarat persamaan
( ) =
+ =n
j
nj
ii
ij
ii
ini ijdenganxa
aahx
1
1
=
=>n
jijii nijdenganaa
1
,...,2,1,1
Algoritma Jacobi Langkah 1
Memeriksa susunan SPL apakah memenuhi syarat atau tidak. Jika tidak memenuhi syarat maka susunan SPL diubah sampai
memenuhi syarat
Langkah 2 Menyusun matrik koefisien, matrik variabel dan matriks hasil
Langkah 3 Menentukan titik variabel x awal kemudian melakukan iterasi
menggunakan rumus diatas sampai didapatkan nilai variabel x yang sama atau hampir sama
-
24/05/2007
18
Contoh Carilah penyelesaian SPL dibawah ini dengan iterasi
Jacobi
88427
1292
321
321
321
=+=+
=++
xxxxxxxxx
Langkah Penyelesaian
Langkah 1
Karena susunan SPL tidak memenuhi syarat maka susunan diubah menjadi Baris 3 ditukar dengan baris 1
Langkah 2
Mencari matriks koefisien, matrik variabel, dan matrik hasil
1292427
88
321
321
321
=++=+
=+
xxxxxx
xxx
=
=
=
124
8
921271118
3
2
1
h
xxx
xA
-
24/05/2007
19
Langkah 3 Menentukan titik awal variabel, misalnya diambil
Iterasi pertama n=1 adalah :
( ) ( ) ( ) 0131
21
1 === xxx
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( ) 333,10920
91
912
571,007
207
174
10810
81
88
13
33
3211
33
31
33
323
13
22
2311
22
21
22
222
13
11
1312
11
12
11
121
=
+=
+=
=
+
=
+=
=
+=
+=
xaax
aa
ahx
xaax
aa
ahx
xaax
aa
ahx
Langkah selanjutnya
Iterasi x1 x2 x3 0,000 0,000 0,0001 1,000 0,571 1,3332 1,095 1,095 1,0953 1,000 1,041 0,9684 0,991 0,991 0,9915 1,000 0,996 1,0036 1,001 1,001 1,0017 1,000 1,000 1,0008 1,000 1,000 1,000
-
24/05/2007
20
METODE ITERASI GAUSS SIEDEL
Tujuan Metode iterasi Gauss Siedel adalah metode penyelesaian
SPL melalui proses iterasi dengan menggunakan persamaan
( )
,...2,1,...2,1
1
1 1
)()1(1
==
= = +=
++
nNidengan
xaa
xaa
ahx
i
j
N
ij
nj
ii
ijnj
ii
ij
ii
ini
-
24/05/2007
21
Algoritma Iterasi Gauss Siedel Langkah 1
Memeriksa susunan SPL apakah memenuhi syarat atau tidak. Jika tidak memenuhi syarat maka susunan SPL diubah sampai
memenuhi syarat
Langkah 2 Menyusun matrik koefisien, matrik variabel dan matriks hasil
Langkah 3 Menentukan titik variabel x awal kemudian melakukan iterasi
menggunakan rumus diatas sampai didapatkan nilai variabel x yang sama atau hampir sama
Contoh Carilah penyelesaian SPL dibawah ini dengan iterasi
Gauss Siedel
Penyelesaian : Langkah 1 dan langkah 2 sama dengan iterasi jacobi
88427
1292
321
321
321
=+=+
=++
xxxxxxxxx
-
24/05/2007
22
Langkah 3 Menentukan titik awal variabel, misalnya diambil Iterasi pertama n=1 adalah :
( ) ( ) ( ) 0131
21
1 === xxx( ) ( )
( ) ( ) ( )
( ) ( )
( ) ( ) ( )
( ) ( )
( ) ( ) ( ) 0634,17147,0921
91
9120
7147,007
217
174
10810
810
880
22
33
3221
33
31
33
323
2
1
3
4
)(
33
31
33
3
33
323
13
22
2321
22
21
22
222
1
1
3
3
)(
22
21
22
2
22
222
13
11
1312
11
12
11
121
0
1
3
2
)(
11
11
11
1
11
121
=
+=
+=
=
===
=
=
+=
+=
=
= =
+
= =
+
= =
+
xaax
aa
ahx
xaa
xaa
ahx
xaax
aa
ahx
xaa
xaa
ahx
xaax
aa
ahx
xaa
xaa
ahx
j j
nj
jnj
j
j j
nj
jnj
j
j j
nj
jnj
j
Iterasi berikutnya
Iterasi x1 x2 x3
0,000 0,000 0,000
1 1,000 0,7143 1,063
2 1,044 1,024 1,063
3 1,005 1,019 0,990
4 0,996 0,997 0,995
5 1,000 0,999 1,001
6 1,000 1,000 1,000
7 1,000 1,000 1,000
-
24/05/2007
23
Contoh : Selesaikan sistem persamaan berikut:
Augmented matrik dari persamaan linier simultan tersebut :
102222
6
321
321
321
=++=+=++
xxxxxxxxx
=
1026
212121
111
3
2
1
xxx