Analisi Numerica - Appunti

STABILITA' DI UN ALGORITMO: un algoritmo si dice stabile se durante la sua successione finita di

istruzioni gli errori di arrotondamento dovuti alle singole operazioni. La stabilità dipende dunque dal

condizionamento delle successioni che compongono l'algoritmo, ossia da quanto perturbazioni sui

dati producono perturbazioni sui risultati. Un algoritmo è bencondizionato e quindi più stabile se a

piccole variazioni sui dati corrispondono piccole variazioni sui risultati. Il risultato trovato con un

algoritmo instabile può produrre risultati non sufficientemente corretti, e quindi inutilizzabili.

Per analizzare la stabilità si può agire in due modi:

1-Analisi In Avanti in cui viene valutata la differenza tra soluzione esatta e soluzione calcolata

2-Analisi all'Indietro in cui la soluzione calcolata viene considerata come la soluzione esatta

di un problema perturbato Q e viene valutato P-Q

APPROSSIMAZIONE: Esistono due tipi di approssimazioni che possono essere effettuati su dati;

la prima è la migliore approssimazione che avviene quando si ha una serie di dati affetti da errori

che vengono approssimati nel loro insieme; la seconda è l'interpolazione che consiste nel cercare

una funzione che passi per i dati esatti. Durante l'approssimazione si usano principalemente classi

di funzioni come i polinomi, le funzioni trigonometriche, le funzioni razionali o le funzioni polinomiali

a tratti dette anche splines.

QUADRATURA: si dice quadratura l'approssimazione dell'area sottesa da una curva. Essa viene

usata soprattutto per risolvere gli integrali di cui è difficile trovare la primitiva. Vengono usate per

distinguere le approssimazioni numeriche di un integrale dalla risoluzione di un equazione

differenziale. L'errore nelle formule di quadratura è dato dalla differenza tra I e I(n+1), dove I(n+1)

è dato dala sommatoria degli w*f(x), con w detti pesi della formula di quadratura e x detti nodi della

formula di quadratura. Il grado di precisione di è uguale a k se la funzione integranda ha grado

minore o uguale a k.

FLOATING POINT: un numero scritto in floating point è un numero reale scritto in una forma

macchina. Esso è composto dal segno, dai numeri di mantissa e dalla base elevata ad un

esponente. Quando un numero reale ha bisogno di un numero maggiore di cifre di mantissa si

produce un errore di arrotondamento. Se necessita di una caratteristica non compresa tra i valori

minimo e massimo dell'esponente si producono errori di underflow o di overflow. Il numero floating

point rappresenta quindi il numero macchina più vicino a quello reale, determinato con

troncamento o arrotondamento.

FONTI DEGLI ERRORI: gli errori possono essere Inerenti, ossia derivare dai dati stessi; possono

essere analitici o di troncamento, ossia derivanti da approssimazioni; possono essere algoritmici,

ossia derivanti dalle approssimazioni effettuate durante l'esecuzione di un algoritmo.

TIPI DI ERRORI: vi è l'errore assoluto, dato dal modulo della differenza tra valore reale e numero

in floating point, oppure quello relativo, ottenuto dal rapporto tra modulo della differenza di numero

reale e numero in floating point e modulo del valore reale. L'errore relativo, al contrario di quello

assoluto, non dipende dall'ordine di grandezza della caratteristica, ma dalla mantissa. La

precisione di un approssimazione deriva da una limitazione superiore degli errori relativi. Essa

viene definita precisione di macchina ed è data da (0.5) B^(1-t) con troncamento (arrotondamento)

TOLLERANZA: differenza tra due numeri reali, che se più piccola della precisione di macchina

rende i due numeri considerabili uguali.

METODI DI RISOLUZIONE DEI SISTEMI LINEARI: vi sono i metodi diretti che trasformano il

sistema in uno equivalente di cui si sa calcolare la soluzione attraverso un numero finito di

operazioni e i metodi iterativi nei quali la soluzione viene ottenuta come limite di una successione,

sfruttando la sparsità della matrice.

NUMERO DI CONDIZIONAMENTO: numero sempre maggiore di uno dato dal prodotto tra le

norme di A e A^(-1). Esso è sempre maggiore o uguale del rapporto tra errore relativo sui risultati e

quello sui dati. Non vi è nessuna relazione tra ordine del sistema e numero di condizionamento o

tra determinante e numero di condizionamento.

METODI DIRETTI:

• Metodo di Cramer: metodo inefficiente per il troppo numero di operazioni richieste

• Metodo di sostituzione in avanti o all'indietro: esso risulta utile se si hanno matrici

triangolari ed ha un costo computazionale di n^2/2 operazioni

• Metodo di Fattorizzazione: trasformare il sistema in uno equivalente esprimendo la matrice

dei coefficienti A come il prodotto tra due matrici triangolari, una superiore ed una inferiore.

• Metodo di Eliminazione di Gauss: il sistema viene risolto eliminando via via le variabili dalle

equazione e riducendosi ad un sistema con matrice dei coefficienti triangolare. Per effettuare

questa operazione possono essere sommate le equazioni, oppure scambiate di ordine,

oppure moltiplicate per uno scalare. L'algoritmo si interrompe se un coefficiente sulla

diagonale è 0. quando i valori sulla diagonale sono piccoli, ci l'algoritmo può essere instabile.

Per evitare l'instabilità si applica o il pivoting totale (si sceglie come valore da modificare

quello più grande tra quelli da trasformare) oppure il pivoting parziali (si sceglie come

elemento pivot quello massimo in una colonna).

• Fattorizzazione di Choleski: se la matrice A è simmetrica e definita positiva, allora si applica

una fattorizzazione di A costruendo una matrice diagonale D in modo tale che A= L * D^1/2 *

D^1/2 * R. ponendo R=U' e S=L*D^1/2; A risulta uguale a S*S'. Esso è un algoritmo stabile

che richiede N^3/6 operazioni, ma viene usato soprattutto per verificare se A è definita

positiva.

METODI ITERATIVI: si vuole costruire una successione che converga alla soluzione e che sia

facilmente costruibile. Vengono usati principalmente per sistemi di grandi dimensione con matrici A

sparse. Dal sistema lineare si decompone A in P-N. X(k+1)=P^-1 N X(k) + P^-1*b = BX(k) + g

• Se B è convergente allora il metodo iterativo converge

• Converge per |p|<1, dove p viene definito raggio spettrale ed è il più grande tra gli

autovalori di B.

• Costruendo tre matrici: D diagonale, E opposto di una triangolare inferiore e F opposto di

una triangolare superiore, derivano due metodi iterativi:

Metodo di Jacobi: dove la matrice P è uguale alla matrice D diagonale

o Metodo di Gauss-Seidel: dove la matrice P è uguale alla matrice diagonale D meno

o

la matrice triangolare inferiore.

• GS converge se e solo se converge J

• Non si può dire che GS converga piu velocemente di J però asintoticamente

sono necessarie la metà delle operazioni.

• Entrambi convergono se la matrice A è diagonale dominante; se è

simmetrica e definita positiva GS converge

POLINOMIO INTERPOLANTE DI LAGRANGE: polinomio di grado n definito dalle basi di

Lagrange…

INTERPOLAZIONE: caso particolare di approssimazione in cui il grado del polinomio è uguale al

numero dei punti meno 1. si possono avere problemi di oscillazione aumentando il grado del

polinomio e per evitarli si passa alle funzioni polinomiali a tratti o splines.

SPLINES: sono funzioni interpolanti di grado basso, in cui l'intervalli viene diviso in tanti

sottointervalli. Se gli estremi coincidono con punti di interpolazione si dicono splines interpolanti nei

nodi.il grado di libertà delle spline è dato da (m+1)*n - (m*(n-1)) = m+n, dove m è il grado della

spline e n il numero di nodi. Le Bspline sono funzioni spline particolari usate nelle applicazioni

industriali tutte positive, a supporto compatto e che formano una partizione nell'unità. Con le

condizioni di interpolazione i gradi di libertà si riducono a m-1.

Tre tipi di spline:

• Naturali: dove le derivate seconde agli estremi sono 0

• Periodiche: dove le edrivate agli estremi sono uguali e i valori dei punti agli estermi

coincidono

• Not a knot: le spline sono di classe c3

REGOLA DEI TRAPEZI: l'integrale da a a b di f(x) è (b-a)/2 * (f(b)+f(a))

REGOLA DI SIMPSON: l'integrale da a a b di f(x) è (b-a) / 6 (f(a) + 4f((a+b)/2) + f(b))

FORMULE DI NEWTON-COTES: formule di quadratura dove i nodi sono prefissati ed equispaziati.

Hanno grado di precisione n o n+1. i pesi sono tutti funzioni razionali ma hanno lo svantaggio che

per n>9 non sono tutti dello stesso segno.

Si basano sul metodo di interpolazione di Lagrange. Ci sono tabelle a simmetria centrale che

definiscono i pesi a seconda del numero di nodi, dato che non dipendono dalla ampiezza.

Precisione n se dispari n+1 se pari

FORMULE GAUSSIANE: i nopdi non sono prefissati ma vengono ricavati con i pesi per

massimizzare il grado di precisione.che diventa 2n+1. il problema è che i pesi, pur essendo

sempre positivi, possono non essere funzioni razionali.

La cosa importante è determinare il numero giusto di suddivisioni valutando l'errore di volta in volta

fino a quando esso non converge. Vengono usate per superare il limite della suddivisione

uniforme.

VELOCITA DI CONVERGENZA: data una successione che converge ad a, sia e(n) = x(n) - a. se

lim -> inf |e(n+1)| / |e(n)|^p=C; p si dice ordine di convergenza e C fattore di convergenza.

VALORE DI INNESCO: valore che è indispensabile scegliere giusto per serie che convergono

localmente.

CRITERI DI ARRESTO: una serie si arresta se l'errore relativo è minore della tolleranza, oppure se

lo è minore quello assoluto, oppure con un criterio misto se l'errrore assoluto è minore uguale della

tolleranza relativa *x(k+1) + la tolleranza assoluta

METODO DI BISEZIONE: metodo per approssimare gli zeri di una funzione che si basa sul

teorema degli zeri. Si divide l'intervallo in due fino a quando non si trova lo zero. c'è sempre

convergenza se f è continua. l'algoritmo è lento perché tiene conto solo dei segni.

METODO DELLA REGULA FALSI: vengono considerati anche i valori della funzioneagli estremi e

si considera come nuova approssimazione la retta passante per (a, f(a); b, f(b)). La convergenza è

globale e la velocità è lineare.

METODO DELLE SECANTI: scelti due valori iniziali si costruisce la successione x(k+1) = x(k) -

((x(k) - x(k-1))/(f(x(k)) - f(x(k-1))) * f(x(k)). Convergenza locale garantita se le approssimazioni

iniziali sono vicine ad a.

METODO DI NEWTON: x(k+1) = x(k) - f(x(k))/f'(x(k)). Esso ha un ordine di convergenza

quadratico.

METODO DI ITERAZIONE FUNZIONALE: si studiano i punti fissi costruendo una opportuna

funzione g tale che f(&)=0 se e solo se & = g(&) la successone diventa quind