Dekomposisi QR

Dekomposisi $\mathrm{QR}$ memfaktorkan matriks menjadi faktor ortogonal dan faktor segitiga atas. Perkalian dengan matriks ortogonal mempertahankan panjang dan sudut, sehingga cocok untuk perhitungan numerik yang stabil.

Misalkan $A\in\mathbb{R}^{m\times n}$ memenuhi $m\geq n$ dan $\operatorname{rank}(A)=n$ . Terdapat matriks ortogonal $Q\in\mathbb{R}^{m\times m}$ dengan $Q^TQ=I$ dan matriks segitiga atas $R\in\mathbb{R}^{m\times n}$ yang $n$ elemen diagonal pertamanya positif, sehingga

Faktorisasi ini disebut dekomposisi $\mathrm{QR}$ dari $A$ .

Misalkan $a_j$ adalah kolom ke- $j$ dari $A$ . Proses Gram-Schmidt menghilangkan komponen pada arah yang sudah diperoleh, lalu menormalkan sisanya:

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

Karena kolom $A$ bebas linear, $\widetilde q_j\neq0$ pada setiap langkah. Vektor yang sudah dinormalkan menjadi kolom $Q_1\in\mathbb{R}^{m\times n}$ dan memenuhi $Q_1^TQ_1=I_n$ . Setiap kolom awal dapat disusun kembali sebagai

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

Jadi, $A=Q_1R_1$ , dengan $R_1\in\mathbb{R}^{n\times n}$ berbentuk segitiga atas dan $r_{ii}=\|\widetilde q_i\|_2>0$ .

Lengkapi $Q_1$ dengan $m-n$ kolom ortonormal sehingga $Q=(Q_1\quad Q_2)\in\mathbb{R}^{m\times m}$ . Tambahkan $m-n$ baris nol pada $R_1$ sehingga $R=\begin{pmatrix}R_1\\0\end{pmatrix}\in\mathbb{R}^{m\times n}$ . Dengan demikian, $A=Q_1R_1=QR$ .

Untuk $A\in\mathbb{R}^{m\times n}$ dengan $m\geq n$ , bentuk lengkap dan bentuk tipis menyatakan faktorisasi yang sama dengan ukuran matriks berbeda.

Bentuk lengkap mempertahankan seluruh $m$ kolom $Q$ :

Pada bentuk lengkap ini, $Q\in\mathbb{R}^{m\times m}$ ortogonal dan $R\in\mathbb{R}^{m\times n}$ memuat blok segitiga atas berukuran $n\times n$ di atas $m-n$ baris nol.

Bentuk tipis menghapus baris nol tersebut beserta kolom $Q$ yang tidak lagi dipakai:

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}$ berisi $n$ kolom pertama $Q$ , sedangkan $R_1\in\mathbb{R}^{n\times n}$ berbentuk segitiga atas. Menyimpan $Q_1$ tanpa matriks penuh $Q$ menghemat memori dan menghindari operasi pada blok yang seluruh elemennya sudah diketahui nol.

Kolom yang tidak dipakai, yaitu $Q_2\in\mathbb{R}^{m\times(m-n)}$ , membentuk basis ortonormal untuk ruang nol $A^T$ :

A^T Q_2 = R_1^T Q_1^T Q_2 = 0

Ruang nol $A^T$ berisi semua vektor $x$ yang memenuhi $A^Tx=0$ .

Untuk matriks dengan peringkat kolom penuh, faktorisasi tipis $A=Q_1R_1$ bersifat unik jika semua elemen diagonal $R_1$ positif.

A=\begin{pmatrix}1&1\\1&0\\0&1\end{pmatrix}=(a_1\ \,a_2)

Gram-Schmidt mula-mula memberikan

q_1=\frac{a_1}{\|a_1\|_2}=\frac1{\sqrt2}\begin{pmatrix}1\\1\\0\end{pmatrix}

Q_1=\begin{pmatrix}1/\sqrt2&1/\sqrt6\\1/\sqrt2&-1/\sqrt6\\0&2/\sqrt6\end{pmatrix}

Gram-Schmidt klasik mudah diturunkan, tetapi kolom yang hampir bergantung linear dapat kehilangan ortogonalitas dalam aritmetika titik mengambang. Gram-Schmidt termodifikasi mengurangi galat tersebut. Perangkat lunak numerik untuk matriks padat umumnya memakai reflektor Householder, sedangkan rotasi Givens berguna ketika hanya elemen tertentu yang perlu dibuat nol.

Untuk vektor satuan $v\in\mathbb{R}^m$ , matriks Householder didefinisikan sebagai

S = I - 2vv^T \in \mathbb{R}^{m \times m}

Produk luar $vv^T$ mengalikan vektor kolom berukuran $m\times1$ dengan vektor baris berukuran $1\times m$ , sehingga produk tersebut berupa matriks $m\times m$ berperingkat satu. Urutan terbalik $v^Tv$ menghasilkan skalar $1$ .

Untuk $S=I-2vv^T$ dan $\|v\|_2=1$ , berlaku sifat berikut:

$S$ adalah simetri: $S^T = S$
$S$ adalah matriks ortogonal: $S^T S = I$
$Sx$ memantulkan $x\in\mathbb{R}^m$ terhadap hiperbidang yang tegak lurus pada $v$
$\text{cond}_2(S) = 1$

Misalkan $A\in\mathbb{R}^{m\times n}$ memenuhi $m\geq n$ dan $\operatorname{rank}(A)=n$ . Setiap langkah Householder membuat elemen di bawah satu posisi diagonal menjadi nol tanpa mengubah nol yang sudah terbentuk pada langkah sebelumnya.

Mulai dengan $A_1=A$ . Pantulkan kolom pertamanya ke kelipatan vektor koordinat pertama:

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

u_1 = \tilde{a}_1 \mp \|\tilde{a}_1\|_2 \cdot e_1

Dengan $S_1=I_m-2v_1v_1^T$ , seluruh elemen kolom pertama di bawah diagonal menjadi nol:

A_2 = S_1 \cdot A_1 = \begin{pmatrix} r_{11} & * \\ 0 & \tilde{A}_2 \end{pmatrix}

Pada matriks $A_2$ , $r_{11} = \pm\|\tilde{a}_1\|_2$ dan $\tilde{A}_2 \in \mathbb{R}^{m-1 \times n-1}$ .

Terapkan reflektor berikutnya hanya pada submatriks kanan bawah yang tersisa:

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

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

Masukkan reflektor kedua ke blok kanan bawah matriks identitas:

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

Seluruh elemen kolom kedua di bawah diagonal kemudian menjadi nol:

A_3 = S_2 \cdot A_2 = \begin{pmatrix} r_{11} & * & * \\ 0 & r_{22} & * \\ 0 & 0 & \tilde{A}_3 \end{pmatrix}

Di sini $r_{22}=\pm\|\widetilde a_2\|_2$ dan $\widetilde A_3\in\mathbb{R}^{(m-2)\times(n-2)}$ . Pengulangan operasi yang sama menyisakan kolom aktif terakhir

\tilde{A}_n = \begin{pmatrix} \tilde{a}_{nn} \\ \vdots \\ \tilde{a}_{mn} \end{pmatrix} \in \mathbb{R}^{m-(n-1) \times 1}

Setelah refleksi terakhir, matriks yang diperoleh berbentuk 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

Karena setiap reflektor ortogonal dan simetris, hasil kalinya memberikan

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

Matriks $Q$ bersifat ortogonal karena merupakan hasil kali beberapa reflektor ortogonal.

Mulai dengan matriks aktif dan faktor ortogonal berikut:

Pada langkah ke- $i$ , ambil bagian aktif dari kolom ke- $i$ :

\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 normanya, pilih tanda yang menghindari pembatalan numerik, lalu bentuk vektor Householder:

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

Faktor skalanya adalah

\beta := \frac{2}{u_i^Tu_i}=\frac{1}{\sigma(\sigma+|\tilde a_{ii}|)}

Vektor ternormalisasi dan reflektor penuhnya adalah

v_i=\frac{u_i}{\|u_i\|_2}

Perbarui matriks aktif dan faktor terkumpul tanpa membentuk perkalian padat tambahan:

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)

Setelah $n$ langkah,

Untuk $m\ge n$ , dekomposisi $\mathrm{QR}$ dengan reflektor Householder memerlukan kira-kira

2mn^2-\frac{2}{3}n^3\text{ operasi titik mengambang}

Perkalian ortogonal mempertahankan nilai singular, sehingga $\operatorname{cond}_2(R)=\operatorname{cond}_2(A)$ untuk matriks dengan peringkat kolom penuh.
Pada langkah ke- $i$ , elemen diagonal baru bernilai $\pm\|\widetilde a_i\|_2$ . Pilih tanda berikut saat menghitung reflektor agar dua bilangan yang hampir sama tidak saling dikurangkan:
$u_i = \tilde{a}_i + s_i\|\tilde{a}_i\|_2e_1$
Setelah faktorisasi selesai, tanda satu kolom $Q$ dan baris $R$ yang bersesuaian dapat dibalik agar diagonal $R$ positif. Jika $\|\widetilde a_i\|_2=0$ , matriks tidak memiliki peringkat kolom penuh dan syarat keunikan tersebut tidak berlaku. Gunakan dekomposisi dengan pivot kolom untuk menentukan peringkat numeriknya.
Implementasi ringkas menyimpan setiap vektor Householder $u_i$ di bawah diagonal salinan kerja $A$ dan menyimpan elemen diagonal secara terpisah. Reflektor kemudian dapat diterapkan tanpa membentuk $Q$ secara eksplisit.
Faktorisasi tipis mempertahankan $n$ kolom pertama $Q$ dan $n$ baris pertama $R$ .

s_i=1\text{ ketika }\tilde a_{ii}\ge0,\qquad s_i=-1\text{ untuk kasus lainnya}

Dekomposisi QR

Keberadaan Dekomposisi QR

Dekomposisi QR

Keberadaan Dekomposisi QR

Pembuktian dengan Gram Schmidt

Dekomposisi QR Lengkap dan Tipis

Dekomposisi QR Lengkap

Dekomposisi QR Tipis

Sifat Keunikan

Contoh Dekomposisi QR Tipis

Metode Householder untuk Dekomposisi QR

Transformasi Householder

Sifat Transformasi Householder

Prosedur Householder

Proses Iteratif Transformasi

Algoritma Householder

Aspek Numerik dan Kompleksitas Householder

Kompleksitas Komputasi

Sifat Numerik