Punti 8–10 Glossario Instabilità Algoritmica vs Stabilità Wilkinson

Fattorizzazione LU senza Pivoting vs $PA = LU$

Il fallimento della fattorizzazione LU standard può dipendere da due motivi: algebrico (pivot nullo) oppure numerico (pivot microscopico non nullo). Qui puoi toccare con mano l'esatto controesempio d'esame del Prof. Piazzon e vedere come il pivoting parziale risolve entrambi i problemi controllando i moltiplicatori $|m_{ik}| \le 1$.

Il Problema Matematico e la Buona Posizione

Consideriamo il sistema lineare $Ax = b$ con: $$A = \begin{pmatrix} \varepsilon & 1 \\ 1 & 1 \end{pmatrix}, \qquad b = \begin{pmatrix} 1 \\ 2 \end{pmatrix}, \qquad \varepsilon \ll 1$$ La matrice ha $\|A\|_\infty = 2$, $\det(A) = \varepsilon - 1 \approx -1$, e inversa $A^{-1} = \frac{1}{\varepsilon - 1}\begin{pmatrix} 1 & -1 \\ -1 & \varepsilon \end{pmatrix}$. Quindi $\|A^{-1}\|_\infty \approx 2$ e il numero di condizionamento è: $$\kappa_\infty(A) = \|A\|_\infty \|A^{-1}\|_\infty \approx 2 \times 2 = 4$$ Il problema matematico è ottimamente condizionato. Qualsiasi errore nella soluzione è quindi imputabile al 100% all'instabilità dell'algoritmo senza pivoting!

Parametri Floating-Point

Parametro $\varepsilon = 10^k$: 1.0e-8

$10^{-1}$ (moderato) $10^{-8}$ (critico) $10^{-14}$ (estremo)

Cifre di Mantissa Simulate ($d$): 8 cifre (Singola)

3 (Didattico) 8 (Float32) 16 (Double IEEE)

Precisione Macchina $\varepsilon_{mac}$: 1.0e-8

Moltiplicatore $m_{21} = 1/\varepsilon$: 1.0e+8

Assorbimento $1 - 1/\varepsilon$: Avvenuto!

Preset Tipici d'Esame:

LU Senza Pivoting (Instabile)

Errore $x_1$: 100%

1. Moltiplicatore:

m₂₁ = 1 / ε = 100000000

2. Operazione critica in U:

U₂₂ = fl(1 - m₂₁) = -100000000

L'1 iniziale viene assorbito e cancellato!

3. Sostituzione indietro:

x₂ = 1.000000
x₁ = (1 - x₂)/ε = 0.000000

Soluzione calcolata $x$: [ 0.0000, 1.0000 ]

PA = LU con Pivoting (Stabile)

Errore $x_1$: 0.000%

1. Scambio righe 1 ↔ 2:

P = [0 1; 1 0], Pivot = 1.0

2. Moltiplicatore controllato:

m₂₁ = ε / 1 = 1.0e-8 ≤ 1

|m₂₁| ≤ 1: nessuna amplificazione!

3. Sostituzione indietro:

x₂ = (1 - 2ε)/(1 - ε) ≈ 1.000000
x₁ = 2 - x₂ ≈ 1.000000

Soluzione calcolata $x$: [ 1.0000, 1.0000 ]

Errore Relativo su $x_1$ vs $\log_{10}(\varepsilon)$

LU No-Pivot PA = LU

Non appena $\varepsilon \le 10^{-d}$, l'algoritmo $LU$ senza pivoting subisce assorbimento e l'errore balza istantaneamente al 100% (linea rossa). Il metodo $PA=LU$ (linea verde) resta imperturbato a precisione macchina.

Il Dettaglio d'Esame: Lo Scambio Contestuale dei Moltiplicatori in $L$

Le matrici di permutazione $P^{(k)}$ e le matrici elementari di Gauss $L^{(k)}$ non commutano ($P^{(k)} L^{(j)} \ne L^{(j)} P^{(k)}$). Per ottenere la forma finale compatta $PA = LU$ con $P = P^{(n-1)} \dots P^{(1)}$, l'algoritmo deve applicare una regola d'oro: quando al passo $k$ si scambiano le righe $k$ ed $r$ nella matrice attiva, si devono scambiare anche i moltiplicatori già memorizzati nelle colonne da $1$ a $k-1$ delle righe $k$ ed $r$!

Preset Matrice:

Stato: Inizializzazione

Matrice Attiva / Fattore $U$

Triangolarizzazione

Righe scambiate o ridotte al passo corrente

Fattore $L$ (Unitario Sottodiagonale)

|m_ik| ≤ 1

I moltiplicatori vengono scambiati contestualmente a $P$!

Permutazione $P$ & Vettore $p$

P = P^(n-1)...P^(1)

p = [ 1, 2, 3 ]

Spiegazione Dettagliata del Passo Corrente

Seleziona un preset o premi Avanti per iniziare la riduzione con pivoting parziale per righe.

Verifica Identità Algebrica d'Esame: $PA = LU$

Residuo $\|PA - LU\|_\infty = \mathbf{0.000000}$

✓ La fattorizzazione è esatta e stabile.