Materiale e dispense

FABRIS Francesco
COMPUTABILITA' E COMPLESSITA'

TEORIA DEGLI ERRORI

1. RAPPRESENTAZIONE POSIZIONALE DEI NUMERI REALI
base
cifre
intero
decimale
periodici

2. RAPPRESENTAZIONE "FLOATING POINT" E NUMERI DI MACCHINA
rappresentazione normale
esponente
mantissa
rappresentazione mista
underflow o overflow
troncamento
arrotondamento
virgola mobile (floating point)
numeri di macchina.
floating point
precisione di macchina o epsilon di macchina o unità di arrotondamento


3. OPERAZIONI DI MACCHINA E PROPAGAZIONE DEGLI ERRORI.
operazione di macchina
indici di condizionamento del problema .
algoritmo
Complementi alla teoria degli errori
analisi all'indietro
indici di condizionamento dell'algoritmo
schema naturale
schema di Horner.



APPROSSIMAZIONE DELLE FUNZIONI
1. INTRODUZIONE

polinomi algebrici
Teorema di Weierstrass
norma lagrangiana
Teorema di Bernstein
polinomi trigonometrici
polinomi esponenziali:
polinomi a tratti
funzioni splines
polinomi razionali

2. METODI INTERPOLATORI.
polinomio d'interpolazione di Lagrange
polinomio di Lagrange.
polinomio di Chebyshev di grado n
relazione ricorsiva
coefficiente principale
massimi e minimi
polinomio monico di Chebyshev
polinomio d'interpolazione di Hermite
polinomio di interpolazione di Birkhoff
differenza divisa di ordine zero
differenza divisa di ordine uno
differenze divise di ordine k
polinomio di Newton.
base triangolare
interpolazione di Lagrange a tratti.
cubiche di Lagrange.
interpolazione di Hermite a tratti
cubiche di Hermite
shape preserving
pchip.m (piecewise cubic Hermite interpolation polynomial)
funzione spline
spline cubiche
spline naturali
spline periodiche
spline cubiche complete
spline "not a knot"
trasformata discreta di Fourier
DFT (Discrete Fourier Transform)
antitrasformata discreta di Fourier
IDFT (Inverse Discrete Fourier Transform)
trasformata rapida di Fourier
FFT Fast Fourier Transform
periodogramma


PROBLEMA DEI MINIMI QUADRATI

range di A
vettore residuo
soluzione ai minimi quadrati
elemento di minimo scarto
sistema di equazioni normali.
valori singolari di A


FORMULE DI QUADRATURA

formule di quadratura
pesi,
nodi
formule di quadratura lagrangiane
formule di Newton-C\364tes
numeri di C\364tes
ordine polinomiale
formula di quadratura composta
formula dei trapezi.
formula di Cavalieri-Simpson.
funzionale lineare
processo di estrapolazione di Richardson
termine principale d'errore
termine secondario d'errore
Eulero e Mac Laurin
quadratura di Romberg.

SPAZI VETTORIALI NORMATI

NOZIONI PRELIMINARI.

ortogonali
trasposta
simmetrica
ortogonale
regolare
non singolare
inversa
involutoria
trasposta coniugata
hermitiana
unitaria
semidefinita positiva
definita positiva
autovalore
autovettore
o autosoluzione
spettro
equazione
caratteristica
traccia
molteplicità algebrica
spettro
autospazio


TEOREMA DI GERSCHGORIN

Matrici di permutazione
Matrici triangolari
Matrici diagonali
vettore unitario

NORME DI VETTORI E DI MATRICI.
norma
norma naturale o norma indotta

SISTEMI LINEARI

METODI ITERATIVI.
fattore asintotico di convergenza
ordine asintotico di convergenza
predominanza diagonale stretta
predominanza diagonale per colonne
parametro di rilassamento
Teorema di Kahan
Teorema di Reich-Ostrowski

METODI DIRETTI
matrici elementari di Gauss
pivot parziale
pivot totale
complessità computazionale

Lemma di perturbazione (di Banach)

EQUAZIONI NON LINEARI

Teorema di convergenza:

EQUAZIONI DIFFERENZIALI


Università  degli Studi di Trieste
Ingegneria
C.d.l. magistrale in INGEGNERIA INFORMATICA

135INC.