Il pivoting parziale è una strategia di scambio delle righe usata nell’eliminazione di Gauss e nella fattorizzazione LU per evitare pivot nulli o troppo piccoli. Prima di eliminare gli elementi sotto il pivot, si cerca nella colonna corrente l’elemento di modulo massimo tra le righe ancora attive e lo si porta sulla diagonale.
Nel calcolo manuale il pivoting può sembrare un dettaglio. Nel calcolo numerico è invece una parte essenziale dell’algoritmo: dividere per un numero molto piccolo amplifica gli errori di arrotondamento e può rendere inaffidabile la soluzione anche quando il sistema lineare è matematicamente risolvibile.
Regola di scelta del pivot
Al passo k dell’eliminazione, si lavora sulla sottomatrice non ancora eliminata. Il pivot parziale è scelto cercando il massimo in modulo nella colonna k, a partire dalla riga k:
Se p_k\ne k, si scambiano le righe p_k e k. Dopo lo scambio, il pivot è:
Poi si eliminano gli elementi sotto il pivot usando i moltiplicatori:
La scelta del massimo nella colonna corrente limita il modulo dei moltiplicatori:
Questa è la ragione pratica del metodo: evita moltiplicatori enormi, che tendono ad amplificare arrotondamenti e cancellazioni numeriche.
Algoritmo operativo
Per un sistema:
il pivoting parziale procede così:
- alla colonna k, cercare tra le righe k,\ldots,n l’elemento di modulo massimo;
- scambiare la riga corrente con la riga che contiene quel massimo;
- applicare lo stesso scambio al termine noto \mathbf{b}, se si lavora sulla matrice aumentata;
- calcolare i moltiplicatori di eliminazione;
- annullare gli elementi sotto il pivot;
- passare alla colonna successiva.
Il termine “parziale” indica che si cercano pivot solo lungo la colonna corrente. Non si cerca il massimo in tutta la sottomatrice attiva, come nel pivoting totale.
Collegamento con la fattorizzazione LU
Senza scambi di riga, la fattorizzazione LU scrive:
Con pivoting parziale, gli scambi di riga sono raccolti in una matrice di permutazione P:
dove L è triangolare inferiore e U è triangolare superiore. Questa è la forma usata da molte librerie numeriche per matrici quadrate dense generiche.
Per risolvere:
si moltiplica implicitamente anche il termine noto:
Poiché PA=LU, si risolvono due sistemi triangolari:
In implementazione, spesso non si costruisce esplicitamente P: si memorizza un vettore di permutazioni o una sequenza di scambi di riga.
Perché serve
Il problema nasce quando il pivot diagonale corrente è nullo o quasi nullo. Consideriamo una matrice schematica:
Se si usa \varepsilon come pivot, il moltiplicatore della seconda riga è:
che può essere enorme. In aritmetica in virgola mobile, questo produce sottrazioni tra numeri grandi e perdita di cifre significative.
Con pivoting parziale, invece, la riga con elemento 1 viene portata in alto. Il pivot diventa grande rispetto alla colonna e il moltiplicatore resta controllato. Il sistema lineare non cambia: cambiano solo l’ordine delle equazioni e la stabilità del calcolo.
Confronto con altre strategie
| Strategia | Scelta del pivot | Costo e uso |
|---|---|---|
| Nessun pivoting | elemento diagonale corrente | veloce, ma fragile |
| Pivoting parziale | massimo in modulo nella colonna | standard in LU numerica |
| Pivoting scalato | massimo relativo alla scala della riga | utile se le righe hanno scale molto diverse |
| Pivoting totale | massimo nella sottomatrice attiva, con scambi di righe e colonne | più stabile, ma più costoso e più complesso |
Il pivoting totale può migliorare la stabilità in casi patologici, ma scambiare colonne significa cambiare l’ordine delle incognite. Questo richiede di tracciare anche una permutazione delle variabili. Per questo, nei risolutori LU ordinari, il pivoting parziale è il compromesso più usato.
Il pivoting scalato confronta gli elementi rispetto alla scala della riga. Può essere utile quando una riga contiene coefficienti molto grandi e un’altra coefficienti molto piccoli: scegliere il massimo assoluto può non rappresentare bene la qualità numerica del pivot.
Stabilità e condizionamento
Il pivoting parziale migliora la stabilità dell’algoritmo, ma non cambia il condizionamento numerico del problema. Questa distinzione è fondamentale.
Il condizionamento misura quanto la soluzione reale può cambiare se cambiano leggermente i dati:
dove \kappa(A) è il numero di condizionamento. Se \kappa(A) è grande, il problema è sensibile per natura: anche un algoritmo stabile può produrre una soluzione con errore relativo significativo.
Il pivoting, quindi, protegge dall’instabilità introdotta dall’eliminazione, ma non trasforma una matrice mal condizionata in una ben condizionata. Per problemi mal condizionati servono anche scaling, precondizionamento, regolarizzazione, riformulazione del modello o metodi numerici più adatti.
Crescita degli elementi
Durante l’eliminazione, gli elementi della matrice possono crescere rispetto a quelli iniziali. Una misura teorica è il fattore di crescita:
Il pivoting parziale tende a mantenere questa crescita moderata nella pratica, ma non garantisce un limite piccolo per ogni matrice possibile. Esistono casi costruiti apposta in cui la crescita è elevata. Questo spiega perché “molto efficace” non significa “matematicamente infallibile”.
Matrici sparse e fill-in
Nei problemi ingegneristici grandi, le matrici sono spesso sparse: molti coefficienti sono nulli. Il pivoting può introdurre fill-in, cioè nuovi elementi non nulli durante la fattorizzazione. Questo aumenta memoria e tempo di calcolo.
I risolutori sparsi bilanciano due obiettivi:
- scegliere pivot numericamente sicuri;
- preservare il più possibile la struttura sparsa.
Per questo usano strategie di ordinamento, soglie di pivoting e strutture dati dedicate. Nei modelli FEM, circuitali, fluidodinamici o di ottimizzazione, la scelta del pivot non è solo una questione algebraica: incide direttamente sul costo computazionale della simulazione.
Quando è sufficiente
Il pivoting parziale è generalmente adeguato per matrici quadrate dense generiche non singolari. È anche lo standard didattico e pratico per spiegare come passare dall’eliminazione di Gauss alla LU numerica.
Può non essere la scelta migliore quando:
- la matrice è simmetrica definita positiva, caso in cui è preferibile la fattorizzazione di Cholesky;
- il problema è di minimi quadrati o rettangolare, dove spesso si usa la fattorizzazione QR;
- la matrice è molto mal condizionata;
- la matrice è sparsa e il fill-in domina il costo;
- servono garanzie di stabilità più forti in casi particolari.
Applicazioni ingegneristiche
Il pivoting parziale compare ogni volta che si risolvono sistemi lineari con metodi diretti: reti elettriche lineari, analisi strutturale agli elementi finiti, discretizzazioni di equazioni differenziali, stima ai minimi quadrati, metodi impliciti per dinamica e trasferimento di calore, ottimizzazione numerica.
In un software tecnico, l’utente spesso non vede il pivoting: chiama una routine per risolvere A\mathbf{x}=\mathbf{b} e la libreria esegue internamente una LU con pivoting. Capire il meccanismo è comunque importante per interpretare warning di matrice quasi singolare, residui elevati, perdita di precisione o risultati instabili al variare di piccole perturbazioni.
Errori comuni
Il primo errore è scambiare le righe di A ma non il vettore \mathbf{b}. In quel caso si risolve un sistema diverso.
Il secondo errore è pensare che il pivoting risolva il mal condizionamento. Il pivoting stabilizza l’eliminazione, ma se i dati sono intrinsecamente sensibili la soluzione resta sensibile.
Il terzo errore è confrontare pivot solo con lo zero esatto. In aritmetica floating point, un pivot non nullo ma molto piccolo può essere numericamente pericoloso.
Il quarto errore è ignorare le permutazioni quando si riusa una fattorizzazione LU. Se si risolvono più sistemi con la stessa matrice, bisogna applicare sempre la stessa permutazione ai nuovi termini noti.
Il quinto errore è usare la LU con pivoting come soluzione universale. Per matrici simmetriche definite positive, sparse, rettangolari o molto mal condizionate, esistono metodi più adatti.
Vedi anche: eliminazione di Gauss, fattorizzazione LU, sistema lineare, matrice aumentata, condizionamento numerico, numero di condizionamento, errore di arrotondamento, virgola mobile, fattorizzazione QR, fattorizzazione di Cholesky e sistemi lineari numerici: Gauss, LU e pivoting.