Queste note sono basate sugli appunti fatti con Gianmarco Manzini negli anni 1995-2005

Costruzione della fattorizzazione QR

Appunti di calcolo numerico

Autore/Autrice
Affiliazione

Enrico Bertolazzi

University of Trento, Department of Industrial Engineering

Matrici Ortogonali

Nella soluzione del problema ai minimi quadrati si è usata la fattorizzazione QR che usa le matrici ortoginali. Qui richiamiamo definizioni e proprietà.

Definizione 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à:

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

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

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

  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 Kronecker, che vale 1 quando i = j e 0 quando i \neq j. Questa proprietà è immediata conseguenza di \bm{Q}^\top\bm{Q}=\bm{I}.

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

Rotazioni di Givens

Le rotazioni di Givens 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 \Bbb{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:

  1. Gli elementi in posizione (i,i) e (j,j) sono sostituiti da \cos\theta.
  2. 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 = \frac{a}{\sqrt{a^2 + b^2}}, \quad \sin\theta = \frac{b}{\sqrt{a^2 + b^2}}

Con questa scelta, applicando la rotazione di Givens, b sarà annullato e a verrà trasformato in r.

Matrici di Householder

Le matrici di Householder 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 2 Una matrice di Householder è una matrice ortogonale \bm{H} definita come:

\bm{H} = \bm{I} - 2 \frac{\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 \frac{\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 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-\textrm{position}}, 0, \cdots, 0 \big)^\top

con l’elemento 1 alla posizione k. La matrice è ottenuta usando il vettore \bm{v}=\bm{x}+\textrm{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=\textrm{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 \frac{\begin{pmatrix} 9 \\ 3 \end{pmatrix} \begin{pmatrix} 9 & 3 \end{pmatrix}}{90}\\ & = \bm{I} - \frac{1}{45} \begin{pmatrix} 81 & 27 \\ 27 & 9\end{pmatrix} \\ & = \frac{1}{45} \begin{pmatrix} -34 & -27 \\ -27 & 36\end{pmatrix} \end{aligned}

Moltiplicando \bm{H} per \bm{v}

\begin{aligned} \bm{H}\bm{v} &= \frac{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}

Fattorizzazione QR

La fattorizzazione QR è una decomposizione di una matrice \bm{A} come prodotto di due matrici: una matrice ortogonale \bm{Q} e una matrice triangolare superiore \bm{R}. Questa fattorizzazione ha molte applicazioni in algebra lineare, come nella risoluzione di sistemi lineari e nel calcolo di autovalori e autovettori.

Algoritmo di Givens

Il metodo di Givens è uno dei metodo molto usato per eseguire la fattorizzazione QR, utilizzando una serie di rotazioni di Givens per annullare gli elementi sotto la diagonale principale di \bm{A}, trasformandola gradualmente in una matrice triangolare superiore \bm{R}.

L’algoritmo per ottenere la fattorizzazione QR di una matrice \bm{A} con il metodo di Givens è il seguente:

  1. Partiamo da \bm{A} e applichiamo una serie di rotazioni di Givens \bm{G}_k, ognuna delle quali annulla un elemento sotto la diagonale.

  2. Alla fine, la matrice risultante sarà triangolare superiore e sarà la nostra matrice \bm{R}.

  3. 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 1 (Fattorizzazione QR con il Metodo di Givens) Consideriamo la matrice \bm{A} di dimensione 3 \times 3:

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

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

    2. Ora calcoliamo il coseno e il seno dell’angolo \theta:

      \cos\theta = \frac{A_{11}}{r} = \frac{4}{5}, \quad \sin\theta = \frac{A_{21}}{r} = \frac{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}

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

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

    2. Ora calcoliamo il coseno e il seno dell’angolo \theta:

      \cos\theta = \frac{A^{(1)}_{11}}{r} = \frac{5}{\sqrt{29}}, \quad \sin\theta = \frac{A^{(1)}_{31}}{r} = \frac{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}

    3. 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} %\\ %& = %\begin{pmatrix} %29/\sqrt{29} & 14/\sqrt{29} & 20/\sqrt{29} \\ %0 & 6 & 2/5 \\ %0 & 6/\sqrt{29} & 47/(5\sqrt{29}) %\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}.

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

    2. Ora calcoliamo il coseno e il seno dell’angolo \theta:

      \cos\theta = \frac{A^{(2)}_{22}}{r} = \frac{\sqrt{29}}{\sqrt{30}}, \quad \sin\theta = \frac{A^{(2)}_{32}}{r} = \frac{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}

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

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

    2. Ora calcoliamo il coseno e il seno dell’angolo \theta:

      \cos\theta = \frac{A_{11}}{r} = \frac{4}{5}, \quad \sin\theta = \frac{A_{21}}{r} = \frac{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}

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

    1. alcoliamo 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 = \frac{A^{(1)}_{11}}{r} = \frac{5}{\sqrt{26}}, \quad \sin\theta = \frac{A^{(1)}_{31}}{r} = \frac{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}

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

    1. 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 = \frac{A^{(2)}_{22}}{r} = \frac{\sqrt{2}}{\sqrt{15}}, \quad \sin\theta = \frac{A^{(2)}_{32}}{r} = \frac{\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}

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

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\frac{\bm{v}\bm{v}^\top}{\bm{v}\cdot\bm{v}}

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

  1. Inizializzazione:
    • Poniamo \bm{Q}=\bm{I} (matrice identità) e \bm{R}=\bm{A}.
  2. Applica le Trasformazioni di Householder:
    • Per ogni colonna j della matrice \bm{R}, dal primo all’ultimo elemento diagonale:
      1. Estrarre il vettore colonna \bm{x} che parte dall’elemento (j, j) fino all’ultimo elemento della colonna.
      2. Costruire il vettore di Householder \bm{v} in base a \bm{x}.
      3. Creare la matrice di Householder \bm{H}_j = \bm{I} - 2\frac{\bm{v}\bm{v}^\top}{\bm{v}\cdot\bm{v}}.
      4. Applicare \bm{H}_j alla matrice \bm{R}: \bm{R} \gets \bm{H}_j\bm{R}.
      5. Aggiornare \bm{Q} moltiplicandolo a sinistra per \bm{H}_j: \bm{Q} \gets \bm{Q}\bm{H}_j.
  3. 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 3 (Fattorizzazione QR con Matrici di Householder) Consideriamo una matrice A 3\times 2:

A = \begin{bmatrix} 4 & 1 \\ 3 & 2 \\ 0 & -1 \end{bmatrix}

  • Passo 1: Trasformazione della Prima Colonna

    1. Prendiamo la prima colonna di \bm{A}, ovvero il vettore \bm{x}^\top=(4,3,12).
    2. Calcoliamo la norma di \bm{x}: \|\bm{x}\|_2 = \sqrt{4^2 + 3^2 + 0^2} = 5.
    3. Costruiamo il vettore di Householder \bm{v}:

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

    1. Costruiamo

    \begin{aligned} \bm{H}_1 & = \bm{I} - 2\frac{\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} .

    1. Moltiplichiamo \bm{H}_1 per \bm{A} per ottenere una nuova matrice \bm{R} con zero sotto l’elemento (1,1).

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

  • Passo 2: Trasformazione della Seconda Colonna

    1. Prendiamo la seconda colonna di \bm{A}, ovvero il vettore \bm{x}^\top=(0,1,-1).
    2. Calcoliamo la norma di \bm{x}: \|\bm{x}\|_2 = \sqrt{0^2+1^2+(-1)^2} = \sqrt{2}.
    3. Costruiamo il vettore di Householder \bm{v}:

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

    1. Costruiamo

    \begin{aligned} \bm{H}_2 & = \bm{I} - 2\frac{\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} .

    1. Moltiplichiamo \bm{H}_2 per \bm{H}_1\bm{A} per ottenere una nuova matrice \bm{R} con zero sotto l’elemento (1,1).

      \bm{H}_2\bm{H}_1\bm{A} = \begin{bmatrix} -5 & -2 \\ 0 & -\sqrt{2} \\ 0 & 0 \end{bmatrix}

Referenze

Golub, Gene H., e Charles F. Van Loan. 1989. Matrix Computations. Johns Hopkins Univ. Press.
Trefethen, Lloyd N., e David Bau. 1997. Numerical Linear Algebra. SIAM.