Cenni su Fattorizzazione QR

Una matrice $A \in \mathbb{R}^{m\times n}$ con $m \ge n$ si può fattorizzare in

$$A = QR$$

Con $R$ matrice triangolare superiore $n\times n$ non singolare e $Q$ matrice ortogonale $m \times n$.

Si rammenta che:

Definizione 6.22 (Matrice ortogonale)   $Q$ ortogonale significa $Q^tQ = I$.

Si può altrimenti caratterizzare:

Lemma 6.7   Se $Q$ è matrice ortogonale le colonne di $Q$ sono vettori ortonormali:

$$\textit{col}_i(Q^t)^t \cdot \textit{col}_\delta (Q) = \delta_{ij} = \begin{cases}i = \delta : 0 \\ i = \delta : 1\end{cases}$$

(La norma euclidea è 1).

Si assuma che $\textit{rango}(A) = n$, ovvero il massimo possibile.

$$A = QR$$

$$AR^{-1} = QRR^{-1} = Q$$

Se $R$ è triangolare superiore allora $R^{-1}$ è anch'essa triangolare superiore.

$$[ \textit{col}_1(A) \textit{col}_2(A) \ldots \textit{col}_n(A) ] ... ...{11} & p_{12} & \cdots & p_{1n} \\ 0 \\ 0 & 0 & \ldots & p_{n,n} \end{bmatrix}$$

$$= \begin{bmatrix}p_{11}\textit{col}(A) & p_{11}\textit{col}_1(A)+... ...cdots & P_{1n}\textit{col}_1(A)+\ldots + p_{nm}\textit{col}_n(A) \end{bmatrix}$$

Risultano vettori ortonormali da vettori indipendenti - il procedimento è equivalente ad applicare Gram-Schmidt sulle colonne di $A$).

$$A = QR \qquad \textit{rango}(A) = n$$

$$A^tA = A^tb$$

$$A^tA = (QR)^t (QR) = R^t \underbrace{(Q^tQ)}_{\mathscr{I}}R= R^tR$$

$$A^tb=R^tQ^tb$$

$$R^tRx=Q^tQ^tb$$

$R$ è una matrice non singolare, per cui il sistema di partenza diventa equivalente a:

$$Rx = Q^t b$$

Questo è il sistema dell'equazione normali scritto in un'altra forma.

La fattorizzazione QR è il secondo algoritmo più usato al mondo (dopo FFT).