QR Dekomposisi

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:

A = Q \cdot R

Representasi ini disebut QR dekomposisi dari $A$ .

Pembuktian dengan Gram-Schmidt

Kolom-kolom $a_j$ untuk $j = 1, \ldots, n$ dari matriks $A$ dapat diorthonormalisasi menggunakan proses Gram-Schmidt:

\tilde{q}_j := a_j - \sum_{k=1}^{j-1} \langle a_j, q_k \rangle \cdot q_k

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:

a_j = \sum_{k=1}^{j-1} \langle a_j, q_k \rangle \cdot q_k + \tilde{q}_j

= \sum_{k=1}^{j-1} \langle a_j, q_k \rangle \cdot q_k + \|\tilde{q}_j\|_2 \cdot q_j

= \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$ .

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$ .

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.

QR Dekomposisi Penuh

QR dekomposisi penuh menggunakan matriks berukuran penuh:

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.

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:

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.

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$ .

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$ :

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$ .

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.

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:

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.

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:

$S$ adalah simetri: $S^T = S$
$S$ adalah matriks ortogonal: $S^T S = I$
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$
$\text{cond}_2(S) = 1$

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.

Mulai dengan $A_1 = A$ dan refleksikan kolom pertama dari $A_1$ terhadap vektor menggunakan bidang refleksi dengan:

\tilde{a}_1 \text{ kolom pertama dari } A_1

\pm\|\tilde{a}_1\|_2 \cdot e_1 \in \mathbb{R}^m \text{ vektor target}

v_1 = u_1/\|u_1\|_2 \text{ dengan } \text{rentang}(v_1)^{\perp}

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:

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}$ .

Lanjutkan dengan refleksi kolom pertama dari submatriks dengan bidang refleksi:

\tilde{a}_2 \text{ kolom pertama dari } \tilde{A}_2

\pm\|\tilde{a}_2\|_2 \cdot \tilde{e}_1 \in \mathbb{R}^{m-1}

v_2 = u_2/\|u_2\|_2

u_2 = \tilde{a}_2 \mp \|\tilde{a}_2\|_2 \cdot \tilde{e}_1

Dengan matriks transformasi:

\tilde{S}_2 = I_{m-1} - 2v_2v_2^T \in \mathbb{R}^{m-1 \times m-1}

S_2 = \begin{pmatrix} I_1 & 0 \\ 0 & \tilde{S}_2 \end{pmatrix} \in \mathbb{R}^{m \times m}

Diperoleh:

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:

\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:

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:

A = Q \cdot R

Q = (S_n \cdot \ldots \cdot S_1)^T = S_1 \cdot \ldots \cdot S_n

dengan $Q$ adalah matriks ortogonal.

Algoritma Implementasi Householder

Implementasi prosedur Householder:

Mulai dengan:

A_1 := A

Q_1 := I

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

\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:

\sigma := \|\tilde{a}_i\|_2

u_i := \tilde{a}_i + \begin{pmatrix} \mp\sigma \\ 0 \\ \vdots \\ 0 \end{pmatrix} \in \mathbb{R}^{m-i+1}

\hat{u}_i := \begin{pmatrix} 0 \\ \vdots \\ 0 \\ u_i \end{pmatrix} \in \mathbb{R}^m

dan:

\beta := 1/(\sigma(\sigma + |\tilde{a}_{ii}|))

Kemudian:

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}

\tilde{S}_i = I_{m-i+1} - 2v_i v_i^T = I_{m-i+1} - \beta u_i u_i^T

S_i = I_m - \beta \hat{u}_i \hat{u}_i^T

Sehingga diperoleh:

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)

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:

R := A_{n+1}

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:

n^2 \cdot m \text{ operasi aritmetika untuk } m \gg n

\frac{2}{3}n^3 \text{ operasi aritmetika untuk } m \approx n

Sifat Numerik

Karena transformasi ortogonal, berlaku $\text{cond}_2(R) = \text{cond}_2(A)$
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:

$u_i = \tilde{a}_i \mp \|\tilde{a}_i\|_2 \cdot e_1 \text{ (bentuk umum)}$
$u_i = \tilde{a}_i + \text{sgn}(\tilde{a}_i) \cdot \|\tilde{a}_i\|_2 \cdot e_1 \text{ (pilihan tanda optimal)}$
Sebagai pengganti membangun $Q$ , dalam penyimpanan kompak juga dapat menyimpan hanya informasi yang diperlukan untuk transformasi:

$\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.
Jika hanya ingin menghitung QR dekomposisi ekonomis, hapus kolom $Q$ dan baris $R$ yang sesuai.

Command Palette