Metode Eliminasi Gauss

Eliminasi Gauss adalah suatu cara mengoperasikan nilai-nilai di dalam matriks sehingga menjadi matriks yang lebih sederhana. Caranya adalah dengan melakukan operasi baris sehingga matriks tersebut menjadi matriks yang eselon-baris. Ini dapat digunakan sebagai salah satu metode penyelesaian persamaan linear dengan menggunakan matriks. Caranya dengan mengubah persamaan linear tersebut ke dalam matriks teraugmentasi dan mengoperasikannya. Setelah menjadi matriks Eselon-baris, lakukan substitusi balik untuk mendapatkan nilai dari variabel-variabel tersebut.

Metode ini berangkat dari kenyataan bahwa bila matriks A berbentuk segitiga atas (menggunakan Operasi Baris Elementer) seperti system persamaan berikut ini:

Maka solusinya dapat dihitung dengan teknik penyulingan mundur (backward substitution):

... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...

Sekali

diketahui, maka nilai

dapat dihitung dengan :

Sekali diketahui, maka nilai

dapat dihitung dengan:

Kondisi

sangat penting. Sebab bila

, persamaan diatas menjerjakan pembagian dengan nol. Apabila kondisi tersebut tidak dipenuhi, maka SPL tidak mempunyai jawaban.

Contoh:

x + y + 2y = 9

2x + 4y - 3z = 1

3x + 6y - 5z = 0

kalikan baris (i) dengan (-2), lalu tambahkan ke baris (ii)

kalikan baris (i) dengan (-3), lalu tambahkan ke baris (iii)

kalikan baris (ii) dengan (1/2)

kalikan baris (ii) dengan (-3), lalu tambahkan ke baris (iii)

kalikan baris (iii) dengan (-2)

Solusi system diperoleh dengan teknik penyulihan mundur sebagai berikut:

Diperoleh penyelesaian x = 1, y = 2, z =

Melakukan pertukaran baris untuk menghindari pivot yang bernilai nol adalah cara pivoting yang sederhana (simple pivoting). Masalahinidapatjugatimbulbilaelemen pivot sangatdekatkenol, karena jika elemen pivot sangat kecil dibandingkan terhadap elemen lainnya, maka gala tpembulatan dapat muncul.

Ada duamacamtata-ancang pivoting, yaitu:

a. Pivoting sebagian (partial pivoting)

Padatata-ancang pivoting sebagian, pivot dipilihdarisemuaelemenpadakolom p yang mempunyainilaimutlakterbesar,

Lalu Lalu pertukarkan baris k denganbariske p. Misalkan setelah operasi baris pertama diperoleh matriksnya seperti yang digambarkan pada matriks di bawah ini. Untuk operasi baris kedua, carilah elemen x pada baris kedua, dimulai dari baris ke-2 sampai baris ke-4, yang nilai mutlaknya terbesar, lalu pertukarkan barisnya dengan baris ke-2

Perhatikanlah bahwa teknik pivoting sebagian juga sekaligus menghindari pemilihan pivot = 0 (sebagaimana dalam simple pivoting) karena 0 tidak akan pernah menjadi elemen dengan nilai mutlak terbesar, kecuali jika seluruh elemen di kolom yang diacu adalah 0. Apabila setelah melakukan pivoting sebagian ternyata elemen pivot = 0, itu berarti system persamaan linier tidak dapat diselesaikan (singular system).

b. Pivoting Lengkap (complete pivoting)

Jika disamping baris, kolom juga dikutkan dalam pencarian elementer besar dan kemudian dipertukarkan, maka tata-ancang ini disebut pivoting lengkap. Pivoting lengkap jarang dipakai dalam program sederhana karena pertukaran kolom mengubahu rutans uku x dan akibatnya menambah kerumitan program secara berarti.Contoh:

Dengan menggunkan 4 angka bena, selesaikan system berikut dengan metode eliminasi Gauss:

a. Tanpa tata-ancang pivoting sebagian (Gauss naif)

b. Dengan tata-ancang pivoting sebagian (Gauss yang dimodifikasi)

Penyelesaian

Tanpa tata-ancang pivoting sebagian

Operasi baris pertama (0.0003 sebagai pivot)

Jadi,

Solusinya diperoleh dengan teknik penyulihan mundur:

(jauh dari solusi sejati)

Jadi, x = (3.333, 1.001). Solusi ini sangat jauh berbeda dengan solusi sejatinya. Kegagalan ini terjadi karena

sangat kecil bila dibandingkan

sehingga galat pembulatan yang kecil pada

menghasilkan galat besar di

. Perhatikan juga bahwa 1.569 - 1.568 adalah pengurangan dua buah bilangan yang hampir sama, yang menimbulkan hilangnya angka bena pada hasil pengurangannya.

b. Dengan tata-ancang pivoting sebagian