md 3 faktorisasi lu partisi matriks

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

Laboratorium Komputasi Program Studi Teknik Informatika Fakultas Teknologi Industri Universitas Atma Jaya Yogyakarta 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 :

A = − −⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

2 6 23 8 0

4 9 2 B =

223

Dengan faktorisasi, persamaan matrik di atas dapat ditulis menjadi :

1 0 01 5 1 02 3 1

2 6 20 1 30 0 7

−−

⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

, xxx

= 223

1

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:

1 0 01 5 1 02 3 1−

−

⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

, yyy

= 223

1

2

3

L y = b

sehingga diperoleh: y1 = 2

y2 = 5

y3 = 14

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

2 6 20 1 30 0 7

⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

xxx

= 25

14

1

2

3

U x = y

sehingga diperoleh: x1 = 2


Laboratorium Komputasi Program Studi Teknik Informatika Fakultas Teknologi Industri Universitas Atma Jaya Yogyakarta 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),

n) ..... 1,+k k, = j(untuk u/ulal

ulau

k,k

1k

1ik,ii,jk,jk,j

1k

1ij,ii,kj,kj,k

⎟⎠

⎞⎜⎝

⎛ −=

−=

∑

∑−

=

−

=

4. Langkah ke‐3:

untuk k=n,

1l

ulau

n,n

1n

1in,ii,nn,nn,n

=

−= ∑−

=

5. Algoritma sudah selesai. Matrik L dan U sudah dapat diperoleh.

Contoh:



− − − −− − −⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

8 16 8 64 5 2 3

0 3 10 04 8 0 4

=

1 0 0 00,5 1 0 00 1 1 0

-0,5 0 -1 1

-8 -16 -8 -60 3 6 00 0 4 00 0 0 1

A = L U

PARTISI MATRIKS

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

sebagai berikut:

AA

A A=

−−

⎡

⎣

⎢⎢⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥⎥⎥

→⎡

⎣⎢

⎤

⎦⎥

8 2 0 2 71 8 2 0 0

4 3 5 1 17 0 8 2 80 0 1 2 4

12

21 22

A = A11

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

A

A

1 1

2 1

8 21 8

4 3

0 2 72 0 05 1 1

7 00 0

8 2 81 2 4

,

,

= −⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

=−

⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

=⎡

⎣⎢

⎤

⎦⎥ =

⎡

⎣⎢

⎤

⎦⎥

A

A

1,2

2,2

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:

AA AA A

B BB B

=⎡

⎣⎢

⎤

⎦⎥

⎡

⎣⎢

⎤

⎦⎥

11 12

21 22

11 12

21 22

B =

maka :

A BA B A BA B A B

+ =+ ++ +

⎡

⎣⎢

⎤

⎦⎥ 11 11 12 12

21 21 22 22


Laboratorium Komputasi Program Studi Teknik Informatika Fakultas Teknologi Industri Universitas Atma Jaya Yogyakarta 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:

AB bcT=⎡

⎣⎢

⎤

⎦⎥β

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

AP qr T

− =⎡

⎣⎢

⎤

⎦⎥

1

σ

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

AAB bc

P qr

I

BP br Bq bc P r c q

T T T

T

T T T

− =⎡

⎣⎢

⎤

⎦⎥

⎡

⎣⎢

⎤

⎦⎥

⎡

⎣⎢

⎤

⎦⎥

=+ ++ +

⎡

⎣⎢

⎤

⎦⎥

1 00 1β σ

σβ βσ

=

Dari persamaan di atas melalui substitusi kemudian didapatkan:

P B B bc Bc B b

r c P

c B bq B b

T

T

T T

T

= +−

= −

=−

= −

−− −

−

−

−

11 1

1

1

1

1

1

β

β

σβσ

Algoritma Untuk Menetapkan A‐1 dari A

AB bcT=⎡

⎣⎢

⎤

⎦⎥β A

P qr T

− =⎡

⎣⎢

⎤

⎦⎥

1

σ

Langkah‐langkah:

1. Tetapkan B‐1


Laboratorium Komputasi Program Studi Teknik Informatika Fakultas Teknologi Industri Universitas Atma Jaya Yogyakarta 2. Hitung v = B‐1 b

3. Hitung σβ

=−1c vT

4. P = B‐1 + σ v cTB‐1

5. q = ‐σ v

6. r cT T= −1β

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.



Contoh : A = − −⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

2 6 23 8 0

4 9 2

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

L =− −

⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

=⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

=⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

1 0 00 5 1 00 75 0 8333 1

4 9 20 15 10 0 2 333

0 0 11 0 00 1 0

.

. ..

. U P

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 :

l = − −⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

⎡

⎣

⎢⎢⎢

⎤

⎦

⎥⎥⎥

0 5 1 00 75 0 833 11 0 0

4 9 20 15 10 0 2 333

.

. . ..

u =

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.


Laboratorium Komputasi Program Studi Teknik Informatika Fakultas Teknologi Industri Universitas Atma Jaya Yogyakarta 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]

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡

112323231

. =

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡

321

xxx

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡

71613

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 )



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



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 ( QT = Q’ = inv(Q))

X = R \ Y

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



‐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


Laboratorium Komputasi Program Studi Teknik Informatika Fakultas Teknologi Industri Universitas Atma Jaya Yogyakarta 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:

A =

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡

531086642

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)



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

A =

⎥⎥⎥

⎦

⎤

⎢⎢⎢

⎣

⎡

423242361

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



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

A =

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

2468126634742562

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

b =

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

268

10



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 ‐ uAvT 11

1−+

A‐1 u vT A‐1

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



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

H ≡

4 3 2 13 3 2 12 2 2 11 1 1 1

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

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

H‐1 ≡ .

1 1 0 01 2 1 0

0 1 20 0 1 2

−− −

− −−

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

1

Sekarang ingin ditetapkan invers dari matrix

G ≡ 1

2 1 0 01 2 1 0

0 1 20 0 1 2

−− −

− −−

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥.

Tampaklah, bahwa matrix G berbeda dari H‐1 hanya pada elemen pada pojok kiri atas. Oleh karena itu, karena

G ≡ 1 1

2 1 0 01 2 1 0

0 1 20 0 1 2

−− −

− −−

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥ = + ,

1 1 0 01 2 1 0

0 1 20 0 1 2

−− −

− −−

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

1 0 0 00 0 0 00 0 0 00 0 0 0

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

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

β ≡ 1 + vTA‐1u = 1 + [ ]1 0 0 0 = 5

4 3 2 13 3 2 12 2 2 11 1 1 1

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

1000

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

maka

A‐1 ‐1β

A‐1 u vT A‐1



G‐1 ≡ ‐

4 3 2 13 3 2 12 2 2 11 1 1 1

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

15

4 3 2 13 3 2 12 2 2 11 1 1 1

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

1 0 0 00 0 0 00 0 0 00 0 0 0

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

4 3 2 13 3 2 12 2 2 11 1 1 1

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

= .

08 06 04 0206 12 08 0404 08 12 0602 04 06 08

. . . .

. . . .

. . . .

. . . .

⎡

⎣

⎢⎢⎢⎢

⎤

⎦

⎥⎥⎥⎥

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 e2

T + u3 e3T + … + un en

T

sehingga dengan menulis pula Bo + I

Z = Bo + u1e1T + u2 e2

T + u3 e3T + … + un en

T. Rumusan ini merupakan basis yang bagus bagi penerapan berulang SMW: Bo = I B⇒ o

‐1 = I B1 = Bo + u1e1

T B⇒ 1‐1 = (Bo + u1e1

T)‐1 dapat dihitung dengan SMW B2 = B1 + u2e2

T B⇒ 2‐1 = (B1 + u2e2

T)‐1 dapat dihitung dengan SMW B3 = B2 + u3e3

T B⇒ 3‐1 = (B2 + u3e3

T)‐1 dapat dihitung dengan SMW M Bn = Bn‐1 + u1e1

T ⇒ Bn‐1 = (Bn‐1 + unen

T)‐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);


Laboratorium Komputasi Program Studi Teknik Informatika Fakultas Teknologi Industri Universitas Atma Jaya Yogyakarta 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 ek

T dan uk dalam ekTBk

‐1uk = ‐1.


md 3 faktorisasi lu partisi matriks

Documents