Modul 2: Solusi Sistem Persamaan Aljabar Linier (SPAL) dengan Metode Eliminasi Gauss dan variannya

Seri Matematika Terapan untuk S2

Modul 2: Solusi Sistem Persamaan Aljabar Linier (SPAL) dengan Metode Eliminasi Gauss dan variannya Sistem Persamaan Aljabar Linier (SPAL) atau dikenal juga sebagai ‘Persamaan Aljabar Linier Serempak’ banyak sekali dijumpai dalam perhitungan-perhitungan teknik kimia yang melibatkan solusi numeris. Beberapa metode solusi yang melibatkan solusi SPAL, di antaranya dalah: solusi Sisten Persamaan Aljabar NonLinier (SPANL), solusi Persamaan Diferensial Biasa (PDB), solusi persamaan Diferensial Parsial (PDP), Regresi Linier dan NonLinier, dll. Dalam modul ini, para mahasiswa S2 akan diajak terlebih dahulu untuk membaca ulang (review) secara ringkas dan cepat tentang beberapa pengertian dasar skalar, vektor, matriks, dan sistem persamaan linier. Pengulangan ini sangat diperlukan mengingat banyak di antara peserta ajar S2 yang sudah terlupa dengan materimateri kuliah matematik yang pernah diikutinya. Di samping itu juga, para pembaca diajak untuk memahami secara praktis tentang konsep-konsep pemahaman dalam aljabar linier yang diimplementasikan dalam metode numerik. Setelah pengulangan tentang aljabar numeris, para pembaca diajak secara ringkas untuk memahami konsep-konsep perhitungan numeris yang berhubungan dengan metode-metode Eliminasi Gauss dan Pivot Gauss. Kemudian, lebih jauh lagi diajak untuk melakukan analisis numerik dalam solusi-solusi Dekomposisi LU dan Matriks Tri-Diagonal. A. Skalar, Vektor, Matriks dan SPAL (a). Skalar atau konstanta didefinisikan sebagai suatu obyek tunggal (berdimensi nol), baik bilangan nyata (R, real) ataupun Intellectual Property of DR. Ir. Setijo Bismo, DEA., TGP-FTUI

Modul 2 – Solusi Sistem Persamaan Aljabar Linier (SPAL) (1/1)


bilangan kompleks (C, complex) yang daripadanya dapat dilakukan sembarang operasi aritmatika/aljabar secara linier, seperti: penambahan (adisi), pengurangan (substraksi), perkalian (multiplikasi), pembagian (divisi), perpangkatan (eksponen), dsb. Dalam prakteknya, besaran skalar dapat dibagi atas 2 bagian besar dalam domain bilangan, yaitu: k = R, suatu skalar dalam bidang bilangan nyata, z = C, suatu skalar dalam bidang bilangan kompleks. (b). Vektor atau ‘ruang vektor V’ adalah suatu set (sekumpulan) obyek berupa skalar (berdimensi satu) yang kepadanya dapat dilakukan operasi-operasi skalar spesifik berupa ‘penambahan vektor’ (vector addition) dan ‘perkalian skalar’ (scalar multiplication). Operasi-operasi tersebut harus memenuhi aturanaturan baku, berupa: asosiatif, komutatif, dan distributif. V = Rn, suatu set skalar dalam bidang bilangan nyata dengan jumlah anggota sebanyak n buah, atau  v1  v 2  V =   , merupakan ‘vektor horizontal’, sedangkan M vn 

H = [h1 h2 L hn ] , merupakan ‘vektor horisontal’, Ζ = Cn, suatu set skalar dalam bidang bilangan kompleks dengan jumlah anggota sebanyak n buah. (c). Matriks didefinisikan sebagai suatu set vektor yang tersususn sedemikian rupa sehingga tebentuk kumpulan bilangan dengan pola persegi-empat, atau berorder m (baris) x n (kolom) (berdimensi dua).

Intellectual Property of DR. Ir. Setijo Bismo, DEA., TGP-FTUI



 a1,1 a1,2 L a1, n  a L a2, n  a  A =  2,1 2, 2 M M M   an,1 an,2 L an, n 

Dalam sistem linier, pada umumnya hanya digunakan matriksmatrik bujur-sangkar sehingga secara sederhana: order matriks identik dengan jumlah persamaan. Lambang matriks selalu dituliskan dalam huruf besar (capital), sedangkan elemenelemennya dituliskan dalam huruf kecil seperti dalam penulisan matriks A di atas. (d). Sistem persamaan linier, dalam modul ini digunakan istilah SPAL (Sistem Persamaan Aljabar Linier) yang didefinisikan sebagai suatu set persamaan-persamaan aljabar yang variabelvariabelnya berpangkat tunggal (linier) dengan notasi berikut: a1,1 x1 + a1,2 x2 + ... + a1, n xn = b1 a2,1 x1 + a2,2 x2 + ... + a2, n xn = b2 a3,1 x1 + a3, 2 x2 + ... + a3, n xn = b3 ... = ... an,1 x1 + an,2 x2 + ... + an, n xn = bM

      

sedemikian rupa sehingga persamaan di atas dapat dituliskan dalam notasi berikut:

[ A] ⋅ [ x ]

= [b]

atau  a1,1 a1,2 a2,1 a2, 2  ...  ... an,1 an,2

... a1, n   x1   b1     b  ... a2,1 x  ⋅  2 =  2 ... ...   ...   ...  bn  ... an, n   xn 

SPAL di atas memiliki n buah variabel atau bilangan anu (xj, j = 1, 2,…, n) yang identik dengan jumlah persamaannya. KoefisienIntellectual Property of DR. Ir. Setijo Bismo, DEA., TGP-FTUI



koefisien xi,j, (x1,1 . . . xn,n) merupakan konstanta (diketahui), demikian juga bi (b1 . . . bn) yang dikenal sebagai vektor ruas kanan (VRK). Menurut konvensi : indeks pertama dari elemen ai,j menyatakan baris (= i) sedangkan indeks kedua menyatakan kolom (= j). Agar solusi SPAL di atas dapat diperoleh, maka persayaratan (teorema) berikut harus dipenuhi: 1. A x = b mempunyai jawab unik x ∈ V untuk setiap b ∈ V, 2. A x = b hanya mempunyai satu solusi x ∈ V untuk setiap b ∈ V, 3. Jika A x = 0, berarti x = 0, 4. A-1 atau inversi dari matriks A ada, 5. Determinan(A) ≠ 0, 6. Rank(A) = n, atau matriks A berorder n. Seperti telah dijelaskan di atas, matriks A merupakan matriks bujur sangkar. Bila teorema di atas tak terpenuhi, maka akan terjadi kombinasi linier (akan mengakibatkan persamaan aljabar di atas bersifat SINGULAR). Kombinasi Linier : ð per baris, cukup hanya 2 baris yang menyebabkannya, ð per kolom, bila semua baris yang menyebabkanya.

B. Solusi SPAL secara numeris Solusi SPAL secara numeris umumnya selalu (harus) lebih efisien dan cepat dibandingkan dengan metode-metode analitis, seperti metode Cramer. Namun demikian, solusi numerik ini secara teknis adakalanya juga berkendala, karena:




ð ada beberapa persamaan yang mendekati kombinasi linier,

akibat adanya “round off error” dari mesin penghitung pada suatu tahap perhitungan ð adanya akumulasi “round off error” pada proses komputasi akan

berakibat domain bilangan nyata (fixed point) dalam perhitungan akan terlampaui (overflow), biasanya akibat dari jumlah persamaan yang terlalu besar Metode-metode solusi numerik yang banyak dipakai, dapat diklasifikasikan sebagai: a. Metode Langsung ð Eliminasi Gauss (EGAUSS), prinsipnya: merupakan operasi

eliminasi dan substitusi variabel-variabelnya sedemikian rupa sehingga dapat terbentuk matriks segitiga atas, dan akhirnya solusinya diselesaikan menggunakan teknik substitusi balik (backsubstitution). Metode Eliminasi Gauss ini secara ringkas dibahas pada Paragraf C. ð Eliminasi Gauss-Jordan (EGJ), prinsipnya: mirip sekali

dengan metode EG, namun dalam metode ini jumlah operasi numerik yang dilakukan jauh lebih besar, karena matriks A mengalami inversi terlebih dahulu untuk mendapatkan matriks identitas (I). Karena kendala tersebut, maka metode ini sangat jarang dipakai, namun sangat bermanfaat untuk menginversikan matriks. Metode ini tidak dibahas lebih lanjut dalam pelajaran ini. ð Dekomposisi

LU (DECOLU), prinsipnya: melakukan dekomposisi matriks A terlebih dahulu sehingga dapat terbentuk matriks-matrik segitiga atas dan bawah, kemudian secara mudah dapat melakukan substitusi balik (backsubstitution) untuk berbagai vektor VRK (vektor ruas kanan). Metode ini secara lebih jelas akan dibahas pada Paragraf F, khusus tentang metode-metode dekomposisi LU dan teknik komputasinya.




ð Solusi

sistem TRIDIAGONAL (S3DIAG), prinsipnya merupakan solusi SPAL dengan bentuk matrik pita (satu diagonal bawah, satu diagonal utama, dan satu diagonal atas) pada matriks A. Metode ini akan dibahas lebih lanjut pada Paragraf K.

b. Metode Tak-Langsung (Metode Iteratif) ð Metode Jacobi, prinsipnya: merupakan metode iteratif yang

melakuakn perbaharuan nilai x yang diperoleh tiap iterasi (mirip metode substitusi berurutan, successive substitution), ð Metode Gauss-Seidel, prinsipnya: mirip metode Jacobi,

namun melibatkan perhitungan implisit, ð Metode Successive Over Relaxation (SOR), prinsipnya:

merupakan perbaikan secara langsung dari Metode GaussSeidel dengan cara menggunakan faktor relaksasi (faktor pembobot) pada setiap tahap/proses iterasi. Metode-metode tak-langsung seperti di atas pada umunya sangat tidak efisien dan ‘time consuming’ (memerlukan CPUtime) yang jauh lebih besar dari metode langsung. Metode ini dapat dilihat dan dipelajari pada buku-buku numerik yang ada di perpustakaan atau toko buku.

C. Algoritma Solusi SPAL dengan Metode Eliminasi Gauss ð Langkah #1: Pilih harga a1(,11) sedemikian rupa yang tidak

berharga nol. Tentukan ‘pengali baris’ sebagai berikut: mi,1 = ai(,11) a1(1,1) ; i = 2,3,…,n

Kemudian, konstanta-konstanta pengali baris (m) di atas digunakan untuk melakukan ‘eliminasi’ term-term x1 pada persamaan-persamaan 2 sampai ke-n, seperti berikut: Intellectual Property of DR. Ir. Setijo Bismo, DEA., TGP-FTUI



ai(,2j) = ai(,1)j − mi,1 ⋅ a1(1, )j ; i,j = 2, …, n bi( 2) = bi(1) − mi,1 ⋅ b1(1) ; i = 2, …, n

Dalam hal ini, baris pertama dari matriks A dan vektor b tidak boleh diganggu, sedangkan kolom pertama dari matriks A(1) di bawah diagonal harus dibuat nol. Sistem A(2)·x = b(2) akan tampak seperti berikut: a (1) a (1) L a (1)   x1   b (1)  1, n  1,1 1(,22)     1( 2)  ( 2)  0 a2,2 L a2,2   x2  b2   ⋅ M  =  M M  M   M     0 a ( 2) L an( 2, n)   xn  bn( 2)  n, 2    

Proses eliminasi dilanjutkan untuk kolom-kolom 2, 3 sampai ken, dan diungkapkan dalam langkah berikut. ð Langkah k: menggunakan k untuk indeks iterasi, untuk rentang

harga: 1 ≤ k ≤ n-1. Bila A(k)·x = b(k) telah terbentuk, dan dengan anggapan termterm x1 , x2 ,K, xk −1 telah tereliminasi pada tahap sebelumnya, sehingga matriks A(k) sekarang memiliki bentuk sebagai berikut:

A(k)

a (1) a (1) ⋅ ⋅ ⋅ a1(,1n)  1,1 1,1   ( 2 ) ( 2 )  0 a a 2, n  2, 2    M O M   =  (k ) (k )   0 L 0 a k , k L ak , n    M M M M    ( k ) ( k )  0 L 0 an, k L an, n  




Pilih harga a1(,11) sedemikian rupa yang tidak berharga nol. Tentukan ‘pengali baris’ sebagai berikut: mi, k = ai(,kk) ak( k, k) ; i = k+1,…,n

Kemudian, gunakan konstanta-konstanta di atas untuk mengeliminasi term-term xk pada persamaan-persamaan k+1 sampai ke-n, seperti berikut: ai(,kj+1) = ai(,kj) − mi, k ⋅ ak(k, )j bi(k +1) = bi( k ) − mi, k ⋅ bk(k ) ; i,j = 2, …, n

Baris-baris terdahulu, dari 1 sampai k, tidak boleh diganggu, dan harga-harga nol dimasukkan pada kolom k di bawah diagonal. Dengan mengikuti langkah-langkah seperti di atas, setelah langkah ke n-1 akan diperoleh suatu matriks dengan susunan seperti berikut: a (1) L L a (1)   x1   b (1)  1 , 1 1 , n      1  M M     0 O  M  ⋅ =  M  M  O M  M        0 L L an( n, n)   xn  bn( n ) 

Perhatikan, bahwa matriks A di atas sekarang telah berubah menjadi matriks segitiga atas (= matriks U), sehingga: U·x = b(n) Hal ini berarti bahwa solusi harga-harga x harus dilakukan dimulai dari indeks terbesar (=n) menuju indeks terkecil (=1), Intellectual Property of DR. Ir. Setijo Bismo, DEA., TGP-FTUI



yang disebut sebagai substitusi balik (back substitution), yang dimulai dengan: xn = bn( n) an( n, n)

kemudian, diikuti dengan: xk =

n  1  (k ) (k ) ; − ⋅ b a x ∑ j k, j  (k )  k j = k +1 ak , k  

k = n-1,n-2,…,1

D. Teknik Pivoting dalam Metode Eliminasi Gauss Dalam beberapa kasus, terutama bila dijumpai matriks-matrik yang bersifat ‘singular’ karena adanya ‘kombinasi linier’, solusi secara langsung menggunakan algoritma metode eliminasi Gauss tidak memberikan hasil dan ketelitian yang baik, bahkan seringkali memberikan hasil yang meleset jauh dari yang diharapkan. Untuk menghindari fenomena tersebut, diperlukan modifikasi dari algoritma eliminasi Gauss. Pada prinsipnya, modifikasi tersebut dilakukan dengan memperhatikan hal-hal berikut:

ð Harga pivot diambil yang terbesar dari setiap baris dan kolom yang sesuai, yaitu komponen aii ,

ð Pemilihan pivot dilakukan berdasarkan ‘pembandingan harga terbesar (maksimum)’ dari setiap elemen a ji ∀ j ≥ i ,

ð Untuk hasil terbaik, sebaiknya gunakan variabel ‘presisi ganda’ (DOUBLE PRECISION atau REAL*8).




E. Contoh Solusi SPAL dengan Eliminasi Gauss Diberikan SPAL berikut: 2 x1 + x2 + 3 x3

= 11

4 x1 + 3 x2 + 10 x3

= 28

2 x1 + 4 x2 + 17 x3

= 31

Maka, solusinya adalah sebagai berikut:

Ü

Tahap I : Triangularisasi

ð ð

Eliminasi x 1 dari persamaan kedua dan ketiga (dalam hal ini : persamaan pertama disebut “persamaan pivotal”, sedangkan koefisien pertama dari persamaan kedua disebut “pivot”) Persamaan pertama dikalikan dengan 2 untuk mengeliminasi x 1 pada persamaan kedua ; Persamaan pertama dikalikan dengan 2 untuk mengeliminasi x 1 pada persamaan ketiga : 2 x1 + x2 + 3 x3 x2 + 4 x3 3 x2 + 14 x3

ð

ð

= 6 = 20

Eliminasi x 2 dari persamaan ketiga (dalam hal ini : persamaan kedua menjadi “persamaan pivotal”, sedangkan koefisien x 2 dari persamaan ketiga disebut “pivot”) Persamaan kedua dikalikan dengan 3 untuk mengeliminasi x 2 pada persamaan kedua : 2 x1 + x2 + 3 x3

Ü

= 11

= 11

x2 + 4 x3

= 6

2 x3

= 2

Tahap II : Substitusi Balik (Back Substitution)




ð ð

Dimulai dari baris ketiga (baris terakhir, baris ke n), langsung dapat dihitung bahwa : x n = b n a n , n Baris lainnya, dimulai dari beris ke n-1 sampai baris pertama dihitung menggunakan algoritma : n    bi − ∑ ai, j ⋅ x j    j = i +1   ; xi = ai , i

Ü

i = n − 1, n − 2,K,1

Perolehan : vektor jawab yang dihasilkan adalah

[x ]

 x1   3   =  x2  = 2  x3  1

(a). Listing Program Eliminasi Gauss (tanpa Pivoting) C C

PROGRAM Solusi Sistem Persamaan Aljabar Linier (SPAL) atau atau Persamaan Aljabar Linier Simultan

C C

Deklarasi Jenis dan Variabel: ----------------------------IMPLICIT NONE INTEGER iarg PARAMETER (iarg = 7) INTEGER i,j,k,neq REAL*8 A(iarg,iarg) REAL*8 b(iarg),x(iarg) CALL system('clear')

C C

Proses Pemasukan Harga Variabel: -------------------------------WRITE(*,10) 'Jumlah Persamaan : ' READ(*,*) neq DO i = 1,neq DO j = 1,neq WRITE(*,20) 'A(',i,',',j,') : ' READ(*,*) A(i,j) ENDDO WRITE(*,30) 'b(',i,') : ' READ(*,*) b(i) ENDDO

C C

Proses Pemanggilan Subprogram Eliminasi Gauss-Jordan: ----------------------------------------------------CALL EGAUSS(neq,A,x,b)

C C

Pemaparan/penyajian Hasil Perhitungan: --------------------------------------




DO i = 1,neq WRITE(*,40) 'x(',i,') = ',x(i) ENDDO 10 20 30 40

FORMAT FORMAT FORMAT FORMAT

(3X,A,$) (3X,A,I1,A1,I1,A,$) (5X,A,I1,A,$) (5X,A,I1,A,G12.7)

STOP END SUBROUTINE EGAUSS(n,A,x,b) C --------------------------------------------------------------------------C SUBPROGRAM 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 A = matriks bujur sangkar n x n yang berisi koefisien persamaan, | 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 A(7,7),b(n),x(n) INTEGER i,j,k REAL*8 PIVOT,MULT,TOP

C C

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

C C

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

Listing program (source code) di atas masih menggunakan subroutine eliminasi Gauss yang belum dilakukan ‘pivoting’ pada setiap penggunaan elemen aii . Di bawah ini diberikan subroutine yang telah menggunakan ‘teknik pivoting’. Intellectual Property of DR. Ir. Setijo Bismo, DEA., TGP-FTUI



(b). Listing Program Eliminasi Gauss (dengan Pivoting) SUBROUTINE PGAUSS(n,A,x,b) C --------------------------------------------------------------------------C SUBPROGRAM ELIMINASI GAUSS dengan TEKNIK PIVOTING | C --------------------------------------------------------------------------C C

Deklarasi Variabel: ------------------INTEGER n REAL*8 A(7,7),b(n),x(n) INTEGER i,j,k REAL*8 PIVOT,PIVMAX,MULT,TOP INTEGER KPOS,ipos(7),itemp

C C

Proses solusi: (a) Substitusi dan Eliminasi -------------------------------------------DO i = 1,n ipos(i) = i ENDDO

C C

C C C

DO j = 1,n-1 Mencari PIVOT terbesar: ----------------------PIVMAX = ABS(A(j,j)) KPOS = j DO i = j+1,n IF (ABS(A(i,j)) .GT. PIVMAX) THEN PIVMAX = ABS(A(i,j)) KPOS = i ENDIF ENDDO IF (KPOS .NE. j) THEN itemp = ipos(j) ipos(j) = ipos(KPOS) ipos(KPOS) = itemp ENDIF Akhir pencarian PIVOT terbesar: ------------------------------write(*,*) 'i-pos = ',ipos(j) PIVOT = A(ipos(j),j) DO i = j+1,n itemp = ipos(i) MULT = A(itemp,j)/PIVOT DO k = j+1,n A(itemp,k) = A(itemp,k) - MULT*A(ipos(j),k) ENDDO b(itemp) = b(itemp) - MULT*b(ipos(j)) ENDDO ENDDO

C C

Proses solusi: (b) Substitusi Balik ----------------------------------x(n) = b(ipos(n))/A(ipos(n),n) DO i = n-1,1,-1 itemp = ipos(i) TOP = b(itemp) DO k = i+1,n TOP = TOP - A(itemp,k)*x(k) ENDDO x(i) = TOP/A(itemp,i) ENDDO RETURN END




F. Prinsip Dekomposisi LU dan Matriks 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

F1. Notasi Matriks LU berdasarkan Metode Doolittle Notasi matriks L seperti di atas dituliskan sbb: 0  1 l 1  2,1  M M  L =  l i,1 l i ,2 l l  i +1,1 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) ! Sedangkan semua elemen di atas diagonal semuanya berharga 0 (nol) ! Notasi matriks U dituliskan sbb: u1,1 u1, 2  0 u 2, 2   M M  U = 0 0  0 0  M  M  0  0

L u1, i

u1, n −1

L L

u 2, n −1 M ui , n −1

O

ui +1, n −1 O

M

L L

0


u1, n  u 2, n  M   ui , n  ui +1, n   M   u n, n 



Perhatikan, bahwa semua elemen yang terletak di bawah diagonal dari matriks U di atas (= u1,1 … un,n) berharga 0 (nol) !

F2. Notasi Matriks LU berdasarkan Metode Crout Notasi matriks L seperti di atas dituliskan sbb: 0  l 1,1  l 2,1 l 2, 2  M M  L =  l i ,1 l i , 2 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: 1 u1, 2 0 1 M M  U = 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) !




F3. 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] 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 L 0  0 L L a 2, n  l =  M2,1 · M  M M    l  l L 1 n , 1 n , 2 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 

G. 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 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), Intellectual Property of DR. Ir. Setijo Bismo, DEA., TGP-FTUI



(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. Tugas/Latihan: Lakukan hal yang sama seperti di atas untuk konfigurasi matriks LU yang disusun dengan Metode Crout !

H. 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 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: Sebagai latihan, coba saudara lakukan sendiri dengan cara mengikuti langah-langkah untuk Metode Doolittle seperti di atas dengan cermat dan seksama! Intellectual Property of DR. Ir. Setijo Bismo, DEA., TGP-FTUI



(c). Komputasi dengan Fortran-77 untuk Metode Doolittle: 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 DO j = 1,neq WRITE(*,20) 'A(',i,',',j,') : ' READ(*,*) A(i,j) ENDDO ENDDO

C C

Proses Pemanggilan Subprogram Eliminasi Gauss: ---------------------------------------------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,i,j,k REAL*8 A(7,7),LU(7,7),sum




C C C C

C C

Proses pengisian matriks L dan U (dalam matriks LU): ---------------------------------------------------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

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

(d). Untuk Pemahaman yang lebih mendalam, cobalah buat program dalam bahasa Fortran-77 untuk Metode Crout!

I. 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 diperoleh dekomposisi matriks [A], karena hasil dekomposisi LU tersebut dapat dipakai untuk semua SPAL dengan matriks [A] yang identik. Intellectual Property of DR. Ir. Setijo Bismo, DEA., TGP-FTUI



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  b x L xn, 2  b bn,2  x =  1, 2 2,2 [A] ·  1, 2 2,2   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!

J. 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: ---------------------------------------------CALL DECOLU(neq,LU) CALL SOLVLU(neq,LU,x,b)

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' SUBROUTINE SOLVLU(n,LU,x,b) C --------------------------------------------------------------------------C SUBPROGRAM ELIMINASI GAUSS: | C Merupakan solusi Sistem Persamaan Aljabar Linier (SPAL) dengan | C teknik dekomposisi LU untuk format persamaan: [A].[x] = [b], | C dengan rincian sbb | C n = jumlah persamaan aljabar linier (dimensi SPAL) | C LU = matriks bujur sangkar n x n yang berisi koefisien persamaan, | 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 LU(7,7),b(n),x(n) INTEGER i,j

C C

Proses solusi: (a) Substitusi dan Eliminasi ------------------------------------------DO i = 2,n DO j = 1,i-1 b(i) = b(i) - LU(i,j)*b(j) ENDDO ENDDO

C C

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




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 !

K. Solusi Numerik SPAL dengan Matriks Tri-Diagonal Solusi SPAL yang berbentuk matriks tri-diagonal seringkali dijumpai pada problem-problem yang berbentuk PDP (persamaan diferensial parsial) yang dominan secara diagonal (definit positif).

K1. Bentuk umum Matrik Tri-Diagonal Secara spesifik, bentuk SPAL yang memiliki matriks tri-diagonal dapat disajikan sebagai berikut:  d1 c1   x1  a d c   x  2 2 2    2     x3  a3 d3 c3  ⋅  O O O M        an −1 d n −1 cn −1 xn −1      an d n   xn  

 b1  b   2   b3  =   M   b   n −1   bn 

atau [A]


[x] = [b]



K2. Teorema Solusi matriks Tri-Diagonal Jika matriks bujur-sangkar [A] di atas merupakan matriks yang dominan secara diagonal (atau definit :positif) dan membentuk matriks tri-diagonal, maka [A] memiliki suatu mentuk faktorisasi LU yang unik, dalam hal ini baik L maupun U hanya memiliki duadiagonal: L adalah matriks bawah dengan struktur diagonal utama (dituliskan dalam lambang [dl]) dan diagonal bawah (dituliskan dalam lambang [al]); sedangkan matriks U adalah matriks atas yang berisi diagonal utama [du] dan diagonal atas [cu]. Langkah solusi yang digunakan adalah analogi dengan metode ELIMINASI GAUSS. Dalam hal ini jika penulisan SPAL di atas disusunulang menjadi:

 d1 x1 c1 x2  a x d x c x  2 1 2 2 2 3     a3 x1 d3 x2 c3 x3   O O O    an −1 x1 d n −1 x2 cn −1 x3    an x1 d n x2  

 b1  b   2   b3  =   M   b   n −1   bn 

Dapat dilihat dengan jelas, selain ketiga diagonal di atas matriks [A] hanya diisi oleh elemen 0 (nol), yang berarti bahwa matriks [A] di atas, tidak perlu disimpan dalam suatu variabel berbentuk matriks, melainkan cukup hanya dalam 3 buah ventor dengan panjang masing-masing (maksimum) sebesar n elemen. Jumlah memori untuk penyimpanan menjadi semakin sangat berarti pada saat harga n menjadi sangat besar. Hal lain yang perlu dicatat adalah, bahwa pada setiap kolom, hanya diperlukan 1 buah elemen tak-nol (bukan 0) yang dieliminasi, yang berarti juga sebagai Intellectual Property of DR. Ir. Setijo Bismo, DEA., TGP-FTUI



“penghematan usaha dan daya komputasi numerik” yang relatif sangat besar, bila dibandingkan dengan penghitungan melalui matriks penuh. Selanjutnya, langkah algoritma penyelesaiannya adalah sebagai berikut: (a). Jika d1 ≠ 0, maka x1 dapat dieliminasi dari persamaan kedua dengan menghitung “faktor pengali” berikut: m1 =

a2 d1

dan dihasilkan persamaan baru sebagai berikut:

d 2' x2 + c2 x3 = b2' dengan, d 2' = d 2 − m1 c1 b2' = b2 − m1 b1' (b). Dengan cara yang sama, jika d 2' ≠ 0 , x2 dapat dieliminasi dari persamaan ketiga sehingga dihasilkan persamaan ketiga yang baru, sebagai berikut:

d3' x3 + c3 x4 = b3' dengan, m2 =

a3 d 2'

dan

d3' = d3 − m2 c2 Intellectual Property of DR. Ir. Setijo Bismo, DEA., TGP-FTUI



b3' = b3 − m2 b2'

(c). Teruskan cara perhitungan di atas, sehingga dapat disimpulkan pada tahap-i, xi dapat dieliminasi dari persamaan i+1 (dengan asumsi d i' ≠ 0 ) dan memberikan persamaan baru berikut:

di' +1 xi +1 + ci +1 xi + 2

= bi' +1

dengan, mi =

ai +1 d i'

dan

di' +1 = di +1 − mi ci bi' +1 = bi +1 − mi bi'

(d). Sekuens-sekuens dalam butir (c) di atas sebenarnya merupakan sesuatu yang beraturan, yaitu keberulangan dari i = 1, 2, … , n-1, sehingga sistem awalnya tertransformasi menjadi “matriks segitiga atas” (e). Sebagai solusi akhirnya, yaitu “substitusi balik” yang juga mirip dengan “metode eliminasi Gauss”, yaitu dengan menganggap bahwa d n' ≠ 0 , akan diperoleh: xn =

bn' d n'

dan kemudian, untuk i = n-1, n-2,…, 1, dapat digunakan: Intellectual Property of DR. Ir. Setijo Bismo, DEA., TGP-FTUI



xi =

bn' − ci xi +1 di'

Listing Program Matriks Tri-Diagonal: C C

PROGRAM Solusi Sistem Persamaan Aljabar Linier (SPAL) atau atau Persamaan Aljabar Linier Simultan dengan TEKNIK TRIDIAGONAL

C C

Deklarasi Jenis dan Variabel: ----------------------------IMPLICIT NONE INTEGER iarg PARAMETER (iarg = 7) INTEGER i,neq REAL*8 a(iarg),b(iarg),c(iarg),d(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),c(1),b(1) DO i = 2,neq-1 READ(10,*) a(i),d(i),c(i),b(i) ENDDO READ(10,*) a(neq),d(neq),b(neq)

C C

Proses Pemanggilan Subprogram Eliminasi Gauss-Jordan: ----------------------------------------------------CALL S3DIAG(neq,a,d,c,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

SUBROUTINE S3DIAG(n,a,d,c,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 a = vektor koefisien pada diagonal bawah dengan dimensi n-1, | C d = vektor koefisien pada diagonal utama dengan dimensi n, | C c = vektor koefisien pada 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 a(n),d(n),c(n),b(n),x(n) INTEGER i REAL*8 PIVOT,MULT

C C

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

C C

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

L. Daftar Pustaka Atkinson, Kendal E., “An Introduction to Numerical Analysis”, John Wiley & Sons, Toronto, 1978. Atkinson, L.V., Harley, P.J., “An Introduction to Numerical Methods with Pascal”, Addison-Wesley Publishing Co., Tokyo, 1983. Bismo, Setijo, “Kumpulan Bahan Kuliah Metode Numerik”, Jurusan TGP-FTUI, 1999. Hanna, O.T., Sandall, O.C., “Computational Methods in Chemical Engineering”, Prentice-Hall International Inc., Englewood Cliffs, New Jersey, 1995. Press, W.H., Flannery, B.P., Teukolsky, S.A., dan Vetterling, W.T., “Numerical Recipes”, Cambridge Univ. Press, 1986.



Modul 2: Solusi Sistem Persamaan Aljabar Linier (SPAL) dengan Metode Eliminasi Gauss dan variannya

Recommend Documents