Eliminasi Gauss Aljabar Linier Pada R
Salsabila Ramadanti Nuraini, Prof.Dr.Suhartono,M.Kom
12/4/2021
Universitas : UIN Maulana Malik Ibrahim Malang
Jurusan : Teknik Informatika
Gambar 1.1: Gambar Eliminasi Gauss
Eliminasi Gauss merupakan sebuah cara untuk mencari penyelesaian sistem persamaan linier. Ide dasar dari eliminasi Gauss adalah melakukan operasi matematika pada baris matriks dan melanjutkannya sampai hanya tersisa satu variabel saja. Kita dapat melakukan lebih dari satu operasi baris elementer pada proses elmininasi ini (contoh: mengalikan sebuah baris dengan konstanta dan menjumlahkan hasilnya pada baris lain).
1. Row Echelon Form
Sebuah matriks merupakan row echelon form jika matriks tersebut memenuhi beberapa kondisi:
Angka bukan nol pertama dari kiri (leading coefficient) selalu di sebelah kanan angka bukan nol pertama pada baris di atasnya.
Baris yang terdiri dari semua nol ada di bagian bawah matriks.
Suatu sistem persamaan linier mempunyai penyelesaian tunggal bila memenuhi syarat-syarat sebagai berikut: 1. ukuran persamaan linier simultan bujursangkar (jumlah persamaan sama dengan jumlah variabel bebas).
sistem persamaan linier non-homogen di mana minimal ada satu nilai vektor konstanta B tidak nol atau terdapat bn≠0.
Determinan dari matriks koefisiensistem persamaan linier tidak sama dengan nol.
Algoritma Row Echelon Form
Berikut adalah sintaks yang digunakan:
ref_matrix <- function(a){
m <- nrow(a)
n <- ncol(a)
piv <- 1
# cek elemen diagonal apakah bernilai nol
for(row_curr in 1:m){
if(piv <= n){
i <- row_curr
while(a[i, piv] == 0 && i < m){
i <- i+1
if(i > m){
i <- row_curr
piv <- piv+1
if(piv > n)
return(a)
}
}
# jika diagonal bernilai nol, lakukan row swapping
if(i != row_curr)
a <- swap_row(a, i, row_curr)
# proses triangulasi untuk membentuk matriks segitiga atas
for(j in row_curr:m)
if(j != row_curr){
c <- a[j, piv]/a[row_curr, piv]
a <- replace_row(a, row_curr, j, -c)
}
piv <- piv+1
}
}
return(a)
}Dengan menggunakan fungsi ref_matrix(), kita dapat membentuk matriks row echelon form
am <- c(1,1,2,
1,2,1,
1,-1,2,
6,2,10)
(m <- matrix(am, nrow=3))## [,1] [,2] [,3] [,4]
## [1,] 1 1 1 6
## [2,] 1 2 -1 2
## [3,] 2 1 2 10(m <- matrix(c(2,3,1,
1,2,-5,
-1,-2,4,
1,1,3), nrow=3))## [,1] [,2] [,3] [,4]
## [1,] 2 1 -1 1
## [2,] 3 2 -2 1
## [3,] 1 -5 4 3Proses lebih lanjut akan menghasilkan penyelesaian sebagai berikut:
x^1=1
x^2=2
x^3=3
2. Eliminasi Gauss-Jordan
Metode eliminasi Gauss-Jordan membentuk matriks menjadi bentuk reduced row echelon form. Metode ini merupakan pengembangan metode eliminasi Gauss, dimana matriks sebelah kiri augmented matrix diubah menjadi matriks diagonal.
Algoritma Metode Eliminasi Gauss-Jordan
Dari algoritma tersebut, kita dapat membangun sebuah fungsi menggunakan R. Fungsi tersebut adalah sebagai berikut:
gauss_jordan <- function (a){
m <- nrow (a)
n <- ncol (a)
piv <- 1
# cek elemen diagonal utama apakah bernilai nol
for(row_curr in 1:m){
if(piv <= n){
i <- row_curr
while(a[i, piv] == 0 && i < m){
i <- i + 1
if(i > m){
i <- row_curr
piv <- piv + 1
if(piv > n)
return (a)
}
}
# jika diagonal utama bernilai nol,lakukan row swapping
if(i != row_curr)
a <- swap_row(a, i, row_curr)
# proses pembentukan matriks reduced row echelon form
piv_val <- a[row_curr , piv]
a <- scale_row (a, row_curr , 1 / piv_val)
for(j in 1: m){
if(j != row_curr){
k <- a[j, piv]/a[row_curr, piv]
a <- replace_row (a, row_curr, j, -k)
}
}
piv <- piv + 1
}
}
return (a)
}Contoh penerapannya adalah sebagai berikut.
(m <- matrix(c(1,2,1,4,3,8), nrow=2))## [,1] [,2] [,3]
## [1,] 1 1 3
## [2,] 2 4 83. Matrik Tridiagonal
Metode eliminasi Gauss merupakan metode yang sederhana untuk digunakan khususnya jika semua koefisien bukan nol berkumpul pada diagonal utama dan beberapa diagonal sekitarnya. Suatu sistem yang bersifat demikian disebut sebagai banded dan banyaknya diagonal yang memuat koefisien bukan nol disebut sebagai bandwidth. Proses eliminasi untuk matriks tridiagonal bersifat trivial karena dengan membentuk sebuah subdiagonal tambahan, proses substitusi mundur segera dapat dilakukan.
Algoritma Penyelesaian Matrik Tridiagonal
Fungsi penyelesaian matriks tridiagonal sebagai berikut.
tridiagmatrix <- function (L, D, U, b){
n <- length (D)
L <- c(NA , L)
## forward sweep
U[1] <- U[1] / D[1]
b[1] <- b[1] / D[1]
for(i in 2:(n - 1)){
U[i] <- U[i] / (D[i] - L[i] * U[i - 1])
b[i] <- (b[i] - L[i] * b[i - 1]) /
(D[i] - L[i] * U[i - 1])
}
b[n] <- (b[n] - L[n] * b[n - 1])/(D[n] - L[n] * U[n - 1])
## backward sweep
x <- rep.int (0, n)
x[n] <- b[n]
for(i in (n - 1) :1)
x[i] <- b[i] - U[i] * x[i + 1]
return (x)
}Untuk menyelesaikan persamaan tersebut menggunakan fungsi tridiagmatrix(), kita perlu membentuk vektor diagonal l,d,u, dan b.
l <- u <- c(4, 2, 3); d <- c(3, 5, 5, 5)
b <- c(20, 28, 18, 18)tridiagmatrix(L=l, D=d, U=u, b=b)## [1] 4 2 1 34. Penyelesaian Sistem Persamaan Linier Menggunakan Fungsi solve()
# memecah matriks m menjadi matriks koefisien dan vektor konstanta
a <- matrix(c(2,3,1,1,2,-5,-1,-2,4),nrow=3)
b <- c(1,1,3)
solve(a,b)## [1] 1 2 35. Penyelesaian Sistem Persamaan Linier Menggunakan Fungsi ’Solve.tridiag()`
library(limSolve)## Warning: package 'limSolve' was built under R version 4.1.2l <- u <- c(4, 2, 3); d <- c(3, 5, 5, 5)
b <- c(20, 28, 18, 18)
Solve.tridiag(diam1=l, dia=d, diap1=u, B=b)## [,1]
## [1,] 4
## [2,] 2
## [3,] 1
## [4,] 3