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

Lihat pula: Matriks 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:

1. Menukar posisi dua baris.
2. Mengalikan suatu baris dengan skalar bukan nol .
3. 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

Artikel utama: 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:

Langkah berikutnya adalah menghilangkan variabel dengan melakukan operasi . Hal ini menghasilkan matriks berikut

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.

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, seperti

menjadi

Perlu 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

Lihat pula: Matriks terbalikkan

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 bahwa

Karena , 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 a, b, c, d, e 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 a, b, c, d, e 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

1. (Farebrother 1988), p. 12.
2. J. B. Fraleigh and R. A. Beauregard, Linear Algebra. Addison-Wesley Publishing Company, 1995, Chapter 10.
3. (Golub & Van Loan 1996), §3.4.6.
4. (Calinger 1999), pp. 234–236
5. Timothy Gowers; June Barrow-Green; Imre Leader (8 September 2008). The Princeton Companion to Mathematics. Princeton University Press. hlm. 607. ISBN 978-0-691-11880-2. 
6. (Grcar 2011a), pp. 169-172
7. (Grcar 2011b), pp. 783-785
8. (Lauritzen), p. 3
9. (Grcar 2011b), p. 789
10. Althoen, Steven C.; McLaughlin, Renate (1987), "Gauss–Jordan reduction: a brief history", The American Mathematical Monthly, Mathematical Association of America, 94 (2): 130–142, doi:10.2307/2322413, ISSN 0002-9890, JSTOR 2322413 

Daftar pustaka

• Atkinson, Kendall A. (1989), An Introduction to Numerical Analysis (edisi ke-2nd), New York: John Wiley & Sons, ISBN 978-0-471-50023-0 .
• Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Trivedi, Kishor S. (2006), Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (edisi ke-2nd), Wiley-Interscience, ISBN 978-0-471-79156-0 .
• Calinger, Ronald (1999), A Contextual History of Mathematics, Prentice Hall, ISBN 978-0-02-318285-3 .
• Farebrother, R.W. (1988), Linear Least Squares Computations, STATISTICS: Textbooks and Monographs, Marcel Dekker, ISBN 978-0-8247-7661-9 .
• Lauritzen, Niels, Undergraduate Convexity: From Fourier and Motzkin to Kuhn and Tucker .
• Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (edisi ke-3rd), Johns Hopkins, ISBN 978-0-8018-5414-9 .
• Grcar, Joseph F. (2011a), "How ordinary elimination became Gaussian elimination", Historia Mathematica, 38 (2): 163–218, arXiv:0907.2397 , doi:10.1016/j.hm.2010.06.003 
• Grcar, Joseph F. (2011b), "Mathematicians of Gaussian elimination" (PDF), Notices of the American Mathematical Society, 58 (6): 782–792 
• Higham, Nicholas (2002), Accuracy and Stability of Numerical Algorithms (edisi ke-2nd), SIAM, ISBN 978-0-89871-521-7 .
• Katz, Victor J. (2004), A History of Mathematics, Brief Version, Addison-Wesley, ISBN 978-0-321-16193-2 .
• Kaw, Autar; Kalu, Egwu (2010). "Numerical Methods with Applications" (edisi ke-1st). [1].  Hapus pranala luar di parameter |publisher= (bantuan); Tidak memiliki atau membutuhkan |url= (bantuan), Chapter 5 deals with Gaussian elimination.
• Lipson, Marc; Lipschutz, Seymour (2001), Schaum's outline of theory and problems of linear algebra, New York: McGraw-Hill, hlm. 69–80, ISBN 978-0-07-136200-9 .
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.2", Numerical Recipes: The Art of Scientific Computing (edisi ke-3rd), New York: Cambridge University Press, ISBN 978-0-521-88068-8