Dekomposisi Cholesky

Dalam banyak kasus, kita sering diminta untuk mencari solusi dari sistem persamaan linier Ax = B, di mana vektor B selalu berubah-ubah. Jika kita menggunakan metode eliminasi Gauss, kita harus menyelesaikan sistem persamaan linier Ax = B secara terpisah untuk setiap perubahan vektor B. Namun, untuk menghindari bekerja dengan eliminasi yang berulang-ulang, kita dapat melakukan faktorisasi atau dekomposisi matriks sebagai langkah singkat dalam proses ini. Faktorisasi matriks merupakan algoritma untuk memecah matriks A, dan hasil pemecahan ini dapat digunakan untuk mencari solusi sistem persamaan linier melalui perkalian antara vektor B dan hasil faktorisasi matriks A.

Dekomposisi Cholesky

Dekomposisi Cholesky adalah suatu faktorisasi matriks alternatif yang menghasilkan hasil perkalian matriks L dengan transpose konjugatnya, L^T, sehingga A = LL^T. Dalam konteks ini, penulis hanya berurusan dengan matriks real dengan nilai riil dan bagian imajiner nol. Oleh karena itu, untuk tujuan sub-bab ini, matriks L^T hanyalah transpose dari matriks L.

Seperti halnya dekomposisi LU, dekomposisi Cholesky dapat digunakan untuk menyelesaikan sistem persamaan linier. Keuntungan yang dimiliki adalah proses pencarian dekomposisi Cholesky jauh lebih cepat dibandingkan dekomposisi LU. Namun, dekomposisi ini hanya dapat diterapkan pada jenis matriks tertentu. Matriks definit positif dan simetris adalah jenis matriks yang hanya dapat digunakan dalam dekomposisi Cholesky.

Untuk setiap elemen matriks A memiliki hubungan yang dituliskan pada Persamaan

Nilai tiap elemen diagonal utama yang tidak bernilai nol dihitung menggunakan Persamaan

Elemen diagonal dihitung menggunakan Persamaan

Algoritma Dekomposisi Cholesky

1. Masukkan matriks A, dan vektor B beserta ukurannya n.
2. Untuk elemen matriks L, hitung menggunakan Persamaan.

3. Untuk nilai diagonal utama matriks L, hitung menggunakan Persamaan (6.31).

4. Untuk memperoleh matriks LT, lakukan transpose pada matriks L.
5. Untuk memperoleh nilai x, -Hitung vektor t menggunakan Persamaan Lx=t. -Hitung vektor x menggunakan Persamaan Ux=t, dimana matriks U=LT.

Berdasarkan algoritma diatas, kita dapat menyusun kodingan pada R untuk melakukan dekomposisi Cholesky. Fungsi tersebut disajikan pada kodingan 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))
     }
}

Untuk contoh penggunaannya bisa kita lihat dengan soal ini.

Lakukan pengecekan pada hasil dekomposisi apakah hasil kali matriks dekomposisi akan menghasilkan matriks semula!

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   12

Fungsi lain yang dapat digunakan untuk melakukan dekomposisi Cholesky adalah menggunakan fungsi chol() pada Paket Matrix.

chol(a)

##      [,1] [,2] [,3]
## [1,]    3   -1    2
## [2,]    0    4   -2
## [3,]    0    0    2

Source : https://bookdown.org/moh_rosidi2610/Metode_Numerik/linearaljabar.html#ludecomp