Macam-macam Dekomposisi Matriks Aljabar Linier
Imamatul Khoiriyah/Prof. Dr. Suhartono, M.Kom
10 November 2021
Prodi : Teknik Informatika
Lembaga : UIN Maulana Malik Ibrahim Malang
Dekomposisi Matriks
Seringkali kita diminta untuk memperoleh nilai penyelesaian suatu persamaan linier \(Ax=B\) , dimana nilai vektor \(B\) yang selalu berubah-ubah. Penggunaan metode eliminasi Gauss mengharuskan untuk menyelesaikan sistem persamaan linier \(Ax=B\) secara terpisah untuk setiap perubahan vektor \(B\). Untuk menghindari pekerjaan eliminasi yang selalu berulang-ulang, faktorisasi menjadi suatu hal yang dapat dilakukan untuk mempersingkat prosesnya. 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\).
Dekomposisi LU
Misalkan kita memiliki persamaan linier seperti yang ditunjukkan oleh Persamaan (6.12). 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\).
Sehingga Persamaan (6.12) akan menjadi Persamaan (6.23).
Langkah penyelesaian sistem persamaan linier, diawali dengan menghadirkan vektor tt yang ditunjukkan pada Persamaan (6.24).
Langkah pada Persamaan (6.24) tidak dimaksudkan untuk menghitung vektor \(t\), melainkan untuk menghitung vektor \(x\) . Vektor \(t\) diperoleh dengan menggunakan Persamaan (6.25).
Kita dapat menyelesaikan sistem persamaan yang ditunjukkan pada Persamaan (6.24) dan Persamaan (6.25) menggunakan berbagai algoritma penyelesaian yang telah dibahas sebelumnya. Namun, karena matriks \(L\) merupakan matriks segitiga bawah dengan nilai nol berada pada bagian atas diagonal utama, penyelesaian \(t\) mengambil langkah yang lebih sedikit. Kondisi ini sama dengan kondisi penyelesaian matriks tridiagonal, dimana kita memanfaatkan sejumlah jalan pintas penyelesaiaannya guna mempercepat komputasi. Matriks segitia bawah \(L\) akan berupa matriks persegi dengan ukuran \(m\), di mana \(m\) merupakan jumlah baris matriks \(A\). Persamaan (6.25) dalam bentuk matriks akan terlihat seperti Persamaan (6.26).
Berdasarkan Persamaan (6.26), diketahui nilai \(t1=b1\). Nilai ini selanjutnya dapat digunakan untuk melakukan proses substitusi guna memperoleh seluruh nilai vektor \(t\). Proses ini disebut sebagai foward substitution. Proses substitusi dapat dituliskan menggunakan Persamaan (6.27).
Seteleh nilai vektor \(t\) dihitung, kita dapat menghitung nilai \(x\) pada Persamaan (6.28).
Jika diperhatikan, kita dapat mengetahui mengetahui nilai \(xn =tn/um,n\) Nilai tersebut selanjutnya dapat digunakan untuk melakukan proses susbtitusi pada nilai lainnya. Proses substitusi ini disebut sebagai backward substitution. Proses dekomposisi atau faktorisasi LU digambarkan pada Gambar 6.1.
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.
Pada praktiknya, proses eliminasi Gauss untuk memperoleh matriks \(U\) kadang menghasilkan nol di kolom pivotnya. Kondisi tersebut mengharuskan kita untuk melakukan proses row swapping atau pertukaran baris (biasanya dengan baris bawahnya) untuk pivot bukan nol. Jika proses tersebut berhasil dilakukan bisa jadi matriks \(A\) mungkin setara dengan matriks LU, tetapi tidak sama dalam hal urutan nilai pada tiap barisnya. Agar kita dapat memperoleh hasil yang sama (matriks A sama dengan matriks LU), diperlukan matriks ketiga, \(P\) . Matriks ini merupakan matriks identitas dengan ukuran sama dengan matriks \(A\). Jika pertukaran baris dilakukan selama proses pembentukan matriks \(U\) , maka pertukaran baris yang sama juga akan diimplemenntasikan pada matriks \(P\) . oleh karena itu, dalam praktiknya matriks \(A=PLU\) dan perkalian dengan matriks \(P\) berfungsi untuk mengembalikan urutan baris.
Contoh 6.6 Selesaikan sistem persamaan linier berikut menggunakan faktorisasi LU
Jawab:
Nayatakan sistem persamaan tersebut ke dalam bentuk matriks \(Ax=b\) .
Lakukan operasi baris elementer pada matriks \(A\) untuk memperoleh matriks \(U\) . Urutan operasi baris elementer yang dilakukan adalah sebagai berikut:
Simpan pengali tiap tahapan pada masing-masing elemen matriks \(L\) . Hasil operasi tersebut akan menghasilkan matriks triangular \(U\).
Untuk matriks \(L\) sebagai berikut:
Karena pada proses operasi baris elementer tidak terdapat operasi pertukaran baris, maka matriks \(P\) tidak mengalami perubahan:
Lakukan operasi forward substitution menggunakan Persamaan (6.26).
Berdasarkan hasil perhitungan diperoleh nilai vektor \(t\) . 
Operasi terakhir yang perlu dilakukan untuk memperoleh nilai \(x\) adalah dengan melakukan backward substitution menggunakan nilai vektor \(t\) yang telah dihitung.
Berdasarkan hasil perhitungan diperoleh nilai \(x\) sebagai berikut:
Berdasarkan algoritma tersebut, kita dapat menyusun algoritma faktorisasi LU menggunakan R. 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))
}
}Kita dapat menyelesaikan sistem persamaan linier pada Contoh 6.6 menggunakan fungsi yang telah kita buat.
# 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$P
## [,1] [,2] [,3] [,4]
## [1,] 1 1 0 3
## [2,] 2 1 -1 1
## [3,] 3 -1 -1 2
## [4,] -1 2 3 -1Contoh 6.7 Lakukan dekomposisi LU pada matriks berikut dan lakukan pengecekan apakah perkalian hasil dekomposisi matriks akan menghasilkan matriks semula!
Jawab:
Lakukan proses dekomposisi menggunakan fungsi lu_solve().
# membentuk matriks a
(A <- matrix(c(0, 1, 7, 1, 5, -1, -2, 9, -5), 3))
## [,1] [,2] [,3]
## [1,] 0 1 -2
## [2,] 1 5 9
## [3,] 7 -1 -5
# dekomposisi lu
decomp<-lu_solve(A)Lakukan pengecekan apakah matriks hasil dekomposisi akan menghasilkan matriks \(A\) .
decomp$P %*% decomp$L %*% decomp$U
## [,1] [,2] [,3]
## [1,] 0 1 -2
## [2,] 1 5 9
## [3,] 7 -1 -5Fungsi lu() pada Paket Matrix dapat digunakan untuk melakukan dekomposisi LU. Untuk meggunakan fungsi tersebut, kita harus menginstall dan mengaktifkan Paket Matrix.
install.packages("Matrix")
library(Matrix)Untuk dapat menggunakannya kita hanya perlu menginputkan matriks kedalam fungsi tersebut. Berikut adalah contoh penerapannya:
# membuat matriks a
a <- Matrix::Matrix(round(rnorm(9),2), nrow=3)
# dekomposisi
lum <- Matrix::lu(a)
lum
## 'MatrixFactorization' of Formal class 'denseLU' [package "Matrix"] with 4 slots
## ..@ x : num [1:9] -0.95 0.705 0.589 0.53 -0.604 ...
## ..@ perm : int [1:3] 2 3 3
## ..@ Dimnames:List of 2
## .. ..$ : NULL
## .. ..$ : NULL
## ..@ Dim : int [1:2] 3 3Untuk 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,] . | .Dekomposisi Cholesky
Dekomposisi Cholesky memberikan faktorisasi matriks alternatif sehingga \(A=LL^T\) , di mana \(L^T\) 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 \(L^T\) hanyalah transpose dari matriks \(L\) .
Seperti dekomposisi LU, dekomposisi Cholesky dapat digunakan untuk menyelesaikan sistem persamaan linier. Kelebihannya, Menemukan dekomposisi Cholesky jauh lebih cepat daripada dekomposisi LU. Namun, dekomposisi ini hanya terbatas pada matriks tertentu saja. Dekomposisi Cholesky hanya dapat digunakan pada matriks definit positif dan simetris. Matriks simeteris merupakan matriks yang nilai di atas dan di bawah diagonalnya simetris atau sama; secara matematis, untuk semua \(i\) dan \(j\) pada matriks \(A\), \(ai;j=aj;i\) . Definit positif berarti bahwa setiap entri pivot (nilai elemen diagonal utama) selelu bernilai positif. Selain itu, untuk matriks definit positif, hubungan \(xAx\) K>0 untuk semua vektor, \(x\) .
Karena \(L^*\) transpose dari matriks \(L\) , makan\(l^ti,j = lj,i\) untuk semua nilai \(i\) dan \(j\) . Tanpa kendala (constraint) ini, dekomposisi Cholesky akan mirip dekomposisi LU. Tetapi dengan kendala ini, nilai elemen matriks \(L\) dan \(L^T\) harus dipilih dengan cermat sehingga hubungan \(A=LL^T\) berlaku. Bentuk dekomposisi Cholesky disajikan pada Persamaan (6.29).
Untuk setiap elemen matriks \(A\) memiliki hubungan yang dituliskan pada Persamaan (6.30).
Berdasarkan Persamaan (6.29), sejumlah nilai elemen \(Li,k\) dan \(Lk,j\) adalah nol. Nilai tiap elemen diagonal utama yang tidak bernilai nol dihitung menggunakan Persamaan (6.31).
Elemen diagonal dihitung menggunakan Persamaan (6.32)
Berdasarkan algoritma tersebut, kita dapat menyusun fungsi pada R untuk melakukan dekomposisi Cholesky. 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))
}
}Contoh 6.8 Dengan menggunakan fungsi cholesky_solve(), lakukan dekomposisi pada matriks berikut! Lakukan pengecekan pada hasil dekomposisi apakah hasil kali matriks dekomposisi akan menghasilkan matriks semula!
Jawab:
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 12
# mengecek hasil dekomposisi
decomp$tL %*% decomp$L
## [,1] [,2] [,3]
## [1,] 9 -3 6
## [2,] -3 17 -10
## [3,] 6 -10 12Fungsi lain yang dapat digunakan untuk melakukan dekomposisi Cholesky adalah menggunakan fungsi chol() pada Paket Matrix. Pada fungsi tersebut, kita hanya perlu menginputkan objek matrik kedalamnya. Berikut adalah contoh penerapan fungsi tersebut menggunakan matriks pada Contoh 6.8.
chol(a)
## [,1] [,2] [,3]
## [1,] 3 -1 2
## [2,] 0 4 -2
## [3,] 0 0 2Penting!!!
Fungsi
chol()hanya menampilkan matriks \(L^T\) . Untuk menampilkan matriks \(L\) , kita perlu melakukan transpose
Dekomposisi Lainnya
Terdapat beberapa algoritma lain yang telah dikembangkan untuk melakukan dekomposisi matriks. Pada buku ini hanya akan dijelaskan secara singkat terkait fungsi yang digunakan dalam melakukan dekomposisi matriks. Algoritma yang akan dijelaskan pada sub-chapter ini antara lain: QR, singular value decomposition (SVD), dan dekomposisi eigen. Untuk algoritma lainnya, pembaca dapat membaca buku terkait atau mengecek dokumentasinya pada Paket base.
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.
Untuk memperoleh informasi terkait dekomposisi ini, pembaca dapat mengetikkan sintaks berikut pada R:
?qrBerikut merupakan contoh penerapan fungsi qr() untuk menyelesaikan sistem persamaan linier:
# 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.3778 -12.1257 -19.8501
## [2,] 0.2775 -6.3105 -7.9392
## [3,] 0.7148 -0.6461 2.3512
## [4,] 0.6382 -0.5654 0.2767
##
## $rank
## [1] 3
##
## $qraux
## [1] 1.069 1.513 1.961
##
## $pivot
## [1] 1 2 3
##
## attr(,"class")
## [1] "qr"
# memperoleh penyelesaian SPL
qr.solve(A,b)
## [1] 0.3046 -0.1111 0.3237Singular Value Decomposition
ingular value decomposition (SVD) merupakan algoritma faktorisasi matriks yang mendekomposisi matriks segiempat menjadi matriks \(UDVH\) , dimana \(D\) merupakan matriks 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.
Pada R, SVD dapat dilakukan menggunakan fungsi svd() dari Paket base. Berikut adalah sintaks untuk memperoleh informasi terkait fungsi tersebut:
?svdBerikut adalah contoh penerapan fungsi svd():
# dekomposisi matriks A
svd(A)
## $d
## [1] 26.094 2.727 1.330
##
## $u
## [,1] [,2] [,3]
## [1,] -0.3685 -0.5661 0.6651
## [2,] -0.4707 -0.5703 -0.6113
## [3,] -0.5740 0.4324 -0.2590
## [4,] -0.5596 0.4089 0.3419
##
## $v
## [,1] [,2] [,3]
## [1,] -0.2257 0.87169 -0.4350
## [2,] -0.5202 -0.48536 -0.7028
## [3,] -0.8237 0.06764 0.5630Dekomposisi 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\) erupakan 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.
Fungsi eigen() pada Paket base dapat digunakan untuk melakukan dekomposisi eigen. Untuk mempelajari lebih jauh terkait fungsi ini, pambaca dapat menjalankan sintaks berikut:
?eigenBerikut adalah contoh sintaks untuk melakukan dekomposisi eigen:
A <- matrix(c(2,-1,0,-1,2,-1,0,-1,2), nrow=3)
# dekomposisi matriks A
eigen(A)
## eigen() decomposition
## $values
## [1] 3.4142 2.0000 0.5858
##
## $vectors
## [,1] [,2] [,3]
## [1,] -0.5000 -7.071e-01 0.5000
## [2,] 0.7071 1.099e-15 0.7071
## [3,] -0.5000 7.071e-01 0.5000REFERENSI:
https://bookdown.org/moh_rosidi2610/Metode_Numerik/linearaljabar.html#dekomposisimatriks