Dekomposisi Matriks
Salsabila Ramadanti Nuraini, Prof.Dr.Suhartono,M.Kom
12/4/2021
Universitas : UIN Maulana Malik Ibrahim Malang
Jurusan : Teknik Informatika
Faktorisasi atau dekomposisi matriks merupakan suatu algoritma untuk memecah matriks A, hasil pemecahan ini selanjutnya digunakan untuk memperoleh penyelesaian sistem persamaan linier melalui perkalian antara vektor B dan hasil faktorisasi matriks A.
1. Dekomposisi LU
Pada metode dekomposisi LU, matriks A difaktorkan menjadi matriks L dan matriks U, dimana ukuran kedua matriks tersebut harus sama dengan ukuran matriks A atau dapat kita tuliskan bahwa hasil perkalian kedua matriks tersebut akan menghasilkan matriks A.
Dekomposisi LU didasarkan pada operasi baris elementer. Pertama, kita perlu menemukan matriks segitiga atas yang sesuai dengan matriks A. Solusi untuk melakukan dekomposisi bisa jadi tak terhingga, namun solusi yang paling sederhana adalah mengubah matriks A menjadi matriks row echelon form. Kedua, L harus menjadi matriks segitiga bawah yang mereduksi ke-l dengan mengikuti operasi baris yang sama yag menghasilkan U. Kita dapat menggunakan algoritma Doolittle untuk menghasilkan L, di mana nilai setiap entri dalam matriks segitiga bawah merupakan pengali yang digunakan untuk menghilangkan entri yang sesuai untuk setiap proses row replacement.
Berikut adalah sintaks yang digunakan.
lu_solve <- function(a, b=NULL){
m <- nrow(a)
n <- ncol(a)
piv <- 1
# membentuk matriks identitas P dan L
P <- L <- diag(n)
# cek elemen diagonal utama apakah bernilai nol
for(row_curr in 1:m){
if(piv <= n){
i <- row_curr
while(a[i, piv] == 0 && i < m){
i <- i + 1
if(i > m){
i <- row_curr
piv <- piv + 1
if(piv > n)
return(list(P = P, L = L, U = a))
}
}
# jika elemen diagonal utama bernilai nol,lakukan row swapping
if(i != row_curr){
a <- swap_row(a, i, row_curr)
P <- swap_row(P, i, row_curr)
}
# pembentukan matriks L dan U
for(j in row_curr:m)
if(j != row_curr){
k <- a[j, piv]/a[row_curr, piv]
# matriks U
a <- replace_row(a, row_curr, j, -k)
# pengisian elemen matriks L
L[j, piv] <- k
}
piv <- piv + 1
}
}
# penyelesaian persamaan linier
if(is.null(b)){
return(list(P = P, L = L, U = a))
}else{
# forward substitution
t <- forwardsolve(L, b)
# backward substitution
x <- backsolve(a, t)
return(list(P = P, L = L, U = a, result=x))
}
}# membuat matriks a dan vektor b
a <- matrix(c(1,2,3,-1,1,1,-1,2,
0,-1,-1,3,3,1,2,-1),
nrow=4)
b <- c(4,1,-3,4)
# penyelesaian
decomp<-lu_solve(a,b)Untuk membentuk kembali matriks A, kita dapat mengalikan matriks L,U, dan P.
decomp$L%*%decomp$U%*%decomp$PUntuk menampilkan hasil dekomposisi, jalankan fungsi expand().
decomp <- Matrix::expand(lum)
decomp
## $L
## 3 x 3 Matrix of class "dtrMatrix" (unitriangular)
## [,1] [,2] [,3]
## [1,] 1.0000 . .
## [2,] 0.7053 1.0000 .
## [3,] 0.5895 -0.2279 1.0000
##
## $U
## 3 x 3 Matrix of class "dtrMatrix"
## [,1] [,2] [,3]
## [1,] -0.9500 0.5300 1.7600
## [2,] . -0.6038 -0.7513
## [3,] . . 0.1913
##
## $P
## 3 x 3 sparse Matrix of class "pMatrix"
##
## [1,] . . |
## [2,] | . .
## [3,] . | .2. Dekomposisi Cholesky
Dekomposisi Cholesky memberikan faktorisasi matriks alternatif sehingga A=LLT, di mana LT merupakan transpose konjugat dari matriks L. Dalam kasus ini, penulis hanya bekerja dengan matriks rill dengan nilai rill dan bagian imajiner nol. Jadi untuk tujuan sub-chapter ini, matriks LT hanyalah transpose dari matriks L.
Fungsi tersebut disajikan pada sintaks berikut:
cholesky_solve <- function(a, b=NULL){
m <- nrow(a)
# membentuk matriks L dengan elemen nol
L = diag(0,m)
# Perhitungan elemen matriks L
for(i in 1:m){
for(k in 1:i){
p_sum <- 0
for(j in 1:k)
p_sum <- p_sum + L[j,i]*L[j,k]
# Pehitungan elemen diagonal utama
if(i==k)
L[k,i]<-sqrt(a[i,i]-p_sum)
else
L[k,i]<-(a[k,i]-p_sum)/L[k,k]
}
}
# Perhitungan elemn matriks L*
tL <- t(L)
# penyelesaian persamaan linier
if(is.null(b)){
return(list(L = L, tL = tL, a = a))
}else{
# forward substitution
t <- forwardsolve(L, b)
# backward substitution
x <- backsolve(tL, t)
return(list(L = L, tL = tL, a = a, result=x))
}
}Dekomposisi Cholesky menggunakan fungsi cholesky_solve(), disajikan pada sintaks berikut:
a <- matrix(c(9,-3,6,-3,17,-10,6,-10,12),3)
# dekomposisi Cholesky
(decomp<-cholesky_solve(a))## $L
## [,1] [,2] [,3]
## [1,] 3 -1 2
## [2,] 0 4 -2
## [3,] 0 0 2
##
## $tL
## [,1] [,2] [,3]
## [1,] 3 0 0
## [2,] -1 4 0
## [3,] 2 -2 2
##
## $a
## [,1] [,2] [,3]
## [1,] 9 -3 6
## [2,] -3 17 -10
## [3,] 6 -10 123. Dekomposisi Lainnya
3.1 Dekomposisi QR
Dekomposisi QR merupakan dekomposisi yang penting dalam menyelesaikan sistem persamaan linier. Dekomposisi ini juga berperan penting untuk menghitung koefisien regresi dan pengaplikasian algoritma Newton-Raphson.
Contoh penerapannya sebagai berikut.
?qr## starting httpd help server ... done# membuat matriks A dan B
set.seed(123)
A <- matrix((1:12)+rnorm(12), nrow=4)
b <- 2:5
# dekomposisi matriks A
qr(A)## $qr
## [,1] [,2] [,3]
## [1,] -6.3777985 -12.1257372 -19.850120
## [2,] 0.2774974 -6.3105459 -7.939245
## [3,] 0.7147777 -0.6461294 2.351193
## [4,] 0.6382310 -0.5653624 0.276672
##
## $rank
## [1] 3
##
## $qraux
## [1] 1.068915 1.512720 1.960964
##
## $pivot
## [1] 1 2 3
##
## attr(,"class")
## [1] "qr"# memperoleh penyelesaian SPL
qr.solve(A,b)## [1] 0.3045952 -0.1111081 0.32368623.2 Singular Value Decomposition
Singular value decomposition (SVD) merupakan algoritma faktorisasi matriks yang mendekomposisi matriks segiempat menjadi matriks UDVH, dimana D merupakan mmatriks diagonal non negatif,U dan V merupakan matriks unitary, dan VH merupakan matriks tanspose konjugat dari matriks V. Algoritma ini banyak digunakan dalam analisis principal component.
?svd# dekomposisi matriks A
svd(A)## $d
## [1] 26.094305 2.727495 1.329585
##
## $u
## [,1] [,2] [,3]
## [1,] -0.3684647 -0.5661362 0.6650563
## [2,] -0.4706958 -0.5703414 -0.6113237
## [3,] -0.5740273 0.4324050 -0.2589679
## [4,] -0.5596176 0.4089332 0.3419343
##
## $v
## [,1] [,2] [,3]
## [1,] -0.2257101 0.87169376 -0.4349769
## [2,] -0.5201583 -0.48536069 -0.7027520
## [3,] -0.8237052 0.06763865 0.56296963.3 Dekomposisi Eigen
Proses umum yang digunakan untuk menemukan nilai eigen dan vektor eigen suatu matriks segiempat dapat dilihat sebagai proses dari dekomposisi eigen. Proses ini akan mendekomposisi matriks menjadi VDV−1, dimana D merupakan matriks diagonal yang terbentuk dari nilai eigen, dan V merupakan vektor eigen. Proses dekomposisi ini akan berguna bagi pembaca yang ingin mempelajari principal component analysis.
Berikut contoh penerapannya.
?eigenA <- matrix(c(2,-1,0,-1,2,-1,0,-1,2), nrow=3)
# dekomposisi matriks A
eigen(A)## eigen() decomposition
## $values
## [1] 3.4142136 2.0000000 0.5857864
##
## $vectors
## [,1] [,2] [,3]
## [1,] -0.5000000 -7.071068e-01 0.5000000
## [2,] 0.7071068 1.099065e-15 0.7071068
## [3,] -0.5000000 7.071068e-01 0.5000000