Teoremi di Calcolo Numerico

uni

Algebra

Algebra Lineare, no dim

$$\begin{array}{c}A\text{ e }{A}^T\text{sono simili}\\ A=A^H\text{Hermitiana}\\ A{A}^H=A^{H}A\text{Normale}\\ A{A}^H=A^{H}A=I\text{Unitaria}\\ A^T=A^{-1}\text{Ortogonale}:\det (A)=\pm 1,\text{unitaria}\\ \text{Simili}⟺\text{stesso polinomio caratteristico}\\ Av=\lambda v,(A-\lambda I)v=0\\ w^{T}A=w^T\lambda ,w^T(A-\lambda I)=(A-\lambda I{)}^{T}w=0\\ A\text{ Simmetrica}⟹v=w\\ ||A|{|}_1={\max }_i{\sum }_j|A_{ji}|\text{max somma valori colonne}\\ ||A|{|}_{\infty }={\max }_i{\sum }_j|A_{ij}|\text{max somma valori righe}\\ ||v|{|}_2=\sqrt{\sum |v_i{|}^2}\\ ||A|{|}_2=\sqrt{\rho (A{A}^H)}\\ ||A|{|}_F=\sqrt{{\sum }_{i,j}|A_{ij}{|}^2}\end{array}$$

Teorema di diagonalizzabilità, no dim

A è diagonalizzabile se e solo se la molteplicità algebrica è uguale alla molteplicità geometrica per ogni autovalore.

Teorema Binett Cauchy, no dim

con $A\in C^{n\times m}\cdot B\in C^{m\times n}$:

$$\det (AB)=\{\begin{array}{ll}0,& m>n\\ \det (A)\cdot \det (B),& m=n\\ \ast ,& m\le n\end{array}$$

$\ast$: dato dalla somma tra il prodotto tra tutti i minori di ordine massimo ($m$) di $A$ e tra il prodotto tra tutti i minori di ordine massimo ($m$) di $B$.

Teorema Rouché-Capelli, no dim

Un sistema $A^{m\times n}x=b$ ammette almeno una soluzione se $\text{rank}(A)=\text{rank}(A|B)$, in particolare ammette una unica soluzione se $\text{rank}(A)=n$ (rango pari al numero di incognite), infinite soluzioni altrimenti.

Teorema Spettrale, no dim

data una matrice hermitiana $A=A^H\in {\mathbb{C}}^{n\times n}$, essa rispetta:

1. $A$ è diagonalizzabile
2. $A$ ha autovalori reali
3. è possibile scegliere una base di autovettori che sia unitaria (o ortonormale nel caso reale). Ovvero esiste una matrice $V$ unitaria ($V{V}^H=V^{H}V=I$) tale che $V^{H}AV=\text{diag}\{{\lambda }_1,...,{\lambda }_n\}$

Teorema equivalenza norme, no dim

Date due norme vettoriali generiche $||x|{|}_p$ e $||x|{|}_q$​, esistono sempre due costanti reali e positive $\alpha$ e $\beta$ tali che per ogni vettore $x$ valga la seguente doppia disuguaglianza:

$$\alpha ||x|{|}_p\le ||x|{|}_q\le \beta ||x|{|}_p,\forall x\in {\mathbb{C}}^n$$

quindi per esempio se una successione converge ad un limite in una determinata norma, essa convergerà allo stesso limite in qualsiasi altra norma equivalente.

Teorema di Hirsch, no dim

$$\rho (A)\le ||A||$$

rispetto ad una qualsiasi norma $||\cdot ||$.

1º Teorema di Gershgorin

Ogni autovalore di una matrice appartiene all’unione dei suoi dischi di Gershgorin.

2º Teorema di Gershgorin, no dim

Se ci sono $N$ dischi con intersezione non vuota, l’unione tra questi $N$ dischi contiene $N$ autovalori.

3º Teorema di Gershgorin, no dim

In una matrice irriducibile se un autovalore si trova sul bordo dell’unione di tutti i dischi, si trova sul bordo di ogni singolo disco.

Corollari dei teoremi di Gershgorin, no dim

• $A$ e $A^T$ hanno gli stessi autovalori, si può quindi prendere come regione dove stanno gli autovalori l’intersezione dell’unione dei loro dischi di gershgorin
• se una matrice è a predominanza diagonale forte allora è non singolare
• se la matrice è a predonominanza diagonale debole ed è irriducibile, allora è non singolare
• in una matrice reale, se un disco contiene un autovalore complesso, deve anche contenere il suo coniugato → un disco isolato di una matrice reale non può contenere autovalori complessi
• se una matrice ha tutti i dischi disgiunti, allora ha tutti autovalori distinti, quindi è diagonalizzabile.

Teorema di Riducibilità

Una matrice è riducibile (per permutazione) se e solo se il suo grafo associato non è fortemente connesso.
Un grafo è fortemente connesso se e solo se da ogni suo nodo è possibile raggiungere qualsiasi altro nodo seguendo un cammino orientato.

Calcolo Numerico

Misc

Formula di Taylor, no dim

Data $f:\mathbb{R}\to \mathbb{R},f\in {\mathbb{C}}^1$, allora dato $x_0\in \mathbb{R}$:

$$f(x)=\sum _{n=0}^k\frac{f^{(n)}(x_0)}{n!}(x-x_0{)}^n+\underset{{ϵ}_l:\text{Errore di Lagrange}}{\underbrace{\frac{f^{(k+1)}(\xi )}{(k+1)!}(x-x_0{)}^{(k+1)}}}$$

con ${ϵ}_l$ Errore di Lagrange al k-esimo grado, con $\xi \in [x_0,x]$ punto di massimo della derivata $k+1$-esima: $\xi ={\text{argmax}}_{x\in [x_0,\overline{x}]}{f}^{(k+1)}(\overline{x})$.

Teorema della rappresentazione, no dim

La rappresentazione in virgola mobile è unica se:

$$\begin{array}{c}\text{dati}\beta \in N,\beta >1,x\in R\text{e}x\ne 0\\ \text{Allora}\exists \text{ed eˋ unica la rappresentazione:}\\ x=\text{segno}(x)\cdot {\beta }^e\cdot {\sum }_{j=1}^{\infty }{\alpha }_j\cdot {\beta }^{-j}\text{tale che}\\ 1.{\alpha }_i\ne 0\\ 2.\nexists k\in N:{\alpha }_j=\beta -1\forall j>k\end{array}$$

Teorema di Condizionamento, no dim

Teorema per la maggiorazione dell’errore inerente relativo sulla soluzione $x$ di un sistema lineare $Ax=b$.

Sia $x$ la soluzione esatta del sistema $Ax=b$, sia la matrice perturbata $A+\delta A$ non singolare, allora vale:

$${ϵ}_{\delta }=\frac{||\delta x||}{||x||}\le \frac{\mu (A)}{1-\mu (A)\frac{||\delta A||}{||A||}}\left(\frac{||\delta A||}{||A||}+\frac{||\delta b||}{||b||}\right)$$

caso semplificato, perturbazione solo su $b$:

$${ϵ}_{\delta }=\frac{||\delta x||}{||x||}\le \mu (A)\frac{||\delta b||}{||b||}$$

Sistemi lineari

Teorema di convergenza dei metodi iterativi di punto fisso, no dim

Un metodo iterativo di punto fisso converge per ogni vettore $x^{(0)}$ se e solo se la sua matrice di iterazione $B$ è convergente, ovvero ha raggio spettrale minore di $1$.

Teorema di convergenza di Jacobi e Gauss Seidel

Il metodo di Jacobi e il metodo di Gauss Seidel risultano convergenti se la matrice $A$ del sistema è a predominanza diagonale forte, oppure se è a predominanza diagonale debole ed irriducibile.

Teorema di convergenza di Jacobi e Gauss-Seidel con matrice tridiagonale, no dim

Se A è una matrice tridiagonale e se è diagonalmente dominante forte oppure se è diagonalmente dominante debole ed irriducibile (ogni elemento sulle codiagonali è diverso da 0), allora i metodi di Jacobi e Gauss-Seidel convergono e vale:

$$\rho (H_{GS})={\rho }^2(H_J)$$

quindi Gauss Seidel converge più velocemente di Jacobi.

Sistemi rettangolari

Teorema di esistenza e unicità delle soluzione delle equazioni normali

Il sistema delle equazioni normali $A^{H}Ax=A^{H}b$ ha sempre soluzione, la soluzione è unica se e solo se $A$ ha rango massimo.

Teorema di esistenza della fattorizzazione QR, no dim

Per ogni matrice esiste sempre una fattorizzazione QR, ma non è mai unica.

Interpolazione

Teorema determinante della matrice di Vandermonde, no dim

Il determinante della matrice di Vandermonde è:

$$\det (V)=\prod _{0\le i<j\le k}(x_j-x_i)$$

con $k$ grado del polinomio. Quindi se $x_i\ne x_j\forall i\ne j$ allora il determinante è diverso da zero.

Teorema di esistenza ed unicità del polinomio interpolante

Dati $k+1$ punti reali distinti $(x_i,y_i)$, esiste è ed unico il polinomio $P_k(x)$ di grado al più $k$ che vale $P_k(x_i)=y_i\forall i=0,1,\dots ,k$.

Teorema di errore di interpolazione polinomiale, no dim

Presi i $k+1$ punti $x_0,\dots ,x_k$ diversi tra loro, sia $f:\mathbb{R}\to \mathbb{R},f\in C^{k+1}(I)$ con $I$ intorno contenente i punti $x_i$. Se $p_k(x)$ è un polinomio di grado al più $k$ che interpola i punti $(x_i,f(x_i))$, allor vale:

$$\text{errore}=f(x)-p_k(x)=\frac{f^{(k+1)}(\xi )}{(k+1)!}\prod _{j=0}^k(x-x_j)$$

per un certo $\xi$ compreso tra il minimo ed il massimo punto dato $x_i$.

Teorema di Faber, no dim

Non esiste alcuna scelta dei nodi di interpolazione che garantisca la convergenza dell’interpolazione polinomiale per tutte le funzioni continue.

Qualunque sia il metodo con cui scegli i nodi, si può sempre trovare una funzione continua per cui l’interpolazione polinomiale fallisce.

Integrazione

Teorema di unicità della formula Gaussiana, no dim

Il sistema non lineare:

$$\{\begin{array}{l}{a}_0+a_1+\cdots +a_n=m_0\\ a_0{x}_0+\dots a_n{x}_n=m_1\\ ⋮\\ a_0{x}_0^{2n+1}+\cdots +a_n{x}_n^{2n+1}=m_{2n+1}\end{array}$$

ammette sempre un’unica soluzione per ogni scelta di $[a,b],n,\rho (x)$, e l’unica formula di quadratura che verifica questo sistema si dice formula Gaussiana, e ha grado di precisione $2n+1$ su $n+1$ nodi.

Teorema di Peano, no dim

Data una funzione derivabile $n+1$ volte ($f(x)\in C^{n+1}$), con $m$ grado di precisione della formula di quadratura $J_n$, allora l’errore $E_n$ si può scrivere come:

$$E_n(f)=I(\rho ,f)-J_n(f)=\frac{1}{m!}{\int }_a^b{f}^{(m+1)}(t)\cdot G(t)dt$$

dove $G(t)$ è detto Nucleo di Peano e vale:

$$G(t)=E_n(s_m(x-t))=I(\rho \cdot s_m(x-t))-J_n(s_m(x-t))$$

e la $s_m(x)$ è:

$$s_m(x)=\{\begin{array}{ll}{x}^m,& x>0\\ 0,& x\le 0\end{array}$$

Sistemi non lineari

Teorema di errore del metodo delle secanti, no dim

Se $f\in C^2([a,b])$ ammette radice, allora il metodo converge localmente con ordine:

$$p=\frac{1+\sqrt{5}}{2}>1$$

ovvero solitamente risulta in un errore migliore del lineare ma peggiore del quaddratico.

Teorema di convergenza locale

Se si ha un intervallo $I\subset R$, con $\alpha \in I$ e $\varphi (\alpha )=\alpha$ e $\varphi \in C^1(I)$ ed esiste $\rho \in {\mathbb{R}}^{+}$ tale che:

$$|{\varphi }^{\prime }(x)|<1,\ne 0\forall x\in [\alpha -\rho ,\alpha +\rho ]$$

Allora:

$$\begin{array}{cc}4.& \forall x_0\in [\alpha -\rho ,\alpha +\rho ]⟹x_n\in [\alpha -\rho ,\alpha +\rho ]\\ 5.& \forall x_0\in [\alpha -\rho ,\alpha +\rho ]⟹{\lim }_{n\to +\infty }{x}_n=\alpha \\ 6.& \alpha \text{ eˋ l’unico punto fisso di }\varphi (x)\text{ in }[\alpha -\rho ,\alpha +\rho ]\end{array}$$

Teorema di convergenza superlineare

La successione $\{x_n\}$ converge con ordine $p\ge 1$ ad $\alpha$ se è solo se vale:

$${\varphi }^{\prime }(\alpha )={\varphi }^{\prime \prime }(\alpha )=...={\varphi }^{(p-1)}(\alpha )=0,{\varphi }^p(\alpha )\ne 0$$

Teorema di convergenza in un intervallo, no dim

Se $\varphi (x)\in C^1([a,b])$ e:

$$\begin{array}{cc}7.& |{\varphi }^{\prime }(x)|<1,\forall x\in [a,b]\\ 8.& \varphi (x)\in [a,b],\forall x\in [a,b]\end{array}$$

allora $\varphi (x)$ converge su $[a,b]$.

Teorema convergenza locale superlineare di Newton

Se $\alpha$ è radice semplice e $f\in C^2([a,b])$ allora il metodo di Newton converge localmente con ordine $p\ge 2$.
In particolare se $f^{\prime \prime }(\alpha )\ne 0⟹p=2$, altrimenti se $f^{\prime \prime }(\alpha )=0⟹p>2$.

Teorema di convergenza globale per Newton (tramite studio della concavità), no dim

Se $\alpha \in [a,b]$ è radice semplice di $f\in C^2([a,b])$ e $f,f^{\prime \prime }$ sono di segno costante su $[a,b]$, il metodo di Newton converge globalmente in maniera superlineare ($p\ge 2$) $\forall x_0$ che verifica $f(x_o)\cdot f^{\prime \prime }(x_0)>0$.

Teorema convergenza locale multivariabile ( ${\mathbb{R}}^m$), no dim

TLDR: un metodo iterativo multivariabile converge ad $\alpha$ radice se $\rho (J_{\varphi }(\alpha ))<1$, se il raggio spettrale è 0 converge superlinearmente.

Sia $\varphi (x)$ continua in un intorno $\Omega \subset {\mathbb{R}}^m$ con $\alpha \in \Omega$ tale che $\varphi (\alpha )=\alpha$, se:

$$\rho (J_{\varphi }(\alpha ))<1$$

allora $\exists \delta >0$ tale che $\forall x^{(0)}:|x^{(0)}-\alpha {|}_2<\delta$ in cui la successione $x^{(n+1)}=\varphi (x^{(n)})$ converge ad $\alpha$, ed $\alpha$ è l’unico punto fisso di $\varphi$ in $\{z\in {\mathbb{R}}^m:|z-\alpha {|}_2<\delta \}$.

Ovvero se per una qualsiasi norma si trova $|J_{\varphi }(\alpha )|<1$ allora il metodo converge localmente.

se $\rho (J_{\varphi }(\alpha ))=0$ il metodo converge superlinearmente ($p\ge 2$).

Teorema convergenza locale del metodo di Newton-Raphson, no dim

Se $J_f(\alpha )$ è non singolare, allora esiste un intorno di $\alpha$ tale che per ogni $x^{(0)}$ nell’intorno la successione generata dal metodo a partire da $x^{(0)}$ converge superlinearmente, poiché vale:

$$|x^{(n+1)}-\alpha {|}_2\le \beta |x^{(n)}-\alpha {|}_2^2$$

Autovalori

Teorema della convergenza del metodo delle potenze, dimostrazione per matrici hermitiane

data $A=A^H\in {\mathbb{C}}^{n\times n}$ hermitiana (quindi diagonalizzabile) con autovalori: $|{\lambda }_1|>|{\lambda }_2|\ge |{\lambda }_3|\ge ...\ge |{\lambda }_n|>0$ e consideriamo la successione:

$$\{\begin{array}{l}{z}^{(0)}=z\\ z^{(k+1)}=A{z}^{(k)}=A^{k+1}{z}^{(0)}=A^{k+1}z\end{array}$$

se $h\in \{1,...,n\}:v_h^{(1)}\ne 0$ e $z^{(0)}\in {\mathbb{C}}^n$ è tale che:

$${\left[V^{(1)}\right]}^H{z}^{(0)}\ne 0\text{(non ortogonali)}$$

allora la successione è tale che:

$$\underset{k\to +\infty }{\lim }\frac{z^{(k)}}{z_h^{(k)}}={\tilde{v}}^{(1)}$$

e per l’autovalore vale:

$$\underset{k\to +\infty }{\lim }\frac{{\left[z^{(k)}\right]}^{H}A{z}^{(k)}}{{\left[z^{(k)}\right]}^H{z}^{(k)}}={\lambda }_1$$

Teorema di validità del metodo QR per gli autovalori, no dim

Metodo QR: $A_{k+1}=Q_k^H{A}_k{Q}_k$.
Presa $A\in R^{n\times n}$ e supposto $|{\lambda }_1|<|{\lambda }_2|<...<|{\lambda }_n|$ allora:

$$\underset{n\to \infty }{\lim }{A}_k=T=\left(\begin{array}{ccc}{t}_{11}& ...& t_{1n}\\ & \ddots & ⋮\\ 0& & t_{nn}\end{array}\right)$$

dove i blocchi $T_{jj}$ sono $1\times 1$ per autovalori reali e $2\times 2$ per autovalori complessi coniugati.