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