INVERS MATRIK DAN ELIMINASI GAUSS Dr. Eng. Supriyanto, M.Sc Lab. Komputer, Departemen Fisika, Universitas Indonesia email:
[email protected] atau
[email protected] 5 Februari 2005
Secara umum, sistem persamaan linear adalah sebagai berikut: a11 x1 + a12 x2 + . . . + a1n xn = b1 a21 x1 + a22 x2 + . . . + a2n xn = b2 ............... = ... ............... = ... an1 x1 + an2 x2 + . . . + ann xn = bn Sistem persamaan linear tersebut dapat dinyatakan dalam bentuk operasi matrik, Ax = b sehingga bentuknya menjadi seperti ini: ⎡ a . . . a1n a ⎢ 11 12 ⎢ a ⎢ 21 a22 . . . a2n ⎢ . .. .. ⎢ .. . . ⎣ an1 an2 . . . ann dimana
⎡ ⎢ ⎢ ⎢ A=⎢ ⎢ ⎣
a11 a12
. . . a1n
a21 a22 . . . .. .. . .
a2n .. .
an1 an2 . . . ann
⎤⎡ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎦⎣
x1 x2 .. . xn ⎡
⎤ ⎥ ⎥ ⎥ ⎥, ⎥ ⎦
(1)
⎢ ⎢ ⎢ x=⎢ ⎢ ⎣
1
⎤
⎡
⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥=⎢ ⎥ ⎢ ⎦ ⎣
x1 x2 .. . xn
⎤ ⎥ ⎥ ⎥ ⎥, ⎥ ⎦
b1 b2 .. . bn
⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦
⎡ ⎢ ⎢ ⎢ b=⎢ ⎢ ⎣
b1 b2 .. . bn
⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦
Dalam kaitannya dengan invers matrik, matrik A disebut matrik non-singular jika matrik A memiliki matrik invers dirinya yaitu A −1 . Atau dengan kata lain, matrik A−1 adalah invers dari matrik A. Jika matrik A tidak memiliki invers, maka matrik A disebut singular. Bila matrik A dikalikan dengan matrik A −1 maka akan menghasilkan matrik identitas I, yaitu suatu matrik yang elemen-elemen diagonalnya bernilai 1. ⎤ ⎡ 1 0 ... 0 ⎥ ⎢ ⎢ 0 1 ... 0 ⎥ ⎥ ⎢ AA−1 = I = ⎢ . . . ⎥ ⎢ .. .. . . ... ⎥ ⎦ ⎣ 0 0 ... 1 Misalnya diketahui, ⎡ ⎢ A=⎢ ⎣
1 2 −1
⎤
⎡
⎥ 0 ⎥ ⎦, 2
2 1 −1 1
⎢ A−1 = ⎢ ⎣
− 29 4 9 − 13
5 9 − 19 1 3
(2)
− 19 2 9 1 3
⎤ ⎥ ⎥ ⎦
Bila keduanya dikalikan, maka akan menghasilkan matrik identitas, ⎤ ⎤⎡ ⎤ ⎡ ⎡ 5 1 − 29 1 0 0 − 1 2 −1 9 9 ⎥ ⎥ ⎥⎢ ⎢ ⎢ −1 1 2 ⎥ = ⎢ 4 ⎥ ⎥ ⎢ ⎢ AA = ⎣ 2 1 0 1 0 0 ⎦ ⎣ 9 −9 ⎦ ⎣ 9 ⎦ 1 1 0 0 1 −1 1 2 − 13 3 3 Lalu bagaimana cara mendapatkan matrik invers, A−1 ? Persamaan (2) bisa dijadikan pedoman.. ⎡ ⎢ ⎢ ⎣
−1 1
⎤⎡
⎤
⎡
⎤
1 0 0 i11 i12 i13 ⎥ ⎢ ⎥⎢ ⎥ ⎥ ⎥ ⎢ ⎢ 0 ⎦ ⎣ i21 i22 i23 ⎦ = ⎣ 0 1 0 ⎥ ⎦ i31 i32 i33 2 0 0 1
1 2 −1 2 1
AA−1 = I
dalam hal ini matrik A−1 adalah
⎡
i11 i12 i13
⎤
⎢ ⎥ ⎥ A−1 = ⎢ i i i 21 22 23 ⎣ ⎦ i31 i32 i33 Elemen-elemen matrik invers, A−1 dapat diperoleh dengan menerapkan metode eliminasi gauss. Diawali dengan membentuk matrik augment: ⎡ ⎤ 1 2 −1 | 1 0 0 ⎢ ⎥ ⎢ 2 1 ⎥ 0 | 0 1 0 ⎣ ⎦ −1 1 2 | 0 0 1 2
Lalu dilanjutkan dengan proses triangularisasi: (P 2 − 2P1 )→(P2 ) dan (P3 + P1 )→(P3 ), kemudian diikuti oleh (P 3 + P2 )→(P3 ): ⎡ ⎤ 1 2 −1 | 1 0 0 ⎢ ⎥ ⎢ 0 −3 ⎥ → 2 | −2 1 0 ⎣ ⎦ 0 3 1 | 1 0 1
⎡
1
2 −1 |
⎢ ⎢ 0 −3 ⎣ 0 0
1 0 0
⎤
⎥ 2 | −2 1 0 ⎥ ⎦ 3 | −1 1 1
Langkah berikutnya, matrik augment yang telah mengalami triangularisasi tersebut dipecah menjadi tiga buah matrik augment seperti berikut ini: ⎤ ⎤ ⎡ ⎡ 1 2 −1 | 0 1 2 −1 | 1 ⎥ ⎥ ⎢ ⎢ ⎥ ⎥ ⎢ 0 −3 ⎢ 0 −3 2 | 1 2 | −2 ⎦ ⎦ ⎣ ⎣ 0 0 3 | 1 0 0 3 | −1
⎡
1
2 −1 | 0
⎢ ⎢ 0 −3 ⎣ 0 0
⎤
⎥ 2 | 0 ⎥ ⎦ 3 | 1
Langkah pamungkasnya adalah melakukan proses substitusi mundur pada ketiga matrik augment di atas, sehingga diperoleh: i11 = − 29 i21 =
4 9
i31 = − 13
i12 =
5 9
i22 = − 19 i32 =
1 3
i13 = − 19 i23 = i33 =
2 9 1 3
Hasil tersebut digabung menjadi sebuah matrik, yaitu matrik A −1 , ⎤ ⎡ 5 1 − − 29 9 9 ⎥ ⎢ 1 2 ⎥ 4 A−1 = ⎢ ⎣ 9 −9 9 ⎦ 1 1 − 13 3 3 Keberadaan matrik A−1 bisa digunakan untuk menyelesaikan sistem persamaan linear (mencari nilai x ), dengan cara sebagai berikut Ax = b A−1 Ax = A−1 b Ix = A−1 b x = A−1 b
(3)
Contoh berikut ini akan menjelaskan prosesnya secara lebih rinci. Misalnya diketahui sistem persamaan linear x1 + 2x2 − x3 = 2 2x1 + x2 = 3 −x1 + x2 + 2x3 = 4 3
Bila dikonversikan kedalam operasi matrik menjadi ⎡ ⎤⎡ ⎤ ⎡ ⎤ 1 2 −1 x1 2 ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ 2 1 ⎢ ⎥ ⎢ ⎥ 0 ⎥ ⎣ ⎦ ⎣ x2 ⎦ = ⎣ 3 ⎦ x3 −1 1 2 4 Berdasarkan persamaan (3), maka elemen-elemen vektor x dapat dicari dengan cara x = A−1 b ⎡ ⎢ x=⎢ ⎣
− 29
4 9 − 13
5 9 − 19 1 3
− 19
2 9 1 3
⎤⎡
2
⎤
⎡
⎥⎢ ⎥ ⎢ ⎥⎢ 3 ⎥ = ⎢ ⎦⎣ ⎦ ⎣ 4
7 9 13 9 5 3
⎤ ⎥ ⎥ ⎦
Akhirnya diperoleh solusi x1 = 7/9, x2 = 13/9, dan x3 = 5/3. Penyelesaian sistem persamaan linear menjadi lebih mudah bila matrik A −1 sudah diketahui. Sayangnya, untuk mendapatkan matrik A−1 , diperlukan langkah-langkah, seperti yang sudah dibahas pada contoh pertama di atas, yang berakibat in-efisiensi proses penyelesaian (secara komputasi) bila dibandingkan dengan metode eliminasi gauss untuk memecahkan sistem persamaan linear. Namun bagaimanapun, secara konseptual kita dianjurkan mengetahui cara bagaimana mendapatkan matrik A−1 . Saya telah memodifikasi program eliminasi gauss yang terdahulu, untuk keperluan perhitungan matrik invers. Program ini ditulis dengan bahasa fortran, sudah berhasil dikompilasi dalam Linux Debian (g77) dan Windows XP (Visual Fortran). Inilah programnya, DIMENSION A(10,20), D(10,10), X(10) REAL MJI INTEGER TKR, BK, TK, Q WRITE (*,*) ’=PROGRAM INVERS MATRIK DENGAN ELIMINASI GAUSS=’ WRITE (*,*) C
LANGKAH 1: MEMASUKAN NILAI ELEMEN-ELEMEN MATRIK A WRITE (*,’(1X,A)’) ’JUMLAH PERSAMAAN ? ’ READ (*,*) N WRITE (*,*) WRITE (*,*) ’MASUKAN ELEMEN-ELEMEN MATRIK A’ M = N + 1 DO 50 I = 1,N 4
DO 60 J = 1,N WRITE (*,’(1X,A,I2,A,I2,A)’) ’A(’,I,’,’,J,’) = ’ READ (*,*) A(I,J) 60
CONTINUE
50
CONTINUE
C
LANGKAH 2: MENDEFINISIKAN MATRIK IDENTITAS WRITE (*,*) ’MENDEFINISIKAN MATRIK IDENTITAS’ DO 70 I = 1,N DO 80 J = M,N+N A(I,J) = 0 IF (I+N .EQ. J) THEN A(I,J) = 1 END IF
80 70
CONTINUE CONTINUE WRITE (*,*)
C
MENAMPILKAN MATRIK AUGMENT WRITE (*,’(1X,A)’) ’MATRIK AUGMENT:’ DO 110 I = 1,N WRITE (*,’(1X,5(F14.8))’) (A(I,J),J=1,N+N)
110
CONTINUE
C
WRITE (*,*) MENGHITUNG JUMLAH TUKAR (TKR) POSISI. MULA2 TKR = 0 TKR = 0
C
MENGHITUNG JUMLAH OPERASI BAGI/KALI (BK). BK = 0
C
MENGHITUNG JUMLAH OPERASI TAMBAH/KURANG (TK). TK = 0
C
LANGKAH 3: MEMERIKSA ELEMEN2 PIVOT DAN PROSES TUKAR POSISI NN = N-1 DO 10 I=1,NN
C
LANGKAH 4: MENDEFINISIKAN P P = I
100
IF (ABS(A(P,I)).GE.1.0E-20 .OR. P.GT.N) GOTO 200 5
P = P+1 GOTO 100 200
IF(P.EQ.N+1)THEN
C
MENAMPILKAN PESAN SINGULAR WRITE(*,5) GOTO 400 END IF
C
LANGKAH 5: PROSES TUKAR POSISI IF(P.NE.I) THEN DO 20 JJ=1,N+N C = A(I,JJ) A(I,JJ) = A(P,JJ) A(P,JJ) = C TKR = TKR + 1
20
CONTINUE END IF
C
LANGKAH 6: PERSIAPAN PROSES TRIANGULARISASI JJ = I+1 DO 30 J=JJ,N
C
LANGKAH 7: TENTUKAN MJI MJI = A(J,I)/A(I,I) BK = BK + 1
C
LANGKAH 8: MELAKUKAN PROSES TRIANGULARISASI DO 40 K=JJ,N+N A(J,K) = A(J,K)-MJI*A(I,K) BK = BK + 1 TK = TK + 1
40
CONTINUE A(J,I) = 0
30
CONTINUE
10
CONTINUE
C
MENAMPILKAN HASIL TRIANGULARISASI WRITE (*,’(1X,A)’) ’HASIL TRIANGULARISASI:’ DO 120 I = 1,N 6
120
WRITE (*,’(1X,5(F14.8))’) (A(I,J),J=1,N+N) CONTINUE
C
LANGKAH 9: MEMERIKSA ELEMEN A(N,N) IF(ABS(A(N,N)).LT.1.0E-20) THEN
C
MENAMPILKAN PESAN SINGULAR WRITE(*,5) GOTO 400 END IF DO 500 J = 1,N Q=N+J
C
LANGKAH 10: MENGHITUNG A(N,N) D(J,N) = A(N,Q)/A(N,N) BK = BK + 1
C
LANGKAH 11: PROSES SUBSTITUSI MUNDUR L = N-1 DO 15 K=1,L I = L-K+1 JJ = I+1 SUM = 0.0 DO 16 KK=JJ,N SUM = SUM+A(I,KK)*D(J,KK) BK = BK + 1 TK = TK + 1
16
CONTINUE D(J,I) = (A(I,Q)-SUM)/A(I,I) BK = BK + 1 TK = TK + 1
15
CONTINUE
500
CONTINUE
C
LANGKAH 12: MENAMPILKAN HASIL PERHITUNGAN WRITE (*,*) WRITE (*,’(1X,A)’) ’MATRIK INVERS:’ DO 220 I = 1,N WRITE (*,’(1X,5(F14.8))’) (D(J,I),J=1,N) 7
220
CONTINUE WRITE(*,8) TKR WRITE(*,9) BK WRITE(*,11) TK
400
STOP
5
FORMAT(1X,’MATRIK A BERSIFAT SINGULAR’)
8
FORMAT(1X,’JUMLAH TUKAR POSISI = ’,3X,I5)
9
FORMAT(1X,’JUMLAH OPERASI BAGI/KALI = ’,3X,I6)
11
FORMAT(1X,’JUMLAH OPERASI JUMLAH/KURANG = ’,3X,I6) END Saya cukupkan sementara sampai disini. Insya Allah akan saya sambung lagi dilain
waktu. Kalau ada yang mau didiskusikan, silakan hubungi saya melalui email.
8
