Analisi numerica

Da Wikipedia, l'enciclopedia libera.
bussola Disambiguazione – "Approssimazione numerica" rimanda qui. Se stai cercando altri significati, vedi Approssimazione.
« La Matematica insegna a calcolare il valore numerico delle incognite che si presentano nei problemi pratici. Questo è lo scopo ultimo di tutte le teorie, analitiche, geometriche e meccaniche. Queste, nelle nostre scuole, devono essere coronate dal calcolo numerico, onde porne in luce il significato e l'applicazione. »
(Giuseppe Peano, Prefazione al volume Tavole Numeriche)

L'analisi numerica (detta anche calcolo numerico o calcolo scientifico) è una branca della matematica applicata che risolve i modelli prodotti dall'analisi matematica alle scomposizioni finite normalmente praticabili, coinvolgendo il concetto di approssimazione. I suoi strumenti detti algoritmi sono caratterizzabili in base a velocità di convergenza, stabilità numerica e computabilità.

Descrizione[modifica | modifica sorgente]

La maggior parte dei metodi di soluzione forniti dall'analisi numerica sono fondate sull'algebra lineare o sulla costruzione di successioni convergenti di numeri o funzioni. 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. Un tipico esempio è dato dal metodo di eliminazione di Gauss per risolvere i sistemi di equazioni lineari. 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.

Tipicamente, si scrive il problema della forma x=F(x) e si applica il teorema di punto fisso. Un classico esempio di algoritmo iterativo è il metodo di Newton per calcolare gli zeri di una funzione. Anche quando esiste un metodo diretto, a volte è preferibile un metodo iterativo perché più efficiente o più stabile, ad esempio quando si devono risolvere sistemi di equazioni lineari con migliaia di incognite.

Le applicazioni[modifica | modifica sorgente]

L'impatto sul mondo reale è decisivo e sfata il luogo comune secondo il quale 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.

Cenni storici[modifica | modifica sorgente]

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 Isaac Newton, Joseph-Louis Lagrange, Philipp Ludwig von Seidel, Carl 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 grandissimo 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; l'invenzione del computer influenzò anche il campo dell'analisi numerica, permettendo lo svolgimento di calcoli gradualmente sempre più complessi.

Le aree di studio[modifica | modifica sorgente]

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

Il calcolo dei valori delle funzioni[modifica | modifica sorgente]

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).

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

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.

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

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 matrici 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.

L'ottimizzazione[modifica | modifica sorgente]

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.

Gli algoritmi di ottimizzazione vengono in genere testati facendo uso di apposite funzioni di test, pensate per metterli alla prova in problemi che presentano particolari difficoltà computazionali.

La valutazione di integrali[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi 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.

Le equazioni differenziali[modifica | modifica sorgente]

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.

Alcuni problemi trattati dall'analisi numerica[modifica | modifica sorgente]

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

La generazione e la propagazione degli errori[modifica | modifica sorgente]

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.

Il software[modifica | modifica sorgente]

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:

Note[modifica | modifica sorgente]

  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-8218-017-1, pp. III-2, III-3

Bibliografia[modifica | modifica sorgente]

Opere introduttive[modifica | modifica sorgente]

  • R. Bevilacqua, D. Bini, M. Capovani, O. Menchi (1987): Introduzione alla Matematica Computazionale, Zanichelli, ISBN 88-08-04356-8
  • Samuel D. Conte, Carl de Boor (1981): Elementary numerical analysis. An algoritmic approach, 3rd ed., McGraw-Hill, ISBN 0-07-012447-7
  • Valeriano Comincioli (1990): Analisi numerica. Metodi, modelli, applicazioni. McGraw-Hill, ISBN 88-386-0646-3; nuova edizione e-book APOGEO, Feltrinelli Milano, 2005 http://www.apogeonline.com/libri/88-503-1031-5/scheda
  • Giovanni Monegato (1990): Fondamenti di calcolo numerico, Levrotto & Bella, Torino
  • (EN) Walter Gautschi (1997): Numerical analysis. An introduction, Birkhäuser ISBN 3-7643-3895-4
  • A. Quarteroni, R. Sacco, F. Saleri (2000): Matematica Numerica, Springer Italia, Milano

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

  • G. Naldi, L. Pareschi, G. Russo (2001, 2004 II ed.): Introduzione al Calcolo Scientifico, McGraw-Hill, ISBN 88-386-0885-7

Opere di riferimento[modifica | modifica sorgente]

Fondamenti teorici[modifica | modifica sorgente]

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

Algebra lineare numerica[modifica | modifica sorgente]

  • D. Bini, M. Capovani, O. Menchi (1988): Metodi Numerici per l'Algebra Lineare, Zanichelli, ISBN 88-08-06438-7
  • (EN) Gene H. Golub, Charles F. Van Loan (1996): Matrix computations, III ed., Johns Hopkins University Press, ISBN 0-8018-5414-8

Altro[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]

Altri progetti[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica