Dekomposisi QR

Keberadaan 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

A = Q \cdot R

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

Pembuktian dengan Gram Schmidt

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

R=\begin{pmatrix}R_1\\0\end{pmatrix}\in\mathbb{R}^{m\times n}

Matriks yang sudah dilengkapi tetap memenuhi $A=Q_1R_1=QR$ .

Dekomposisi QR Lengkap dan Tipis

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$ . Keduanya menghasilkan $A$ saat dikalikan kembali, sehingga pilihannya bergantung pada apakah kamu memerlukan basis ortonormal lengkap atau hanya kolom yang memuat datanya.

Dekomposisi QR Lengkap

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

A = Q \cdot R

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.

Dekomposisi QR Tipis

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

\begin{aligned} A &= Q \cdot R \\ &= (Q_1 \quad Q_2) \cdot \begin{pmatrix} R_1 \\ 0 \end{pmatrix} \\ &= Q_1 \cdot R_1 \end{aligned}

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

Sifat Keunikan

Untuk matriks dengan peringkat kolom penuh, faktorisasi tipis $A=Q_1R_1$ bersifat unik jika semua $elemen diagonal$ $R_1$ $positif$ . Syarat tanda itu menghapus kebebasan yang tersisa, karena mengalikan satu kolom $Q_1$ dan baris $R_1$ yang bersesuaian dengan $-1$ tidak mengubah hasil kalinya.

Contoh Dekomposisi QR Tipis

Misalkan

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}

Dengan demikian,

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

Metode Householder untuk Dekomposisi QR

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.

Transformasi Householder

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

Sifat Transformasi Householder

Untuk $S=I-2vv^T$ dan $\|v\|_2=1$ , berlaku sifat berikut. Sifat simetri dan ortogonal berasal dari vektor satuan pada definisinya, sifat pantulan menjelaskan pengaruh transformasi pada sebuah vektor, dan $bilangan kondisi satu$ berarti pantulan eksak mempertahankan norma Euklides vektor gangguan.

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

Prosedur Householder

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

Proses Iteratif Transformasi

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:

\begin{aligned} 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 \end{aligned}

Karena setiap reflektor ortogonal dan simetris, hasil kalinya memberikan

A = Q \cdot R

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

Algoritma Householder

Mulai dengan matriks aktif dan faktor ortogonal berikut:

A_1 := A

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

\begin{aligned} \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} \end{aligned}

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:

\begin{aligned} 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) \end{aligned}

Setelah $n$ langkah,

R := A_{n+1}

Aspek Numerik dan Kompleksitas Householder

Menerapkan dekomposisi dalam aritmetika floating-point memunculkan dua pertanyaan praktis, yaitu berapa banyak operasi yang dibutuhkan dan bagaimana $galat pembulatannya$ berperilaku. Jawaban keduanya menentukan apakah metode ini cocok untuk masalahmu: jumlah operasi menentukan waktu jalan pada matriks besar, sedangkan perilaku pembulatannya menentukan seberapa jauh hasil hitungan bisa dipercaya.

Kompleksitas Komputasi

Perhitungan berikut menyimpan $Q$ $secara implisit sebagai reflektor$ dan menghitung $R$ . Membentuk matriks penuh $Q$ berukuran $m\times m$ secara eksplisit memerlukan operasi tambahan.

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

2mn^2-\frac23n^3

Perkiraan banyaknya $operasi floating-point$ saat $m=n$ adalah:

\frac43n^3

Sifat Numerik

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 $\mathrm{QR}$ dengan pivot kolom untuk menentukan peringkat numeriknya.

Implementasi ringkas menskalakan vektor Householder agar entri aktif pertamanya 1. Entri sisanya disimpan di bawah diagonal matriks kerja, sedangkan skalar terpisah menyimpan kekuatan reflektor. Diagonal dan segitiga atas tetap menyimpan $R$ . Terapkan reflektor tersimpan tanpa membentuk $Q$ secara eksplisit.

Faktorisasi tipis mempertahankan $n$ kolom pertama $Q$ dan $n$ baris pertama $R$ .