# 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/qr-dekomposisi
Source: https://raw.githubusercontent.com/nakafaai/nakafa.com/refs/heads/main/packages/contents/material/lesson/ai-ds/linear-methods/qr-decomposition/id.mdx
Pelajari QR dekomposisi menggunakan metode Gram-Schmidt dan Householder untuk faktorisasi matriks, transformasi ortogonal, dan sistem linear.
---
## Teorema Eksistensi QR Dekomposisi
Kita ingin mengubah matriks menjadi bentuk segitiga atas, tetapi bukan melalui operasi baris elementer, melainkan melalui transformasi ortogonal yang lebih baik kondisinya. Bayangkan seperti memutar dan memantulkan ruang geometris untuk menyederhanakan matriks, tanpa mengubah sifat fundamentalnya.
Misalkan $$A \in \mathbb{R}^{m \times n}$$ adalah matriks persegi panjang dengan $$m \geq n$$ dan $$\text{Peringkat}A = n$$. Maka terdapat matriks ortogonal $$Q \in \mathbb{R}^{m \times m}$$ dengan $$Q^T Q = I$$ dan matriks segitiga atas $$R \in \mathbb{R}^{m \times n}$$ dengan elemen diagonal $$r_{ii} > 0$$ untuk $$i = 1, \ldots, n$$, sehingga:
Visible text: Misalkan adalah matriks persegi panjang dengan dan . Maka terdapat matriks ortogonal dengan dan matriks segitiga atas dengan elemen diagonal untuk , sehingga:
```math
A = Q \cdot R
```
Representasi ini disebut QR dekomposisi dari $$A$$.
Visible text: Representasi ini disebut QR dekomposisi dari .
### Pembuktian dengan Gram-Schmidt
Kolom-kolom $$a_j$$ untuk $$j = 1, \ldots, n$$ dari matriks $$A$$ dapat diorthonormalisasi menggunakan proses Gram-Schmidt:
Visible text: Kolom-kolom untuk dari matriks dapat diorthonormalisasi menggunakan proses Gram-Schmidt:
Component: MathContainer
Children:
```math
\tilde{q}_j := a_j - \sum_{k=1}^{j-1} \langle a_j, q_k \rangle \cdot q_k
```
```math
q_j := \frac{\tilde{q}_j}{\|\tilde{q}_j\|_2}
```
Kita memperoleh vektor ortonormal $$q_j$$ untuk $$j = 1, \ldots, n$$ sebagai kolom dari matriks ortogonal $$Q_1 \in \mathbb{R}^{m \times n}$$. Sebaliknya:
Visible text: Kita memperoleh vektor ortonormal untuk sebagai kolom dari matriks ortogonal . Sebaliknya:
Component: MathContainer
Children:
```math
a_j = \sum_{k=1}^{j-1} \langle a_j, q_k \rangle \cdot q_k + \tilde{q}_j
```
```math
= \sum_{k=1}^{j-1} \langle a_j, q_k \rangle \cdot q_k + \|\tilde{q}_j\|_2 \cdot q_j
```
```math
= \sum_{k=1}^{j-1} q_k \cdot r_{kj} + q_j \cdot r_{jj}
```
Jadi $$A = Q_1 R_1$$ dengan matriks segitiga atas $$R_1 \in \mathbb{R}^{n \times n}$$ yang elemen diagonalnya $$r_{ii} = \|\tilde{q}_i\|_2 > 0$$.
Visible text: Jadi dengan matriks segitiga atas yang elemen diagonalnya .
Jika $$Q_1$$ dilengkapi dengan $$m - n$$ kolom tambahan menjadi matriks ortogonal $$Q = (Q_1 \quad Q_2) \in \mathbb{R}^{m \times m}$$ dan $$R_1$$ menjadi $$R = \begin{pmatrix} R_1 \\ 0 \end{pmatrix} \in \mathbb{R}^{m \times n}$$, maka $$A = Q_1 R_1 = QR$$.
Visible text: Jika dilengkapi dengan kolom tambahan menjadi matriks ortogonal dan menjadi , maka .
## QR Dekomposisi Penuh dan Ekonomis
Ketika kita memiliki matriks $$A \in \mathbb{R}^{m \times n}$$ dengan $$m \geq n$$,
ada dua cara untuk merepresentasikan QR dekomposisi. Perbedaannya terletak pada ukuran matriks yang digunakan.
Visible text: Ketika kita memiliki matriks dengan ,
ada dua cara untuk merepresentasikan QR dekomposisi. Perbedaannya terletak pada ukuran matriks yang digunakan.
### QR Dekomposisi Penuh
QR dekomposisi penuh menggunakan matriks berukuran penuh:
```math
A = Q \cdot R
```
dengan $$Q \in \mathbb{R}^{m \times m}$$ adalah matriks ortogonal berukuran penuh dan
$$R \in \mathbb{R}^{m \times n}$$ adalah matriks segitiga atas.
Visible text: dengan adalah matriks ortogonal berukuran penuh dan
adalah matriks segitiga atas.
### QR Dekomposisi Ekonomis
Karena bagian bawah matriks $$R$$ hanya berisi nol, kita bisa menghemat penyimpanan dan komputasi.
QR dekomposisi ekonomis hanya menggunakan bagian yang benar-benar diperlukan:
Visible text: Karena bagian bawah matriks hanya berisi nol, kita bisa menghemat penyimpanan dan komputasi.
QR dekomposisi ekonomis hanya menggunakan bagian yang benar-benar diperlukan:
```math
A = Q \cdot R = (Q_1 \quad Q_2) \cdot \begin{pmatrix} R_1 \\ 0 \end{pmatrix} = Q_1 \cdot R_1
```
Di sini $$Q_1 \in \mathbb{R}^{m \times n}$$ hanya mengambil kolom pertama sampai ke-$$n$$
dari $$Q$$, dan $$R_1 \in \mathbb{R}^{n \times n}$$ adalah matriks segitiga atas persegi.
Visible text: Di sini hanya mengambil kolom pertama sampai ke-
dari , dan adalah matriks segitiga atas persegi.
Mengapa disebut ekonomis? Karena kita menghemat ruang penyimpanan dan waktu komputasi.
Alih-alih menyimpan matriks $$Q$$ berukuran $$m \times m$$ yang bisa sangat besar,
kita hanya perlu $$Q_1$$ berukuran $$m \times n$$.
Visible text: Mengapa disebut ekonomis? Karena kita menghemat ruang penyimpanan dan waktu komputasi.
Alih-alih menyimpan matriks berukuran yang bisa sangat besar,
kita hanya perlu berukuran .
Kolom-kolom matriks $$Q_2 \in \mathbb{R}^{m \times (m-n)}$$ yang tidak kita pakai membentuk
basis ortonormal dari kernel (ruang nol) $$\text{Kernel}A^T$$:
Visible text: Kolom-kolom matriks yang tidak kita pakai membentuk
basis ortonormal dari kernel (ruang nol) :
```math
A^T Q_2 = R_1^T Q_1^T Q_2 = 0
```
Di sini kernel dari $$A^T$$ adalah himpunan semua vektor $$x$$ yang memenuhi $$A^T x = 0$$.
Visible text: Di sini kernel dari adalah himpunan semua vektor yang memenuhi .
### Sifat Keunikan
QR dekomposisi ekonomis $$A = Q_1 \cdot R_1$$ dengan kondisi $$r_{ii} > 0$$
untuk semua $$i = 1, \ldots, n$$ adalah unik untuk matriks $$A$$
yang memiliki peringkat penuh.
Visible text: QR dekomposisi ekonomis dengan kondisi
untuk semua adalah unik untuk matriks
yang memiliki peringkat penuh.
## Metode Householder untuk QR Dekomposisi
Meskipun proses Gram-Schmidt memberikan cara teoretis yang elegan untuk memperoleh QR dekomposisi,
metode ini tidak cocok untuk perhitungan praktis. Masalah utamanya adalah ketidakstabilan numerik akibat pembatalan,
ortogonalitas kolom-kolom cepat hilang selama komputasi.
Untuk mengatasi masalah ini, kita memerlukan metode yang lebih stabil secara numerik.
Salah satu pendekatan yang paling berhasil adalah prosedur Householder,
yang menggunakan transformasi refleksi ortogonal. Alternatif lain adalah prosedur Givens dengan transformasi rotasi.
### Transformasi Householder
Untuk vektor $$v \in \mathbb{R}^m$$ dengan $$\|v\|_2 = 1$$,
kita dapat mendefinisikan matriks transformasi Householder:
Visible text: Untuk vektor dengan ,
kita dapat mendefinisikan matriks transformasi Householder:
```math
S = I - 2vv^T \in \mathbb{R}^{m \times m}
```
Perhatikan bahwa $$vv^T$$ adalah produk diadik (outer product), yaitu perkalian vektor kolom
$$v \in \mathbb{R}^{m \times 1}$$ dengan vektor baris $$v^T \in \mathbb{R}^{1 \times m}$$.
Hasil perkalian ini adalah matriks $$m \times m$$ dengan peringkat 1 untuk $$v \neq 0$$.
Jangan sampai tertukar dengan perkalian skalar $$v^T v \in \mathbb{R}$$ yang menghasilkan bilangan tunggal.
Visible text: Perhatikan bahwa adalah produk diadik (outer product), yaitu perkalian vektor kolom
dengan vektor baris .
Hasil perkalian ini adalah matriks dengan peringkat 1 untuk .
Jangan sampai tertukar dengan perkalian skalar yang menghasilkan bilangan tunggal.
## Sifat-sifat Transformasi Householder
Misalkan $$S = I - 2vv^T \in \mathbb{R}^{m \times m}$$ adalah matriks transformasi Householder
untuk vektor $$v \in \mathbb{R}^m$$ dengan $$\|v\|_2 = 1$$. Maka berlaku:
Visible text: Misalkan adalah matriks transformasi Householder
untuk vektor dengan . Maka berlaku:
1. $$S$$ adalah simetri: $$S^T = S$$
2. $$S$$ adalah matriks ortogonal: $$S^T S = I$$
3. Perkalian $$S \cdot x$$ dari $$S$$ dari kiri dengan vektor $$x \in \mathbb{R}^n$$
menyebabkan refleksi $$x$$ pada subruang $$\text{rentang}(v)^{\perp}$$,
yaitu pada hiperplane (bidang datar berdimensi tinggi) dengan vektor normal $$v$$
4. $$\text{cond}_2(S) = 1$$
Visible text: 1. adalah simetri:
2. adalah matriks ortogonal:
3. Perkalian dari dari kiri dengan vektor
menyebabkan refleksi pada subruang ,
yaitu pada hiperplane (bidang datar berdimensi tinggi) dengan vektor normal
4.
## Prosedur Householder
Diberikan matriks $$A \in \mathbb{R}^{m \times n}$$ dengan $$m \geq n$$
dan $$\text{Peringkat}A = n$$. Untuk perhitungan QR dekomposisi,
matriks $$A$$ ditransformasi kolom demi kolom melalui refleksi Householder
menjadi bentuk segitiga atas.
Visible text: Diberikan matriks dengan
dan . Untuk perhitungan QR dekomposisi,
matriks ditransformasi kolom demi kolom melalui refleksi Householder
menjadi bentuk segitiga atas.
Mulai dengan $$A_1 = A$$ dan refleksikan kolom pertama dari $$A_1$$
terhadap vektor menggunakan bidang refleksi dengan:
Visible text: Mulai dengan dan refleksikan kolom pertama dari
terhadap vektor menggunakan bidang refleksi dengan:
Component: MathContainer
Children:
```math
\tilde{a}_1 \text{ kolom pertama dari } A_1
```
```math
\pm\|\tilde{a}_1\|_2 \cdot e_1 \in \mathbb{R}^m \text{ vektor target}
```
```math
v_1 = u_1/\|u_1\|_2 \text{ dengan } \text{rentang}(v_1)^{\perp}
```
```math
u_1 = \tilde{a}_1 \mp \|\tilde{a}_1\|_2 \cdot e_1
```
### Proses Iteratif Transformasi
Matriks transformasi Householder $$S_1 = I_m - 2v_1v_1^T \in \mathbb{R}^{m \times m}$$. Diperoleh:
Visible text: Matriks transformasi Householder . Diperoleh:
```math
A_2 = S_1 \cdot A_1 = \begin{pmatrix} r_{11} & * \\ 0 & \tilde{A}_2 \end{pmatrix}
```
dengan $$r_{11} = \pm\|\tilde{a}_1\|_2$$ dan $$\tilde{A}_2 \in \mathbb{R}^{m-1 \times n-1}$$.
Visible text: dengan dan .
Lanjutkan dengan refleksi kolom pertama dari submatriks dengan bidang refleksi:
Component: MathContainer
Children:
```math
\tilde{a}_2 \text{ kolom pertama dari } \tilde{A}_2
```
```math
\pm\|\tilde{a}_2\|_2 \cdot \tilde{e}_1 \in \mathbb{R}^{m-1}
```
```math
v_2 = u_2/\|u_2\|_2
```
```math
u_2 = \tilde{a}_2 \mp \|\tilde{a}_2\|_2 \cdot \tilde{e}_1
```
Dengan matriks transformasi:
Component: MathContainer
Children:
```math
\tilde{S}_2 = I_{m-1} - 2v_2v_2^T \in \mathbb{R}^{m-1 \times m-1}
```
```math
S_2 = \begin{pmatrix} I_1 & 0 \\ 0 & \tilde{S}_2 \end{pmatrix} \in \mathbb{R}^{m \times m}
```
Diperoleh:
```math
A_3 = S_2 \cdot A_2 = \begin{pmatrix} r_{11} & * & * \\ 0 & r_{22} & * \\ 0 & 0 & \tilde{A}_3 \end{pmatrix}
```
dengan $$r_{22} = \pm\|\tilde{a}_2\|_2$$ dan $$\tilde{A}_3 \in \mathbb{R}^{m-2 \times n-2}$$, dan seterusnya hingga:
Visible text: dengan dan , dan seterusnya hingga:
```math
\tilde{A}_n = \begin{pmatrix} \tilde{a}_{nn} \\ \vdots \\ \tilde{a}_{mn} \end{pmatrix} \in \mathbb{R}^{m-(n-1) \times 1}
```
Pada akhirnya diperoleh matriks segitiga atas:
```math
A_{n+1} = R = \begin{pmatrix} r_{11} & & * \\ & \ddots & \\ 0 & & r_{nn} \\ 0 & \cdots & 0 \\ \vdots & & \vdots \\ 0 & \cdots & 0 \end{pmatrix} = S_n \cdot \ldots \cdot S_1 \cdot A = Q^T \cdot A
```
Jadi diperoleh faktorisasi:
Component: MathContainer
Children:
```math
A = Q \cdot R
```
```math
Q = (S_n \cdot \ldots \cdot S_1)^T = S_1 \cdot \ldots \cdot S_n
```
dengan $$Q$$ adalah matriks ortogonal.
Visible text: dengan adalah matriks ortogonal.
## Algoritma Implementasi Householder
Implementasi prosedur Householder:
Mulai dengan:
Component: MathContainer
Children:
```math
A_1 := A
```
```math
Q_1 := I
```
Untuk $$i = 1, \ldots, n$$:
Visible text: Untuk :
```math
\tilde{a}_i = \begin{pmatrix} a_{ii} \\ \vdots \\ a_{mi} \end{pmatrix} := \begin{pmatrix} (A_i)_{ii} \\ \vdots \\ (A_i)_{mi} \end{pmatrix} \in \mathbb{R}^{m-i+1}
```
Hitung:
Component: MathContainer
Children:
```math
\sigma := \|\tilde{a}_i\|_2
```
```math
u_i := \tilde{a}_i + \begin{pmatrix} \mp\sigma \\ 0 \\ \vdots \\ 0 \end{pmatrix} \in \mathbb{R}^{m-i+1}
```
```math
\hat{u}_i := \begin{pmatrix} 0 \\ \vdots \\ 0 \\ u_i \end{pmatrix} \in \mathbb{R}^m
```
dan:
```math
\beta := 1/(\sigma(\sigma + |\tilde{a}_{ii}|))
```
Kemudian:
Component: MathContainer
Children:
```math
v_i = \frac{\tilde{a}_i \mp \|\tilde{a}_i\|_2 \cdot e_1}{\|\tilde{a}_i \mp \|\tilde{a}_i\|_2 \cdot e_1\|_2} = \frac{u_i}{\|u_i\|_2}
```
```math
\tilde{S}_i = I_{m-i+1} - 2v_i v_i^T = I_{m-i+1} - \beta u_i u_i^T
```
```math
S_i = I_m - \beta \hat{u}_i \hat{u}_i^T
```
Sehingga diperoleh:
Component: MathContainer
Children:
```math
A_{i+1} := S_i A_i = (I_m - \beta \hat{u}_i \hat{u}_i^T) A_i = A_i - \hat{u}_i (\beta \hat{u}_i^T A_i)
```
```math
Q_{i+1} := Q_i S_i = Q_i (I_m - \beta \hat{u}_i \hat{u}_i^T) = Q_i - (Q_i \hat{u}_i) \beta \hat{u}_i^T
```
Akhirnya diperoleh:
Component: MathContainer
Children:
```math
R := A_{n+1}
```
```math
Q := Q_{n+1}
```
## Aspek Numerik dan Kompleksitas Householder
### Kompleksitas Komputasi
Kompleksitas numerik untuk perhitungan QR dekomposisi matriks $$A \in \mathbb{R}^{m \times n}$$
dengan prosedur Householder pada dasarnya adalah:
Visible text: Kompleksitas numerik untuk perhitungan QR dekomposisi matriks
dengan prosedur Householder pada dasarnya adalah:
Component: MathContainer
Children:
```math
n^2 \cdot m \text{ operasi aritmetika untuk } m \gg n
```
```math
\frac{2}{3}n^3 \text{ operasi aritmetika untuk } m \approx n
```
### Sifat Numerik
1. Karena transformasi ortogonal, berlaku $$\text{cond}_2(R) = \text{cond}_2(A)$$
2. Elemen diagonal $$R$$ adalah bilangan $$\pm\|\tilde{a}_i\|_2$$
dari langkah ke-$$i$$. Memilih transformasi sehingga semuanya positif memberikan QR dekomposisi.
Jika $$\|\tilde{a}_i\|_2 = 0$$, $$A$$ tidak memiliki peringkat penuh
dan algoritma berhenti.
Untuk alasan numerik memilih tanda sehingga pembatalan dihindari:
```math
u_i = \tilde{a}_i \mp \|\tilde{a}_i\|_2 \cdot e_1 \text{ (bentuk umum)}
```
```math
u_i = \tilde{a}_i + \text{sgn}(\tilde{a}_i) \cdot \|\tilde{a}_i\|_2 \cdot e_1 \text{ (pilihan tanda optimal)}
```
3. Sebagai pengganti membangun $$Q$$, dalam penyimpanan kompak juga dapat menyimpan
hanya informasi yang diperlukan untuk transformasi:
```math
\text{Simpan vektor } \tilde{a}_i \mp \|\tilde{a}_i\|_2 \cdot e_1
```
di tempat bebas dari $$A$$ di bawah diagonal dan elemen diagonal dalam vektor tambahan.
4. Jika hanya ingin menghitung QR dekomposisi ekonomis, hapus kolom $$Q$$ dan baris $$R$$ yang sesuai.
Visible text: 1. Karena transformasi ortogonal, berlaku
2. Elemen diagonal adalah bilangan
dari langkah ke-. Memilih transformasi sehingga semuanya positif memberikan QR dekomposisi.
Jika , tidak memiliki peringkat penuh
dan algoritma berhenti.
Untuk alasan numerik memilih tanda sehingga pembatalan dihindari:
3. Sebagai pengganti membangun , dalam penyimpanan kompak juga dapat menyimpan
hanya informasi yang diperlukan untuk transformasi:
di tempat bebas dari di bawah diagonal dan elemen diagonal dalam vektor tambahan.
4. Jika hanya ingin menghitung QR dekomposisi ekonomis, hapus kolom dan baris yang sesuai.