Dekomposisi Cholesky

Mengapa Tidak Perlu Tukar Baris

Misalkan $A\in\mathbb{R}^{n\times n}$ simetris positif definit, yang berarti

x^TAx>0\qquad\text{untuk setiap }x\neq0

Syarat ini memastikan dekomposisi LU dapat dilakukan tanpa pertukaran baris. Dalam aritmetika eksak, $setiap pivot eliminasi bernilai positif$ .

Jadi, kita memperoleh faktorisasi $A = L \cdot U$ dengan elemen diagonal $U$ berupa pivot positif.

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

\begin{aligned} A &= A^T \\ &= (L \cdot U)^T \\ &= (L \cdot D \cdot \tilde{U})^T \\ &= \tilde{U}^T \cdot D \cdot L^T \end{aligned}

Pada persamaan tersebut, $\tilde{U}$ adalah matriks yang diagonal utamanya dinormalisasi menjadi $1$ , sedangkan $D$ adalah matriks diagonal:

\tilde{U} = \begin{pmatrix} 1 & \frac{u_{12}}{u_{11}} & \cdots & \frac{u_{1n}}{u_{11}} \\ & \ddots & \ddots & \vdots \\ & & 1 & \frac{u_{n-1,n}}{u_{n-1,n-1}} \\ 0 & & & 1 \end{pmatrix}

Ketika $L$ dan $\tilde U$ berdiagonal satu, dekomposisi $\mathrm{LU}$ ini unik. Perbandingan kedua faktorisasi menghasilkan

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

Definisikan matriks akar diagonal sebagai berikut.

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

Matriks tersebut memenuhi $D^{\frac{1}{2}} \cdot D^{\frac{1}{2}} = D$ .

Faktor Segitiga Bawah dengan Diagonal Positif

Setiap matriks real simetris positif definit $A \in \mathbb{R}^{n \times n}$ memiliki faktor Cholesky tunggal dengan elemen diagonal positif:

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

Matriks $\tilde{L} = L \cdot D^{\frac{1}{2}}$ merupakan matriks segitiga bawah yang dapat diinversi. Akar positif dari setiap pivot menetapkan tanda diagonal dan $membuat faktor Cholesky tersebut tunggal$ .

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

\tilde L=\begin{pmatrix}\tilde l_{11}&0&\cdots&0\\\tilde l_{21}&\tilde l_{22}&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\\tilde l_{n1}&\tilde l_{n2}&\cdots&\tilde l_{nn}\end{pmatrix}

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

Algoritma Cholesky

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

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

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

\tilde l_{ii}:=\sqrt{a_{ii}-\sum_{k=1}^{i-1}\tilde l_{ik}^2}

Hitung dahulu sisa entrinya:

r_{ji}=a_{ji}-\sum_{k=1}^{i-1}\tilde l_{jk}\tilde l_{ik}

Rumus kedua berlaku untuk $j = i + 1, \ldots, n$ .

$Besaran di dalam setiap akar$ harus tetap positif. Nilai nol atau negatif berarti bahwa masukan tidak positif definit atau pembulatan telah memengaruhi masalah yang hampir singular. Mengganti nilai tersebut dengan nilai mutlak akan mengubah relasi rekursif dan dapat menghasilkan faktor yang tidak memenuhi $A=LL^T$ .

Setelah algoritma selesai, kita memperoleh faktor Cholesky segitiga bawah:

\tilde L=\begin{pmatrix}\tilde l_{11}&0&\cdots&0\\\tilde l_{21}&\tilde l_{22}&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\\tilde l_{n1}&\tilde l_{n2}&\cdots&\tilde l_{nn}\end{pmatrix}

Memfaktorkan Matriks Positif Definit Ordo Dua

Faktorkan matriks

A=\begin{pmatrix}4&2\\2&5\end{pmatrix}

Elemen faktor segitiga bawah diperoleh langsung dari algoritma:

\tilde l_{11}=\sqrt4=2

Jadi,

\tilde L=\begin{pmatrix}2&0\\1&2\end{pmatrix}

Setelah faktor diketahui, selesaikan $Ax=b$ melalui $dua sistem segitiga$ : $\tilde Ly=b$ terlebih dahulu, kemudian $\tilde L^Tx=y$ . Cara ini menghindari perhitungan invers matriks.

Kompleksitas Algoritma Cholesky

Algoritma Cholesky untuk menghitung faktor Cholesky $\tilde{L}$ dari $A \in \mathbb{R}^{n \times n}$ memerlukan:

\frac{1}{3}n^3 + O(n^2)\quad\text{flops}

Rumus tersebut menyatakan jumlah operasi aritmetika.

Biaya utama faktorisasi Cholesky terdiri atas sekitar $n^3/6$ perkalian dan $n^3/6$ penjumlahan. Jika digabungkan, totalnya sekitar $n^3/3$ operasi titik mengambang, kira-kira separuh biaya utama $2n^3/3$ untuk faktorisasi $\mathrm{LU}$ matriks rapat umum. Cholesky menghemat kerja dengan $memanfaatkan kesimetrian$ dan hanya menyimpan satu bagian segitiga dari faktorisasi.