Effetto Pivoting

Instabilità della fattorizzazione LU

Problema e definizioni

Partendo da (1) e definendo l'effetto benefico del pivoting:

• Fattore di crescita: \( \rho = \frac{\max |a_{ij,k}|}{\max |a_{ij}|} \)

Problema: determinare \( L \) e \( U \) tali che \( A = LU \).

Stima e aritmetica di macchina

Si ottiene una nuova stima:

In pratica, per effetto dell’aritmetica di macchina si trovano \( \tilde{L} \) e \( \tilde{U} \) tali che:

\( \tilde{L} \tilde{U} = A + \delta A, \; \delta A \in \mathbb{R}^{n \times n} \)

\( \| \delta A \| \leq n \cdot u \cdot \| A \| \)

Effetto del pivoting

Attenzione: quando \( \rho \cdot u \geq 1 \), invece di risolvere il sistema \( Ax = b \), si sta risolvendo il sistema \( (A + \delta A)\tilde{x} = b \).

Se non si effettua pivoting o si effettua pivoting parziale, si ha:

\( \|\tilde{L}\| \cdot \|\tilde{U}\| \leq \rho n^2 (3\|A\| + 5\|A\| + \|\delta A\|) \leq n^2 \cdot u\)

Pivoting totale

Se si effettua pivoting totale si ha:

\( \rho \leq n^{1/2} \)

Per dimensione del sistema \( n = \frac{1}{2}, \frac{1}{2}, \frac{1}{3}, \frac{1}{n-1}, \frac{1}{2}(2, 3, 4, \ldots, n) \)

\( \rho \leq n \cdot \rho_n = 1.1102 \times 10^{-16} \; (\epsilon = u = 2^{-53} \; \text{in unità di roundoff} \; (\text{MATLAB}))\)

Osservazioni pratiche

In pratica si osserva che per la pivotazione totale si ha \( \rho < n \).

Risolvo con LU senza pivoting:

• \(\max |a_{ij,k}| = \max |a_{ij}| = 2 \Rightarrow \max|u_{ij}| = 2\)
• \( \max |a_{ij}| = 1 \Rightarrow \rho \ll n \)

Il pivoting totale garantisce che \( \rho \) resti limitato al crescere di \( n \) e \( \rho \cdot u \ll n \).

Esempio pratico

Guardiamo quando \( \rho \geq u \):

Esempio: se \( i = j = n \), \( A^{-1}_{ij} > j \), in MATLAB: \( \beta = 2 \) e \( t = 54 \).

Consideriamo come termine noto il vettore \( b = [1; 1; 1; \ldots; 1] \) per \( n = 55 \).

Segue che \( \rho \geq n \geq u \). La soluzione esatta del sistema \( Ax = b \) per \( n \leq 54 \) dovrebbe essere risolta senza problemi. Per \( n \geq 55 \), la risoluzione del sistema dovrebbe risultare inesatta.

Implementazione in Matlab

Per svolgere la fattorizzazione LU senza pivoting, non si può usare il comando di MATLAB lu, ma bisogna usare metodi alternativi.

Proviamo a risolvere il sistema con \( n = 55 \) con la fattorizzazione LU senza pivoting.