Penerapan Metode Gauss, Gauss Jacobi, Gauss Seidel untuk Sistem Persamaan Linear¶

Eliminasi Gauss¶

Eliminasi gauss merupakan salah satu metode eliminasi yang ditemukan oleh Carl Friedrich Gauss yang merupakan seorang matematikawan yang berkebangsaan Jerman. Metede gauss dimanfaatkan untuk memecahkan sebuah sistem persamaan linear dengan merepresentasikan persamaan kedalam bentuk matriks. Dalam eliminasi gauss terdiri dari 2 langkah yaitu, Eliminasi Maju (forward elimination), dan Subsitusi Mundur (backword subsitution). Eliminasi maju merupakan langkah untuk menjadikan matriks $ A $ ke dalam bentuk matriks segitigas atas (upper tringular form), menggunakan Operasi baris elementer (OBE). Dan Subsitutusi mundur merupakan langkah untuk penyelesaian variabel akhir.

Sebuah sistem persamaan linear memiliki sebuah representasi, yaitu $ Ax = B $. dimana $ A $ merupakan reperesentasi koefisien dalam bentuk matriks, $ x $ sebagai representasi dari variabel dalam bentuk matriks, dan $ B $ sebagai representasi nilai dari persamaan dalam bentuk matriks.

$-3x + y = -3 \\ x + y = 5$

$Ax = B \\ \begin{bmatrix} -3 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} \begin{bmatrix} -3 \\ 5 \end{bmatrix}$

Contoh Eliminasi dengan Gauss¶

Ketika terdapat Sistem Persamaan Linear seperti berikut

$6x_1 - 2x_2 + 2x_3 + 4x_4 = 16 \\ 12x_1 -8x_2 + 6x_3 + 10x_4 = 16 \\ 3x_1 -12x_2 + 9x_3 + 3x_4 = -19 \\ -6x_1 + 6x_2 + x_3 -18x_4 = -34$

Kita dapat mengeliminasi dengan metode Gauss dengan membentuk menjadi persamaan $ Ax = B $

$\begin{bmatrix} 6 & -2 & 2 & 4 \\ 12 & -8 & 6 & 10 \\ 3 & -13 & 9 & 3 \\ -6 & 4 & 1 & -18 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} \begin{bmatrix} 16 \\ 26 \\ -19 \\ -34 \end{bmatrix}$

Selanjutnya kita dapat melakukan Eliminasi Maju (forward elimination) untuk menjadi matriks A menjadi matriks segitiga atas, dengan menjadi nilai dibawah diagonal matriks A menjadi 0. Untuk melakukan eliminasi maju kita dapat menggunakan rumus berikut.

Forward Elimination¶

$x_k = {\left.\begin{aligned} A_{ij} \leftarrow A_{ij} - \left ( {A_{ik} \over A_{kk}} \right)A_{kj} &; (k \leq j \leq n)\\ b_i \leftarrow b_i - \left ( {A_{ik} \over A_{kk}} \right)b_{k} &; \end{aligned}\right\rbrace {k+1 \leq i \leq n}}$

Untuk menjadikan 0 pada matriks A baris 2 kolom ke 1 menggunakan rumus diatas, yaitu seperti berikut.

$A_{21} = A_{21} - \left ({A_{21} \over A_{11}}\right ) \times A_{11} \\ A_{21} = 12- \left ({12 \over 6} \right) \times 6$

Eliminasi dilakukan sampai $ x_{n-1} $. Kemudian akan mengasilkan seperti berikut.

$\begin{bmatrix} 6 & -2 & 2 & 4 \\ 0 & -4 & 2 & 2 \\ 0 & -12 & 8 & 1\\ 0 & 2& 3& -14 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} \begin{bmatrix} 16 \\ -6 \\ -27\\ -18 \end{bmatrix}$

$\begin{bmatrix} 6 & -2 & 2 & 4 \\ 0 & -4 & 2 & 2 \\ 0 & 0 & 2 & -5\\ 0 & 0& 4& -13 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} \begin{bmatrix} 16 \\ -6 \\ -9\\ -21 \end{bmatrix}$

$\begin{bmatrix} 6 & -2 & 2 & 4 \\ 0 & -4 & 2 & 2 \\ 0 & 0 & 2 & -5\\ 0 & 0 & 0 & -3 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} \begin{bmatrix} 16 \\ -6 \\ -9\\ -3 \end{bmatrix}$

Setelah menyelesaikan eliminasi sampai $ x_{n-1} $, kita dapat melakukan Subsitusi Mundur (Backward Subsitution) untuk mencari nilai $ x_1 $ sampai $ x_n $ .

Backward Subsitution¶

$x_n = {b_n \over a_{nn}} \\ x_i = {b_i \sum _{j=i+1}^{n} a_{ij}x_j \over a_{ii} }$

Menggunakan rumus diatas kita dapat mencari nilai x tersebut.

$x_4 = {-3 \over -3} = 1 \\ x_3 = {-9 + 5 \over 2} = -2 \\ x_2 = {-6-2(-2)-2(1) \over -4} = 1 \\ x_1 = {16 + 2(1) - 2(-2) + 4(1) \over 6} = 3$

Setelah melakukan subsitusi mundur, maka ditemukan nilai $x_1 = 3$ , $x_2 = 1$ , $x_3 = -2$ , $x_4 = 1 $

Implementasi Eliminasi Gauss dengan Python¶

from numpy import linalg

##A = [[6, -2, 2, 4], [12, -8, 6, 10], [3, -13, 9, 3], [-6, 4, 1, -18]]
##B = [16, 26, -19, -34]
A = []
B = []

n_spl = int(input('masukkan banyak persamaan : '))
for i in range(n_spl):
    temp = []
    for j in range(n_var):
        temp.append(float(input('masukkan koefisien SPL ke-%i x%i : '%((i+1),(j+1)))))
    A.append(temp)
    B.append(float(input('masukkan hasil SPL ke-%i : '%(i+1))))


X = [0] * len(A)

def tampil_matrix(matrix):
    for i in range(len(matrix)):
        print('|', end=' ')
        for j in range(len(matrix[0])):
            print(matrix[i][j], end=' ')
        print('|')
    print()

print('Matrix A')   
tampil_matrix(A)
print('Matrix B', B)
print()

if linalg.det(A) != 0:
    #forward elimination
    for k in range(len(A)-1):
        for i in range(k+1, len(A)):
            factor = A[i][k] / A[k][k]
            for j in range(k, len(A)):
                A[i][j]= A[i][j] - factor * A[k][j]
            B[i] = B[i] - factor * B[k]

    #backward elimination
    X[len(A)-1] = B[len(A)-1] / A[len(A)-1][len(A[0])-1]
    for i in range(len(A)-1, -1, -1):
        isum = B[i]
        for j in range(i+1, len(A)):
            isum = isum - A[i][j] * X[j]
        X[i] = isum / A[i][i]
else:
    print('tidak ada peneyelesaian untuk persamaan tersebut!')

print('hasil eliminasi gauss')
print('Matrix A') 
tampil_matrix(A)
print('Matrix B', B, '\n')
for i in range(len(X)):
    print('X'+str(i+1),':', X[i])

Dari program diatas, kita menginisialisasikan matriks A, B, dan X sebagai list, dan membuat inputan yang memita banyaknya persamaan. Dari inputan tersebut kemudian dilakukan looping untuk memberikan inputan yang meminta koefisien dari tiap persamaan dan hasil dari persamaan yang kemudian akan di masukkan pada list masing -masing, sehingga list akan menjadi list 2 dimensi untuk list A.

A = []
B = []

n_spl = int(input('masukkan banyak persamaan : '))
for i in range(n_spl):
    temp = []
    for j in range(n_var):
        temp.append(float(input('masukkan koefisien SPL ke-%i x%i : '%((i+1),(j+1)))))
    A.append(temp)
    B.append(float(input('masukkan hasil SPL ke-%i : '%(i+1))))

X = [0] * len(A)

Kemudian terdapat fungsi tampil_matriks(matriks), yang nantinya digunakan untuk menampilkan list 2 dimensi, agar tampil seperti matrik yang memiliki baris dan kolom

def tampil_matrix(matrix):
    for i in range(len(matrix)):
        print('|', end=' ')
        for j in range(len(matrix[0])):
            print(matrix[i][j], end=' ')
        print('|')
    print()

Dan pada program tersebut terdapat kondisi untuk mengecek determinan matriks A. Ketika determinan matriks A tidak sama dengan 0 maka program akan melakukan proses forward elimination dan backward subsitution. untuk mencari determinan menggunakan fungsi det() yang merupakan fungsi bawaan modul numpy.

if linalg.det(A) != 0:
    #forward elimination
    #bacward subsition
else:
    else:
    print('tidak ada peneyelesaian untuk persamaan tersebut!')

Selanjutnya pada program tersebut terdapat metode forward elimination, yang melakukan komputasi dari rumus berikut $ A_{ij} \leftarrow A_{ij} - \left ( {A_{ik} \over A_{kk}} \right)A_{kj}, b_i \leftarrow b_i - \left ( {A_{ik} \over A_{kk}} \right)b_{k} $

#forward elimination
    for k in range(len(A)-1):
        for i in range(k+1, len(A)):
            factor = A[i][k] / A[k][k]
            for j in range(k, len(A)):
                A[i][j]= A[i][j] - factor * A[k][j]
            B[i] = B[i] - factor * B[k]

Dan bacward subsitution yang merupakan komputasi dari rumus $ x_n = {b_n \over a_{nn}} \\ x_i = {b_i \sum _{j=i+1}^{n} a_{ij}x_j \over a_{ii} } $

#backward elimination
    X[len(A)-1] = B[len(A)-1] / A[len(A)-1][len(A[0])-1]
    for i in range(len(A)-1, -1, -1):
        isum = B[i]
        for j in range(i+1, len(A)):
            isum = isum - A[i][j] * X[j]
        X[i] = isum / A[i][i]

Saat program tersebut dijalankan maka menghasilkan output seperti berikut.

Matrix A
| 6 -2 2 4 |
| 12 -8 6 10 |
| 3 -13 9 3 |
| -6 4 1 -18 |

Matrix B [16, 26, -19, -34]

hasil eliminasi gauss
Matrix A
| 6 -2 2 4 |
| 0.0 -4.0 2.0 2.0 |
| 0.0 0.0 2.0 -5.0 |
| 0.0 0.0 0.0 -3.0 |

Matrix B [16, -6.0, -9.0, -3.0] 

X1 : 3.0
X2 : 1.0
X3 : -2.0
X4 : 1.0

Metode Gauss Jacobi¶

Gauss Jacobi adalah metode iteratif untuk menyelesaikan sebuah sistem persamaan linear dengan ukuran n x n dengan memperbaharui nilai x yang diperoleh setiap iterasi. nilai x merupakan variabel dari persamaan yang akan dicari nilainya. Iterasi pada metode jacobi secara umum di definisikan sebagai berikut.

$\sum _ { i = 1 }^{n} x _i ^{(k+1)} = {b_i - \sum _{j=1}^{i-1} a_{ij}x_{j}^{(k)} \sum _{j=i+1}^{n} a_{ij}x_{j}^{(k)} \over a_{ii}}$

Perhitungan Gauss Jacobi¶

Tedapat sistem persamaan linear seperti berikut, kita akan mencari nilai x dengan metode Gauss Jacobi.

$10x_1 - x_2 + 2x_3 = 6 \\ -x_1 + 11x_2 - x_3 + 3x_3 = 25 \\ 2x_1 - x_2 + 10x_3 - x_4 = -11 \\ 3x_2 - x_3 + 8x_4 = 15$

Pertama kita dapat menginisialisasi nilai x, dalam contoh ini semua nilai x di inisialisasi dengan 0.

$x_1=0, x_2=0, x_3=0, x_4=0$

Kemudian kita dapat mulai menghitung nilai x menggunakan rumus iteratif metode gauss jacobi diatas yang dimulai dari iterasi pertama, atau k=1

$x_1 = {x_2 + 2x_3 + 6 \over 10}, x_1= {0 + 2(0) + 6 \over 10} = 0,6000 \\ x_2 = {-x_1 + x_3 - 3x_4 + 25 \over 11}, x_2 = {0 + 0 -3(0) + 25 \over 11} = 2,2727 \\ x_3 = {-2x_1 + x_2 + x_4 + 11 \over 10}, x_3 = {-2(0) + 0 + 0 +11 \over 10} = -1,1000 \\ x_4 = {-3x_2 + x_3 +15 \over -8}, x_4 = {-3(0) + 0 + 15 \over -8} = 1.8750$

Dengan menghitung menggunakan metode Gauss Jacobi satu iterasi, maka ditmukan nilai $x_1=0,6000$ , $x_2=2,2727$ , $x_3=1,1000$ , $x_4=1.9570$ .

Implementasi Gauss Jacobi dengan Python¶

import math
import copy
from numpy import linalg

##A = [[10, -1, 2, 0], [-1, 11, -1, 3], [2, -1, 10, -1], [0, 3, -1, 8]]
##B = [6, 25, -11, 15]

A = []
B = []

n_spl = int(input('masukkan banyak persamaan : '))
for i in range(n_spl):
    temp = []
    for j in range(n_var):
        temp.append(float(input('masukkan koefisien SPL ke-%i x%i : '%((i+1),(j+1)))))
    A.append(temp)
    B.append(float(input('masukkan hasil SPL ke-%i : '%(i+1))))

error = float(input('masukkan batas error : '))
max_iterasi = int(input('masukkan maksimal iterasi : '))

X = [0] * len(A)
X_temp = copy.copy(X)


def tampil_matrix(matrix):
    for i in range(len(matrix)):
        print('|', end=' ')
        for j in range(len(matrix[0])):
            print(matrix[i][j], end=' ')
        print('|')
    print()

print('Matrix A')   
tampil_matrix(A)
print('Matrix B', B)
print()

e = 1
iterasi = 0
while math.sqrt(e) >= error and iterasi < max_iterasi:
    if linalg.det(A) != 0:
        for i in range(len(X)):
            i_sum = 0
            for j in range(len(X)):
                if j!=i:
                    i_sum += A[i][j] * X_temp[j]
            X[i] = round((B[i] - i_sum) / A[i][i], 4)  

        print('k-'+str(iterasi+1), 'X =', X)

        e = 0
        for i in range(len(X)):
            e += (X[i] - X_temp[i]) ** 2

        X_temp = copy.copy(X)
        iterasi+=1
    else:
        print('tidak ada peneyelesaian untuk persamaan tersebut!')

for i in range(len(X)):
    print('X'+str(i+1),':', X[i])

Pada program tersebut di deklarasikan error (treshold) dan maksimal program untuk melakukan iterasi. Dalam kasus ini akan di selesaikan sistem persamaan berikut untuk menguji program metode gauss jacobi.

error = 0.001
max_iterasi = 100

A = [[10, -1, 2, 0], [-1, 11, -1, 3], [2, -1, 10, -1], [0, 3, -1, 8]]
B = [6, 25, -11, 15]
X = [0] * len(A)
X_temp = copy.copy(X)

Letak komputasi utama terdapat pada listing berikut. Program tersebut akan berhenti saat nilai dari $ \sqrt { \sum _{i=1}^{n} (x_i - x_{i-1})^2 } $ kurang dari error yang ditetapkan, atau iterasi telah mencapai batas yang ditentukan

e = 1
iterasi = 0
while math.sqrt(e) >= error and iterasi < max_iterasi:
    if linalg.det(A) != 0:

        ##Gauss Jacobi Method

        print('k-'+str(iterasi+1), 'X =', X)

        e = 0
        for i in range(len(X)):
            e += (X[i] - X_temp[i]) ** 2

        X_temp = copy.copy(X)
        iterasi+=1
    else:
        print('tidak ada peneyelesaian untuk persamaan tersebut!')

Dalam listing berikut melakukan komputasi dari motode Gauss Jacobi, yaitu $ \sum _ { i = 1 }^{n} x _i ^{(k+1)} = {b_i - \sum _{j=1}^{i-1} a_{ij}x_{j}^{(k)} \sum _{j=i+1}^{n} a_{ij}x_{j}^{(k)} \over a_{ii}} $

for i in range(len(X)):
    i_sum = 0
    for j in range(len(X)):
        if j!=i:
            i_sum += A[i][j] * X_temp[j]
    X[i] = round((B[i] - i_sum) / A[i][i], 4)

Setelah program tersebut dijalankan maka menghasilkan output seperti berikut.

Matrix A
| 10 -1 2 0 |
| -1 11 -1 3 |
| 2 -1 10 -1 |
| 0 3 -1 8 |

Matrix B [6, 25, -11, 15]

k-1 X = [0.6, 2.2727, -1.1, 1.875]
k-2 X = [1.0473, 1.7159, -0.8052, 0.8852]
k-3 X = [0.9326, 2.0533, -1.0494, 1.1309]
k-4 X = [1.0152, 1.9537, -0.9681, 0.9738]
k-5 X = [0.989, 2.0114, -1.0103, 1.0213]
k-6 X = [1.0032, 1.9923, -0.9945, 0.9944]
k-7 X = [0.9981, 2.0023, -1.002, 1.0036]
k-8 X = [1.0006, 1.9987, -0.999, 0.9989]
k-9 X = [0.9997, 2.0004, -1.0004, 1.0006]
k-10 X = [1.0001, 1.9998, -0.9998, 0.9998]
k-11 X = [0.9999, 2.0001, -1.0001, 1.0001]
X1 : 0.9999
X2 : 2.0001
X3 : -1.0001
X4 : 1.0001

Metode Gauss Seidel¶

Gauss Seidel adalah salah satu metode iteratif yang menggunakan proses iterasi hingga diperoleh nilai-nilai yang berubah-ubah dan akhirnya relatif konstan. Metode iterasi Gauss-Seidel dikembangkan dari gagasan metode iterasi pada solusi persamaan tak linier. Secara umum iterasi gauss seidel di definisikan sebagai berikut.

$\sum _ { i = 1 }^{n} x _i ^{(k+1)} = {b_i - \sum _{j=1}^{i-1} a_{ij}x_{j}^{(k+1)} \sum _{j=i+1}^{n} a_{ij}x_{j}^{(k)} \over a_{ii}}$

Perhitungan Gauss Seidel¶

Sebagai contoh, terdapat sistem persamaan linear berikut. Kita dapat mencari nilai x tersebut menggunakan metode Gauss Seidel.

$10x_1 - x_2 + 2x_3 = 6 \\ -x_1 + 11x_2 - x_3 + 3x_3 = 25 \\ 2x_1 - x_2 + 10x_3 - x_4 = -11 \\ 3x_2 - x_3 + 8x_4 = 15$

Pertama kita dapat menginisialisasi nilai x, dalam contoh ini semua nilai x di inisialisasi dengan 0.

$x_1=0, x_2=0, x_3=0, x_4=0$

Sama halnya dengan perhitungan metode Gauss Jacobi, hanya saja dalam perhitungan metode Gauss Seidel menggunakan nilai x terbaru setiap mencari nilai x berikutnya.

$x_1 = {x_2 + 2x_3 + 6 \over 10}, x_1= {0 + 2(0) + 6 \over 10} = 0,6000 \\ x_2 = {-x_1 + x_3 - 3x_4 + 25 \over 11}, x_2 = {0,6 + 0 -3(0) + 25 \over 11} = 2,3273 \\ x_3 = {-2x_1 + x_2 + x_4 + 11 \over 10}, x_3 = {-2(0,6) + 2,3273 + 0 +11 \over 10} = -0,9873 \\ x_4 = {-3x_2 + x_3 +15 \over -8}, x_4 = {-3(2,3273) + (-0,9873) + 15 \over -8} = 0,8789$

Setelah menyelesaikan satu iterasi dari metode Gauss Seidel maka ditemukan nilai $x_1=0,6000$ , $x_2=2,3273$ , $x_3=-0,9873$ , dan $x_4=0,8789$ .

Implementasi Gauss Seidel dengan Python¶

import math
import copy
from numpy import linalg

##A = [[10, -1, 2, 0], [-1, 11, -1, 3], [2, -1, 10, -1], [0, 3, -1, 8]]
##B = [6, 25, -11, 15]

A = []
B = []

n_spl = int(input('masukkan banyak persamaan : '))
for i in range(n_spl):
    temp = []
    for j in range(n_var):
        temp.append(float(input('masukkan koefisien SPL ke-%i x%i : '%((i+1),(j+1)))))
    A.append(temp)
    B.append(float(input('masukkan hasil SPL ke-%i : '%(i+1))))

error = float(input('masukkan batas error : '))
max_iterasi = int(input('masukkan maksimal iterasi : '))           

X = [0] * len(A)
X_prev = copy.copy(X)


def tampil_matrix(matrix):
    for i in range(len(matrix)):
        print('|', end=' ')
        for j in range(len(matrix[0])):
            print(matrix[i][j], end=' ')
        print('|')
    print()

print('Matrix A')   
tampil_matrix(A)
print('Matrix B', B)
print()

e = 1
iterasi = 0
while math.sqrt(e) >= error and iterasi < max_iterasi:
    if linalg.det(A) != 0:
        for i in range(len(X)):
            i_sum = 0
            for j in range(len(X)):
                if j!=i:
                    i_sum += A[i][j] * X[j]
            X[i] = round((B[i] - i_sum) / A[i][i], 4)  

        print('k-'+str(iterasi+1), 'X =', X)

        e = 0
        for i in range(len(X)):
            e += (X[i] - X_prev[i]) ** 2

        X_prev = copy.copy(X)
        iterasi+=1
    else:
        print('tidak ada peneyelesaian untuk persamaan tersebut!')

for i in range(len(X)):
    print('X'+str(i+1),':', X[i])

Berikut merupakan listing utama dari program tersebut. listing tersebut merupakan tempat komputasi dari metode Gauss Seidel. Program tersebut akan berjalan dan berhenti dalam kondisi seperti program Gauss Jacobi, hanya saja perbedaannya terletak pada proses perhitungan.

e = 1
iterasi = 0
while math.sqrt(e) >= error and iterasi < max_iterasi:
    if linalg.det(A) != 0:

        ### Gauss Seidel Method

        print('k-'+str(iterasi+1), 'X =', X)

        e = 0
        for i in range(len(X)):
            e += (X[i] - X_prev[i]) ** 2

        X_prev = copy.copy(X)
        iterasi+=1
    else:
        print('tidak ada peneyelesaian untuk persamaan tersebut!')

Dalam listing berikut melakukan komputasi dari motode Gauss Seidel, yaitu $ \sum _ { i = 1 }^{n} x _i ^{(k+1)} = {b_i - \sum _{j=1}^{i-1} a_{ij}x_{j}^{(k+1)} \sum _{j=i+1}^{n} a_{ij}x_{j}^{(k)} \over a_{ii}} $

 for i in range(len(X)):
    i_sum = 0
    for j in range(len(X)):
        if j!=i:
            i_sum += A[i][j] * X[j]
    X[i] = round((B[i] - i_sum) / A[i][i], 4)

Setelah program tersebut dijalankan maka menghasilkan output seperti berikut.

Matrix A
| 10 -1 2 0 |
| -1 11 -1 3 |
| 2 -1 10 -1 |
| 0 3 -1 8 |

Matrix B [6, 25, -11, 15]

k-1 X = [0.6, 2.3273, -0.9873, 0.8788]
k-2 X = [1.0302, 2.037, -1.0145, 0.9843]
k-3 X = [1.0066, 2.0036, -1.0025, 0.9983]
k-4 X = [1.0009, 2.0003, -1.0003, 0.9998]
k-5 X = [1.0001, 2.0, -1.0, 1.0]
X1 : 1.0001
X2 : 2.0
X3 : -1.0
X4 : 1.0

Sekian terimakasih :)