Dekomposisi Matriks:Dekomposisi LU Pada R/RStudio
Shafira Halmahera
28/10/2021
Dosen Pengampu : Prof. Dr. Suhartono, M.Kom
Lembaga : Universitas Islam Negeri Maulana Malik Ibrahim Malang
Jurusan : Teknik Informatika
Fakultas : Sains dan Teknologi
🟤Dekomposisi Matriks🟤 |
Seringkali kita diminta untuk memperoleh nilai penyelesaian suatu persamaan linier Ax=B , dimana nilai vektorByangselaluberubah-ubah. Penggunaan metode eliminasi Gauss mengharuskan untuk menyelesaikan sistem persamaan linierx=Bsecara 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 .
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).
Jika diperhatikan, kita dapat mengetahui mengetahui nilai x=tnu,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
Simpan pengali tiap tahapan pada masing-masing elemen matriks L . Hasil operasi tersebut akan menghasilkan matriks triangular U
Simpan pengali tiap tahapan pada masing-masing elemen matriks L . Hasil operasi tersebut akan menghasilkan matriks triangular U
Algoritma Dekomposisi LU
1). Masukkan matriks A , dan vektor B beserta ukurannya n
2). Lakukan langkah poin ke-4 s/d poin 5 untuk meperoleh matriks U
3). Untuk baris ke- i di mana i=1 s/d n , perhatikan apakah nilai ai,j sama dengan nol
Bila iya, lakukan row swapping antara baris ke- i dan baris ke- i+k≤n , dimana ai+k,j tidak sama dengan nol. Bila tidak ada berarti perhitungan tidak bisa dilanjutkan dan proses dihentikan dengan tanpa penyelesaian.
Bila tidak, lanjutkan.
4). Untuk baris ke- , dimana j=i+1 s/d n , lakukan operasi baris elementer
Hitung c=aj,iai,i
untuk kolom k , dimana k=1 s/d n+1 , hitung aj,k=aj,k−ci.ai,k
5). Lakukan langkah poin ke-7 s/d poin 9 untuk memperoleh matriks L
6). Untuk diagonal matriks L isikan dengan nilai 1 dan elemen di atas diagonal dengan nilai nol
7). Untuk elemen di bawah diagonal isikan dengan faktor pengali operasi baris elementer matriks U .
8). Lakukan proses forward substitution menggunakan Persamaan (6.27) untuk memperoleh nilai vektor t .
9). 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 A , kita dapat mengalikan matriks , U , dan P.
decomp$L%*%decomp$U%*%decomp$PContoh 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] 1.19 -0.37 0.126 -1.59 2.092 ...
## ..@ perm : int [1:3] 1 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.0000000 . .
## [2,] -0.3697479 1.0000000 .
## [3,] 0.1260504 0.4925289 1.0000000
##
## $U
## 3 x 3 Matrix of class "dtrMatrix"
## [,1] [,2] [,3]
## [1,] 1.1900000 -1.5900000 -0.2200000
## [2,] . 2.0921008 0.2086555
## [3,] . . 0.9549622
##
## $P
## 3 x 3 sparse Matrix of class "pMatrix"
##
## [1,] | . .
## [2,] . . |
## [3,] . | .