Eliminasi Gauss

Dalam matematika, eliminasi Gauss adalah algoritma yang digunakan untuk menyelesaikan sistem persamaan linear. Algoritma ini terdiri dari serangkaian operasi yang dilakukan pada matriks koefisien dari sistem persamaan tersebut. Walau akan mengubah bentuk matriks, operasi-operasi tersebut tidak akan mengubah solusi dari sistem persamaan. Hal ini memungkinkan matriks koefisien dibentuk menjadi sebuah matriks segitiga atas, sehingga solusi sistem persamaan dapat ditentukan dengan cukup melakukan eliminasi variabel secara berulang. Eliminasi Gauss juga dapat digunakan untuk menghitung rank dari matriks, determinan dari matriks persegi, dan invers dari matriks nonsingular. Metode ini dinamai dari matematikawan Carl Friedrich Gauss (1777–1855), walaupun beberapa kasus khusus dari metode ini — tapi tanpa dilengkapi bukti — sudah dikenal oleh matematikawan Tionghoa semenjak tahun 179 M. Matriks segitiga atas yang didapat dari algoritma ini akan memiliki bentuk eselon baris. Jika semua koefisien utama matriks bernilai 1, dan kolom-kolom yang mengandung koefisien utama memiliki bentuk yang sama dengan kolom pada matriks identitas, matriks tersebut dikatakan memiliki bentuk eselon baris tereduksi. Eliminasi Gauss yang dilakukan untuk mengubah matriks koefisien sampai menjadi bentuk eselon baris tereduksi terkadang disebut sebagai eliminasi Gauss–Jordan. Karena alasan komputasi, operasi baris untuk mencari solusi sistem persamaan terkadang dihentikan sebelum matriks berada dalam bentuk tereduksinya. Kompleksitas komputasi eliminasi Gauss untuk sebuah matriks berukuran n × n adalah n 3 . Dalam bentuk paling sederhana, secara numerik algoritma ini rentan terhadap galat pembulatan. Namun hal ini dapat diatasi dengan menggunakan metode pivot; menjadikannya cara standar menemukan solusi sistem persamaan linear, dan menjadi bagian pustaka program aljabar linear yang penting seperti NAG, IMSL, dan LAPACK.