03-Pemecahan Persamaan Linier (2) Dosen: Anny Yuniarti, M.Comp.Sc Gasal 2011-2012
Anny2011
1
Agenda • Bagian 1: Matriks Invers • Bagian 2: Eliminasi = Faktorisasi: A = LU • Bagian 3: Transpos dan Permutasi
Anny2011
2
Bagian 1
MATRIKS INVERS
Anny2011
3
Pendahuluan • Matriks invers dari sebuah matriks persegi A dinotasikan dengan A-1. – A-1A = I – A-1Ax = x
• Sebuah matriks A mungkin juga tidak memiliki inversnya (A-1 tidak eksis) • Perkalian A-1 dengan Ax = b menghasilkan A-1Ax = A-1b x = A-1b
Anny2011
4
Definisi • Sebuah matriks dikatakan invertible jika terdapat sebuah matriks A-1 sedemikian hingga A-1A = I dan AA-1 = I. • Tidak semua matriks memiliki invers • Invers akan ada jika dan hanya jika eliminasi menghasilkan n pivot (pertukaran baris dibolehkan). • Eliminasi dapat menghasilkan solusi Ax = b tanpa secara eksplisit menghitung A-1.
Anny2011
5
Definisi (2) • Sebuah matriks tidak mungkin memiliki dua matriks invers yang berbeda. Misal BA = I, AC = I, maka B = C B(AC) = (BA)C BI = IC B = C
• Jika A memiliki invers (invertible), maka satusatunya solusi Ax = b adalah x = A-1b. • Misal terdapat vektor bukan nol x sedemikian hingga Ax = 0, maka A tidak memiliki invers.
– Jika A invertible, maka Ax = 0 hanya memiliki solusi x = A-10 = 0 (zero vector) Anny2011
6
Definisi (3) • Sebuah matriks 2x2 mempunyai invers (invertible) jika dan hanya jika ad – bc tidak sama dengan nol – Nilai ad – bc adalah determinan matriks A.
• Sebuah matriks diagonal memiliki invers jika tidak terdapat nilai nol pada diagonalnya.
Anny2011
7
Contoh 1 • Apakah matriks A berikut memiliki invers? Sebutkan tiga alasannya. A
• Tidak
1 2 1 2
1. Determinan A = 0 2. Jumlah pivot yang tidak sama dengan 0 hanya 1 (bukan 2) 3. Ax = 0 untuk x = (2, -1) Anny2011
8
Invers Perkalian Matriks AB • Hasil perkalian matriks AB memiliki invers jika dan hanya jika matriks A dan B masingmasing memiliki invers dan ukurannya sama. • Invers matriks AB: AB-1 = B-1A-1
– AA-1 = I – (AB) B-1A-1 =A(BB-1)A-1 = AIA-1 =AA-1 = I
• Aturan reverse order :
Anny2011
9
Contoh 2 • Jika matriks eliminasi E mengurangi 5 kali baris pertama dari baris kedua, invers matriks E-1 menambahkan 5 kali baris pertama ke baris kedua.
• Matriks persegi memiliki karakteristik jika AB = I maka BA = I Anny2011
10
Eliminasi Gauss-Jordan • Meski persamaan Ax = b dapat dipecahkan dengan x = A-1b, menghitung A-1 kemudian mengalikannya dengan b kadang kurang efisien.
• Dengan eliminasi solusi x dapat langsung dicari. • Dengan eliminasi juga, matriks invers A-1 juga dapat dihasilkan • Ide dasar Gauss-Jordan adalah mencari solusi AA-1 = I, yakni dengan menentukan setiap kolom matriks A-1. Anny2011
11
Eliminasi Gauss-Jordan (2) • Matriks A dikalikan kolom pertama matriks A-1 (sebut kolom ini x1) menghasilkan kolom pertama matriks I (sebut kolom ini e1) • Persamaannya:
Ax1 = e1 = (1, 0, 0)
• Dua persamaan yang lain: Ax2 = e2 = (0, 1, 0) Ax3 = e3 = (0, 0, 1)
Anny2011
12
Eliminasi Gauss-Jordan (3) • Metode Gauss-Jordan menghitung A-1 dengan mencari solusi ketiga persamaan tsb (jika matriksnya 3x3), atau n persamaan jika matriksnya nxn. • Misal terdapat sebuah matriks K: • Matriks identitas I:
2 1 0
1 0 0 0 1 0
1 2 1
0 1 2
0 0 1
• Untuk mencari K-1:
– Matriks gabungan [K I]:
2 1
1 2
0
1
0 1 0 0 1 0 1 0 2
0 0 1
– Lakukan eliminasi dengan meng-nol-kan elemen dibawah pivot pertama: 2 1 0 1 0 0 0
3 2
1
1 2
1 0
0
1
2
0 0 1
2
1
0
1 0 0
– Lakukan eliminasi dengan meng-nol-kan elemen dibawah pivot kedua: 0 0
3 2
0
1 4 3
1 2 1 3
1 0 Anny2011 2 1 3
13
Eliminasi Gauss-Jordan (4) 2
1
0
3 2
0
0
0 1 4 3
1 0 0 1 2 1 3
1 0 2 3
1
• Matriks diatas 3 kolom pertamanya adalah U (upper triangular), pivot pada diagonalnya adalah 2, 3/2, dan 4/3. • Selanjutnya metode Gauss-Jordan menghasilkan bentuk reduksi (nilai nol diatas pivot: 2 0
1 0 1 0 0 3 0 34 32 34 2
0
0
4 3
1 3
2 3
2 0 0 0 32 0 0 0
1
Anny2011
4 3
3 2 3 4 1 3
1 3 2 2 3
1 2 3 4
1
14
Eliminasi Gauss-Jordan (5) 3 2 3 4 1 3
2 0 0 0 32 0 0 0
4 3
1 2 3 4
1 3 2 2 3
1
• Langkah terakhir metode Gauss-Jordan adalah membagi setiap baris dengan nilai pivot pada baris yang bersangkutan, sehingga pivot yang baru adalah 1: 1 0 0 0 1 0 0 0 1
3 4 1 2 1 4
1 2
1 1 2
1 4 1 2 3 4
• Tiga kolom terakhir matriks diatas adalah K-1 yang dicari Anny2011
15
Karakteristik Matriks K dan K-1 2 K
1 0
1 2 1
0 1 2
K
1
3 4 1 2 1 4
1 2 1 1 2
1 4 1 2 3 4
3 2 1 1 2 4 2 4 1 2 3
• Matriks K symmetric pada diagonal utamanya, begitu pula matriks K-1. • Matriks K tridiagonal (hanya tiga nilai bukan nol pada diagonalnya). Matriks K-1 adalah dense matrix tanpa ada nilai nol. • Hasil perkalian pivot matriks U: 2*(3/2)*(4/3) = 4. Nilai 4 ini merupakan determinan dari K.
Anny2011
16
Contoh 1 •
2 3 Untuk matriks A = 4 7 ,
tentukan A-1 dengan eliminasi Gauss-Jordan.
• [A I] = 2 3 1 0 4 7 0 1
2 3
• Langkah 1 Eliminasi:
0 1
• Langkah 2 Eliminasi:
2 0 0 1
• Dibagi dengan pivot: • A-1 =
7 2 2
3 2 1
1 0 0 1
1
0
2 1 7
3
2
1
7 2 2
3 2 1
Anny2011
17
Contoh 2 • Untuk matriks L =
1 0 0 3 1 0 4 5 1
,
tentukan L-1 dengan eliminasi Gauss-Jordan. 1 0 0 1 0 0
• [L I] =
3 1 0 0 1 0 4 5 1 0 0 1
• Langkah 1 Eliminasi:
• Langkah 2 Eliminasi: • Langkah 3 Eliminasi :
• L-1 =
1 3 11
0
0
1
0
1 0 0
1
0 1 0 4 5 1 1 0 0
0 0
3 1 0 0 1
0 1 0 0
0 1 0
3 1 0
0 5 1 1 0 0
4 0 1 1 0 0
0 1 0
3
0 0 1
11
1
0
5 1
5 1 Anny2011
18
Bagian 2
ELIMINASI = FAKTORISASI: A = LU Anny2011
19
Faktorisasi Matriks • Matriks A merupakan hasil perkalian dua atau tiga matriks spesial yang lain. • Dari eliminasi, faktor matriks A adalah matriks triangular L dan U: A = LU.
– U: matriks upper triangular dengan nilai-nilai pivot pada diagonalnya. Dengan eliminasi matriks A dapat diubah menjadi U. – L: matriks lower triangular yang dapat digunakan untuk mengubah matriks U kembali menjadi A.
Anny2011
20
Faktorisasi Matriks (2) • Matriks A berukuran 2x2:
2 1 6 8
• Baris kedua diatas adalah faktorisasi matriks A: LU = A • Untuk matriks 3x3, matriks A akan dikalikan dengan E21, E31, dan E32 untuk menjadi matriks U. – asumsi tidak ada pertukaran baris pada matriks A
• Jika invers dari matriks-matriks eliminasi dikalikan dengan sistem, dihasilkan A = (E21-1E31-1E32-1)U = LU. Anny2011
21
Faktorisasi Matriks (3) • • • • •
A = LU adalah eliminasi tanpa ada pertukaran baris pada A. Matriks U memiliki nilai-nilai pivot pada diagonalnya. Matriks L memiliki nilai 1 pada diagonalnya. Pengali lij berada di bawah diagonal matriks L. Misal, matriks A = 2 1 0 1 2 1 0 1 2
• Eliminasi akan mengurangkan ½ kali baris 1 dari baris 2, l21 = ½, kemudian mengurangkan 2/3 kali baris 2 dari baris 3, l32 = 2/3. • Berapa L? Berapa U? • Perkalian LU menghasilkan A:
Anny2011
22
Contoh • Sebuah matriks 4x4: • Tentukan matriks L dan U! • Pola spesial:
– Jika sebuah baris pada A berawal dengan nol, begitu pula baris pada L – Jika sebuah kolom pada A berawal dengan nol, begitu pula kolom pada U Anny2011
23
A = LDU • Diagonal matriks L bernilai 1 • Diagonal matriks U berisi nilai pivot
• Jika matriks U dibagi dengan pivotnya, akan dihasilkan matriks U yang diagonalnya bernilai 1
Anny2011
24
Bagian 3
TRANSPOS DAN PERMUTASI
Anny2011
25
Transpos • Transpos matriks lower triangular adalah matriks upper triangular • Transpos A + B = (A + B)T = AT + BT
• Transpos AB = (AB)T = BTAT
Jika A = LDU, berapa AT?
• Transpos A-1 = (A-1)T = (AT)-1 Anny2011
26
Inner Product • Jika ada dua vektor x dan y, berapa inner product dari x dan y? • Nilai tsb dapat juga diperoleh menggunakan perkalian matriks: xTy • AT adalah matriks yang menjadikan dua nilai inner product dari x dan y sama:
Anny2011
27
Matriks Simetrik • Matriks simetrik: AT = A • Contoh: • Invers matriks simetrik menghasilkan matriks simetrik juga • Contoh:
Anny2011
28
Matriks Simetrik • Sebuah matriks berukuran m x n jika ditranspos kemudian dikalikan dengan matriks tsb menghasilkan matriks persegi simetrik – (m x n)T n x m – (n x m)(m x n) (n x n)
• Menggunakan karakteristik transpos perkalian matriks, berapa transpos dari RTR? • (RTR)T = RT(RT)T = RTR Anny2011
29
Matriks Simetri pada Eliminasi
• Jika A matriks simetrik, bentuk A = LDU berubah menjadi A = LDLT
• Perhatikan transpos dari LDLT! • (LDLT)T = (LT)TDTLT = LDLT Anny2011
30
Matriks Permutasi • Karakteristik matriks permutasi P: – Memiliki satu nilai “1” di setiap baris dan di setiap kolom – Jika ditranspos akan menghasilkan matriks permutasi juga – Perkalian antar matriks permutasi menghasilkan matriks permutasi juga – Dibentuk dari matriks identitas I, kemudian baris-barisnya ditukar Anny2011
31
Matriks Permutasi 3x3 • Terdapat 6 matriks permutasi 3x3: – I, P21, P31, P32, P32P21, P21P32
• Untuk matriks dengan orde n, ada berapa matriks permutasi? n!
• P-1 juga matriks permutasi • P-1 = PT Anny2011
32
PA = LU • Pada eliminasi, kadang pertukaran baris diperlukan, sehingga P…E…P…E…A = U A = (E-1…P-1…E-1…P-1…)U
• Jika pertukaran baris direpresentasikan menggunakan sebuah matriks permutasi P, ada dua kemungkinan cara melakukan semua pertukaran baris yang diperlukan: – sebelum eliminasi, sehingga PA = LU – sesudah eliminasi, sehingga A = L1P1U1 MATLAB menggunakan PA = LU Anny2011
33
Latihan Pertemuan 3 • Chapter 2.5 – Problem 3, 4, 25, 27
• Chapter 2.6 – Problem 1, 2, 5
• Chapter 2.7 – Problem 20, 24, 31
Anny2011
34
