Analisi numerica

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Calcolo scientifico)
Vai alla navigazione Vai alla ricerca
Disambiguazione – "Approssimazione numerica" rimanda qui. Se stai cercando altri significati, vedi Approssimazione.

L'analisi numerica è 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à.

«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.»

La maggior parte dei metodi di soluzione forniti dall'analisi numerica è fondata sull'algebra lineare o sulla costruzione di successioni convergenti di numeri o funzioni a cui si aggiungono i contributi della combinatoria e della geometria e 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 e in questi casi è spesso possibile usare un metodo iterativo. Un metodo iterativo 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 wikitesto]

L'impatto sul mondo reale è decisivo e sfata il luogo comune secondo 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 e della risoluzione di problemi della multimedialità come, tra i più importanti, compressione JPEG di immagini, compressione MP3 di musica, compressione mpeg di filmati, campionamento e filtraggio di segnali.

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 efficiente può essere preferito a un metodo con una solida base teorica, ma inefficiente. Gli efficienti linguaggi di programmazione Fortran e C, anche se datati, sono i più usati.

In generale l'analisi numerica è una scienza sia teorica sia sperimentale. Infatti non usa soltanto 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.

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.

Aree di studio

[modifica | modifica wikitesto]

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

Il calcolo dei valori delle funzioni

[modifica | modifica wikitesto]

Uno dei problemi più semplici è la valutazione di una funzione in un dato punto. 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 come quelle che causano cancellazione numerica.

L'interpolazione, l'estrapolazione e la regressione

[modifica | modifica wikitesto]

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 wikitesto]

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 è efficiente se la precisione desiderata è stata raggiunta in un numero accettabile di iterazioni.[2]

Se le equazioni sono 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 wikitesto]
Lo stesso argomento in dettaglio: Ottimizzazione (matematica).

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 sono 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 wikitesto]
Lo stesso argomento in dettaglio: 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 wikitesto]
Lo stesso argomento in dettaglio: Equazione differenziale.

L'analisi numerica si interessa anche al calcolo approssimato della soluzione delle equazioni differenziali, sia ordinarie sia 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 un metodo ai volumi finiti, particolarmente usato nell'ingegneria. 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 wikitesto]

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 devono crescere in maniera incontrollata quando la taglia dei calcoli aumenta
  • Accuratezza - l'approssimazione numerica deve 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 wikitesto]

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 propaga 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. Questi 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. Un altro obiettivo dell'analisi numerica è trovare, per ogni problema mal-condizionato, un problema ben-condizionato la cui soluzione approssimi quella del problema originale.

Quando algoritmi di analisi numerica sono tradotti in un linguaggio di programmazione e 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:

  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

Opere introduttive

[modifica | modifica wikitesto]

(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
  • (EN) Endre Süli e David Mayers, An Introduction to Numerical Analysis, Cambridge, Cambridge University Press, 2003, ISBN 978-0-521-00794-8.

Opere di riferimento

[modifica | modifica wikitesto]

Fondamenti teorici

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

Algebra lineare numerica

[modifica | modifica wikitesto]
  • 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

Voci correlate

[modifica | modifica wikitesto]

Altri progetti

[modifica | modifica wikitesto]

Collegamenti esterni

[modifica | modifica wikitesto]
Controllo di autoritàThesaurus BNCF 1143 · LCCN (ENsh85093237 · GND (DE4042805-9 · BNF (FRcb11930888x (data) · J9U (ENHE987007538744005171
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica