MENGEMBANGKAN PENYELESAIAN NUMERIK PADA SISTEM PERSAMAAN LINIER DENGAN KONSEP ALJABAR Bambang Agus Sulistyono Pendidikan Matematika Universitas Nusantara PGRI Kediri email:
[email protected]
Abstrak Permasalahan sistem persamaan linear banyak dijumpai dalam persoalan ilmu pengetahuan dan teknologi, seperti pada penyelesaian numerik persamaan diferensial biasa, diferensial parsial, analisis jaringan dan sebagainya. Ukuran yang besar dan bilangan yang terlibat dalam matriks seringkali menjadi kendala dalam menyelesaikan secara analitik. Penyelesaian secara numerik adalah salah satu alternatif yang dapat dilakukan. Dalam mengembangkan kearah numerik, algoritma dibangun dengan konsep aljabar, agar mampu digunakan dalam menyelesaikan sistem persamaan linear secara umum. Dalam paper ini dibahas bagaimana mengkonstruksi algoritma dari bentuk aljabar linier ke perhitungan numerik. Kata kunci : sistem linear, metode langsung, metode iterasi.
yang
1. PENDAHULUAN Sistem persamaan linear muncul
memenuhi
sistem
persamaan
berikut:
hampir di setiap cabang matematika
a11 x1 a12 x2
a1n xn
b1
terapan. Dalam beberapa hal persamaan
a21 x1 a22 x2
a2 n xn
b2
an1 x1 an 2 x2
ann xn
bn
ini muncul langsung dari perumusan awal dari persoalannya, di dalam banyak hal lain
penyelesaian
merupakan
dari
persamaan
dengan a adalah koefisien konstan, b
dari
pengerjaan
adalah
bagian
konstan,
n
beberapa macam persoalan lain. Hal yang
persamaan,
menarik
bilangan tak diketahui.
adalah
bahwa
persamaan
diferensial
didekati
dengan
membutuhkan
penyelesaian parsial
metode
penyelesaian
dan
adalah
jumlah adalah
sering
Dalam paper ini akan dikaji dua
yang
metode numerik untuk menyelesaikan
sistem
sistem persamaan linier yaitu metode
persamaan.
langsung (seperti eliminasi Gauss
Di dalam
penyelesaian sistem
dan
dekomposisi LU ) dan metode iterasi
persamaan akan dicari nilai
382
Jurnal Ilmiah Pendidikan Matematika Vol 3 No. 2 Februari 2015
383
Bambang Agus Sulistyono : Mengembangkan Penyelesaian ......382 - 389
(seperti metode iterasi Jacobi dan metode
ke 1 dilakukan untuk membuat a21
iterasi Gauss-Seidel).
menjadi nol. Di sini kita gunakan
p
a21 / a11 ,
a11
sebagai pembagi
2. PEMBAHASAN disebut elemen pivot. Pada tahap ini
Metode Langsung
algoritma dapat disusun
a. Eliminasi Gauss Metode eliminasi Gauss adalah salah satu metode yang paling awal
p:=-a[2,1]/a[1,1] Untuk j:=2, 3, …, n+1 a[2,j]:=a[2,j]+p*a[1,j]
dikembangkan dan banyak digunakan dalam penyelesaian sistem persamaan
a[2,1]:=0
linier. Prosedur penyelesaian dari metode ini adalah mengurangi sistem persamaan ke dalam bentuk segitiga atas sedemikian
Penggantian baris ke-3 dengan baris ke-3 ditambah p kali baris ke 1 dilakukan
sehingga salah satu dari persamaan-
untuk membuat a31 menjadi nol, kita
persamaan tersebut hanya mengandung
gunakan
satu bilangan tak diketahui, dan setiap
algoritma
p
a31 / a11 ,
persamaan berikutnya hanya terdiri dari
p:=-a[3,1]/a[1,1]
satu tambahan bilangan tak diketahui
Untuk j:=2, …, n+1
baru.
dengan
a[3,j]:=a[3,j]+p*a[1,j] Untuk itu terlebih dahulu tuliskan
a[3,1]:=0
sistem persamaan linier di atas ke dalam bentuk matrik yang diperbesar,
a11 a12 a21 a22
a1n a2 n
Penggantian baris ke-4 dan seterusnya
a1n 1 a2 n 1
dapat dilakukan dengan cara yang sama, sehingga
keseluruhan
tahap
tersebut
dapat digabungkan menjadi
an1
ann
ann
1
Untuk i:=2, 3, …, n
Kolom ke-n+1 sebagai vektor b. OBE
p:=a[i,1]/a[1,1]
selanjutnya diterapkan untuk membuat
Untuk j:=2, 3, …, n+1
nol elemen yang berada di bawah diagonal utama. Untuk membuat nol elemen a21 , a31 ,
, an1 , kita ikuti proses
berikut. Operasi penggantian baris ke-2
a[i,j]:=a[i,j]-p*a[1,j] a[i,1]:=0 Sampai di sini kita peroleh matrik perluasan, menjadi
dengan baris ke-2 ditambah p kali baris
Jurnal Ilmiah Pendidikan Matematika Vol 3 No. 2 Februari 2015
384
Bambang Agus Sulistyono : Mengembangkan Penyelesaian ......382 - 389
a11 0 0 0
a12 a22
a1n a2 n
utama. Sehingga penyelesaian SPL dalam
a1n 1 a2 n 1
dua tahap
Ly b, Ux an 2
ann
ann
y
1
diselesaikan
dari
y SPL
pertama,
Tahap berikutnya adalah membuatnol
kemudian diikuti menentukan x melalui
kolom ke-2 (warna merah), dengan
matrik U . Masalah sekarang adalah
algoritma
bagaimana mendekomposisi A menjadi Untuk i:=3, …, n
dua matrik L dan U , dan membuat
p:=a[i,2]/a[2,2]
algoritma-nya.
Untuk j:=3, …, n+1
Kita ikuti proses dekomposisi
a[i,j]:=a[i,j]-
untuk
p*a[2,j]
matrik
ukuran
3x3
berikut.
Diberikan matrik
a[i,2]:=0 Begitu seterusnya untuk kolom yang lain,
A:
sehingga keseluruhan diperoleh algoritma
a11(1) (1) a21
a12(1) (1) a22
a13(1) (1) a23
(1) a31
(1) a32
(1) a33
eliminasi Gauss
Kita gunakan superscript (1) untuk
Untuk k:=1, 2, …, n-1 Untuk i:=k+1, k+2, …, n
menyatakan sebagai notasi awal, dan
p:=a[i,k]/a[k,k]
setelah
melalui
proses
perhitungan
Untuk j:=k+1, k+2,
tempat yang ada akan ditimpa, karena matrik L dan U akan disimpan pada
…, n+1
matrik A tersebut.
a[i,j]:=a[i,j]-
Sebagai matrik dekomposisinya
p*a[k,j]
kita misalkan mempunyai elemen
a[i,k]:=0
L
b. Dekomposisi LU Suatu cara menyelesaikan SPL
1
0
0
a11
a21
a13
m21
1
0 , U
0
a22
a23
m31
m32
1
0
0
a33
Ax b adalah dengan memecah matrik
A
Hasil perkalian
menjadi matrik segitiga bawah L dan matrik segitiga atas U , lebih khusus lagi
L mempunyai elemen 1 pada diagonal
LU
a11
a12
a13
m21a11
a12 m21 a22
a13 m21 a23
a11m31
a12 m31 a22 m32
Jurnal Ilmiah Pendidikan Matematika Vol 3 No. 2 Februari 2015
a13m31 a23m32
a33
385
Bambang Agus Sulistyono : Mengembangkan Penyelesaian ......382 - 389
(3) a33
A , dan
disamakan dengan elemen
(2) a33
a33
(2) . m32 a23
Hasil
ditentukan elemen pada matrik L dan U
perhitungan, matrik L dan U diletakkan
,
pada satu matrik
baris a11
pertama: (1) 11
a ,
(1) 12
a12
a ,
(1) 13
a13
a
baris kedua: (1) (2) a21 / a11(1) , a22
m21
(2) a23
a11(1) m21
a12(1) (2) a22
a13(1) (2) a23
m31
m32
(3) a33
(1) a22 m21a12(1)
a22
(1) a23 m21Sekarang a13(1) kita lihat proses dekomposisi
a23
untuk matrik ukuran 4x4. Dari matrik
(1) (1) , dan kita a31 / a11
baris ketiga: m31 gunakan notasi (2) 32
a
(1) 32
a
(1) 31 12
m a ,
(2) 33
a
(1) 33
(1) 31 13
a
m a
a11(1) (1) a21
a12(1) (1) a22
a13(1) (1) a23
a14(1) (1) a24
(1) a31
(1) a32
(1) a33
(1) a34
(1) a41
(1) a42
(1) a43
(1) a44
kita misalkan didekomposisi menjadi sebagai
notasi
mewadahi kesamaan
dua (1) a32
sementara
untuk
suku
pertama
dari
m31a12
m32 a22
pada
L:
elemen baris-3 kolom-2, sama halnya
1 m21
0 1
m31 m32 m41 m42
0 0
0 0
1 m43
0 1
U:
a11
a12
a13
a14
0 0
a22 0
a23 a33
a24 a34
0
0
0
a44
untuk baris-3 kolom-3. Sehingga m32 dapat m32
dihitung (2) 32
a
LU
(2) 22
/a
,
menggunakan dan
Hasil
perkalian
keduanya
akhirnya
a11 m21a11
a12 m21a12 a22
a13 m21a13 a23
a14 m21a14 a24
m31a11 m41a11
m31a12 m32 a22 m41a12 m42 a22
m31a13 m32 a23 a33 m41a13 m42 a23 m43a33
m31a14 m32 a24 a34 m41a14 m42 a24 m43a34 a44
Dengan menyamakan LU dan A , kita
m21
(1) (2) a21 / a11(1) ; a22
peroleh a11
(1) a11 ,
a12
(1) a12 ,
a13
(1) a13 ,
a14
(1) a14 ,
Jurnal Ilmiah Pendidikan Matematika Vol 3 No. 2 Februari 2015
(1) a22 m21a12(1)
(2) a23
(1) a23 m21a13(1)
(2) a24
(1) a24 m21a14(1)
386
Bambang Agus Sulistyono : Mengembangkan Penyelesaian ......382 - 389
(1) (2) a31 / a11(1) ; a32
m31
(1) a32 m31a12(1)
(2) a33
(1) a33 m31a13(1)
(2) a34
(1) a34 m31a14(1)
m42
(2) (2) (3) a42 / a22 ; a43
(2) (2) a43 m42 a23
(3) a44
(2) (2) a44 m42 a24
berkaitan dengan suku warna merah dan nilai
biru pada matrik LU . Sampai tahap ini
sementara dari elemen pada posisi yang
kita sudah menghitung hamper semua
ditunjukkan oleh indek, terkait dengan
elemen
suku yang berwarna merah pada LU .
ditampilkan pada matrik berikut, warna
(2) (2) (2) a32 , a33 , a34
merupakan
(1) (2) a41 / a11(1) ; a42
m41
(2) 42
a
(2) 43
,a
(2) 44
U , seperti yang
dan
hijau.
(1) a42 m41a12(1)
(2) a43
(1) a43 m41a13(1)
(2) a44
(1) a44 m41a14(1)
merupakan
,a
L
nilai
a11(1) m21
a12(1) (2) a22
a13(1) (2) a23
a14(1) (2) a24
m31
m32
(3) a33
(3) a34
m41
m42
a4(3)3
a4(3)4
Dua elemen tersisa dihitung sebagai
sementara dari elemen pada posisi yang
berikut
ditunjukkan oleh indek, terkait dengan
m43
suku yang berwarna merah pada LU .
(3) (3) a43 / a33 ;
(4) a44
Sampai tahap ini, matrik yang diperoleh,
L dan U disimpn dalam matrik A , (1) 11
(1) 12 (2) 22 (2) 32 (2) 42
(1) 13 (2) 23 (2) 33 (2) 43
(1) 14 (2) 24 (2) 34 (2) 44
a m21
a a
a a
a a
m31
a
a
a
m41
a
a
a
Baris pertama dan kedua sudah selesai diolah,
begitu
juga
dengan
kolom
pertama (warna hijau). Baris ke tiga dan ke empat perlu disempurnakan. Untuk itu kita lakukan perhitungan
m32
Sehingga diperoleh
a11(1) m21
a12(1) (2) a22
a13(1) (2) a23
a14(1) (2) a24
m31
m32
(3) a33
(3) a34
m41
m42
m43
(4) a44
Dengan
mengikuti
proses
dekomposisi dari matrik 3x3 dan 4x4, diharapkan berpikir
dapat untuk
memberikan
pola
mendekomposisikan
matrik ukuran nxn. Sedangkan eksistensi
(2) (2) (3) a32 / a22 ; a33 (3) a34
(2) (2) a33 m32 a22
dari dekomposisi matrik A=LU dijamin:
(2) (2) a34 m 32 a14 Anton (lihat & Rorres, Elementary
Linear Alg., hal. 479), yaitu:
Jurnal Ilmiah Pendidikan Matematika Vol 3 No. 2 Februari 2015
(3) a44
(3) m43 a34
387
Bambang Agus Sulistyono : Mengembangkan Penyelesaian ......382 - 389
Jika A matrik bujur sangkar yang dapat
Warna kuning merupakan elemen dari U
direduksi menjadi bentuk eselon baris U
dan sisanya elemen dari
dengan eliminasi Gauss tanpa penukaran
diagonal utama bernilai satu.
L dengan
baris, maka A dapat difaktorkan sebagai
A LU , U
Metode Iterasi
dengan
Em Em
; E1 , E2 ,
E2 E1 A,
1
E1 1 E2 1
L
Dalam
Em1
masing
, Em matrik elementer yang langkah-langkah
yang
dekomposisi
(1) a11 , a12
masing-
persamaan yang ada dihitung
tidak
diketahui,
menggunakan
pada matrik ukuran nxn: a11
iterasi,
nilai perkiraan awal dari satu variabel
berkaitan dengan operasi baris. Berikut
proses
(1) a12 ,
, a1n
nilai
dengan perkiraan
sebelumnya. Perhitungan ini diulang
a1(1) n
terus dengan harapan iterasi berikutnya akan lebih dekat ke solusi sebenarnya.
Untuk p=1,2,…,n
arc( p
Persamaan pertama dari Sistem (1)
arp( p ) / a (ppp ) , r
mrp 1)
arc( p )
p 1, p 2,dapat , n digunakan untuk menghitung mrp a (pcp ) , c p 1, sebagai p 2, , nfungsi dari
.
Persamaan kedua untuk menghitung Matrik yang diperoleh
sebagai
fungsi
dari
,
demikian seterusnya sehingga didapat :
a11(1) m21 m31
a12(1) (2) a22 m32
a13(1) (2) a23 (3) a33
a1(1)n a2(2)n a3(3)n
mn1
mn 2
mn 3
(n) ann
x1
b1
a12 x2 a13 x3
a1n xn
/ a11
x2
b2
a21 x1 a23 x3
a2 n xn
/ a22
xn
bn
an1 x1 an 2 x2
ann 1 xn
Hitungan dimulai nilai perkiraan
1
(2)
/ ann kanan
dari
sistem
Persamaan
(2).
awal sebarang untuk variabel yang dicari
Selanjutnya nilai variabel yang didapat
(biasanya semua variabel diambil sama
tersebut disubstitusikan ke ruas kanan
dengan
awal
dari Sistem (2) lagi untuk mendapatkan
tersebut disubstitusikan ke dalam ruas
nilai perkiraan kedua. Prosedur tersebut
nol).
Nilai
perkiraan
Jurnal Ilmiah Pendidikan Matematika Vol 3 No. 2 Februari 2015
388
Bambang Agus Sulistyono : Mengembangkan Penyelesaian ......382 - 389
diulangi lagi sampai nilai setiap variabel
iterasi ke n-1. Persamaan (2) dapat ditulis
pada iterasi ke n mendekati nilai pada
menjadi :
x1( k
1)
b1
a12 x2( k )
a13 x3( k )
a1n xn( k )
/ a11
x2( k
1)
b2
a21 x1( k )
a23 x3( k )
a2 n xn( k )
/ a22
xn( k
1)
bn
an1 x1( k )
an 2 x2( k )
ann 1 xn( k 1)
k
Superskript
pada
x
menyatakan
(3)
/ ann
juga nilai
tidak digunakan untuk
banyak-nya iterasi yang telah dilakukan.
mencari
Tentunya rumus iterasi tersebut dibentuk
tidak dimanfaatkan. Sebenarnya nilai
dengan memilih elemen diagonalnya
baru tersebut lebih baik dari nilai-nilai
tidak boleh nol. Bila ada yang nol, maka
yang lama. Didalam metode Gauss-
sistem persamaan linier perlu diubah
Seidel nilai-nilai dimanfaatkan untuk
lebih dahulu urutan persamaannya. Iterasi
menghitung variabel berikutnya. Iterasi Gauss-Seidel sebagai cara
diatas dikenal sebagai metode Jacobi, dan
penyelesaian sistem persamaan linier
penghentian iterasi dilakukan dengan
max xi( k
1)
1 i n
xi( k )
tidak jauh beda dengan iterasi Jacobi.
Tol
Pada iterasi Gauss-Seidel, nilai hasil
dapat juga digunakan nilai relatifnya
max 1 i n
, sehingga nilai-nilai tersebut
( k 1) (k ) i i ( k 1) i
x
x
x
perhitungan pada baris awal langsung digunakan
Tol
untuk
perhitungan
nilai
selanjutnya di dalam iterasi. Dengan cara ini konvergensi akan tercapai lebih cepat.
Di dalam metode Jacobi, nilai yang dihitung dari persamaan pertama
Bentuk
umum
iterasi
tidak digunakan untuk menghitung nilai
adalah sebagai berikut :
Gauss-Seidel
dengan persamaan kedua. Demikian
Pada
x1( k
1)
b1
a12 x2( k )
x2( k
1)
b2
a21 x1( k
1)
a23 x3( k )
x3( k
1)
b2
a31 x1( k
1)
a32 x3( k
1)
xn( k
1)
bn
an1 x1( k
1)
an 2 x2( k
1)
saat
gunakan
menghitung x2( k ) , x3( k ) , x4( k ) ,
a13 x3( k )
x1( k
a1n xn( k )
/ a11
a2 n xn( k ) a34 x4( k )
/ a22 a2 n xn( k )
ann 1 xn( k 11)
1)
kita
x2( k
1)
, xn( k ) ,
pada
x1( k
1)
/ a33
/ ann kita
, x3( k ) , x4( k ) ,
gunakan
, xn( k ) ,
Jurnal Ilmiah Pendidikan Matematika Vol 3 No. 2 Februari 2015
hasil
389
Bambang Agus Sulistyono : Mengembangkan Penyelesaian ......382 - 389
perhitungan sebelumnya digunakan pada tahap ini, begitu juga untuk menghitung
4. DAFTAR PUSTAKA
x3( k
1)
Djojodihardjo,
x1( k
1)
menggunakan , x2( k
1)
, x4( k ) ,
, xn( k ) ,
semakin
ke
bawah semakin banyak hasil iterasi kek+1 yang digunakan. Agar iterasi konvergen metoda Jacobi
dan
mengharuskan
juga
Gauss-Seidel
matrik
koefisiennya n
diagonal dominant, yaitu aii
aij . j 1 j i
H,
2000,
Metode
Numerik, Penerbit PT Gramedia Pustaka Utama. L.H. Wiryanto, 2014, Metoda Numerik Pada Sistem Persamaan Linier, disampaikan pada kuliah tamu di UNP Kediri. Triatmodjo, B, 2002, Metode Numerik dilengkapi
dengan
program
komputer, Beta Offset.
Kondisi ini merupakan syarat cukup, yaitu
bila
dipenuhi
maka
iterasi
konvergen, tetapi bila tidak dipenuhi masih dimungkinkan konvergen, dengan lambat.
3. KESIMPULAN Sistem persamaan yang banyak dijumpai bersifat ‘jarang’ dan banyak koefisien yang merupakan nol. Dalam hal ini cara iterasi lebih baik. Sistem persamaan ini banyak dijumpai pada persamaan diferensial. Sistem persamaan yang banyak, bila diselesaikan dengan eliminasi
akan
kurang
teliti
dan
membutuhkan tempat yang banyak bila diprogram pada komputer.
Jurnal Ilmiah Pendidikan Matematika Vol 3 No. 2 Februari 2015
