MODUL 3 FAKTORISASI LU, PARTISI MATRIK DAN FAKTORISASI QR

Laboratorium Komputasi Program Studi Teknik Informatika Fakultas Teknologi Industri Universitas Atma Jaya Yogyakarta

MODUL 3 FAKTORISASI LU, PARTISI MATRIK DAN FAKTORISASI QR KOMPETENSI: 1. Memahami penggunaan faktorisasi LU dalam penyelesaian persamaan linear. 2. Memahami penggunaan partisi matrik dalam penyelesaian persamaan linear. 3. Memahami penggunaan faktorisasi QR dalam penyelesaian persamaan linear. 4. Mengetahui kegunaan dan efisiensi masing‐masing algoritma dalam hal beban perhitungannya. I. DASAR TEORI

Untuk berbagai keperluan teknik sering kita jumpai sistem persamaan linear simultan,

yang dapat dituliskan dalam bentuk persamaan matrik, misalnya Ax = b. A adalah matrik bujur sangkar dengan ordo (dimensi) n x n, A dan b adalah matrik dan vektor kolom yang diketahui, sedangkan x adalah vektor kolom yang akan dicari. Peyelesaian sistem persamaan tersebut adalah : x = A‐1. b Akan tetapi untuk memperoleh penyelesaian persamaan ini kita harus mencari invers matrik A. Seringkali muncul kesulitan di sini, karena mencari invers suatu matrik tidaklah mudah, apalagi untuk matrik yang berdimensi besar (n>4). Apalagi kalau matriknya tidak bujursangkar, melainkan persegi panjang.

Faktorisasi pada dasarnya adalah membentuk suatu matrik bujur sangkar sebagai

perkalian dua matrik segitiga. Yang satu adalah matrik segitiga bawah (lower triangular matrix) dan yang satunya adalah matrik segitiga atas (upper triangular matrix). Secara sistematis dapat dituliskan A = L U. Faktorisasi ini disebut faktorisasi LU atau kadang‐kadang disebut faktorisasi LR. Dengan faktorisasi kita dapat menyelesaikan sistem persamaan Ax = b tanpa harus mencari invers matrik A.

Langkah‐langkah yang dibutuhkan untuk menyelesaikan sistem persamaan diatas

adalah sebagai berikut:

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR

halaman 1 dari 18


1. Faktorisasi, tetapkan matrik L dan U, sehingga A = L U. Di sini L adalah matrik segitiga bawah satuan (matrik segitiga bawah dengan elemen diagonal 1), sedangkan U adalah matrik segitiga atas. 2. Definisikan y = u x, tetapkan harga y dari persamaan linier L y = b. Ini dapat dilakukan dengan aljabar biasa tanpa harus melakukan operasi invers terhadap matrik L. 3. Setelah itu tetapkan x dari persamaan U x = y. Di sini juga tidak diperlukan operasi invers terhadap matrik U. Contoh di bawah ini akan mengillustrasikan prosedur di atas :

⎡ 2 6 2⎤ A = ⎢−3 −8 0⎥ ⎢ ⎥ ⎢⎣ 4 9 2 ⎥⎦

⎡2 ⎤ B = ⎢⎢2 ⎥⎥ ⎢⎣ 3⎥⎦

Dengan faktorisasi, persamaan matrik di atas dapat ditulis menjadi :

0 0⎤ ⎡2 6 2 ⎤ ⎡ x1 ⎤ ⎡ 1 ⎢ −1,5 1 0⎥ ⎢0 1 3⎥ ⎢ x 2 ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢⎣ 2 −3 1⎥⎦ ⎢⎣0 0 7⎥⎦ ⎢⎣ x 3 ⎥⎦

⎡2 ⎤ = ⎢⎢2 ⎥⎥ ⎢⎣ 3⎥⎦

L U x = b Definisikan y = U x, sehingga L y = b. Dari situ dapat kita hitung y1, y2 dan y3 dengan persamaan:

0 0⎤ ⎡ 1 ⎢ −1,5 1 0⎥ ⎢ ⎥ ⎢⎣ 2 −3 1⎥⎦

⎡ y1 ⎤ ⎢y ⎥ ⎢ 2⎥ ⎢⎣ y 3 ⎥⎦

⎡2 ⎤ = ⎢⎢2 ⎥⎥ ⎢⎣ 3⎥⎦

L y =

sehingga diperoleh:

y1

=

2

y2

=

5

y3

=

14

b

Setelah vektor kolom y ditemukan, nilai‐nilai x1, x2 dan x3 dapat pula dihitung dari persamaan:

⎡2 6 2 ⎤ ⎢0 1 3⎥ ⎢ ⎥ ⎢⎣0 0 7 ⎥⎦

U

sehingga diperoleh:

x1

⎡ x1 ⎤ ⎢x ⎥ ⎢ 2⎥ ⎢⎣ x 3 ⎥⎦ x

=

=

⎡2⎤ ⎢ 5 ⎥ ⎢ ⎥ ⎢⎣14 ⎥⎦

= y

2


halaman 2 dari 18


x2

=

‐1

x3

=

2

Dengan demikian, sistem persamaan kita tadi sudah diperoleh penyelesaiannya. Proses faktorisasi A menjadi LU merupakan langkah yang mahal, yaitu kira‐kira sebanding dengan operasi perkalian sebanyak n9. ALGORITMA FAKTORISASI DOOLITTLE. Algoritma faktorisasi L U yang paling populer adalah faktorisasi Doolittle yang menggunakan langkah‐langkah sebagai berikut: 1. Didefinisikan suatu matrik A dengan notasi (ai,j) dimana I adalah baris matrik A dan j adalah kolom matrik A. 2. Langkah ke‐1:

untuk k=1,

u1,j = a1,j

(untuk j = k, k+1, ....n)

lj,1 = aj,1/u1,1

(untuk j = k, k+1, ....n)

3. Langkah ke‐2:

untuk k = 2,3, ....... (n‐1), k −1

u k , j = a k , j − ∑ lk ,i u i , j

i =1

l j, k

k −1 ⎛ ⎞ = ⎜ a j, k − ∑ l j,i u i , k ⎟ / u k , k i =1 ⎝ ⎠

(untuk j = k, k + 1, ..... n)

4. Langkah ke‐3:

untuk k=n, n −1

u n , n = a n , n − ∑ ln ,i u i , n i =1

ln , n = 1 5. Algoritma sudah selesai. Matrik L dan U sudah dapat diperoleh. Contoh:


halaman 3 dari 18


⎡ −8 −16 −8 −6⎤ ⎢−4 −5 2 −3⎥ ⎢ ⎥ ⎢0 3 10 0 ⎥ ⎢ ⎥ 8 0 4⎦ ⎣4

A

=

=

⎡ 1 ⎢ 0,5 ⎢ ⎢ 0 ⎢ ⎣-0,5

0⎤ 1 0 0⎥ ⎥ 1 1 0⎥ ⎥ 0 -1 1⎦

L

0

0

⎡-8 -16 -8 -6⎤ ⎢0 3 6 0⎥ ⎢ ⎥ ⎢0 0 4 0⎥ ⎢ ⎥ ⎣0 0 0 1⎦

U

PARTISI MATRIKS

Suatu matrik A dapat dipartisi atau disekat dalam bagian berupa matrik (sub‐matrik)

sebagai berikut:

⎡8 ⎢ −1 ⎢ A=⎢4 ⎢ ⎢7 ⎢⎣ 0

2 0 2 8 3 0 0

2 5 8 1

0 1 2 2

7⎤ 0⎥ ⎥ −1⎥ ⎥ 8⎥ 4 ⎥⎦

A12 ⎤ A22 ⎥⎦

⎡A 11 → A= ⎢ ⎣ A21

dimana A11, A12, A21, A22 adalah sebagai berikut :

⎡ 8 2⎤ A1,1 = ⎢⎢−1 8⎥⎥ ⎢⎣ 4 3⎥⎦

A 1,2

⎡0 2 7 ⎤ = ⎢⎢2 0 0 ⎥⎥ ⎢⎣5 1 −1⎥⎦

⎡ 7 0⎤ A2 ,1 = ⎢ ⎥ ⎣ 0 0⎦

⎡8 2 8 ⎤ A 2,2 = ⎢ ⎥ ⎣1 2 4 ⎦

A. Operasi Matrik dalam bentuk Partisi

Operasi matrik dalam bentuk partisi hanya dapat dilakukan bila masing‐masing elemen

partisi mempunyai kesesuaian (mempunyai baris dan kolom yang sama), misalnya:

⎡ A11 A=⎢ ⎣ A21

A12 ⎤ A22 ⎥⎦

⎡ B11 B= ⎢ ⎣ B21

B12 ⎤ B22 ⎥⎦

maka :

A+B =

⎡ A11 + B11 ⎢A + B 21 ⎣ 21

A12 + B12 ⎤ A22 + B22 ⎥⎦


halaman 4 dari 18


Operasi dalam bentuk partisi mempunyai keuntungan sebagai berikut: 1. Kesederhanaan dalam penulisan 2. Segi efisiensi lebih baik B. Algoritma Invers dengan Partisi Matriks Suatu matrik A dapat dipartisi menjadi:

b⎤ β ⎥⎦

⎡B A=⎢ T ⎣c

Maka penyelesaian untuk A x = b, dengan mencari A‐1. Dimisalkan suatu matrik:

q⎤ σ ⎥⎦

⎡P A −1 = ⎢ T ⎣r

maka A A‐1 = I atau A‐1 A = I.

⎡B AA −1 = ⎢ T ⎣c

b⎤ β ⎥⎦

⎡P ⎢r T ⎣

⎡ BP + br T = ⎢ T T ⎣c P + βr

q⎤ ⎡I = ⎢ T ⎥ σ⎦ ⎣0

0⎤ 1⎥⎦

Bq + σb ⎤ ⎥ c T q + βσ ⎦

Dari persamaan di atas melalui substitusi kemudian didapatkan:

P = B −1 +

rT = −

σ=

1

β

B −1bc T B −1 β − c T B −1b

cT P

1 β − c T B −1b

q = −σB −1b Algoritma Untuk Menetapkan A‐1 dari A

⎡B A=⎢ T ⎣c

b⎤ β ⎥⎦

⎡P A −1 = ⎢ T ⎣r

q⎤ σ ⎥⎦

Langkah‐langkah: 1. Tetapkan B‐1


halaman 5 dari 18


2. Hitung v = B‐1 b 3. Hitung σ =

1 β − cT v

4. P = B‐1 + σ v cTB‐1 5. q = ‐σ v 6.

rT = −

1

β

cT P

Algoritma selesai dan telah didapatkan matrik A‐1. Keuntungan memakai cara partisi ini adalah perhitungan invers matrik A dilakukan dalam ukuran yang lebih kecil. FAKTORISASI QR

Faktorisasi QR pada dasarnya sama dengan faktorisasi LU, hanya saja faktorisasi QR ini

dapat digunakan baik untuk matrik bujur sangkar maupun untuk matrik persegi panjang. Matrik A dapat difaktorisasikan dalam perkalian matrik orthonormal dan matrik segitiga atas.

Faktorisasi QR ini dapat digunakan utuk menyelesaikan persamaan linear A x = b,

sehingga penyelesaian itu didapatkan dengan 2 langkah, yaitu: 1. y = QT * b 2. x = R\y ARTI PERMUTASI PADA FAKTORISASI LU MATLAB Sebelum melakukan faktorisasi, MATLAB melakukan suatu proses yang dinamakan pivoting terlebih dahulu. Pivoting ini disebut dengan permutasi, yaitu menempatkan nilai terbesar dari data pada kolom pertama (sembarang baris) ke baris pertama kolom pertama. Keterangan di atas dapat di tulis sebagai berikut :

P*X = L*U

dimana X adalah matrik yang ingin kita cari faktorisasinya, P adalah matrik permutasi, L adalah matrik segitiga bawah, dan U adalah matrik segitiga atas.

Bila matrik A (3 kali 3) pada contoh di depan dicari faktorisasinya dengan

menggunakan MATLAB, maka akan didapatkan hasil yang berbeda karena pada MATLAB sebelumnya sudah dilakukan pivoting yang meletakkan elemen terbesar pada baris pertama, baru kemudian dilakukan algoritma untuk menghitung LU‐nya.


halaman 6 dari 18


⎡ 2 6 2⎤ Contoh : A = ⎢−3 −8 0⎥ ⎢ ⎥ ⎢⎣ 4 9 2 ⎥⎦

Bila dituliskan sintaks [L,U,P] = lu(A), maka akan menghasilkan hasil sebagai berikut :

0 0⎤ ⎡ 1 ⎢ L = 0.5 1 0⎥⎥ ⎢ ⎢⎣ −0.75 −0.8333 1⎥⎦

2 ⎤ ⎡4 9 ⎢ U = ⎢0 15 . 1 ⎥⎥ ⎢⎣0 0 2.333⎥⎦

⎡0 0 1⎤ P = ⎢⎢1 0 0⎥⎥ ⎢⎣0 1 0⎥⎦

Matrik P diatas berarti bahwa baris ketiga dipindah ke baris pertama (karena bernilai paling besar yaitu sama dengan 4). Bila ditulis dengan sintaks [l,u] = lu(A), maka akan menghasilkan hasil sebagai berikut :

1 0⎤ ⎡ 0.5 ⎢ l = −0.75 −0.833 1⎥ ⎢ ⎥ ⎢⎣ 1 0 0⎥⎦

2 ⎤ ⎡4 9 ⎢ u = ⎢0 15 . 1 ⎥⎥ ⎢⎣0 0 2.333⎥⎦

Tampak bahwa l bukan matrik segitiga bawah murni karena L (matrik segitiga bawah) sudah dikalikan dengan inv(P) dan yang kemudian menghasilkan l. Penulisan sintaks di atas adalah benar kedua‐duanya dan hasilnya juga kedua‐duanya benar. Penjabarannya adalah sebagai berikut :

P * A = L * U

inv(P) * P *A = inv(P) * L* U

A = inv(P) * L * U ; inv(P)*L = l dan U = u

A = l * u

Jadi seandainya tidak ada pertukaran komponen baris (permutasi berupa matrik identitas) maka nilai l dan u dengan sintaks [l,u] = lu(A) sama dengan nilai L dan U dengan sintaks [L,U,P] = lu(A). II. DEMO KASUS: Menghadapi Semester Genap 2005/2006, fakultas teknologi industri, ekonomi dan hukum Universitas Atma Jaya Yogyakarta membeli perlengkapan perkuliahan sebagai tambahan fasilitas pada masing‐masing fakultas, yakni unit komputer, proyektor dan whiteboard.


halaman 7 dari 18


Fakultas teknologi industri membeli 10 unit komputer, 5 buah proyektor dan 3 buah whiteboard. Fakultas ekonomi membeli 2 unit komputer, 3 buah proyektor dan sebuah whiteboard. Sedangkan fakultas hukum membeli 3 unit komputer, sebuah proyektor dan juga sebuah whiteboard. Untuk kesemuanya itu, pihak fakultas tekonologi industri harus mengeluarkan biaya 3650 US$, fakultas ekonomi mengeluarkan biaya 950 US$ dan fakultas hukum mengeluarkan biaya 1050 US$. Tentukan harga 1 unit komputer, 1 buah proyektor dan 1 buah whiteboard dengan menggunakan MatLab ! LANGKAH KERJA: A. Membuat Model matematis Perumusan model matematis (persamaan linear simultan) untuk masalah ditas adalah sbb: x1 + 3x2 + 2x3 = 13

3x1 + 2x2 + 3x3 = 16

2x1 + 1x2 + x3 = 7

B. Mengubah Model Matematis ke Bentuk Matriks A x = b [A] [x} = [b]

⎡1 3 2 ⎤ ⎡ x1 ⎤ ⎡13⎤ ⎢3 2 3⎥ . ⎢ x 2⎥ = ⎢16⎥ ⎢ ⎢ ⎥ ⎢ ⎥ ⎥ ⎢⎣2 1 1⎥⎦ ⎢⎣ x3⎥⎦ ⎢⎣ 7 ⎥⎦ C. Solusi dengan teknik Faktorisasi LU menggunakan Matlab : Prinsip Penyelesaian dengan Faktorisasi LU

A x = b L U x = b

( A = L U)

L y = b ( y = U x )

y = L \ b

x = U \ y

1. Menentukan matriks A ( A x = b )


halaman 8 dari 18


>> A = [ 1 3 2; 3 2 3; 2 1 1 ] A =

1 3 2

3 2 3

2 1 1

2. Menentukan vector kolom b ( A x = b ) >> b = [ 13; 16; 7 ] b =

13

16

7

3. Mencari L dan U >>[L,U]=lu(A)

L =

0.3333 1.0000 0

1.0000 0 0

0.6667 ‐0.1429 1.0000

U = 3.0000 2.0000 3.0000

0 2.3333 1.0000

0 0 ‐0.8571

4. Mencari nilai y ( y = U*x ; L y = b ) >> y=L\B y = 16.0000


halaman 9 dari 18


7.6667 ‐2.5714 5. Mencari nilai x ( x = U\y )

>> x=U\y x = 1.0000 2.0000 3.0000 Sehingga didapatkan nilai dari x1, x2 dan x3 dalam bentuk matriks. Jadi x1 = 1 x2 = 2 x3 = 3 D. Solusi dengan teknik Faktorisasi QR menggunakan Matlab Prinsip Penyelesaian dengan Faktorisasi QR

A X = b

Y = QT \ b

X = R \ Y

( QT = Q’ = inv(Q))

Catatan : Karena Matriks A dan vector kolom x serta vector kolom b telah didefinisikan sebelumnya maka tidak perlu mengulang langkah membuat matriks A, vector kolom x dan vector kolom b. 1. Mencari Q dan R >> [Q,R]=qr(A) Q = ‐0.2673 0.9567 0.1155 ‐0.8018 ‐0.1543 ‐0.5774


halaman 10 dari 18


‐0.5345 ‐0.2469 0.8083 R = ‐3.7417 ‐2.9399 ‐3.4744 0 2.3146 1.2036 0 0 ‐0.6928 2. Mencari nilai Y ( Y = QT*b ) >> Y = Q'*b Y =

‐20.0446

8.2398

‐2.0785

3.

Mencari nilai X ( X = R\Y ) >> X = R\Y X =

1.0000 2.0000 3.0000 Sehingga didapatkan nilai dari X1, X2 dan X3 dalam bentuk matriks

Jadi

X1 = 1.0000 X2 = 2.0000 X3 = 3.0000 KESIMPULAN Baik penggunaan cara faktorisasi LU maupun faktorisasi QR dalam menyelesaikan persamaan linier akan menghasilkan nilai yang sama besar


halaman 11 dari 18


III. LATIHAN TERPANDU LANGKAH ‐ LANGKAH KERJA: 1. Hidupkan komputer anda dan tunggu sampai keluar prompt C. 2. Jalankan program MATLAB. 3. Pada langkah percobaan di bawah ini, menggunakan fungsi builtin dari Matlab yaitu fungsi lu, cara yang digunakan adalah sintaks: [L,U] = lu(A) 4. Langkah pertama, masukkan suatu komponen matrik A sebagai berikut:

⎡ 2 4 6⎤ ⎢ ⎥ A = 6 8 0 ⎢ ⎥ ⎢⎣1 3 5⎥⎦

5. Untuk melihat faktorisasi LU, gunakan fungsi HELP MATLAB. Catatlah / print‐lah HELP nya. Sintaksnya : >>[L,U] = lu(A) Catat hasilnya! 6. Untuk mencek apakah hasil permutasinya sudah benar atau tidak maka dapat dilakukan perkalian matrik L dan U dengan : >> L*U 7. Cari invers dari contoh matrik di atas dengan : >> X =inv(A) Invers juga dapat dicari dengan menggunakan invers dari matrik dan U. >> X=inv(U)*inv(L)

8. Cari determinan dari contoh di atas : >> d1 = det(A) kemudian hitung determinan dari matrik L dan U : >> d2 = det(L)*det(U)


halaman 12 dari 18


Catat hasilnya! Dari dua determinan diatas keduanya mempunyai format yang berbeda, mengapa hal itu terjadi? 9. Sekarang buat suatu contoh sistem persamaan linear A x = b, b adalah vektor kolom dengan komponen‐komponen : b11 = 200, b21 = 400, b31 = 600, atau : >> b = [ 200 ; 400 ; 600 ] Carilah penyelesaian dari persamaan A x = b dengan MATLAB, dengan operasi pembagian matrik : >> x = A\b Catat hasilnya! Kemudian dengan faktorisasi LU selesaikan pula persamaan itu dengan sistem dua matrik segitiga: >> y = L\b >> x = U\y. 10. Buat suatu matrik A dengan elemen‐elemen sebagai berikut (dalam MATLAB):

⎡1 6 3 ⎤ ⎥ ⎢ A = 2 4 2 ⎥ ⎢ ⎢⎣3 2 4⎥⎦

Lalu cari invers dengan matrik partisi sebagai berikut: Buat matrik partisinya dahulu: >> A11 = A(1:2,1:2) >> A12 = A(1:2,3) >> A21 = A(3,1: 2) >> A22 = A(3,3) kemudian selesaikan satu persatu: >> AI = inv(A11) >> C = AI*A12


halaman 13 dari 18


>> B22 = 1/(A22‐A21*C) >> B11 = AI+B22*C*A21*AI >> B12 = ‐B22*C >> B21 = ‐(A21*B11)/A22 Setelah diketahui elemen‐elemennya sekarang gabungkan matrik tersebut dengan perintah: >> B = [ B11 B12; B21 B22] Disini B adalah invers dari matrik A. Sekarang bandingkan dengan menginvers langsung A : >> B2 = inv(A) dan bandingkan antara B dan B2. Catat hasilnya! 11. FAKTORISASI QR Buatlah matrik dengan komponen‐komponen sebagai berikut:

⎡2 ⎢4 A = ⎢ ⎢6 ⎢ ⎣8

6 7 6 6

5 4 2 4

2⎤ 3⎥⎥ 1⎥ ⎥ 2⎦

Buatlah faktorisasi QR. Carilah helpnya pada HELP MATLAB! Sintaksnya adalah : >>[Q,R] = qr(A) Cetaklah hasilnya ! 12. Cari penyelesaian persamaan linear berikut dengan matriks A seperti pada soal 11

Ax = b , dengan elemen b

⎡10⎤ ⎢8⎥ b = ⎢ ⎥ ⎢6⎥ ⎢ ⎥ ⎣2⎦


halaman 14 dari 18


dengan cara pembagian matrik :

>> x = A\b Catat hasilnya! 13. Kemudian bandingkan dengan cara berikut: >> y = Q * b

>> x = R \ y

Catat hasilnya! 14. Cek hasilnya dengan mengalikan matrik A dengan penyelesaian matrik x : >> A*x Catat hasilnya! PRAKTIKAN KOMPUTASI DASAR A(4). mencari invers matrix dengan metode det, SMW dan metode iterasi. Tujuan pokok unit kegiatan praktikum ini adalah MATLAB sebagai alat untuk penetapan invers sebuah matrix bujur sangkar dalam rangka menyelesaikan persamaan linear simultan. Metode det menetapkan nilai determinan dari matrix bujur sangkar. Metode SMW menetapkan invers sebuah matrix dengan rumus SMW. Rumus untuk menetapkan invers dengan metode iterasi adalah: Xbaru := Xlama(2I‐AXlama) dengan taksiran awal Xo harus dipilih dengan bijaksana, yaitu Xo : = (1/c)AT dengan c := nilai‐ pribadi yang terbesar dari matrix ATA. Rumus Sherman‐Morrison‐Woodbury:

( A + u vT )‐1 = A‐1 ‐

1 A‐1 u vT A‐1 1 + v A −1 u T

Perhatikanlah, bahwa β ≡ 1 + vTA‐1u bernilai real.


halaman 15 dari 18


Apakah kehebatan relasi ini? Amatilah bahwa sebenarnya ada dua buah matrix A dan B, dengan B hanya berbeda dari A sebesar u vT saja, yaitu B = A + uvT. Menurut SMW, jika A telah diketahui inversnya, maka invers dari B dapat dihitung dengan melakukan koreksi atas invers A. Sebagai ilustrasi sederhana, diketahui bahwa

⎡4 ⎢3 ⎢ H ≡ ⎢2 ⎢ ⎣1

3 2 1⎤ 3 2 1⎥ ⎥ 2 2 1⎥ ⎥ 1 1 1⎦

memiliki invers dibawah ini, yang dapat dibuktikan dengan langsung memperkalikan kedua matrix itu.

⎡ 1 −1 0 0 ⎤ ⎢− 1 2 − 1 0 ⎥ ⎥ ⎢ ‐1 H ≡ ⎢ 0 − 1 2 − 1⎥ . ⎥ ⎢ ⎣ 0 0 −1 2 ⎦ Sekarang ingin ditetapkan invers dari matrix

⎡ 2 −1 0 0 ⎤ ⎢− 1 2 − 1 0 ⎥ ⎢ ⎥ G ≡ ⎢ 0 − 1 2 − 1⎥ . ⎢ ⎥ ⎣ 0 0 −1 2 ⎦ Tampaklah, bahwa matrix G berbeda dari H‐1 hanya pada elemen pada pojok kiri atas. Oleh karena itu, karena

⎡ 2 − 1 0 0 ⎤ ⎡ 1 − 1 0 0 ⎤ ⎡1 ⎢− 1 2 − 1 0 ⎥ ⎢− 1 2 − 1 0 ⎥ ⎢0 ⎢ ⎥ ⎢ ⎥ ⎢ G ≡ ⎢ 0 − 1 2 − 1⎥ = ⎢ 0 − 1 2 − 1⎥ + ⎢0 ⎢ ⎥ ⎢ ⎥ ⎢ ⎣ 0 0 − 1 2 ⎦ ⎣ 0 0 − 1 2 ⎦ ⎣0

0 0 0⎤ 0 0 0⎥ ⎥ 0 0 0⎥ , ⎥ 0 0 0⎦

maka teramati bahwa dalam relasi SMW tersebut A = H‐1, dan u = v = e1. Jadi karena

⎡4 ⎢3 ⎢ T ‐1 β ≡ 1 + v A u = 1 + [1 0 0 0] ⎢2 ⎢ ⎣1

3 2 1⎤ ⎡1⎤ 3 2 1⎥ ⎢0⎥ ⎥⎢ ⎥ 2 2 1⎥ ⎢0⎥ = 5 ⎥ 1 1 1⎦ ⎢⎣0⎥⎦

maka A‐1 ‐

1

β

A‐1 u vT A‐1


halaman 16 dari 18


3 2 1⎤ ⎡4 3 2 1⎥ 1 ⎢3 ⎥ ⎢ 2 2 1⎥ ‐ 5 ⎢2 ⎥ ⎢ 1 1 1⎦ ⎣1 . 0.6 0.4 ⎡08 ⎢0.6 12 . 08 . ⎢ = ⎢0.4 08 . 12 . ⎢ ⎣0.2 0.4 0.6

⎡4 ⎢3 ⎢ ‐1 G ≡ ⎢2 ⎢ ⎣1

3 2 1⎤ ⎡1 3 2 1⎥ ⎢0 ⎥ ⎢ 2 2 1⎥ ⎢0 ⎥ ⎢ 1 1 1⎦ ⎣0 0.2⎤ 0.4⎥ ⎥ 0.6⎥ . ⎥ 08 . ⎦

0 0 0⎤ ⎡4 0 0 0⎥ ⎢3 ⎥ ⎢ 0 0 0⎥ ⎢2 ⎥ ⎢ 0 0 0⎦ ⎣1

3 2 1⎤ 3 2 1⎥ ⎥ 2 2 1⎥ ⎥ 1 1 1⎦

Mencari invers sembarang matrix Z. Atas dasar kenyataan itu, invers sembarang matrix Z (jika invers itu ada) dapat ditetapkan dengan penerapan berulang‐ulang relasi SMW, bertolak dari fakta awal, misalnya, bahwa invers dari matrix satuan adalah matrix satuan juga. – Berhubung dengan kenyataan itu dapatlah ditulis Z = I + (Z‐I). Dalam notasi matrix dapat ditulis (Z‐I) = [ u1 u2 u3 un ], dengan uk adalah vektor yang dibentuk oleh kolom ke‐k dari matrix (Z‐U). Atas dasar itu diperoleh (Z‐I) = u1e1T + u2 e2T + u3 e3T + … + un enT sehingga dengan menulis pula Bo + I Z = Bo + u1e1T + u2 e2T + u3 e3T + … + un enT. Rumusan ini merupakan basis yang bagus bagi penerapan berulang SMW: Bo = I ⇒ Bo‐1 = I T ‐1 B1 = Bo + u1e1 ⇒ B1 = (Bo + u1e1T)‐1 dapat dihitung dengan SMW B2 = B1 + u2e2T ⇒ B2‐1 = (B1 + u2e2T)‐1 dapat dihitung dengan SMW B3 = B2 + u3e3T ⇒ B3‐1 = (B2 + u3e3T)‐1 dapat dihitung dengan SMW M Bn = Bn‐1 + u1e1T ⇒ Bn‐1 = (Bn‐1 + unenT)‐1 = Z‐1 yang ingin ditetapkan. Program MATLAB untuk itu adalah sebagai berikut: function [a] = smw(a) % mencari invers dengan sherman‐morrison‐woodbury % matrix a harus diinputkan lebih dahulu [m,n] = size(a); z = a ‐ eye(n,n); a = eye(n,n);


halaman 17 dari 18


for k = 1:n zz = 1 + a(k,:)*z(:,k); a = a ‐ a*z(:,k)*a(k,:)/zz; end; Apakah yang terjadi jika penerapan berulang itu dilaksanakan atas matrix yang sebenarnya sudah diketahui bersifat singular? ‐‐ Mengingat matrix singular tidak memiliki invers penerapan SMW secara berulang haruslahjuga tidak menghasilkan invers. Artinya, pastilah ada tahap penerapan SMW yang mengalami kegagalan. Dan itu dengan mudah terjadi pada tahapan dimana β ≡ 1 + ekTBk‐1uk = 0. Atau, itu terjadi pada tahapan itu kombinasi antara ekT dan uk dalam ekTBk‐1uk = ‐1.


halaman 18 dari 18

MODUL 3 FAKTORISASI LU, PARTISI MATRIK DAN FAKTORISASI QR

Recommend Documents