Dosen Pengampu : Prof. Dr. Suhartono, M.Kom

Lembaga : Universitas Islam Negeri Maulana Malik Ibrahim Malang

Jurusan : Teknik Informatika

Fakultas : Sains dan Teknologi

Siapa itu Gauss?

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

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.

6.3 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).

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

Jawab:

Augmented matrix sistem persamaan linier tersebut adalah sebagai berikut :

Setelah diperoleh matriks row echelon form selanjutnya penyelesaian persamaan dapat dikerjakan menggunakan Persamaan (6.16).

————————————————————————————————————

Algoritma Row Echelon Form

(1). Masukkan matriks A, dan vektor B beserta ukurannya n

(2). Buat augmented matrix [A|B] namakan dengan A

(3). Untuk baris ke- i dimana i=1 s/d n , perhatikan apakah nilai sama dengan nol.a)Bilaiya,lakukanrowswappingantarabaris
ke- i dan baris ke- i+k≤n , dimana ai+k,j tidak sama dengan nol. Bila tidak ada berarti perhitungan tidak bisa dilanjutkan dan proses dihentikan dengan tanpa penyelesaian, b) Bila tidak, lanjutkan.

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

(5). 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,]    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:

\(Referensi\)