e-tp.ub.ac.id
Persamaan Linier Simultan II
Arif Hidayat TPI4104 – Matematika Industri
Eliminasi Gauss a11 a21
a12 a22
a13 x1 a23 * x2
b1 b2
....... E1 ....... E2
a31
a32
a33
b3
....... E3
x3
Forward Elimination
a11 a12 ' 0 a22 0
0
a13 x1 ' a23 * x2
b1 b2'
'' a33
b3''
x3
Back Substitution
x3
'' b3'' / a33
x2
' ' (b2' a23 x3 ) / a22
x1
(b1
a12 x2 a13 x3 ) / a11
Eliminasi Gauss Proses Forward Elimination : 1. Eliminasikan x1 dari E2 dan E3 Hitung: m21 = a21/a11 E’2 = E2 - m21*E1 Hitung: m31 = a31/a11 E’3 = E3 – m31*E1 2. Eliminasikan x2 dari E’3 Hitung: m32 = a’32/a’22 E’’3 = E’3 – m32*E’2 Proses Back Substitution : 1. x3 = b’’3 / a’’3
2. x2 = (b’2 – a’23*x3) / a’22 x1 = (b1 - a12*x2 - a13*x3) / a11
a11 a12 ' 0 a22 0
' a32
a11 a12 ' 0 a22 0
0
....... E1
a13 x1 ' a23 * x2
b1 b2'
....... E2'
' a33
x3
b3'
....... E3'
a13 x1 ' a23 * x2
b1 b2'
....... E1 ....... E2'
'' a33
b3''
....... E3''
x3
Eliminasi Gauss x + y + 2z = 9 2x + 4y – 3z = 1 3x + 6y – 5z = 0
ditulis dalam bentuk matriks augmented
lalu diusahakan berbentuk
1 1 2
9
2 4 -3
1
3 6 -5
0
1 1 2
9
0 ? ?
?
0 0 ?
?
dengan proses Operasi Baris Elementer (OBE) (Elementary Row Operation - ERO)
Eliminasi Gauss Operasi Baris Elementer (OBE) (Elementary Row Operation - ERO) 1 1 2
9
2 4 -3
1
baris-2 + (-2) x baris-1
1 1 2
9
0 2 -7
-17
0 3 -11
-27
baris-3 + (-3) x baris-1
3 6 -5
0
baris-3 + (-3/2)x baris-2
1 1 2 0 2 -7 0 0 -½
9 -17 -3/2
Eliminasi Gauss x
y
z
1 0 0
1 2 0
2 -7 -½
9 -17 -3/2
1 0 0
1 2 0
2 -7 -½
9 -17 -3/2
1 0 0
1 2 0
2 -7 -½
9 -17 -3/2
Substitusi Balik: -1/2 z = -3/2
z =3
z
2y – 7z = - 17 2y = 21 – 17
y=2
y
x + y + 2z = 9 x =–2–6+9
x =1
z
Eliminasi Gauss Eliminasi Gauss (ringkasan): Sistem Persamaan → Linier
Matriks Augmented
→
OBE
Eliminasi → Substitusi Gauss Balik
Latihan Selesaikan dengan eliminasi gauss
2 x 6 y 10z 0 x 3 y 3z 2 3x 14 y 28z 8
Latihan 2 x 6 y 10z 0 x 3 y 3z 2 3x 14 y 28z 8
x3 x2 x1
1 1 13( 1) 8 1 5 1 6(1) 10( 1) 0 2
2
2 1
6 10 | 3 3 |
0 2
3 14 28 |
8
2 6 0 0
10 | 2 |
0 2
0 5
13 |
8
2 6 0 5
10 | 13 |
0 8
0 0
2 |
2
Eliminasi Gauss-Jordan a11 a21
a12 a22
a13 x1 a23 * x2
b1 b2
a31
a32
a33
b3
x3
Forward Elimination NO Back Substitution
x1
b1*
0 1 0 * x2 0 0 1 x3
b2* b3*
1 0 0
x1
b1*
x2
b2*
x3
b3*
Eliminasi Gauss-Jordan x + y – z = -2
1 1 -1
-2
2x – y + z = 5
2 -1 1
5
-x + 2y + 2z = 1
-1 2
1
diusahakan berbentuk
1 0 0 0 1 0
? ?
0 0 1
?
2
dengan proses Operasi Baris Elementer (OBE) (Elementary Row Operation - ERO)
Eliminasi Gauss-Jordan Di kolom pertama posisi diagonal sudah terdapat angka 1, dibawahnya harus diubah menjadi nol. Nol yang pertama didapat dengan mengalikan baris pertama dengan -2 dan menambahkan hasilnya ke baris 2:
Baris 1 tidak berubah (-2) kali baris 1 ditambahkan ke baris 2 Baris 3 tidak berubah
Eliminasi Gauss-Jordan
Nol yang kedua didapat dengan menambah kan baris 1 ke baris 3 (mengalikan baris 1 dengan 1 dan menambahkan hasilnya ke baris 3) Baris 1 tidak berubah baris 2 tidak berubah Baris 1 ditambahkan ke baris 3
Eliminasi Gauss-Jordan
Di Kolom 2, posisi diagonal diupayakan ber nilai 1 (nilai saat ini -3). Untuk mendapatkkan nya, tiap eleman di baris 2 dibagi -3 Baris 1 tidak berubah Baris 2 dibagi -3 Baris 3 tidak berubah
Eliminasi Gauss-Jordan
Untuk mendapatkan 0 dibawah nilai 1 di kolom 2, baris 2 dikalikan dengan -3 dan di jumlahkan ke baris 3 Baris 1 tidak berubah Baris 2 tidak berubah (-3) kali baris 2 di tambahkan ke baris 3
Eliminasi Gauss-Jordan
Untuk mendapatkan 1 di posisi diagonal kolom 3, baris 3 dibagi dengan 4 Baris 1 tidak berubah Baris 2 tidak berubah Baris 3 dibagi 4
Eliminasi Gauss-Jordan
Operasi dilanjutkan ke atas. Untuk men dapatkan nilai 0 di kolom 3: Baris 3 ditambahkan ke baris 2 Baris 3 ditambahkan ke baris 1 Baris 3 tidak berubah
Eliminasi Gauss-Jordan Untuk mendapat matriks identitas, nilai 1 Di baris 1 kolom 2 harus diubah menjadi 0. Sehingga baris 2 dikalikan dengan -1 dan hasilnya ditambahkan ke baris 1. Baris 2 dan 3 tidak berubah
Eliminasi Gauss-Jordan Dari matriks terakhir ini, bisa dilihat bahwa Solusi masalah adalah
Latihan Selesaikan dengan eliminasi Gauss-Jordan
x 3 y 2 z 15 2 x 4 y 3z 22 3x 4 y 7 z 39
Latihan 1 3 2 15 2 4 3 22 3 4 7 39
1 0
3 2
0
5
1 0
3 2
0
5
' R 2 15 1 ' 1 8 R2 ' 1 6 R3
R1 R2
2 R1'
R3
3R1'
2 15 R1' R1 3R2' R2 2 1 8 R2' 1
' 6 R3
R3
5 R2' 1 R' 2 3 1 R' 2 3
1 0 1 2 15 0 1 12 4
R1'
R1
R2'
R2
0 0 7 2 14
R3'
R3
7 2
Latihan 1 0 0 1 0 1 0 2 0 0 1 4
Sehingga : X=1 Y=2 Z=4
LU Factorization Sebuah matriks Anxn dapat ditulis sebagai sebuah produk dari matriks segitiga bawah (L) dan matriks segitiga atas (U), sehingga A = LU Matriks Segitiga Atas Square matriks dengan elemen dibawah diagonal utama adalah nol
Matriks Segitiga Bawah Square matriks dengan elemen diatas diagonal utama adalah nol
1 4
3
0 6
0
0 0
2
1
0
0
6
1
0
5
7 3
LU Factorization Misalkan sistem persamaan linier ditulis dalam Ax =b Jika A dapat difaktorkan dalam L dan U, maka LUx = b Jika Ux = y, maka Ly =b Sehingga, langkah penyelesaian persamaan linier dengan LU Factorization: Nyatakan y = Ux dan selesaikan Ly = b untuk y Selesaikan Ux = y untuk x
LU Factorization Matriks U adalah hasil eliminasi Gauss dari matriks asal, sedangkan L adalah faktor pengali dalam eliminasi gauss tersebut untuk baris yang bersangkutan. Contoh: cari faktor L dan U dari matriks A 1
3 0
0
1 3
2
10 2
1
3 0
0
1 3
0
4 2 R3'
R3'
R3
3 0 1 3
2
10 2
2R1
U R3
1 0
( 4R2 )
1 0
3 1
0 3
0
0 14
L
1
0 0
0
1 0
2
4
1
Selesaikan dengan LU Factorization x1
3 x2 x2 10x2
2 x1
A
5 1 20
3x3 2 x3
1
3 0
1
0 0
1
3
0
0
1 3
0
1 0
0
1
3
2
10 2
2
4 1 0
LU
0 14
(1) Selesaikan Ly b 1 0 2
0 0 1 0 4 1
y1 y2 y3
5 1 20
y1 y2 y3
5 1 20 2 y1 4 y2 20 2( 5) 4( 1)
14
(2) Selesaikan Ux 1 0 0
3 0 1 3 0 14
Sehingga x3 x2 x1
y x1 x2 x3 1 1 3 x3
1 (3)( 1)
5 3 x2
5 3(2) 1
Solusi persamaan adalah
x
1 2 1
5 1 14
2
Latihan Selesaikan dengan LU Factorization 80x1 20x1
20x2 40x2
20x3 20x3
20 20
20x1
20x2
130x3
20
Kelemahan Eliminasi
Kesalahan karena pembulatan Pembagian dengan nol dalam operasi baris
Solusi 1. Menambah angka penting - mengurangi kesalahan karena pembulatan - tidak menghindarkan pembagian dengan nol 2. Eliminasi Gauss dengan partial pivoting - mengurangi kesalahan karena pembulatan - menghindarkan pembagian dengan nol
Kesalahan karena pembulatan Dari sistem persamaan linear
10 7 0 3 2.099 6
x2
5
x3
1
5
x1
10 7 0 7 3 2.099 6 3.901
7 = 3.901 6
5
1
5 6
Akhir dari Forward Elimination 7
10
7
0
x1
0
0.001
6
x2 = 6.001
10 0
15004
0
0
0
15005
x3
7 0.001 0
0 6
7 6.001
15005 15004
Kesalahan karena pembulatan Back Substitution x3 10 0 0
7 0.001 0
0 6
x1 x2
7 6.001
15005 x3
15004
x1
x2
15004 0.99993 15005
6.001 6 x3 0.001
7 7 x 2 0 x3 10
1.5
0.3500
Kesalahan karena pembulatan Bandingkan solusi exact dengan hasil perhitungan
X
X
exact
calculated
x1 x2
0 1
x3
1
x1 x2 x3
0.35 1.5 0.99993
Kesalahan karena pembulatan Bandingkan solusi exact dengan hasil perhitungan
X
X
exact
calculated
x1 x2
0 1
x3
1
x1 x2 x3
0.35 1.5 0.99993
Pembagian dengan nol
Consider this system: 0
1
2
2
3
8
Immediately run into problem: algorithm wants us to divide by zero!
Pivoting Eliminasi Gauss dengan partial pivoting mengubah tata urutan baris untuk bisa mengaplikasikan Eliminasi Gauss secara Normal How? Di awal sebelum langkah ke-k pada forward elimination, temukan angka maksimum dari:
akk , ak
Jika nilai maksimumnya Maka tukar baris p dan k.
1, k
a pk
,......... ......., ank Pada baris ke p,
k
p n,
Partial Pivoting What does it Mean? Gaussian Elimination with Partial Pivoting ensures that each step of Forward Elimination is performed with the pivoting element |akk| having the largest absolute value. Jadi,
Kita mengecek pada setiap langkah apakah angka paling atas (pivoting element) adalah selalu paling besar
Partial Pivoting: Example Consider the system of equations
10 x1 7 x2
7
3 x1 2.099x2 5 x1
x2 5 x3
6 x3
3.901
6
In matrix form
x1
10 7 0 3 2.099 6
x2
5
x3
1
5
7 = 3.901 6
Solve using Gaussian Elimination with Partial Pivoting using five significant digits with chopping
Partial Pivoting: Example Forward Elimination: Step 1 Examining the values of the first column |10|, |-3|, and |5| or 10, 3, and 5
The largest absolute value is 10, which means, to follow the rules of Partial Pivoting, we don’t need to switch the rows Performing Forward Elimination
10 7 0 x1 3 2.099 6 x2 5
1
5 x3
7 3.901
10 0
7 0 x1 0.001 6 x 2
6
0
2.5
5 x3
7 6.001 2.5
Partial Pivoting: Example Forward Elimination: Step 2 Examining the values of the second column |-0.001| and |2.5| or 0.0001 and 2.5
The largest absolute value is 2.5, so row 2 is switched with row 3 Performing the row swap
10 0
7 0 x1 0.001 6 x 2
0
2.5
5 x3
7 6.001
10 0
2.5
0
7 2.5
0 x1 5 x2
0.001 6 x3
7 2.5 6.001
Partial Pivoting: Example Forward Elimination: Step 2
Performing the Forward Elimination results in:
10 7 0 2.5 0
0
0 5
x1 x2
6.002 x3
7 2.5 6.002
Partial Pivoting: Example Back Substitution Solving the equations through back substitution
10 7 0 2.5 0
0
0 5
x1 x2
6.002 x3
x3
7 2.5 6.002
2.5 5 x 2 2.5
1
7 7 x 2 0 x3 10
0
x2 x1
6.002 1 6.002
Partial Pivoting: Example Compare the calculated and exact solution
X
calculated
x1 x2
0 1
x3
1
X
exact
x1 x2
0 1
x3
1
Partial Pivoting: Example
0
1
2
2
3
8
Swap rows 1 and 2:
Now continue:
2
3
8
0
1
2
1
3
2
4
1
0
1
0
1
2
0
1
2
Iterasi Jacobi Untuk sistem linier berukuran besar, dimana biasanya banyak element matriksnya adalah 0, biasanya solusi bisa diperoleh lebih efisien dengan metode iterasi dibanding eliminasi. Beberapa metode iterasi antara lain Jacobi, Gauss-Seidel dan SOR. Iterasi Jacobi, dimulai dengan perkiraan awal variabel yang dicari (biasanya nol), kemudian dilanjutkan secara simultan untuk semua nilai yang dicari. Iterasi diteruskan hingga hasil iterasi ke n hampir sama dengan nilai iterasi ke n-1
Iterasi Jacobi Rumus perhitungan nilai variabel :
X
(k i) i
(k ) i
x
(k ) i
R ai ,i
(i 1,2....... n)
n (k ) i
R
bi
ai , j X j 1
(k ) j
(i 1,2....... n)
Contoh 4X1 – X2 + X4 – X1 + 4X2 –X3 + X5 – X2 + 4X3 – X4 X1 – X3 + 4X4 – X5 X2 – X4 + 4X5
= 100 = 100 = 100 = 100 = 100
Persamaan ini dapat ditulis dalam: R1 = 100 – (4X1 – X2 + X4) R2 = 100 – (– X1 + 4X2 –X3 + X5) R3 = 100 – (– X2 + 4X3 – X4 ) R4 = 100 – (X1 – X3 + 4X4 – X5) R5 = 100 – (X2 – X4 + 4X5)
Contoh Dengan perkiraan awal x(0) = [0 0 0 0 0], didapat R1-5 = 100 dan X1-5 = 25. Prosedur ini diteruskan dengan hasil sbb: k
X1
X2
X3
X4
X5
0
0
0
0
0
0
1
25
25
25
25
25
2
25
31,25
37,5
31,25
25
………….
………….
………….
………….
………….
………….
17
25
35,714285 42,857142 35,714285
25
18
25
35,714285 42,857143 35,714285
25
Iterasi Gauss-Seidel Mirip dengan Iterasi Jacobi, hanya di metode ini nilai yang diperoleh langsung dimasukkan dalam perhitungan berikutnya
X
(k i) i
(k ) i
x
(k ) i
R ai ,i
i 1 (k ) i
R
bi
n
ai , j X j 1
(i 1,2....... n)
(k ) j
ai , j X j 1
(k ) j
(i 1,2....... n)
Contoh Dengan iterasi Gauss-Seidel, soal diatas dapat dipecahkan dengan iterasi lebih sedikit k
X1
X2
X3
X4
X5
0
0
0
0
0
0
1
25
31,25
32,8125
2
…………. 14 15
26,953125 23,925781
26,074219 33,740234 40,173340 34,506226 25,191498
………….
………….
………….
………….
25,000001 35,714286 42,857143 35,714285 25
35,714286 42,857143 35,714286
…………. 25 25
