4 Costruzione della fattorizzazione QR
4.1 Matrici Ortogonali
Per risolvere il problema dei minimi quadrati abbiamo usato la fattorizzazione QR, che si basa su matrici ortogonali. Richiamiamo qui alcune definizioni e proprietà.
Definizione 4.1 Una matrice quadrata \bm{Q} di ordine n è ortogonale se:
\bm{Q}^\top \bm{Q} = \bm{Q} \bm{Q}^\top = \bm{I}
dove \bm{I} è la matrice identità.
Questa definizione implica che la matrice ortogonale è invertibile e la sua inversa coincide con la sua trasposta:
\bm{Q}^{-1} = \bm{Q}^\top
Proprietà
Le matrici ortogonali hanno le seguenti proprietà:
- Preservazione delle lunghezze: La moltiplicazione di un vettore per una matrice ortogonale non cambia la sua lunghezza:
\|\bm{Q}\bm{x}\|_2 = \|\bm{x}\|_2
- Preservazione degli angoli: La matrice ortogonale preserva l’angolo tra due vettori \bm{u} e \bm{v}:
(\bm{Q}\bm{u})\cdot(\bm{Q} \bm{v}) = \bm{u}^\top\bm{Q}^\top\bm{Q}\bm{v} = \bm{u}^\top\bm{v} = \bm{u}\cdot\bm{v}
Determinante: Il determinante di una matrice ortogonale è sempre \pm 1. 1=|\bm{I}|=|\bm{Q}^{-1}\bm{Q}|= |\bm{Q}^\top\bm{Q}|=|\bm{Q}^\top|\,|\bm{Q}|=|\bm{Q}|^2
Colonne e righe ortogonali: Le colonne e le righe di una matrice ortogonale sono ortogonali tra loro e hanno norma unitaria:
\bm{c}_i\cdot\bm{c}_j = \delta_{ij}
dove \delta_{ij} è il delta di Kronecker1, che vale 1 quando i = j e 0 quando i \neq j. Questa proprietà è immediata conseguenza di \bm{Q}^\top\bm{Q}=\bm{I}.
Prodotto: Il prodotto di matrici ortogonali è una matrice ortogonale. Infatti vale
\bm{M}=\bm{Q}_1\bm{Q}_2\cdots\bm{Q}_m
inoltre
\bm{M}\bm{M}^\top = \bm{Q}_1\bm{Q}_2\cdots \underbrace{\bm{Q}_m\bm{Q}_m^\top}_{=\bm{I}}\bm{Q}_{m-1}^\top\cdots\bm{Q}_1^\top=\bm{I}
4.2 Rotazioni di Givens
Le rotazioni di Givens2 sono trasformazioni che agiscono su coppie di righe di una matrice per eliminare elementi specifici. Una matrice di rotazione di Givens \bm{G}(i,j,\theta) è una matrice ortogonale di dimensione n \times n che opera sulla riga i e j per annullare un elemento specifico di \bm{A}. In altre parole, moltiplicando \bm{A} per una rotazione di Givens, possiamo rendere zero un elemento di \bm{A} senza modificare altri elementi in colonna.
Prima di considerare il caso generale consideriamo la matrice di rotazione nel piano \mathbb{R}^2:
\bm{G} = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \phantom{-}\cos\theta \end{pmatrix}
Questa matrice rappresenta una rotazione di un angolo \theta nel piano. Se moltiplichiamo un vettore \bm{x} = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} per \bm{G}, otteniamo il vettore ruotato, ma la lunghezza del vettore rimane invariata:
\|\bm{G}\bm{x}\|_2 = \|\bm{x}\|_2
La matrice \bm{G} è ortogonale, poiché:
\begin{aligned} \bm{G}^\top \bm{G} &= \begin{pmatrix} \phantom{-}\cos\theta & \sin\theta \\ -\sin\theta & \cos\theta \end{pmatrix} \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \phantom{-}\cos\theta \end{pmatrix} \\ & = \begin{pmatrix} (\sin\theta)^2+(\cos\theta)^2 & 0 \\ 0 & (\sin\theta)^2+(\cos\theta)^2 \end{pmatrix} \\ & = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = \bm{I} \end{aligned}
Forma della Matrice di Rotazione di Givens
La matrice di rotazione di Givens \bm{G}(i,j,\theta) è una matrice identità con le seguenti modifiche:
- Gli elementi in posizione (i,i) e (j,j) sono sostituiti da \cos\theta.
- Gli elementi in posizione (i,j) e (j,i) sono sostituiti rispettivamente da \sin\theta e -\sin\theta.
Quindi \bm{G}(i,j,\theta) assume la forma:
\bm{G}(i,j,\theta) = \begin{pmatrix} 1 & \cdots & 0 & \cdots & 0 & \cdots & 0 \\ \vdots & \ddots & \vdots & & \vdots & & \vdots \\ 0 & \cdots & \cos\theta & \cdots & \sin\theta & \cdots & 0 \\ \vdots & & \vdots & \ddots & \vdots & & \vdots \\ 0 & \cdots & -\sin\theta & \cdots & \cos\theta & \cdots & 0 \\ \vdots & & \vdots & & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & \cdots & 0 & \cdots & 1 \end{pmatrix}
In questo caso, l’elemento della riga i e della colonna j viene annullato se scegliamo il seno e il coseno dell’angolo \theta in modo appropriato.
Calcolo di \cos\theta e \sin\theta
Dato che vogliamo trasformare un vettore \begin{pmatrix} a \\ b \end{pmatrix} in \begin{pmatrix} r \\ 0 \end{pmatrix}, dove r = \sqrt{a^2 + b^2}, definiamo \cos\theta e \sin\theta come segue:
\cos\theta = \dfrac{a}{\sqrt{a^2 + b^2}}, \quad \sin\theta = \dfrac{b}{\sqrt{a^2 + b^2}}
Con questa scelta, applicando la rotazione di Givens, b sarà annullato e a verrà trasformato in r.
4.3 Matrici di Householder
Le matrici di Householder3 sono una classe speciale di matrici ortogonali che vengono utilizzate principalmente nella decomposizione QR di una matrice e in altre applicazioni di analisi numerica. Queste matrici sono particolarmente utili per ridurre una matrice a una forma più semplice, come una matrice triangolare superiore, senza alterarne il rango.
Definizione 4.2 Una matrice di Householder è una matrice ortogonale \bm{H} definita come:
\bm{H} = \bm{I} - 2 \dfrac{\bm{v}\bm{v}^\top}{\bm{v}\cdot\bm{v}}
dove \bm{v} è un vettore (detto vettore di Householder) e \bm{I} è la matrice identità.
Questa matrice riflette i vettori rispetto al piano ortogonale con normale \bm{v}, cioè applicando \bm{H} a un vettore, si ottiene un riflesso rispetto a un iperpiano che passa per l’origine e ortogonale a \bm{v}.
Proprietà
La matrice \bm{H} è simmetrica e coincide con la sua inversa:
\bm{H}^\top = \bm{H}\qquad \bm{H}\bm{H} = \bm{I}
La matrice riflette il vettore \bm{v} infatti
\bm{H}\bm{v} = \left(\bm{I} - 2 \dfrac{\bm{v}\bm{v}^\top}{\bm{v}\cdot\bm{v}}\right)\bm{v} =\bm{v}-2\dfrac{\bm{v}\cancel{\bm{v}^T\bm{v}}}{\cancel{\bm{v}\cdot\bm{v}}} = \bm{v}-2\bm{v}=-\bm{v}
Possiamo costruire matrici di Householder particolari che sono utili nella costruzione della fattorizzazione QR.
Lemma 4.1 Dato un vettore \bm{x} possiamo costruire una matrice di Householder che lo riflette nel vettore \pm\|x\|_2 \bm{e}_k dove
\bm{e}_k=\big( 0, \cdots, 0, \underbrace{1}_{k-\text{position}}, 0, \cdots, 0 \big)^\top
con l’elemento 1 alla posizione k. La matrice è ottenuta usando il vettore \bm{v}=\bm{x}+\text{sign}(x_k)\|\bm{x}\|_2\bm{e}_k.
Dimostrazione. Basta considerare il vettore
\bm{v} = \bm{x}+s\|x\|_2 \bm{e}_k,\qquad s=\pm 1
infatti
\begin{aligned} (\bm{x}+s\|x\|_2 \bm{e}_k)\cdot(\bm{x}+s\|x\|_2 \bm{e}_k) &= \overbrace{\bm{x}\cdot\bm{x}}^{=\|\bm{x}\|_2^2}+2s \|\bm{x}\|_2 x_k + \overbrace{s^2}^{=1}\|\bm{x}\|_2^2\\ &= 2\|\bm{x}\|_2^2+2s\|\bm{x}\|_2 x_k\\ &= 2\|\bm{x}\|_2(\|\bm{x}\|_2+sx_k)\\ (\bm{x}+s\|x\|_2 \bm{e}_k)\cdot\bm{x} &=\|\bm{x}\|_2^2+s x_k\|\bm{x}\|_2 \\ &= \|\bm{x}\|_2(\|\bm{x}\|_2+s x_k) \end{aligned}
e quindi
\begin{aligned} \bm{H}\bm{v} &= \left( \bm{I}-2\dfrac{\bm{v}\bm{v}^\top}{\bm{v}\cdot\bm{v}} \right)\bm{x}\\ &= \left( \bm{I}-2\dfrac{(\bm{x}+s\|x\|_2 \bm{e}_k)(\bm{x}+s\|x\|_2 \bm{e}_k)^\top} {(\bm{x}+s\|x\|_2 \bm{e}_k)\cdot(\bm{x}+s\|x\|_2\bm{e}_k)} \right)\bm{x}\\ &= \bm{x}-\cancel{2}\dfrac{(\bm{x}+s\|x\|_2 \bm{e}_k)\cancel{\|\bm{x}\|_2(\|\bm{x}\|_2+s x_k)}} {\cancel{2}\cancel{\|\bm{x}\|_2(\|\bm{x}\|_2+sx_k)}} \\ &=\bm{x}-\bm{x}-s\|x\|_2 \bm{e}_k = -s\|x\|_2 \bm{e}_k \end{aligned}
il segno s=\text{sign}(x_k) in modo che sx_k=|x_k| e si evitano cancellazioni numeriche.
Esempio di Matrice di Householder
Consideriamo il vettore
\bm{v} = \begin{pmatrix} 9 \\ 3 \end{pmatrix}, \qquad \bm{v}\cdot\bm{v}=9^2+3^2 = 90
La matrice di Householder è:
\begin{aligned} \bm{H} &= \bm{I} - 2 \dfrac{\bm{v}\bm{v}^\top}{\bm{v}\cdot\bm{v}} \\ & = \bm{I} - 2 \dfrac{\begin{pmatrix} 9 \\ 3 \end{pmatrix} \begin{pmatrix} 9 & 3 \end{pmatrix}}{90}\\ & = \bm{I} - \dfrac{1}{45} \begin{pmatrix} 81 & 27 \\ 27 & 9\end{pmatrix} \\ & = \dfrac{1}{45} \begin{pmatrix} -34 & -27 \\ -27 & 36\end{pmatrix} \end{aligned}
Moltiplicando \bm{H} per \bm{v}
\begin{aligned} \bm{H}\bm{v} &= \dfrac{1}{45} \begin{pmatrix} -34 & -27 \\ -27 & 36\end{pmatrix} \begin{pmatrix} 9 \\ 3 \end{pmatrix} \\ &= \dfrac{1}{15} \begin{pmatrix} -129 \\[1em] -45 \end{pmatrix} = - \begin{pmatrix} 9 \\ 3 \end{pmatrix} = -\bm{v} \end{aligned}
4.4 Fattorizzazione QR
La fattorizzazione QR rappresenta una matrice \bm{A} come prodotto di due matrici: una matrice ortogonale \bm{Q} e una matrice triangolare superiore \bm{R}. È utile in diverse applicazioni dell’algebra lineare, tra cui la risoluzione di sistemi lineari e il calcolo di autovalori e autovettori.
Algoritmo di Givens
Il metodo di Givens è ampiamente usato per calcolare la fattorizzazione QR. Esso applica una successione di rotazioni di Givens per annullare gli elementi sotto la diagonale principale di \bm{A} e trasformarla gradualmente nella matrice triangolare superiore \bm{R}.
L’algoritmo per ottenere la fattorizzazione QR di una matrice \bm{A} con il metodo di Givens è il seguente:
Si parte da \bm{A} e si applica una serie di rotazioni di Givens \bm{G}_k, ognuna delle quali annulla un elemento sotto la diagonale.
La matrice risultante è triangolare superiore e coincide con \bm{R}.
La matrice ortogonale \bm{Q} sarà data dal prodotto delle trasposte delle matrici di Givens, cioè \bm{Q} = \bm{G}_1^\top \bm{G}_2^\top \cdots \bm{G}_m^\top.
Esempio 4.1 (Fattorizzazione QR con il Metodo di Givens) Consideriamo la matrice \bm{A} di dimensione 3 \times 2:
\bm{A} = \begin{pmatrix} 4 & -2 & 2 \\ 3 & 6 & 2 \\ 2 & 2 & 3 \end{pmatrix}
L’obiettivo è decomporre questa matrice in una matrice ortogonale \bm{Q} e una matrice triangolare superiore \bm{R} tali che:
\bm{A} = \bm{Q}\bm{R}
Passo 1: Applicazione della prima rotazione di Givens per annullare l’elemento A_{21}
La rotazione di Givens è una matrice \bm{G}_1 che agisce sulla prima e seconda riga di \bm{A}. La rotazione annullerà l’elemento A_{21}.
Calcoliamo l’angolo \theta utilizzando la formula per ottenere i coseni e seni per la rotazione. Vogliamo trasformare il vettore (4,3)^\top in un vettore con il secondo elemento uguale a zero. Pertanto, calcoliamo il raggio r come:
r = \sqrt{A_{11}^2 + A_{21}^2} = \sqrt{4^2 + 3^2} = \sqrt{16 + 9} = 5
Ora calcoliamo il coseno e il seno dell’angolo \theta:
\cos\theta = \dfrac{A_{11}}{r} = \dfrac{4}{5}, \quad \sin\theta = \dfrac{A_{21}}{r} = \dfrac{3}{5}
La matrice di rotazione di Givens è quindi:
\bm{G}_1 = \begin{pmatrix} \cos\theta & \sin\theta & 0 \\ -\sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{pmatrix} = \dfrac{1}{5} \begin{pmatrix} 4 & 3 & 0 \\ -3 & 4 & 0 \\ 0 & 0 & 5 \end{pmatrix}
Applichiamo la rotazione \bm{G}_1 alla matrice \bm{A}:
\begin{aligned} \bm{A}^{(1)} = \bm{G}_1\bm{A} &= \dfrac{1}{5} \begin{pmatrix} 4 & 3 & 0 \\ -3 & 4 & 0 \\ 0 & 0 & 5 \end{pmatrix} \begin{pmatrix} 4 & -2 & 2 \\ 3 & 6 & 2 \\ 2 & 2 & 3 \end{pmatrix} \\ &= \dfrac{1}{5} \begin{pmatrix} 25 & 10 & 14 \\ 0 & 30 & 2 \\ 10 & 10 & 15 \end{pmatrix} %= %\begin{pmatrix} %5 & 2 & 14/5 \\ %0 & 6 & 2/5 \\ %2 & 2 & 3 %\end{pmatrix} \end{aligned}
Passo 2: Applicazione della seconda rotazione di Givens per annullare l’elemento A^{(1)}_{31}
La rotazione di Givens è una matrice \bm{G}_2 che agisce sulla prima e terza riga di \bm{A}^{(1)}. La rotazione annullerà l’elemento A^{(1)}_{31}.
Calcoliamo l’angolo \theta utilizzando la formula per ottenere i coseni e seni per la rotazione. Vogliamo trasformare il vettore (5,2)^\top in un vettore con il secondo elemento uguale a zero. Pertanto, calcoliamo il raggio r come:
r = \sqrt{A_{11}^2 + A_{31}^2} = \sqrt{5^2 + 2^2} = \sqrt{25 + 4} = \sqrt{29}
Ora calcoliamo il coseno e il seno dell’angolo \theta:
\cos\theta = \dfrac{A^{(1)}_{11}}{r} = \dfrac{5}{\sqrt{29}}, \quad \sin\theta = \dfrac{A^{(1)}_{31}}{r} = \dfrac{2}{\sqrt{29}}
La matrice di rotazione di Givens \bm{G}_2 per annullare l’elemento A^{(1)}_{31} è quindi:
\bm{G}_2 = \begin{pmatrix} \cos\theta & 0 & \sin\theta \\ 0 & 1 & 0 \\ -\sin\theta & 0 & \cos\theta \end{pmatrix} = \dfrac{1}{\sqrt{29}} \begin{pmatrix} 5 & 0 & 2 \\ 0 & \sqrt{29} & 0 \\ -2 & 0 & 5 \end{pmatrix}
Applichiamo la rotazione \bm{G}_2 alla matrice \bm{A}^{(1)}.
\begin{aligned} \bm{A}^{(2)}= \bm{G}_2\bm{A}^{(1)} &= \dfrac{1}{\sqrt{29}} \begin{pmatrix} 5 & 0 & 2 \\ 0 & \sqrt{29} & 0 \\ -2 & 0 & 5 \end{pmatrix} \begin{pmatrix} 5 & 2 & 14/5 \\ 0 & 6 & 2/5 \\ 2 & 2 & 3 \end{pmatrix} \\ &= \dfrac{1}{\sqrt{29}} \begin{pmatrix} 29 & 14 & 20 \\ 0 & 6\sqrt{29} & 2\sqrt{29}/5 \\ 0 & 6 & 47/5 \end{pmatrix} \end{aligned}
Passo 3: Applicazione della terza rotazione di Givens per annullare l’elemento A^{(2)}_{32}
La rotazione di Givens è una matrice \bm{G}_3 che agisce sulla prima e terza riga di \bm{A}^{(3)}. La rotazione annullerà l’elemento A^{(3)}_{32}.
Calcoliamo l’angolo \theta utilizzando la formula per ottenere i coseni e seni per la rotazione. Vogliamo trasformare il vettore (6,6/\sqrt{29})^\top in un vettore con il secondo elemento uguale a zero. Pertanto, calcoliamo il raggio r come:
r = \sqrt{A_{22}^2 + A_{32}^2} = \sqrt{6^2 + 6^2/29} = 6\sqrt{30/29}
Ora calcoliamo il coseno e il seno dell’angolo \theta:
\cos\theta = \dfrac{A^{(2)}_{22}}{r} = \dfrac{\sqrt{29}}{\sqrt{30}}, \quad \sin\theta = \dfrac{A^{(2)}_{32}}{r} = \dfrac{1}{\sqrt{30}}
La matrice di rotazione di Givens \bm{G}_3 per annullare l’elemento A^{(2)}_{32} è quindi:
\bm{G}_3 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & \cos\theta & \sin\theta \\ 0 & -\sin\theta & \cos\theta \end{pmatrix} = \dfrac{1}{\sqrt{30}} \begin{pmatrix} 1 & 0 & 0 \\ 0 & \sqrt{29} & 1 \\ 0 & -1 & \sqrt{29} \end{pmatrix}
Applichiamo la rotazione \bm{G}_3 alla matrice \bm{A}^{(2)}:
\begin{aligned} \bm{A}^{(3)}= \bm{G}_3\bm{A}^{(2)} &= \dfrac{1}{\sqrt{30}} \begin{pmatrix} 1 & 0 & 0 \\ 0 & \sqrt{29} & 1 \\ 0 & -1 & \sqrt{29} \end{pmatrix} \times \dfrac{1}{\sqrt{29}} \begin{pmatrix} 29 & 14 & 20 \\ 0 & 6\sqrt{29} & 2\sqrt{29}/5 \\ 0 & 6 & 47/5 \end{pmatrix} \\ &= \dfrac{1}{\sqrt{30\cdot 29}} \begin{pmatrix} 29 & 14 & 20 \\ 0 & 174 & 58/5 \\ 0 & 0 & 9\sqrt{29} \end{pmatrix} \end{aligned}
Le rotazioni di Given non sono limitate a matrici quadrate ma si possono applicare a matrici rettangolari.
Esempio 4.2 (Fattorizzazione QR con Rotazioni di Givens per una Matrice 3\times 2) Consideriamo la matrice \bm{A} di dimensione 3 \times 3:
\bm{A} = \begin{pmatrix} 4 & 1 \\ 3 & 2 \\ 1 & 3 \end{pmatrix}
L’obiettivo è decomporre questa matrice in una matrice ortogonale \bm{Q} e una matrice triangolare superiore \bm{R} tali che:
\bm{A} = \bm{Q}\begin{pmatrix} \bm{R} \\ \bm{0} \end{pmatrix}
Passo 1: Applicazione della prima rotazione di Givens per annullare l’elemento A_{21}
Calcoliamo l’angolo \theta utilizzando la formula per ottenere i coseni e seni per la rotazione.
r = \sqrt{A_{11}^2 + A_{21}^2} = \sqrt{4^2 + 3^2} = \sqrt{16 + 9} = 5
Ora calcoliamo il coseno e il seno dell’angolo \theta:
\cos\theta = \dfrac{A_{11}}{r} = \dfrac{4}{5}, \quad \sin\theta = \dfrac{A_{21}}{r} = \dfrac{3}{5}
La matrice di rotazione di Givens è quindi:
\bm{G}_1 = \begin{pmatrix} \cos\theta & \sin\theta & 0 \\ -\sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{pmatrix} = \dfrac{1}{5} \begin{pmatrix} 4 & 3 & 0 \\ -3 & 4 & 0 \\ 0 & 0 & 5 \end{pmatrix}
Applichiamo la rotazione \bm{G}_1 alla matrice \bm{A}:
\begin{aligned} \bm{A}^{(1)} = \bm{G}_1\bm{A} &= \dfrac{1}{5} \begin{pmatrix} 4 & 3 & 0 \\ -3 & 4 & 0 \\ 0 & 0 & 5 \end{pmatrix} \begin{pmatrix} 4 & 1 \\ 3 & 2 \\ 1 & 3 \end{pmatrix} \\ &= \dfrac{1}{5} \begin{pmatrix} 25 & 10 \\ 0 & 5 \\ 5 & 15 \end{pmatrix} = \begin{pmatrix} 5 & 2 \\ 0 & 1 \\ 1 & 3 \end{pmatrix} \end{aligned}
Passo 2: Applicazione della seconda rotazione di Givens per annullare l’elemento A^{(1)}_{31}
Calcoliamo il coseno e il seno della rotazione
r = \sqrt{A_{11}^2 + A_{31}^2} = \sqrt{5^2 + 1^2} = \sqrt{25 + 1} = \sqrt{26}
\cos\theta = \dfrac{A^{(1)}_{11}}{r} = \dfrac{5}{\sqrt{26}}, \quad \sin\theta = \dfrac{A^{(1)}_{31}}{r} = \dfrac{1}{\sqrt{26}}
La matrice di rotazione di Givens \bm{G}_2 per annullare l’elemento A^{(1)}_{31} è quindi:
\bm{G}_2 = \begin{pmatrix} \cos\theta & 0 & \sin\theta \\ 0 & 1 & 0 \\ -\sin\theta & 0 & \cos\theta \end{pmatrix} = \dfrac{1}{\sqrt{26}} \begin{pmatrix} 5 & 0 & 1 \\ 0 & \sqrt{26} & 0 \\ -1 & 0 & 5 \end{pmatrix}
Applichiamo la rotazione \bm{G}_2 alla matrice \bm{A}^{(1)}.
\begin{aligned} \bm{A}^{(2)}= \bm{G}_2\bm{A}^{(1)} &= \dfrac{1}{\sqrt{26}} \begin{pmatrix} 5 & 0 & 1 \\ 0 & \sqrt{26} & 0 \\ -1 & 0 & 5 \end{pmatrix} \begin{pmatrix} 5 & 2 \\ 0 & 1 \\ 1 & 3 \end{pmatrix} \\ &= \dfrac{1}{\sqrt{26}} \begin{pmatrix} 26 & 13 \\ 0 & \sqrt{26} \\ 0 & 13 \end{pmatrix} \end{aligned}
Passo 3: Applicazione della terza rotazione di Givens per annullare l’elemento A^{(2)}_{32}
Calcoliamo il coseno e il seno dell’angolo \theta:
r = \sqrt{A_{22}^2 + A_{32}^2} = \sqrt{1^2 + 13^2/26} = \sqrt{15/2}
\cos\theta = \dfrac{A^{(2)}_{22}}{r} = \dfrac{\sqrt{2}}{\sqrt{15}}, \quad \sin\theta = \dfrac{A^{(2)}_{32}}{r} = \dfrac{\sqrt{13}}{\sqrt{15}}
La matrice di rotazione di Givens \bm{G}_3 per annullare l’elemento A^{(2)}_{32} è quindi:
\bm{G}_3 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & \cos\theta & \sin\theta \\ 0 & -\sin\theta & \cos\theta \end{pmatrix} = \dfrac{1}{\sqrt{15}} \begin{pmatrix} 1 & 0 & 0 \\ 0 & \sqrt{2} & \sqrt{13} \\ 0 & -\sqrt{13} & \sqrt{2} \end{pmatrix}
Applichiamo la rotazione \bm{G}_3 alla matrice \bm{A}^{(2)}:
\begin{aligned} \bm{A}^{(3)}= \bm{G}_3\bm{A}^{(2)} &= \dfrac{1}{\sqrt{15}} \begin{pmatrix} 1 & 0 & 0 \\ 0 & \sqrt{2} & \sqrt{13} \\ 0 & -\sqrt{13} & \sqrt{2} \end{pmatrix} \times \dfrac{1}{\sqrt{26}} \begin{pmatrix} 26 & 13 \\ 0 & \sqrt{26} \\ 0 & 13 \end{pmatrix} \\ &= \dfrac{1}{\sqrt{390}} \begin{pmatrix} 26 & 13 \\ 0 & 15\sqrt{13} \\ 0 & 0 \end{pmatrix} \end{aligned}
4.5 Algoritmo di Householder
Data una matrice \bm{A} di dimensioni m \times n, vogliamo applicare una trasformazione di Householder che agisca su una colonna di \bm{A}, trasformando i valori sotto la diagonale in zeri. La trasformazione di Householder è definita come:
\bm{H} = \bm{I} - 2\dfrac{\bm{v}\bm{v}^\top}{\bm{v}\cdot\bm{v}}
dove: - \bm{I} è la matrice identità di dimensione appropriata. - v è un vettore di Householder, scelto in modo tale da creare una riflessione che annulli i valori desiderati.
Costruzione del Vettore di Householder
Dato un vettore colonna \bm{x} di dimensione m, il vettore \bm{v} di Householder è costruito come:
\bm{v} = \bm{x} + \text{sign}(x_1)\|\bm{x}\|_2\bm{e}_1
dove: - \text{sign}(x_1) è il segno del primo elemento di \bm{x} (serve per evitare problemi di cancellazione numerica). - \|\bm{x}\|_2 è la norma euclidea di \bm{x}. - \bm{e}_1 è il vettore unitario che ha 1 come primo elemento e 0 altrove.
In questo modo, il vettore \bm{v} è parallelo alla direzione di \bm{x} ma modificato per creare una riflessione che annulli tutti gli elementi di \bm{x} tranne il primo.
La fattorizzazione QR può essere ottenuta applicando una serie di trasformazioni di Householder a una matrice \bm{A}, così da ridurla alla forma triangolare superiore \bm{R}. Ogni trasformazione annulla gli elementi sotto la diagonale di una colonna specifica.
Passaggi per la Fattorizzazione QR
Supponiamo di voler fattorizzare una matrice \bm{A} di dimensioni m \times n:
- Inizializzazione:
- Poniamo \bm{Q}=\bm{I} (matrice identità) e \bm{R}=\bm{A}.
- Applica le Trasformazioni di Householder:
- Per ogni colonna j della matrice \bm{R}, dal primo all’ultimo elemento diagonale:
- Estrarre il vettore colonna \bm{x} che parte dall’elemento (j, j) fino all’ultimo elemento della colonna.
- Costruire il vettore di Householder \bm{v} in base a \bm{x}.
- Creare la matrice di Householder \bm{H}_j = \bm{I} - 2\dfrac{\bm{v}\bm{v}^\top}{\bm{v}\cdot\bm{v}}.
- Applicare \bm{H}_j alla matrice \bm{R}: \bm{R} \gets \bm{H}_j\bm{R}.
- Aggiornare \bm{Q} moltiplicandolo a sinistra per \bm{H}_j: \bm{Q} \gets \bm{Q}\bm{H}_j.
- Per ogni colonna j della matrice \bm{R}, dal primo all’ultimo elemento diagonale:
- Itera fino a Ottenere \bm{R} in Forma Triangolare:
- Continua applicando le trasformazioni di Householder a tutte le colonne successive, fino a che \bm{R} non è in forma triangolare superiore.
Alla fine della procedura, avremo:
\bm{A} = \bm{Q}\bm{R}
dove \bm{Q} è il prodotto delle matrici di Householder e risulta ortogonale (\bm{Q}^\top\bm{Q} = \bm{I}), e \bm{R} è triangolare superiore.
Esempio 4.3 (Fattorizzazione QR con Matrici di Householder) Consideriamo una matrice \bm{A} di dimensione 3\times 2:
\bm{A} = \begin{bmatrix} 4 & 1 \\ 3 & 2 \\ 0 & -1 \end{bmatrix}
Passo 1: Trasformazione della Prima Colonna
- Prendiamo la prima colonna di \bm{A}, ovvero il vettore \bm{x}^\top=(4,3,12).
- Calcoliamo la norma di \bm{x}: \|\bm{x}\|_2 = \sqrt{4^2 + 3^2 + 0^2} = 5.
- Costruiamo il vettore di Householder \bm{v}:
\bm{v} = \bm{x} + \text{sign}(4) \|\bm{x}\|_2 \bm{e}_1 = \begin{bmatrix} 4 \\ 3 \\ 0 \end{bmatrix} + 5 \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 9 \\ 3 \\ 0 \end{bmatrix}
- Costruiamo
\begin{aligned} \bm{H}_1 & = \bm{I} - 2\dfrac{\bm{v}\bm{v}^\top}{\bm{v}\cdot\bm{v}} \\ &=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} -\dfrac{1}{90} \begin{bmatrix} 9 \\ 3 \\ 0 \end{bmatrix} \begin{bmatrix} 9 \\ 3 \\ 0 \end{bmatrix}^\top \\ &= \begin{bmatrix} -4/5 & -3/5 & 0 \\ -3/5 & 4/4 & 0 \\ 0 & 0 & 1 \end{bmatrix} \end{aligned}
Moltiplichiamo \bm{H}_1 per \bm{A} per ottenere una nuova matrice \bm{R} con zero sotto l’elemento (1,1).
\bm{H}_1\bm{A} = \begin{bmatrix} -4/5 & -3/5 & 0 \\ -3/5 & 4/4 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 4 & 1 \\ 3 & 2 \\ 0 & -1 \end{bmatrix} = \begin{bmatrix} -5 & -2 \\ 0 & 1 \\ 0 & -1 \end{bmatrix}
Passo 2: Trasformazione della Seconda Colonna
- Prendiamo la seconda colonna di \bm{A}, ovvero il vettore \bm{x}^\top=(0,1,-1).
- Calcoliamo la norma di \bm{x}: \|\bm{x}\|_2 = \sqrt{0^2+1^2+(-1)^2} = \sqrt{2}.
- Costruiamo il vettore di Householder \bm{v}:
\bm{v} = \bm{x} + \text{sign}(1) \|\bm{x}\|_2 \bm{e}_2 = \begin{bmatrix} 0 \\ 1 \\ -1 \end{bmatrix} + \sqrt{2} \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 1+ \sqrt{2} \\ -1 \end{bmatrix}
- Costruiamo
\begin{aligned} \bm{H}_2 & = \bm{I} - 2\dfrac{\bm{v}\bm{v}^\top}{\bm{v}\cdot\bm{v}} \\ &=\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} -\dfrac{1}{2+\sqrt{2}} \begin{bmatrix} 0 \\ 1+\sqrt{2} \\ -1 \end{bmatrix} \begin{bmatrix} 0 \\ 1+\sqrt{2} \\ -1 \end{bmatrix}^\top \\ &= \begin{bmatrix} 1 & 0 & 0 \\ 0 & -\sqrt{2}/2 & (1+\sqrt{2})/(2+\sqrt{2}) \\ 0 &(1+\sqrt{2})/(2+\sqrt{2}) & \sqrt{2}/2 \end{bmatrix} \end{aligned}
Moltiplichiamo \bm{H}_2 per \bm{H}_1\bm{A} per ottenere una nuova matrice \bm{R} con zero sotto l’elemento (2,2).
\bm{H}_2\bm{H}_1\bm{A} = \begin{bmatrix} -5 & -2 \\ 0 & -\sqrt{2} \\ 0 & 0 \end{bmatrix}
In sintesi
- Le matrici ortogonali conservano la norma euclidea: applicate ai minimi quadrati non alterano il residuo, e per questo sono lo strumento giusto.
- Le rotazioni di Givens annullano un elemento alla volta: convenienti per matrici sparse o quasi triangolari.
- Le riflessioni di Householder annullano un’intera colonna sotto la diagonale in un colpo solo: è la scelta standard per matrici piene.
- In entrambi i casi si ottiene \bm{A}=\bm{Q}\bm{R} e il problema dei minimi quadrati diventa triangolare, senza mai formare \bm{A}^T\bm{A}.