Fattorizzazione QR

Voci di Glossario Algebra LineareAnalisi Matematica
Indice dei contenuti

    La fattorizzazione QR decompone una matrice A∈Mm×n(R)A \in M_{m \times n}(\mathbb{R}) (con m≥nm \geq n) nel prodotto A=QRA = QR dove QQ ha colonne ortonormali e RR è 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∈Mm×n(R)A \in M_{m \times n}(\mathbb{R}) con m≥nm \geq n e colonne linearmente indipendenti esistono:

    • Q∈Mm×n(R)Q \in M_{m \times n}(\mathbb{R}) con QTQ=InQ^T Q = I_n (colonne ortonormali)
    • R∈Mn×n(R)R \in M_{n \times n}(\mathbb{R}) triangolare superiore con elementi diagonali positivi

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

    Nella forma piena: Qfull∈Mm×m(R)Q_{\text{full}} \in M_{m \times m}(\mathbb{R}) è ortogonale e Rfull∈Mm×n(R)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 AA produce QQ e RR direttamente. La versione modificata è numericamente più stabile. Vedi: Gram-Schmidt.

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

    Riflessioni di Householder

    Una riflessione di Householder è una matrice ortogonale della forma:

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

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

    Hn⋯H2H1A=R  ⟹  A=QR,Q=H1H2⋯HnH_n \cdots H_2 H_1 A = R \implies A = Q R, \quad Q = H_1 H_2 \cdots H_n

    Costo: O(mn2−n3/3)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)(i,j):

    G(i,j,θ)=(⋱c⋯−s⋮⋱⋮s⋯c⋱)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 Ax⃗≈b⃗A\vec{x} \approx \vec{b} (m>nm > n), la soluzione ai minimi quadrati min⁡x⃗∥Ax⃗−b⃗∥2\min_{\vec{x}} \|A\vec{x} - \vec{b}\|_2 si ottiene:

    A=QR  ⟹  ∥Ax⃗−b⃗∥2=∥Rx⃗−QTb⃗∥2+∥(residuo)∥2A = QR \implies \|A\vec{x} - \vec{b}\|^2 = \|R\vec{x} - Q^T\vec{b}\|^2 + \|(\text{residuo})\|^2

    La soluzione è Rx⃗=QTb⃗R\vec{x} = Q^T\vec{b}, risolta per sostituzione all’indietro. È più stabile della soluzione tramite le equazioni normali ATAx⃗=ATb⃗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:

    A0=A,Ak=QkRk,Ak+1=RkQkA_0 = A, \quad A_k = Q_k R_k, \quad A_{k+1} = R_k Q_k

    Le matrici AkA_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.

    Ultimo aggiornamento: