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 (row echelon form). Jika semua koefisien utama (nilai bukan nol pertama pada sebuah baris) 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 (reduced row echelon form). 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  adalah . 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.

Algoritma

Operasi baris dasar 
Setelah menyusun sistem persamaan linear menjadi sebuah matriks koefisien, eliminasi Gauss melakukan serangkaian operasi baris dasar untuk "menyederhanakan" baris-baris matriks. Eliminasi ini dapat dibagi menjadi dua bagian. Bagian pertama, terkadang disebut dengan eliminasi maju, mereduksi sistem yang diberikan ke dalam bentuk eselon baris. Hasil dari bagian ini dapat memberitahu apakah sistem persamaan linear tidak memiliki solusi, memiliki solusi unik, atau memiliki tak hingga solusi. Bagian kedua, terkadang disebut substitusi mundur, melanjutkan penggunaan operasi baris dasar sampai matriks berada dalam bentuk eselon baris tereduksi, dengan kata lain, hingga solusi ditemukan.

Ada tiga jenis operasi baris dasar yang dapat dilakukan pada baris matriks tersebut:
 Menukar posisi dua baris.
 Mengalikan suatu baris dengan skalar bukan nol .
 Menambahkan suatu baris dengan suatu kelipatan dari baris yang lain.

Operasi-operasi ini tidak mengubah kumpulan solusi. Oleh karena itu, jika tujuan seseorang adalah untuk menyelesaikan sistem persamaan linear, penggunaan operasi baris ini dapat membuat masalah menjadi lebih mudah. Operasi baris dasar juga dapat dianggap sebagai proses menghasilkan dekomposisi matriks dari matriks asli. Sudut pandang ini ternyata sangat berguna dalam menganalisis algoritma. Operasi baris dasar dapat dilihat sebagai sebuah perkalian matriks dasar (di sebelah kiri) dengan matriks asli. Hal ini mengartikan bagian pertama dari eliminasi Gauss sebenarnya mencari dekomposisi LU; sedangkan bagian kedua menyatakan matriks asli sebagai hasil perkalian dari suatu matriks terbalikkan yang unik dengan suatu matriks eselon baris tereduksi yang unik.

Operasi dasar yang lain adalah menukar posisi dua kolom. Hal ini tidak diharuskan dalam menjalankan algoritma, namun terkadang digunakan dalam program komputer karena alasan stabilitas. Analoginya, ketika menghitung dalam kepala, kita terkadang menghindari mengalikan baris dengan bentuk pecahan yang rumit. Kekurangan dari operasi ini adalah menghasilkan komputasi tambahan dan juga mengubah nilai determinan dari matriks koefisien.

Bentuk eselon baris 
Untuk setiap baris pada matriks, jika entri baris tersebut tidak semuanya terdiri dari angka nol, maka entri bukan nol pertama (dari kiri) disebut koefisien utama (atau pivot) dari baris itu. Lebih lanjut, jika ada dua koefisien utama berada di kolom yang sama, maka operasi baris jenis ke-3 dapat digunakan untuk membuat salah satu koefisien tersebut menjadi nol. Operasi baris jenis ke-1 selanjutnya dipakai untuk mengurutkan baris-baris. Baris dengan koefisien utama muncul terlebih dahulu (posisinya lebih kiri) ketimbang baris yang lain, akan ditempatkan pada baris yang lebih tinggi di matriks koefisien. Sedangkan baris tanpa koefisien utama (semua entri bernilai nol) akan diletakkan pada baris terbawah pada matriks. Ketika semua operasi tersebut selesai dilakukan, maka matriks dikatakan berada dalam bentuk eselon baris. Kata "eselon" digunakan di sini karena secara kasar orang dapat membayangkan setiap baris diberi peringkat berdasarkan ukurannya, dengan yang terbesar di atas dan yang terkecil di bawah.

Sebagai contoh, matriks berikut dalam bentuk eselon baris, dengan koefisien utamanya ditunjukkan dengan warna merah:

 

Terlihat baris pertama memiliki koefisien utama memiliki posisi lebih kiri (berada di kolom kedua) ketimbang baris kedua, yang koefisien utamanya berada di kolom ketiga. Selain itu, baris berisi nol terletak pada baris paling bawah. 

Suatu matriks dikatakan dalam bentuk eselon baris tereduksi jika selanjutnya semua koefisien utama sama dengan 1 (yang dapat dicapai dengan menggunakan operasi baris dasar jenis ke-2), dan di setiap kolom yang berisi koefisien utama, semua entri lain di kolom itu adalah nol (yang dapat dicapai dengan menggunakan operasi baris dasar jenis ke-3). Bentuk eselon baris tereduksi dari contoh di atas adalah:

Contoh algoritma 
Misalkan kita ingin menemukan dan mendeskripsikan himpunan solusi ke sistem persamaan linear berikut:
 
Persamaan tersebut dapat dinyatakan dalam bentuk matriks koefisien gabungan:

Prosedur operasi baris dasar dapat diringkas sebagai berikut: hilangkan variabel  dari semua persamaan di bawah , lalu hilangkan variabel  dari semua persamaan di bawah ini . Ini akan membuat matriks memiliki bentuk matriks segitiga atas. Langkah ini hanya dapat bekerja jika tidak ada elemen diagonal pada matriks yang bernilai nol. Pada kasus ada elemen diagonal bernilai nol, pertukaran dengan baris lain (yang tidak bernilai nol pada kolom elemen diagonal yang dimaksud) perlu dilakukan.

Untuk pada langkah pertama, variabel  dihilangkan dari  dengan menambahkan  ke . Intepretasi lain dari operasi ini adalah mengganti  dengan , yang dilambangkan dengan . Sedangkan  dihilangkan dari  dengan menambahkan  ke . Langkah ini akan menghasilkan matriks koefisien dan sistem persamaan berikut: 
{| class="wikitable" style="background-color:white;"
|-
! Matriks koefisien gabungan !! Sistem persamaan
|- align="center"
| 
| 
|}
Langkah berikutnya adalah menghilangkan variabel   dengan melakukan operasi . Hal ini menghasilkan matriks berikut
{| class="wikitable" style="background-color:white;"
|-
! Matriks koefisien gabungan !! Sistem persamaan
|- align="center"
|
| 
|}
Saat ini bagian pertama pertama dari eliminasi Gauss telah selesai. Bagian berikutnya adalah menemukan solusi dari variabel dalam urutan terbalik, sebuah proses yang dikenal sebagai substitusi balik. Untuk permasalahan di atas, kita pertama kali mendapatkan . Lalu dengan mensubtitusi nilai  ke persamaan  akan didapatkan . Melanjutkan proses, didapatkan . Dari sudut pandang komputasi, cara ini lebih cepat untuk menemukan solusi sistem persamaan.

Alih-alih berhenti setelah matriks dalam bentuk eselon baris, seseorang dapat melanjutkan hingga matriks dalam bentuk eselon baris tereduksi, seperti yang dilakukan pada tabel berikut. Proses operasi baris hingga ke bentuk eselon baris tereduksi terkadang disebut sebagai Eliminasi Gauss–Jordan, untuk membedakannya dari proses operasi baris yang berhenti setelah mencapai bentuk eselon.

 {| class="wikitable" style="background-color:white;"
|-
! Operasi baris 
! Hasil matriks koefisien gabungan
! Sistem persamaan 
|- align="center"
| 
| 
| 
|- align="center"
| 
| 
| 
|- align="center"
| 
| 
| 
|}

Operasi pivot 
Secara umum, algoritma eliminasi Gauss tidak dapat bekerja tanpa menukar baris. Pada contoh algoritma di atas, algoritma tidak akan berjalan jika persamaan  adalah . Untuk mengatasi ini, perlu dipilih sebuah elemen tidak bernilai 0 pada kolom pertama matriks koefisien. Elemen ini disebut sebagai elemen pivot. Pada kasus ini, elemen  dari persamaan  digunakan sebagai elemen pivot:Setelah menukar baris pertama dengan baris kedua, eliminasi Gauss dapat berjalan:Untuk kalkulasi secara manual, elemen pivot bernilai -1 atau 1 menguntungkan untuk dipilih; karena memudahkan perhitungan eliminasi nilai elemen-elemen lain. Namun untuk kalkulasi menggunakan komputer, elemen pivot dengan nilai mutlak terbesar menguntungkan untuk digunakan; karena menghasilkan algoritma dengan stabilitas numerik paling baik. Operasi pivot juga dapat dilakukan dengan menukar kolom, sepertimenjadiPerlu diingat ketika bagian subtitusi balik, operasi pivot kolom mengubah susunan variabel di sistem persamaan, sehingga penyesuaian perlu dilakukan. Jika operasi pivot dilakukan dengan memilih elemen matriks dengan nilai mutlak terbesar, operasi pivot tersebut dinamakan dengan operasi pivot total (total pivoting). Secara umum, baris dan kolom dari matriks perlu ditukar untuk melakukan pivot jenis ini.

Operasi pivot dapat dilakukan tanpa memerlukan komputasi yang signifikan jika entri-entri pada matriks dan sisi ruas kanan persamaan tidak mengalami penukaran; informasi mengenai pertukaran baris/kolom dicatat dalam suatu vektor indeks

Sifat dari algoritma

Banyak operasi yang diperlukan 
Salah satu cara menentukan kompleksitas komputasi adalah menghitung banyaknya operasi aritmetika yang diperlukan oleh algoritma. Untuk menyelesaikan sistem persamaan linear dengan  persamaan dan  variabel, eliminasi Gauss perlu melakukan operasi baris dasar sampai matriks memiliki bentuk eselon baris, lalu menemukan solusi setiap variabel dengan urutan terbalik. Hal ini memerlukan  operasi pembagian,  operasi perkalian, dan  operasi pengurangan. Ketika ditotal, eliminasi Gauss memerlukan sekitar  operasi; menjadikannya algoritma dengan kompleksitas . Hal ini membuat eliminasi Gauss sebaiknya hanya dipakai untuk menyelesaikan sistem persamaan berukuran kecil sampai sedang (kurang lebih ). Metode iteratif umumnya lebih baik dalam menyelesaikan matriks dengan dimensi yang lebih tinggi dari ini.

Jika eliminasi Gauss dilakukan agar matriks berukuran  berbentuk eselon baris tereduksi, maka diperlukan  operasi aritmetika. Hal ini kurang lebih memerlukan 50% lebih banyak langkah komputasi, ketimbang hanya membuat matriks berbentuk eselon baris.

Akurasi dari solusi 
Salah satu kendala dari eliminasi Gauss adalah ketidakstabilan numeriknya, akibat pembagian oleh bilangan yang sangat kecil. Sebagai contoh, jika koefisien utama  dari suatu baris sangat dekat nilainya dengan 0, operasi baris akan melibatkan proses mengalikan baris dengan . Galat pembulatan dari perkalian ini akan merambat dan dapat membesar ke perhitungan-perhitungan selanjutnya. Untuk matriks secara umum, eliminasi Gauss umumnya stabil jika menerapkan operasi pivot (baik pivot baris atau pivot kolom), walaupun tetap ada beberapa kasus matriks dengan komputasi yang tidak stabil. Stabilitas dapat ditingkatkan dengan menerapkan operasi pivot total, namun ini jarang digunakan karena kompleksitas komputasi yang perlu dilakukan. Dekomposisi QR umumnya memiliki stabilitas yang lebih baik dalam hal ini, namun juga lebih sulit untuk menghitungnya.

Eliminasi Gauss stabil secara numerik untuk matriks yang dominan secara diagonal (diagonally dominant) dan matriks definit positif, sehingga dapat dilakukan tanpa melakukan pivoting; karena tidak ada nol di elemen diagonal matriks.

Sejarah 
Metode eliminasi Gauss muncul - meskipun tanpa dilengkapi bukti - dalam teks matematika Cina Bab Delapan: Array Persegi Panjang dari Sembilan Bab tentang Seni Matematika. Penggunaannya diilustrasikan dalam delapan belas soal, dengan dua hingga lima persamaan. Referensi pertama ke buku dengan judul ini bertanggal 179 M, tetapi sebagian dari referensi tersebut sudah ditulis setidaknya sejak sekitar 150 SM. Itu dikomentari oleh Liu Hui pada abad ke-3.

Metode di Eropa berasal dari catatan Isaac Newton. Pada 1670, dia menulis bahwa semua buku aljabar yang dikenalnya tidak memiliki pelajaran untuk memecahkan sistem persamaan simultan. Dalam catatannya, Newton selanjutnya mengembangkan materi mengenai masalah ini. Universitas Cambridge akhirnya menerbitkan catatan tersebut sebagai  Arithmetica Universalis pada tahun 1707; lama setelah Newton meninggalkan kehidupan akademisnya. Catatan itu ditiru secara luas, dan menjadi (apa yang sekarang disebut) eliminasi Gauss sebagai pelajaran standar dalam buku teks aljabar pada akhir abad ke-18. Carl Friedrich Gauss pada tahun 1810 merancang sebuah notasi untuk eliminasi simetris (symmetric elimination) yang diadopsi pada abad ke-19 oleh komputer tangan profesional untuk menyelesaikan persamaan kuadrat terkecil. Algoritma yang diajarkan di sekolah baru menggunakan nama Gauss pada sekitar tahun 1950-an, akibat kebingungan mengenai asal-usul dari algoritma ini.

Beberapa penulis menggunakan istilah eliminasi Gauss untuk merujuk hanya pada prosedur mengubah matriks sampai dalam bentuk eselon baris, dan menggunakan istilah eliminasi Gauss–Jordan untuk merujuk pada prosedur mengubah sampai ke bentuk eselon baris tereduksi. Nama ini digunakan sebagai variasi dari eliminasi Gauss yang dijelaskan oleh Wilhelm Jordan pada tahun 1888. Namun, variasi ini juga muncul dalam artikel oleh Clasen yang diterbitkan pada tahun yang sama. Jordan dan Clasen mungkin menemukan eliminasi Gauss–Jordan secara independen.

Aplikasi 
Secara historis, penerapan pertama dari operasi baris elementer adalah untuk menyelesaikan sistem persamaan linear. Berikut adalah beberapa aplikasi penting lainnya dari algoritma eliminasi Gauss.

Menghitung determinan 
Operasi-operasi baris dasar pada eliminasi Gauss memungkinkan perhitungan determinan matriks persegi. Hal ini terjadi karena operasi baris erat kaitannya dengan perkalian sebuah matriks dasar. Hal ini berefek pada:

 Menukar dua baris sama dengan mengalikan determinan matriks dengan  −1
 Mengalikan baris dengan skalar bukan nol mengalikan determinan dengan skalar yang sama
 Menambahkan kelipatan skalar dari baris lain ke suatu baris tidak mengubah nilai determinan.

Jika eliminasi Gauss diterapkan pada matriks persegi , matriks eselon baris  yang dihasilkan merupakan sebuah matriks segitiga atas. Determinan dari matriks ini selanjutnya dapat ditentukan dengan mengalikan semua elemen-elemen diagonal utamanya. Dari fakta ini, kita dapat menuliskan hubungan determinan matriks  dan matriks :Secara komputasi, metode ini cepat karena hanya memerlukan  operasi untuk sebuah matriks berukuran . Di sisi lain, rumus Leibniz untuk determinan memerlukan  operasi (untuk banyaknya penjumlahan diperlukan) sedangkan ekspansi Laplace memerlukan  operasi (banyaknya submatriks yang perlu dihitung, jika semua submatriks unik); menjadikannya [hampir] tidak berguna untuk .

Menemukan invers dari sebuah matriks 

Variasi dari eliminasi Gauss yang dikenal dengan eliminasi Gauss–Jordan dapat digunakan untuk menemukan invers dari matriks nonsingular. Misalkan  adalah matriks berukuran . Lalu bentuk matriks blok , dengan  adalah matriks identitas berukuran . Matriks  memiliki invers jika dan hanya jika serangkaian operasi baris dasar dapat dilakukan ke sisi kiri matriks blok sehingga  berubah menjadi matriks identitas . Pada kasus ini, sisi kanan dari matriks blok akan menjadi . Namun jika  tidak dapat diubah menjadi matriks identitas, maka  tidak memiliki invers.

Sebagai contoh, misalkan kita ingin menemukan invers dari matriks berikut:

 

Pertama, kita perlu membuat matriks blok dengan "menempelkan" matriks identitas ke sisi kanan  seperti berikut:

 

Dengan menerapkan eliminasi Gauss-Jordan, kita dapat mengecek bentuk eselon baris tereduksi dari matriks blok di atas adalah

 

Proses operasi baris dasar dapat dianggap sebagai sebuah perkalian dengan matriks dasar dari sebelah kiri. Jika  merupakan hasil perkalian semua matriks dasar yang dilakukan,  dapat ditunjukkan bahwaKarena , kita simpulkan .  Prosedur ini dapat diterapkan untuk mencari invers matriks dengan sebarang ukuran.

Menghitung rank dan menentukan basis 
Algoritma eliminasi Gauss juga dapat diterapkan untuk sebarang matriks  berukuran . Misalkan sebuah matriks berukuran  berhasil diubah menjadi bentuk eselon baris berikut

 

dengan simbol bintang menandakan entri yang nilainya sebarang, sedangkan  berupa entri tidak bernilai 0. Matriks eselon baris  mengandung banyak informasi mengenai matriks : rank dari  adalah 5, karena ada lima baris yang tidak semuanya bernilai nol di ; ruang vektor yang dibangun dari kolom-kolom  memiliki basis berisi kolom 1, 3, 4, 7 dan 9 (bersesuaian dengan kolom  di ), dan bintang-bintang menyatakan bagaimana kolom-kolom dari  dapat dinyatakan sebagai kombinasi linear dari kolom-kolom basis.

Cara ini juga berlaku untuk matriks berbentuk eselon baris tereduksi; yang merupakan kasus khusus dari bentuk eselon baris.

Lihat pula 
Fangcheng (matematika)

Referensi

Daftar pustaka 
 .
 .
 .
 .
 .
 .
 
 
 .
 .
 , Chapter 5 deals with Gaussian elimination.
 .
 

Algoritme
Aljabar linear