1
BAB X MATRIK DAN SISTEM PERSAMAAN LINIER SIMULTAN
Pembahasan berikut ini akan meninjau salah satu implementasi operasi matrik untuk menyelesaikan sistem persamaan linier simultan. Selain menggunakan invers matrik, terdapat beberapa metoda yang dapat digunakan untuk menyelesaikan sistem persamaan linier dengan memanfaatkan perhitungan matrik, yaitu eliminasi Gauss, eliminasi Gauss-Jordan, Jacobi, dan Gauss-Seidel.
10.1. Metoda Eliminasi Gauss Untuk memahami metoda eliminasi Gauss dalam menyelesaikan sistem persamaan linier simultan akan dijelaskan melalui contoh berikut ini. Jika diketahui dua buah persamaan dengan dua variabel yang tidak diketahui, yaitu sebagai berikut: 2X + 3Y = 7 3X + 5Y = 11
(1) (2)
Harga variabel X dan Y pada kedua persamaan di atas dapat dihitung atau ditemukan dengan cara sebagai berikut. Mula-mula kita harus mengeliminasi salah satu variabel dalam persamaan, misal X. Untuk mengeliminasi variabel X dari persamaan (2) dapat dilakukan dengan cara membagi persamaan (1) dengan 2, sehingga persamaan (1) akan menjadi sebagai berikut: 2X + 3Y = 7 ……………………… (1) (2X + 3Y = 7) / 2 X + 3/2Y = 7/2 ……………………. (3) Hasil yang diperoleh pada persamaan (3) tersebut nantinya akan digunakan untuk mengurangi pada persamaan (2). Karena koefisien variabel X dalam (2) adalah 2, maka sebelum digunakan untuk mengurangi, maka persamaan (3) perlu dikalikan 3 terlebih dahulu. Hasil yang akan diperoleh adalah sebagai berikut: X + 3/2Y = 7/2 ……………………. (3)
2
3(X + 3/2Y = 7/2) 3X + 9/2Y = 21/2 …………
(4)
Hasil pada persamaan (4) kemudian akan digunakan untuk mengurangi pada persamaan (2), sehingga akan diperoleh hasil sebagai berikut:
3X + 5Y = 7/2 3X + 9/2Y = 21/2 ½Y = ½
………………… (2) ………………. (4) ………………. (5)
Untuk menentukan harga Y, maka persamaan (5) harus dikalikan dengan 2, sehingga akan menjadi sebagai berikut: ½Y = ½ ………………………….. (5) 2(½Y = ½) Y = 1……………………… (6) Dari perhitungan di atas, maka harga variabel Y adalah 1. Selanjutnya untuk menghitung harga variabel X, maka subsitusikan harga Y tersebut ke dalam persamaan (1), sehingga akan diperoleh hasil sebagai berikut: 2X + 3Y = 7 ……………………….… (1) 2X + 3x1 = 7 2X + 3 = 7 2X = 4 X = 2 ……………………… (7) Berdasarkan hasil-hasil perhitungan yang ditujukkan pada persamaan (6) dan (7), maka harga penyelesaian pada sistem persamaan linier di atas adalah Y=1, dan X=2. Sekarang kita akan meninjau teknik eliminasi Gauss untuk menyelesaikan sistem persamaan linier simultan. Secara umum sistem persamaan linier dapat dinotasikan sebagai berikut ini: A11 X1 + A12 X2 + ….. + A1N XN = B1 A21 X1 + A22 X2 + ….. + A2N XN = B2 A31 X1 + A32 X2 + ….. + A3N XN = B3 . . . . . . AN1 X1 + AN2 X2 + ….. + ANN XN = BN
3
Sistem perasamaan tersebut dapat diubah ke dalam persamaan notasi matrik sebagai berikut: AX = B …………………………….… (8) Dimana A, X, dan B merupakan matrik yang masing-masing mempunyai entri sebagai berikut: ANXN = A11 A21 A31 . . AN1
A12 A22 A32 . . AN2
….. A1N ….. A2N ….. A3N . . ….. ANN
XNX1
= X1 X2 X3 . . XN
BNXN = B1 B2 B3 . . BN B
B
B
B
Notasi dalam persamaan (8), dapat dituliskan menjadi persamaan notasi matrik yang diperbesar (augmented matrik), yaitu sebagai berikut: A11 A21 A31 . . AN1
A12……A1N A22……A2N A32……A3N . . . . AN2……ANN
B1 B2 B3 . . BN
Dan selanjutnya matrik X merupakan matrik yang akan dicari dengan metoda eliminasi Gauss. Secara garis besar, penyelesaian sistem persamaan linier simultan dengan metoda eliminasi Gauss adalah terdiri dari dua tahapan, yaitu sebagai berikut: 1. Eliminasi maju, yaitu dimulai dari baris paling atas dan kemudian menurun, membagi setiap elemen baris dengan elemen diagonal yang disebut “pivot”, sehingga diperoleh harga 1 pada elemen diagonalnya. Kemudian kurangkan hasil perkalian suatu baris pada masing-masing baris dibawahnya sehingga diperoleh harga 0 pada kolom dibawah elemen pivot. 2. Subsitusi mundur, kurangkan harga hasil perkalian pada baris-baris yang lebih rendah sehingga semua elemen mempunyai harga 0 (nol) kecuali pada diagonal utama yang mempunyai harga 1 dan pada kolom paling kanan.
4
Setelah kedua tahap tersebut dilaksanakan, maka hasil penyelesaiannya dapat dilihat pada kolom paling kanan yaitu: XNX1
=
X1 X2 X3 . . XN
Untuk memperjeles proses dalam metoda eliminasi Gauss, contoh sistem persamaan di atas akan diselesaikan dengan metoda eliminasi Gauss. Sistem persamaan tersebut akan dituliskan kembali, yaitu: 2X + 3Y = 7 ……………………… (1) 3X + 5Y = 11 ……………………… (2) Sistem persamaan tersebut dapat diubah ke dalam notasi matrik sebagai berikut ini: AX = B Berdasarkan sistem persamaan tersebut, maka A, X, dan B adalah matrik-matrik yang mempunyai entri sebagai berikut: A2X2
=
2 3
3 5
B2X1 = 7 11
X2X1 = X1 X2
Dalam contoh di sini, harga N adalah 2. Selanjutnya berdasarkan notasi pada matrik yang diperbesar akan diselesaikan sesuai dengan tahapan penyelesaian dalam metoda eliminasi Gauss. Elemen bertanda kotak dimaksudkan sebagai elemen pivot pada setiap langkah perhitungan. Untuk membedakan operasi arimatika dalam perhitungan, maka operasi perkalian akan dinotasikan dengan simbol khusus yaitu “%”. Sedangkan nomor baris dalam matrik yang diperbesar akan dinotasikan dengan simbol “R”. sebagai contoh, simbol R1 digunakan untuk menyatakan baris ke-1, R2 untuk baris ke-2, R3 untuk menyatakan baris ke-3, dan seterusnya. Selain itu, untuk menyatakan kolom tertentu dalam matrik akan digunakan simbol C.
5
Berdasarkan notasi matrik diperbesar di atas, maka proses perhitungan untuk penyelesaian sistem persamaan di atas dapat dituliskan sebagai berikut ini: 1. Langkah ke-1, baris ke-1 dibagi dengan 2 R1%2↔
1 3
3
/2 5
7
/2 11
2. Langkah ke-2, baris ke-2 dikurangi dengan 3 kali baris ke-1 R2-3 x R1 ↔ 1 0
3
/2 1 /2
7
/2 ½
3. Langkah ke-3, baris ke-2 dibagi dengan ½ 3 7 /2 /2 1 0 1 1 4. Langkah ke-4, baris ke-1 dikurangi dengan 3/2 kali baris ke-2
R2%½ ↔
R-3/2 x R2 ↔ 1 0
0 1
2 1
Pada akhir langkah ke-4 semua elemen matrik telah mempunyai harga 0 (nol) kecuali pada diagonal utama yang mempunyai harga 1 dan pada kolom paling kanan, seningga proses telah selesai. Hasil penyelesaian sistem persamaan linier adalah ditunjukan pada kolom paling kanan, yaitu X=2 dan Y=1. Perhitungan pada langkah ke-1 hingga langkah ke-3 adalah memperlihatkan tahap eliminasi maju. Sedangkan langkah ke-4 adalah subsitusi mundur. Berdasarkan proses perhitungan di atas, selanjutnya dapat dikembangkan solusi dalam bentuk algoritma prosedurnya. Untuk menuliskan algoritma prosedur yang dimaksud, di sini akan digunakan dua variabel bantu yaitu N dan M. Variabel N adalah menyatakan indeks terbesar pada elemen matrik A. Sedangkan variabel M menyatakan indeks terbesar pada elemen matrik yang diperbesar yang mempunyai harga M=N+1. Selain itu, variabel I, J, dan K digunakan untuk menyatakan subskrip pada larik dan sekaligus berfungsi sebagai variabel pencacah untuk kendali pada proses perulangan. Dengan asumsi bahwa semua entri pada matrik yang diperbesar telah diketahui, maka algoritma prosedur penyelesaian sistem persamaan linier simultan dengan metoda eliminasi Gauss
6
adalah dituliskan di bawah ini. Sedangkan Gambar 10.1 adalah menunjukan flowchart prosedurnya. Algoritma prosedur yang dituliskan di sini akan memberikan hasil sebagai berikut: 1 0 0
0…… 0 1…… 0 . . 0…… 1
X1 X2 . . XN
Dalam matrik hasil tersebut harga-harga penyelesaian yang dicari untuk sistem persamaan linier simultan adalah ditunjukkan pada kolom paling kanan yaitu dalam variabel X1, X2, X3, dan seterusnya hingga XN dimana N adalah sesuai dengan banyaknya persamaan. Dari matrik yang diperbesar dengan entri A[I,J]. N menyatakan indeks terbesar pada matrik A dan M=N+1. A[K,M] dan A[K,I] adalah harga-harga penyelesaian untuk sistem persamaan linier simultan. 1. Mulai 2. Proses berulang langkah-3 s/d langkah-4 untuk eliminasi maju FOR I = 1 TO N 3. Proses berulang untuk membagi setiap elemen dalam baris dengan pivot FOR J = I TO M Hitung A[I,J] = A[I,J] / A[I,I] 4. Proses berulang untuk mengurangkan hasil perkalian suatu baris pada setiap baris di bawahnya FOR K = I + 1 TO N Hitung A[K,J] = A[K,J] - A[K,J] x A[I,J] 5. Proses berulang untuk subsitusi mundur FOR I = N DOWN TO 2 Hitung secara berulang FOR K = 1 TO I-1 A[K,M] = A[K,M] - A[K,I] x A[I,M]
7
A[K,I] = 0 6. Cetak hasil 7. Selesai Beberapa variasi dapat dilakukan pada metoda eliminasi Gauss. Setiap entri pada baris dapat dibagi dengan elemen pivot setelah tahap eliminasi maju, selama proses eliminasi maju berlangsung, atau bahkan setelah tahap subsitusi mundur selesai dijalankan. Variasi lain yang penting adalah dengan melakukan perputaran atau “pivoting”. Kesalahan yang terjadi akibat pembulatan angka, dapat diminimalkan dengan saling menukar antar baris dan kolom. Jika pertukaran dilakukan antar baris dan kolom sekaligus, maka disebut eliminasi dengan perputaran penuh atau “ full pivoting”. Sedangkan jika pertukaran hanya dilakukan antar baris saja maka disebut sebagai eliminasi dengan perputaran sebagian atau “partial pivoting”. Proses pertukaran antar baris akan mengakibatkan suatu perubahan yang sederhana pada bentuk persamaan. Di lain pihak, suatu pertukaran antar kolom adalah sama dengan mengubah bentuk persamaan dalam sebagian kecil variabel-variabelnya. Karenanya, kita perlu menyimpan jejak kolom-kolom yang saling dipertukarkan tersebut untuk mengetahui pada bagian mana harga-harga variabel X1, X2, ….. XN yang akan muncul pada kolom paling kanan. Jika pertukaran dilakukan antara kolom ke-I dan kolom ke-J, maka hasil X[I] dan X[J] juga harus saling ditukarkan tempatnya. Simbol ↔ digunakan untuk menyatakan pertukaran antar baris atau kolom. Sebagai contoh, jika baris ke-1 akan ditukarkan dengan baris ke-3 maka akan dituliskan dengan notasi sebagai berikut: R1 ↔ R3 Berikut ini akan diberikan contoh menyelesaikan sistem persamaan linier dengan menggunakan metoda eliminasi Gauss tanpa perputaran, dengan perputaran sebagian, dan dengan perputaran penuh. Sistem persamaan linier simultan yang akan diselesaikan adalah dari tiga persamaan, yaitu sebagai berikut ini: X1 + 3X2 - 2X3
=7
8
4X1 - X2 - 3X3 -5X1 + 2X2 + 3X3 =7
= 10
Proses penyelesaian pada masing-masing variasi metoda eliminasi Gauss tersebut adalah dijelaskan seperti berikut ini.
1. Eliminasi Gauss tanpa perputaran Matrik yang diperbesar dalam sistem persamaan tersebut adalah sebagai berikut: 1 4 -5
3 -1 2
-2 3 3
7 10 7
Langkah ke-1: R2 – 4R1 R3 + 5R1
⇔
1 3 -2 7 0 0 11 -18
Langkah ke-2: R2% -13
⇔
1 3 -2 7 0 1 -0.8462 1.3846 0 17 14 42
Langkah k3-3: R3 – 17R2
⇔
1 3 -2 7 0 1 -0.8462 -1.3846 0 0 7.3854 -18.4618
Langkah ke-4: R3%7.3854
⇔
1 3 0 1 0 0
-2 7 -0.8462 1.3846 1 2.4998
Langkah ke-5: R1+2R3 ⇔ R2+0.8462Xr3
1 3 0 1 0 0
-2 0 1
11.9996 3.4999 2.4998
⇔
1 0 0 1 0 0
0 0 1
11.4999 3.4999 2.4998
Langkah ke-6: R1-3R2
Pada akhir langkah ke-6 semua elemen matrik telah mempunyai harga 0 (nol) kecuali pada diagonal utama yang mempunyai harga 1 dan pada kolom paling kanan, sehingga proses telah selesai. Hasil penyelesaian sistem persamaan linier adalah ditunjukkan pada kolom paling kanan, yaitu X1 = 1.4999, X2 = 3.4999, dan X3 = 2.4998.
9
2. Eliminasi Gauss dengan perputaran sebagian Matrik yang diperbesar dalam sistem persaman tersebut adalah sebagai berikut: 1 4 -5
3 -1 2
-2 3 3
7 10 7
Langkah ke-1: R1 – R3⇔
-5 2
Langkah ke-2: R1%-5 ⇔
1
Langkah ke-3: R2 - 4R1⇔
Langkah ke-4: R2↔R3 ⇔
3 7 4 -1 3 10 1 3 -2 7
-0.4 -0.6 4 -1 1 3
1
-1.4 3 -2
-0.4 -0.6 0 0.6 0 3.4
1
-0.4 0 0
10 7
-1.4 5.4 -1.4
8.4 8.4
-1.4 -1.4 5.4
8.4 15.6
-0.6 1 0.6
Langkah ke-5:
R2%3.4
⇔
1 0 0
-0.4 1 0.6
Langkah ke-6:
R3-0.6R2
⇔
1 0 0
-0.4 1 0
Langkah ke-7:
R3%5.6471 ⇔
1 0 0
-0.4 -0.6 -1.4 1 -0.4118 2.4706 0 1 2.5000
Langkah ke-8:
R10.6R3 ⇔ 1 R2+0.4118R3 0 0
Langkah ke-8:
R1+0.4R2
⇔
1 0 0
-0.6 -1.4 -0.4118 2.4706 5.4 15.6 -0.6 -0.4118 5.6471
-0.4 0 1 0 0 1
0.1000 3.5001 2.5000
0 1 0
1.5000 3.5001 2.5000
0 0 1
-1.4 2.4706 14.1176
Pada akhir langkah ke-6 semua elemen matrik telah mempunyai harga 0 (nol) kecuali pada diagonal uatama yang mempunyai harga 1 dan pada kolom paling kanan, sehingga proses telah selesai. Hasil penyelesaian sistem persamaan linier adalah ditunjukkan pada kolom paling kanan, yaitu X1 = 1.5000, X2 = 3.5001, dan X3 = 2.5000.
10
3. Eliminasi Gauss dengan Perputaran penuh Matrik yang diperbesar dalam sistem persamaan tersebut adalah sebagai berikut: 1 4 -5
3 -1 2
-2 3 3
7 10 7
Langkah ke-1: R1↔ R3
⇔
-5 2 3 7 4 -1 3 10 1 3 -2 7
Langkah ke-2: R1%-5
⇔
1 4 1
-0.4 -1 3
-0.6 3 2
Langkah ke-3: R2 – 4R1 R3-R1
⇔
1 0 0
-0.4 0.6 3.4
-0.6 5.4 -1.4
Langkah ke-4: C2↔C3
⇔
1 0 0
-0.6 5.4 1.4
Langkah ke-5:
R2%5.4
⇔
1 0 0
-0.6 1 -1.4
-0.4 -1.4 -0.1111 2.8889 3.4 8.4
Langkah ke-6:
R3+1.4R2
⇔
1 0 0
-0.6 1 0
-0.4 -1.4 -0.1111 2.8889 3.5555 12.4445
Langkah ke-7:
R3%3.5555
⇔
1 0 0
-0.6 1 0
-0.4 -1.4 -0.1111 2.88889 1 3.5001
Langkah ke-8:
R1+0.4R3 R2-0.1111R3
⇔
1 0 0
-0.6 1 0
0 0 1
0 2.5000 3.5001
Langkah ke-9:
R1+0.4R3 R1+0.6xR2
⇔
1 0 0
0 1 0
0 0 1
1.5000 2.5000 3.5001
-0.4 0.6 3.4
-1.4 10 7 -1.4 15.6 8.4 -1.4 15.6 8.4
Perhatikan, pada langkah ke-4 dalam perhitungan di atas elemen-elemen pada kolom ke-2 ditukarkan dengan elemen-elemen pada kolom ke-3. hal ini akan
11
mengakibatkan pertukaran lokasi pada harga X2 dan X3. Jelasnya, pertukaran tersebut akan mengakibatkan pertukaran pada harga X2 dan X3, dimana X2 akan muncul pada baris ke-3 dan X3 pada baris ke-2. Oleh karenanya hasil akhir penyelesaian yang diperoleh pada masing-masing variabelnya juga menjadi berubah, yaitu X1 = 1.5000, X2 = 3.5001, X3 = 2.500. Jika dihitung dengan cara subsitusi, maka hasil penyelesaianyang sebenarnya dari sistem persamaan linier simultan di atas adalah X1 = 1.5, X2 = 3.5, dan X3 = 2.5. Sebagaimana dapat kita lihat pada hasil perhitungan dengan tiga variasi metoda eliminasi Gauss di atas, setiap metoda telah memberikan hasil yang berbeda. Oleh karena itu kita akan dapat membandingkan tingkat akurasi setiap metoda tersebut berdasarkan hasil akhir penyelesaian yang diperoleh. Selisih atau kesalahan absolut untuk metoda eliminasi Gauss tanpa perputaran adalah 0.0004, dengan perputaran sebaian adalah 0.0001 dan dengan perputaran penuh adalah 0.0001. Pada umumnya, penerapan operasi perputaran dalam metoda eliminasi Gauss akan dapat mengurangi tingkat kesalahan pada hasil perhitungannya.
Dengan
kalimat
yang
lain,
operasi
perputaran
akan
menghasilkan penyelesaian yang lebih akurat. Flowchart prosedur penyelesaian persamaan linier simultan dengan metode eliminasi Gauss ditunjukkan oleh Gambar 10.1.
12
Mulai Baca matrik yg diperbesar,N,M FOR I = 1 TO N FOR J = 1 TO N A[I,J] = A[I,J]/A[I,I] NEXT J FOR K = 1 TO N FOR J = 1 TO M A[k,J] = A[k,J]xA[I,J] NEXT J NEXT K NEXT I FOR I = N DOWN TO 2 FOR K = I TO I-1 A[K,M]=A[K,M] – A[K,I] x A[I,M], A[K,J] = 0 NEXT K NEXT I Cetak hasil Selesai
Gambar 10.1: Flowchart prosedur penyelesaian sistem persamaan linier simultan dengan metoda eliminasi Gauss
13
10.2. Metoda Eliminasi Gauss-Jordan Metoda eliminasi Gauss-Jordan merupakan teknik lain untuk menyelesaikan sistem persamaan linier simultan. Proses penyelesaian dalam metoda ini hampir sama dengan metoda eliminasi Gauss. Perbedaannya adalah bahwa dalam metoda eliminasi Gauss-Jordan elemen-elemen di atas pivot dieliminasi pada saat yang bersamaan sebagaimana dilakukan pada elemen-elemen di bawahnya. Dengan demikian, tahapan subsitusi mundur tidak diperlukan lagi dalam etoda eliminasi Gauss-Jordan. Karenanya langkah penyelesaiannya akan lebih singkat, jika dibandingkan dengan penyelesaian dalam metoda Gauss. Sebagaimana dalam eliminasi Gauss, operasi perputaran antar baris dan antar kolom atau perputaran antar kolom saja juga dapat diterapkan dalam metoda ini. Sekalipun demikian, metoda ini relatif kurang efisien dibandingkan dengan metoda eliminasi Gauss. Hal ini disebabkan adanya kebutuhan operasi-operasi arimatika yang lebih banyak dalam langkah-langkah penyelesaiannya. Dengan asumsi bahwa semua elemen pada matrik yang diperbesar telah diketahui, maka algoritma prosedur penyelesaian sistem persamaan linier simultan dengan metoda eliminasi Gauss-Jordan dapat dituliskan sebagai berikut: Dari matrik yang diperbesar dengan entri A[I,J]. N menyatakan indeks terbesar pada matrik A dan M = N + 1. A[K,J] adalah harga-harga penyelesaian untuk sistem persamaan linier simultan. 1. Mulai 2. Proses berulang langkah-3 s/d langkah-4 FOR I = 1 TO N 3. Proses berulang untuk membagi masing-masing elemen dalam baris dengan pivot FOR J = I TO M Hitung A[I,J] = A[I,J]/A[I,I] 4. Proses berulang untuk mengurangkan hasil perkalian suatu baris pada setiap baris yang lain FOR K = 1 TO N
14
IF K <> I Hitung FOR J = I TO M A[K,J] = A[K,J] – A[K,I] x A[I,J] 5. Cetak hasil 6. Selesai Algoritma prosedur eliminasi Gauss-Jordan di atas akan memberikan hasil yang sama dengan algoritma prosedur eliminasi Gauss tanpa perputaran. Untuk lebih jelasnya berikut ini akan diberikan contoh penerapannya. Jika sistem persamaan yang akan diselesaikan adalah sama dengan contoh sebelumnya, maka di bawah ini akan ditampilkan langkah-langkah penyelesaian dengan menggunakkan metoda eliminasi Gauss-Jordan. Pada bagian yang lebih dahulu adalah penyelesaian tanpa perputaran, sedangkan berikutnya merupakan variasi dengan perputaran sebagian. Selanjutnya, anda dipersilakan mencobanya jika menggunakan variasi penuh.
1. Eliminasi Gauss-Jordan tanpa perputaran Matrik yang diperbesar dalam sistem persamaan tersebut adalah sebagai berikut: 1 4 -5
3 -1 2
-2 3 3
7 10 7
Langkah ke-1:
R3+R1
⇔
1 0 0
3 -13 17
-2 11 -7
Langkah ke-2:
R2%-13
⇔
1 0 0
3 1 17
-2 -0.8462 -7
7 1.3846 42
Langkah ke-3:
R1-3R2 R3-17R2
⇔
1 0 0
0 1 0
0.5386 -462 1
2.8462 1.3846 2.4998
Langkah ke-4:
R3%7.3845 ⇔
1 0 0
0 1 0
0.5386 -462 1
2.8462 1.38446 2.4998
7 -18 42
15
Langkah ke-5:
⇔
R1-0.5386R3 R2+0.8462R3
1 0 0
0 1 0
0 0 1
1.4998 3.4999 2.4998
Penyelesaian pada masing-masing variabel untuk sistem persamaan di atas dengan metoda eliminasi Gauss tanpa perputaran adalah X1 = 1.4999, X2 = 2.4998, dan X3 = 2.4998.
2. Eliminasi Gauss-Jordan dengan perputaran sebagian Matrik yang diperbesar dalam sistem persamaan terbut adalah sebagai berikut: 1 4 -5
3 -1 2
-2 3 3
7 10 7
Langkah ke-1:
R3↔R3
⇔
-5 4 1
2 -1 3
Langkah ke-2:
R1%-5
⇔
1 4 1
-0.4 -0.6 -1 3 3 -2
-1.4 10 7
Langkah ke-3:
R2-4R1 R2-4R1 R3-1R1
⇔
1 0 0
-0.4 -0.6 0.6 5.4 3.4 -1.4
-1.4 15.6 8.4
Langkah ke-4:
R2↔R3
⇔
Langkah ke-5:
R2%3.4
⇔
1 0 0 1 0 0
-0.4 3.4 0.6 -0.4 1 0.6
-0.6 -1.4 5.4 -0.6 -0.4118 5.4
-1.4 8.4 15.6 -1.4 2.4706 15.6
Langkah ke-6:
R1+0.4R2 R3-0.6xR2
⇔
1 0 0
0.6 1 0
-0.7647 -0.4118 5.6471
-0.4118 2.4706 14.1176
Langkah ke-7:
R2%5.6471
⇔
1 0 0
0 1 0
-0.7647 -0.4118 1
-0.4118 2.4706 2.5
3 3 -2
7 10 7
16
Langkah ke-8: R1+07647R3 ⇔ 1 R2+0.4118xR3 0 1 0 0
0 0 1
0
1.5 3.5001 2.5
Hasil penyelesaian yang diperoleh pada masing-masing variabel dengan menggunakan metoda eliminasi Gauss dengan perputaran sebagian adalah X1 = 1, X2 = 3.5001, dan X3 = 2.5. Dari hasil tersebut dapat disimpulkan, bahwa Penggunaan operasi perputaran akan memberikan hasil yang lebih akurat pada penyelesaian sistem persamaan. Sebagai catatan tambahan, penting diperhatikan bahwa jika salah satu elemen diagonal matrik berharga 0 (nol), algoritma eliminasi Gauss dan eliminasi Gaussjordan akan mengalami kegagalan, yaitu sejak langkah ke-2 dimana elemen pivot membagi elemen-elemen baris. Untuk mengatasi hal ini dapat dilakukan dengan cara menambahkan satu langkah pengecekkan harga 0 (nol) pada awal langkah ke-2. jika ditemeukan 0 (nol) pada elemen diagonal, kemudian dicek pada baris berikutnya untuk kolom yang sama. Penetapan pivot pada baris asli adalah dilakukan dengan menggunakan elemen pada kolom yang lain. Dan proses selanjutnya tetap mengikuti prosedur sebagaimana algoritma yang telah ditulis di atas. Flowchart prosedur penyelesaian sistem persamaan linier simultan dengan metoda eliminasi Gauss-Jordan adalah ditunjukkan pada Gambar 10.2.
17
Mulai Baca matrik yg diperbesar FOR I = 1 TO N FOR J = I TO M A[I,J] = A[I,J]/A[I,I] NEXT J FOR K = 1 TO M YA
K<>I
TIDAK
FOR J = I TO M A[K,J] = A[K,J]-A[K,J]Xa[I,j] NEXT J NEXT K NEXT I Cetak hasil Selesai
Gambar 10.2: Flowchart prosedur penyelesaian persamaan linier simultan dengan metoda eliminasi Gauss-Jordan
10.3. Metoda Iterasi Jacobi metoda Jacobi sangat menguntungkan untuk diterapkan pada penyelesaian sistem persamaan linier simultan jika matrik koefisiennya memiliki banyak elemen 0 (n0l), atau lebih dikenal sebagai matrik jarang (sparse matrik). Metoda
18
ini melaksanakan proses pnyelesaian sistem persamaan secara iteratif, dan umumnya implementasi ke dalam program aplikasi komputer dapat dilakukan dengan mundah. Proses dalam metoda Jacobi dapat dijelaskan sebagai berikut. Mula-mula pada langkah pertama adalah menyelesaikan salah satu variabel pada masing-masing persamaan. Sebagai contoh, jika diketahui sistem persamaan dengan bentuk sebagai berikut: 5X1 + X2 + 3X3 = 10 X1 + X2 + 5X3 = 8 2X1 +4X2+ X3 = 11
(1) (2) (3)
Bentuk persamaan-persamaan tersebut dapat ditranformasikan ke dalam bentuk sebagai berikut ini: X1 = 2.00 - 0.20 X2 - 0.60 X3 X2 = 2.75 - 0.5 X1 - 0.25 X3 X3 = 1.60 - 0.20 X1 - 0.20 X2
(1) (2) (3)
Kemudian kita membuat inisialisasi harga awal sembarang untuk masing-masing variabel. Dalam banyak kesempatan, sering ditetapkan harga 0 (nol) pada sema variabel, terutama jika tak ada harga awal yang lebih baik sebagai estimasi pada harga-harga sesungguhnya yang harus dicari. Selanjutnya harga-harga tersebut digunkan sebagai dasar bagi estimasi harga-harga variabel yang sebenarnya lebih baik. Prosedur ini dilakukan berulang-ulang hingga harga-harga variabel yang sebenarnya ditemukan. Harga penyelesaian akan ditemukan apabila harga kedua estimasi yang berururtan telah cukup rapat atau memiliki selisih yang sangat kecil. Kriteria yang menentukan telah ditemukanya harga penyelesaian adalah jika jumlah kuadrat selisih hasil hitungan lebih kecil dari batas yang ditentukan. Batas ketelitian yang digunakan biasanya adalah suatu harga yang sangat kecil hampir mendekati 0 (nol) yang sering disebut epsilon. Jika X
I
J
menyatakan harga estimasi variabel XJ pada iterasi ke-I, dan N adalah
menyetakan cacah variabel yang akan diselesaikan, maka kita akan memperoleh harga-harga X1, X2, …XN sebagai penyelesaian sistem persamaan jika:
19
N
∑( X J =1
I J
− X JI −1 ) 2 < EPSILON
Dengan demikian, jika N menyatakan cacah variabel yang tidak diketahui dan X1, X2, …XN adalah larik harga awal yang diinisialisasikan, dan F1, F2, …FNmenyatakan
persamaan-persamaan
yang
akan
digunakan
untuk
menyelesaikan sistem persamaan, maka algoritma di bawah ini akan menyelesaikan persamaan-persamaan berikut: X1 X2 X3 . . XN
= F1 (X2,X3…XN) = F2 (X1,X3, X4 …XN) = F3 (X1,X3, X4 …XN) . . = FN (X1,X2…XN-1)
Harga-harga pendekatan pada iterasi yang lebih akhir akan disimpan dalam vektor yang diberi nama BARU. Proses akan berhenti ketika jumlah kuadrat selisih dua hasil yang berurutan kurang dari harga EPSILON atau jika iterasi perulangan telah dilakukan 30 kali. Dengan batasan cacah iterasi sebanyak 30 tersebut, maka apabila sistem persamaan memang memiliki penyelesaian akan dapat ditemukan. Dari sistem persamaan yang telah ditransformasikan dalam bentuk: X[J] = F[J](X[1], X[2], … X[J-1], X9[J+1],… X[N]). N menyatakan indeks terbesar dalam sistem persamaan linier simultan. X[J] adalah harga-harga penyelesaian yang dicari untuk sistem persamaan linier simultan. 1. Mulai 2. Tentukan cacah maksimal iterasi untuk melaksanakan langkah-3 s/d 5 FOR I = 1 TO 30 3. Proses berulang untuk menghitung harga-harga pendekatan baru FOR J = 1 TO N Hitung BARU[J] = F[J](X[1], X[2],…X[J-1], X[J+1],…X[N]). 4. Tes konvergensi hasil perhitungan JUMLAH = 0
20
FOR J = 1 TO N Hitung JUMLAH = JUMLAH+(BARU[J]-X[J]^2 Cek konvergensi IF JUMLAH < EPSILON Jika ya, cetak hasil perhitungan (BARU[1], BARU[2],…BARU[N]) Selesai 5. Proses berulang untuk menentukan hraga-harga pendekatan baru FOR J = 1 TO N X[J] = BARU [J] 6. Cetak pesan bahwa konvergensi gagal/penyelesaian tidak ditemukan (“Penyelesaian tidak ditemukan dalam 30 iterasi, hasil hitungnya: “, X[1],X[2],…X[N]) 7. Selesai Flowchart prosedur untuk menyelesaikan sistem persamaan dengan metoda Jacobi adalah ditunjukkan pada Gambar 10.3. Selanjutnya, Tabel 10.1 adalah menunjukkan contoh proses penyelesaian sistem persaman diatas, yaitu: X1 = 2.00 - 0.20 X2 - 0.60 X3 X2 = 2.75 - 0.5 X1 - 0.25 X3 X3 = 1.60 - 0.20 X1 - 0.20 X2
(1) (2) (3)
Harga awal yang digunakan untuk X1, X2, dan X3 masing-masing adalah 0 (nol). Tingkat ketelitian yang digunakan adalah 4 (empat) digit di belakang koma atau 0,0001. Berdasarkan hasil perhitungsn dalam tabel tersebut, maka harga penyelesaian yang diperoleh adalah X1 = 1.0000, X2 = 2.0000, dan X3 = 1.0000. Penyelesaian tersebut adalah ditemukan setelah 21 iterasi perulangan.
21
Tabel 10.1: Contoh penyelesaian sistem persamaan linier simultan secara iteratif dengan metoda Jacobi Iterasi Ke 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
X1 0 2.0 0.49 1.34 0.7943 1.1275 0.9201 1.0490 0.9695 1.0188 0.9883 1.0072 0.9955 1.0027 0.9983 1.0010 0.9993 1.0004 0.9998 1.0001 0.9999 1.000
X2 0 2.75 1.35 2.3425 1.7720 2.1379 1.9144 2.0532 1.9672 2.0203 1.9874 2.0078 1.9952 2.0030 1.9982 2.0011 1.9993 2.0004 1.9997 2.0001 1.9999 2.0000
X3 0 1.6 0.65 1.232 0.8635 1.0871 0.9469 1.0331 0.9796 1.0126 0.9921 1.0048 0.9970 1.0018 0.9988 1.0007 0.9995 1.0002 0.9998 1.0001 0.9999 1.0000
22
Mulai Baca sistem persamaan, N,ε FOR I = 1 TO 30 FOR J = 1 TO N BARU[J]=F[J](X1,X[2],…X[J-1],X[J+1],…X[N] NEXT J JUMLAH = 0 FOR J = 1 TO N JUMLAH = JUMLAH+(BARU[J]-X[J])^2
YA
JUMLAH<ε
Cetak”Penyelesaian adalah:”, BARU[1],BARU[2],…BARU[N]
TIDAK
NEXT J FOR J = 1 TO N X[J]=BARU [J] NEXT J NEXT I
Cetak”Penyelesaian tidak ditemukan dalam 30 iterasi, hasil hitung:”,X[1],X[2],…X[N]
mulai
Gambar 10.3: Flowchart prosedur penyelesaian persamaan linier simultan secara iteratif dengan metoda Jacobi
10.4. Metoda Iterasi Gauss-Seidel Metoda Gauss-Seidel merupakan modifikasi dari metoda Jacobi. Dalam metoda Jacobi harga-harga pendekatan baru pada iterasi berikutnya adalah selalu didasarkan pada harga-harga pendekatan sebelumnya yang baru saja dihitung.
23
Jika harga-harga pendekatan baru tersebut dihitung secara individual, maka metoda ini disebut metoda iterasi Gauss-Seidel. Metoda ini dijamin lebih berhasil jika koefisien pada variabel dalam masing-masing persamaan mempunyai magnitude lebih besar dari pada jumlah absolut harga koefisienkoefisien lain dalam persamaan. Kondisi semacam ini lebih menguntungkan untuk menyelesaikan sistem persamaan linier simultan dalam bidang teknik. Sebagaimana dalam metoda Jacobi, jika N adalah menyatakan cacah variabel yang tidak diketahui, X1, X2,…XN adalah larik harga awal yang ditetapkan, F1, F2,…FN
menyatakan
persamaan-persamaan
yang
akan
digunkan
untuk
menyelesaikan sistem persamaan, maka algoritma prosedur metoda GaussSeidel dapat dituliskan seperti di bawah ini. Dari sistem persamaan yang telah diteransformasikan dalam bentuk: X[J]=F[J](X[1],X[2],…X[J-1],X[J+1],…X[N]) N menyatakan indeks terbesar dalam sistem persamaan linier simultan. EPSILON menyatakan batas ketelitian yang digunakan. 1. Mulai 2. Menentukan batas maksimal iterasi untuk melaksanakan langkah-3 s/d 4 Inisialisasikan JUMLAH = 0 Proses berulang FOR J = I TO J Hitung LAMA = X[J] X[J] = F[J](X[1], X[2],…X[J-1], X[J+1],…X[N]) 3. Tes konvergensi hasil perhitungkan IF JUMLAH <EPSILON Jika ya, cetak hasil (“Penyelesaianya adalah:”,X[1],X[2],…X[N] 4. Cetak pesan bahwa konvergensi gagal/penyelesaian tidak ditemukan (“Pernyelesaian tidak ditemukan dalam 30 iterasi, hasil hitungannya:”, X[1],X[2],…X[N]) 5. Selesai
24
Flowchart prosedur sistem persaman linier simultan dengan metoda GaussSeidel
adalah
ditunjukkan
pada
Gambar
10.4.
dan
sebagai
contoh
penerapannya, Tabel 10.1 adalah menunjukkan proses perhitungan pendekatan pada harga-harga penyelesaian untuk sistem persamaan berikut: X1 + -1.4000 + 0.4000 X2 + 0.6000 X3 X2 + 2.3333 + 0.3333 X1 + 0.6666 X3 X3 + 3.3333 + 1.3333 X1 + 0.3333 X3
Mulai Baca sistem persamaan,N,ε FOR I = 1 TO 30 JUMLAH = 0 FOR J = 1 TO N LAMA = X[J] X[J]=F[J](X[1],X[2],…X[J-1],X[J+1],…X[N] JUMLAH = JUMLAH+(X[J]-LAMA)^2
Ya
NEXT J JUMLAH<ε
Tidak NEXT J
Cetak penyelesaian adalah:”, X[1],X[2],..x[n] Cetak penyelesaian tidak ditemukan dalam 30 iterasi, hasil hitung X[1],X[2],..x[n]
Selesai
Gambar 10.4: Flowchart prosedur penelesaian linier simultan secara iteratif dengan metoda Gauss-Seidel
25
Tabel 10.2: Contoh menyelesaikan sistem persamaan linier simultan secara iteratif dengan metoda Gauss-Seidel X2 X3 Iterasi Ke: X1 0 0 0 0 0.85 1.75 2.0 1 0.9785 1.9675 1.14 2 0.9970 1.9956 1.0194 3 0.9996 1.9994 1.0026 4 0.9999 1.9999 1.0003 5 1.0000 2.0000 1.0000 6 Dengan menggunakan harga awal untuk X1, X2, X3 masing-masing adalah 0 (nol) dan dengan menggunakan tingkat ketelitian 4 digit desimal (=0.0001), maka sebagaimana terlihat dalam tabel tersebut, untuk menentukan harga-harga penyelesaian sistem persamaan linier simultan di atas, hanya diperlukan 6 iterasi perulangan saja. Hasil akhirnya masing-masing adalah X1 = 1.0000, X2 = 2.0000, X3 = 1.0000.
