Eliminasi gauss

Eliminasi gauss adolah algoritme nan digunoan untuak manyalasaian sistem pasamoan linear. Metode iko diambiak dari matematikawan Carl Friedrich Gauss (1777–1855), walaupun metode iko alah dikana dek matematikawan Cino samanjak taun 179 M.

Ado tigo jinih operasi nan dapek dilakukan dalam metode iko:

1. Mengganti urutan duo barih
2. Mangalian barih jo angko nan bukan nol
3. Manambah suatu barih jo barih nan lainnyo

Jo caro iko, matriks dapek diubah manjadi matriks sagitigo ateh.

Proses reduksi barih manggunokan operasi barih dasa, nan dapek dibagi manjadi duo bagian. Bagian nan partamo (kadang disabuik eliminasi maju) mareduksi sistem nan diagiah manjadi bantuak eselon barih, nan baguno supayo urang dapek mangatahui apo iyo indak ado solusi, solusi unik, atau banyak solusi tak inggo. Bagian kaduo (acok disabuik substitusi baliak) taruih manggunokan operasi barih hinggo solusi nan ditamui; jo kato lain, iko manampekkan matriks ka dalam bantuak eselon barih tareduksi .

Sudut pandang lain, nan baguno untuak maanalisis algoritma, adolah basonyo reduksi barih maasiakan dekomposisi matriks dari matriks nan asli. Operasi barih elementer dapek dicaliak sabagai pakalian di sabalah kida dari matriks asli jo matriks elementer. Atau, urutan operasi dasa nan mangurangi satu barih dapek dicaliak sabagai pakalian jo matriks Frobenius. Kamudian bagian partamo dari algoritma maetong sabuah LU penguraian, sadangkan bagian kaduo manulih matriks asli sabagai hasil pakalian dari matriks nan dapek dibaliak nan ditantuan sacaro unik jo matriks eselon barih nan tareduksi nan ditantuan sacaro unik.

Operasi barih

Ado tigo jinih operasi barih dasa nan dapek dilakukan pado barih matriks:

1. Tuka posisi duo barih.
2. Mangalikan barih jo bukan nol skalar.
3. Tambahkan ka satu barih babarapo skalar dari nan lain.

Jiko matriks dikaitkan jo sistem pasamoan linear, mako operasi iko indak maubah kumpulan solusi. Dek karano itu, jiko tujuan sasaurang adolah untuak manyalasaian sistem pasamoan linier, mako manggunokan operasi barih iko dapek mambuek masalah manjadi labiah mudah.

Bantuak eselon

Untuak satiok barih dalam matriks, jiko barih tasabuik indak hanyo tadiri dari angko nol sajo, mako entri indak nol paliang kida disabuik koefisien awal (atau poros) dari barih itu. Jadi jiko duo koefisien utamo talatak di kolom nan samo, mako operasi barih Tipe 3 dapek digunoan untuak mambuek salah satu koefisien tasabuik manjadi nol. Kamudian jo manggunokan operasi patukaran barih, sasaurang taruih dapek mauruikkan barih sahinggo untuak satiok barih nan bukan nol, koefisien paliang muko ado di sabalah suok koefisien nan paliang muko dari barih di ateh. Mako matriks dikatokan barado dalam bantuak eselon barih. Jadi bagian kida bawah matriks hanyo baisi angko nol, jo sadoalah barih nol barado di bawah barih bukan nol. Kato "eselon" digunokan di siko dek sacaro kasa urang dapek mambayangan barih nan diagiah paringkek manuruik ukurannyo, sarato nan paliang gadang di ateh jo nan paliang ketek di bawah.

Misalnyo, matriks barikuik dalam bantuak eselon barih, nan koefisien utamonyo ditandoi jo rono sirah:

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

dalam bantuak eselon karano barih nol di bawah, jo koefisien nan paliang muko dari barih kaduo (di kolom katigo), adolah di sabalah suok koefisien nan paliang muko dari barih partamo (di kolom kaduo).

Suatu matriks dikatoan dalam bantuak eselon barih nan tareduksi jiko salanjuiknyo sadoalah koefisien utamo samo jo 1 (nan dapek dicapai jo manggunokan operasi barih dasa tipe 2), jo di satiok kolom nan baisi koefisien utamo, sadoalah entri lain di kolom itu adolah nol (nan dapek dicapai jo caro manggunokan operasi barih dasa tipe 3).