PAM 252 Metode Numerik Bab 3 Sistem Persamaan Linier

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 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




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




  . 



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




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




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




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




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




Algoritma substitusi maju?

9

Mahdhivan Syafwan



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




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 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 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


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





··· ··· ···

··· ··· ··· ···

···


 a1,n+1 a2,n+1   a3,n+1   .  .  .  an,n+1


 a1,n+1 a2,n+1   a3,n+1   .  .  . 


 a1,n+1 a2,n+1   a3,n+1   .  .  . 

an,n+1

. . . a11  a21   a31   .  .  . an1 

13

a12 a22 a32 . . . an2

··· ··· ···

···


 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 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 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

··· ··· ··· . . . ···


 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

··· ··· ··· . . . ···


 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 eliminasi Gauss - algoritma tahap eliminasi

→

16

Mahdhivan Syafwan




Algoritma metode eliminasi Gauss

17

Mahdhivan Syafwan




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




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




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




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




Eliminasi Gauss dengan penumpuan parsial - contoh

20

Mahdhivan Syafwan




Eliminasi Gauss dengan penumpuan parsial - algoritma?

21

Mahdhivan Syafwan




Eliminasi Gauss dengan penumpuan parsial - algoritma?

21

Mahdhivan Syafwan




Eliminasi Gauss dengan penumpuan parsial - algoritma

22

Mahdhivan Syafwan




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




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




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




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




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




Perhitungan invers Gunakan metode eliminasi Gauss-Jordan (eliminasi maju dan mundur): A I ∼ · · · ∼ I A−1 . [justifikasi!]

26

Mahdhivan Syafwan




Perhitungan invers Gunakan metode eliminasi Gauss-Jordan (eliminasi maju dan mundur): A I ∼ · · · ∼ I A−1 . [justifikasi!] Contoh.

26

Mahdhivan Syafwan




Perhitungan invers Gunakan metode eliminasi Gauss-Jordan (eliminasi maju dan mundur): A I ∼ · · · ∼ I A−1 . [justifikasi!] Contoh.

Algoritmanya? 26

Mahdhivan Syafwan




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



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




Ilustrasi

29

Mahdhivan Syafwan




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




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




Faktorisasi LU Doolitle dengan eliminasi Gauss - algoritma

32

Mahdhivan Syafwan




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




Perhitungan invers matriks - algoritma

34

Mahdhivan Syafwan




Perhitungan invers matriks - algoritma

34

Mahdhivan Syafwan



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




Ilustrasi

Figure : (a) Metode Gauss-Seidel, (b) Metode Jacobi 36

Mahdhivan Syafwan




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 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




Algoritma metode Jacobi

38

Mahdhivan Syafwan




Algoritma metode Jacobi

38

Mahdhivan Syafwan




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 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




Algoritma metode Gauss-Seidel

40

Mahdhivan Syafwan




Algoritma metode Gauss-Seidel

40

Mahdhivan Syafwan




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


PAM 252 Metode Numerik Bab 3 Sistem Persamaan Linier

Recommend Documents