Formule sommatorie
$\sum\limits_{k=1}^nk^2 = \frac{n(n+1)(n+2)}{6}$
$\sum\limits_{k=1}^nk = \frac{n(n+1)}{2}$
Laplace: $O(n!)$
Cramer: $O((n+1)!)$
Risoluzione sistema $Tx=b$: $O(\frac{n^2}{2})$, $T$ è triangolare
Confronti nel Pivoting parziale: $O(\frac{n^2}{2})$
Confronti nel pivoting totale: $O(\frac{n^3}{3})$
Tecniche compatte per determinare la fattorizzazione LU: $O(\frac{n^3}{3})$
Risolvere un sistema AX=B con fattorizzazione LU: $O(\frac{n^3}{3}+rn^2)$
Metodo di Gauss (triangolarizzazione): $O(\frac{n^3}{3})$
Diagonalizzare una matrice con la Variante di Gauss Jordan del metodo di eliminazione di Gauss: $O(\frac{n^3}{2})$
Metodo di Gauss-Jordan per il calcolo dell'inversa: $O(n^3)$
Metodi iterativi per sistemi lineari: $O(Kn^2)$, dove $K$ è il numero di iterazioni
Costruzionee tabella delle differenze divise: $O(\frac{n^2}{2})$
Polinomio di Lagrange: $O(2n^2+2n)$
Interpolazione di Hermite
E' un caso particolare di polinomio osculatore.
Dati $n+1$ nodi $x_0, x_1, ...,x_n$, il polinomio interpolante di Hermite di grado $2n+1$ è tale che soddisfa:
$p_H=f(x_i), i=0,...,n$ ($n+1$ condizioni)
$p^{'}_H=f^{'}(x_i), i=0,...,n$ ($n+1$ condizioni)
Abbiamo $2n+2$ condizioni.
Il polinomio di Hermite può essere rappresentato usando gli $L_j(x)$ di Lagrange:
$p_H(x)=\sum\limits_{j=0}^n[U_j(x)f(x_j)+V_j(x)f^{'}(x)]$ dove
per $j =0,...,n$
Allora $\exists\xi\in]a,b[$ tale che il resto del polinomio di Hermite è dato da $r(x)=\pi_{n+1}^2(x)\frac{f^{2n+2}(\xi)}{(2n+2)!}$
Dati $n+1$ nodi $x_0, x_1, ...,x_n$, il polinomio interpolante di Hermite di grado $2n+1$ è tale che soddisfa:
$p_H=f(x_i), i=0,...,n$ ($n+1$ condizioni)
$p^{'}_H=f^{'}(x_i), i=0,...,n$ ($n+1$ condizioni)
Abbiamo $2n+2$ condizioni.
Il polinomio di Hermite può essere rappresentato usando gli $L_j(x)$ di Lagrange:
$p_H(x)=\sum\limits_{j=0}^n[U_j(x)f(x_j)+V_j(x)f^{'}(x)]$ dove
per $j =0,...,n$
- $U_j(x)=L^2_j(x)[1-2L^{'}_j(x_j)(x-x_j)]$
- $V_j(x)=L^2_j(x)(x-x_j)$
Resto nell'interpolazione di HermiteSiano $a=\min\limits_{0 \leq i \leq n}\{x_i\}, b=\max\limits_{0\leq i\leq n}\{x_i\}$ e sia $f(x) \in C^{2n+2}([a,b])$.
Allora $\exists\xi\in]a,b[$ tale che il resto del polinomio di Hermite è dato da $r(x)=\pi_{n+1}^2(x)\frac{f^{2n+2}(\xi)}{(2n+2)!}$
Nodi di Chebyshev
Osservando i polinomi interpolanti la funzione di Runge su nodi equidistanti si vede che l'errore di interpolazione è minore al centro dell'intervallo [-5,5], mentre cresce, al crescere di n,agli estremi dell'intervallo [-5, 5]. Ci suggerisce di interpolare con una distribuzione di nodi non equidistanti. Una buona scelta è quella dei nodi di Chebyshev:
$x_i=\frac{a+b}{2}-\frac{b-a}{2}cos[\frac{(2i+1)}{2(n+1)}\pi], i=0,1,...,n$
Questa scelta è quella che nell'espressione del resto $r(x)$, minimizza il $\pi_{n+1}(x)$ .
Per concludere, la "bontà" dell'interpolazione, dipende da:
$x_i=\frac{a+b}{2}-\frac{b-a}{2}cos[\frac{(2i+1)}{2(n+1)}\pi], i=0,1,...,n$
Questa scelta è quella che nell'espressione del resto $r(x)$, minimizza il $\pi_{n+1}(x)$ .
Per concludere, la "bontà" dell'interpolazione, dipende da:
- il numero dei nodi (non ha senso costruire polinomi interpolatori per $n \geq 7$)
- la distribuzione dei nodi
Polinomi osculatori
// $f^{(0)}(x_i) = {p^{(0)}}_n(x_i), i=0,...,n$
I polinomi osculatori sono polinomi che nei nodi $x_i, i=0,...,n$ soddisfano condizioni che coinvolgono la funzione interpolanda $f(x)$ e le sue derivate
$p^{(k)}(x_i)=f^{(k)}(x_i), i=0,...n, k=0,...n$
Prendere n ci garantisce che $\exists!$ il polinomio osculatore.
Il grado del polinomio osculatore è pari al numero delle condizioni di interpolazione meno uno.
Condizione sufficiente per l'$\exists!$ del polinomio osculatoreIl polinomio osculatore $\exists!$ quando solo se, quando si impone una condizione di interpolazione sulla $k$-esima derivata in un nodo $x_j$ fissato, $p^{(k)}(x_j)=f^{(k)}(x_j)$ allora vengono imposte anche tutte le condizioni di interpolazione sule derivata di ordine inferiore a $k$, cioè $0,1,...,k-1$ sullo stesso nodo $x_j$.
Metodo di Gauss Seidel
$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$
$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}$
Iscriviti a:
Post (Atom)