$M = D-B$
$N = C$
$B_{GS} = M^{-1}N=(D-B)^{-1}C$
$d=M^{-1}b=(D-B)^{-1}b$
Poiché in generale, non è sempre agevole e può risultare computazionalmente oneroso valutare l'inversa della matrice $(D-B)$ per valutare la matrice di iterazione $B_{GS}=(D-B)^{-1}C$ conviene considerare la seguente forma equivalente:
$x^{(k)} = [(D-B)^{-1}C]x^{(k-1)}+b$
$Dx^{(k)}-Bx^{(k)}=Cx^{(k-1)}+b$
$Dx^{(k)}=Bx^{(k)}+Cx^{(k-1)}+b$
$x^{(k)}=D^{-1}Bx^{(k)}+D^{-1}Cx^{(k-1)}+D^{-1}b$ (molto simile a Jacobi)
Tale espressione può essere interpretata come l'iterazione di Jacobi nella quale allo step $k$-esimo, per calcolare la componente $x_i^{(k)}$ si usano le componenti già calcolate nello stesso step, $x_j^{(k)}, j=1,...,i-1$ e le componenti $x_j^{(k-1)}, j=i+1,...,n$ dello step precedente cioè il $(k-1)$-simo. Per tale motivo il metodo di Gauss-Seidel è detto "Metodo degli spostamenti successivi".
[... mancano i calcoli per ricavarsi le componenti ]
Quindi, in termini di componenti:
$x_i^{(k)} = \frac{1}{a_{ii}}[b_i-(\sum\limits_{j=1}^{i-1}a_{ij}x_j^{(k)}+\sum\limits_{j=i+1}^{n}a_{ij}x_j^{(k-1)})]$ per $i=1,2,...,n$ e $k=1,..,n$
Metodo di Cholesky
Se A è simmetrica e definita positiva esiste ed è unica la fattorizzazione $A=LL^T$ con $L$ matrice triangolare inferiore.
La tecnica compatta che va sotto il nome di Metodo di Cholesky, usa le seguenti relazioni per determinare gli elementi $l_{ij}$ della matrice $L$.
$j=1,2,...,n$ $\begin{cases}l_{jj}=\sqrt{a_{jj}-\sum\limits_{k=1}^{j-1}l_{jk}^2}, \\l_{ij}=\frac{1}{l_{jj}}[a_{ij}-\sum\limits_{k=1}^{j-1}l_{ik}l_{jk}], & \mbox{if } i=j+1,...,n, j \neq n\end{cases}$
La tecnica compatta che va sotto il nome di Metodo di Cholesky, usa le seguenti relazioni per determinare gli elementi $l_{ij}$ della matrice $L$.
$j=1,2,...,n$ $\begin{cases}l_{jj}=\sqrt{a_{jj}-\sum\limits_{k=1}^{j-1}l_{jk}^2}, \\l_{ij}=\frac{1}{l_{jj}}[a_{ij}-\sum\limits_{k=1}^{j-1}l_{ik}l_{jk}], & \mbox{if } i=j+1,...,n, j \neq n\end{cases}$
Resto nell'interpolazione
Viste le condizioni di interpolazione $f(x_i)=p(x_i), i=0,...,n$, per "costruzione" (e prescindendo dagli errori sui dati e dagli errori di arrotondamento) l'operazione di interpolazione restituisce una risposta "esatta" sui nodi per cui se la funzione $f(x)$
Insieme dei numeri macchina
Il calcolatore, essendo una macchina finita, consente la rappresentazione di un sottoinsieme finito di reali.
$\mathbb{F}(t, \beta, L, U)=\{0\} \cup \{ x \in \mathbb{R} / x = segno(x) \beta^p \sum \limits_{i=1}^t d_i \beta^{-1} \}$ con $0 \leq d_i \leq \beta -1, i=1,2...,t$
$d_1 \neq 0$
$L \leq p \leq U$ dove $L$ intero negativo, $U$ intero positivo.
$x=\pm(.x_1x_2...x_t)\beta^p$
Il calcolatore usa solo un sottoinsieme finito di $\mathbb{R}$ e ogni volta che deve rappresentare un numero $x \in \mathbb{R}$ tale che $x \notin \mathbb{F}$ deve associargli un opportuno $\hat{x}\in \mathbb{F}$ tale che $x \approx \hat{x}$. Se $x \in \mathbb{R}, x\neq0, x\notin \mathbb{F}(t, \beta, L, U)$ si procede nel modo seguente:
Definizione.Si definisce insieme dei numeri macchina con $t>0$ cifre significative, base $\beta \geq 2$ e rango $(1,U)$ il sottoinsieme di $\mathbb{R}$ così definito:
$\mathbb{F}(t, \beta, L, U)=\{0\} \cup \{ x \in \mathbb{R} / x = segno(x) \beta^p \sum \limits_{i=1}^t d_i \beta^{-1} \}$ con $0 \leq d_i \leq \beta -1, i=1,2...,t$
$d_1 \neq 0$
$L \leq p \leq U$ dove $L$ intero negativo, $U$ intero positivo.
$x=\pm(.x_1x_2...x_t)\beta^p$
Il calcolatore usa solo un sottoinsieme finito di $\mathbb{R}$ e ogni volta che deve rappresentare un numero $x \in \mathbb{R}$ tale che $x \notin \mathbb{F}$ deve associargli un opportuno $\hat{x}\in \mathbb{F}$ tale che $x \approx \hat{x}$. Se $x \in \mathbb{R}, x\neq0, x\notin \mathbb{F}(t, \beta, L, U)$ si procede nel modo seguente:
- se $p<L \Rightarrow x \rightarrow \hat{x}=0$ e indicazione di underflow
- se $p>U \Rightarrow x \rightarrow$ nessun $\hat{x}$ ("Inf") e indicazione di overflow
- se $L \leq p \leq U$ ma $x \notin \mathbb{F}$ perché le sue cifre con $i>t$ non sono tutte nulle, si procede per troncamento o per arrotondamento:
- se $d_{t+1} < \frac{\beta}{2}$
$\Rightarrow x \rightarrow \hat{x}=trn(x)=\beta^p\sum\limits_{i=1}^td_i\beta^{-1}$
$\Rightarrow \hat{x}=(.d_1d_2...d_t)\beta^p$ - se $d_{t+1} \geq \frac{\beta}{2}$
$\Rightarrow x \rightarrow \hat{x}=arr(x)=trn(x)\beta^{p-t}$
$\Rightarrow \hat{x}=(.d_1d_2...(d_t)+1)\beta^p$
- se $d_{t+1} < \frac{\beta}{2}$
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}$
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:
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$
Notazione posizionale.$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.
L'errore inerente da una stima della sensibilità della soluzione agli errori sui dati.
Definizione.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}$.
In particolare:
$\alpha = x^TAx$ è uno scalare, cioè $\alpha \in \mathbb{R}$.
Definizione.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
Iscriviti a:
Post (Atom)