Review Operasi Matriks
Menghitung invers matriks? Determinan? Matriks Singular?
Menghitung invers matriks c11 c 21 c11 a11 c a 11 12
c12 c 22
a11 a 21
a12 1 = a 22 0
c12 a 21 c12 a 22 c 21 a11 c 21 a12
0 1
1 0 = c 22 a 21 0 c 22 a 22 1
Determinan Hanya untuk square matrices
a det c
b a ≡ d c
b d
≡ ad − bc
a1 a 2 a 3 det b1 b2 b3 c1 c 2 c3 ≡ a1b 2 c3 − a1b 3 c 2 + a 2 b 3 c1 − a 2 b 1 c3 + a 3b 1 c 2 − a 3b 2 c1
Jika determinan = 0 matriks singular, tidak punya invers
Cari invers nya"
2 2
4 5
1 2
2 4
Sistem Persamaan Linear
Simultaneous Linear Equations
Metode Penyelesaian • • • • •
Metode grafik Eliminasi Gauss Metode Gauss – Jourdan Metode Gauss – Seidel LU decomposition
Metode Grafik 1 2 x1 4 1 − 1 x = 2 2
Det{A} ≠ 0 ⇒ A is nonsingular so invertible Unique solution
-2
2
Sistem persamaan yang tak terselesaikan 1 2
2 x1 4 = 4 x2 5
No solution Det [A] = 0, but system is inconsistent Then this system of equations is not solvable
Sistem dengan solusi tak terbatas Det{A} = 0 ⇒ A is singular infinite number of solutions 1 2
2 x1 4 = 4 x2 8
Consistent so solvable
Ill-conditioned system of equations A linear system of equations is said to be “illconditioned” if the coefficient matrix tends to be singular
Ill-conditioned system of equations • A small deviation in the entries of A matrix, causes a large deviation in the solution. 1 0 .48 1 0 .49
2 x1 3 x1 1 ⇒ = = 0 .99 x 2 1 .47 x 2 1 2 x1 3 ⇒ = 0 .99 x 2 1 .47
x1 3 x = 0 2
Gaussian Elimination Merupakan salah satu teknik paling populer dalam menyelesaikan sistem persamaan linear dalam bentuk:
[A ][X ] = [C ] Terdiri dari dua step 1. Forward Elimination of Unknowns. 2. Back Substitution
Forward Elimination Tujuan Forward Elimination adalah untuk membentuk matriks koefisien menjadi Upper Triangular Matrix
25 64 144
1 25 1 → 0 0 12 1 5 8
5 − 4 .8 0
− 1 .56 0 .7 1
Forward Elimination Persamaan linear n persamaan dengan n variabel yang tak diketahui
a11 x1 + a12 x 2 + a13 x3 + ... + a1n x n = b1
a 21 x1 + a 22 x 2 + a 23 x3 + ... + a 2 n x n = b2 . . .
. . .
a n1 x1 + a n 2 x2 + a n 3 x3 + ... + a nn xn = bn
Contoh 2 x1 + 3 x 2 − 2 x3 − x 4 = − 2 2 x1 + 5 x 2 − 3 x3 + x 4 = 7
matriks input
− 2 x1 + x 2 + 3 x3 − 2 x 4 = 1 − 5 x1 + 2 x 2 − x3 + 3 x 4 = 8
2 2 − 2 − 5
3
−2
−1
5 1
−3 3
1 −2
2
1
3
− 2 7 1 8
Forward Elimination 2 2 − 2 − 5
1 3 2 2 0 0 4 0 19 2
3
−2
−1
5 1
−3 3
1 −2
2
1
3
−1
−1
−1 1
2 −3 1 2
−6
2
− 2 7 1 8
− 1 9 − 1 3
R 1' = R 1
2 R 2' = R 2 − 2 R 1' R 3' = R 3 − 2 R 1' R 4' = R 4 − 5 R 1'
R 1' = R 1 R 2' =
R2
2 R 3' = R 3 + 4 R 2' R 4' = R 4 + 19
2
R 1'
1 3 2 2 0 0 4 0 19 2 1 0 0 0
3
2 1 0 0
−1
−1
−1 1
2 −3 1 2
−6
−1 −1 2 3 −5 4
−1
2
2
1 −7 −9
− 1 9 − 1 3 −1 9 2 − 19 − 159
4
Forward Elimination 1 0 0 0
1 0 0 0
3
2 1 0 0
3
−1 −1 2 3 −5 4
0
−1 −1 2 1
0
0
2 1
−1
−1 9 2 − 19 − 159 4
2
1 −7 −9
−1 1 −7
2
3 − 143 12
R 1' = R 1 R 2' = R 2 R 3' =
3
R = R4 + 5
3 − 572 12 −1 9 2 − 19
R3
' 4
4
R
' 3
R 1' = R 1 R 2' = R 2 R 3' = R 3 R 4' =
R4
− 143 12
1 0 0 0
1 0 0 0
3
0
−1 −1 2 1
0
0
2 1
3
0
−1 −1 2 1
0
0
2 1
−1
2
1 −7
3 − 143 12
−1 1 −7 1
2
3
3 − 572 12 −1 9 2 − 19
3 572 143 −1 9 2 − 19
Back substitution x1 +
x4 = 4
3 x 2 2 x2
− x3 − 1 x3 2 x3
− 1 x4 2 + x4 − 7 x4 3 x4
= −1 =9 2 = − 19 3 = 572 143
Gauss - Jourdan 1 2 3 1 0 0
1 0 0
3 4 4 3 −2 −5
0 1 0
2 3 7
15 22 39
2 15 − 1 − 8 1 − 6
1 2 15 1 2 4 7 2 14
1 0 0
R 1' = R 1 R 2' = R 2 − 2 R 1' R 3' = R 3 − 3 R 1'
1 0 0
R 1' = R 1 − 3 R 2' R 2' = − R 2 2 R 3' = R 3 − 5 R 2'
R 1' = R 1 − 1
3 −2 −5
R 3'
2 R 2' = R 2 − 1 R 3' 2 R R 3' = 3 − 7 2
1 0 0
2 15 − 1 − 8 1 − 6 1 2 15 1 2 4 7 2 14
0 1 0 0 1 0
0 0 1
1 2 4
Warning.. Dua kemungkinan kesalahan -Pembagian dengan nol mungkin terjadi pada langkah forward elimination. Misalkan:
10 x1 − 7 x 2 = 7 6 x3 + 2 .099 x 2 − 3 x1 = 3 .901 5 x1 − x 2 + 5 x3 = 6 - Kemungkinan error karena round-off (kesalahan pembulatan)
Contoh Dari sistem persamaan linear 10 − 3 5
−7 2 .099 −1
0 6 5
x1 7 x 3 .901 2 = x3 6
10 − 3 5
−7 2 .099
0 6
−1
5
7 3 .901 6
Akhir dari Forward Elimination 10 0 0
−7
− 0 .001 6 0 15005 0
x1 7 x = 6 .001 2 x3 15004
10 0 0
−7
0
− 0 .001 6 0 15005
6 .001 15004 7
Kesalahan yang mungkin terjadi Back Substitution x3 = 10 0 0
−7 − 0 .001 0
x1 7 x = 6 .001 2 15005 x 3 15004 0 6
15004 = 0 .99993 15005
6 .001 − 6 x3 x2 = = − 1 .5 − 0 .001
7 + 7 x 2 − 0 x3 x1 = = − 0 .3500 10
Contoh kesalahan Bandung-kan solusi exact dengan hasil perhitungan
[X ] exact [X ] calculated
x1 0 = x 2 = − 1 x 3 1 x1 − 0 .35 = x 2 = − 1 .5 x 3 0 .99993
Improvements Menambah jumlah angka penting Mengurangi round-off error (kesalahan pembulatan) Tidak menghindarkan pembagian dengan nol
Gaussian Elimination with Partial Pivoting Menghindarkan pembagian dengan nol Mengurangi round-off error
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:
a kk , a k +1, k ,......... ......., a nk
Jika nilai maksimumnya Maka tukar baris p dan k.
a pk
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 x 2 = 7 − 3 x1 + 2 .099 x 2 + 6 x3 = 3 .901 5 x1 − x 2 + 5 x3 = 6 In matrix form
10 − 3 5
−7 2 .099 −1
0 6 5
x1 7 x 3 .901 2 = x 3 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 − 3 5
−7 2 .099 −1
0 x1 7 6 x 2 = 3 .901 5 x3 6
⇒
10 0 0
−7 − 0 .001 2 .5
0 x1 7 6 x 2 = 6 .001 5 x 3 2 .5
Partial Pivoting: Example Forward Elimination: Step 2 Examining the values of the first 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 0
−7 − 0 .001 2 .5
0 x1 7 6 x 2 = 6 .001 5 x 3 2 .5
⇒
10 0 0
−7 2 .5 − 0 .001
0 x1 7 5 x 2 = 2 .5 6 x3 6 .001
Partial Pivoting: Example Forward Elimination: Step 2
Performing the Forward Elimination results in:
10 0 0
−7 2 .5 0
0 x1 7 5 x 2 = 2 .5 6 .002 x 3 6 .002
Partial Pivoting: Example Back Substitution Solving the equations through back substitution
10 0 0
−7 2 .5 0
0 x1 7 5 x 2 = 2 .5 6 .002 x 3 6 .002
6 .002 x3 = =1 6 .002
2 .5 − 5 x 2 x2 = =1 2 .5 7 + 7 x 2 − 0 x3 x1 = =0 10
Partial Pivoting: Example Compare the calculated and exact solution The fact that they are equal is coincidence, but it does illustrate the advantage of Partial Pivoting
[X ] calculated
x1 0 = x 2 = − 1 x3 1
[X ] exact
x1 0 = x 2 = − 1 x 3 1
Summary -Forward Elimination -Back Substitution -Pitfalls -Improvements -Partial Pivoting
