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$.
Iscriviti a:
Post (Atom)