Penerapan Eliminasi Gauss pada Rstudio
Fitria Susanti, Prof. Dr. Suhartono, M.Kom
01/12/2021
Eliminasi Gauss
Pada sub-chapter ini kita akan menggunakan operasi baris elementer yang telah dijelaskan pada Chapter 2.5. Terdapat dua topik yang akan dibahas pada sub-chapter ini, yaitu: row echelon form termasuk reduced row echelon form dan matriks tridiagonal.
Eliminasi Gauss merupakan sebuah cara untuk mencari penyelesaian sistem persamaan linier. Ide dasar dari eliminasi Gauss adalah melakukan operasi matematika pada baris matriks (lihat Chapter 2.5) 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).
Row Echelon For
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.
Misalkan terdapat persamaan linier seperti yang ditunjukkan pada Persamaan (6.10).
dimana:
matriks A merupakan matriks koefisien / Jacobian
vaktor X merupakan vaktor variabel
vektor B merupakan vektor konstanta
matriks pada Persamaan (6.11) dapat diubah menjadi augmented matrix, yaitu: perluasan matriks A dengan menambahkan vektor B pada kolom terakhirnya.
Teorema 6.1 (spltheorem) 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 BB tidak nol atau terdapat bn???0bn???0.
Determinan dari matriks koefisiensistem persamaan linier tidak sama dengan nol.
Untuk memperoleh penyelesaian sistem persamaan linier, Persamaan (6.13) perlu dilakukan operasi baris elementer.
Algoritma Row Echelon Form
Masukkan matriks AA, dan vektor BB beserta ukurannya nn
Buat augmented matrix \[A\|B\]\[A\|B\] namakan dengan AA
Untuk baris ke-ii dimana i=1i=1 s/d nn, perhatikan apakah nilai ai,jai,j sama dengan nol. a) Bila iya, lakukan row swapping antara baris ke-ii dan baris ke-i+k???ni+k???n, dimana ai+k,jai+k,j tidak sama dengan nol. Bila tidak ada berarti perhitungan tidak bisa dilanjutkan dan proses dihentikan dengan tanpa penyelesaian, b) Bila tidak, lanjutkan.
Untuk baris ke-jj, dimana j=i+1j=i+1 s/d nn, lakukan operasi baris elementer:a) Hitung c=aj,iai,ic=aj,iai,i, b) untuk kolom kk, dimana k=1k=1 s/d n+1n+1, hitung aj,k=aj,k???c.ai,kaj,k=aj,k???c.ai,k.
Hitung akar, untuk i=ni=n s/d 1 (bergerak dari baris pertama) menggunakan Persamaan (6.16).
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)
}Dengan menggunakan fungsi ref_matrix(), kita dapat membentuk matriks row echelon form pada Contoh 6.1.
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
ref_matrix(m)
## [,1] [,2] [,3] [,4]
## [1,] 1 1 1 6
## [2,] 0 1 -2 -4
## [3,] 0 0 -2 -6Matrik 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. Bentuk matriks tridiagonal disajikan pada Persamaan (6.19).
Algoritma Penyelesaian Matrik Tridiagonal
Bentuk sistem persamaan linier menjadi matriks pada Persamaan (6.21).
Lakukan foward sweep. Setiap elemen diagonal l dieliminasi menggunakan reduksi baris.
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)
}Contoh 6.5. Selesaikan sistem persamaan berikut menggunakan fungsi tridiagmatrix() dan fungsi gauss_jordan()!
Jawab:
Langkah pertama untuk menyelesaikannya, kita harus merubah persamaan tersebut kedalam bentuk matriks
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)Setelah terbentuk, vektor tersebut dapat langsung dimasukkan ke dalam fungsi tridiagmatrix().
tridiagmatrix(L=l, D=d, U=u, b=b)
## [1] 4 2 1 3
Untuk menyelesaikannya menggunakan fungsi gauss_jordan(), kita perlu membentuk augmented matrix-nya terlebih dahulu.
m <- matrix(c(3,4,0,0,4,5,2,0,
0,2,5,3,0,0,3,5,
20,28,18,18), nrow=4)
gauss_jordan(m## [,1] [,2] [,3] [,4] [,5]
## [1,] 1 0 0 0 4
## [2,] 0 1 0 0 2
## [3,] 0 0 1 0 1
## [4,] 0 0 0 1 3Penyelesaian Sistem Persamaan Linier Menggunakan Fungsi solve()
R menyediakan fungsi bawaan solve() untuk menyelesaiakan sistem persamaan linier. Format fungsi solve() adalah sebagai berikut:
solve(a,b)Catatan: • a: matriks koefisien atau matriks segiempat • b: vektor konstanta
Berikut adalah contoh penerapan fungsi solve() pada sistem persamaan linier yang disajikan pada Contoh 6.2:
# 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 3Jika kita hanya memasukkan matriks persegi, maka output yang akan dihasilkan adalah invers dari matriks yang kita masukkan.
solve(a)## [,1] [,2] [,3]
## [1,] 2 -1 7.401487e-17
## [2,] 14 -9 -1.000000e+00
## [3,] 17 -11 -1.000000e+00Jika kita mengalikan invers dengan matriks semula, maka akan dihasilkan output berupa matriks identitas.
a%*%solve(a)## [,1] [,2] [,3]
## [1,] 1 0 0
## [2,] 0 1 0
## [3,] 0 0 1Penyelesaian Sistem Persamaan Linier Menggunakan Fungsi ’Solve.tridiag()‘
Penyelesaian matriks tridiagonal selain menggunakan fungsi solve(), juga dapat menggunakan fungsi Solve.tridiag() dari Paket limSolve. Untuk menginstall dan mengaktifkan Paket tersebut, jalankan sintaks berikut:
install.packages("limSolve")library(limSolve)Fungsi Solve.tridiag() memiliki format sebagai berikut:
Solve.tridiag ( diam1, dia, diap1, B=rep(0,times=length(dia)))
Catatan:
• diam1: vektor bukan nol di bawah diagonal matriks
• dia: vektor bukan nol pada diagonal matriks
• diap1: vektor bukan nol di atas diagonal matriks
• B: vektor konstanta
l <- 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