Eliminasi Gauss: Metode untuk Menyelesaikan Sistem Persamaan

Eliminasi Gauss adalah salah satu algoritme paling mendasar dalam aljabar linear untuk menyelesaikan sistem persamaan linear. Dinamai menurut matematikawan Jerman Carl Friedrich Gauss, metode ini mengubah suatu sistem persamaan menjadi bentuk yang setara namun lebih sederhana dengan melakukan serangkaian operasi pada representasi matriksnya.

Artikel ini akan membahas cara kerja eliminasi Gauss, implementasinya di Python, serta aplikasinya dalam ilmu data dan komputasi numerik. Dengan memahami algoritme ini, kita akan memperoleh wawasan tentang teknik fundamental yang mendasari banyak metode komputasi yang digunakan dalam analisis data.

Apa Itu Eliminasi Gauss?

Eliminasi Gauss adalah algoritme untuk menyelesaikan sistem persamaan linear dengan secara sistematis mengubah matriks augmentasi dari sistem tersebut menjadi bentuk eselon baris (REF). Transformasi ini mempertahankan himpunan solusi sekaligus memudahkan pencarian nilai variabel.

Sebuah matriks berada dalam bentuk eselon baris ketika:

• Semua baris yang seluruh elemennya nol berada di bagian bawah matriks
• Entri utama (elemen tak nol pertama) dari setiap baris tak nol berada di sebelah kanan entri utama baris di atasnya
• Semua elemen di bawah entri utama bernilai nol

Untuk mencapai bentuk eselon baris, kita menggunakan tiga jenis operasi baris elementer:

• Pertukaran baris: Menukar dua baris
• Penskalaan baris: Mengalikan semua elemen dalam satu baris dengan konstanta tak nol
• Penjumlahan baris: Mengganti satu baris dengan hasil penjumlahan baris tersebut dan kelipatan dari baris lain

Selain itu, penting untuk membedakan antara eliminasi Gauss dan eliminasi Gauss–Jordan:

• Eliminasi Gauss mengubah matriks ke bentuk eselon baris, yang memerlukan substitusi balik untuk menemukan nilai variabel
• Eliminasi Gauss–Jordan melanjutkan proses hingga bentuk eselon baris tereduksi (RREF), di mana semua entri utama bernilai 1 dan semua entri lain pada kolom entri utama tersebut bernilai 0

Walau eliminasi Gauss–Jordan memberikan solusi yang lebih langsung, eliminasi Gauss umumnya lebih efisien untuk sistem berukuran besar, terutama jika digabungkan dengan substitusi balik dan teknik seperti dekomposisi LU.

Uraian Langkah demi Langkah Algoritme Eliminasi Gauss

Mari menelusuri proses eliminasi Gauss menggunakan contoh sederhana. Pertimbangkan sistem persamaan linear berikut:

Sistem persamaan linear. Gambar oleh Penulis.

Langkah 1: Buat matriks augmentasi

Pertama, kita merepresentasikan sistem sebagai matriks augmentasi, yang menggabungkan matriks koefisien dengan konstanta:

Matriks augmentasi. Gambar oleh Penulis.

Langkah 2: Eliminasi maju

Sekarang kita akan melakukan operasi baris elementer untuk mengubah matriks menjadi bentuk eselon baris.

Jadikan elemen pertama pada kolom pertama sebagai pivot dan nolkan semua elemen di bawahnya:

• Tambahkan 3/2 × Baris 1 ke Baris 2:

Tambahkan 3/2 × Baris 1 ke Baris 2. Gambar oleh Penulis.

• Tambahkan Baris 1 ke Baris 3:

Tambahkan Baris 1 ke Baris 3. Gambar oleh Penulis.

Pindah ke kolom kedua dan nolkan semua elemen di bawah pivot:

• Kalikan Baris 2 dengan 2 agar pivot bernilai 1:

Kalikan Baris 2 dengan 2. Gambar oleh Penulis.

• Kurangkan 2 × Baris 2 dari Baris 3:

Kurangkan 2 × Baris 2. Gambar oleh Penulis.

Jadikan pivot pada baris ketiga bernilai positif:

• Kalikan Baris 3 dengan -1:

Kalikan Baris 3 dengan -1. Gambar oleh Penulis.

Matriks sekarang berada dalam bentuk eselon baris.

Langkah 3: Substitusi balik

Sekarang kita dapat menemukan nilai variabel melalui substitusi balik:

Dari Baris 3: 

          z = -1

Dari Baris 2: 

          y + z = 2,

          sehingga y + (-1) = 2,

          yang menghasilkan y = 3

Dari Baris 1: 

          2x + y - z = 8,

          sehingga 2x + 3 - (-1) = 8,

          yang menghasilkan 2x = 4,

          sehingga x = 2

Dengan demikian, solusinya adalah x = 2, y = 3, z = -1.

Walaupun kita menerapkan eliminasi Gauss pada contoh ini, langkah-langkahnya tetap sama untuk sistem persamaan linear lainnya.

Implementasi Eliminasi Gauss di Python

Meskipun kita bisa menulis algoritmenya menggunakan Python dasar, operasi tervektorisasi NumPy membuat implementasi menjadi lebih ringkas dan jauh lebih cepat. 

Untuk tujuan edukasi, memahami algoritme dasarnya sangat berharga, namun untuk penggunaan produksi, disarankan memanfaatkan pustaka yang telah dioptimalkan. Setelah memahami algoritme dasarnya pada bagian sebelumnya, sekarang kita akan membahas implementasi menggunakan pustaka yang dioptimalkan di Python.

Implementasi berbasis NumPy

NumPy menyediakan fungsi numpy.linalg.solve() yang mengimplementasikan solusi yang sangat dioptimalkan untuk sistem persamaan linear:

import numpy as np

# Define the coefficient matrix A and constant vector b
A = np.array([[2, 1, -1],
             [-3, -1, 2],
             [-2, 1, 2]], dtype=float)
b = np.array([8, -11, -3], dtype=float)

# Solve the system Ax = b
x = np.linalg.solve(A, b)

print("Solution:", x)Didukung oleh

Pada kode di atas, kita mendefinisikan matriks koefisien A beserta vektor konstanta b, sama seperti matriks augmentasi yang kita buat pada langkah 1 contoh eliminasi Gauss di atas. 

Kita menggunakan fungsi numpy.linalg.solve() untuk memperoleh solusi dan mencetak keluarannya seperti terlihat di bawah ini:

Solusi menggunakan implementasi kode. Gambar oleh Penulis.

Implementasi ini menggunakan LAPACK di balik layar, yang menerapkan dekomposisi LU (varian dari eliminasi Gauss) yang dioptimalkan untuk stabilitas numerik dan kinerja.

Menangani kasus khusus

Saat mengimplementasikan eliminasi Gauss, Anda akan menemui beberapa kasus khusus yang memerlukan penanganan cermat:

• Matriks singular: Jika determinan matriks koefisien Anda nol atau sangat mendekati nol, sistem tersebut tidak memiliki solusi atau memiliki tak hingga banyak solusi. Fungsi linalg.solve() dari NumPy akan memunculkan LinAlgError dalam kasus ini.

• Stabilitas numerik: Dengan aritmetika floating-point, kesalahan pembulatan dapat terakumulasi dan menghasilkan hasil yang tidak akurat. Pivot parsial, yaitu memilih elemen terbesar dalam suatu kolom sebagai pivot, membantu mengurangi masalah ini.

• Sistem overdetermined atau underdetermined: Ketika jumlah persamaan tidak sama dengan jumlah variabel, Anda dapat menggunakan numpy.linalg.lstsq() sebagai gantinya, yang mencari solusi kuadrat terkecil (least squares).

Untuk sistem besar dengan banyak nol, pemecah matriks jarang (sparse) dari SciPy bisa berkali-kali lipat lebih cepat dibanding pemecah densitas (dense):

from scipy.sparse import csr_matrix
from scipy.sparse.linalg import spsolve

# For large sparse matrices
A_sparse = csr_matrix(A)
x = spsolve(A_sparse, b)Didukung oleh

Meskipun memahami mekanisme algoritme bernilai penting, dalam praktiknya, memanfaatkan implementasi NumPy dan SciPy yang dioptimalkan memungkinkan Anda menyelesaikan sistem linear secara efisien dan andal tanpa membuat ulang dari awal.

Di Mana Eliminasi Gauss Digunakan

Eliminasi Gauss jauh melampaui matematika teoretis dan memiliki banyak aplikasi praktis di berbagai bidang sains, teknik, dan analisis data. 

Berikut adalah beberapa aplikasi dunia nyata terpenting dari algoritme fundamental ini:

• Regresi linear: Dalam ilmu data, eliminasi Gauss digunakan untuk menyelesaikan persamaan normal yang muncul saat mencari parameter best-fit dalam model regresi linear. Ini memungkinkan analis membuat prediksi berdasarkan data historis.
• Analisis jaringan: Insinyur menggunakan eliminasi Gauss untuk menyelesaikan arus atau tegangan yang tidak diketahui dalam rangkaian listrik dengan menerapkan hukum Kirchhoff, yang menghasilkan sistem persamaan linear yang harus diselesaikan secara simultan.
• Invers matriks: Eliminasi Gauss menjadi dasar untuk menghitung invers matriks, yang penting dalam transformasi, analisis statistik, dan penyelesaian masalah matematika kompleks dalam algoritme pembelajaran mesin.
• Integrasi numerik: Saat mengimplementasikan metode numerik tingkat lanjut seperti Euler implisit atau skema integrasi Runge–Kutta, eliminasi Gauss digunakan untuk menyelesaikan sistem persamaan yang dihasilkan, memastikan stabilitas dalam simulasi sistem dinamis.

Dengan memahami aplikasi-aplikasi ini, kita dapat melihat bagaimana satu teknik matematika dapat menjadi tulang punggung bagi banyak alat yang digunakan setiap hari oleh data scientist, insinyur, dan peneliti.

Kesimpulan

Artikel ini membahas algoritme fundamental eliminasi Gauss untuk menyelesaikan sistem persamaan linear dengan mengubah matriks menjadi bentuk eselon baris. Kita juga mempelajari cara mengimplementasikan teknik ini di Python menggunakan fungsi-fungsi NumPy yang dioptimalkan, serta memahami aplikasi praktisnya dalam regresi linear, analisis jaringan, invers matriks, dan metode numerik. 

Untuk memperdalam pengetahuan Anda tentang aljabar linear dan penerapannya dalam ilmu data, pertimbangkan untuk mengikuti kursus Aljabar Linear kami, tempat Anda akan mempelajari konsep yang lebih lanjut dan implementasi dari teknik-teknik fundamental ini.