# Nakafa Learning Content

> For AI agents: use [llms.txt](https://nakafa.com/llms.txt) for the site index. Markdown versions are available by appending `.md` to content URLs or sending `Accept: text/markdown`.

URL: https://nakafa.com/id/materi/ai-ds/metode-linear-ai/cholesky-dekomposisi
Source: https://raw.githubusercontent.com/nakafaai/nakafa.com/refs/heads/main/packages/contents/material/lesson/ai-ds/linear-methods/cholesky-decomposition/id.mdx

Pelajari dekomposisi Cholesky untuk matriks positif definit dengan algoritma efisien, faktorisasi segitiga bawah, dan analisis kompleksitas komputasi.

---

## Dekomposisi LU untuk Matriks Positif Definit

Untuk matriks positif definit, ada sifat khusus yang membuat dekomposisi menjadi lebih sederhana. [Dekomposisi LU](/id/materi/ai-ds/metode-linear-ai/lu-dekomposisi) dapat dilakukan tanpa menggunakan matriks permutasi $$P$$ karena eliminasi Gauss dapat berjalan tanpa pertukaran baris, dan semua elemen pivot yang dihasilkan dijamin positif.

Visible text: Untuk matriks positif definit, ada sifat khusus yang membuat dekomposisi menjadi lebih sederhana. [Dekomposisi LU](/id/materi/ai-ds/metode-linear-ai/lu-dekomposisi) dapat dilakukan tanpa menggunakan matriks permutasi 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 \cdot U$$, di mana elemen diagonal dari $$U$$ adalah elemen pivot yang positif untuk semua indeks diagonal.

Visible text: Hal ini berarti kita memperoleh faktorisasi dalam bentuk , di mana elemen diagonal dari adalah elemen pivot yang positif untuk semua indeks diagonal.

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

Visible text: Karena , kita juga memiliki:

Component: MathContainer
Children:

```math
A = A^T = (L \cdot U)^T = (L \cdot D \cdot \tilde{U})^T = \tilde{U}^T \cdot D \cdot L^T
```

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

Visible text: di mana adalah matriks yang diagonal utamanya dinormalisasi menjadi , dan adalah matriks diagonal:

Component: MathContainer
Children:

```math
\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}
```

```math
D = \begin{pmatrix} u_{11} & & 0 \\ & \ddots & \\ 0 & & u_{nn} \end{pmatrix}
```

Karena dekomposisi LU tanpa $$P$$ adalah unik, maka:

Visible text: Karena dekomposisi LU tanpa adalah unik, maka:

Component: MathContainer
Children:

```math
A = L \cdot U = \tilde{U}^T \cdot (D \cdot L^T)
```

```math
L = \tilde{U}^T \quad \text{dan} \quad U = D \cdot L^T
```

Jika kita mendefinisikan:

```math
D^{\frac{1}{2}} = \begin{pmatrix} \sqrt{u_{11}} & & 0 \\ & \ddots & \\ 0 & & \sqrt{u_{nn}} \end{pmatrix}
```

maka $$D^{\frac{1}{2}} \cdot D^{\frac{1}{2}} = D$$.

Visible text: maka .

## Dekomposisi Cholesky

Matriks positif definit $$A \in \mathbb{R}^{n \times n}$$ memungkinkan adanya dekomposisi Cholesky:

Visible text: Matriks positif definit memungkinkan adanya dekomposisi Cholesky:

```math
A = L \cdot D \cdot L^T = \tilde{L} \cdot \tilde{L}^T
```

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

Visible text: dengan adalah matriks segitiga bawah reguler. Matriks ini dapat dihitung menggunakan algoritma Cholesky.

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

Visible text: Perhitungan matriks dilakukan dengan:

```math
\tilde{L} = \begin{pmatrix} \tilde{l}_{11} & 0 \\ \vdots & \ddots \\ \tilde{l}_{n1} & \cdots & \tilde{l}_{nn} \end{pmatrix}
```

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

Visible text: berdasarkan hubungan . Algoritma berikut menghasilkan faktor Cholesky.

## Algoritma Cholesky

Diberikan matriks positif definit $$A \in \mathbb{R}^{n \times n}$$.

Visible text: Diberikan matriks positif definit .

Component: MathContainer
Children:

```math
\tilde{l}_{11} := \sqrt{a_{11}}
```

```math
\tilde{l}_{j1} := \frac{a_{j1}}{\tilde{l}_{11}}, \quad j = 2, \ldots, n
```

Untuk $$i = 2, \ldots, n$$:

Visible text: Untuk :

Component: MathContainer
Children:

```math
\tilde{l}_{ii} := \sqrt{a_{ii} - \tilde{l}_{i1}^2 - \tilde{l}_{i2}^2 - \ldots - \tilde{l}_{i,i-1}^2}
```

```math
\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, \ldots, n$$.

Visible text: untuk .

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

```math
\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 $$\tilde{L}$$ dari $$A \in \mathbb{R}^{n \times n}$$ memerlukan:

Visible text: Algoritma Cholesky untuk menghitung faktor Cholesky dari memerlukan:

```math
\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.