Pivot (matematica)

Da Wikipedia, l'enciclopedia libera.

In matematica, e più specificamente in algebra lineare, e in informatica, il pivot (in francese perno), elemento di pivot o elemento pivotale di una matrice è l'elemento della matrice che viene scelto per primo da un algoritmo (algoritmo di Gauss, ordinamento quicksort, metodo del simplesso, etc) e che si richiede rispetti determinate proprietà allo scopo di far funzionare correttamente o del tutto l'algoritmo, o più semplicemente per renderne l'esecuzione più efficiente.

Quando ci si riferisce a matrici a scalini, solitamente nell'ambito dell'eliminazione gaussiana, con pivot di una riga si intende il primo elemento non nullo della riga (se esiste).

Pivoting[modifica | modifica wikitesto]

Per far sì che l'elemento in posizione di pivot sia qualitativamente buono, cioè rispetti le proprietà necessarie ad assicurare il funzionamento o l'efficienza dell'algoritmo, vengono effettuati una serie di scambi di righe e di colonne della matrice: questa serie di scambi volta ad individuare il pivot prende il nome di pivoting o pivotazione.

Quando vengono scambiate solo le righe o solo le colonne della matrice si parla di pivoting parziale o pivotazione parziale, quando vengono scambiate sia le righe che le colonne si parla invece di pivoting totale o pivotazione totale.

La serie di scambi effettuati nel pivoting può essere rappresentata tramite una matrice di permutazione ottenuta effettuando gli stessi scambi di righe e/o colonne sulla matrice identità. La moltiplicazione della matrice originale per questa matrice di permutazione risulta nella matrice risultato del pivoting.

Nella pratica, comunque, è raro che gli algoritmi effettuino realmente gli scambi, ma, per motivi di efficienza, si limitano a tenere traccia delle permutazioni effettuate.

Esempi[modifica | modifica wikitesto]

Nell'algoritmo di Gauss la scelta di un pivot con valore assoluto grande migliora la stabilità numerica dell'algoritmo.

Nell'algoritmo di ordinamento quicksort, l'elemento di pivot viene usato per partizionare gli elementi in quelli minori o uguali e in quelli maggiori del pivot. Più il pivot sarà vicino all'elemento mediano più l'algoritmo opererà con efficienza.

Voci correlate[modifica | modifica wikitesto]