METODE ITERASI DALAM SISTEM PERSAMAAN LINEAR Penulis: Dr. Eng. Supriyanto, M.Sc, email:
[email protected] Staf Lab. Komputer, Departemen Fisika, Universitas Indonesia Penulisan vektor-kolom Sebelum kita membahas metode iterasi untuk menyelesaikan problem sistem persamaan linear, saya ingin menyampaikan satu hal yang sangat sederhana, yaitu tentang cara merepresentasikan elemen-elemen suatu vektor-kolom. Sebagaimana tertulis pada catatan catatan sebelumnya, biasanya suatu vektor-kolom ditulis sebagai ⎡ ⎤ x ⎢ 1⎥ ⎢ x2 ⎥ ⎢ ⎥ x=⎢ . ⎥ ⎢ .. ⎥ ⎣ ⎦ xn Dengan operasi transpose, vektor-kolom tersebut dapat dinyatakan sebagai t x = x1 x2 . . . xn Contoh:
⎡
3
(1)
(2)
⎤
⎢ ⎥ t ⎢−2⎥ ⎥ = 3 −2 8 5 x=⎢ ⎢8⎥ ⎣ ⎦ 5 Cara penulisan seperti ini digunakan untuk menyatakan vektor-kolom pada suatu kalimat didalam paragraf. Alasannya supaya tidak terlalu menyita banyak ruang penulisan. Sementara, persamaan (1), lebih sering digunakan pada penulisan operasi matrik. Satu hal lagi, pada paragraf-paragraf berikutnya, saya persingkat penulisan istilah vektor-kolom menjadi vektor saja. Pengenalan norm Vektor x = (x1 ; x2 ; ...; xn )t memiliki norm 2 dan ∞ yang didefinisikan sebagai 2 = x2 = {
n i=1
1
x2i }1/2
(3)
dan ∞ = x∞ = max |xi | 1≤i≤n
(4)
Contoh: x = (3; −2; 8; 5)T memiliki norm 2 yaitu 2 = x2 =
(3)2 + (−2)2 + (8)2 + (5)2 = 10, 0995
dan norm ∞ yaitu ∞ = x∞ = max{(3), (−2), (8), (5)} = 8 Saya menyarankan agar kedua norm ini diingat-ingat dengan baik, karena akan banyak disinggung pada catatan-catatan berikutnya. Pengenalan metode iterasi Sekarang kita mulai pembahasan tentang metode iterasi untuk menyelesaikan problem sistem persamaan linear. Metode ini berbeda dengan metode-metode yang telah dijelaskan sebelumnya, dimana metode ini dimulai dengan menentukan nilai awal (initial value) untuk setiap elemen vektor x. Kemudian berdasarkan nilai awal tersebut, dilakukan langkah perhitungan untuk mendapatkan elemen-elemen vektor x yang baru. x(baru) = T x(lama) + c atau xk = T xk−1 + c
(5)
dimana k = 1, 2, 3, ... Untuk lebih jelasnya, marilah kita perhatikan contoh berikut, diketahui sistem persamaan linear Ax = b yaitu 10x1 − x2 + 2x3 = 6 −x1 + 11x2 − x3 + 3x4 = 25 2x1 − x2 + 10x3 − x4 = −11 3x2 − x3 + 8x4 = 15
2
Lalu, sistem persamaan tersebut diubah susunannya menjadi seperti ini 1 2 6 x2 − x3 + x1 = 10 10 10 1 1 3 25 x2 = x1 + x3 − x4 + 11 11 11 11 2 1 1 11 x3 = − x1 + x2 + x4 − 10 10 10 10 3 1 15 x4 = − x2 + x3 + 8 8 8 Kita bisa menyatakan bahwa nilai x1 , x2 , x3 dan x4 yang berada di ruas kiri tanda = (baca: sama dengan) sebagai x(baru) . Sementara nilai x1 , x2 , x3 dan x4 yang berada di ruas kanan tanda = (baca: sama dengan) sebagai x(lama) . Sistem persamaan tersebut menjadi seperti ini 1 (lama) 2 (lama) 6 x2 − x3 + 10 10 10 1 (lama) 1 (lama) 3 (lama) 25 x1 = + x3 − x4 + 11 11 11 11 2 (lama) 1 1 (lama) 11 = − x1 + x2 + x4 − 10 10 10 10 3 (lama) 1 (lama) 15 = − x2 + x3 + 8 8 8
(baru)
x1
=
(baru)
x2
(baru)
x3
(baru)
x4 atau seperti ini
1 (k−1) 2 (k−1) 6 x2 − x3 + 10 10 10 1 1 3 (k−1) 25 (k) (k−1) (k−1) + x3 − x4 + x2 = x1 11 11 11 11 2 1 1 11 (k) (k−1) (k−1) (k−1) + x2 + x4 − x3 = − x1 10 10 10 10 3 1 15 (k) (k−1) (k−1) + x3 + x4 = − x2 8 8 8 Sehingga bentuk sistem persamaan yang terakhir ini dapat dinyatakan dalam persamaan (k)
x1
=
matrik sebagai berikut x(k) = Tx(k−1) + c Pada k = 1, (1)
x1
(1)
x2
(1)
x3
(1)
x4
1 (0) 2 (0) 6 x2 − x3 + 10 10 10 1 (0) 1 (0) 3 (0) 25 x1 + x3 − x4 + = 11 11 11 11 2 (0) 1 (0) 1 (0) 11 = − x1 + x2 + x4 − 10 10 10 10 3 (0) 1 (0) 15 = − x2 + x3 + 8 8 8 =
3
(6)
(0)
(0)
(0)
Misalnya kita tentukan nilai-nilai awal x (0) sebagai berikut x1 = 0, x2 = 0, x3 = 0 (0)
dan x4 = 0. Atau dinyatakan seperti ini x(0) = (0; 0; 0; 0)t. Maka kita akan memperoleh nilai-nilai x(1) sebagai berikut (1)
x1
(1)
x2
(1)
x3
(1)
x4
6 10 25 = 11 11 = 10 15 = 8 =
atau x(1) = (0, 6000; 2, 2727; −1, 1000; 1, 8750)t. Setelah kita memperoleh nilai-nilai x(1) , perhitungan tersebut diulangi kembali dengan nilai k = 2. Lalu nilai-nilai x (1) = (0, 6000; 2, 2727; −1, 1000; 1, 8750)t dimasukan ke ruas kanan, (2)
x1
(2)
x2
(2)
x3
(2)
x4
1 (1) 2 (1) 6 x2 − x3 + 10 10 10 1 (1) 1 (1) 3 (1) 25 = x1 + x3 − x4 + 11 11 11 11 2 (1) 1 (1) 1 (1) 11 = − x1 + x2 + x4 − 10 10 10 10 3 (1) 1 (1) 15 = − x2 + x3 + 8 8 8 =
maka kita akan memperoleh nilai-nilai x (2) = (1, 0473; 1, 7159; −0, 8052; 0, 8852)t. Setelah kita memperoleh nilai-nilai x (2) , perhitungan tersebut diulangi kembali dengan nilai k = 3. Lalu nilai-nilai x(2) = (1, 0473; 1, 7159; −0, 8052; 0, 8852)t dimasukan ke ruas kanan untuk mendapatkan x(3) , (3)
x1
(3)
x2
(3)
x3
(3)
x4
1 (2) 2 (2) 6 x2 − x3 + 10 10 10 1 (2) 1 (2) 3 (2) 25 x1 + x3 − x4 + = 11 11 11 11 2 (2) 1 (2) 1 (2) 11 = − x1 + x2 + x4 − 10 10 10 10 3 (2) 1 (2) 15 = − x2 + x3 + 8 8 8 =
maka kita akan memperoleh nilai-nilai x (3) = (0, 9326; 2, 0530; −1, 0493; 1, 1309)t. Lalu proses perhitungan diulangi lagi dengan k = 4. Begitu seterusnya proses ini diulangulang lagi untuk nilai-nilai k berikutnya. Proses yang berulang ini disebut iterasi. Sampai dengan x(3) di atas, kita sudah melakukan tiga kali proses iterasi. Lantas sampai kapankah 4
k (k)
x1
(k) x2 (k) x3 (k) x4
0
1
2
3
4
...
9
10
0,0000
0,6000
1,0473
0,9326
1,0152
...
0,9997
1,0001
0,0000
2,2727
1,7159
2,0530
1,9537
...
2,0004
1,9998
0,0000 -1,1000 -0,8052 -1,0493 -0,9681
...
-1,0004 -0,9998
0,0000
...
1,0006
1,8852
0,8852
1,1309
0,9739
0,9998
proses iterasi ini terus berlanjut? Jawabnya adalah sampai x (baru) mendekati solusi yang sesungguhnya, yaitu x = (1; 2; −1; 1)t Dengan kata lain, proses iterasi harus di-stop atau dihentikan bila x (baru) sudah mendekati solusi. Lalu kriteria apa yang digunakan sehingga suatu hasil iterasi bisa dikatakan paling dekat dengan solusi yang sebenarnya? OK, simpan dulu pertanyaan ini, marilah kita amati hasil seluruh iterasi dari iterasi yang pertama hingga iterasi yang ke sepuluh. Tabel di atas ini menampilkan hasil perhitungan hingga iterasi yang ke sepuluh. Kita bisa saksikan bahwa hasil iterasi ke-1, x(1) = (0, 6000; 2, 2727; −1, 1000; 1, 8852) adalah hasil yang paling tidak mendekati solusi x = (1; 2; −1; 1) t. Dibandingkan dengan hasil iterasi ke-2, jelas terlihat bahwa hasil iterasi ke-2 lebih mendekati solusi. Kalau terus diurutkan, maka hasil iterasi ke-10 merupakan hasil yang paling dekat dengan solusi. Dengan memanfaatkan perhitungan norm, secara kuantitatif dapat disimpulkan bahwa iterasi yang ke-10 adalah yang paling dekat dengan solusi. Pada tabel dibawah ini, saya menggunakan norm 2 , sedangkan hasil perhitungan norm, saya beri nama epsilon, . Jadi semakin kecil nilai epsilon, , hasil iterasinya semakin dekat dengan solusi. Kembali ke pertanyaan penting yang tadi yaitu kriteria apa yang digunakan sehingga suatu hasil iterasi bisa dikatakan paling dekat dengan solusi yang sebenarnya? Jawabnya adalah besar kecilnya nilai . Artinya kalau nilai ditentukan sebesar 0,2 , maka iterasi akan berhenti pada iterasi yang ke-4. Atau kalau nilai ditentukan sebesar 0,001 , maka proses iterasi akan berhenti pada iterasi yang ke-10. Kesimpulannya, semakin kecil nilai , semakin panjang proses iterasinya, namun hasil akhirnya semakin dekat dengan solusi sebenarnya. Jadi nilai berperan penting untuk menghentikan proses iterasi. Dalam hal ini, disebut sebagai stopping-criteria. norm 2
(2) x − x(1) 2
(3) x − x(2) 2
(4) x − x(3) 2
...
(10) x − x(9) 2
1,2557
0,4967
0,2189
...
0,0012
5
Metode yang baru saja kita bahas ini disebut metode Iterasi Jacobi. Metode ini bertujuan mencari nilai-nilai pengganti variabel-variabel x dengan perumusan n (k−1) x −a + bi ij j j=1 (k) xi = aii
(7)
dimana i=1,2,3,...,n. Algoritma Iterasi Jacobi • Langkah 1: Tentukan k=1 • Langkah 2: Ketika (k ≤ N) lakukan Langkah 3-6 – Langkah 3: Untuk i=1,...,n, hitunglah − nj=1 (aij XOj ) + bi xi = aii – Langkah 4: Jika x − XO < , maka keluarkan OUTPUT (x1 , ..., xn ) lalu STOP – Langkah 5: Tentukan k=k+1 – Langkah 6: Untuk i=1,...n, tentukan XO i = xi • Langkah 7: OUTPUT (’Iterasi maksimum telah terlampaui’) lalu STOP
Program dalam Fortran IMPLICIT NONE DIMENSION A(10,10),B(10),X(10),XO(10) REAL A,B,X,XO,EPS,NORM,S INTEGER N,I,J,K,ITMAX WRITE(*,*) ’==> ITERASI JACOBI UNTUK SISTEM LINEAR <==’ WRITE(*,*) WRITE (*,’(1X,A)’) ’JUMLAH PERSAMAAN ? ’ READ (*,*) N WRITE (*,*) ’MASUKAN ELEMEN-ELEMEN MATRIK A DAN VEKTOR B’ DO 52 I = 1,N DO 62 J = 1,N 6
WRITE (*,’(1X,A,I2,A,I2,A)’) ’A(’,I,’,’,J,’) = ’ READ (*,*) A(I,J) 62
CONTINUE WRITE (*,’(1X,A,I2,A)’) ’B(’,I,’) ? ’ READ (*,*) B(I) WRITE (*,*)
52
CONTINUE WRITE (*,’(1X,A)’) ’JUMLAH ITERASI MAKSIMUM ? ’ READ (*,*) ITMAX WRITE (*,’(1X,A)’) ’NILAI EPSILON ATAU TOLERANSI ? ’ READ (*,*) EPS WRITE (*,*) ’MASUKAN NILAI AWAL UNTUK XO’ DO 72 I = 1,N WRITE (*,’(1X,A,I2,A)’) ’XO(’,I,’) ? ’ READ (*,*) XO(I)
72
CONTINUE WRITE (*,*)
C
MENAMPILKAN MATRIK A WRITE (*,’(1X,A)’) ’MATRIK A:’ DO 110 I = 1,N
110
WRITE (*,6) (A(I,J),J=1,N) CONTINUE WRITE (*,*)
C
MENAMPILKAN VEKTOR B WRITE (*,’(1X,A)’) ’VEKTOR B:’ DO 111 I = 1,N WRITE (*,6) B(I)
111
CONTINUE WRITE (*,*)
C
LANGKAH 1 K = 1
C
LANGKAH 2
100
IF(K.GT.ITMAX) GOTO 200
C
LANGKAH 3 7
NORM = 0.0 DO 10 I = 1,N S = 0.0 DO 20 J=1,N 20
S = S-A(I,J)*XO(J) CONTINUE S = (S+B(I))/A(I,I) IF (ABS(S).GT.NORM) NORM=ABS(S) X(I) = XO(I)+S
10
CONTINUE WRITE(*,’(1X,A,I3)’) ’ITERASI KE-’, K WRITE(*,’(1X,A,F14.8)’) ’NORM = ’, NORM WRITE(*,’(1X,A,I3,A,F14.8)’) (’X(’,I,’) = ’, X(I),I=1,N) WRITE(*,*)
C
LANGKAH 4 IF(NORM.LE.EPS) THEN WRITE(*,7) K,NORM GOTO 400 END IF
C
LANGKAH 5 K = K+1
C
LANGKAH 6 DO 30 I=1,N XO(I) = X(I)
30
CONTINUE GOTO 100
C
LANGKAH 7
200
CONTINUE WRITE(*,9)
400
STOP
5
FORMAT(1X,I3)
6
FORMAT(1X,(6(1X,F14.8)))
7
FORMAT(1X,’KONVERGEN PADA ITERASI YANG KE- ’,I3, 8
9
*’ , NORM= ’,F14.8) FORMAT(1X,’MELEBIHI BATAS MAKSIMUM ITERASI’) END Demikianlah catatan singkat dari saya tentang metode Iterasi Jacobi untuk menyele-
saikan problem sistem persamaan linear. Saya cukupkan sementara sampai disini. Insya Allah akan saya sambung lagi dilain waktu. Kalau ada yang mau didiskusikan, silakan hubungi saya melalui email:
[email protected].
9
