Calcolo di $A^{-1}$ con fattorizzazione LU

Si considerino $k$ sistemi con matrice $A$ e termine noto $b^{(i)}$:

$$Ax^{(i)} = b^{(i)} \qquad 1 \leq i \leq k$$

Per risolverli il modo ingenuo può essere, con costo $O(n^3) \cdot k$:

$$[A\vert b^{(i)}] \overset{MEG}{\to} [U\vert\beta] \overset{\text{sost. indietro}}{\to} x^{(i)}$$

Non è però il metodo più intelligente per procedere.

Ricordiamo:

$$A \overset{MEG}{\to} U \Rightarrow PA = LU$$

Allora possiamo riscrivere i sistemi come coppie di sistemi triangolari:

$$\begin{cases}Ly^{(i)} = Pb^{(i)} \\ Ux^{(i)} = y^{(i)} \end{cases} 1 \le i \le k$$

Con $k$ significativi il costo è vantaggioso:

$$C = \underbrace{O(n^3)}_{\text{Calcola una sola volta L, U}} + \u... ...ace{k \cdot O(n^2)}_{k \text{ risoluzioni di sistemi con matrici triangolari}}$$

Consideriamo una base $B$:

$$B \in \mathbb{R}^{m\times n} \alpha \in \mathbb{R}^n$$

È notorialmente possibile rappresentare qualunque vettore $v$ dato come:

$$v = Bc = \alpha_1 C_1 + \alpha_2 C_2 + \ldots + \alpha_nC_n \qquad c_i \in \mathbb{R}^n, c = \textit{col}_i(B)$$

Definiamo $e^{(i)}$ come elemento $i$-esimo della base canonica:

$$e^{(i)} = \begin{pmatrix}0\\ 0\\ \vdots\\ 1\\ \vdots\\ 0\\ 0\\ \end{pmatrix}$$

Dunque $Be^{(i)} = \textit{col}_i(B)$.

Osserviamo che data una matrice $A$ invertibile vale allora:

$$A^{-1}e^{(i)}= col_i(A^{-1})$$   per $$m = n$$

Moltiplicando a sinistra entrambi gli elementi per la matrice $A$:

$$\underbrace{A A^{-1}}_{I} e^{(i)} = A \textit{col}_i (A^{-1}) \qquad 1 \le i \le n$$

Poichè:

$$A^{-1} = [ \textit{col}_1(A^{-1}), \textit{col}_2(A^{-1}), \ldots, \textit{col}_n(A^{-1})$$

Allora è possibile riformulare il problema come:

$$[A \vert e^{(i)} ] \overset{MEG}{\to} [U \vert \beta^{(i)}]$$

$$\begin{cases}Ly^{(i)} = Pe^{(i)} \\ U col_i(A) = y^{(i)} \end{cases}$$