Eliminasi Gaussian - Komputasi Aljabar Linear

Kita sekarang akan mendeskripsikan prosedur sistematis, yang disebut eliminasi Gaussian, yang memungkinkan kita mereduksi sistem linear $L$ menjadi sistem $L'$ dalam bentuk eselon baris. Sesuai dengan pembahasan sebelumnya, kita akan mengidentifikasi sistem $L$ dengan matriks augmentasinya $A$ . Kemudian, mereduksi sistem linear menggunakan operasi baris elementer pada persamaan tersebut dengan operasi baris elementer pada matriks.

Eliminasi Gauss adalah algoritma yang digunakan untuk menyelesaikan sistem persamaan linear dengan mengubah matriks koefisien menjadi bentuk yang lebih sederhana, yaitu matriks segitiga atas atau eselon baris, sehingga solusi dapat diperoleh melalui subsitusi balik.

Definisi matriks¶

Sebuah matriks adalah susunan bilangan berbentuk persegi panjang. Matriks dengan $m$ baris dan $n$ kolom dikatakan memiliki ukuran (atau dimensi) $m \times n$ .

Definisi matriks augmentasi¶

Misalkan $L$ adalah sistem linier

\begin{array}{ccccccccc} a_{11}x_1 &+& a_{12}x_2 &+& \cdots &+& a_{1n}x_n &=& b_1 \\ a_{21}x_1 &+& a_{22}x_2 &+& \cdots &+& a_{2n}x_n &=& b_2 \\ & \vdots &&& \vdots &&& \vdots &\\ a_{m1}x_1 &+& a_{m2}x_2 &+& \cdots &+& a_{mn}x_n &=& b_m \end{array}

(1)

Matriks augmentasi yang terkait dengan $L$ adalah matriks

\begin{bmatrix}{|} a_{11} &+& a_{12} &+& \cdots &+& a_{1n} && b_1 \\ a_{21} &+& a_{22} &+& \cdots &+& a_{2n} && b_2 \\ \vdots && \vdots && \ddots && \vdots && \vdots\\ a_{m1} &+& a_{m2} &+& \cdots &+& a_{mn} && b_m \end{bmatrix}

(2)

Definisi matriks bentuk eselon baris¶

Baris nol dari suatu matriks adalah baris yang semua entrinya sama dengan nol; baris tak-nol adalah baris yang memuat setidaknya satu entri tak-nol.

Suatu matriks berada dalam bentuk eselon baris jika kondisi-kondisi berikut terpenuhi.

(i) Pada sembarang baris tak-nol, entri tak-nol pertama (yaitu, paling kiri) sama dengan satu. Satu utama (pivot) dari suatu matriks adalah entri dari suatu baris yang sama dengan satu, dan merupakan entri tak-nol pertama dari baris tersebut.

(ii) Semua baris nol dikelompokkan bersama di bagian bawah matriks.

(iii) Diberikan dua baris tak-nol sembarang dalam matriks, satu utama (pivot) dari baris yang lebih bawah terletak di sebelah kanan satu utama dari baris di atasnya.

Suatu matriks berada dalam bentuk eselon baris tereduksi jika selain memenuhi kondisi (i)-(iii) juga memenuhi kondisi berikut.

(iv) Setiap kolom matriks yang memuat satu utama pada salah satu barisnya,maka itu adalah satu-satunya entri tak-nol dari kolom tersebut.

Sistem linear $L$ berada dalam bentuk eselon baris (masing-masing bentuk eselon baris tereduksi) jika matriks augmentasinya berada dalam bentuk eselon baris (masing-masing bentuk eselon baris tereduksi).

Dalam praktik untuk memutuskan apakah suatu matriks berada dalam bentuk eselon baris (tereduksi), ikuti langkah-langkah berikut:

Pertama verifikasi apakah semua baris nol berada di bagian bawah.
Untuk setiap baris tak-nol, tentukan apakah entri tak-nol pertama adalah 1, dan tandai kotak pada pivot tersebut.
Pastikan kotak-kotak tersebut membentuk pola tangga.
(Dan untuk bentuk eselon baris tereduksi.) Tentukan apakah setiap kolom selain pivot memiliki nilai 0.

Example Bentuk eselon baris versus bentuk eselon baris tereduksi

Untuk setiap matriks, tentukan (a) apakah matriks tersebut berada dalam bentuk eselon baris, dan (b) apakah matriks tersebut berada dalam bentuk eselon baris tereduksi.

\begin{bmatrix} 0 & 2 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ \end{bmatrix}

(3)

Di bawah ini Anda menemukan matriks dengan satu utama yang ditandai kotak. Matriks ini bukan dalam bentuk eselon baris juga bentuk eselon baris tereduksi karena berbagai alasan: baris nol tidak semuanya dikelompokkan di bagian bawah matrik; baris pertama tak-nol, tetapi tidak memiliki satu utama; satu utama dari baris keempat berada di sebelah kiri satu utama dari baris di atasnya.

\begin{bmatrix} 1 & 0 & 0 & -3 & -7\\ 0 & 0 & 1 & 2 & 0\\ 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ \end{bmatrix}

(4)

Di bawah ini Anda menemukan matriks dengan satu utama yang ditandai kotak. Matriks ini berada dalam bentuk eselon baris: baris nol (baris 4 dan 5) dikelompokkan di bagian bawah; setiap baris tak-nol memiliki satu utama (diberi kotak pada matriks di bawah); satu utama secara berurutan berada disebelah bawah kanannya untuk setiap baris dan membentuk tangga.

Matriks ini tidak berada dalam bentuk eselon baris tereduksi, karena kolom terakhir memuat satu utama pada baris ketiganya, dan entri tak-nol pada baris pertamanya.

Definisi Operasi baris elementer pada matriks¶

Sebuah operasi baris elementer adalah salah satu dari tiga jenis operasi matriks berikut. Misalkan $A$ adalah matriks $m \times n$ yang diberikan, dan nyatakan dengan $r_i$ baris ke- $i$ dari $A$ .

Perkalian Skalar Kalikan sebuah baris dengan bilangan tak-nol : $c \neq 0$ yaitu, ganti $r_i$ dengan $cr_i$ , hasil perkalian semua entri baris dengan $c$ .
Pertukaran baris Tukar dua baris dari $A$
Penjumlahan baris Tambahkan kelipatan satu baris lain: yaitu, ganti $r_i$ dengan $r_i + cr_j$ untuk suatu $c,i$ dan $j$ .

Proses mengubah matriks menggunakan operasi baris elementer disebut reduksi baris.

Dua matriks ekuivalen baris jika yang salah satunya dari matrik diperoleh dari yang lain dengan melakukan serangkaian operasi baris elementer.

Definisi Eliminasi Gaussian¶

Eliminasi Gaussian adalah algoritma yang dijelaskan di bawah. Algoritma ini menerima masukan matriks $A$ dan mengembalikan matriks $B$ yang ekuivalen baris dalam bentuk eselon baris.

Langkah 1 Temukan kolom tak-nol paling kiri dan lakukan pertukaran baris untuk memindahkan baris dengan entri tak-nol ini ke bagian atas matriks.
Langkah 2 Skala baris teratas yang baru untuk menghasilkan satu utama pada baris tersebut. Sebut baris baru ini $r$ .
Langkah 3 Untuk setiap baris $r_i$ di bawah $r$ , lakukan operasi baris berbentuk $r_i + cr$ untuk mengganti semua entri di bawah satu utama dari $r$ dengan nol.
Langkah 4 Mulai lagi dengan Langkah 1 yang diterapkan pada matriks yang terdiri dari semua baris di bawah $r$ . Lanjutkan hingga matriks berada dalam bentuk eselon baris.

Example $$ \begin{aligned}

\begin{bmatrix} 0&0&-2&0&7&12\\ 2&4&-10&6&12&28\\ 2&4&-5&6&-5&-1 \end{bmatrix}

(5)

&\xrightarrow{r_1 \leftrightarrow r_2}

\begin{bmatrix} 2&4&-10&6&12&28\\ 0&0&-2&0&7&12\\ 2&4&-5&6&-5&-1 \end{bmatrix}

(6)

&\xrightarrow{\frac12 r_1}

\begin{bmatrix} 1&2&-5&3&6&14\\ 0&0&-2&0&7&12\\ 2&4&-5&6&-5&-1 \end{bmatrix}

(7)

&\xrightarrow{r_3-2r_1}

\begin{bmatrix} 1&2&-5&3&6&14\\ 0&0&-2&0&7&12\\ 0&0&5&0&-17&-29 \end{bmatrix}

(8)

&\xrightarrow{-\frac12 r_2}

\begin{bmatrix} 1&2&-5&3&6&14\\ 0&0&1&0&-\frac{7}{2}&-6\\ 0&0&5&0&-17&-29 \end{bmatrix}

(9)

&\xrightarrow{r_3+(-5)r_2}

\begin{bmatrix} 1&2&-5&3&6&14\\ 0&0&1&0&-\frac{7}{2}&-6\\ 0&0&0&0&\frac12&1 \end{bmatrix}

(10)

&\xrightarrow{2r_3}

\begin{bmatrix} 1&2&-5&3&6&14\\ 0&0&1&0&-\frac{7}{2}&-6\\ 0&0&0&0&1&2 \end{bmatrix}

(11)

\end{aligned} $$ Matriks yang dihasilkan oleh eliminasi Gaussian dijamin berada dalam bentuk eselon baris, tetapi mungkin tidak berada dalam bentuk eselon baris tereduksi.

Definisi Eliminasi Gauss-Jordan¶

Eliminasi Gauss-Jordan adalah algoritma menerima masukan matriks $A$ dan menhgasilkan matriks $B$ yang ekuivalen baris dalam bentuk eselon baris tereduksi.

Langkah 1-4 Terapkan eliminasi Gaussian untuk mengubah $A$ menjadi matriks dalam bentuk eselon baris.
Langkah 5 Temukan kolom paling kanan dari matriks yang memuat satu utama. Misalkan $r_i$ adalah baris yang memuat satu utama ini. Untuk setiap baris $r_j$ di atas $r_i$ , lakukan operasi baris berbentuk $r_i + cr_j$ untuk mengganti semua entri di atas satu utama dengan nol.
Langkah 6 Mulai lagi dengan Langkah 5 untuk diterapkan pada kolom berikutnya di sebelah kiri yang memuat satu utama. Lanjutkan hingga matriks berada dalam bentuk eselon baris tereduksi.

Example $$ \begin{aligned}

\begin{bmatrix} 1 & 2 & -5 & 3 & 6 & 14\\ 0 & 0 & 1 & 0 & -\frac{7}{2} & -6\\ 0& 0 & 0 & 0 & 1 & 2 \end{bmatrix}

(12)

&\xrightarrow{r_2 + \frac{7}{2}r_3}

\begin{bmatrix} 1 & 2 & -5 & 3 & 6 & 14\\ 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 2 \end{bmatrix}

(13)

&\xrightarrow{r_1 - 6r_3}

\begin{bmatrix} 1 & 2 & -5 & 3 & 0 & 2\\ 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 2 \end{bmatrix}

(14)

&\xrightarrow{r_1 + 5r_2}

\begin{bmatrix} 1 & 2 & 0 & 3 & 0 & 7\\ 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 2 \end{bmatrix}

(15)

\end{aligned} $$

Indeks baris dimulai dari 0 (bukan 1). Jadi baris pertama adalah baris ke-0, baris kedua adalah baris ke-1, dst.
Operasi ini mengubah matriks secara langsung (in place).

Example Sistem Persamaan Linear

sistem persamaan:
$x + y + z = 6\\ 2x + y + z = 3\\ x + 2y - z = 2\\$
(16)
Matriks Augmentasi
$\left[ \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 2 & -1 & 1 & 3 \\ 1 & 2 & -1 & 2 \end{array} \right]$
(17)
Langkah 1 : Eliminasi $x$ pada baris 2 dan 3
$R_2 \rightarrow R_2 - 2R_1 \left[ \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & -3 & -1 & -9 \\ 1 & 2 & -1 & 2 \end{array} \right]$
(18)
$R_3 \rightarrow R_3 - R_1 \left[ \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & -3 & -1 & -9 \\ 0 & 1 & -2 & -4 \end{array} \right]$
(19)
Langkah 2 : Tukar baris 2 dan 3 agar pivot lebih mudah.
$R_2 \leftrightarrow R_3 \left[ \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -2 & -4\\ 0 & -3 & -1 & -9 \end{array} \right]$
(20)
Langkah 3 : Eliminasi $y$ pada baris 3.
$R_3 \rightarrow R_3 + 3R_2 \left[ \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -2 & -4\\ 0 & 0 & -7 & -21 \end{array} \right]$
(21)
Langkah 4 : Normalisasikan baris 3.
$R_3 \rightarrow -\frac{1}{7}R_3 \left[ \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -2 & -4\\ 0 & 0 & 1 & 3 \end{array} \right]$
(22)
Dari sini diperoleh $z = 3$ . Lanjutkan ke bentuk eselon baris tereduksi.

R_2 \rightarrow R_2 + 2R_3 \left[ \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & 0 & 2\\ 0 & 0 & 1 & 3 \end{array} \right]

(23)

R_1 \rightarrow R_1 - R_3 \left[ \begin{array}{ccc|c} 1 & 1 & 0 & 3 \\ 0 & 1 & 0 & 2\\ 0 & 0 & 1 & 3 \end{array} \right]

(24)

Langkah 5 : Eliminasi $y$ pada baris 1.
$R_1 \rightarrow R_1 - R_2 \left[ \begin{array}{ccc|c} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 2\\ 0 & 0 & 1 & 3 \end{array} \right]$
(25)

Kesimpulan: didapatkan $x=1, y=1, z=1$ .

Tiga operasi dalam baris¶

A.rescale_row(i, a) Fungsi: Mengalikan baris ke-i dengan skalar a
$baris_i=a×baris_i$
(26)

A.add_multiple_of_row(i, j, a) Fungsi: Menambahkan 𝑎× baris ke- $j$ ke baris ke- $i$ .
$baris_i=a×baris_j+baris_i$
(27)