Fattorizzazione QR — ingegnerismo.it

La fattorizzazione QR decompone una matrice $A \in M_{m \times n}(\mathbb{R})$ (con $m \geq n$ ) nel prodotto $A = QR$ dove $Q$ ha colonne ortonormali e $R$ è triangolare superiore. È il fondamento numerico dei metodi per i minimi quadrati e per il calcolo degli autovalori.

Vedi anche: Gram-Schmidt, Decomposizione SVD, Numero di Condizionamento.

Enunciato

Teorema: per ogni $A \in M_{m \times n}(\mathbb{R})$ con $m \geq n$ e colonne linearmente indipendenti esistono:

$Q \in M_{m \times n}(\mathbb{R})$ con $Q^T Q = I_n$ (colonne ortonormali)
$R \in M_{n \times n}(\mathbb{R})$ triangolare superiore con elementi diagonali positivi

tali che $A = QR$ . La fattorizzazione è unica.

Nella forma piena: $Q_{\text{full}} \in M_{m \times m}(\mathbb{R})$ è ortogonale e $R_{\text{full}} \in M_{m \times n}(\mathbb{R})$ ha la parte inferiore nulla.

Metodi di Calcolo

Gram-Schmidt (classico e modificato)

Il procedimento di Gram-Schmidt applicato alle colonne di $A$ produce $Q$ e $R$ direttamente. La versione modificata è numericamente più stabile. Vedi: Gram-Schmidt.

Costo: $O(mn^2)$ , numericamente meno stabile delle riflessioni di Householder.

Riflessioni di Householder

Una riflessione di Householder è una matrice ortogonale della forma:

$H = I - 2\vec{v}\vec{v}^T, \quad \|\vec{v}\| = 1$

Riflette rispetto all’iperpiano ortogonale a $\vec{v}$ . Applicata opportunamente azzera gli elementi sotto la diagonale colonna per colonna:

$H_n \cdots H_2 H_1 A = R \implies A = Q R, \quad Q = H_1 H_2 \cdots H_n$

Costo: $O(mn^2 - n^3/3)$ , numericamente stabile. Metodo standard nelle librerie LAPACK.

Rotazioni di Givens

Una rotazione di Givens azzera un singolo elemento introducendo una rotazione piana nei piani $(i,j)$ :

$G(i,j,\theta) = \begin{pmatrix} \ddots & & & \\ & c & \cdots & -s \\ & \vdots & \ddots & \vdots \\ & s & \cdots & c \\ & & & & \ddots \end{pmatrix}$

Utile per matrici sparse (si azzera un elemento alla volta senza introdurre fill-in).

Applicazione ai Minimi Quadrati

Per il sistema sovradeterminato $A\vec{x} \approx \vec{b}$ ( $m > n$ ), la soluzione ai minimi quadrati $\min_{\vec{x}} \|A\vec{x} - \vec{b}\|_2$ si ottiene:

$A = QR \implies \|A\vec{x} - \vec{b}\|^2 = \|R\vec{x} - Q^T\vec{b}\|^2 + \|(\text{residuo})\|^2$

La soluzione è $R\vec{x} = Q^T\vec{b}$ , risolta per sostituzione all’indietro. È più stabile della soluzione tramite le equazioni normali $A^T A \vec{x} = A^T \vec{b}$ (che eleva al quadrato il numero di condizionamento).

Algoritmo QR per Autovalori

L’algoritmo QR calcola gli autovalori di una matrice simmetrica tramite iterazioni:

$A_0 = A, \quad A_k = Q_k R_k, \quad A_{k+1} = R_k Q_k$

Le matrici $A_k$ convergono a una forma diagonale (o triangolare) con gli autovalori sulla diagonale. È l’algoritmo standard nei solvitori di autovalori (con shifts per accelerare la convergenza). Vedi: Polinomio Caratteristico.

Applicazioni ingegneristiche

Regressione lineare: la fattorizzazione QR è il metodo numerico preferito per la regressione; è già implementata in numpy.linalg.lstsq, MATLAB \, R lm().
Analisi modale: il calcolo degli autovalori della matrice di rigidezza usa l’algoritmo QR con shifts di Wilkinson nelle librerie LAPACK (routine dsyev).
Controllo ottimo: il problema LQR (Linear Quadratic Regulator) richiede la soluzione dell’equazione di Riccati, che si risolve tramite decomposizione di Schur — una variante della fattorizzazione QR.