Analisi numerica

Da Wikipedia, l'enciclopedia libera.

L'analisi numerica (detta anche calcolo numerico o calcolo scientifico) è una disciplina che rientra nella classe della matematica applicata. Il suo obiettivo è di sviluppare metodi per la risoluzione "pratica" di problemi matematici nel continuo (cioè relativi ai numeri reali o ai numeri complessi) tramite algoritmi che

  1. siano stabili, nel senso che non amplifichino gli errori inevitabilmente presenti sui dati di partenza
  2. siano efficienti, ossia abbiano basso costo computazionale, nel senso che la soluzione possa essere fornita da un calcolatore in un tempo accettabile.

Si noti che la soluzione calcolata dall'algoritmo (detta anche soluzione numerica) è sempre un'approssimazione di quella esatta: un algoritmo non ha ovviamente interesse se la soluzione calcolata si discosta molto da quella esatta.

La maggior parte delle soluzioni a problemi di analisi numerica sono fondate sull'algebra lineare. Non vanno peraltro trascurati i contributi della combinatorica e della geometria, come pure i collegamenti con i metodi probabilistici e fisico matematici.

Alcuni problemi della matematica del continuo possono essere risolti con algoritmi che risolvono il problema in un numero finito (e possibilmente noto a priori) di passi. Questi metodi sono detti metodi diretti. Tuttavia, per la maggior parte dei problemi numerici non ci sono metodi diretti. In tali casi, è spesso possibile usare un metodo iterativo. Un tale metodo inizia da un tentativo, e trova approssimazioni successive che sperabilmente convergono alla soluzione. Sono metodi iterativi l'algoritmo di Gauss-Jordan per risolvere i sistemi di equazioni lineari, e l'algoritmo del simplesso in programmazione lineare. Anche quando esiste un metodo diretto, a volte è preferibile un metodo iterativo perché più efficiente o più stabile, soprattutto quando si devono trattare matrici di dimensioni considerevoli (ad esempio una 1000x1000).

Indice

[modifica] Introduzione

[modifica] Le applicazioni

L'impatto sul mondo reale è decisivo e sfata il luogo comune per cui la matematica non avrebbe alcun fine pratico. Un esempio per tutti: l'algoritmo FFT (Trasformata Veloce di Fourier), che è uno dei successi dell'analisi numerica, è alla base degli algoritmi ricostruttivi delle immagini di tomografia computerizzata e di risonanza magnetica, come di risoluzione di problemi della multimedialità (compressione JPEG di immagini, compressione MP3 di musica, compressione mpeg di filmati, campionamento e filtraggio di segnali, solo per citare i più importanti).

Ma gli algoritmi di analisi numerica sono applicati quotidianamente per risolvere molti altri problemi scientifici e tecnici. Ne sono esempi la progettazione di strutture come ponti e aeroplani, le previsioni meteorologiche, l'analisi di molecole (chimica computazionale). Gli algoritmi di analisi numerica sono anche alla base dei programmi di CAE, e quasi tutti i supercomputer sono costantemente impegnati a eseguire algoritmi di analisi numerica.

L'efficienza degli algoritmi e della loro implementazione ha una grande importanza. Pertanto, un metodo euristico ma efficiente può essere preferito a un metodo con una solida base teorica ma inefficiente, e i linguaggi di programmazione datati ma efficienti Fortran e C sono i più usati.

In generale, l'analisi numerica è una scienza sia teorica che sperimentale. Infatti usa assiomi, teoremi e dimostrazioni, come il resto della matematica, ma usa anche i risultati empirici delle elaborazioni eseguite per studiare i metodi migliori per risolvere i problemi.

[modifica] Cenni storici

Il campo dell'analisi numerica risale a secoli prima dell'invenzione dei calcolatori elettronici. Di fatto, molti grandi matematici del passato si dedicarono all'analisi numerica, come è evidente dai nomi di importanti algoritmi dovuti a Newton, Joseph-Louis Lagrange,Seidel,Jacobi Carl Friedrich Gauss, o Eulero.

Per facilitare i calcoli a mano, furono stampati grandi libri pieni di formule e tabelle di dati come i punti interpolanti e i coefficienti di funzioni. Usando queste tabelle, si potevano trovare i valori da inserire nelle formule date e ottenere stime numeriche molto buone di alcune funzioni. Il lavoro canonico nel campo è la pubblicazione del NIST curata da Abramowitz e Stegun, un libro di oltre 1000 pagine contenente un gradissimo numero di formule e funzioni comunemente usate e i loro valori in molti punti. I valori delle funzioni non sono più molto utili quando si può usare un computer, ma il grande elenco di formule può ancora essere molto comodo.

La calcolatrice meccanica fu pure sviluppata come strumento per il calcolo manuale. Queste calcolatrici evolsero nei calcolatori elettronici negli anni 1940, e allora fu trovato che questi computer erano utili anche per scopi amministrativi. Ma l'invenzione del computer influenzò anche il campo dell'analisi numerica, siccome adesso si potevano fare calcoli più lunghi e più complicati.

[modifica] La generazione e la propagazione degli errori

Lo studio degli errori costituisce una parte importante dell'analisi numerica. Ci sono più modi in cui si possono introdurre errori nella soluzione di un problema:

Un errore, una volta che è stato generato, generalmente si propagherà attraverso il calcolo. Questo conduce al concetto di stabilità numerica: un algoritmo si dice numericamente stabile se un errore, una volta che è stato generato, non cresce troppo durante il calcolo. Per alcuni problemi non esistono algoritmi stabili, in quanto per variazioni arbitrariamente piccole dei dati del problema, la soluzione varia comunque di molto. Tali problemi sono detti mal-condizionati. Un problema non mal-condizionato si dice ben-condizionato.

Tuttavia, un algoritmo che risolve un problema ben-condizionato può essere numericamente stabile oppure no. L'obiettivo primario dell'analisi numerica è trovare algoritmi stabili per risolvere problemi ben-condizionati.

Siccome capita di imbattersi in problemi mal-condizionati, un altro obiettivo dell'analisi numerica sta nel trovare, per ogni problema mal-condizionato, un problema ben-condizionato la cui soluzione approssimi quella del problema originale.

[modifica] Le aree di studio

Il campo dell'analisi numerica è suddiviso in diverse discipline a seconda del problema da risolvere.

[modifica] Il calcolo dei valori delle funzioni

Uno dei problemi più semplici è la valutazione di una funzione in un dato punto. Ma perfino valutare un polinomio non è immediato: l'algoritmo di Horner è spesso più efficiente del metodo banale. In generale, l'attenzione principale nella risoluzione di questi problemi è volta a stimare e tenere sotto controllo gli errori di arrotondamento dovuti all'aritmetica a virgola mobile. Ciò viene fatto ponendo attenzione all'ordine in cui vengono eseguite le operazioni aritmetiche, cercando di minimizzare il numero delle stesse e cercando di evitare, quando possibile, quelle 'pericolose', quelle cioè che portano ad una perdita di cifre significative (vedi per esempio il fenomeno della cancellazione numerica).

[modifica] L'interpolazione, l'estrapolazione e la regressione

I metodi di interpolazione e estrapolazione stimano il valore di una funzione incognita dato il valore della funzione stessa in alcuni punti. Il più semplice metodo di interpolazione è l'interpolazione lineare, che suppone che la funzione sconosciuta sia lineare fra ogni coppia di punti consecutivi. Questo metodo può essere generalizzato dall'interpolazione polinomiale, che è talvolta più accurata ma soffre del fenomeno di Runge. Altri metodi di interpolazione usano funzioni regolari a tratti come le spline o le wavelet. L'estrapolazione, a differenza dall'interpolazione, stima la funzione in punti esterni ai punti per cui la funzione è nota.

La regressione è simile ai suddetti problemi, ma tiene conto che i valori dati sono imprecisi. La tecnica più usata per la regressione è il metodo dei minimi quadrati.

[modifica] La soluzione di equazioni e di sistemi di equazioni

Un altro problema fondamentale è calcolare la soluzione di un'equazione o di un sistema di equazioni. La distinzione principale è tra equazioni (o sistemi di equazioni) lineari e tra equazioni (o sistemi di equazioni) non lineari. I problemi lineari sono più facili da risolvere.

I metodi per la risoluzione di sistemi di equazioni lineari possono essere divisi in due categorie.

La prima categoria è quella dei metodi diretti. A questa categoria appartengono per esempio il metodo di eliminazione gaussiana e la fattorizzazione LU. I metodi diretti costruiscono l'esatta soluzione, a meno di errori di arrotondamento, in un numero finito di passi. In sostanza utilizzano l'idea della fattorizzazione della matrice dei coefficienti del sistema nel prodotto di due matrici più semplici (solitamente triangolari o ortogonali).[1] Sono generalmente i metodi più efficienti, soprattutto quando operano su matrici dei coefficienti dense, ma su sistemi di grosse dimensioni e/o con matrice dei coefficienti sparse tendono ad essere troppo onerosi in termini di consumo di memoria. In queste situazioni sono di norma preferibili i metodi appartenenti alla seconda categoria.

La seconda categoria è quella dei metodi iterativi. Appartengono ai metodi iterativi per esempio il metodo di Jacobi, il metodo di Gauss-Seidel e il metodo del gradiente coniugato. I metodi iterativi conducono alla soluzione del sistema in un numero teoricamente infinito di passi: partendo da un'approssimazione iniziale della soluzione, forniscono una serie di approssimazioni che, sotto opportune ipotesi, convergono alla soluzione esatta. Il processo iterativo viene arrestato non appena la precisione desiderata è stata raggiunta. Il metodo applicato risulterà efficiente se la precisione desiderata sarà stata raggiunta in un numero accettabile di iterazioni.[2]

Quando ci si trova invece di fronte ad equazioni non lineari, si ricorre agli algoritmi per trovare radici. Se la funzione è derivabile e la sua derivata è nota, allora il metodo di Newton è una scelta diffusa. La linearizzazione è un'altra tecnica per risolvere equazioni non lineari.

[modifica] L'ottimizzazione

I problemi di ottimizzazione richiedono di trovare il punto in cui una data funzione assume il valore massimo (o minimo). Spesso, il punto deve soddisfare anche alcuni vincoli.

Il campo dell'ottimizzazione è ulteriormente diviso in più sottocampi, a seconda della forma della funzione obiettivo e dei vincoli. Per esempio, la programmazione lineare tratta il caso in cui sia la funzione obiettivo che i vincoli siano lineari. Il più famoso algoritmo della programmazione lineare è il metodo del simplesso.

Il metodo dei moltiplicatori di Lagrange può essere usato per ridurre i problemi di ottimizzazione vincolata a problemi di ottimizzazione non vincolata.

[modifica] La valutazione di integrali

Per approfondire, vedi la voce Integrazione numerica.

L'integrazione numerica, nota anche come quadratura numerica, stima il valore di un integrale definito. I metodi diffusi usano qualche formula di Newton-Cotes, per esempio la regola del punto di mezzo o la regola del trapezio, oppure la quadratura Gaussiana. Tuttavia, se la dimensione del dominio di integrazione diventa grande, questi metodi diventano proibitivamente costosi. In questa situazione, si può usare un metodo Monte Carlo, un metodo quasi-Monte Carlo, o, per dimensioni moderatamente grandi, il metodo delle griglie sparse.

[modifica] Le equazioni differenziali

L'analisi numerica si interessa anche al calcolo (approssimato) della soluzione delle equazioni differenziali, sia ordinarie che alle derivate parziali. Le equazioni differenziali vengono risolte dapprima discretizzando l'equazione, cioè portandola in un sottospazio a dimensione finita. Questo si può fare con un metodo a elementi finiti, un metodo alle differenze finite, o (particolarmente nell'ingegneria) un metodo ai volumi finiti. La giustificazione teorica di questi metodi spesso implica teoremi dell'analisi funzionale. Questo riduce il problema alla soluzione di un'equazione algebrica.

[modifica] Il software

Quando algoritmi di analisi numerica sono tradotti in un linguaggio di programmazione ed opportunamente adattati alle caratteristiche dell'ambiente di calcolo (ad esempio implementati ed eseguiti su un calcolatore), si parla di software numerico. Ci sono almeno tre categorie di software numerico:

[modifica] Alcuni problemi trattati dall'analisi numerica

I problemi considerati dall'analisi numerica includono:

Quando sono possibili differenti soluzioni a problemi numerici, tre fattori pesano per decidere quale metodo seguire:

  • Stabilità - gli errori nell'approssimazione non dovrebbero crescere in maniera incontrollata quando la taglia dei calcoli aumenta
  • Accuratezza - l'approssimazione numerica dovrebbe essere la più accurata possibile
  • Efficienza - più è veloce il calcolo, migliore è il metodo. Si deve comunque trovare un compromesso tra accuratezza ed efficienza

[modifica] Note

  1. ^ Valeriano Comincioli, Metodi Numerici e Statistici per le Scienze Applicate, C.E.A. Casa Editrice Ambrosiana, 1992, ISBN 88-408-0757-8
  2. ^ Giovanni Monegato, Elementi di Calcolo Numerico, Ed. Levrotto & Bella, Torino 1995, ISBN 978-88-82-18017-1, pp. III-2, III-3

[modifica] Bibliografia

[modifica] Opere introduttive

(disponibile anche una versione inglese più ampia) ISBN 88-470-0077-7

[modifica] Opere di riferimento

[modifica] Fondamenti teorici

  • Kendall Atkinsons, Weimin Han (2001): Theoretical Numerical Analysis. A functional analysis framework, Springer ISBN 0-387-95142-3

[modifica] Algebra lineare numerica

[modifica] Altro

[modifica] Voci correlate

[modifica] Altri progetti

[modifica] Collegamenti esterni

Estratto da "http://it.wikipedia.org/wiki/Analisi_numerica"
Strumenti personali