Eliminasi Gauss: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k Bot: Penggantian teks otomatis (-algoritma, +algoritme) |
Tag: Suntingan perangkat seluler Suntingan peramban seluler Suntingan seluler lanjutan |
||
Baris 7:
Dengan cara ini, [[matriks]] dapat diubah menjadi [[matriks segitiga atas]].
== Definisi dan contoh algoritma ==
Proses reduksi baris menggunakan [[operasi baris dasar]], dan dapat dibagi menjadi dua bagian. Bagian pertama (kadang disebut eliminasi maju) mereduksi sistem yang diberikan menjadi '' bentuk eselon baris '', dari mana seseorang dapat mengetahui apakah tidak ada solusi, solusi unik, atau banyak solusi tak hingga. Bagian kedua (terkadang disebut [[Matriks segitiga#Substitusi maju dan mundur|substitusi kembali]]) terus menggunakan operasi baris hingga solusi ditemukan; dengan kata lain, ini menempatkan matriks ke dalam bentuk eselon baris '' tereduksi ''.
Sudut pandang lain, yang ternyata sangat berguna untuk menganalisis algoritme, adalah bahwa reduksi baris menghasilkan [[dekomposisi matriks]] dari matriks asli. Operasi baris elementer dapat dilihat sebagai perkalian di sebelah kiri dari matriks asli dengan [[matriks elementer]]. Atau, urutan operasi dasar yang mengurangi satu baris dapat dilihat sebagai perkalian dengan [[matriks Frobenius]]. Kemudian bagian pertama dari algoritma menghitung sebuah [[LU penguraian]], sedangkan bagian kedua menulis matriks asli sebagai hasil perkalian dari matriks yang dapat dibalik yang ditentukan secara unik dan matriks eselon baris tereduksi yang ditentukan secara unik.
=== Operasi baris ===
{{see also|Matriks dasar}}
Ada tiga jenis operasi baris dasar yang dapat dilakukan pada baris matriks:
# Tukar posisi dua baris.
# Mengalikan baris dengan bukan nol [[skalar (matematika)|skalar]].
# Tambahkan ke satu baris beberapa skalar dari yang lain.
Jika matriks dikaitkan dengan sistem persamaan linear, maka operasi ini tidak mengubah kumpulan solusi. Oleh karena itu, jika tujuan seseorang adalah untuk menyelesaikan sistem persamaan linier, maka menggunakan operasi baris ini dapat membuat masalah menjadi lebih mudah.
=== Bentuk eselon ===
{{main|Bentuk eselon baris}}
Untuk setiap baris dalam matriks, jika baris tersebut tidak hanya terdiri dari angka nol, maka entri bukan nol paling kiri disebut '' [[koefisien awal]] '' (atau '' poros '') dari baris itu. Jadi jika dua koefisien utama berada di kolom yang sama, maka operasi baris [[#Operasi baris|Tipe 3]] dapat digunakan untuk membuat salah satu koefisien tersebut menjadi nol. Kemudian dengan menggunakan operasi pertukaran baris, seseorang selalu dapat mengurutkan baris sehingga untuk setiap baris bukan nol, koefisien terdepan ada di sebelah kanan koefisien terdepan dari baris di atas. Jika demikian, maka matriks dikatakan berada dalam '''bentuk eselon baris'''. Jadi bagian kiri bawah matriks hanya berisi angka nol, dan semua baris nol berada di bawah baris bukan nol. Kata "eselon" digunakan di sini karena secara kasar orang dapat membayangkan baris diberi peringkat berdasarkan ukurannya, dengan yang terbesar di atas dan yang terkecil di bawah.
Misalnya, matriks berikut dalam bentuk eselon baris, dan koefisien utamanya ditunjukkan dengan warna merah:
: <math>\begin{bmatrix}
0 & \color{red}{\mathbf{2}} & 1 & -1 \\
0 & 0 & \color{red}{\mathbf{3}} & 1 \\
0 & 0 & 0 & 0
\end{bmatrix}.</math>
Ini dalam bentuk eselon karena baris nol di bawah, dan koefisien terdepan dari baris kedua (di kolom ketiga), adalah di sebelah kanan koefisien terdepan dari baris pertama (di kolom kedua).
Suatu matriks dikatakan dalam '''bentuk eselon baris tereduksi''' jika selanjutnya semua koefisien utama sama dengan 1 (yang dapat dicapai dengan menggunakan operasi baris dasar tipe 2), dan di setiap kolom yang berisi koefisien utama, semua entri lain di kolom itu adalah nol (yang dapat dicapai dengan menggunakan operasi baris dasar tipe 3).
=== Contoh algoritma ===
Misalkan tujuannya adalah untuk menemukan dan mendeskripsikan himpunan solusi ke [[sistem persamaan linear]] berikut:
: <math>
\begin{alignat}{4}
2x &{}+{}& y &{}-{}& z &{}={}& 8 & \qquad (L_1) \\
-3x &{}-{}& y &{}+{}& 2z &{}={}& -11 & \qquad (L_2) \\
-2x &{}+{}& y &{}+{}& 2z &{}={}& -3 & \qquad (L_3)
\end{alignat}
</math>
Tabel di bawah ini adalah proses reduksi baris yang diterapkan secara bersamaan ke sistem persamaan dan [[matriks besar]] yang terkait. Dalam praktiknya, seseorang biasanya tidak berurusan dengan sistem dalam hal persamaan, melainkan menggunakan matriks yang diperbesar, mana yang lebih cocok untuk manipulasi komputer. Prosedur pengurangan baris dapat diringkas sebagai berikut: hilangkan {{mvar|x}} dari semua persamaan di bawah {{math|''L''<sub>1</sub>}}, lalu hilangkan {{mvar|y}} dari semua persamaan di bawah ini {{math|''L''<sub>2</sub>}}. Ini akan membuat sistem menjadi [[bentuk segitiga]]. Kemudian, dengan menggunakan substitusi balik, setiap ketidaktahuan dapat diselesaikan.
: {| style="background-color:white;" class="wikitable"
|-
! Sistem persamaan !! Operasi baris !! Matriks yang diperbesar
|- align="center"
| <math>
\begin{alignat}{ 2x &
-3x &
-2x &
\end{alignat}
</math> | | <math> \left[
2 & 1 & -1 & 8 \\
-3 & -1 & 2 & -11 \\
-2 & 1 & 2 & -3
\end{array}
</math>
|- align="center"
| <math>
\begin{alignat}{ 2x &{}+{}&
&
\end{alignat}
</math>
| <math>
\begin{align}
L_2 + \tfrac32 L_1 &\to L_2 \\
L_3 + L_1 &\to L_3
\end{align}
</math>
| <math>
\left[\begin{array}{rrr|r}
2 & 1 & -1 & 8 \\
0 & \frac12 & \frac12 & 1 \\
0 & 2 & 1 & 5
\end{array}\right]
</math>
|- align="center"
| <math>
\begin{alignat}{ 2x &{}+{}&
&
\end{alignat}
</math> | <math> L_3 + - | <math> \left[ 2 & 1 & -1 & 8 \\
0 &
0 & 0 & -1 & 1
\end{array}
</math> |-
|
|- align="center"
| <math>
\begin{alignat}{ 2x &{}+{}&
&
\end{alignat}
</math>
| <math>
\begin{align}
L_2 + \tfrac12 L_3 &\to L_2 \\
L_1 - L_3 &\to L_1
\end{align}
</math>
| <math>
\left[\begin{array}{rrr|r}
2 & 1 & 0 & 7 \\
0 & \frac12 & 0 & \frac32 \\
0 & 0 & -1 & 1
\end{array}\right]
</math>
|- align="center"
| <math>
\begin{alignat}{ 2x &
\end{alignat}
</math>
| <math>
\begin{align}
2 L_2 &\to L_2 \\
-L_3 &\to L_3
\end{align}
</math>
| <math>
\left[\begin{array}{rrr|r}
2 & 1 & 0 & 7 \\
0 & 1 & 0 & 3 \\
0 & 0 & 1 & -1
\end{array}\right]
</math>
|- align="center"
| <math>
\begin{alignat}{ x
\end{alignat}
</math>
| <math>
\begin{align}
L_1 - L_2 &\to L_1 \\
\tfrac12 L_1 &\to L_1
\end{align}
</math>
| <math>
\left[\begin{array}{rrr|r}
1 & 0 & 0 & 2 \\
0 & 1 & 0 & 3 \\
0 & 0 & 1 & -1
\end{array}\right]
</math>
|}
Kolom kedua menjelaskan operasi baris mana yang baru saja dilakukan. Jadi untuk langkah pertama, {{mvar|x}} dihilangkan dari {{math|''L''<sub>2</sub>}} dengan menambahkan {{math|{{sfrac|3|2}} ''L''<sub> 1</sub>}} hingga {{math|''L''<sub>2</sub>}}. Berikutnya, {{mvar|x}} dihilangkan dari {{math | ''L'' <sub> 3 </sub>}} dengan menambahkan {{math|''L''<sub>1</sub>}} ke {{math|''L''<sub>3</sub>}}. Operasi baris ini diberi label pada tabel sebagai
: <math>\begin{align}
L_2 + \tfrac32 L_1 &\to L_2, \\
L_3 + L_1 &\to L_3.
\end{align}</math>
Setelah {{mvar|y}} juga dihilangkan dari baris ketiga, hasilnya adalah sistem persamaan linier dalam bentuk segitiga, dan bagian pertama dari algoritme telah selesai. Dari sudut pandang komputasi, lebih cepat untuk menyelesaikan variabel dalam urutan terbalik, sebuah proses yang dikenal sebagai substitusi balik. Satu melihat solusinya adalah {{math|''z'' {{=}} −1}}, {{math|''y'' {{=}} 3}}, dan {{math|''x'' {{=}} 2}}. Jadi ada solusi unik untuk sistem persamaan asli.
Alih-alih berhenti setelah matriks dalam bentuk eselon, seseorang dapat melanjutkan hingga matriks dalam bentuk eselon baris '' tereduksi '', seperti yang dilakukan pada tabel. Proses pengurangan baris hingga matriks dikurangi kadang-kadang disebut sebagai '''Eliminasi Gauss–Jordan''', untuk membedakannya dari berhenti setelah mencapai bentuk eselon.
== Sejarah ==
Metode eliminasi Gaussian muncul - meskipun tanpa bukti - dalam teks matematika Cina [[Kalkulus batang#Sistem persamaan linear|Bab Delapan:''Array Persegi Panjang'']] dari '' [[Sembilan Bab tentang Seni Matematika]] ''. Penggunaannya diilustrasikan dalam delapan belas soal, dengan dua hingga lima persamaan. Referensi pertama ke buku dengan judul ini bertanggal 179 M, tetapi sebagian darinya ditulis sekitar 150 SM.<ref>{{harvtxt|Calinger|1999}}, pp. 234–236</ref><ref name="princeton">{{cite book|author1=Timothy Gowers|author2=June Barrow-Green|author3=Imre Leader|title=The Princeton Companion to Mathematics|url=https://archive.org/details/princetoncompanio00gowe|date=8 September 2008|publisher=Princeton University Press|isbn=978-0-691-11880-2|page=607}}<!-- |accessdate=28 September 2012 --></ref> Itu dikomentari oleh [[Liu Hui]] pada abad ke-3.
Metode di Eropa berasal dari catatan [[Isaac Newton]].<ref>{{harvtxt|Grcar|2011a}}, pp. 169-172</ref><ref>{{harvtxt|Grcar|2011b}}, pp. 783-785</ref> Pada 1670, dia menulis bahwa semua buku aljabar yang dikenalnya tidak memiliki pelajaran untuk memecahkan persamaan simultan, yang kemudian diberikan Newton. Universitas Cambridge akhirnya menerbitkan catatan tersebut sebagai '' Arithmetica Universalis '' pada tahun 1707 lama setelah Newton meninggalkan kehidupan akademis. Catatan itu ditiru secara luas, yang menjadikan (apa yang sekarang disebut) eliminasi Gaussian sebagai pelajaran standar dalam buku teks aljabar pada akhir abad ke-18. [[Carl Friedrich Gauss]] pada tahun 1810 merancang sebuah notasi untuk eliminasi simetris yang diadopsi pada abad ke-19 oleh [[Komputer manusia | komputer tangan]] profesional untuk menyelesaikan persamaan normal leas.<ref>{{harvtxt|Lauritzen|}}, p. 3</ref> The algorithm that is taught in high school was named for Gauss only in the 1950s as a result of confusion over the history of the subject.<ref>{{harvtxt|Grcar|2011b}}, p. 789</ref>
Beberapa penulis menggunakan istilah '' eliminasi Gaussian '' untuk merujuk hanya pada prosedur sampai matriks dalam bentuk eselon, dan menggunakan istilah '''eliminasi Gauss – Jordan''' untuk merujuk pada prosedur yang. Nama ini digunakan karena merupakan variasi dari eliminasi Gaussian seperti yang dijelaskan oleh [[Wilhelm Jordan (ahli geodesi)|Wilhelm Jordan]] pada tahun 1888. Namun, metode tersebut juga muncul dalam artikel oleh Clasen yang diterbitkan pada tahun yang sama. Jordan dan Clasen mungkin menemukan eliminasi Gauss–Jordan secara independen.<ref>{{Citation | last1=Althoen | first1=Steven C. | last2=McLaughlin | first2=Renate | title=Gauss–Jordan reduction: a brief history | doi=10.2307/2322413 | year=1987 | journal=[[American Mathematical Monthly|The American Mathematical Monthly]] | issn=0002-9890 | volume=94 | issue=2 | pages=130–142 | jstor=2322413 | publisher=Mathematical Association of America}}</ref>
== Aplikasi ==
Secara historis, aplikasi pertama dari metode reduksi baris adalah untuk menyelesaikan [[sistem persamaan linier]]. Berikut adalah beberapa aplikasi penting lainnya dari algoritme.
== Menghitung determinan ==
Untuk menjelaskan bagaimana eliminasi Gaussian memungkinkan perhitungan determinan matriks persegi, kita harus mengingat bagaimana operasi baris dasar mengubah determinan:
* Menukar dua baris mengalikan determinan dengan −1
* Mengalikan baris dengan skalar bukan nol mengalikan determinan dengan skalar yang sama
* Menambahkan kelipatan skalar dari baris lain ke satu baris tidak mengubah determinan.
Jika eliminasi Gauss diterapkan pada matriks persegi, {{mvar | A}} menghasilkan matriks eselon baris {{mvar | B}}, biarkan {{mvar | d}} menjadi produk skalar yang determinannya telah dikalikan, menggunakan aturan di atas. Maka determinan dari {{mvar | A}} adalah hasil bagi oleh {{mvar | d}} dari hasil kali elemen diagonal dari {{mvar|B}}:
:<math>\det(A) = \frac{\prod\operatorname{diag}(B)}{d}.</math>
<!--
Computationally, for an {{math|''n'' × ''n''}} matrix, this method needs only {{math|[[O notation|O(''n''<sup>3</sup>)]]}} arithmetic operations, while solving by elementary methods requires {{math|O(2<sup>''n''</sup>)}} or {{math|O(''n''!)}} operations. Even on the fastest computers, the elementary methods are impractical for {{math|''n''}} above 20.
=== Finding the inverse of a matrix ===
{{see also|Invertible matrix}}
A variant of Gaussian elimination called Gauss–Jordan elimination can be used for finding the inverse of a matrix, if it exists. If {{math|''A''}} is an {{math|''n'' × ''n''}} square matrix, then one can use row reduction to compute its [[invertible matrix|inverse matrix]], if it exists. First, the {{math|''n'' × ''n''}} [[identity matrix]] is augmented to the right of {{math|''A''}}, forming an {{math|''n'' × 2''n''}} [[block matrix]] {{math|[''A'' {{!}} ''I'']}}. Now through application of elementary row operations, find the reduced echelon form of this {{math|''n'' × 2''n''}} matrix. The matrix {{math|''A''}} is invertible if and only if the left block can be reduced to the identity matrix {{math|''I''}}; in this case the right block of the final matrix is {{math|''A''<sup>−1</sup>}}. If the algorithm is unable to reduce the left block to {{math|''I''}}, then {{math|''A''}} is not invertible.
For example, consider the following matrix:
: <math>A =
\begin{bmatrix}
2 & -1 & 0 \\
-1 & 2 & -1 \\
0 & -1 & 2
\end{bmatrix}.
</math>
To find the inverse of this matrix, one takes the following matrix augmented by the identity and row-reduces it as a 3 × 6 matrix:
: <math>[ A | I ] =
\left[\begin{array}{ccc|ccc}
2 & -1 & 0 & 1 & 0 & 0 \\
-1 & 2 & -1 & 0 & 1 & 0 \\
0 & -1 & 2 & 0 & 0 & 1
\end{array}\right].
</math>
By performing row operations, one can check that the reduced row echelon form of this augmented matrix is
: <math>[ I | B ] =
\left[\begin{array}{rrr|rrr}
1 & 0 & 0 & \frac34 & \frac12 & \frac14 \\
0 & 1 & 0 & \frac12 & 1 & \frac12 \\
0 & 0 & 1 & \frac14 & \frac12 & \frac34
\end{array}\right].
</math>
One can think of each row operation as the left product by an [[elementary matrix]]. Denoting by {{math|''B''}} the product of these elementary matrices, we showed, on the left, that {{math|''BA'' {{=}} ''I''}}, and therefore, {{math|''B'' {{=}} ''A''<sup>−1</sup>}}. On the right, we kept a record of {{math|''BI'' {{=}} ''B''}}, which we know is the inverse desired. This procedure for finding the inverse works for square matrices of any size.
=== Computing ranks and bases ===
The Gaussian elimination algorithm can be applied to any {{math|''m'' × ''n''}} matrix {{mvar|A}}. In this way, for example, some 6 × 9 matrices can be transformed to a matrix that has a row echelon form like
:<math> T=
\begin{bmatrix}
a & * & * & *& * & * & * & * & * \\
0 & 0 & b & * & * & * & * & * & * \\
0 & 0 & 0 & c & * & * & * & * & * \\
0 & 0 & 0 & 0 & 0 & 0 & d & * & * \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & e \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix},
</math>
where the stars are arbitrary entries, and {{math|''a'', ''b'', ''c'', ''d'', ''e''}} are nonzero entries. This echelon matrix {{mvar|T}} contains a wealth of information about {{mvar|A}}: the [[rank of a matrix|rank]] of {{mvar|A}} is 5, since there are 5 nonzero rows in {{mvar|T}}; the [[vector space]] spanned by the columns of {{mvar|A}} has a basis consisting of its columns 1, 3, 4, 7 and 9 (the columns with {{math|''a'', ''b'', ''c'', ''d'', ''e''}} in {{mvar|T}}), and the stars show how the other columns of {{mvar|A}} can be written as linear combinations of the basis columns. This is a consequence of the distributivity of the [[dot product]] in the expression of a linear map [[Linear map#Matrices|as a matrix]].
All of this applies also to the reduced row echelon form, which is a particular row echelon format.
-->
== Daftar pustaka ==
| |||