Contoh Algoritma Metode Iterative

PENYELESAIAN  SISTEM  PERSAMAAN  LINEAR  DENGAN METODE  ITERASI

Sistem persamaan linear yang terdiri dari n persamaan dengan n variabel x1, x2, ..., xn dinyatakan dengan

Sistem (1.1) dapat diekspresikan dengan bentuk perkalian matriks. Sistem per-samaan linear dapat diselesaikan dengan metode langsung atau metode iterasi. Kedua metode tersebut mempunyai kelemahan dan keunggulan. Metode yang dipilih akan menentukan keakuratan penyelesaian sistem tersebut. Dalam kasus tertentu, yaitu sistem yang besar, metode iterasi lebih cocok digunakan. Dalam menentukan penyelesaian sistem persamaan linear, metode iterasi menggunakan algoritma secara rekursif. Algoritma tersebut dilakukan sampai diperoleh suatu nilai yang konvergen dengan toleransi yang diberikan. Ada dua metode iterasi yang sering digunakan, yaitu metode Jacobi dan metode Gauss-Seidel. Metode Jacobi dikenalkan oleh Carl Jacobi (1804-1851) dan metode Gauss-Seidel dike-nalkan oleh Johann Carl Friedrich Gauss (1777-1855) dan Philipp Ludwig von Seidel (1821-1896).

.  Penurunan Algoritma

Dalam bagian ini, metode Jacobi dan metode Gauss-Seidel diturunkan ulang. Penurunan tersebut mengacu pada May [3].

4.1. Metode Jacobi. Persamaan ke-i dalam sistem persamaan (1.1) dinyatakan sebagai


Untuk menyelesikan sistem persamaan linear dengan metode Jacobi (maupun metode Gauss-Seidel) diperlukan suatu nilai pendekatan awal yaitu x(0). Nilai x(0) biasanya tidak diketahui dan dipilih x(0) = 0.

4.2.  Metode Gauss-Seidel.  Metode Gauss-Seidel pada prinsipnya hampir sama

dengan metode Jacobi. Pada metode Jacobi, x(ik+1) dihitung dari x(1k), x(2k), ..., x(nk), tetapi nilai estimasi baru dari x(1k+1), x(2k+1), ..., x(i−k+1)1 sudah dihitung. Dalam
metode Gauss-Seidel, nilai estimasi baru tersebut digunakan dalam perhitungan. Seperti dalam metode Jacobi, penyelesaian persamaan ke-i diekspresikan menja-di persamaan (4.3). Tetapi sekarang karena nilai estimasi baru yang digunakan dalam perhitungan maka penjumlahan pada persamaan (4.3) diekspresikan kem-bali menjadi dua bagian sehingga diperoleh



Pada persamaan (4.10), tampak bahwa e(k) → 0 untuk k → ∞ jika dan hanya jika Mk → 0 untuk k → 0. Hal ini ekuivalen dengan syarat cukup dan perlu metode iterasi konvergen untuk sebarang x(0)yang dipilih adalah

5.  Penerapan Dalam Kasus

Dalam menyelesaikan sistem persamaan linear dengan metode iterasi, perhi-tungan secara manual sangat tidak efisien. Oleh karena itu, perlu dibuat pro-gram yang menggunakan Mathematica atau Microsoft Excel. Pada bagian ini, diberikan dua sistem persamaan linear yaitu sistem yang dominan secara diagonal dan yang tidak dominan secara diagonal yang diselesaikan dengan menggunakan metode Jacobi dan metode Gauss-Seidel.

Kasus 5.1. Diberikan sistem persamaan linier diambil dari [1] yaitu
 7x1 − 2x2 + x3 + 2x4 = 3
2x1 + 8x2 + 3x3 + 1x4  = −2                                                                 (5.1)
−1x1 + 5x3 + 2x4 = 5 2x2 − 1x3 + 4x4 = 4

Akan ditentukan penyelesaian sistem tersebut menggunakan metode Jacobi dan metode Gauss-Seidel. Dapat dilihat bahwa koefisien-koefisien sistem tersebut memenuhi syarat cukup (4.12) sehingga dapat dipastikan penyelesaiannya kon-vergen. Diambil x(0) = 0 sehingga diperoleh penyelesaian yang ditunjukkan dalam Tabel 1 dan Tabel 2 kolom ke-2, 3, 4, dan 5.

Dengan metode Jacobi maupun metode Gauss-seidel, diperoleh penyelesaian yang sangat akurat yaitu x1 = −0.175172, x2 = −0.533793, x3 = 0.416552, dan x4 = 1.37103. Untuk memperoleh penyelesaian yang dimaksud, metode Jaco-bi memerlukan 28 iterasi sedangkan metode Gauss-Seidel hanya memerlukan 14 iterasi. Hal ini menunjukkan bahwa metode Gauss-seidel mempunyai laju konver-gensi yang lebih cepat dari pada metode Jacobi. Kemudian dengan menerapkan persamaan (4.13) dan (4.14), diperoleh nilai rasio eror C dan estimasi batas eror seperti pada Tabel 1 dan Tabel 2 kolom ke-6 dan 7. Dengan metode Jacobi, rasio eror C yang terjadi adalah 1 sedangkan dengan metode Gauss-seidel, rasio erornya adalah 0.769231. Hal ini menunjukkan bahwa laju konvergensi metode Jacobi maupun  metode  Gauss-seidel  adalah  linear. Batas  eror  untuk  metode  Jacobi maupun metode Gauss-Seidel masing-masing adalah − 1, 4.10−5  dan 6, 67.10−6.

Kasus 5.2. Diberikan sistem persamaan linier diambil dari [2] yaitu
4x1 + 7x2 − 3x3 = 20
3x1 + x2 − x3 = 5 (5.2)
2x1 − 2x3 + 5x4 = 10

Dengan menerapkan algoritma metode Jacobi dan Gauss-Seidel, kemudian di-ambil sebarang nilai x(0) dapat diketahui bahwa penyelesaian sistem (5.2) tidak konvergen. Hal ini dikarenakan, sistem (5.2) tidak memenuhi syarat cukup (4.12). Oleh karena itu, agar diperoleh penyelesaian yang konvergen, sistem (5.2) perlu diatur kembali agar memenuhi syarat (4.12) menjadi

3x1 + x2 − x3 = 5
4x1 + 7x2 − 3x3 = 20 (5.3)
2x1 − 2x3 + 5x3 = 10.

Sistem (5.3) memenuhi syarat cukup (4.12) sehingga dapat dipastikan penyele-saiannya konvergen. Dengan menerapkan algoritma metode Jacobi dan metode Gauss-Seidel dan mengambil nilai pendekatan awal x0 = 0 diperoleh penyelesa-ian yang sangat akurat yaitu x1 = 1.50602, x2 = 3.13253, dan x3 = 2.6506. Un-tuk memperoleh penyelesaian yang dimaksud, metode Jacobi dan metode Gauss-Seidel masing-masing memerlukan 18 dan 13 iterasi. Hal ini menunjukkan bahwa metode Gauss-Seidel mempunyai laju konvergensi yang lebih cepat dari metode Jacobi. Kemudian untuk menentukan rasio eror dan estimasi batas eror, diterap-kan persamaan (4.13) dan (4.14). Rasio eror yang terjadi pada metode Jacobi dan

metode Gauss-seidel masing-masing adalah 0,6 dan 1. Hal ini menunjukkan bah-wa kedua metode tersebut mempunyai laju konvergensi linear. Sedangkan batas eror yang terjadi dengan metode Jacobi maupun metode Gauss-seidel masing-masing adalah 1, 5.10−5 dan 5.10−6.

----------------------------------------------------------------------------------------------------------------------------------

Daftar Pustaka

1. Module for jacobi and gauss-seidel iteration, http://math.fullerton.edu/mathews/n2003/ gaussseidelMod.html.
2. Sistem persamaan linear, http://ft.uns.ac.id/ts/kul−ol/numerik/numerik05−LPc.htm.
3. R. L. May, Numerical linear algebra, Royal Melbourne Institude of Technology Ltd., Mel-bourne, 1992.