Decomposizione QR

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

In matematica, in particolare in algebra lineare, la decomposizione QR o fattorizzazione QR di una matrice quadrata a coefficienti reali o complessi ${\displaystyle M}$ è una scomposizione del tipo

${\displaystyle M=QR,}$

dove ${\displaystyle Q}$ è una matrice ortogonale, e ${\displaystyle R}$ è una matrice triangolare superiore. Si può dimostrare che tutte le matrici quadrate ammettono una decomposizione QR, anche se essa non è unica. Nel caso in cui la matrice ${\displaystyle M}$ sia a coefficienti complessi, allora ${\displaystyle Q}$ è una matrice unitaria.

Si può calcolare esplicitamente la fattorizzazione QR di una matrice data in tempo ${\displaystyle O(n^{3})}$ operazioni aritmetiche attraverso l'uso delle trasformazioni di Householder o di quelle di Givens.

L'applicazione principale della fattorizzazione QR è la soluzione di sistemi lineari: una volta fattorizzata la matrice ${\displaystyle A=QR}$ di un sistema lineare ${\displaystyle Ax=b}$ con costo ${\displaystyle O(n^{3})}$, la soluzione del sistema è data da

${\displaystyle x=R^{-1}(Q^{t}b)}$

Il calcolo di ${\displaystyle c=Q^{t}b}$ richiede ${\displaystyle O(n^{2})}$ operazioni, mentre il calcolo di ${\displaystyle x=R^{-1}c}$ si può effettuare attraverso un algoritmo di sostituzione all'indietro sempre con ${\displaystyle O(n^{2})}$ operazioni. Il costo dominante quindi è proprio quello della fattorizzazione.

La complessità computazionale di questo metodo risolutivo è quindi la stessa della soluzione mediante la fattorizzazione LU (o algoritmo di Gauss), ma questo algoritmo risulta avere una migliore stabilità numerica.

Inoltre, la fattorizzazione QR può essere utilizzata per il calcolo di basi ortonormali e per la risoluzione di un sistema ai minimi quadrati.

Alla base della fattorizzazione QR vi è un metodo, noto come metodo QR, utilizzato per calcolare gli autovalori di una matrice e i rispettivi autovettori.

• Decomposizione LU
• Decomposizione di Cholesky
• Decomposizione di una matrice
• Sistema lineare
• Algoritmo di Gauss
• Trasformazione di Householder

• (EN) Eric W. Weisstein, QR Decomposition, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica