Command Palette

Search for a command to run...

Metode Linear AI

Cholesky Dekomposisi

Dekomposisi LU untuk Matriks Positif Definit

Untuk matriks positif definit, ada sifat khusus yang membuat dekomposisi menjadi lebih sederhana. Dekomposisi LU dapat dilakukan tanpa menggunakan matriks permutasi PP karena eliminasi Gauss dapat berjalan tanpa pertukaran baris, dan semua elemen pivot yang dihasilkan dijamin positif.

Hal ini berarti kita memperoleh faktorisasi dalam bentuk A=L⋅UA = L \cdot U, di mana elemen diagonal dari UU adalah elemen pivot yang positif untuk semua indeks diagonal.

Karena A=ATA = A^T, kita juga memiliki:

A=AT=(L⋅U)T=(L⋅D⋅U~)T=U~T⋅D⋅LTA = A^T = (L \cdot U)^T = (L \cdot D \cdot \tilde{U})^T = \tilde{U}^T \cdot D \cdot L^T

di mana U~\tilde{U} adalah matriks yang diagonal utamanya dinormalisasi menjadi 1, dan DD adalah matriks diagonal:

U~=(1u12/u11⋯u1n/u11⋱⋱⋮1un−1,n/un−1,n−101)\tilde{U} = \begin{pmatrix} 1 & u_{12}/u_{11} & \cdots & u_{1n}/u_{11} \\ & \ddots & \ddots & \vdots \\ & & 1 & u_{n-1,n}/u_{n-1,n-1} \\ 0 & & & 1 \end{pmatrix}
D=(u110⋱0unn)D = \begin{pmatrix} u_{11} & & 0 \\ & \ddots & \\ 0 & & u_{nn} \end{pmatrix}

Karena dekomposisi LU tanpa PP adalah unik, maka:

A=L⋅U=U~T⋅(D⋅LT)A = L \cdot U = \tilde{U}^T \cdot (D \cdot L^T)
L=U~TdanU=D⋅LTL = \tilde{U}^T \quad \text{dan} \quad U = D \cdot L^T

Jika kita mendefinisikan:

D12=(u110⋱0unn)D^{\frac{1}{2}} = \begin{pmatrix} \sqrt{u_{11}} & & 0 \\ & \ddots & \\ 0 & & \sqrt{u_{nn}} \end{pmatrix}

maka D12⋅D12=DD^{\frac{1}{2}} \cdot D^{\frac{1}{2}} = D.

Dekomposisi Cholesky

Matriks positif definit A∈Rn×nA \in \mathbb{R}^{n \times n} memungkinkan adanya dekomposisi Cholesky:

A=L⋅D⋅LT=L~⋅L~TA = L \cdot D \cdot L^T = \tilde{L} \cdot \tilde{L}^T

dengan L~=L⋅D12\tilde{L} = L \cdot D^{\frac{1}{2}} adalah matriks segitiga bawah reguler. Matriks ini dapat dihitung menggunakan algoritma Cholesky.

Perhitungan matriks L~\tilde{L} dilakukan dengan:

L~=(l~110⋮⋱l~n1⋯l~nn)\tilde{L} = \begin{pmatrix} \tilde{l}_{11} & 0 \\ \vdots & \ddots \\ \tilde{l}_{n1} & \cdots & \tilde{l}_{nn} \end{pmatrix}

berdasarkan hubungan L~⋅L~T=A\tilde{L} \cdot \tilde{L}^T = A. Algoritma berikut menghasilkan faktor Cholesky.

Algoritma Cholesky

Diberikan matriks positif definit A∈Rn×nA \in \mathbb{R}^{n \times n}.

l~11:=a11\tilde{l}_{11} := \sqrt{a_{11}}
l~j1:=aj1l~11,j=2,…,n\tilde{l}_{j1} := \frac{a_{j1}}{\tilde{l}_{11}}, \quad j = 2, \ldots, n

Untuk i=2,…,ni = 2, \ldots, n:

l~ii:=aii−l~i12−l~i22−…−l~i,i−12\tilde{l}_{ii} := \sqrt{a_{ii} - \tilde{l}_{i1}^2 - \tilde{l}_{i2}^2 - \ldots - \tilde{l}_{i,i-1}^2}
l~ji:=l~ii−1⋅(aji−l~j1l~i1−l~j2l~i2−…−l~j,i−1l~i,i−1)\tilde{l}_{ji} := \tilde{l}_{ii}^{-1} \cdot \left( a_{ji} - \tilde{l}_{j1}\tilde{l}_{i1} - \tilde{l}_{j2}\tilde{l}_{i2} - \ldots - \tilde{l}_{j,i-1}\tilde{l}_{i,i-1} \right)

untuk j=i+1,…,nj = i + 1, \ldots, n.

Setelah menjalankan algoritma ini, kita akan mendapatkan faktor Cholesky yang merupakan matriks segitiga bawah:

L~=(l~110⋮⋱l~n1⋯l~nn)\tilde{L} = \begin{pmatrix} \tilde{l}_{11} & 0 \\ \vdots & \ddots \\ \tilde{l}_{n1} & \cdots & \tilde{l}_{nn} \end{pmatrix}

Kompleksitas Algoritma Cholesky

Algoritma Cholesky untuk menghitung faktor Cholesky L~\tilde{L} dari A∈Rn×nA \in \mathbb{R}^{n \times n} memerlukan:

16n3+O(n2)\frac{1}{6}n^3 + O(n^2)

operasi aritmetika.

Hal ini merupakan setengah dari jumlah operasi yang diperlukan untuk menghitung dekomposisi LU, karena penggunaan simetri memungkinkan kita melakukan perhitungan tanpa pertukaran baris dalam urutan yang berbeda.

Sebelumnya

LU Dekomposisi

Selanjutnya

QR Dekomposisi