Numerical Analysis

Rappresentazione in macchina

Un calcolatore può rappresentare solo un numero finito di cifre, ciò implica che i numeri reali introdotti nel calcolatore vengono approssimati così come vengono approssimati i risultati delle operazioni elementari su tali numeri.
Quindi quando eseguiamo un algoritmo su un calcolatore, si ha una generazione e propagazione di errori.
Per esaminare la generazione degli errori inerenti bisognare parlare di rappresentazione in base di un numero. Dato un intero $\beta>1$ (detto base della rappresentazione), un nnumero $x \in \mathbb{R}, x \neq 0$, si può scrivere/esprimere in modo univoco nella forma:
$x=segno(x)[d_1\beta^{-1}+d_2\beta^{-2}+...]\beta^p=\pm\beta^p\sum\limits_{i=1}^{+\infty}d_i\beta^{-1}$

$x=segno(x)=\begin{cases}1, & \mbox{if } x>0\\-1, & \mbox{if } x<0\end{cases}$
$p \in \mathbb{Z}$ detto caratteristica (o esponente) della rappresentazione di $x$.
$d_i \in \mathbb{Z}, i=1,2,...$, sono dette cifre della rappresentazione di $x$ e verificano le condizioni

$0 \leq d_i \leq \beta - 1, i=1,2,...$
$d_1 \neq 0$ e $d_i$ non sono mai definitivamente uguali a $\beta-1$

$x=\pm(.d_1d_2...)\beta^p$ $d_1 \neq 0 \rightarrow$ notazione normalizzata.

La normalizzazione oltre ad essere necessaria per l'unicità, si rivela vantaggiosa quando si rappresenta un numero solo con un numero finito di cifre.

Esempio:
$x=frac{1}{7000}$ può essere rappresentato in $\beta=10$ nei due modi seguenti:

$x_1=(.142857142857...)10^{-3}$ ovvero in rappresentazione normalizzata
$x_2=(.000142857142857...)$ rappresentazione non normalizzata.

per un numero massimo di $t=12$ cifre di mantissa

$x_1=(.142857142857...)10^{-3}$
$x_2=(.000142857142...)$

$\Rightarrow x_1$ è una rappresentazione di $x$ migliore di $x_2$ perché guadagno 3 numeri di mantissa. Ovvero fornisce un'approssimazione migliore di $x$ rispetto ad $x_2$, perché l'informazione che in $x_2$ è contenuta negli zeri viene spostata all'esponente.

Condizionamento di un problema

Stima degli errori sui dati input: quando si realizza una computazione per via automatica, qualunque metodo si usi, non si può prescindere dall'errore di rappresentazione dei dati (errore inerente) e dall'errore di arrotondamento sulle singole operazioni (errore algoritmico), che dipende dal metodo usato ed è indipendente dall'errore sui dati.
L'errore inerente da una stima della sensibilità della soluzione agli errori sui dati.

Un problema si dice malcondizionato se a "piccole" perturbazioni/errori sui dati iniziali corrispondono "grandi" perturbazioni sui dati finali. Viceversa si dice ben condizionato. Chiaramente i termini "piccole" e "grandi" dipendono dal contesto.

Matrici definite in segno

Sia $A \in \mathbb{R}^{nxn}$ una matrice simmetrica ($A=A^T, a_{ij}=a_{ji}$) e $x \in \mathbb{R}^n$, allora $\alpha = x^TAx$
$\alpha = x^TAx$ è uno scalare, cioè $\alpha \in \mathbb{R}$.

Se $A \in \mathbb{R}^{nxn}$ è una matrice simmetrica e $\forall x \in \mathbb{R}^n, x \neq 0$ il numero reale $\alpha = x^TAx$ mantiene lo stesso segno, la matrice $A$ si dice definita in segno.
In particolare:

se $\alpha = x^TAx > 0$, $A$ è detta definita positiva
se $\alpha = x^TAx \geq 0$, $A$ è detta semidefinita positiva
se $\alpha = x^TAx < 0$, $A$ è detta definita negativa
se $\alpha = x^TAx \leq 0$, $A$ è detta semidefinita negativa

Matrice a predominanza diagonale

Una matrice $A \in \mathbb{R}^{nxn}$ si dice:

a predominanza diagonale in senso stretto (o forte) per righe se:
$|a_{ii}|>\sum\limits_{j=1, i \neq j}^n|a_{ij}|, \forall i=1,...,n$
a predominanza diagonale debole per righe se:
$|a_{ii}|\geq \sum\limits_{j=1, i \neq j}^n|a_{ij}|, \forall i=1,...,n$
a predominanza diagonale in senso stretto per colonne se:
$|a_{jj}|> \sum\limits_{i=1, i \neq j}^n|a_{ij}|, \forall j=1,...,n$
a predominanza diagonale debole per colonne se:

Se $A$ è simmetrica $\Rightarrow$ pdf per righe $\equiv$ pdf per colonne
Se $A$ è a pdf per colonne $\Rightarrow$ nel procedimento di eliminazione di Gauss non è necessario fare pivoting parziale.
L'algoritmo di Gauss è sempre stabile.
Se $A$ è a pdf:

$A$ non è singolare, cioè $|A| \neq 0$
Tutti i minori principali di testa di $A$ sono non nulli
$A$ è fattorizzabile in forma LU

Fattorizzazioni di Matrici "Speciali"

pro:

rende più stabile l'algoritmo di fattorizzazione

contro:

modificare la struttura della matrice (ad esempio si può avere perdita di simmetria: una matrice simmetrica occupa memoria solo $\frac{n^2}{2}$ posizioni anziché $n^2$.

Ci chiediamo se esistono classi di matrici per cui la condizione di pivoting è automaticamente soddisfatta.

Sì, cioè:

Matrici a diagonale dominante (o "a predominanza diagonale",..)
Matrici simmetriche definite in segno

Metodi iterativi per sistemi lineari

Prerequisiti

Una matrice $A$ di ordine $n, n \geq 2$, si dice riducibile se $\exists$ una matrice di permutazione $P$ e un intero $k, 0<k<n$ tale che:

$ B=PAP^T = \left( \begin{array}{cc} A_{11} & A_{12} \\ 0 & A_{22} \end{array} \right)$ in cui $A_{11} \in \mathbb{R}^{kxk}$ e $A_{22} \in \mathbb{R}^{(n-k)x(n-k)}$
Se la matrice A non è riducibile allora si dice irriducibile.
N.B.: Se A è riducibile, possono esistere differenti matrici di permutazione $P$ che consentono di trasformare $A$ nella forma $B$.
$A = \left( \begin{array}{ccc} 1 & 3 & 0 \\ 0 & 2 & -1 \\ -1 & 0 & 2 \end{array} \right) n=3 \Rightarrow$ avremo un grafo con 3 nodi $P_1,P_2,P_3$. Se $a_{ij} \neq 0 \Rightarrow \exists$ un arco uscente da $P_i$ entrante in $P_j$. [! Aggiungere immagine grafo] [P1 .> P1; P1 .> P2; P2 .> P2; P2 .> P3; P3 .> P3; P3 .> P1] Per determinare se $A$ di ordine $n$ è riducibile si può usare il grafo orientato associato ad $A$, cioè un grafo che ha $n$ nodi $p_i , i=1,...,n$ e un arco orientato uscente da $P_i$ ed entrante in $P_j$ se $a_{ij} \neq 0, \forall i,k$
Se il nodo di arrivo di un arco è il nodo di partenza di un altro arco $\Rightarrow$ questi sono contigui.

Due archi di un grafo si dicono contigui se il nodo di arrivo del primo arco è anche il nodo di partenza del secondo arco.

Una successione di archi contigui si dice cammino orientato

Un grafo orientato si dice fortemente connesso se per ogni coppia di indici $(i,j), 1 \leq i,j \leq n, i \neq j$, esiste un cammino orientato che parte da $P_i$ e arriva in $P_j$

Una matrice $A$ è riducibile $\Leftrightarrow$ il suo grafo orientato NON è fortemente connesso.

se $A$ è irriducibile $\Rightarrow \exists$ un cammino orientato chiuso che tocca tutti i nodi

Metodo di Jacobi

Il metodo di Jacobi è anche detto "Metodo degli spostamenti simultanei", perché le componenti del vettore soluzione al passo k-esimo, $x^{(k)}$, sostituiscono simultaneamente, alla fine dell'iterata, le componenti del vettore soluzione al passo precedente, $x^{(k-1)}$. Inoltre il metodo di Jacobi risolve un sistema lineare, equivalente ad $Ax=b$, in cui la i-esima equazione, $i=1,...,m$ viene "isolata" l'incogninita i-esima, $i=1,...,n$
La matrice di iterazione di Jacobi è:
$B_j=M^{-1}N=D^{-1}(B+C) = \left( \begin{array}{ccccc} 0 & -\frac{a_{12}}{a_{11}} & -\frac{a_{13}}{a_{11}} & ... & -\frac{a_{1n}}{a_{11}} \\ -\frac{a_{21}}{a_{22}} & 0 & ... & ... & -\frac{a_{2n}}{a_{22}} \\ . & . & & & . \\ . & & . & & . \\ . & & & . & . \\ . & & & . & . \\ -\frac{a_{n1}}{a_{nn}} & -\frac{a_{n2}}{a_{nn}} & ... & ... & 0 \end{array} \right)$