gauss jordan
by
aripradani358.blogspot.com
- Juni 06, 2013
BAB I
PENDAHULUAN
A.
Latar Belakang
Karl Friedich Gauss (1977-1855) adalah seorang
ahli matematika dan ilmuwan dari Jerman. Gauss yang kadang-kadang dijuluki
“pangeran ahli matematika” disejajarkan dengan Isaac Newton dan Archimedes sebagai salah satu dari
tiga ahli matematika yang terbesar yang pernah ada. Dalam seluruh sejarah
matematika, tidak pernah ada seorang anak yang begitu cepat berkembang,
sebagaimana Gauss, yang dengan usahanya sendiri menyelesaikan dasar aritmetika
sebelum ia dapat berbicara. Pada suatu hari, saat ia bahkan belum berusia tiga
tahun, melalui cara dramatis orang tuanya mulai menyadari kejeniusan Gauss.
Wilhelm Jordan (1842-1899) adalah seorang
insinyur Jerman yang ahli dalam bidang geodesi. Sumbangannya untuk penyelesaian
sistem linear dalam buku populernya, Handbuch de Vermessungskunde (Buku
panduan Geodesi) pada tahun 1988. Contoh Sumbangannya untuk penyelesaian sistem
linear dalam buku populernya
Dalam aljabar linear, eliminasi Gauss-Jordan
adalah versi dari eliminasi Gauss. Pada metode eliminasi Gauus-Jordan kita
membuat nol elemen-elemen di bawah maupun di atas diagonal utama suatu matriks.
Hasilnya adalah matriks tereduksi yang berupa matriks diagonal satuan (Semua
elemen pada diagonal utama bernilai 1, elemen-elemen lainnya nol).
Metode eliminasi Gauss-Jordan kurang efisien
untuk menyelesaikan sebuah SPL, tetapi lebih efisien daripada eliminasi Gauss
jika kita ingin menyelesaikan SPL dengan matriks koefisien sama.
Motede tersebut dinamai Eliminasi Gauss-Jordan
untuk menghormati Carl Friedrich Gauss dan Whilhelm Jordan.
B.
Tujuan
1.
Mencari solusi system
persamaan linier menggunakan metode eliminasi Gauss
2.
Mencari solusi system
persamaan linier menggunakan metode eliminasi Gauss-Jordan
BAB
II
PEMBAHASAN
Di
dalam matematika, system persamaan linier
adalah kumpulan persamaan-persamaan linier yang memiliki variabel-variabel yang sama.
Bentuk umum dari sistem persamaan linier dengan n peubah dinyatakan
sebagai berikut:
. . . .
. . . .
. . . .
Dengan
mengunakan perkalian matriks, kita dapat menulis persamaan di atas sebagai
persamaan matriks
Yang dalam hal ini,
Yaitu:
A.
Metode
Eliminasi Gauss
Metode Eliminasi Gauss merupakan metode yang
dikembangkan dari metode eliminasi, yaitu menghilangkan atau mengurangi jumlah
variabel sehingga dapat diperoleh nilai dari suatu variabel bebas. Cara
eliminasi ini sudah banyak dikenal.
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:
Kondisi
sangat penting. Sebab bila
,
persamaan diatas menjerjakan pembagian dengan nol. Apabila kondisi tersebut tidak
dipenuhi, maka SPL tidak mempunyai jawaban.
Contoh :
Solusi
system diperoleh dengan teknik penyulihan mundur sebagai berikut:
Diperoleh
penyelesaian x = 1, y = 2, z = 3.
©
Tata
ancang pivoting
Prinsip tata ancang pivoting
adalah sebagai berikut: jika
= 0,
cari baris k dengan
dan k > p, lalu pertukaran baris p dan
baris k. Metode eliminasi Gauss dengan tata
ancang pivoting disebut metode eliminasi Gauss yang diperbaiki (modified
Gauusian elimination)
Contoh:
Selesaikan sistem prsamaan lanjar berikut
dengan meetode eliminasi Gauss yang menerapkan tata ancang pivoting.
Operasi baris 1
Operasi baris 2
Setelah operasi baris 1, elemen
yang akan
menjadi pivot pada operasi baris 2 ternyata sama dengan nol. Karena itu, pada
operasi baris 2, elemen baris 2 dipertukarkan dengan elemen baris 3. Tanda (*)
menyatakan pertukaran baris terjadi akibat proses pivoting. Sekarang elemen
sehingga operasi baris elementer dapat
diteruskan. Tetapi, karena matriks A sudah membentuk matriks U, proses
eliminasi selesai. Solusinya diperoleh dengan teknik penyulihan mundur, yaitu
.
Melakukan pertukaran baris
untuk menghindari pivot yang bernilai nol adalah cara pivoting yang sederhana (simple
pivoting). Masalah ini dapat juga timbul bila elemen pivot sangat dekat ke
nol, karena jika elemen pivot sangat kecil dibandingkan terhadap elemen
lainnya, maka galat pembulatan dapat muncul.
Ada dua macam tata-ancang pivoting, yaitu:
a.
Pivoting
sebagian (partial pivoting)
Pada
tata-ancang pivoting sebagian, pivot dipilih dari semua elemen pada kolom p
yang mempunyai nilai mutlak terbesar,
½
½
½
½,½
½,…, ½
½,½
½}
Lalu
pertukarkan baris k dengan baris ke 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. Elemen x yang nilai mutlaknya terbesar itu sekarang menjadi
pivot untuk operasi baris selanjutnya.
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 elemen terbesar dan
kemudian dipertukarkan, maka tata-ancang ini disebut pivoting lengkap. Pivoting
lengkap jarang dipakai dalam program sederhana karena pertukaran kolom mengubah
urutan suku 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
a.
Tanpa
tata-ancang pivoting sebagian
Operasi
baris pertama
(Tanda “
”
berarti “diisi” atau “diganti dengan”)
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
dinbandingkan½
½, sehingga galat
pembulatan yang kecil pada
menghasilkan
galat besar di
. Perhatikan juga bahwa 1.569
1.568 adalah
pengurangan dua buah bilangan yang hamper sama, yang menimbulkan hilangnya
angka bena pada hasil pengurangannya.
b. Dengan tata-ancang
pivoting sebagian
Dengan
teknik penyulihan mundur diperoleh:
Jadi, solusinya adalah x = (10.02, 1.000), yang
lebih baik daripada solusi a. keberhasilan ini karena ½
½ tidak sangat
kecil dibandingkan dengan ½
½, sehingga galat
pembulatan yang kecil pada
tidak akan
menghasilkan galat yang besar pada
.
©
Penskalaan
Kemungkinan solusi SPL
Selain dengan pivoting
sebagian, penskalaan (scaling) juga dapat digunakan untuk mengurangi
galat pembulatan pada SPL yang mempunyai perbedaan koefisien yang mencolok.
Situasi demikian sering ditemui dalam praktek rekayasa yang menggunakan ukuran
satuan yang berbeda-beda dalam menentukan persamaan simultan. Misalnya pada
persoalan rangkaian listrik, tegangan listrik dapat dinyatakan dalam satuan
yang berkisar dari microvolt sampai kilovolt. Pemakaian satuan yang
berbeda-beda dapat menuju ke koefisien yang besarnya sangat berlainan. Ini
terdampak pada galat pembulatan, dank arena itu mempengaruhi pivoting. Dengan
penskalaan berarti kita menormalkan persamaan. Cara menskala adalah membagi
tiap baris persamaan dengan nilai mutlak koefisien terbesar di ruang kirinya.
Akibat penskalaan, koefisien maksimum dalam tiap baris adalah 1. Cara menskala
seperti ini dinamakan dengan menormalkan SPL.
Contoh:
Selesaikan system persamaan lanjut berikut
sampai 3 angka bena dengna menggunakan metode eliminasi Gauss yang menerapkan
perskalaan dan tanpa perskalaan:
Penyelesaian:
(i)
Tanpa
perskalaan
Solusinya
adalah
(ii) Dengan penskalaan
Solusinya,
Yang
sesuai dengan solusi sejati. Contoh di atas juga memperlihatkan bahwa
penskalaan dapat mengubah pemilihan pivot.
©
Kemungkinan
solusi SPL
Tidak semua SPL mempunyai
solusi. Ada 3 kemungkinan yang dapat terjadi pada SPL:
a)
Mempunyai
solusi yang unik
b)
Mempunyai
banyak solusi, atau
c)
Tidak
ada solusi sama sekali
Untuk SPL dengan tiga buah persamaan atau
lebih (dengan tiga peubah atau lebih)tidak terdapat tafsiran geometrinya (tidak
mungkin dibuat ilustrasi grafiknya) seperti pada SPL dengan dua buah persamaan.
Namun, kita masih dapat memeriksa masing-masing kemungkinan solusi itu berdasarkan
pada bentuk matriks akhirnya. Agar lebih jelas, tinjau contoh pada SPL yang
disusun oleh tiga persamaan.
1)
Solusi
unik/tunggal
Solusi:
2)
Solusi
banyak/tidak terhingga
Perhatikan
hasil eliminasi Gauss pada baris terakhir. Persamaan yang bersesuaian dengan
baris terakhir tersebut adalah
Yang
dipenuhi oleh banyak nilai x. solusinya diberikan dalam bentuk
parameter:
Misalkan
Maka
3)
Tidak
ada solusi
Perhatikan
hasil eliminasi Gauss pada baris terakhir. Persamaan yang bersesuaian dengan
baris terakhir tersebut adalah
Yang
dalam hal ini, tidak nilai
yang memenuhi, i=1,2,3
B.
Eliminasi
Gauss-Jordan
Dalam aljabar linear, eliminasi Gauss-Jordan
adalah versi dari eliminasi Gauss. Pada metode eliminasi Gauss-Jordan kita
membuat nol elemen-elemen di bawah maupun di atas diagonal utama suatu matriks.
Hasilnya adalah matriks tereduksi yang berupa matriks diagonal satuan (semua
elemen pada diagonal utama bernilai 1, elemen-elemen lainnya nol).
Dalam bentuk matriks, eliminasi Gauss-Jordan
ditulis sebagai berikut.
Solusinya:
Seperti
pada metode eliminasi gauss naïf, metode eliminasi Gauss-Jordan naïf tidak
menerapkan tata-ancang pivoting dalam proses eliminasinya.
Langkah-langkah
operasi baris yang dikemukakan oleh Gauss dan disempurnakan oleh Jordan
sehingga dikenal dengan Eliminasi Gauss-Jordan, sebagai berikut:
1.
Jika
suatu baris tidak seluruhnya dari nol, maka bilangan tak nol pertama pada baris
itu adalah 1. Bilangan ini disebut 1 utama (leading 1).
2.
Jika
terdapat baris yang seluruhnya terdiri dari nol, maka baris-baris ini akan
dikelompokkan bersama pada bagian paling bawah dari matriks.
3.
Jika
terdapat dua baris berurutan yang tidak seluruhnya dari nol, maka 1 utama pada
baris yang lebih rendah terdapat pada kolom yang lebih kanan dari 1 utama pada
baris yang lebih tinggi.
4.
Setiap
kolom memiliki 1 utama memiliki nol pada tempat lain.
Algoritma Metode Eliminasi
Gauss-Jordan adalah sebagai berikut:
1.
Masukkan
matriks A dan vector B beserta ukurannya n
2.
Buat
augmented matriks [A½B] namakan dengan A
3.
Untuk
baris ke-i dimana i=1 s/d n
a)
Perhatikan
apakah nilai
sama dengan nol:
Bila ya:
Pertukarkan
baris ke-i dan baris ke i+k≤n, dimana
tidak sama dengan nol, bila tidak ada berarti
perhitungan tidak bisa dilanjutkan dan proses dihentikan dengan tanpa
penyelesaian.
Bila
tidak: Lanjutkan
b)
Jadikan
nilai diagonalnya menjadi satu, dengan cara untuk setiap kolom k dimana k=1 s/d
n+1, hitung
4.
Untuk
baris ke j, dimana j=i+1 s/d n
Lakukan operasi baris elementer untuk kolom k
dimana k=1 s/d n
Hitung
Hitung
5.
Penyelesaian,
untuk i=n s/d 1 (bergerak dari baris ke n sampai baris pertama)
Contoh:
Penyelesaian:
Diperoleh
penyelesaian x = 1, y = 2, z = 3.
Penyelesaian SPL dengan Operasi Baris
Elementer Menggunakan MATLAB
Misalkan diberikan SPL
sebagai berikut:
Kita
akan coba menyelesaikan SPL di atas dengan operasi baris elementer dengan
MATLAB.
1)
|
clc;
clear;
disp('Solusi
dari persamaan: x + y + 2z = 9')
disp(' 2x+4y - 3z = 1')
disp(' 3x+6y - 5z = 0')
disp('Menggunakan
Metode Eliminasi Gauss')
A=[1 1 2 9;2
4 -3 1;3 6 -5 0]
disp('Baris
1 = Baris 1 bagi baris 1 kolom 1')
A(1,:)=A(1,:)/A(1,1)
disp('Baris
2 = - Baris 2 kolom 1 kali baris 1 + Baris 2')
A(2,:)=-A(2,1)*A(1,:)+A(2,:)
disp('Baris
3 = - Baris 3 kolom 1 kali baris 1 + Baris 3')
A(3,:)=-A(3,1)*A(1,:)+A(3,:)
disp('Baris
2 = Baris 2 bagi baris 2 kolom 2')
A(2,:)=A(2,:)/A(2,2)
disp('Baris
3 = - Baris 3 kolom 2 kali baris 2 + Baris 3')
A(3,:)=-A(3,2)*A(2,:)+A(3,:)
disp('Baris
3 = Baris 3 bagi baris 3 kolom 3')
A(3,:)=A(3,:)/A(3,3)
disp('Dengan
Menggunakan Teknik Penyulihan Mundur, diperoleh:')
x3=A(3,4)
x2=A(2,4)-A(2,3)*x3
x1=A(1,4)-A(1,2)*x2-A(1,3)*x3
|
|
Solusi dari persamaan: x + y + 2z = 9
2x+4y - 3z = 1
3x+6y - 5z = 0
Menggunakan Metode Eliminasi Gauss
A =
1 1 2
9
2 4 -3
1
3 6 -5
0
Baris 1 = Baris 1 bagi baris 1 kolom 1
A =
1 1 2
9
2 4 -3
1
3 6 -5
0
Baris 2 = - Baris 2 kolom 1 kali baris
1 + Baris 2
A =
1 1 2
9
0 2 -7
-17
3 6 -5
0
Baris 3 = - Baris 3 kolom 1 kali baris
1 + Baris 3
A =
1 1 2
9
0 2 -7
-17
0 3 -11
-27
Baris 2 = Baris 2 bagi baris 2 kolom 2
A =
1.0000 1.0000 2.0000 9.0000
0
1.0000
-3.5000 -8.5000
0
3.0000
-11.0000 -27.0000
Baris 3 = - Baris 3 kolom 2 kali baris
2 + Baris 3
A =
1.0000 1.0000 2.0000 9.0000
0
1.0000
-3.5000 -8.5000
0 0 -0.5000
-1.5000
Baris 3 = Baris 3 bagi baris 3 kolom 3
A =
1.0000 1.0000 2.0000 9.0000
0
1.0000
-3.5000 -8.5000
0 0
1.0000 3.0000
Dengan Menggunakan Teknik Penyulihan
Mundur, diperoleh:
x3 =
3
x2 =
2
x1 =
1
>>
|
|
clc;
clear;
disp('Solusi dari persamaan: x + y + 2z
= 9')
disp(' 2x+4y - 3z = 1')
disp(' 3x+6y - 5z = 0')
disp('Menggunakan Metode Eliminasi
Gauss-Jordan')
A=[1 1 2 9;2 4 -3 1;3 6 -5 0]
disp('Baris 1 = Baris 1 bagi baris 1 kolom 1')
A(1,:)=A(1,:)/A(1,1)
disp('Baris 2 = - Baris 2 kolom 1 kali
baris 1 + Baris 2')
A(2,:)=-A(2,1)*A(1,:)+A(2,:)
disp('Baris 3 = - Baris 3 kolom 1 kali
baris 1 + Baris 3')
A(3,:)=-A(3,1)*A(1,:)+A(3,:)
disp('Baris 2 = Baris 2 bagi baris 2
kolom 2')
A(2,:)=A(2,:)/A(2,2)
disp('Baris 3 = - Baris 3 kolom 2 kali
baris 2 + Baris 3')
A(3,:)=-A(3,2)*A(2,:)+A(3,:)
disp('Baris 3 = Baris 3 bagi baris 3
kolom 3')
A(3,:)=A(3,:)/A(3,3)
disp('Baris 1 = - Baris 1 kolom 2 kali
baris 2 + Baris 1')
A(1,:)=-A(1,2)*A(2,:)+A(1,:)
disp('Baris 2 = - Baris 2 kolom 3 kali baris
3 + Baris 2')
A(2,:)=-A(2,3)*A(3,:)+A(2,:)
disp('Baris 1 = - Baris 1 kolom 3 kali
baris 3 + Baris 1')
A(1,:)=-A(1,3)*A(3,:)+A(1,:)
disp('Dengan demikian, diperoleh:')
x1=A(1,4)
x2=A(2,4)
x3=A(3,4)
|
Outputnya :
|
Solusi dari persamaan: x + y + 2z = 9
2x+4y - 3z = 1
3x+6y - 5z = 0
Menggunakan Metode Eliminasi
Gauss-Jordan
A =
1 1 2
9
2 4 -3
1
3 6 -5
0
Baris 1 = Baris 1 bagi baris 1 kolom 1
A =
1 1 2
9
2 4 -3
1
3 6 -5
0
Baris 2 = - Baris 2 kolom 1 kali baris 1
+ Baris 2
A =
1 1 2
9
0 2
-7 -17
3 6 -5
0
Baris 3 = - Baris 3 kolom 1 kali baris 1
+ Baris 3
A =
1 1 2
9
0 2 -7
-17
0 3 -11
-27
Baris 2 = Baris 2 bagi baris 2 kolom 2
A =
1.0000 1.0000 2.0000 9.0000
0 1.0000 -3.5000
-8.5000
0 3.0000
-11.0000 -27.0000
|
|
Baris 3 = - Baris 3 kolom 2 kali baris 2
+ Baris 3
A =
1.0000 1.0000 2.0000 9.0000
0 1.0000 -3.5000
-8.5000
0 0 -0.5000
-1.5000
Baris 3 = Baris 3 bagi baris 3 kolom 3
A =
1.0000 1.0000 2.0000 9.0000
0 1.0000 -3.5000
-8.5000
0 0 1.0000 3.0000
Baris 1 = - Baris 1 kolom 2 kali baris 2
+ Baris 1
A =
1.0000 0 5.5000
17.5000
0 1.0000 -3.5000
-8.5000
0 0 1.0000 3.0000
Baris 2 = - Baris 2 kolom 3 kali baris 3
+ Baris 2
A =
1.0000 0 5.5000
17.5000
0 1.0000 0 2.0000
0 0 1.0000 3.0000
Baris 1 = - Baris 1 kolom 3 kali baris 3
+ Baris 1
A =
1 0 0
1
0 1 0
2
0 0 1
3
Dengan demikian, diperoleh:
x1 =
1
x2 =
2
x3 =
3
>>
|
|
clc;
clear;
disp('Penyelesaian SPL Menggunakan
Invers Matriks')
disp('Menentukan Solusi dari Persamaan:
x + y + 2z = 9')
disp(' 2x+4y - 3z = 1')
disp(' 3x+6y - 5z = 0')
A=[1 1 2;2 4 -3;3 6 -5]
b=[9;1;0]
x=inv(A)*b
|
Outputnya:
|
Penyelesaian SPL Menggunakan Invers
Matriks
Menentukan Solusi dari Persamaan: x + y
+ 2z = 9
2x+4y - 3z = 1
3x+6y - 5z = 0
A =
1 1 2
2 4 -3
3 6 -5
b =
9
1
0
x =
1.0000
2.0000
3.0000
|
BAB III
PENUTUP
A.
Kesimpulan
1.
Eliminasi
Gauss adalah suatu cara mengoperasikan nilai-nilai di dalam matriks sehingga
menjadi matriks yang lebih sederhana.
System
persamaannya adalahsebagai berikut:
2.
Dalam
aljabar linear, eliminasi Gauss-Jordan adalah versi dari eliminasi Gauss. Pada
metode eliminasi Gauus-Jordan kita membuat nol elemen-elemen di bawah maupun di
atas diagonal utama suatu matriks. Hasilnya adalah matriks tereduksi yang
berupa matriks diagonal satuan (semua elemen pada diagonal utama bernilai 1,
elemen-elemen lainnya nol).
B.
Saran
Untuk
bisa memahami materi tentang metode numerik maka perlu mengumpulkan banyak
referensi dari berbagai sumber.