Ciao a tutti! Oggi ci immergeremo in un concetto matematico potente e sorprendentemente accessibile: la formula di Sherman-Morrison. Questo strumento davvero utile ed efficiente per calcolare l’inversa di una matrice a cui viene aggiunta una perturbazione. Sia che tu stia lavorando su problemi di algebra lineare, ottimizzazione o qualsiasi altro campo che richieda la manipolazione di matrici, la formula di Sherman-Morrison è qualcosa che ti farà risparmiare tempo e fatica.
Se invece di leggere, preferisci guardare un video sull’argomento, puoi trovarlo qui:
Introduzione alla formula di Sherman-Morrison
Consideriamo una matrice $A\in\mathbb{R}^{n\times n}$ che supponiamo essere invertibile, ovvero supponiamo che ammetta una matrice inversa $A^{-1}\in\mathbb{R}^{n\times n}$. Introduciamo poi due vettori colonna generici $u,v\in\mathbb{R}^n$. Allora, definita la matrice $M=A+uv^T$, e supposta essere questa invertibile, la formula di Sherman-Morrison dice che
$ M^{-1} = A^{-1} – \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}=:B$.
Per cercare di essere abbastanza conciso, ho deciso di lasciare come esercizio la dimostrazione del fatto che $M$ è invertibile se e solo se $1+v^TA^{-1}u\neq 0$. Ciò ci garantisce che le ipotesi di partenza rendano ben definita la matrice $B$.
Nelle due prossime sezioni andremo a dimostrarla per via diretta, ovvero verificando che
$M^{-1}B=BM^{-1}=I_n,$
dove $I_n\in\mathbb{R}^{n\times n}$ è la matrice identità. Ciò corrisponde al dire che $B$ è effettivamente l’inversa destra e sinistra di $M$.
Prima di procedere con la dimostrazione, però, ci tengo a sottolineare l’importanza di questa formula. La matrice $uv^T$ è una matrice di rango 1 (se non sai il perché qui trovi un video in cui lo spiego : Proprietà della matrice $uv^T$). Allo stesso modo, dato che
$\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u} = \frac{(A^{-1}u)(v^TA^{-1})}{1+v^TA^{-1}u} = \frac{(A^{-1}u)(A^{-T}v)}{1+v^TA^{-1}u},$
anche la matrice che aggiungiamo ad $A^{-1}$ è di rango 1. Questa formula quindi ci dice in particolare che l’inversa di una perturbazione additiva di rango 1 della matrice $A$, sarà a sua volta una perturbazione additiva di rango 1 della matrice $A^{-1}$. Questo risultato si può estendere a perturbazioni di generico rango $r$, ma magari di questo ne possiamo parlare più avanti.
Prima parte della dimostrazione
Ora verifichiamo che $BM=I_n$, e lo facciamo procedendo con la seguente derivazione:
$B(A + uv^T) = \left[ A^{-1} – \frac{A^{-1} uv^T A^{-1}}{1 + v^T A^{-1} u} \right](A + uv^T) $
$= I_n – \frac{A^{-1} uv^T}{1 + v^T A^{-1} u}+A^{-1}uv^T- \frac{A^{-1} uv^T A^{-1} uv^T}{1 + v^T A^{-1} u}$
Siccome $v^TA^{-1}u\in\mathbb{R}$, abbiamo che
$B(A+uv^T)= I_n – \frac{A^{-1} uv^T}{1 + v^T A^{-1} u}+A^{-1}uv^T- \frac{v^T A^{-1} u}{1 + v^T A^{-1} u}A^{-1} uv^T$
$= I_n + \frac{A^{-1}uv^T}{1+v^TA^{-1}u}\left(-1+1+v^TA^{-1}u-v^TA^{-1}u\right)=I_n$,
come volevamo dimostrare.
Seconda parte della dimostrazione
Per concludere, verifichiamo che $MB=I_n$, e procediamo ancora per derivazioni dirette:
$(A+uv^T)B = (A+uv^T)\left[ A^{-1} – \frac{A^{-1} uv^T A^{-1}}{1 + v^T A^{-1} u} \right] $
$= I_n + uv^TA^{-1}-\frac{uv^TA^{-1}+uv^TA^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}$
$=I_n + uv^TA^{-1}-\frac{uv^TA^{-1}\left(1+uv^TA^{-1}\right)}{1+v^TA^{-1}u}$
$=I_n + \frac{uv^TA^{-1}}{1+v^TA^{-1}u}\left(1+v^TA^{-1}u-1-uv^TA^{-1}\right) = I_n$
$\blacksquare$
Con ciò possiamo concludere questa semplice dimostrazione. Se ti interessa vederne una più informativa e meno diretta, fammelo sapere con un commento.
Caso particolare della formula di Sherman-Morrison
Per fissare un po’ il ragionamento, credo possa essere parecchio utile concentrarci un attimo sul caso $A=I_n$, dato che in questa circostanza la formula si semplifica parecchio. Inoltre, questo è un caso che si presenta abbastanza spesso in vari contesti.
Quando $A=I_n$, abbiamo anche che $A^{-1}=I_n$, da cui segue
$B = M^{-1} = I_n – \frac{uv^T}{1+u^Tv},$
che come vedi è una formula molto molto semplice che ci permette di calcolare l’inversa di una matrice potenzialmente densa e complicata da invertire a priori.
Esempio
Ora, per finire, ti mostro un esempio in cui questa formula è applicata ad una matrice di dimensione $50\times 50$. Credo sia interessante confrontare i tempi per invertirla usando le routine di Python, e la formula di Sherman-Morrison, così da poter apprezzarne l’efficacia ed efficienza.
Se ti va di giocare con il codice, puoi aprirlo tranquillamente in Google Colab ed interagirvi ✌🏻 : https://colab.research.google.com/drive/1VkHD1LJKPxjpOtUtg_nyMHSCPkphAxpp?usp=sharing
Conclusione
Con ciò direi che possiamo chiudere questo breve (ma intenso) articolo. Se hai domande scrivi pure nei commenti, e ovviamente anche i suggerimenti per nuovi contenuti sono ben accetti!
Lascia un commento