Modul 3: Solusi SPAL dengan Teknik Dekomposisi LU

Modul 3: Solusi SPAL dengan Teknik Dekomposisi LU

A. Prinsip Dekomposisi LU dan Identitas Matriks [A] dari SPAL didekomposisi (difaktorisasis) menjadi matriks-matrik segitiga bawah (L) dan segitiga atas (U) sedemikian rupa sehingga identitasnya adalah: [A] = [L]·[U]

atau

A = L·U

B. Notasi Matriks LU berdasarkan Metode Doolittle Notasi matriks L seperti di atas dituliskan sbb:

L =

0  1  l 2,1 1  M M  l i,2  l i,1 l i +1,1 l i +1,2  M M   l n,1 l n,2

L 0 L 0 O M L 1 L l i +1, i M L l n, i

L 0 L 0 M  L 0 L 0 O M  L 1

Perhatikan, bahwa semua elemen diagonal dari matriks L di atas berharga 1 (satu) ! Notasi matriks U dituliskan sbb:

U =

u1,1 u1, 2  0 u 2,2  M M  0  0 0  0  M M  0 0 

u1, n −1 u1, n  u 2, n −1 u 2, n  M M  ui , n −1 ui , n  O ui +1, n −1 ui +1, n  O M M  L L 0 u n, n  L u1, i L L

Perhatikan, bahwa semua elemen yang terletak di bawah Seri Kuliah Metode Numerik (Modul 3: Solusi SPAL dengan Teknik Dekomposisi LU)

(1/1)

diagonal dari matriks U di atas (= u1,1 … un,n) berharga 0 (nol) ! C. Notasi Matriks LU berdasarkan Metode Crout Notasi matriks L seperti di atas dituliskan sbb:

L =

0  l 1,1  l 2,1 l 2, 2  M M  l i,2  l i ,1 l i +1,1 l i +1, 2  M M l  n,1 l n, 2

L L

0 0 M L l i ,i L l i +1,i M L l n,i

       L l n,n 

L L O L L

0 0 M 0 0 M

Perhatikan, bahwa semua elemen diagonal dari matriks L di atas tidak harus berharga 1 (satu), sedangkan, elemen-elemen di atas diagonal semuanya berharga 0 (nol) ! Notasi matriks U dituliskan sbb:

U =

1 u1, 2 0 1 M M  0 0 0 0 M M 0 0 

u1, n −1 u1, n  u 2, n −1 u2, n  M M   ui , n −1 ui , n  ui +1, n −1 ui +1, n  M M  L L 0 1  L u1, i L L O O

Perhatikan, bahwa semua elemen diagonal (= u1,1 … un,n) berharga 1 (satu), sedangkan yang terletak di bawahnya berharga 0 (nol) ! D. Notasi Matriks A dan LU dalam SPAL Notasi Matriks LU sebagai dekomposan matriks A dapat dituliskan dalam SPAL sbb: [A] · [x] = [L]·[U]·[x] = [b]

Seri Kuliah Metode Numerik (Modul 3: Solusi SPAL dengan Teknik Dekomposisi LU)

(2/2)

Sehingga, dalam notasi Metode Doolittle dapat dituliskan:  a1,1 a1, 2 L a1,n  a2,1 a2, 2 L a2,n   M M    an,1 L L an,n 

=

0 L 0 u1,1 u1, 2 L u1,n   1 l 2,1 L L 0  0 L L a2,n  ·  M M  M M    l   n,1 l n, 2 L 1  0 0 L u n,n 

Sedangkan, dalam notasi Metode Crout dapat dituliskan:  a1,1 a1, 2 L a1,n  a2,1 a2, 2 L a2,n   M M    an,1 L L an,n 

=

 l 1,1 0 l 2,1 O  M  l n,1 l n, 2

L 0  L 0  · O M   L l n ,n 

1 u1, 2 0 1 M  0 0

L u1,n  L a 2 ,n  O M   L 1 

E. Deskripsi Tahapan dan Strategi Dekomposisi Notasi A = LU dalam Metode Doolittle seperti di atas dapat diuraikan dalam operasi perkalian matriks (sebagai contoh: matriks n x n) sbb: Baris 1 (i = 1): a1,1 = u1,1 a1, 2 = u1, 2 M M a1, n = u1, n

   u1, i = a1, i ;  

i = 1, K , n

Baris 2 (i = 2): a2,1 = l2,1·u1,1 a2,2 = l2,1·u1,2 + u2,2 a2,3 = l2,1·u1,3 + u2,3 M M a2,n = l2,1·u1,n + u2,n


(3/3)

Baris 3 (i = 3): a3,1 = l3,1·u1,1 a3,2 = l3,1·u1,2 + l32·u2,2 a3,3 = l3,1·u1,3 + l32·u2,3 + u3,3 M M a3,n = l3,1·u1,n + l32·u2,n + u3,n Baris n (i = n): an,1 an,2 an,3 M an,n-1 an,n

= ln,1·u1,1 = ln,1·u1,2 + ln,2·u2,2 = ln,1·u1,3 + ln,2·u2,3 + ln,3·u3,3 M = ln,1·u1,n-1 + ln,2·u2,n-1 + ln,3·u3,n-1 + … + ln,n-1·un-1,n-1 = ln,1·u1,n + ln,2·u2,n + ln,3·u3,n + … + … + un,n

# Dari operasi-operasi perkalian matriks LU seperti di atas, dapat disimpulkan beberapa hal berikut: (1). Mekanisme ‘proses dekomposisi’ dilakukan dengan cara mengisi terlebih dahulu baris pertama matriks U. Selanjutnya, mengisi matriks L pada baris terendah terlebih dulu (mulai baris ke-2), dan kemudian diikuti pengisian matriks U pada baris yang sama, demikian seterusnya sampai baris terakhir (ke-n). (2). Harga-harga dari semua elemen matriks U pada baris 1 identik dengan elemen-elemen matriks A (matriks asal), (3). Harga-harga elemen pada kolom 1 untuk matriks L, dapat dihitung menggunakan persamaan berikut: li,1 = ai,1 / u1,1 ;

i = 2,…,n

(4). Jumlah maksimum operasi penjumlahan per elemen matriks A sesuai dengan jumlah/posisi baris, (5). Pada baris rendah, langkah/iterasi pengisian matriks U lebih banyak dibandingkan dengan matriks L, dan sebaliknya. Seri Kuliah Metode Numerik (Modul 3: Solusi SPAL dengan Teknik Dekomposisi LU)

(4/4)

Tugas/Latihan: Lakukan hal yang sama seperti di atas untuk konfigurasi matriks LU yang disusun dengan Metode Crout ! F. Algoritma Dekomposisi dan Komputasi Praktis (a). Algoritma solusi numerik dengan Metode Doolittle: Baris 1: u1, i = a1, i ; i = 1, L , n Baris 2: ð Pengisian matriks L:

a2,1 u1,1 ð Pengisian matriks U: u 2, 2 = a2, 2 − l 2,1 ⋅ u1, 2 u 2,3 = a2,3 − l 2,1 ⋅ u1,3 u 2, 4 = a2, 4 − l 2,1 ⋅ u1, 4 l 2,1 =

M u 2, n = a2, n − l 2, n ⋅ u1, n Baris 3: ð Pengisian matriks L:

a3,1 u1,1 (a − l 3,1 ⋅ u1,2 ) l 3, 2 = 3, 2 u 2, 2 ð Pengisian matriks U: u3,3 = a3,3 − l 3,1 ⋅ u1,3 − l 3, 2 ⋅ u2,3 u3, 4 = a3, 4 − l 3,1 ⋅ u1, 4 − l 3, 2 ⋅ u2, 4 l 3,1 =

M u3, n = a3, n − l 3,1 ⋅ u1, n − l 3, 2 ⋅ u 2, n


(5/5)

Baris n: ð Pengisian matriks L:

an ,1 u1,1 (a − l n,1 ⋅ u1,2 ) = n, 2 u 2, 2 (a − l n,1 ⋅ u1,3 − l n,2 ⋅ u2,3 ) = n ,3 u3,3

l n,1 = l n, 2 l n ,3 M

l n, n −1 =

(an, n −1 − l n,1 ⋅ u1, n −1 − l n,2 ⋅ u2, n −1 − L − l n, n −1 ⋅ un −1, n −1 ) u n −1, n −1

ð Pengisian matriks U:

u n, n = an, n − l n ,1 ⋅ u1, n − l n, 2 ⋅ u2, n − L − l n, n −1 ⋅ un −1, n

(b). Algoritma solusi numerik dengan Metode Crout: Sebaai latihan, coba saudara lakukan sendiri dengan cara mengikuti langah-langkah untuk Metode Doolittle seperti di atas dengan cermat dan seksama! (c). Komputasi dengan Fortran-77 untuk Metode Doolittle: MODEL VARIABEL MATRIKS (2-dimensi): C

PROGRAM Pengujian Dekomposisi LU

C C

Deklarasi Jenis dan Variabel: ----------------------------IMPLICIT NONE INTEGER iarg PARAMETER (iarg = 7) INTEGER i,j,neq REAL*8 A(iarg,iarg),LU(iarg,iarg) LU(iarg,iarg)

C

CALL system('clear') C C

Proses Pemasukan Harga Variabel: -------------------------------WRITE(*,10) 'Jumlah Persamaan : ' READ(*,*) neq DO i = 1,neq


(6/6)

DO j = 1,neq WRITE(*,20) 'A(',i,',',j,') : ' READ(*,*) A(i,j) ENDDO ENDDO C C

Proses Pemanggilan Subprogram Eliminasi Gauss-Jordan: ----------------------------------------------------CALL DECOLU(neq,A,LU)

C C

Pemaparan/penyajian Hasil Perhitungan: -------------------------------------WRITE(*,30) 'Matriks LU yang diperoleh:' DO i = 1,neq DO j = 1,neq WRITE(*,40) LU(i,j) ENDDO WRITE(*,*) ENDDO

C

10 20 30 40 40

FORMAT FORMAT FORMAT FORMAT FORMAT

(3X,A,$) (3X,A,I1,A1,I1,A,$) (/,1X,A) (3X,F10.4,$) (3X,F10.4,3X,F10.4,3X,F10.4,3X,F10.4,3X,F10.4)

STOP END

SUBROUTINE DECOLU(n,A,LU) C --------------------------------------------------------------------------C SUBPROGRAM DEKOMPOSI LU: | C Merupakan solusi DEKOMPOSISI Matriks A menjadi matriks-matriks L | C dan U dengan format [A] = [L].[U] yang hasilnya disimpan dalam LU | C n = dimensi matriks A (identik dengan jumlah PAL), | C A = matriks bujur sangkar n x n yang berisi koefisien persamaan, | C LU = matriks bujur sangkar tempat penyimpanan hasil dekomposisi | C matrik A menjadi L dan U (yang disimpan sekaligus dalam LU). | C --------------------------------------------------------------------------C C

Deklarasi Variabel: ------------------INTEGER n REAL*8 A(7,7),LU(7,7) INTEGER i,j,k REAL*8 sum

C C

Proses pengisian matriks L dan U (dalam matriks LU): ----------------------------------------------------

C C

C C

DO j = 1,n Proses pengisian matriks U pada baris pertama: ---------------------------------------------LU(1,j) = A(1,j) ENDDO DO i = 2,n Proses pengisian matriks L: --------------------------LU(i,1) = A(i,1)/LU(1,1) sum = 0.0D0 DO j = 2,i-1 DO k = 1,i-2 sum = sum + LU(i,k)*LU(k,j) ENDDO LU(i,j) = (A(i,j) - sum)/LU(j,j) ENDDO


(7/7)

C C

Proses pengisian matriks U: --------------------------DO j = i,n sum = 0.0D0 DO k = 1,i-1 sum = sum + LU(i,k)*LU(k,j) ENDDO LU(i,j) = A(i,j) - sum ENDDO ENDDO RETURN END

MODEL VARIABEL VEKTOR (2-dimensi): C C C

PROGRAM Solusi Sistem Persamaan Aljabar Linier (SPAL) atau atau Persamaan Aljabar Linier Simultan dengan teknik TRIDIAGONAL yang terwakili (disimpan) dalam 1 vektor

C C

Deklarasi Jenis dan Variabel: ----------------------------IMPLICIT NONE INTEGER iarg PARAMETER (iarg = 7) INTEGER i,neq REAL*8 b(iarg),d(3*iarg),x(iarg) CALL system('clear') OPEN (10,FILE='s3diag.dta')

C C

Proses Pemasukan Harga Variabel: -------------------------------READ(10,*) neq WRITE(*,*) 'Jumlah Persamaan : ',neq READ(10,*) d(1+neq),d(1+2*neq),b(1) DO i = 2,neq-1 READ(10,*) d(i),d(i+neq),d(i+2*neq),b(i) ENDDO READ(10,*) d(neq),d(neq+neq),b(neq)

C C

Proses Pemanggilan Subprogram Eliminasi Gauss-Jordan: ----------------------------------------------------CALL V3DIAG(neq,d,x,b)

C C

Pemaparan/penyajian Hasil Perhitungan: -------------------------------------WRITE(*,*) '--------HASIL---------' DO i = 1,neq WRITE(*,40) 'x(',i,') = ',x(i) ENDDO CLOSE(10) 20 FORMAT (3X,A,I1,A1,I1,A,G15.7) 30 FORMAT (5X,A,I1,A,G15.7) 40 FORMAT (5X,A,I1,A,G15.7) STOP END INCLUDE 'v3diag.sub'


(8/8)

File v3diag.sub (dalam include): SUBROUTINE V3DIAG(n,d,x,b) C --------------------------------------------------------------------------C SUBPROGRAM SOLUSI MATRIKS TRI-DIAGONAL dengan ELIMINASI GAUSS | C Merupakan solusi Sistem Persamaan Aljabar Linier (SPAL) dengan | C format persamaan matriks: [A].[x] = [b], dengan rincian sbb | C n = jumlah persamaan aljabar linier (dimensi SPAL) | C d(2..n) = vektor koefisien diagonal bawah dengan dimensi n-1,| C d(n+1..2n) = vektor koefisien diagonal utama dengan dimensi n, | C d(2n+1..3n-1) = vektor koefisien diagonal atas dengan dimensi n-1, | C x = vektor variabel persamaan yang akan dicari harga-harganya | C b = vektor ruas kanan yang berisi harga-harga persamaan tunggal | C --------------------------------------------------------------------------C C

Deklarasi Variabel: ------------------INTEGER n REAL*8 d(3*n),b(n),x(n) INTEGER i,l,m REAL*8 PIVOT,MULT

C C

Proses solusi: (a) Substitusi dan Eliminasi ------------------------------------------DO i = 1,n-1 PIVOT = d(i+n) MULT = d(i+1)/PIVOT d(i+1) = MULT d(i+n+1) = d(i+n+1) - MULT*d(i+2*n) b(i+1) = b(i+1) - MULT*b(i) ENDDO

C C

Proses solusi: (b) Substitusi Balik ----------------------------------x(n) = b(n)/d(n+n) DO i = n-1,1,-1 x(i) = (b(i) - d(i+2*n)*x(i+1))/d(i+n) ENDDO RETURN END

(d). Untuk Pemahaman yang lebih mendalam, cobalah buat program dalam bahasa Fortran-77 untuk Metode Crout! G. Manfaat Dekomposisi LU untuk Solusi SPAL Solusi SPAL [A] · [x] = [b], melalui teknik dekomposisi matriks [A], sangat bermanfaat untuk menyelesaikan problem-problem ataupun model matematis yang membentuk SPAL dengan matriks [A] yang sama untuk berbagai vektor jawab, [b]. Dengan teknik dekomposisi LU ini, penyelesaian akan menjadi sangat efisien dan banyak menghemat waktu pada saat telah Seri Kuliah Metode Numerik (Modul 3: Solusi SPAL dengan Teknik Dekomposisi LU)

(9/9)

diperoleh dekomposisi matriks [A], karena hasil dekomposisi LU tersebut dapat dipakai untuk semua SPAL dengan matriks [A] yang identik. Bentuk umum SPAL yang menggunakan matriks [A] yang identik, seperti disebutkan di atas, dapat dituliskan sbb:  b1,1 b2,1 L bn,1   x1,1 x2,1 L xn,1  b1, 2 b2,2  x1, 2 x2,2 L xn,2  bn,2  = [A] ·   M M M  M M    M b1, n b2, n L bn, n   x1, n x2, n L xn, n 

Perhatikan, bahwa bentuk di atas sesungguhnya merupakan perkalian 2 bentuk matriks, antara matriks bujur sangkar [A] yang berdimensi n x n dengan matrik segi 4 yang berdimensi n x m, dengan hasil matriks lain yang juga berdimensi n x m! H. Solusi Numerik SPAL melalui Dekomposisi LU Subprogram (SUBROUTINE) di bawah ini dapat digunakan untuk solusi SPAL dengan bentuk normal: [A] · [x] = [b], menggunakan matriks LU sebagai hasil dekomposisi matriks [A] dengan Metode Doolittle. C

PROGRAM Solusi SPAL dengan Dekomposisi LU

C C

Deklarasi Jenis dan Variabel: ----------------------------IMPLICIT NONE INTEGER iarg PARAMETER (iarg = 7) INTEGER i,j,neq REAL*8 LU(iarg,iarg),b(iarg),x(iarg) CALL system('clear') OPEN (11,FILE='inputLU.dta')

C C

Proses Pemasukan Harga Variabel dari FILE: -----------------------------------------READ(11,*) neq DO i = 1,neq READ(11,*) (LU(i,j), j=1,neq),b(i) ENDDO

C C

Proses Pemanggilan Subprogram Eliminasi Gauss-Jordan: ----------------------------------------------------CALL DECOLU(neq,LU) CALL SOLVLU(neq,LU,x,b)


(10/10)

C C

Pemaparan/penyajian Hasil Perhitungan: -------------------------------------WRITE(*,30) 'Matriks LU dan vektor x yang diperoleh:' DO i = 1,neq DO j = 1,neq WRITE(*,40) LU(i,j) ENDDO WRITE(*,50) 'x(',i,') = ',x(i) ENDDO CLOSE(11) 10 20 30 40 50

FORMAT FORMAT FORMAT FORMAT FORMAT

(3X,A,$) (3X,A,I1,A1,I1,A,$) (/,1X,A) (3X,F10.4,$) (5X,1H|,5X,A,I1,A,G10.4)

STOP END INCLUDE 'decoLU.sub' INCLUDE 'solvLU.sub'

Tugas ! Ujilah program di atas untuk SPAL berikut: 2 1 3  x1  11 4 3 10 ⋅  x2  = 28       2 4 17  x3   31

Perhatikan dengan seksama hasil dekomposisinya (matriks LU) dan solusi vektor x-nya !

I. Daftar Pustaka Atkinson, Kendal E., “An Introduction to Numerical Analysis”, John Wiley & Sons, Toronto, pp. 33-39, 1978. Atkinson, L.V., Harley, P.J., “An Introduction to Numerical Methods with Pascal”, Addison-Wesley Publishing Co., Tokyo, pp. 49-59, 1983. Bismo, Setijo, “Kumpulan Bahan Kuliah Metode Numerik”, Jurusan TGP-FTUI, 1999.


(11/11)

Modul 3: Solusi SPAL dengan Teknik Dekomposisi LU

Recommend Documents