Variante del pivot parziale

Non ci siamo occupati di considerare il caso in cui a_kk=0(o è un valore di macchina così piccolo da poter essere considerato nullo). Questo può essere dovuto talora ad errori del sistema floating-point, ma spesso accade perché una sottomatrice di A non è invertibile. Infatti il Teorema 4.4 garantisce l'esistenza della fattorizzazione LU se le sottomatrici principali di testa sono non singolari.

Nel caso generale, invece, bisogna sfruttare il Teorema 4.5: esso dice che, permutando opportunamente le righe del sistema, si può sempre trovare la fattorizzazione LU. Ciò significa che, quando al passo k dobbiamo scegliere il pivot, anziche prendere a_kk prendiamo un elemento non nullo tra gli a_ik (con $i\geq k$), quindi scambiamo la i-esima e la k-esima riga e proseguiamo. In questo modo il pivot del passo k è certamente non nullo.

In pratica, anziché scegliere semplicemente un elemento non nullo, si sceglie l'elemento di massimo modulo (in questo modo l'algoritmo risulta più stabile). Lo scambio delle righe viene fatto scambiando semplicemente i puntatori. Abbiamo allora

    /* Passo k dell'eliminazione di Gauss con pivot parziale */
                       /* Ricerca del pivot sulla colonna */
    pivot = a[k][k];
    irig = k;
    for (i=k+1; i<n; i++)
        if ( fabs(a[i][k])>fabs(pivot) ) {
            pivot = a[i][k];
            irig = i;
        }
                       /* Scambio delle righe */
    temp = a[irig];
    a[irig] = a[k];
    a[k] = temp;
                       /* Procede come prima */
    for (i=k+1; i<n; i++) {
        m = -a[i][k] / pivot;
        for (j=k; j<n; j++)
            a[i][j] = a[i][j] + m*a[k][j];
    }

In forma matriciale, un'operazione di scelta del pivot corrisponde ad una moltiplicazione a sinistra per una matrice di permutazione (che semplicemente scambia due righe).

Si deve tenere conto di questo scambio di righe, a seconda di cosa si sta facendo:

• se si risolve un sistema lineare, bisogna effettuare lo scambio anche sul vettore dei termini noti: il sistema $A{\bf x}={\bf b}$ viene trasformato in $PA{\bf x}=P{\bf b}$, che è equivalente;
• se si calcola il determinante, esso cambia segno ad ogni scambio di righe; bisogna quindi ``contare'' gli scambi, e il determinante che si ottiene alla fine come $\prod u_{ii}$ va cambiato di segno se il numero di scambi è dispari.