Dekomposisi Matriks Pada RStudio
Heny Rimadana, Prof. Dr. Suhartono, M.Kom
10/26/2021
Mata Kuliah : Kalkulus
Prodi : Teknik Informatika
Lembaga : Universitas Islam Negeri Maulana Malik Ibrahim Malang
Dekomposisi Matriks Pada RStudio
Seringkali kita diminta untuk memperoleh nilai penyelesaian suatu persamaan linier Ax=BAx=B, dimana nilai vektor BB yang selalu berubah-ubah. Penggunaan metode eliminasi Gauss mengharuskan untuk menyelesaikan sistem persamaan linier Ax=BAx=B secara terpisah untuk setiap perubahan vektor BB. 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 AA, hasil pemecahan ini selanjutnya digunakan untuk memperoleh penyelesaian sistem persamaan linier melalui perkalian antara vektor BB dan hasil faktorisasi matriks AA.
Dekomposisi LU Pada RStudio
Misalkan kita memiliki persamaan linier seperti yang ditunjukkan oleh Persamaan (6.12). Pada metode dekomposisi LU, matriks AA difaktorkan menjadi matriks LL dan matriks UU, dimana ukuran kedua matriks tersebut harus sama dengan ukuran matriks AA atau dapat kita tuliskan bahwa hasil perkalian kedua matriks tersebut akan menghasilkan matriks AA.
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 LL merupakan matriks segitiga bawah dengan nilai nol berada pada bagian atas diagonal utama, penyelesaian tt 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 LL akan berupa matriks persegi dengan ukuran mm, di mana mm merupakan jumlah baris matriks AA. Persamaan (6.25) dalam bentuk matriks akan terlihat seperti Persamaan (6.26).
Jika diperhatikan, kita dapat mengetahui mengetahui nilai xn=tnum,nxn=tnum,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 AA. Solusi untuk melakukan dekomposisi bisa jadi tak terhingga, namun solusi yang paling sederhana adalah mengubah matriks AA menjadi matriks row echelon form. Kedua, LL harus menjadi matriks segitiga bawah yang mereduksi ke-ll dengan mengikuti operasi baris yang sama yag menghasilkan UU. Kita dapat menggunakan algoritma Doolittle untuk menghasilkan LL, 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 UU 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 AA 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, PP. Matriks ini merupakan matriks identitas dengan ukuran sama dengan matriks AA. Jika pertukaran baris dilakukan selama proses pembentukan matriks UU, maka pertukaran baris yang sama juga akan diimplemenntasikan pada matriks PP. oleh karena itu, dalam praktiknya matriks A=PLUA=PLU dan perkalian dengan matriks PP berfungsi untuk mengembalikan urutan baris.
Contoh 6.6 Selesaikan sistem persamaan linier berikut menggunakan faktorisasi LU
Simpan pengali tiap tahapan pada masing-masing elemen matriks LL. Hasil operasi tersebut akan menghasilkan matriks triangular UU.
Algoritma Dekomposisi LU
Masukkan matriks AA, dan vektor BB beserta ukurannya nn
Lakukan langkah poin ke-4 s/d poin 5 untuk meperoleh matriks UU.
Untuk baris ke-ii di mana i=1i=1 s/d nn, perhatikan apakah nilai ai,jai,j sama dengan nol.
Bila iya, lakukan row swapping antara baris ke-ii dan baris ke-i+k≤ni+k≤n, dimana ai+k,jai+k,j tidak sama dengan nol. Bila tidak ada berarti perhitungan tidak bisa dilanjutkan dan proses dihentikan dengan tanpa penyelesaian.
Bila tidak, lanjutkan.
- Untuk baris ke-jj, dimana j=i+1j=i+1 s/d nn, lakukan operasi baris elementer:
Hitung c=aj,iai,ic=aj,iai,i
untuk kolom kk, dimana k=1k=1 s/d n+1n+1, hitung aj,k=aj,k−ci.ai,kaj,k=aj,k−ci.ai,k
Lakukan langkah poin ke-7 s/d poin 9 untuk memperoleh matriks LL
Untuk diagonal matriks LL isikan dengan nilai 1 dan elemen di atas diagonal dengan nilai nol.
Untuk elemen di bawah diagonal isikan dengan faktor pengali operasi baris elementer matriks UU.
Lakukan proses forward substitution menggunakan Persamaan (6.27) untuk memperoleh nilai vektor tt.
Lakukan backward substituion menggunakan Persamaan (6.16).
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 AA, kita dapat mengalikan matriks LL, UU, dan PP.
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!
⎡⎢ ⎢⎣01−11597−1−5⎤⎥ ⎥⎦[01−11597−1−5]
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 AA.
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,] . | .