md 3 faktorisasi lu partisi matriks

18
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 masingmasing 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=LU. Faktorisasi ini disebut faktorisasi LU atau kadangkadang disebut faktorisasi LR. Dengan faktorisasi kita dapat menyelesaikan sistem persamaan Ax = b tanpa harus mencari invers matrik A. Langkahlangkah yang dibutuhkan untuk menyelesaikan sistem persamaan diatas adalah sebagai berikut: Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 1 dari 18

Upload: erwin-hermawan

Post on 17-Jan-2016

29 views

Category:

Documents


2 download

DESCRIPTION

Md 3 Faktorisasi Lu Partisi Matriks

TRANSCRIPT

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

Page 2: Md 3 Faktorisasi Lu Partisi Matriks

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 

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 2 dari 18

Page 3: Md 3 Faktorisasi Lu Partisi Matriks

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: 

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 3 dari 18

Page 4: Md 3 Faktorisasi Lu Partisi Matriks

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

     

− − − −− − −⎡

⎢⎢⎢⎢

⎥⎥⎥⎥

⎢⎢⎢⎢

⎥⎥⎥⎥

⎢⎢⎢⎢

⎥⎥⎥⎥

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

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 4 dari 18

Page 5: Md 3 Faktorisasi Lu Partisi Matriks

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 

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 5 dari 18

Page 6: Md 3 Faktorisasi Lu Partisi Matriks

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. 

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 6 dari 18

Page 7: Md 3 Faktorisasi Lu Partisi Matriks

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

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. 

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 7 dari 18

Page 8: Md 3 Faktorisasi Lu Partisi Matriks

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 ) 

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 8 dari 18

Page 9: Md 3 Faktorisasi Lu Partisi Matriks

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

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

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 9 dari 18

Page 10: Md 3 Faktorisasi Lu Partisi Matriks

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

    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 

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 10 dari 18

Page 11: Md 3 Faktorisasi Lu Partisi Matriks

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

   ‐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 

 

 

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 11 dari 18

Page 12: Md 3 Faktorisasi Lu Partisi Matriks

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) 

 

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 12 dari 18

Page 13: Md 3 Faktorisasi Lu Partisi Matriks

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

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 

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 13 dari 18

Page 14: Md 3 Faktorisasi Lu Partisi Matriks

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

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

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 14 dari 18

Page 15: Md 3 Faktorisasi Lu Partisi Matriks

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

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.  

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 15 dari 18

Page 16: Md 3 Faktorisasi Lu Partisi Matriks

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

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

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 16 dari 18

Page 17: Md 3 Faktorisasi Lu Partisi Matriks

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

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

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

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 17 dari 18

Page 18: Md 3 Faktorisasi Lu Partisi Matriks

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.   

Modul 4 – Faktorisasi LU, Partisi Matriz dan Faktorisasi QR halaman 18 dari 18