Tecniche del pivot

Tecnica del pivot parziale[modifica | modifica wikitesto]

Supponiamo di essere al k-esimo passo di fattorizzazione, in cui devo azzerare i coefficienti della k-esima colonna a partire dall'entrata . Cerco l'indice tale che , e scambio quindi la -esima riga con la -esima, applicando alla matrice la matrice di permutazione , che è l'identità in cui scambio la -esima riga con la k-esima.

Bisogna verificare che anche moltiplicando per la matrice di permutazione, la fattorizzazione rimane del tipo .

Esempio in dimensione n=4[modifica | modifica wikitesto]

In dimensione , all'ultimo passo dell'eliminazione si ottiene

(le matrici di permutazione sono alternate a quelle elementari)

Le matrici di permutazione hanno la proprietà che , allora, inserisco il doppio prodotto nell'uguaglianza nelle posizioni opportune, per far comparire vicine tra loro le matrici di permutazione.

Ad esempio:

Ponendo , al passo successivo ottengo:
e ponendo , e , ottengo:
e pongo .
Voglio verificare che anche le matrici segnate sono ancora matrici elementari di Gauss, e quindi invertibili.

Considero, ad esempio,

Invece
Allora calcolo il prodotto :
(scambio la terza riga con la quarta.) Invece, moltiplicando a destra per , scambio la terza e la quarta colonna, e ottengo la matrice
che ha la stessa forma di .
Consideriamo invece la matrice che scambia la seconda riga con la terza:
Allora
e moltiplicando per :
che non è più una matrice elementare di Gauss.
In ogni caso, la moltiplicazione per non è più un'operazione ammissibile nell'eliminazione di Gauss al passo , perché si può operare solo nella sottomatrice in basso a destra, quindi non ci sono problemi.

Fattorizzazione[modifica | modifica wikitesto]

Dato il sistema , moltiplico per ambo i membri per far comparire la matrice di permutazione, e ottengo:

Allora devo considerare il termine noto permutato , e risolvo prima il sistma lineare
e poi

Effetti del pivot parziale[modifica | modifica wikitesto]

Il pivot parziale ha un effetto stabilizzante, ovvero riduce l'errore algoritmico. In particolare:

  1. Come prima, è una matrice triangolare inferiore con 1 sulla diagonale principale e nella parte inferiore.
  2. I moltiplicatori hanno espressione
    quindi, per ogni i coefficienti sono .
  3. La crescita degli elementi di è limitata, infatti i coefficienti della "nuova" matrice sono:
    mentre per gli elementi della matrice rimangono invariati, e quindi
    in definitiva
    Chiamo il massimo modulo degli elementi della matrice . Allora, passando ai massimi nella disuguaglianza sopra,
    e applicando a ritroso la relazione

Errore algoritmico[modifica | modifica wikitesto]

Teorema 2.7

Sia tale che i suoi elementi siano numeri macchina (focus sull'errore algoritmico). Chiamo le matrici effettivamente calcolate, allora dove vale la relazione

(a livello notazionale, chiamo la matrice che ha come componenti i moduli degli elementi di )

 
In questa relazione, oltre alla dipendenza dalla dimensione, da e dalla precisione di macchina, il fatto significativo è che compaiono .
Teorema 2.8

Siano e, considerando effettivamente calcolate, chiamo la soluzione del sistema e soluzione di . Allora è la soluzione di

con
(interpreto l'errore algoritmico come errore inerente del problema perturbato)

 


Esempio 2.7

Considero la matrice

dove è scelto in modo che la soluzione del sistema lineare sia . Il problema è ben condizionato, infatti
e quindi se è piccolo, .

Per quanto riguarda la stabilità, senza tecnica del pivot:

mentre la soluzione esatta ha entrambe le componenti uguali a 1, e il problema è dato dalla crescita dei coefficienti di .

 

Tecnica del pivot totale[modifica | modifica wikitesto]

Per ogni passo , cerco tale che

assumo di poter fare permutazioni di colonne oltre che permutazioni di righe .
Il problema che sorge è che, facendo permutazioni di colonne, si permuta l'ordine delle incognite.

Esempio 2.8

Nella catena di moltiplicazioni di matrici elementari, nel caso ,

ma pongo . L'altro pezzo di viene trattato come prima.

 

Come prima

e per risolvere il sistema permuto a sinistra,
devo inserire la , allora pongo
Calcolo permutazione del termine noto, e risolvo quindi:
Questo procedimento ha un effetto più stabilizzante rispetto al pivot parziale, infatti si ha:
e non sono state trovate matrici per cui vale l'uguaglianza.

Costo computazionale[modifica | modifica wikitesto]

La risoluzione forward o backward, considerando il numero di operazioni moltiplicative, ha come costo computazionale

infatti, per ogni incognita, si ha l'espressione
Invece la fattorizzazione ha costo
che è dell'ordine di (il primo addendo serve per il calcolo dei moltiplicatori, e il secondo per il calcolo del blocco quadrato in basso a destra).

 PrecedenteSuccessivo