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 $n\times 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 .

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:

${\begin{bmatrix}0&\color {red}{\mathbf {2} }&1&-1\\0&0&\color {red}{\mathbf {3} }&1\\0&0&0&0\end{bmatrix}}.$

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:

${\begin{bmatrix}0&\color {red}{\mathbf {1} }&0&-{\dfrac {2}{3}}\\0&0&\color {red}{\mathbf {1} }&{\dfrac {1}{3}}\\0&0&0&0\end{bmatrix}}.$

Contoh algoritma

Misalkan kita ingin menemukan dan mendeskripsikan himpunan solusi ke sistem persamaan linear berikut:

${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\qquad (L_{1})\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\qquad (L_{2})\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\qquad (L_{3})\end{alignedat}}$

Persamaan tersebut dapat dinyatakan dalam bentuk matriks koefisien gabungan:

$\left[{\begin{array}{rrr|r}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]$

Prosedur operasi baris dasar dapat diringkas sebagai berikut: hilangkan variabel $x$ dari semua persamaan di bawah $L_{1}$, lalu hilangkan variabel $y$ dari semua persamaan di bawah ini $L_{2}$. 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 $x$ dihilangkan dari $L_{2}$ dengan menambahkan ${\tfrac {3}{2}}L_{1}$ ke $L_{2}$. Intepretasi lain dari operasi ini adalah mengganti $L_{2}$ dengan ${\tfrac {3}{2}}L_{1}+L_{2}$, yang dilambangkan dengan ${\tfrac {3}{2}}L_{1}+L_{2}\to L_{2}$. Sedangkan $x$ dihilangkan dari $L_{3}$ dengan menambahkan $L_{1}$ ke $L_{3}$. Langkah ini akan menghasilkan matriks koefisien dan sistem persamaan berikut:

Matriks koefisien gabungan	Sistem persamaan
$\left[{\begin{array}{rrr|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&2&1&5\end{array}}\right]$	${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&2y&{}+{}&z&{}={}&5&\end{alignedat}}$

Langkah berikutnya adalah menghilangkan variabel $y$ dengan melakukan operasi $L_{3}+-4L_{2}\to L_{3}$. Hal ini menghasilkan matriks berikut

Matriks koefisien gabungan	Sistem persamaan
$\left[{\begin{array}{rrr|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&-1&1\end{array}}\right]$	${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&&&-z&{}={}&1&\end{alignedat}}$

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 $z=-1$. Lalu dengan mensubtitusi nilai $z$ ke persamaan ${\tfrac {1}{2}}y+{\tfrac {1}{2}}z=1$ akan didapatkan $y=3$. Melanjutkan proses, didapatkan $x=2$. 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 baris	Hasil matriks koefisien gabungan	Sistem persamaan
${\begin{aligned}L_{2}+{\tfrac {1}{2}}L_{3}&\to L_{2}\\L_{1}-L_{3}&\to L_{1}\end{aligned}}$	$\left[{\begin{array}{rrr|r}2&1&0&7\\0&{\frac {1}{2}}&0&{\frac {3}{2}}\\0&0&-1&1\end{array}}\right]$	${\begin{alignedat}{4}2x&{}+{}&y&&&{}={}7&\\&&{\tfrac {1}{2}}y&&&{}={}{\tfrac {3}{2}}&\\&&&{}-{}&z&{}={}1&\end{alignedat}}$
${\begin{aligned}2L_{2}&\to L_{2}\\-L_{3}&\to L_{3}\end{aligned}}$	$\left[{\begin{array}{rrr|r}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}}\right]$	${\begin{alignedat}{4}2x&{}+{}&y&\quad &&{}={}&7&\\&&y&\quad &&{}={}&3&\\&&&\quad &z&{}={}&-1&\end{alignedat}}$
${\begin{aligned}L_{1}-L_{2}&\to L_{1}\\{\tfrac {1}{2}}L_{1}&\to L_{1}\end{aligned}}$	$\left[{\begin{array}{rrr|r}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]$	${\begin{alignedat}{4}x&\quad &&\quad &&{}={}&2&\\&\quad &y&\quad &&{}={}&3&\\&\quad &&\quad &z&{}={}&-1&\end{alignedat}}$

Sejarah

Metode eliminasi Gaussian muncul - meskipun tanpa 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 darinya ditulis 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 persamaan simultan, yang kemudian diberikan Newton. Universitas Cambridge akhirnya menerbitkan catatan tersebut sebagai Arithmetica Universalis pada tahun 1707 lama setelah Newton meninggalkan kehidupan akademis. Catatan itu ditiru secara luas, yang menjadikan (apa yang sekarang disebut) eliminasi Gaussian sebagai pelajaran standar dalam buku teks aljabar pada akhir abad ke-18. Carl Friedrich Gauss pada tahun 1810 merancang sebuah notasi untuk eliminasi simetris yang diadopsi pada abad ke-19 oleh komputer tangan profesional untuk menyelesaikan persamaan normal leas. The algorithm that is taught in high school was named for Gauss only in the 1950s as a result of confusion over the history of the subject.

Beberapa penulis menggunakan istilah eliminasi Gaussian untuk merujuk hanya pada prosedur sampai matriks dalam bentuk eselon, dan menggunakan istilah eliminasi Gauss – Jordan untuk merujuk pada prosedur yang. Nama ini digunakan karena merupakan variasi dari eliminasi Gaussian seperti yang dijelaskan oleh Wilhelm Jordan pada tahun 1888. Namun, metode tersebut 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, aplikasi pertama dari metode reduksi baris adalah untuk menyelesaikan sistem persamaan linier. Berikut adalah beberapa aplikasi penting lainnya dari algoritme.

Menghitung determinan

Untuk menjelaskan bagaimana eliminasi Gaussian memungkinkan perhitungan determinan matriks persegi, kita harus mengingat bagaimana operasi baris dasar mengubah determinan:

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

Jika eliminasi Gauss diterapkan pada matriks persegi, A menghasilkan matriks eselon baris B, biarkan d menjadi produk skalar yang determinannya telah dikalikan, menggunakan aturan di atas. Maka determinan dari A adalah hasil bagi oleh d dari hasil kali elemen diagonal dari B:

$\det(A)={\frac {\prod \operatorname {diag} (B)}{d}}.$

Lihat pula

• Fangcheng (matematika)

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].  , 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