Fattorizzazione QR

Motivazioni

è una matrice unitaria, cioè , allora , e è una triangolare superiore.


Ci chiediamo per quale motivo serve un'alternativa alla fattorizzazione .


Il vantaggio della fattorizzazione è una maggior stabilità rispetto alla . Infatti la è una fattorizzazione con matrici elementari unitarie, che conservano la norma 2.


Lo svantaggio è il raddoppio del costo computazionale.


Non occorre la tecnica del pivot.


Ci sono situazioni più sofisticate in cui si usa una tecnica di pivot per colonne, per garantire che gli elementi diagonali della abbiano una certa proprietà di ordinamento. Questa fattorizzazione si usa solo in casi limite, ad esempio nel calcolo degli autovalori (spettro completo) e del rango, e della s.v.d..


Data una matrice hermitiana, allora si può diagonalizzare con trasformazioni unitarie, scrivendo . La decomposizione in fattori singolari è l'estensione di quest'idea anche ai casi in cui la matrice non è simmetrica e non è quadrata.


La fattorizzazione esiste sempre ma non è unica.

Risoluzione del sistema

Con la fattorizzazione viene fattorizzata nel prodotto di una matrice unitaria e di una triangolare superiore. è unitaria quindi .


Nel sistema , cioè , pongo , risolvo prima

quindi si risolve
con matrice triangolare.


Il costo di risoluzione è .

Matrici elementari di Hausolder

Definizione 2.13

Una matrice elementare è una matrice della forma , con , parametro, e il prodotto è una diade.

 

La matrice della diade ha rango uguale a 1.


Nella fattorizzazione consideriamo le matrici elementari di Hausolder (o matrici di riflessione). Queste matrici sono della forma:


Proposizione 2.2

Le matrici di riflessione sono hermitiane, e sono unitarie se scelgo .

 
Dimostrazione

Dim. Hermitiane:

Unitarie: Sappiamo che , e per hermitianità

(infatti ) quindi
implica
cioè, se , deve valere , cioè

cvd

 

Altre proprietà sulle matrici di Hausolder

  1. Sia (la matrice di Hausolder è univocamente determinata da ), con , e . Allora per ogni , la matrice di Hausolder si comporta come l'identità.Infatti:
    infatti per .
  2. applicata nel sottospazio è:
    e per definizione di :
    cioè si ha una riflessione.

Esistenza della matrice elementare P

Teorema 2.10

Per ogni esiste matrice elementare di Hausolder tale che .

 
Dimostrazione

Dim. Devo determinare il parametro e la matrice elementare di Hausolder .


Siccome , (relazione ). Deve essere , allora

Inoltre è un'isometria quindi conserva la norma 2, cioè:
allora, eguagliando le due espressioni trovate per , ottengo:
Per determinare l'angolo , dev'essere
Per hermitianità di :
allora siccome lo scalare è uguale al suo coniugato, è reale, quindi .


, allora posso scriverlo come (relazione ).

e sostituendo l'espressione di :
, allora
ovvero con .


In conclusione:

e per la ,
Se , allora pongo .


Vale che

e per definizione di ottengo:
Chiamo il coefficiente che moltiplica , e metto in evidenza :


Osservazione 2.5

A patto di escludere che , è lecito porre , inquanto

allora per il fatto che , posso porre .

 



Tornando alla formula:

e ponendo , ottengo:

NB: posso escludere il caso , infatti, per definizione, se e solo se , e posso scegliere il vettore al di fuori del complemento ortogonale.


Calcoliamo:

e la quantità è positiva se come nell'ipotesi.


cvd

 


Riassumendo, poniamo

modifica solo la prima componente del vettore . Quindi:
e non c'è possibilità di errori di cancellazione.


Se , per costruzione, allora è una simmetrica ortogonale.

Il calcolo di costa operazioni per il calcolo della norma di , operazioni moltiplicative, un'estrazione di radice, cioè un numero dell'ordine di operazioni.

Algoritmo della fattorizzazione QR

Utilizziamo il teorema dimostrato per determinare la fattorizzazione .


Suppongo di essere al passo k-esimo della fattorizzazione . Allora chiamo la -esima sottocolonna della matrice , che devo azzerare (corrisponde al vettore del teorema). Scelgo il vettore che ha 0 nelle prime componenti, e le componenti successive sono:

dove definisco

(per la definizione di sfrutto l'espressione ricavata nel teorema, cioè , e sfrutto anche l'espressione ricavata per )
Allora calcoliamo:
e raccogliendo ottengo:
cioè
Allora ho determinato univocamente la matrice


Se il vettore è tutto nullo, considero e , in modo che a quel passo la matrice di Hausolder sia l'identità.


Applicando la matrice trovata al vettore cioè alla colonna , tutte le entrate di da a n vengono azzerate, mentre si ha (infatti ). Applico poi la matrice di Hausolder allae colonne rimanenti di A.


Riepilogando, data la matrice di partenza, con il primo passo azzero la prima colonna e modifico , e poi ripeto il procedimento, per passi, e ottengo la matrice triangolare superiore .


Il prodotto di matrici unitarie è unitario, e sappiamo che

e per hermitianità:
quindi

Non unicità della fattorizzazione

Proposizione 2.3

Per ogni esiste la fattorizzazione , ma non è unica.

 
Dimostrazione

Considero una matrice di fase , cioè una matrice diagonale con elementi con , ed è una matrice unitaria. Allora , cioè , e definisco dove e , dove è ancora unitaria e è triangolare superiore. Allora ho comunque una fattorizzazione della matrice.


cvd

 



Questa proprietà può essere sfruttata per scegliere la in modo che gli elementi sulla diagonale siano ordinati in una certa maniera.

Fattorizzazione e risoluzione dei sistemi

Per risolvere il sistema lineare, non è necessario trovare esplicitamente la matrice , e nemmeno le .


Passo 1: pongo , e chiamo la matrice che accosta e .


Passo 2: Chiamo , con

Chiamo poi il vettore riga , in modo da scrivere:

Passo :

con
Infine


Passo n:

il vettore è stato calcolato senza calcolare esplicitamente le matrici , ed è tale che .

Costo computazionale

Per analizzare il costo del -esimo passo, tengo conto che ha componenti nulle e componenti diverse da 0. Per calcolare , le operazioni sono quindi .

Stabilità della fattorizzazione QR

Definizione 2.14

Si definisce norma di Frobenius di la quantità

 


Questa non è una norma matriciale indotta, infatti

ed è diversa da 1, mentre con le norme matriciali inditte l'identità a norma 1.

Teorema 2.11

Sia la soluzione effettivamente calcolata con l'applicazione delle effettive alla matrice per calcolare la . Sia il vettore che compare nella risoluzione backward del sistema . Allora è soluzione esatta di un sistema

dove

 

L'entità della perturbazione dipende dai dati iniziali, dalle dimensioni della matrice, e dalla matrice di fattorizzazione. Non dipende dalla norma di Frobenius di che è 1.

Consideriamo le matrici al k-esimo passo di fattorizzazione, e calcolo il prodotto

siccome allora non varia con i passi di fattorizzazione. Allora
allora
inoltre
allora non c'è possibilità di esplosione dei coefficienti.

La è stabile e può essere fatta senza pivot.

 PrecedenteSuccessivo