Fattorizzazione di Cholesky

Esistenza della fattorizzazione A = R^t R

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

Dim. : è 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

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

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

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à

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

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

Dim. 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