Lestrapolazione di Richardson è un metodo che permette la costruzione di approssimazioni numeriche di ordine superiore a partire da formule di ordine inferiore. Prende il nome da Lewis Fry Richardson, che introdusse il metodo agli inizi del XX secolo, ed è una tecnica importante in analisi numerica, definita da alcuni autori come un metodo per "trasformare il piombo in oro" e "la cui importanza difficilmente può essere sopravvalutata".
Applicazioni dell'estrapolazione di Richardson includono il metodo di Romberg, che applica l'estrapolazione di Richardson alla regola del trapezio, e l'algoritmo di Bulirsch-Stoer per la soluzione di equazioni differenziali ordinarie.
Idea intuitiva L'estrapolazione di Richardson è come correggere la mira quando si sa che l'errore segue un pattern prevedibile. Se ogni volta che si calcola qualcosa commetti sempre lo stesso tipo di errore sistematico, puoi "cancellarlo" combinando intelligentemente due calcoli con precisioni diverse.
Si immagini di voler misurare la distanza di un edificio lontano. Si sa che lo strumento sottostima sempre la distanza in modo proporzionale al quadrato della nebbia. Se si misura con nebbia normale e con nebbia dimezzata, si possono combinare le due misure per eliminare l'errore sistematico e ottenere il valore vero.
L'analogia della fotografia È come quando si scatta una foto con diverse impostazioni sapendo che la fotocamera ha un bias sistematico. Se conosci il pattern dell'errore, puoi combinare le foto per ottenere un'immagine più fedele alla realtà.
Come funziona in pratica Il trucco dell'estrapolazione di Richardson si basa su una scoperta fondamentale: molti errori numerici hanno una struttura matematica prevedibili.
Il pattern dell'errore Quando approssimi una quantità con un metodo numerico che usa passo , l'errore spesso si comporta come:
dove: è il calcolo approssimato; è una costante sconosciuta (ma fissa); è l'ordine dell'errore (spesso conosciuto); è il "passo" del metodo (dimensione griglia, intervallo, ecc.).
La cancellazione magica Se si calcola la stessa quantità con passo e passo , si ottiene:
La seconda equazione diventa:
Combinando opportunamente le due equazioni, il termine si cancella completamente, lasciando solo errori di ordine superiore (molto più piccoli).
La formula risultante è:
Esempio numerico semplice Supponiamo di voler calcolare usando l'area di poligoni inscritti in un cerchio.
Con 6 lati: (errore grande). Con 12 lati: (errore dimezzato). Sapendo che l'errore va come (quindi ):
Risultato molto più vicino a rispetto alle singole approssimazioni.
Applicazioni principali L'estrapolazione di Richardson ha applicazioni concrete fondamentali.
Integrazione numerica (metodo di Romberg) Quando calcoli un integrale con la regola del trapezio, l'errore diminuisce come . Applicando Richardson ottieni automaticamente formule più precise come la regola di Simpson e oltre.
Esempio: calcolare Trapezi con 2 intervalli: 1,859 (errore ~0,14). Trapezi con 4 intervalli: 1,754 (errore ~0,04). Richardson su questi due: 1,719 (errore ~0,001).
Derivazione numerica Per approssimare , l'errore va come . Richardson elimina questo errore sistematico.
Equazioni differenziali (Bulirsch-Stoer) Nei metodi per risolvere equazioni differenziali, Richardson permette di ottenere soluzioni molto precise combinando passi diversi.
Limiti e serie Accelera la convergenza di successioni che convergono lentamente, trasformando convergenza lineare in convergenza quadratica o superiore.
Quando usarla e quando no L'estrapolazione di Richardson è potente ma ha limitazioni.
Quando funziona bene: l'errore ha davvero la forma attesa; la costante non cambia troppo al variare di ; la funzione è sufficientemente regolare (derivabile abbastanza volte); si conosce l'ordine dell'errore principale.
Quando può fallire: errori di arrotondamento che diventano dominanti per molto piccoli; funzioni con discontinuità o singolarità; metodi numerici instabili; l'assunzione sulla forma dell'errore è sbagliata.
Strategia pratica: Applicare il metodo base con passo . Ricalcolare con passo (o altro fattore). Applicare Richardson per eliminare l'errore dominante. Verificare confrontando con se necessario. Fermarsi quando gli errori di arrotondamento diventano dominanti.
Estensioni avanzate Il metodo può essere generalizzato e applicato ripetutamente.
Schema piramidale Partendo da più approssimazioni con passi diversi, si può costruire una "piramide" di valori sempre più precisi, eliminando successivamente errori di ordine , , , ecc.
Estrapolazione vettoriale Il metodo si estende a funzioni vettoriali e sistemi di equazioni, mantenendo le stesse proprietà di accelerazione della convergenza.
Combinazione con altri metodi Richardson si combina naturalmente con tecniche adattive, controllo automatico del passo, e metodi di tipo predictor-corrector.
Formulazione Sia data una funzione e una sua approssimazione numerica con passo e errore di troncamento di ordine
il cui residuo ha forma
dove sono costanti ignote e sono costanti note e tali che per ogni .
Applicando l'approssimazione con passo , dove è una costante arbitraria, si ottiene
Moltiplicando entrambi i membri per e sottraendo la formula originale
il termine di errore di ordine si cancella
ottenendo una nuova formula di ordine :
Il metodo può essere applicato ricorsivamente, costruendo una successione di formule
con , tale che .
Note
Bibliografia Testi fondamentali C. Brezinski, M. Redivo Zaglia (1991). Extrapolation Methods. Theory and Practice. North-Holland. Ivan Dimov, Zahari Zlatev, Istvan Farago, Agnes Havasi (2017). Richardson Extrapolation: Practical Aspects and Applications. Walter de Gruyter. J. Stoer, R. Bulirsch (2002). Introduction to Numerical Analysis. 3rd edition. Springer.
Articoli classici L.F. Richardson (1911). "The approximate arithmetical solution by finite differences of physical problems involving differential equations". Philosophical Transactions of the Royal Society A 210: 307-357. L.F. Richardson, J.A. Gaunt (1927). "The deferred approach to the limit". Philosophical Transactions of the Royal Society A 226: 299-349. W. Romberg (1955). "Vereinfachte numerische Integration". Det Kongelige Norske Videnskabers Selskab Forhandlinger 28: 30-36.
Testi avanzati J. Wimp (1981). Sequence Transformations and Their Applications. Academic Press. C. Brezinski (1977). Accélération de la Convergence en Analyse Numérique. Springer. A. Sidi (2003). Practical Extrapolation Methods: Theory and Applications. Cambridge University Press.
Applicazioni specifiche R. Bulirsch, J. Stoer (1966). "Numerical treatment of ordinary differential equations by extrapolation methods". Numerische Mathematik 8: 1-13. P. Deuflhard (1983). "Order and stepsize control in extrapolation methods". Numerische Mathematik 41: 399-422. E. Hairer, S.P. Nørsett, G. Wanner (1993). Solving Ordinary Differential Equations I: Nonstiff Problems. 2nd edition. Springer.
Voci correlate Regola del trapezio Integrazione numerica Analisi numerica
Collegamenti esterni
Fundamental Methods of Numerical Extrapolation With Applications , MIT Richardson-Extrapolation, UBC Richardson extrapolation, Robert Israel (University of British Columbia) Richardson Extrapolation, MathWorld Numerical Recipes Online - Capitolo su Richardson Extrapolation
Categoria:Analisi numerica Categoria:Algoritmi