# Formulario Calcolo Numerico

## Rappresentazione in macchina

### Insieme dei numeri di macchina
$$
\mathbb{F} = \mathbb{F}(B, t, m, M)
$$
dove $B$ è la base, $t$ è il numero di cifre, $m$ e $M$ rappresentano il range: da -$m$ a $M$ per l'esponente della base

#### Precisione di macchina
$$
u = B^{1-t}
$$

#### Minimo numero positivo
$$
\omega = B^{-m-1}
$$

#### Massimo numero positivo
$$
\Omega = B^{M(1-B^{-t})}
$$

#### Cardinalità insieme dei numeri di macchina
$$
N = 2B^{t-1}(B-1)(M+m+1)+1
$$

#### Appartenenza all'insieme
$$
\omega \le |x| \le \Omega
$$
nota che abbiamo anche i casi particolari gestiti separatamente di $0$, $+\infty$, $-\infty$, $NaN$
abbiamo anche i casi di overflow e underflow:
- Underflow:
$$
|x|<\omega
$$
- Overflow:
$$
|x|>\Omega
$$

## Analisi degli errori

### Errore inerente
#### Formula generale
$$
\epsilon_{in} = \frac{ f(\widetilde{x}) - f(x) } { f(x) }
$$

#### Formula con coefficiente
Se f(x) è derivabile due volte
$$
\epsilon_{in} = c_x\epsilon_x \\
c_x \doteq \frac{f'(x)}{f(x)}x
$$
#### Formula coefficiente a più variabili
$$
\epsilon_{in} = \sum_{i=1}^n c_{x_i}\epsilon_{x_i} \\
c_{x_i} \doteq \frac{1}{f(x)}\frac{\partial f}{\partial x_i}x_i
$$

### Errore algoritmico

#### Errori inerenti alle operazioni di macchina
- Somma
$$
f(x, y) = x+y \quad \epsilon_{in} \doteq c_x\epsilon_x + c_y\epsilon_y \\
c_x = \frac{x}{x+y}, \quad c_y = \frac{y}{x+y}
$$
- Differenza
$$
f(x, y) = x-y \quad \epsilon_{in} \doteq c_x\epsilon_x + c_y\epsilon_y \\
c_x = \frac{x}{x-y}, \quad c_y = \frac{-y}{x-y}
$$
- Moltiplicazione
$$
f(x, y) = x\cdot y \quad \epsilon_{in} \doteq c_x\epsilon_x + c_y\epsilon_y \\
c_x = 1, \quad c_y = 1
$$
- Divisione
$$
f(x, y) = x / y \quad \epsilon_{in} \doteq c_x\epsilon_x + c_y\epsilon_y \\
c_x = 1, \quad c_y = -1
$$

#### Creazione del grafo
Si considera la sequenza di operazioni (eventualmente in parallelo) previste dall'algoritmo dato. Si creano una serie di variabili che rappresentano i risultati intermedi. Partendo dalle variabili di input si fa l'albero delle operazioni (ogni nodo è una soluzione di una singola operazione). Sugli archi di indicano i coefficienti di amplificazione inerenti alle singole operazioni. Quindi si parte dalla soluzione finale, e si somma l'errore locale dell'operazione con il coefficiente di amplificazione indicato sull'arco per tutto ciò che lo precede. Si maggiora tutte le espilon con u e si trova quando diverge o quando è troppo grande per vedere se è stabile.

## Invertibilità matrice
* #### Matrice predominante diagonale
Se la matrice ha la diagonale in modulo maggione della somma dei moduli degli altri elementi sulla riga (predomaninante per righe) o sulla colonne (predominante per colonne). Nel caso non sia specificato si intende per righe, ma per quanto riguarda l'invertibilità basta una delle due.
* #### Determinante $\neq 0$
* #### $Ax = 0 \iff x = 0$
* #### Non ha autovettori $=0$
### Calcolo inversa
* #### Direttamente ponendo $AA^{-1} = I$
* #### Risolvendo le colonne con $Ax = e_j$ dove $e_j$ è il vettore con tutti $0$ eccetto un $1$ in posizione $j$

## Fattorizzazione LU
### Condizione sufficiente per l'eistenza e l'unicità della fattorizzazione LU
Se tutte le sottomatrici di testa sono invertibili allora esiste ed è unica la fattorizzazione LU
### Calcolo completo (condizione necessaria e sufficiente)
$$
\begin{bmatrix}
A_{n-1} & z \\
v^T & \alpha
\end{bmatrix} =
\begin{bmatrix}
L_{n-1} & 0 \\
x^T & 1
\end{bmatrix}
\begin{bmatrix}
U_{n-1} & y \\
0 & \beta
\end{bmatrix}
$$

$$
\begin{cases}
A_{n-1} = L_{n-1}U_{n-1} \\
z = L_{n-1}y \\
v^T = x^T U_{n-1} \\
\alpha = x^T y + \beta
\end{cases}
$$

## Determinante matrice
- #### Se è triangolare è la moltiplicazione degli elementi sulla diagonale
### Laplace
Fissata una riga $i$ di $A$
$$
detA = \sum_{j=1}^n (-1)^{i+j} * a_{ij} * detA_{ij}
$$
oppure
Fissata una colonna $j$ di $A$
$$
detA = \sum_{i=1}^n (-1)^{i+j} * a_{ij} * detA_{ij}
$$
### Fattorizzazione LU
Prendendo la fattorizzazione LU di A (se esiste) si ha che $detA = detU$

## Jacobi e Gauss-Seidel
- Jacobi prende la matrice $M$ con la diagonale di $A$
- Gauss-Seidel prende la matrice $M$ con la parte triangolare inferiore di $A$
- Il conto è $x^{k+1} = M^{-1}Nx^k + M^{-1}b = Px^k + q$
### Applicabilità del metodo $\iff M$ è invertibile
- In entrambi i casi vale se gli elementi sulla diagonale di $M$ sono diversi da $0$
### Convergenza
- #### Condizione sufficiente per la convergenza è che la matrice $P$ sia predominante diagonale
- #### Condizione sufficiente per la convergenza è che esista una norma matriciale indotta di $P$ che risulti $< 1$ (provare norma $1$ e $\infty$)
- #### Condizione necessaria e sufficiente per la convergenza è che la matrice $\rho(P)<1$ ovvero che il raggio spettrale della matrice sia minore di uno. Il raggio spettrale è il modulo dell'autovalore di modulo massimo. Per trovare gli autovalori si può anche risolvere $det(\lambda I - P)$

## Autovalori matrice
- #### Caso triangolare o diagonale
Se la matrice è triangolare o diagonale gli autovalori sono tutti e soli gli elementi sulla diagonale.
- #### Si calcola il $det(A-\lambda I)$ usando anche Laplace

- #### Si risolve il sistema $Ax = \lambda x$
- #### Si cera una fattorizzazione LU di $(A-\lambda I)$ e quindi $det(A-\lambda I) = det(U)$

## Metodo tangenti
- $f \in C^2([a, b])$
- $f(\alpha) = 0$
- $\alpha \in (a, b)$
$$
x_{k+1} = x_k - {f(x)\over f'(x)}
$$
### Localmente convergente
Si ha convergenza locale se $f'(\alpha) \neq 0$
e la convergenza è almeno quadratica:
$$
\lim_{k \rightarrow +\infty} {|x_{k+1}-\alpha| \over |x_k-\alpha|^2} = c\in \mathbb{R}
$$
### Convergenza in largo
Se possiamo trovare $\delta$ tale che valgono entrambe
- $f'(x) \neq 0$ nell'intervallo $(\alpha, \alpha + \delta]$
- $f(x)f''(x) > 0$

allora il metodo delle tangenti converge ad $\alpha$