PEMECAHAN SISTEM PERSAMAAN LINIER NON HOMOGEN DENGAN METODE SAPUAN GANDA CHOLESKY Oleh : Yusup Fakultas Ilmu Komputer, Universitas AKI Semarang Abstract The fraction of Non Homogen Linearity Adjustment System toward Cholensky Double Sweeping Method is by substituting the grade of xi – 1 in i row of linearity adjustment system. After that it counts the coeficiency of Pi and Qi from grade i = 1 to i = n, as the first sweeping step. As it reaches n point, the calculation is conducted on the contrary, that is from n to 1, to count unknown xi. number. Keywords : Tridiagonal Matrix, Linear Equation Systems, Cholesky. Pendahuluan Persamaan Linier sering dipakai dalam proses analisis, desain dan sintesis dari sistem perekayasaan. Sebuah Sistem
sehingga diperoleh matriks
Persamaan Linier yang terdiri dari m buah persamaan linier dengan n buah bilangan yang tidak diketahui dapat dinyatakan dengan : Jika B = 0 (matriks nol) maka Sistem Persamaan Linier itu disebut dengan Sistem
Persamaan
Linier
Homogen.
Sedangkan jika B 0, maka Sistem Persamaan Linier tersebut disebut dengan dimana x1, x2, … , xn adalah bilanganbilangan yang tidak diketahui dan a, b menyatakan kontanta-konstanta. Dan apabila Sistem Persamaan Linier tersebut
dinyatakan
dengan
perkalian
matriks AX = B, maka dapat dinyatakan dengan : -34-
Sistem Persamaan Linier Non Homogen. Persamaan
Linier
mempunyai
3
(tiga)
tersebut
akan
kemungkinan
penyelesaian, yaitu : a. Penyelesaian yang unik, jika A 0,
Pemecahan SPL Non Hmogen denganMetode Sapuan Ganda Cholesky (Yusup)
b. Tidak mempunyai penyelesaian jika A = 0 dan B 0,
sehingga
c. Penyelesaian lebih dari satu jika A
semua
persamaan
linier
terpenuhi. Solusi tersebut dapat disajikan dalam bentuk vektor yang disebut dengan
= 0 dan B = 0. Penyelesaian
berlaku x1 = k1, x2 = k2, …, xn = kn,
(Solusi)
dari
Sistem
vektor
solusi.
Bagan
berikut
Persamaan Linier tersebut adalah jika
memudahkan
terdapat himpunan bilangan k1, k2, …, kn
gambaran secara umum tentang Sistem
yang
Persamaan
merupakan
nilai
dari
variabel-
untuk
ini
mendapatkan
Linier.
variabel yang tidak diketahui (x), dan Sistem Persamaan Linier AX = B
Homogen B=0
Tak Homogen B0
Tidak Ada Solusi r(A) r(A,B)
Selalu Ada Solusi
Solusi Trivial (Solusi Nol)
Solusi Non Trivial
Ada Solusi r(A) = r(A,B)
Solusi Tunggal r=n
Solusi Banyak r
Gambar 1. Gambaran Umum Sistem Persamaan Linier
Dimana : n = jumlah variabel yang tidak diketahui. r = rank matriks. Pandang matriks A berordo (mxn) dengan elemen-elemennya bilangan riil :
a11 a12 a1n a a 22 a 2n 21 A= a m1 a m1 a mn Tiap-tiap baris (kolom) dari matriks A dapat dipandang sebagai vektor-vektor baris
(kolom)
dari
A,
yang
akan
-35-
Majalah Ilmiah INFORMATiKA Vol. 2 No.1 Januari 2011 membentuk ruang vektor. Sehingga dapat
Metode Sapuan Ganda Cholesky
didefinisikan bahwa rank baris (kolom)
Disebut juga metode penyelesaian
dari matriks A ditulis r(A) adalah dimensi
langsung, karena pemakaiannya mudah dan
dari ruang baris (kolom) matriks A.
matriks tridiagonal banyak dijumpai dalam
Dimensi
berbagai permasalahan terutama dalam
ruang
vektor
baris
(kolom)
matriks A didefinisikan sebagai jumlah maksimum vektor-vektor baris (kolom) yang
bebas
linier,
sedangkan
penyelesaian Sistem Persamaan Linier. Matriks, Tridiagonal adalah matriks
setiap
yang mempunyai elemen sama dengan 0,
himpunan n vektor baris (kolom) yang
kecuali pada satu jalur yang berpusat pada
bebas linier dari ruang vektor baris (kolom)
diagonal utama, bentuknya sebagai berikut:
berdimensi n disebut basis dari ruang
a11 a12 a a 22 A = 21 0 a32 0 0
vektor baris (kolom) itu. Jadi rank matriks menyatakan jumlah maksimum vektorvektor baris (kolom) yang bebas linier.
0 a 23 a33 a 43
0 0 a34 a 44
Dipandang Sistem Persamaan Linier sebagai berikut:
b1 x1 c1 x2 a x b x c x 2 3 2 1 2 2 a3 x2 b3 x3 c3 x4 ai xi 1 bi xi ci xi 1 a n xn 1 bn xn
Baris pertama pada persamaan (1) dari
d1 d 2 d3 (1) di d n
sistem memungkinkan untuk menulis
c1 d dan Q1 = 1 , bila b1 b1
bilangan tak diketahui x1 sebagai fungsi
nilai x1 disubstitusikan ke dalam baris
bilangan tak diketahui x2 dalam bentuk:
kedua persamaan (1), maka didapat:
x1 = (2) -36-
c1 d x2 + 1 atau x1 = P1 x2 + Q1 b1 b1
dengan P1 =
Pemecahan SPL Non Hmogen denganMetode Sapuan Ganda Cholesky (Yusup)
a2 (
c1 d x2 + 1 ) + b2 x2 + c2 x3 = d2 b1 b1
atau (
a2 c1 + b2 ) x2 = c2 x3 + (d2 b1
d1 ) b1
a2
xi =
ci (ai Pi 1 bi )
(ai Pi 1 bi )
dalam bentuk: xi = Pi xi + 1 + Qi (3a) dengan:
Q2
Pi
=
ci (ai Pi 1 bi )
dan
(3b)
dengan P2 =
d1 b1
a 2 c1 b2 b1
c2 dan Q2 = a 2 c1 b2 b1
Qi =
di ai Qi 1
(3c)
(ai Pi 1 bi )
Untuk i = 1, maka persamaan (3a), menjadi:
,
persamaan
ini
x1 = P1x2 + Q1 (4a) dengan:
menunjukkan bahwa x2 merupakan fungsi dari x3, langkah seperti tadi dapat diulangi lagi untuk semua baris pada persamaan berikutnya. Dengan demikian setiap bilangan tak diketahui dapat dinyatakan sebagai bilangan tak
Misalnya telah diperoleh persamaan
c1 dan (4b) (a1 P0 b1 )
d1 a1 Q0 (4c) (a1 P0 b1 )
Perbandingan persamaan (4) dan (2), menunjukkan bahwa: P0 = 0 dan Q0 = 0
(5)
untuk menghitung koefisien Pi serta Qi dari nilai i = 1 sampai i = n, langkah ini
sebagai berikut:
merupakan sapuan pertama. Setelah
xi – 1 = Pi – 1 xi + Qi – 1 Apabila nilai xi
Q1 =
P1 =
Persamaan (4) dan (5), memungkinkan
diketahui berikutnya.
– 1
disubstitusikan ke
dalam baris ke i dari sistem persamaan (1), maka: ai (Pi – 1 xi + Qi – 1) + bi xi + ci xi + 1 = di (ai Pi – 1 + bi ) xi + ci xi + 1 = di (ai Qi – 1)
di ai Qi 1
Persamaan tersebut di atas dapat ditulis
dapat pula ditulis sebagai: x2 = P2 x3 +
d 2 a2
xi 1 +
sampai titik ke n hitungan dilakukan dalam arah kebalikannya, yaitu dari n ke 1, untuk menghitung bilangan tak diketahui xi. Untuk itu persamaan terakhir dari sistem persamaan (1) ditulis dalam bentuk: -37-
Majalah Ilmiah INFORMATiKA Vol. 2 No.1 Januari 2011
2 x1 x2 7 x1 x2 3x3 10 6 x 2 2 x3 x 4 7 2 x3 3x4 13
an xn – 1 + bn xn = dn (6) Pada sistem persamaan (3), apabila i = n 1, maka: xn – 1 = Pn – 1 xn + Qn – 1 (7)
(c1)
Substitusi dari persamaan (7) ke dalam
Penyelesaian:
persamaan (6), akan memberikan:
Sistem persamaan di atas dapat ditulis
an(Pn – 1 xn + Qn – 1) + bnxn = dn
dalam bentuk matriks tridiagonal, yang
(anPn – 1 + bn ) xn = dn an Qn – 1
penyelesaiannya
xn =
d n an Qn 1
dengan
(an Pn 1 bn )
berikut:
dapat
dilakukan
menggunakan
persamaan
Sesuai dengan persamaan (3a), maka: xi = Pi xi + 1 + Qi (c2)
xn = Qn. Nilai xn dapat diperoleh, berdasarkan nilai xn yang didapat maka nilai xn
dengan:
Qi =
Dari nilai xn – 1 kemudian dihitung nilai xn
– 3,
ci (ai Pi 1 bi )
di ai Qi 1 (ai Pi 1 bi )
(c4)
Skema penyelesaian sistem persamaan
dan seterusnya hingga ke
dengan metode sapuan ganda sebagai
nilai x1.
berikut: Contoh soal: Selesaikan sistem persamaan berikut ini
dengan
menggunakan
metode
sapuan ganda. Pi , Qi (i = 1,2,3,4) P1 , Q1
P2 , Q2
P3 , Q3
P4 , Q4
i=1
i=2 x2
i=3 x3
i=4 x4
x1
xi (i = 4,3,2,1)
-38-
dan
(c3)
sebagai berikut: xn – 1 = Pn – 1 xn + Qn – 1.
– 2,
=
– 1
dapat dihitung pula dengan persamaan
xn
Pi
Pemecahan SPL Non Hmogen denganMetode Sapuan Ganda Cholesky (Yusup)
d 2 a2 Q1 (10) 1(3,5) = 1(0,5) 1 a2 P1 b2
Q2 = Langkah pertama dihitung nilai Pi dan Qi (i = 1, 2, 3, 4) dari kiri ke kanan.
13,5 = 27. 0,5
=
Setelah sampai ke titik i = n = 4, dihitung nilai xn = Qn. Berdasarkan
Untuk i = 3, P2 = 6 dan Q2 = 27.
nilai xn tersebut, kemudian hitungan
P3 =
dilanjutkan dari kanan ke kiri untuk mendapatkan nilai xi (i = 4, 3, 2, 1). a) Menghitung koefisien Pi dan Qi (i =
c3 1 = = a3 P2 b3 6 6 2
1 = 0,02941. 34
Q3 =
1, 2, 3, 4)
d 3 a3 Q2 7 (6 (27)) = = a3 P2 b3 6 (6) (2)
dengan menggunakan persamaan
169 = 4,97059. 34
(c3) dan (c4), berdasarkan sistem
Untuk i = n = 4, Pn = 0 dan Qn =
Koefisien
Pi
dan
Qi
dihitung
persamaan (c1).
d n an Qn 1
, maka:
Untuk i = 1, P0 = 0 dan Q0 = 0.
(an Pn 1 bn ) x4
=
P1 =
c1 c 1 = 1 = = 2 a1 P0 b1 b1
0,5. Q1 =
d1 a1 Q0 7 70 = = = a1 P0 b1 0 2 2
3,5. Untuk i = 2, P1 = 0,5 dan Q1 =
Q4
d 4 a4 Q3 a4 P3 b4
13 (2 (4,97059 )) 2 (0,02941) (3)
= =
3,05882 = 1,00. 3,05882 Setelah nilai Pi dan Qi (i = 1, 2, 3, 4) didapat, lalu dihitung nilai xi (i =
3,5. P2
=
=
3 = 6. 1 0,5 1
c2 = a2 P1 b2
4, 3, 2, 1).
b) Menghitung xi (i = 4, 3, 2, 1) Variabel xi (i = 4, 3, 2, 1) dihitung dengan menggunakan persamaan (c2): xi = Pi xi + 1 + Qi Untuk i = 4, maka x4 = Q4 = 1,00.
-39-
Majalah Ilmiah INFORMATiKA Vol. 2 No.1 Januari 2011 Untuk i = 3, maka x3 = P3x4 + Q3 =
x1 = 2,00;
(0,02941(1,00)) + 4,97059 =
x4 = 1,00.
5,00.
Untuk
Untuk i = 2, maka x2 = P2x3 + Q2 =
tidaknya hasil yang diperoleh, maka
(6(5,00)) + (27) = 3,00.
nilai-nilai tersebut dimasukkan ke
Untuk i = 1, maka x1 = P1x2 + Q1 =
dalam
(0,5(3,00)) + 3,5 = 2,00.
diselesaikan.
Dengan
demikian
hasil
x2 = 3,00; x3 = 5,00;
mengetahui
persamaan
benar
yang
yang
diperoleh adalah:
2 (2,00) 2,00
+ 3,00
= 7
(= 7)
+ 3,00
3 (5,00)
= 10
(= 10)
6 (3,00)
2 (5,00) + (1,00)
= 7
(= 7)
2 (5,00) 3 (1,00) = 13 Daftar Pustaka Chapra Steven C, Canale Raymond P, 2006, Numerical Methods for Engeneers, Fifth Edition, Mc Graw Hill Inc, New York. Charles G. Cullen (alih bahasa oleh Bambang Sumantri, Ir.), 1993, Aljabar Linier dengan Penerapannya, PT. Gramedia Pustaka Utama, Jakarta. 202.91.15.14/upload/files/4460_Bab_2.doc (Senin, 10 januari 2011)
-40-
(= 13)
atau
telah
