Eliminasi Gauss
Mutiara Aprillia Dzakiroh
2/12/2021
Dosen Pengampu : Prof. Dr. Suhartono, M.Kom
Mata Kuliah : Kalkulus
Prodi : Teknik Informatika
Lembaga : Universitas Islam Negeri Maulana Malik Ibrahim Malang
Carl Friedrich Gauss (1777-1855) adalah seorang matematikawan berkebangsaan Jerman yang mempunyai kontribusi besar didalam bidang geometri, teori bilangan, teori fungsi dan teori probabilitas. Dia menemukan cara untuk menghitung lintasan asteroid, membuat penemuan dasar di dalam teori potensial (bidang elektromagnetik), dan orang pertama yang menggunakan telegraf (1833). Karena konstribusinya itu, dia mempunyai julukan “Prince of Mathematics”.
Eliminasi gauss ditemukan oleh Carl Friedrich Gauss, metode ini dapat dimanfaatkan untuk memecahkan sistem persamaan linear dengan merepresentasikan (mengubah) menjadi bentuk matriks, matriks tersebut lalu diubah kebentuk Eselon Baris melalui Operasi Baris Elementer. Kemudian sistem diselesaikan dengan substitusi balik.
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:
1. Angka bukan nol pertama dari kiri (leading coefficient) selalu di sebelah kanan angka bukan nol pertama pada baris di atasnya.
2. Baris yang terdiri dari semua nol ada di bagian bawah matriks.Misalkan terdapat persamaan linier seperti yang ditunjukkan pada Persamaan berikut.
dimana:
matriks A merupakan matriks koefisien / Jacobian
vaktor X merupakan vaktor variabel
vektor B merupakan vektor konstanta
Suatu sistem persamaan linier mempunyai penyelesaian tunggal bila memenuhi syarat-syarat sebagai berikut:
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.
Berdasarkan algoritma tersebut, kita dapat menyusun fungsi pada R untuk menyelesaikan sistem persamaan linier menggunakan matriks row echelon form. Fungsi yang akan dibentuk hanya sampai pada algoritma ke-4. Proses substitusi akan dilakukan secara manual. 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)
}
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 102. Eliminasi Gauss-Jordan
Berbeda dengan metode eliminasi Gauss, 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 :
Masukkan matriks A dan vektor B beserta ukurannya \(n\)
Buat augmented matrix [A|B] namakan dengan A
Untuk baris ke-\(i\) dimana \(i\)=1 s/d \(n\)
Perhatikan apakah nilai ai.i sama dengan nol:
Bila ya: pertukakan baris ke-i dan baris ke-i+k≤n, dimana ai+k.i tidak sama dengan nol, bila tidak ada berarti perhitungan tidak bisa dilanjutkan dan proses dihentikan dengan tanpa penyelesaian.
Bila tidak: lanjutkan
Jadikan nilai diagonalnya menjadi satu dengan cara untuk setiap kolom k dimana k=1 s/d n+1, hitung ai.k=ai.k dibagi ai.i
- Untuk baris ke-j, dimana j=i+1 s/d n. Lakukan operasi baris elementer untuk kolom k dimana k=1 s/d n.
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)
}
(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. Contoh khusus yang sering dijumpai adalah matriks tridiagonal yang memiliki bandwidth tiga.
Proses eliminasi untuk matriks tridiagonal bersifat trivial karena dengan membentuk sebuah subdiagonal tambahan, proses substitusi mundur segera dapat dilakukan.
Algoritma Penyelesaian Matrik Tridiagonal:
Bentuk sistem persamaan linier menjadi matriks pada Persamaan
Lakukan foward sweep. Setiap elemen diagonal l dieliminasi menggunakan reduksi baris.
Lakukan backward sweep. Setiap elemen diagonal u dilakukan eliminasi.
Berdasarkan algoritma tersebut, kita dapat membangun sebuah fungsi pada R. Fungsi penyelesaian matriks tridiagonal disajikan 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)
}
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 3