Tecniche del pivot

Tecnica del pivot parziale

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

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

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

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

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 Errore del parser (errore di sintassi): {\displaystyle \\delta_A \le 4 n u (|A|+|\bar L| |\bar U|+o(u^2))} (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

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

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