Metode Eliminasi Gauss, Proses Reduksi Baris Yang Diterapkan Secara Simultan – Eliminasi Gaussian adalah algoritma yang memungkinkan untuk mengubah sistem persamaan linier menjadi sistem yang setara (yaitu, sistem yang memiliki solusi yang sama dengan yang asli) dalam bentuk eselon baris. Operasi baris elementer dilakukan pada sistem sampai sistem dalam bentuk eselon baris. Kemudian, dapat dengan mudah diselesaikan dengan substitusi balik.
Metode Eliminasi Gauss, Proses Reduksi Baris Yang Diterapkan Secara Simultan
transitionmathproject – Suatu matriks dikatakan dalam bentuk eselon baris tereduksi jika selanjutnya semua koefisien terdepan sama dengan 1 (yang dapat dicapai dengan menggunakan operasi baris elementer tipe 2), dan pada setiap kolom yang mengandung koefisien terdepan, semua matriks entri lain dalam kolom itu adalah nol (yang dapat dicapai dengan menggunakan operasi baris elementer tipe 3).
Baca Juga : Mengenal Lebih Dalam Tentang Sistem Koefisien Persamaan Linear Matematika
Mencari invers suatu matriks
Sebuah varian dari eliminasi Gauss yang disebut eliminasi Gauss-Jordan dapat digunakan untuk menemukan invers suatu matriks, jika ada. Jika A adalah matriks bujur sangkar n × n, maka kita dapat menggunakan reduksi baris untuk menghitung matriks inversnya, jika ada.
Pertama, matriks identitas n × n diperbesar di sebelah kanan A, membentuk matriks blok n × 2n. Sekarang melalui penerapan operasi baris elementer, temukan bentuk eselon tereduksi dari matriks n × 2n ini. Matriks A dapat dibalik jika dan hanya jika blok kiri dapat direduksi menjadi matriks identitas I. dalam hal ini blok kanan dari matriks akhir adalah A−1.
Jika algoritma tidak dapat mereduksi blok kiri menjadi I, maka A tidak dapat dibalik. Seseorang dapat menganggap setiap operasi baris sebagai hasil kali kiri oleh matriks elementer. Dilambangkan dengan B hasil kali matriks-matriks elementer ini, di sebelah kiri kita tunjukkan bahwa BA = I, dan karena itu, B = A−1.
Di sebelah kanan, kami menyimpan catatan BI = B, yang kami tahu adalah kebalikan yang diinginkan. Prosedur untuk menemukan invers ini berfungsi untuk matriks persegi dengan ukuran berapa pun.
Komputasi peringkat dan basis
Algoritma eliminasi Gaussian dapat diterapkan pada sembarang matriks A m × n. Dengan cara ini, misalnya, beberapa matriks 6 × 9 dapat ditransformasikan menjadi matriks yang memiliki bentuk eselon baris seperti di mana bintang-bintang adalah entri sewenang-wenang, dan a, b, c, d, e adalah entri bukan nol.
Matriks eselon T ini berisi banyak informasi tentang A: peringkat A adalah 5, karena ada 5 baris bukan nol di T. ruang vektor yang direntang oleh kolom A memiliki basis yang terdiri dari kolomnya 1, 3, 4, 7 dan 9 (kolom dengan a, b, c, d, e di T), dan bintang-bintang menunjukkan bagaimana kolom lainnya dari A dapat ditulis sebagai kombinasi linier dari kolom basis. Ini adalah konsekuensi dari distribusi produk titik dalam ekspresi peta linier sebagai matriks.
Efisiensi komputasi
Jumlah operasi aritmatika yang diperlukan untuk melakukan reduksi baris adalah salah satu cara untuk mengukur efisiensi komputasi algoritma. Misalnya, untuk menyelesaikan sistem n persamaan untuk n yang tidak diketahui dengan melakukan operasi baris pada matriks sampai dalam bentuk eselon, dan kemudian menyelesaikan setiap yang tidak diketahui dalam urutan terbalik, membutuhkan n(n + 1)/2 pembagian, (2n3 + 3n2 5n)/6 perkalian, dan (2n3 + 3n2 5n)/6 pengurangan, untuk total sekitar 2n3/3 operasi.
Jadi ia memiliki kompleksitas aritmatika O(n3); lihat notasi O Besar. Kompleksitas aritmatika ini adalah ukuran yang baik dari waktu yang dibutuhkan untuk seluruh perhitungan ketika waktu untuk setiap operasi aritmatika kira-kira konstan. Ini adalah kasus ketika koefisien diwakili oleh angka floating-point atau ketika mereka termasuk dalam bidang terbatas.
Jika koefisiennya adalah bilangan bulat atau bilangan rasional yang direpresentasikan secara tepat, entri perantara dapat bertambah besar secara eksponensial, sehingga kompleksitas bitnya eksponensial. Namun, ada varian dari eliminasi Gauss, yang disebut algoritma Bareiss, yang menghindari pertumbuhan eksponensial dari entri perantara ini dan, dengan kompleksitas aritmatika yang sama dari O(n3), memiliki sedikit kompleksitas O(n5).
Algoritma ini dapat digunakan pada komputer untuk sistem dengan ribuan persamaan dan tidak diketahui. Namun, biaya menjadi penghalang untuk sistem dengan jutaan persamaan. Sistem besar ini umumnya diselesaikan dengan menggunakan metode iteratif. Ada metode khusus untuk sistem yang koefisiennya mengikuti pola yang teratur (lihat sistem persamaan linier).
Untuk menempatkan matriks n × n ke dalam bentuk eselon tereduksi dengan operasi baris, diperlukan operasi aritmatika n3, yang kira-kira 50% lebih banyak langkah komputasinya. Salah satu masalah yang mungkin adalah ketidakstabilan numerik, yang disebabkan oleh kemungkinan pembagian dengan angka yang sangat kecil. Jika misalnya, koefisien terdepan dari salah satu baris sangat dekat dengan nol, maka untuk mereduksi baris matriks, seseorang perlu membagi dengan angka itu.
Ini berarti bahwa kesalahan apa pun yang ada untuk angka yang mendekati nol akan diperkuat. Eliminasi Gaussian stabil secara numerik untuk matriks dominan diagonal atau matriks berdefinisi positif. Untuk matriks umum, eliminasi Gaussian biasanya dianggap stabil, ketika menggunakan pivot parsial, meskipun ada contoh matriks stabil yang tidak stabil.
Generalisasi
Eliminasi Gaussian dapat dilakukan pada bidang apa pun, bukan hanya bilangan real. Algoritma Buchberger adalah generalisasi dari eliminasi Gauss ke sistem persamaan polinomial. Generalisasi ini sangat bergantung pada gagasan tentang tatanan monomial.
Pilihan urutan pada variabel sudah tersirat dalam eliminasi Gaussian, yang bermanifestasi sebagai pilihan untuk bekerja dari kiri ke kanan saat memilih posisi pivot. Menghitung peringkat tensor orde lebih besar dari 2 adalah NP-hard. Oleh karena itu, jika P NP, tidak mungkin ada analog waktu polinomial dari eliminasi Gauss untuk tensor orde tinggi (matriks adalah representasi array tensor orde-2).
Kode semu
Seperti dijelaskan di atas, eliminasi Gauss mengubah matriks A berukuran m × n menjadi matriks dalam bentuk eselon baris. Dalam pseudocode berikut, A menunjukkan entri matriks A pada baris i dan kolom j dengan indeks mulai dari 1. Transformasi dilakukan di tempat, artinya matriks asli hilang karena akhirnya digantikan oleh bentuk eselon barisnya.
Algoritma ini sedikit berbeda dari yang dibahas sebelumnya, dengan memilih pivot dengan nilai absolut terbesar. Pivot parsial semacam itu mungkin diperlukan jika, di tempat pivot, entri matriks adalah nol. Bagaimanapun, memilih nilai absolut terbesar yang mungkin dari pivot meningkatkan stabilitas numerik algoritme, ketika floating point digunakan untuk mewakili angka. Setelah menyelesaikan prosedur ini, matriks akan berada dalam bentuk eselon baris dan sistem yang sesuai dapat diselesaikan dengan substitusi balik.
Eliminasi Gaussian dengan pivoting parsial
Perhatikan bahwa pada langkah 6 dari algoritma eliminasi Gaussian kita belum menentukan kriteria untuk memilih baris mana yang akan dipertukarkan dengan baris saat ini (jika ada lebih dari satu kemungkinan). Ketika kita mengimplementasikan algoritma eliminasi Gaussian di komputer, kriteria yang biasanya kita ikuti adalah memilih pertukaran yang memindahkan elemen terbesar (dalam nilai absolut) ke posisi pivot.
Ini dilakukan untuk meningkatkan stabilitas numerik algoritme: karena pada langkah 7 kita menghitung rasio , kita ingin sejauh mungkin dari nol ( untuk menghindari masalah pembagian dengan nol yang disebabkan oleh pembulatan numerik); sebagai konsekuensinya, kami memilih pertukaran baris untuk membuat nilai absolut sebesar mungkin. Metode pemilihan pivot ini disebut pivot parsial.
Baca Juga : Teori Relativitas Umum Einstein Menyingkap Kosmos
Eliminasi Gaussian dengan pivoting lengkap
Versi lain dari algoritma ini adalah yang disebut eliminasi Gaussian dengan pivoting lengkap, di mana nilai absolut dari pivot dimaksimalkan tidak hanya dengan menukar baris, tetapi juga dengan menukar kolom (yaitu, dengan mengubah urutan yang tidak diketahui).
Pada langkah 6 dari algoritma ini kami mencari semua kuadran dari matriks koefisien di bawah dan di sebelah kanan posisi pivot untuk elemen yang memiliki nilai absolut terbesar dan kemudian kami memindahkan elemen tersebut ke posisi pivot dengan baris dan kolom yang saling bertukar .