Fattorizzazione di Cholesky

Esistenza della fattorizzazione A = R^t R[modifica | modifica wikitesto]

Questo tipo di fattorizzazione si applica solo al caso di matrici definite positive.
Teorema 2.9

Supponiamo di avere simmetrica e non singolare. è definita positiva se e solo se esiste triangolare superiore tale che .

 
Dimostrazione

: è non singolare, e supponiamo , allora è non singolare infatti

e quindi implica non singolare. Allora
quindi
e siccome ho escluso il caso nullo,
e è definita positiva.
: considero simmetrica e definita positiva:
dove è una sottomatrice di dimensione e è un vettore di componenti.
Definisco nel seguente modo:
Il prodotto delle due matrici è:
ed eguaglio termine a termine la decomposizione a blocchi con il risultato del prodotto ottengo:
Definiamo la quantità
Se è ancora simmetrica e definita positiva, si può iterare la procedura, lavorando su , fino a ottenere la fattorizzazione con triangolare superiore. Quindi verifichiamo che è simmetrica definita positiva.

Simmetria: Sappiamo che

Positività: Applico ad una matrice elementare per azzerare la prima sottocolonna, con
Il risultato del prodotto è:
(come nell'eliminazione di Gauss ordinaria, la prima riga rimane invariata e la prima colonna viene azzerata)
Per poter azzerare una sottoriga, applico alla matrice un passo di eliminazione gaussiana per righe. Eseguo il prodotto con
(ora la sottocolonna dei coefficienti è sulla prima riga)
Calcolando il prodotto
Osservo che . Ponendo , per ogni ,
e perché è non singolare. Siccome per ipotesi è definita positiva, è maggiore di 0, e quindi la matrice grande è definita positiva.

Allora

è definita positiva, perché sottomatrice principale di una definita positiva. Quindi è definita positiva e la procedura si può iterare sulla matrice di dimensioni . Lavorando su , si determinano progressivamente gli elementi di , triangolare superiore.
cvd

 


Osservazione 2.4

Considero

Alla matrice definita positiva, sottraggo una matrice semidefinita positiva, e non è ovvio che il risultato sia una definita positiva. Infatti, ad esempio
non è definita positiva.

 

Complemento di Shur[modifica | modifica wikitesto]

Questa dimostrazione permette di osservare la seguente proprietà: il complemento di Shur di una definita positiva è definito positivo, dove è il complemento di Shur di in .
Definizione 2.12

In generale, data una matrice a blocchi della forma

dove il primo blocco è , il secondo , e così via, e dove la dimensione della matrice è , si chiede che sia non singolare, allora il complemento di Shur è definito come

 

Algoritmo per il calcolo di R[modifica | modifica wikitesto]

In questa scrittura suppongo che gli elementi di vengano progressivamente sovrascritti con quelli di trovati passo per passo.

Descrizione esplicita: Per calcolo
e al passo -esimo questa è l'unica operazione da fare.

Allora, per , faccio le seguenti operazioni:

  1. Per ,
    (queste istruzioni corrispondono a , definizione del vettore )
  2. per , e per ,
    (Nell'ultimo blocco di istruzioni si definiscono i coefficienti di , cioè ).

Ovviamente, alla fine di ogni passo k, le entrate con vengono annullate.

Costo computazionale[modifica | modifica wikitesto]

E' sufficiente calcolare solo metà della sottomatrice , che è simmetrica.

Le operazioni richieste sono quindi:

  1. estrazioni di radici quadrate (una per ogni passo di fattorizzazione)
  2. operazioni moltiplicative per ogni passo . Infatti, al passo k, ha indici da a , eper ciascun elemento houna divisione.
  3. Per ogni elemento di , ho un'operazione moltiplicativa, e quindi per ogni passo le operazioni sono
    con , cioè

Complessivamente il numero di operazioni è:

e raccogliendo ottengo:
Il costo computazionale è pari a quello dell'eliminazione di Gauss per le simmetriche.

Stabilità[modifica | modifica wikitesto]

Considerando il prodotto , segue che

Allora ciascun è tale che , quindi
Chiamando l'elemento di modulo massimo, si ha
Quindi gli elementi di hanno crescita controllata da .

L'algoritmo è stabile.

Rapporto tra fattorizzazione LU e di Cholesky[modifica | modifica wikitesto]

Data una matrice simmetrica definita positiva, considero il rapporto tra la fattorizzazione e quella di Cholesky. La fattorizzazione esiste unica per una definita positiva, perché le matrici di testa di una definita positiva sono definite positive, e non singolari, quindi le ipotesi del teorema di esistenza e unicità della fattorizzazione sono soddisfatte.

Tuttavia perché la diagonale di ha entrate uguali a 1.

Pongo dove è una matrice con elementi diagonali dati dalla diagonale principale di .

Per ipotesi

e per l'unicità di fattorizzazione,
allora
con matrice a elementi diagonali positivi. Pongo , allora
perché è definita positiva, allora è non singolare.
Definisco come la matrice che ha come elementi diagonali le radici quadrate degli elementi di .

Allora

cioè
dove , .

Proposizione 2.1

L'eliminazione gaussiana conserva simmetria e definita positività.

 
Dimostrazione

Simmetria: Sappiamo che

con
cioè, sostituendo esplicitamente :
per simmetria di , quindi si può scrivere:
e tenendo conto che si ha
cioè la sottomatrice in basso a destra ottenuta dopo il passo k-esimo è ancora simmetrica.

Definita positività: Consideriamo

L'ultima entrata è il complemento di Shur di in , allora siccome è definita positiva, anche il completamento è definito positivo. Allora l'eliminazione gaussiana è stabile sulle definite positive.

cvd

 
 PrecedenteSuccessivo