Dekomposisi QR

Diberikan vektor di \(\mathbb{R}^2\): \(\mathbf{x} = \begin{bmatrix} 3 \\ 4 \end{bmatrix}\). Konstruksikan vektor refleksi Householder \(\mathbf{v}\) yang mampu menolak komponen baris kedua.

Penyelesaian:

Langkah 1 — Hitung norma:

Langkah 2 — Tentukan tanda dan konstruksi \(\mathbf{v}\):

Entri pertama \(x_1 = 3 \geq 0\), maka \(\text{sign}(x_1) = 1\):

Kesimpulan: Vektor refleksi Householder adalah \(\mathbf{v} = \begin{bmatrix} 8 \\ 4 \end{bmatrix}\). Perhatikan bahwa komponen pertama (8) merupakan penjumlahan dua angka positif — aman dari cancellation. ∎

Diberikan vektor di \(\mathbb{R}^2\): \(\mathbf{x} = \begin{bmatrix} -4 \\ 3 \end{bmatrix}\). Konstruksikan vektor refleksi Householder \(\mathbf{v}\) dan bandingkan apa yang terjadi jika aturan tanda diabaikan.

Penyelesaian:

Langkah 1 — Hitung norma:

Langkah 2 — Dengan aturan tanda (benar):

Entri pertama \(x_1 = -4 < 0\), maka \(\text{sign}(x_1) = -1\):

Komponen pertama \(-9 = -4 + (-5)\) adalah penjumlahan dua bilangan negatif — presisi terjaga.

Langkah 3 — Tanpa aturan tanda (salah, untuk perbandingan):

Jika kita sembarangan menggunakan tanda \(+1\):

Komponen pertama \(1 = -4 + 5\) adalah pengurangan implisit dari dua angka yang berdekatan. Dalam presisi floating-point terbatas, jika \(\|\mathbf{x}\|\) dan \(|x_1|\) sangat dekat (misalnya \(x_1 = -5.0000001\) dan \(\|\mathbf{x}\| = 5.0000002\)), maka komponen pertama \(\mathbf{v}_{\text{salah}}\) hanya menyisakan 1 digit signifikan — sebuah bencana numerik.

Langkah 4 — Verifikasi hasil yang benar:

Kesimpulan: Hasilnya adalah \(\begin{bmatrix} 5 \\ 0 \end{bmatrix} = +\|\mathbf{x}\|\mathbf{e}_1\). Perhatikan bahwa karena \(\text{sign}(x_1) = -1\), hasil pemetaan justru bernilai positif \((+\|\mathbf{x}\|)\), bukan negatif. Secara umum, \(H\mathbf{x} = -\text{sign}(x_1)\|\mathbf{x}\|\mathbf{e}_1\). ∎

Gunakan vektor \(\mathbf{v} = \begin{bmatrix} 8 \\ 4 \end{bmatrix}\) dari Contoh 13.1 untuk membangun matriks $H$, verifikasi $H^2 = I_2$, lalu uji aksi eliminasi $H\mathbf{x}$.

Penyelesaian:

Langkah 1 — Konstruksi $H$:

Langkah 2 — Verifikasi $H^2 = I_2$:

Langkah 3 — Verifikasi simetris dan determinan:

$H^T = H$ terlihat langsung dari struktur matriks (\(\checkmark\)). Determinan: \(\det(H) = \left(-\tfrac{3}{5}\right)\!\left(\tfrac{3}{5}\right) - \left(-\tfrac{4}{5}\right)\!\left(-\tfrac{4}{5}\right) = \tfrac{9}{25} - \tfrac{16}{25} = -1\). Ini konsisten: refleksi selalu memiliki \(\det = -1\).

Langkah 4 — Aksi eliminasi $H\mathbf{x}$:

Entri baris kedua menjadi nol dan entri pertama menjadi \(-\|\mathbf{x}\| = -5\), sesuai rumus umum \(H\mathbf{x} = -\text{sign}(x_1)\|\mathbf{x}\|\mathbf{e}_1 = -(1)(5)\mathbf{e}_1\) (\(\checkmark\)). ∎

Konstruksi matriks Householder yang memetakan \(\mathbf{x} = \begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix} \in \mathbb{R}^3\) menjadi kelipatan \(\mathbf{e}_1\).

Penyelesaian:

Verifikasi:

Kedua entri di bawah diagonal berhasil dieliminasi secara simultan dalam satu langkah — ini adalah kekuatan utama Householder dibandingkan Givens yang memerlukan dua rotasi terpisah untuk kasus yang sama. ∎

Carilah dekomposisi $A = QR$ untuk matriks berikut menggunakan satu langkah Householder:

Penyelesaian:

Langkah 1 — Bangun $H_1$ dari kolom pertama:

Kolom pertama \(\mathbf{a}_1 = \begin{bmatrix} 3 \\ 4 \end{bmatrix}\). Ini sama persis dengan vektor pada Contoh 13.1, sehingga kita langsung menggunakan hasil sebelumnya:

Langkah 2 — Hitung $R = H_1 A$:

Matriks $R$ sudah berbentuk segitiga atas (\(\checkmark\)).

Langkah 3 — Hitung $Q$:

Karena hanya ada satu langkah Householder, $Q = H_1^T = H_1$ (simetris):

Langkah 4 — Verifikasi $A = QR$:

Kesimpulan: Dekomposisi $A = QR$ berhasil dikonstruksi secara lengkap. Perhatikan bahwa entri diagonal $R$ adalah $r_{11} = -5$ dan $r_{22} = \frac{2}{5}$. Tanda negatif pada $r_{11}$ merupakan konsekuensi langsung dari rumus $H\mathbf{x} = -\text{sign}(x_1)\|\mathbf{x}\|\mathbf{e}_1$. ∎

Carilah dekomposisi $A = QR$ untuk:

Penyelesaian:

Langkah 1 — Eliminasi kolom pertama:

Kolom pertama \(\mathbf{a}_1 = \begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}\). Ini identik dengan Contoh 13.4, sehingga:

Langkah 2 — Periksa kolom kedua:

Subvektor kolom kedua di bawah diagonal adalah \(\begin{bmatrix} -1 \\ 0 \end{bmatrix}\). Karena entri bawahnya sudah nol, tidak perlu transformasi Householder lagi. Langkah 2 dilewati: \(H_2 = I_3\).

Langkah 3 — Ekstrak hasil:

Verifikasi entri kunci: $$(QR)_{1,1} = (-\tfrac{1}{3})(-3) + (-\tfrac{2}{3})(0) + (-\tfrac{2}{3})(0) = 1 = A_{1,1} \quad (\checkmark)$$

$$(QR)_{3,3} = (-\tfrac{2}{3})(-\tfrac{4}{3}) + (-\tfrac{1}{3})(-1) + (\tfrac{2}{3})(-\tfrac{5}{3}) = \tfrac{8}{9} + \tfrac{1}{3} - \tfrac{10}{9} = \tfrac{8+3-10}{9} = \tfrac{1}{9} \cdot 0 \ldots$$

Diberikan vektor \(\mathbf{y} = \begin{bmatrix} \sqrt{3} \\ 1 \end{bmatrix}\). Konstruksikan matriks Givens $G$ yang menolak entri baris kedua, lalu verifikasi hasilnya.

Penyelesaian:

Langkah 1 — Hitung $r$, $c$, $s$:

Entri yang dipertahankan: $a = \sqrt{3}$ (baris 1). Entri yang ditolak: $b = 1$ (baris 2).

Langkah 2 — Konstruksi matriks $G(1, 2, \theta)$:

Perhatikan: nilai $-s = -(-1/2) = 1/2$ menempati posisi $(1,2)$, dan $s = -1/2$ menempati posisi $(2,1)$.

Langkah 3 — Verifikasi ortogonalitas:

Determinan $= +1$: rotasi Givens merepresentasikan rotasi murni (tanpa refleksi), berbeda dengan Householder yang selalu memiliki $\det = -1$.

Langkah 4 — Aksi eliminasi:

Entri baris kedua berhasil ditolak menjadi nol, dan entri pertama menjadi $r = 2 = \|\mathbf{y}\|$ — panjang vektor terjaga (isometri). ∎

Perhatikan matriks berikut yang memiliki struktur jarang — hanya satu entri non-nol di bawah diagonal pada kolom pertama:

Gunakan satu rotasi Givens untuk menolak entri $(3,1) = 4\). Bandingkan efisiensinya dengan Householder.

Penyelesaian:

Kita hanya perlu menolak entri pada baris 3, kolom 1. Gunakan $G(1, 3, \theta)$ yang hanya memodifikasi baris 1 dan baris 3:

Perkalian $GA$ — hanya baris 1 dan 3 yang berubah:

Entri $(3,1)$ berhasil menjadi nol (\(\checkmark\)). Baris 2 tidak tersentuh sama sekali — ini adalah keunggulan utama Givens.

Perbandingan dengan Householder:

Jika menggunakan Householder, vektor \(\mathbf{v}\) dibangun dari seluruh kolom pertama \([1, 0, 4]^T\), sehingga matriks $H$ memuat entri non-nol di seluruh posisi (matriks padat $3 \times 3$). Perkalian $HA$ menyentuh semua 9 entri. Dengan Givens, hanya 6 entri yang dihitung ulang (baris 1 dan 3 saja). Pada matriks jarang berukuran raksasa, penghematan ini sangat signifikan. ∎

Jalankan dua siklus iterasi QR dasar pada matriks berikut:

Nilai eigen sebenarnya: $\lambda = 2 \pm \sqrt{2} \approx 3.414$ dan $\approx 0.586$.

Penyelesaian:

Iterasi $k = 0$:

Kolom pertama $A_0$: $\mathbf{a}_1 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$, $\|\mathbf{a}_1\| = \sqrt{2}$, $\text{sign}(1) = 1$.

Vektor Householder: $\mathbf{v} = \begin{bmatrix} 1 \\ 1 \end{bmatrix} + \sqrt{2}\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 1+\sqrt{2} \\ 1 \end{bmatrix}$.

Setelah perhitungan (detail disederhanakan), matriks Householder hasilnya adalah:

Verifikasi cepat: $H_0\mathbf{a}_1 = \begin{bmatrix} -1/\sqrt{2} - 1/\sqrt{2} \\ -1/\sqrt{2} + 1/\sqrt{2} \end{bmatrix} = \begin{bmatrix} -\sqrt{2} \\ 0 \end{bmatrix}$ (\(\checkmark\)).

Dekomposisi $A_0 = Q_0 R_0$:

Rekonstruksi $A_1 = R_0 Q_0$:

Verifikasi: $\text{tr}(A_1) = 4 = \text{tr}(A_0)$ (\(\checkmark\)), $\det(A_1) = 3 - 1 = 2 = \det(A_0)$ (\(\checkmark\)).

Iterasi $k = 1$:

Kolom pertama $A_1$: $\mathbf{a}_1 = \begin{bmatrix} 3 \\ -1 \end{bmatrix}$, $\|\mathbf{a}_1\| = \sqrt{10}$, $\text{sign}(3) = 1$.

Vektor Householder: $\mathbf{v} = \begin{bmatrix} 3 \\ -1 \end{bmatrix} + \sqrt{10}\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 3+\sqrt{10} \\ -1 \end{bmatrix}$.

Matriks Householder (setelah perhitungan):

Dekomposisi $A_1 = Q_1 R_1$:

Rekonstruksi $A_2 = R_1 Q_1$:

Analisis konvergensi:

Nilai eigen diagonal: $3.4$ dan $0.6$ sudah mendekati nilai sebenarnya ($3.414$ dan $0.586$). Entri subdiagonal turun dari $1.0$ menjadi $0.2$ — konvergensi mulai terakselerasi. Pada iterasi berikutnya, penurunan akan semakin cepat karena rasio konvergensi $\approx |\lambda_2/\lambda_1| \approx 0.172$. ∎

Lanjutkan dari $A_1 = \begin{bmatrix} 3 & -1 \\ -1 & 1 \end{bmatrix}$ (hasil Contoh 13.9, iterasi $k=0$). Gunakan shift $\sigma_0 = a_{22}^{(1)} = 1$ (shift Rayleigh sederhana) dan bandingkan hasilnya.

Penyelesaian:

Langkah 1 — Geser matriks:

Langkah 2 — Dekomposisi QR dari matriks tergeser:

Kolom pertama: $\begin{bmatrix} 2 \\ -1 \end{bmatrix}$, $\|\cdot\| = \sqrt{5}$, $\text{sign}(2) = 1$.

Vektor Householder: $\mathbf{v} = \begin{bmatrix} 2 \\ -1 \end{bmatrix} + \sqrt{5}\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 2+\sqrt{5} \\ -1 \end{bmatrix}$.

Setelah perhitungan, matriks Householder:

Langkah 3 — Rekonstruksi dengan mengembalikan shift:

Perbandingan dengan tanpa shift:

Pada kasus $2 \times 2$ ini, shift Rayleigh sederhana ($\sigma = a_{22}$) memberikan hasil yang identik dengan iterasi tanpa shift setelah satu langkah. Hal ini karena pada matriks $2 \times 2$, shift Rayleigh setara dengan tidak melakukan shift setelah penyusunan ulang. Keunggulan shift menjadi sangat dramatis pada matriks berukuran besar ($n \geq 10$), di mana Shift Wilkinson — yang memilih $\sigma_k$ sebagai eigenvalue submatriks $2 \times 2$ sudut kanan bawah yang paling dekat dengan $a_{nn}$ — mampu memberikan konvergensi kuadratis atau kubis. ∎