Fattorizzazione lU (eliminazione gaussiana)

Eliminazione gaussiana[modifica | modifica wikitesto]

Considero la matrice e faccio operazioni sulle sue righe.

Risolvo direttamente l'eliminazione di Gauss sulla matrice che ha come colonne le colonne di e poi i termini noti. Se i termini non sono noti a priori possono esserci dei problemi, e si può applicare il metodo della potenza inversa, che serve per calcolare l'autovalore di modulo minimo.

Dopo aver fattorizzato , devo risolvere i sistemi e poi , spezzo quindi il problema in due parti, separando la fattorizzazione della matrice dalla trattazione vera e propria della soluzione.

Descrizione dell'algoritmo[modifica | modifica wikitesto]

L'eliminazione gaussiana trasforma un sistema della forma in un sistema della forma .

Supponiamo di essere al k-esimo passo di fattorizzazione, cioè supponiamo che la parte della matrice superiore alla riga sia già stata ridotta a una triangolare superiore. A ogni passo, le operazioni sulle righe della matrice modificano anche il blocco quadrato in basso a destra, con le righe dalla -esima all'-esima.

Sottraggo alla -esima equazione la -esima moltiplicata per un opportuno coefficiente.

Descrivendo l'algoritmo, per (passi di fattorizzazione), per (righe successive alla k-esima), definisco l'elemento

e sottraggo ad la riga , in modo che
Ad esempio, nel passo , prendo la prima riga e la sottraggo a tutte le altre moltiplicata per il rispettivo coefficiente , nel passo successivo lascio invariate le righe precedenti alla k-esima, e così via.

I coefficienti nel blocco quadrato degli con in basso a destra, che vengono modificati ad ogni passo k, diventa:

Analogamente per il termine noto:

Matrice elementare di Gauss[modifica | modifica wikitesto]

Definizione 2.11

Sia una matrice triangolare inferiore, con , divisa in quattro blocchi e tale che:

  1. Nel blocco in alto a sinistra c'è l'identità;
  2. i blocchi di nord-est e di sud-ovest sono nulli.
  3. la matrice in basso a destra ha la prima sottocolonna della forma
    dove gli sono i coefficienti definiti prima, mentre la prima riga di questo blocco è il vettore , e nel quadrato in basso c'è l'identità.

In forma sintetica:

 

In maniera compatta: , dove è un vettore colonna con le prime k componenti uguali a 0, e le restanti uguali a e è il k-esimo vettore della base canonica. Il prodotto tra il vettore colonna e il vettore riga è una matrice.

Rappresentazione compatta dell'eliminazione di Gauss[modifica | modifica wikitesto]

Poniamo , per , dove indica la matrice ottenuta al passo k-esimo. Ogni passo dell'eliminazione di Gauss può essere quindi rappresentato in modo compatto come un prodotto tra due matrici. Allora, chiamando la matrice triangolare superiore ottenuta all'ultimo passo, si ha:

Per poter scrivere , ci si chiede se il prodotto delle è invertibile, e questo è vero perché è prodotto di matrici invertibili. Allora si può scrivere:
ed esplicitando la matrice inversa del prodotto:

Osservazione 2.3

Siccome è la matrice triangolare inferiore con entrate uguali a 1 sulla diagonale, il suo determinante, prodotto delle entrate diagonali, è 1, e quindi

allora la fattorizzazione della matrice può essere considerata anche come un modo per calcolare il determinante.

 

Teniamo conto del fatto che:

Allora
infatti si verifica che
ma è il vettore nullo, gli altri due termini sono opposti e rimane .

Considero allora , che si riscrive come

L'ultimo passaggio vale perché, ad esempio
e come prima, perché hanno zeri in posizioni complementari. In generale
i termini misti si annullano, e quindi rimane
e, procedendo così fino al passo n-esimo, le colonne si sommano una accanto all'altra, e si ottiene la matrice triangolare inferiore cercata, con entrate uguali a 1 sulla diagonale, zeri nella parte superiore, e i moltiplicatori nella parte inferiore. (i moltiplicatori in sono positivi)

Operazioni sul termine noto[modifica | modifica wikitesto]

Le operazioni che l'eliminazione gaussiana fa sul termine noto equivalgono alla risoluzione del sistema . Eseguo, per e per :

Esempio 2.6

Ad esempio, nel caso di una matrice ,

Al primo passo di eliminazione gaussiana, il primo coefficiente è già definitivo mentre tutti gli altri vengono modificati. Al secondo passo anche il secondo coefficiente risulta definitivo, e così via. Al terzo passo, si lavora solo sull'ultima componente.

Si ha un aggiornamento progressivo per colonne.

 

La fattorizzazione ha un costo computazionale di operazioni, mentre la risoluzione vera e propria ne richiede .

[modifica | modifica wikitesto]

Vogliamo risolvere il sistema , e nell'algoritmo dell'eliminazione gaussiana, per , per , compiamo le seguenti operazioni:

  1. definiamo i moltiplicatori
  2. per
  3. Sul termine noto
  4. passo quindi dal sistema al sistema con soluzione di .
  5. è la matrice ottenuta dopo l'eliminazione gaussiana, mentre ha entrate uguali a 1 sulla diagonale principale e ha i coefficienti nella parte inferiore.

Problema dell'esistenza della fattorizzazione[modifica | modifica wikitesto]

Data una matrice quadrata , chiamo sottomatrici principali di le matrici , ottenute privando della k-esima riga e della k-esima colonna. Si dicono matrici principali di testa le sottomatrici che contengono il coefficiente .
Teorema 2.5

Data una matrice quadrata in , se le matrici sono non singolari per , allora esiste unica la fattorizzazione .

 
Nel momento del calcolo del moltiplicatore , in aritmetica esatta si hanno problemi se . Siccome la matrice è non singolare, esisterà una riga in cui il termine in posizione k è diverso da 0, allora, per evitare problemi, si scambia questa riga con la k-esima.
Teorema 2.6

Data , allora esiste matrice di permutazione tale che è fattorizzabile nel prodotto .

 

Una matrice di permutazione che scambia le righe i-esima e k-esima si ottiene scambiando tali righe nella matrice identica, in particolare, considerando i quattro coefficienti e , si inverte il loro valore, ponendo e .

 PrecedenteSuccessivo