Eliminasi Gauss

Eliminasi Gauss adalah algoritme yang digunakan untuk menyelesaikan sistem persamaan linear. Metode ini dinamai dari matematikawan Carl Friedrich Gauss (1777–1855), walaupun metode ini sudah dikenal oleh matematikawan Tionghoa semenjak tahun 179 M.

Terdapat tiga jenis operasi yang dapat dilakukan dalam metode ini:

1. Mengganti urutan dua baris
2. Mengalikan baris dengan angka yang bukan nol
3. Menambah suatu baris dengan baris yang lainnya

Dengan cara ini, matriks dapat diubah menjadi matriks segitiga atas.

Definisi dan contoh algoritma

Proses reduksi baris menggunakan operasi baris dasar, dan dapat dibagi menjadi dua bagian. Bagian pertama (kadang disebut eliminasi maju) mereduksi sistem yang diberikan menjadi bentuk eselon baris , dari mana seseorang dapat mengetahui apakah tidak ada solusi, solusi unik, atau banyak solusi tak hingga. Bagian kedua (terkadang disebut substitusi kembali) terus menggunakan operasi baris hingga solusi ditemukan; dengan kata lain, ini menempatkan matriks ke dalam bentuk eselon baris tereduksi .

Sudut pandang lain, yang ternyata sangat berguna untuk menganalisis algoritme, adalah bahwa reduksi baris menghasilkan dekomposisi matriks dari matriks asli. Operasi baris elementer dapat dilihat sebagai perkalian di sebelah kiri dari matriks asli dengan matriks elementer. Atau, urutan operasi dasar yang mengurangi satu baris dapat dilihat sebagai perkalian dengan matriks Frobenius. Kemudian bagian pertama dari algoritma menghitung sebuah LU penguraian, sedangkan bagian kedua menulis matriks asli sebagai hasil perkalian dari matriks yang dapat dibalik yang ditentukan secara unik dan matriks eselon baris tereduksi yang ditentukan secara unik.

Operasi baris

Lihat pula: Matriks dasar

Ada tiga jenis operasi baris dasar yang dapat dilakukan pada baris matriks:

1. Tukar posisi dua baris.
2. Mengalikan baris dengan bukan nol skalar.
3. Tambahkan ke satu baris beberapa skalar dari yang lain.

Jika matriks dikaitkan dengan sistem persamaan linear, maka operasi ini tidak mengubah kumpulan solusi. Oleh karena itu, jika tujuan seseorang adalah untuk menyelesaikan sistem persamaan linier, maka menggunakan operasi baris ini dapat membuat masalah menjadi lebih mudah.

Bentuk eselon

Artikel utama: Bentuk eselon baris

Untuk setiap baris dalam matriks, jika baris tersebut tidak hanya terdiri dari angka nol, maka entri bukan nol paling kiri disebut koefisien awal (atau poros ) dari baris itu. Jadi jika dua koefisien utama berada di kolom yang sama, maka operasi baris Tipe 3 dapat digunakan untuk membuat salah satu koefisien tersebut menjadi nol. Kemudian dengan menggunakan operasi pertukaran baris, seseorang selalu dapat mengurutkan baris sehingga untuk setiap baris bukan nol, koefisien terdepan ada di sebelah kanan koefisien terdepan dari baris di atas. Jika demikian, maka matriks dikatakan berada dalam bentuk eselon baris. Jadi bagian kiri bawah matriks hanya berisi angka nol, dan semua baris nol berada di bawah baris bukan nol. Kata "eselon" digunakan di sini karena secara kasar orang dapat membayangkan baris diberi peringkat berdasarkan ukurannya, dengan yang terbesar di atas dan yang terkecil di bawah.

Misalnya, matriks berikut dalam bentuk eselon baris, dan 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}}.$

Ini dalam bentuk eselon karena baris nol di bawah, dan koefisien terdepan dari baris kedua (di kolom ketiga), adalah di sebelah kanan koefisien terdepan dari baris pertama (di kolom kedua).

Suatu matriks dikatakan dalam bentuk eselon baris tereduksi jika selanjutnya semua koefisien utama sama dengan 1 (yang dapat dicapai dengan menggunakan operasi baris dasar tipe 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 tipe 3).

Contoh algoritma

Misalkan tujuannya adalah untuk 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}}$

Tabel di bawah ini adalah proses reduksi baris yang diterapkan secara bersamaan ke sistem persamaan dan matriks besar yang terkait. Dalam praktiknya, seseorang biasanya tidak berurusan dengan sistem dalam hal persamaan, melainkan menggunakan matriks yang diperbesar, mana yang lebih cocok untuk manipulasi komputer. Prosedur pengurangan baris dapat diringkas sebagai berikut: hilangkan x dari semua persamaan di bawah L₁, lalu hilangkan y dari semua persamaan di bawah ini L₂. Ini akan membuat sistem menjadi bentuk segitiga. Kemudian, dengan menggunakan substitusi balik, setiap ketidaktahuan dapat diselesaikan.

Sistem persamaan	Operasi baris	Matriks yang diperbesar
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\end{alignedat}}$		$\left[{\begin{array}{rrr|r}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&2y&{}+{}&z&{}={}&5&\end{alignedat}}$	${\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2}\\L_{3}+L_{1}&\to L_{3}\end{aligned}}$	$\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&\\&&&&-z&{}={}&1&\end{alignedat}}$	$L_{3}+-4L_{2}\to L_{3}$	$\left[{\begin{array}{rrr|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&-1&1\end{array}}\right]$
Matriks sekarang dalam bentuk eselon (juga disebut bentuk segitiga)
${\begin{alignedat}{4}2x&{}+{}&y&&&{}={}7&\\&&{\tfrac {1}{2}}y&&&{}={}{\tfrac {3}{2}}&\\&&&{}-{}&z&{}={}1&\end{alignedat}}$	${\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&\quad &&{}={}&7&\\&&y&\quad &&{}={}&3&\\&&&\quad &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}x&\quad &&\quad &&{}={}&2&\\&\quad &y&\quad &&{}={}&3&\\&\quad &&\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]$

Kolom kedua menjelaskan operasi baris mana yang baru saja dilakukan. Jadi untuk langkah pertama, x dihilangkan dari L₂ dengan menambahkan 32 L ₁ hingga L₂. Berikutnya, x dihilangkan dari L ₃ dengan menambahkan L₁ ke L₃. Operasi baris ini diberi label pada tabel sebagai

${\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2},\\L_{3}+L_{1}&\to L_{3}.\end{aligned}}$

Setelah y juga dihilangkan dari baris ketiga, hasilnya adalah sistem persamaan linier dalam bentuk segitiga, dan bagian pertama dari algoritme telah selesai. Dari sudut pandang komputasi, lebih cepat untuk menyelesaikan variabel dalam urutan terbalik, sebuah proses yang dikenal sebagai substitusi balik. Satu melihat solusinya adalah z = −1, y = 3, dan x = 2. Jadi ada solusi unik untuk sistem persamaan asli.

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

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}}.$

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