Calcolo numerico/Tecniche del pivot

Tecnica del pivot parziale

Supponiamo di essere al $k$-esimo passo di fattorizzazione, in cui bisogna azzerare i coefficienti della $k$-esima colonna a partire dall'entrata $k+1$. Cerchiamo l'indice $\overline{i}$ tale che $A_{\overline{i},k}={max}_{i=k}^n|a_{ik}|$, e scambiamo quindi la $\overline{i}$-esima riga con la $k$-esima, applicando alla matrice $A^{(k)}$ la matrice di permutazione $p_k$, che è l'identità in cui scambio la $\overline{i}$-esima riga con la $k$-esima.

Bisogna verificare che anche moltiplicando per la matrice di permutazione, la fattorizzazione rimane del tipo $LU$.

Esempio in dimensione n=4

In dimensione $n=4$, all'ultimo passo dell'eliminazione si ottiene

$U=M_3{P}_3{M}_2{P}_2{M}_1{P}_{1}A,$

(le matrici di permutazione sono alternate a quelle elementari)

Le matrici di permutazione hanno la proprietà che $P_k{P}_k=I$, allora, inserisco il doppio prodotto nell'uguaglianza nelle posizioni opportune, per far comparire vicine tra loro le matrici di permutazione.

Ad esempio:

$\text{passo 1},U=M_3{P}_3{M}_2{P}_2{M}_1{P}_2{P}_2{P}_{1}A,$

Ponendo ${\overline{M}}_1=P_2{M}_1{P}_2$, al passo successivo otteniamo:

$U=M_3{P}_3{M}_2{P}_3{P}_3{\overline{M}}_1{P}_3{P}_3{P}_2{P}_{1}A$

e ponendo ${\overline{M}}_2=P_3{M}_2{P}_3$, e ${\hat{M}}_1=P_3{\overline{M}}_1{P}_3$, ottengo:

$U=M_3{\overline{M}}_2{\hat{M}}_1{P}_3{P}_2{P}_{1}A$

e si pone $P_3{P}_2{P}_{1}A=PA$.

Vogliamo verificare che anche le matrici segnate sono ancora matrici elementari di Gauss, e quindi invertibili.

Consideriamo, ad esempio, ${\overline{M}}_2=P_3{M}_2{P}_3$

$M_2=\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& M_{32}& 1& 0\\ 0& M_{42}& 0& 1\end{array}$

Invece

$P_3=\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}$

Allora calcoliamo il prodotto $P_3{M}_2{P}_3$:

$P_3{M}_2=\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& M_{42}& 0& 1\\ 0& M_{32}& 1& 0\end{array}$

(scambiiamo la terza riga con la quarta). Invece, moltiplicando a destra per $P_3$, scambiamo la terza e la quarta colonna, e otteniamo la matrice

${\overline{M}}_2=\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& M_{42}& 1& 0\\ 0& M_{32}& 0& 1\end{array}$

che ha la stessa forma di $M_2$.

Consideriamo invece la matrice $P_2$ che scambia la seconda riga con la terza:

$p_2=\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$

Allora

$P_2{M}_2=\begin{array}{cccc}1& 0& 0& 0\\ 0& M_{32}& 1& 0\\ 0& 1& 0& 0\\ 0& M_{42}& 0& 1\end{array}$

e moltiplicando per $P_2$:

$P_2{M}_2{P}_2=\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& M_{32}& 0\\ 0& 0& 1& 0\\ 0& 0& M_{42}& 1\end{array}$

che non è più una matrice elementare di Gauss.

In ogni caso, la moltiplicazione per $P_2$ non è più un'operazione ammissibile nell'eliminazione di Gauss al passo $k=2$, perché si può operare solo nella sottomatrice $2\times 2$ in basso a destra, quindi non ci sono problemi.

Fattorizzazione

Dato il sistema $A𝒙=𝒃$, moltiplichiamo per $P$ ambo i membri per far comparire la matrice di permutazione, e otteniamo:

$PA𝒙=P𝒃$

$PA=LU⟶LU𝒙=P𝒃$

Allora bisogna considerare il termine noto permutato $\overline{𝒃}$, e risolviamo prima il sistema lineare

$L𝒚=\overline{𝒃}$

e poi

$U𝒙=𝒚$

Effetti del pivot parziale

Il pivot parziale ha un effetto stabilizzante, ovvero riduce l'errore algoritmico. In particolare:

1. Come prima, $L$ è una matrice triangolare inferiore con 1 sulla diagonale principale e $M_{ik}$ nella parte inferiore.

2. I moltiplicatori hanno espressione

$M_{ik}=\frac{|A_{ik}|}{{max}_{j=k}^n|A_{jk}|}$

quindi, per ogni $i=k+1,\dots ,n$ i coefficienti sono $\le 1$.

3. La crescita degli elementi di $U$ è limitata, infatti i coefficienti della "nuova" matrice sono:

$A_{ij}^{(k+1)}=A_{ij}^{(k)}-M_{ik}{A}_{kj}^{(k)}$

mentre per $i,j=1,\dots k$ gli elementi della matrice rimangono invariati, e quindi

$A_{ij}^{(k+1)}=A_{ij}^{(k)}$

in definitiva

$|A_{ij}{|}^{(k+1)}\le |A_{ij}{|}^{(k)}+|M_{ik}||A_{kj}{|}^{(k)}\le |A_{ij}|+|A_{kj}|$

Chiamiamo $A_m^{(k)}$ il massimo modulo degli elementi della matrice $A^{(k)}$. Allora, passando ai massimi nella disuguaglianza sopra,

$|A_m^{(k+1)}|\le |A_m^{(k)}|+|A_m^{(k)}|=2|A_m^{(k)}|$

e applicando a ritroso la relazione

$|A_m{|}^{(n)}\le 2^{n-1}|A_m^{(1)}|$

Errore algoritmico

Teorema 2.7

Sia $A\in {ℂ}_{n,n}$ tale che i suoi elementi siano numeri macchina (focus sull'errore algoritmico). Chiamiamo $\overline{L},\overline{U}$ le matrici effettivamente calcolate, allora $\overline{L}\ast \overline{U}=A+{\delta }_A$ dove vale la relazione

$|{\delta }_A|\le 2nu(|A|+|\overline{L}|\ast |\overline{U}|)+O(u^2)$

(a livello notazionale, chiamiamo $|B|$ la matrice che ha come componenti i moduli degli elementi di $B$)

In questa relazione, oltre alla dipendenza dalla dimensione, da $A$ e dalla precisione di macchina, il fatto significativo è che compaiono $\overline{L},\overline{U}$.

Teorema 2.8

Siano $A,B\in {ℂ}_{n,n}$ e, considerando $\overline{L},\overline{U}$ effettivamente calcolate, chiamiamo $\overline{𝒚}$ la soluzione del sistema $\overline{L}𝒚=𝒃$ e $\overline{𝒙}$ soluzione di $\overline{U}𝒙=𝒚$. Allora $\overline{𝒙}$ è la soluzione di

$(A+{\delta }_A)\overline{𝒙}=𝒃$

con

${\delta }_A\le 4nu(|A|+|\overline{L}||\overline{U}|+o(u^2))$

(interpretiamo l'errore algoritmico come errore inerente del problema perturbato)

Esempio 2.7

Consideriamo la matrice

$A=\left(\begin{array}{cc}\epsilon & 1\\ 1& 0\end{array}\right)$

$𝒃=(1+\epsilon ,1)$

dove $\epsilon$ è scelto in modo che la soluzione del sistema lineare $A𝒙=𝒃$ sia $(1,1)$. Il problema è ben condizionato, infatti

$A^{-1}=\begin{array}{cc}0& 1\\ 1& -\epsilon \end{array}$

$K(A)=|A{|}_{\mathrm{\infty }}\ast |A^{-1}{|}_{\mathrm{\infty }}=(1+\epsilon {)}^2$

e quindi se $\epsilon$ è piccolo, $K(A)\simeq 1$.

Per quanto riguarda la stabilità, senza tecnica del pivot:

$L=\begin{array}{cc}1& 0\\ 1/\epsilon & 1\end{array}$

$U=\begin{array}{cc}\epsilon & 1\\ 0& -1/\epsilon \end{array}$

$\overline{𝒙}=(0,1)$

mentre la soluzione esatta ha entrambe le componenti uguali a 1, e il problema è dato dalla crescita dei coefficienti di $U$.

Tecnica del pivot totale

Per ogni passo $k$, cerchiamo $\overline{i},\overline{j}$ tale che

$|A_{\overline{i},\overline{j}}|={max}_{i,j=k}^n|A_{i,j}|$

assumiamo di poter fare permutazioni di colonne ${\hat{P}}_k$ oltre che permutazioni di righe $P_k$.

Il problema che sorge è che, facendo permutazioni di colonne, si permuta l'ordine delle incognite.

Esempio 2.8

Nella catena di moltiplicazioni di matrici elementari, nel caso $n=4$,

$U=M_3{P}_3{M}_2{P}_2{M}_1{P}_{1}A{\hat{P}}_1{\hat{P}}_2{\hat{P}}_3$

ma poniamo ${\hat{P}}_1{\hat{P}}_2{\hat{P}}_3=\hat{P}$. L'altro pezzo di $U$ viene trattato come prima.

Come prima

$PA\hat{P}=LU$

e per risolvere il sistema $A𝒙=𝒃$ permutiamo a sinistra,

$PA𝒙=P𝒃$

bisogna inserire la $\hat{P}$, allora poniamo $\hat{P}𝒛=𝒙$

$PA\hat{P}𝒛=P𝒃$

Calcoliamo $\overline{𝒃}$ permutazione del termine noto, e risolviamo quindi:

$L𝒚=\overline{𝒃}$

$U𝒛=𝒚$

$\hat{P}𝒛=𝒙,\text{è una moltiplicazione matrice per vettore}$

Questo procedimento ha un effetto più stabilizzante rispetto al pivot parziale, infatti si ha:

$A_k\le \sqrt{k\prod _{j=2}^n{j}^{j-1}}$

e non sono state trovate matrici per cui vale l'uguaglianza.

Costo computazionale

La risoluzione forward o backward, considerando il numero di operazioni moltiplicative, ha come costo computazionale

$\sum _{i=1}^{n}i$

infatti, per ogni incognita, si ha l'espressione

$x_i=\frac{b_i-\sum _{j=1}^{i-1}{a}_{ij}{x}_j}{a_{ii}}$

Invece la fattorizzazione $LU$ ha costo

$\sum _{k=1}^{n-1}[(\sum _{i=k+1}^{n}1)+\sum _{i=k+1}^n\sum _{j=k+1}^{n}1]$

che è dell'ordine di $n^3/3$ (il primo addendo serve per il calcolo dei moltiplicatori, e il secondo per il calcolo del blocco quadrato in basso a destra).