Eliminasi Gauss pada Aljabar Linier dalam Bahasa R

Prodi : Teknik Informatika

Lembaga : UIN Maulana Malik Ibrahim Malang

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 (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 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 (6.10).

dimana \(ai,j\) untuk \(i\) =1 sampai dengan \(m\) dan \(j\) =1 sampai dengan \(n\) merupakan koefisien persamaan linier. \(xi\) untuk \(i\) =1 sampai dengan \(n\) merupakan variabel bebas pada sistem persamaan linier.

Persamaan linier pada Persamaan (6.10) dapat dinyatakan ke dalam bentuk matriks pada Persamaan (6.11).

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 (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 \(B\) tidak nol atau terdapat \(bn≠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. Hasil operasi baris dasar akan menghasilkan matriks row echelon form yang disajikan pada Persamaan (6.15).

Sehingga penyelesaian sistem persamaan linier dapat diperoleh menggunakan Persamaan (6.16).

Contoh 6.1 Selesaikan sistem persamaan berikut:

Jawab:

Augmented matrix sistem

persamaan linier tersebut adalah sebagai berikut:

Operasi baris elementer selanjutnya dilakukan pada matriks tersebut. Pada langkah pertama, baris ke-2 dikurangkan dengan baris ke-1 ((\(B2\) − \(B1\) ) dan baris ke-3 dikurangkan oleh dua kali baris ke-1 ( \(B3\) - \(2B1\) ).

Hasil dari langkah pertama tersebut, selanjutnya menjadi input dari langkah selanjutnya. Pada langkah selanjutnya operasi baris elementer kembali dilanjutkan. Baris ke-3 dikurangkan denganbaris ke-2 ( \(B3\) - \(B2\) ).

Setelah diperoleh matriks row echelon form selanjutnya penyelesaian persamaan dapat dikerjakan 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   -6

matriks yang diperoleh selanjutnya dapat diselesaikan menggunakan Persamaan (6.16).

Contoh 6.2 Dengan menggunakan fungsi ref_matrix(), buatlah matriks row echelon form dari sistem persamaan linier berikut:

Jawab:

Augmented matrix dari sistem persamaan tersebut adalah sebagai berikut:

Penyelesaian matriks tersebut adalah sebagai berikut:

(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    3##      [,1] [,2] [,3] [,4]
## [1,]    2    1   -1    1
## [2,]    3    2   -2    1
## [3,]    1   -5    4    3

ref_matrix(m)

##      [,1] [,2] [,3] [,4]
## [1,]    2  1.0 -1.0  1.0
## [2,]    0  0.5 -0.5 -0.5
## [3,]    0  0.0 -1.0 -3.0

Proses lebih lanjut akan menghasilkan penyelesaian sebagai berikut:

Eliminasi Gauss-Jordan

Berbeda dengan metode eliminasi Gauss yang telah dijelaskan pada Chapter 6.3.1, 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 (lihat Persamaan (6.17)).

Sehingga penyelesaian persamaan linier tersebut adalah nilai $d1,d2,d3,…,dn$ dan atau:

Contoh 6.3 Selesaikan sistem persamaan berikut:

Jawab:

Augmented matrix dari persamaan linier tersebut adalah sebagai berikut:

Operasi baris elementer selanjutnya dilakukan pada matriks tersebut.

Penyelesaian persamaan linier tersebut adalah sebagai berikut:

---

---

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)
}

Dengan menggunakan fungsi gauss_jordan(), sistem persamaan linier pada Contoh 6.3:

(m <- matrix(c(1,2,1,4,3,8), nrow=2))

##      [,1] [,2] [,3]
## [1,]    1    1    3
## [2,]    2    4    8

gauss_jordan(m)

##      [,1] [,2] [,3]
## [1,]    1    0    2
## [2,]    0    1    1

Contoh 6.4 Dengan menggunakan fungsi gauss_jordan(), carilah penyelesaian sistem persamaan linier pada Contoh 6.1 dan Contoh 6.2:

Jawab:

Untuk Contoh 6.1:

am <- c(1,1,2,
        1,2,1,
        1,-1,2,
        6,2,10)
m <- matrix(am, nrow=3)

gauss_jordan(m)

##      [,1] [,2] [,3] [,4]
## [1,]    1    0    0    1
## [2,]    0    1    0    2
## [3,]    0    0    1    3

Untuk Contoh 6.2:

m <- matrix(c(2,3,1,1,2,-5,
              -1,-2,4,1,1,3), 
            nrow=3)
gauss_jordan(m)

##      [,1] [,2] [,3] [,4]
## [1,]    1    0    0    1
## [2,]    0    1    0    2
## [3,]    0    0    1    3

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. Bentuk matriks tridiagonal disajikan pada Persamaan (6.19).

Penyelesaian persamaan tersebut disajikan pada Persamaan (6.20).

dimana \(i = n - 1,n-2,...1\)

Pada beberapa textbook, diagonal matriks sering dilambangkan dengan \(l\) diagonal bawah), \(d\) (diagonal tengah), dan \(u\) (diagonal atas). Bentuk matriksnya disajikan pada Persamaan (6.21).

---

---

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    3

Penyelesaian 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 3

Jika 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.401e-17
## [2,]   14   -9 -1.000e+00
## [3,]   17  -11 -1.000e+00

Jika 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    1

Penyelesaian 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

Untuk memahami penerapannya, kita akan menggunakan kembali matriks yang ada pada Contoh 6.5.

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

REFERENSI:

https://bookdown.org/moh_rosidi2610/Metode_Numerik/linearaljabar.html#gausselimination