Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
PAM 252 Metode Numerik Bab 3 Sistem Persamaan Linier Mahdhivan Syafwan Jurusan Matematika FMIPA Universitas Andalas
Semester Genap 2013/2014
1
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review matriks Review sistem persamaan linier (SPL)
Bentuk-bentuk khusus matriks persegi
Matriks simetrik Matriks diagonal Matriks identitas Matriks segitiga atas Matriks segitiga bawah Matriks tridiagonal Matriks Hessenberg
2
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review matriks Review sistem persamaan linier (SPL)
Bentuk umum Bentuk umum dari SPL: a11 x1 + a12 x2 a21 x1 + a22 x2 .. .. . . an1 x1
+
an2 x2
+ ··· + + ··· +
a1n xn a2n xn .. .
= =
b1 b2 .. .
+ ··· +
ann xn
=
bn
Dalam bentuk matriks, SPL di atas dapat ditulis dengan Ax = b, dimana
A=
a11 a21 .. .
a12 a22 .. .
· · · a1n · · · a2n .. .
an1
an2
· · · ann
Apakah solusi untuk x = [x1 3
Mahdhivan Syafwan
,
x2
x=
x1 x2 .. . xn
... xn ]T ?
,
b=
b1 b2 .. . bn
Metode Numerik: Sistem Persamaan Linier
.
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review matriks Review sistem persamaan linier (SPL)
Tentang solusi SPL Ada tiga kemungkinan mengenai solusi SPL: (a) Tidak ada solusi (b) Tak-hingga solusi (c) Solusi tunggal Tafsiran geometris:
4
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review matriks Review sistem persamaan linier (SPL)
Matriks koefisien, matriks lengkap SPL, dan OBE Pada persamaan sebelumnya, A disebut matriks koefisien. Matriks yang dibentuk oleh matriks A dengan penambahan vektor kolom b disebut matriks lengkap dari SPL, yaitu a11 a12 · · · a1n b1 a21 a22 · · · a2n b2 .. .. .. .. . . . . . an1 an2 · · · ann
bn
Operasi baris elementer (OBE):
Menukarkan dua buah baris Mengalikan suatu baris dengan suatu konstanta tak-nol Menambahkan k kali baris ke-i pada baris ke-j
Sifat: OBE tidak mengubah penyelesaian SPL. 5
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review matriks Review sistem persamaan linier (SPL)
SPL segitiga atas Bentuk umum dari SPL segitiga atas: a11 x1
+
a12 x2 a22 x2
+ ··· + + ··· + .. .
Matriks lengkap dari SPL segitiga atas: a11 a12 · · · a1n a22 · · · a2n .. .. . . ann
a1n x1 a2n x2 .. .
= =
b1 b2 .. .
ann xn
=
bn
b1 b2 .. . bn
.
Sifat: SPL segitiga atas mempunyai solusi tunggal jika dan hanya jika setiap elemen diagonal dari matriks koefisiennya tidak nol, yaitu akk 6= 0, k = 1, 2, ..., n. 6
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review matriks Review sistem persamaan linier (SPL)
Substitusi mundur Solusi dari SPL segitiga atas dapat dihitung sebagai berikut: xn xn−1 xn−2
xk
= bn /ann = (bn−1 − an−1 xn )/an−1,n−1 = (bn−2 − (an−2,n−1 xn−1 + an−2,n xn ))/an−2,n−2 .. . ! n X = bk − aki xi /akk i =k+1
.. .
x1
=
b1 −
n X
a1i xi
i =2
!
/a11
Proses perhitungan di atas dinamakan substitusi mundur, karena ... 7
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review matriks Review sistem persamaan linier (SPL)
Algoritma substitusi mundur Apa saja yang harus diperhatikan? Dalam setiap iterasi, sebelum nilai xk dihitung, dilakukan pemeriksaan terlebih dahulu terhadap elemen diagonal akk (proses dihentikan jika ...) ˜ adalah matriks lengkap. Maka vektor b berada pada Misalkan A ˜ kolom ke ... dari matriks A.
8
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review matriks Review sistem persamaan linier (SPL)
Algoritma substitusi maju?
9
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Metode eliminasi Gauss - contoh Dengan menggunakan metode eliminasi Gauss, selesaikan SPL berikut ini: −x1 + x2 + 2x3 = 1, 3x1 − x2 + x3 = 1, −x1 + 3x2 + 4x3 = 1.
10
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Dua tahap besar pada metode eliminasi Gauss
11
1
Tahap eliminasi (maju), yaitu mengubah SPL semula menjadi SPL segitiga atas melalui serangkaian OBE (operasi ini tidak mengubah solusi dari SPL semula).
2
Tahap substitusi mundur, yaitu menyelesaikan SPL segitiga atas yang terbentuk.
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Metode eliminasi Gauss - tahap eliminasi Langkah pertama: membuat agar elemen-elemen kolom pertama mulai baris ke-2, 3, ..., n (yaitu a11 , a21 , ..., an1 ) menjadi nol. a11 a12 · · · a1n a1,n+1 a11 a12 · · · a1n a1,n+1 a21 a22 · · · a2n a2,n+1 0 a22 · · · a2n a2,n+1 .. .. .. .. .. .. ∼ .. .. . . . . . . . . an1
an2
· · · ann
an,n+1
0
an2
· · · ann
an,n+1
Catatan:
Notasi ∼ menyatakan bahwa proses yang dilakukan adalah melalui serangkaian OBE. Elemen-elemen pada kedua matriks lengkap di atas menggunakan notasi yang sama, yaitu aij . Hal ini tidak berarti bahwa nilainya juga sama. Pemakaian notasi yang sama ini ditujukan untuk keperluan pada pemograman komputer. 12
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Metode eliminasi Gauss - tahap eliminasi Langkah pertama - ilustrasi a11 a21 a 31 . . . an1
a12 a22 a32 . . . an2
a11 a21 a31 . . . an1
a12 a22 a32 . . . an2
··· ··· ···
··· ··· ··· ···
···
a1n a2n a3n . . . ann
a11 a1,n+1 0 a2,n+1 a21 a3,n+1 (b)2 ←(b)2 − a (b)1 a31 11 . . . . . . an,n+1 an1
a12 a22 a32 . . . an2
a1n a2n a3n . . . ann
a11 a1,n+1 0 a2,n+1 a a3,n+1 (b)3 ←(b)3 − a31 (b)1 0 11 . . . . . . an1 an,n+1
a12 a22 a32 . . . an2
··· ··· ···
··· ··· ··· ···
···
a1n a2n a3n . . . ann
a1,n+1 a2,n+1 a3,n+1 . . . an,n+1
a1n a2n a3n . . . ann
a1,n+1 a2,n+1 a3,n+1 . . .
a1n a2n a3n . . . ann
a1,n+1 a2,n+1 a3,n+1 . . .
an,n+1
. . . a11 a21 a31 . . . an1
13
a12 a22 a32 . . . an2
··· ··· ···
···
a1n a2n a3n . . . ann
a1,n+1 a2,n+1 a a3,n+1 (b)n ←(b)n − an1 (b)1 11 . . .
an,n+1
Mahdhivan Syafwan
a11 0 0 . . . 0
a12 a22 a32 . . . an2
··· ··· ···
···
an,n+1
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Metode eliminasi Gauss - tahap eliminasi Langkah pertama - algoritma (b)2 ← (b)2 − (b)3 ← (b)3 − .. . (b)n ← (b)n −
14
a21 a11 (b)1 a31 a11 (b)1
an1 a11 (b)1
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Metode eliminasi Gauss - tahap eliminasi Langkah kedua: mengeliminasi kolom kedua dari matriks lengkap SPL. a11 0 0 . . . 0
a12 a22 a32 . . . an2
a13 a23 a33
an3
··· ··· ··· . . . ···
a1n a2n a3n . . . ann
a1,n+1 a2,n+1 a3,n+1 an,n+1
a (b)3 ←(b)3 − 32 (b)2 a22 a42 (b)4 ←(b)4 − (b)2 a22
. . . a (b)n ←(b)n − n2 (b)2 a22
a11 0 0 . . . 0
a12 a22 0 . . . 0
a13 a23 a33
an3
··· ··· ··· . . . ···
a1n a2n a3n . . . ann
a1,n+1 a2,n+1 a3,n+1
an,n+1
Langkah ke-3, 4, ..., n − 1: mengeliminasi kolom ke-3, 4, ..., n − 1 dari matriks lengkap SPL. Hasil akhir dari tahap eliminasi adalah suatu SPL segitiga atas. Solusi SPL dapat diperoleh dengan menjalankan algoritma substitusi mundur. 15
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Metode eliminasi Gauss - algoritma tahap eliminasi
→
16
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Algoritma metode eliminasi Gauss
17
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Kelemahan metode eliminasi Gauss & perbaikannya Kelemahan metode eliminasi Gauss: Proses eliminasi tidak dapat dilakukan jika elemen penumpu (pivot) bernilai nol. Jika nilai mutlak dari elemen pivot sangat kecil, maka pada realisasi komputer akan menimbulkan perambatan galat pembulatan yang besar.
18
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Kelemahan metode eliminasi Gauss & perbaikannya Kelemahan metode eliminasi Gauss: Proses eliminasi tidak dapat dilakukan jika elemen penumpu (pivot) bernilai nol. Jika nilai mutlak dari elemen pivot sangat kecil, maka pada realisasi komputer akan menimbulkan perambatan galat pembulatan yang besar. Cara memperbaikinya? Perlu dipilih elemen penumpu yang nilai mutlaknya besar. Hal ini direalisasikan dengan melakukan pertukaran baris dan/atau kolom pada matriks lengkap. Pertukaran baris tidak mengubah solusi SPL. Pertukaran kolom bagaimana?
18
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Kelemahan metode eliminasi Gauss & perbaikannya Kelemahan metode eliminasi Gauss: Proses eliminasi tidak dapat dilakukan jika elemen penumpu (pivot) bernilai nol. Jika nilai mutlak dari elemen pivot sangat kecil, maka pada realisasi komputer akan menimbulkan perambatan galat pembulatan yang besar. Cara memperbaikinya? Perlu dipilih elemen penumpu yang nilai mutlaknya besar. Hal ini direalisasikan dengan melakukan pertukaran baris dan/atau kolom pada matriks lengkap. Pertukaran baris tidak mengubah solusi SPL. Pertukaran kolom bagaimana? Teknik pemilihan elemen penumpu ini dinamakan teknik penumpuan (pivoting). 18
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Beberapa macam teknik penumpuan Penumpuan total Elemen penumpu diambil dari max |aij | k≤i ,j≤n
Memerlukan pertukaran baris dan/atau kolom
Penumpuan parsial Elemen penumpu diambil dari max |aik | k≤i ≤n
Hanya memerlukan pertukaran baris saja
Penumpuan parsial terskala Elemen penumpu diambil dari max |aik /akk | k≤i ≤n
Hanya memerlukan pertukaran baris saja
Elemen penumpu yang dipilih kemudian ditempatkan pada posisi (k, k) dari matriks lengkap SPL. 19
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Eliminasi Gauss dengan penumpuan parsial - contoh
20
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Eliminasi Gauss dengan penumpuan parsial - algoritma?
21
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Eliminasi Gauss dengan penumpuan parsial - algoritma?
21
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Eliminasi Gauss dengan penumpuan parsial - algoritma
22
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Beberapa SPL dengan matriks koefisien sama Pandang dua SPL berikut:
x1 2x1 4x1 −3x1
x1 2x1 4x1 −3x1
+
2x2
+ +
2x2 x2
+
2x2
+ +
2x2 x2
+ + + +
x3 4x3 2x3 3x3
+ + + +
4x4 3x4 x4 2x4
= = = =
13 28 20 0
+ + + +
x3 4x3 2x3 3x3
+ + + +
4x4 3x4 x4 2x4
= = = =
8 9 9 3
Matriks lengkap dari dua SPL tersebut dapat ditulis:
1 2 4 −3
2 0 2 1
1 4 2 3
4 3 1 2
13 28 20 6
8 9 . 9 3
Solusi dari masing-masing SPL dapat ditentukan dengan metode eliminasi Gauss. 23
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Perhitungan determinan - dasar teori Teorema (determinan matriks segitiga atas) Jika A matriks segitiga atas berukuran n × n, maka det(A) =
n Y
aii .
i =1
Bukti. Lakukan ekspansi kofaktor berkali-kali sepanjang baris terakhir. Teorema (pengaruh OBE terhadap nilai determinan suatu matriks) Misalkan A matriks berukuran n × n. Jika B adalah matriks hasil dari perkalian suatu baris (kolom) matriks A dengan konstanta k, maka det(B) = k det(A). Jika B adalah matriks hasil dari pertukaran dua baris (kolom) matriks A, maka det(B) = − det(A). Jika B adalah matriks hasil penambahan k kali baris (kolom) ke baris (kolom) lain dari matriks A, maka det(B) = det(A). Bukti. ... 24
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Perhitungan determinan - penerapan, contoh, & algoritma Untuk menghitung determinan suatu matriks, lakukan serangkaian OBE terhadap matriks tersebut sedemikian sehingga menjadi matriks segitiga atas. Perhatikan perubahan nilai determinan selama melakukan OBE.
25
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Perhitungan determinan - penerapan, contoh, & algoritma Untuk menghitung determinan suatu matriks, lakukan serangkaian OBE terhadap matriks tersebut sedemikian sehingga menjadi matriks segitiga atas. Perhatikan perubahan nilai determinan selama melakukan OBE. Contoh. Dengan menggunakan metode eliminasi Gauss dengan penumpuan parsial, tentukan determinan dari 1 2 1 4 2 0 4 3 4 2 2 1 . −3 1 3 2
25
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Perhitungan determinan - penerapan, contoh, & algoritma Untuk menghitung determinan suatu matriks, lakukan serangkaian OBE terhadap matriks tersebut sedemikian sehingga menjadi matriks segitiga atas. Perhatikan perubahan nilai determinan selama melakukan OBE. Contoh. Dengan menggunakan metode eliminasi Gauss dengan penumpuan parsial, tentukan determinan dari 1 2 1 4 2 0 4 3 4 2 2 1 . −3 1 3 2 Algoritmanya? → tugas kelompok
25
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Perhitungan invers Gunakan metode eliminasi Gauss-Jordan (eliminasi maju dan mundur): A I ∼ · · · ∼ I A−1 . [justifikasi!]
26
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Perhitungan invers Gunakan metode eliminasi Gauss-Jordan (eliminasi maju dan mundur): A I ∼ · · · ∼ I A−1 . [justifikasi!] Contoh.
26
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Perhitungan invers Gunakan metode eliminasi Gauss-Jordan (eliminasi maju dan mundur): A I ∼ · · · ∼ I A−1 . [justifikasi!] Contoh.
Algoritmanya? 26
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Review Tahap eliminasi dan algoritma Teknik penumpuan Perhitungan determinan, invers, dll
Modifikasi eliminasi Gauss untuk SPL tridiagonal Perhatikan matriks SPL tridiagonal berikut: b1 c1 x1 d1 a2 b2 c2 x 2 d2 . .. x3 = d3 . a 3 b3 . . . .. .. . . . cn−1 . . xn dn an bn Pada SPL tersebut, banyak sekali koefisiennya yang bernilai nol. Bagaimana algoritma yang paling efisien untuk mencari solusi SPL tersebut? 27
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Apa itu faktorisasi LU? Beberapa jenis faktorisasi LU Faktorisasi LU Doolitle dengan eliminasi Gauss Aplikasi faktorisasi LU: perhitungan invers matriks
Definisi faktorisasi LU dan kegunaannya Definisi (Faktorisasi LU/Segitiga) Matriks nonsingular A dikatakan mempunyai faktorisasi LU (juga dikenal dengan faktorisasi segitiga) jika ia dapat ditulis sebagai perkalian matriks segitiga bawah L dan matriks segitiga atas U, yaitu A = LU. Misalkan matriks koefisien A dari SPL Ax = b mempunyai faktorisasi LU. Maka Ax = b ⇔ (LU)x = b ⇔ L(Ux) = b. Sekarang misalkan d = Ux. SPL segitiga bawah Ld = b dapat diselesaikan dengan substitusi maju. Setelah d diperoleh, solusi x dapat dicari dari SPL segitiga atas Ux = d dengan substitusi mundur. 28
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Apa itu faktorisasi LU? Beberapa jenis faktorisasi LU Faktorisasi LU Doolitle dengan eliminasi Gauss Aplikasi faktorisasi LU: perhitungan invers matriks
Ilustrasi
29
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Apa itu faktorisasi LU? Beberapa jenis faktorisasi LU Faktorisasi LU Doolitle dengan eliminasi Gauss Aplikasi faktorisasi LU: perhitungan invers matriks
Beberapa jenis faktorisasi LU
Secara umum faktorisasi LU tidak tunggal. Agar hasilnya tunggal, biasanya dilakukan dengan memilih matriks L dan U yang memiliki sifat tertentu. Beberapa faktorisasi LU yang dikenal: Faktorisasi/dekomposisi Doolitle, yaitu elemen diagonal matriks L dipilih bernilai 1. Faktorisasi/dekomposisi Crout, yaitu elemen diagonal matriks U dipilih bernilai 1. Faktorisasi/dekomposisi Cholesky, yaitu matriks U dibuat sama dengan LT jika A matriks simetris.
30
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Apa itu faktorisasi LU? Beberapa jenis faktorisasi LU Faktorisasi LU Doolitle dengan eliminasi Gauss Aplikasi faktorisasi LU: perhitungan invers matriks
Faktorisasi LU Doolitle dengan eliminasi Gauss - proses Misalkan dari tahap eliminasi pada eliminasi Gauss diperoleh a11 a12 · · · a1n a11 a12 · · · a1n (1) (1) 0 a21 a22 · · · a2n a22 ··· a2n A= . . . . . . ∼ ··· ∼ . = U, . . .. .. .. . . . (n−1) an1 an2 · · · ann 0 0 · · · ann (k)
dimana aij menyatakan elemen matriks A pada posisi (i , j) yang nilainya merupakan hasil dari OBE pada iterasi ke-k. Meskipun tidak muncul secara langsung, matriks L juga dihasilkan dari proses eliminasi ini, yaitu diberikan oleh 1 l21 L= . .. ln1
(j−1)
dimana lij = aij 31
(j−1)
/ajj
0 1 .. .
··· ···
ln2
···
0 0 .. , . 1
(0)
dan ai 1 = ai 1 [periksa!].
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Apa itu faktorisasi LU? Beberapa jenis faktorisasi LU Faktorisasi LU Doolitle dengan eliminasi Gauss Aplikasi faktorisasi LU: perhitungan invers matriks
Faktorisasi LU Doolitle dengan eliminasi Gauss - algoritma
32
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Apa itu faktorisasi LU? Beberapa jenis faktorisasi LU Faktorisasi LU Doolitle dengan eliminasi Gauss Aplikasi faktorisasi LU: perhitungan invers matriks
Perhitungan invers matriks - dasar teori & penerapan Diberikan sistem 1 0 Ax1 = .. . 0
,
Ax2 =
0 1 .. . 0
,
...
, Axn =
0 0 .. . 1
,
dimana A adalah matriks berukuran n × n dan x1 , x2 , ..., xn adalah vektor-vektor berukuran n × 1. Jika A dapat diinverskan, maka A−1 = [x1
x2
...
xn ] .
[tunjukkan!]
Solusi x1 , x2 , ..., xn dapat ditentukan dengan menggunakan faktorisasi LU. Karena sistem di atas memiliki matriks koefisien yang sama, maka matriks L dan U cukup dihitung sekali. 33
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Apa itu faktorisasi LU? Beberapa jenis faktorisasi LU Faktorisasi LU Doolitle dengan eliminasi Gauss Aplikasi faktorisasi LU: perhitungan invers matriks
Perhitungan invers matriks - algoritma
34
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Apa itu faktorisasi LU? Beberapa jenis faktorisasi LU Faktorisasi LU Doolitle dengan eliminasi Gauss Aplikasi faktorisasi LU: perhitungan invers matriks
Perhitungan invers matriks - algoritma
34
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Metode Jacobi vs Gauss-Seidel
Metode iterasi? Alternatif metode untuk menyelesaikan SPL (dan juga SPNL). Metode iteratif dimulai dengan sebuah tebakan awal, kemudian digunakan suatu metode sistematis untuk memperoleh barisan yang diharapkan konvergen ke solusi yang ingin dicari. Metode iteratif untuk SPL: metode Jacobi dan metode Gauss-Seidel. Metode iteratif untuk SPNL: metode substitusi berturutan dan metode Newton-Raphson (kasus multivariat) [tidak dipelajari].
35
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Metode Jacobi vs Gauss-Seidel
Ilustrasi
Figure : (a) Metode Gauss-Seidel, (b) Metode Jacobi 36
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Metode Jacobi vs Gauss-Seidel
Metode Jacobi Diberikan SPL berikut: a11 x1 + a12 x2 a21 x1 + a22 x2 .. .. . . an1 x1
+
an2 x2
+ ··· + + ··· +
a1n xn a2n xn .. .
= =
b1 b2 .. .
+ ··· +
ann xn
=
bn
Rumus iterasi dari metode Jacobi:
37
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Metode Jacobi vs Gauss-Seidel
Metode Jacobi Diberikan SPL berikut: a11 x1 + a12 x2 a21 x1 + a22 x2 .. .. . . an1 x1
+
an2 x2
+ ··· + + ··· +
a1n xn a2n xn .. .
= =
b1 b2 .. .
+ ··· +
ann xn
=
bn
Rumus iterasi dari metode Jacobi: n X (k+1) (k) xi = bi − aij xj /aii ,
i = 1, 2, ..., n.
j=1,j6=i
Catatan: indeks (k) menyatakan langkah iterasi. iT h (0) (0) (0) · · · xn x2 Ambil tebakan awal x = x1 . (k+1) (k) − xi < ǫ. Kriteria penghentian iterasi: max xi 1≤i ≤n
37
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Metode Jacobi vs Gauss-Seidel
Algoritma metode Jacobi
38
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Metode Jacobi vs Gauss-Seidel
Algoritma metode Jacobi
38
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Metode Jacobi vs Gauss-Seidel
Metode Gauss-Seidel Diberikan SPL berikut: a11 x1 + a12 x2 a21 x1 + a22 x2 .. .. . . an1 x1
+
an2 x2
+ ··· + + ··· +
a1n xn a2n xn .. .
= =
b1 b2 .. .
+ ··· +
ann xn
=
bn
Rumus iterasi dari metode Gauss-Seidel:
39
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Metode Jacobi vs Gauss-Seidel
Metode Gauss-Seidel Diberikan SPL berikut: a11 x1 + a12 x2 a21 x1 + a22 x2 .. .. . . an1 x1
+
an2 x2
+ ··· + + ··· +
a1n xn a2n xn .. .
= =
b1 b2 .. .
+ ··· +
ann xn
=
bn
Rumus iterasi dari metode Gauss-Seidel: i −1 n X X (k+1) (k+1) (k) xi = bi − aij xj − aij xj /aii ,
i = 1, 2, ..., n.
j=i +1
j=1
Catatan: indeks (k) menyatakan langkah iterasi. iT h (0) (0) (0) · · · xn x2 Ambil tebakan awal x = x1 . (k+1) (k) − xi < ǫ. Kriteria penghentian iterasi: max xi 1≤i ≤n
39
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Metode Jacobi vs Gauss-Seidel
Algoritma metode Gauss-Seidel
40
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Metode Jacobi vs Gauss-Seidel
Algoritma metode Gauss-Seidel
40
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier
Review Matriks dan SPL Metode eliminasi Gauss Faktorisasi LU Metode Iterasi
Metode Jacobi vs Gauss-Seidel
Kekonvergenan metode Jacobi dan Gauss-Seidel Metode Jacobi dan Gauss-Seidel tidak selalu konvergen. Syarat cukup agar kedua metode tersebut konvergen adalah matriks koefisien A bersifat dominan kuat secara diagonal, yaitu |aii | >
n X
|aij |,
i = 1, 2, ..., n.
j=1,j6=i
Sebelum metode Jacobi dan Gauss-Seidel digunakan, lakukan dulu pemeriksaan apakah matriks koefisien A bersifat dominan kuat secara diagonal. Salah satu cara agar matriks koefisien A bersifat dominan kuat secara diagonal adalah dengan menukarkan baris-baris dari SPL tersebut. Bila proses penukaran baris tidak berhasil membuat matriks koefisien A bersifat dominan kuat secara diagonal, maka metode Jacobi dan Gauss-Seidel biasanya tidak dapat digunakan. 41
Mahdhivan Syafwan
Metode Numerik: Sistem Persamaan Linier