Richardson extrapolation

In numerical analysis, Richardson extrapolation is a method to improve an approximation that depends on a step size.

Let A(h) be an approximation of A that depends on a positive step size h with an error formula of the form

<math> A - A(h) = a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots <math>

where the ai are unknown constants and the ki are known constants such that hki > hki+1.

The exact value sought can be given by

<math> A = A(h) + a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots <math>

which can be simplified with Big O notation to be

<math> A = A(h)+ a_0h^{k_0} + O(h^{k_1}). \,\!<math>

Using the step sizes h and h / t for some t, the two formulas for A are:

<math> A = A(h)+ a_0h^{k_0} + O(h^{k_1}) \,\!<math>
<math> A = A\left(\frac{h}{t}\right) + a_0\left(\frac{h}{t}\right)^{k_0} + O(h^{k_1}) .<math>

Multiplying the second equation by tk0 and subtracting the first equation gives

<math> (t^{k_0}-1)A = t^{k_0}A\left(\frac{h}{t}\right) - A(h) + O(h^{k_1}) <math>

which can be solved for A to give

<math>A = \frac{t^{k_0}A\left(\frac{h}{t}\right) - A(h)}{t^{k_0}-1} + O(h^{k_1}) .<math>

By this process, we have achieved a better approximation of A by subtracting the largest term in the error which was O(hk0). This process can be repeated to remove more error terms to get even better approximations.

A general recurrence relation can be defined for the approximations by

<math> A_{i+1}(h) = \frac{t^{k_i}A_i\left(\frac{h}{t}\right) - A_i(h)}{t^{k_i}-1} <math>

such that

<math> A = A_{i+1}(h) + O(h^{k_{i+1}}) .<math>

A well-known practical use of Richardson extrapolation is Romberg integration, which applies Richardson extrapolation to the trapezium rule.

Example

Using Taylor's theorem,

<math>f(x+h) = f(x) + f'(x)h + \frac{f''(x)}{2}h^2 + \cdots<math>

so the derivative of f(x) is given by

<math>f'(x) = \frac{f(x+h) - f(x)}{h} - \frac{f''(x)}{2}h + \cdots.<math>

If the initial approximations of the derivative are chosen to be

<math>A_0(h) = \frac{f(x+h) - f(x)}{h}<math>

then ki = i+1.

For t = 2, the first formula extrapolated for A would be

<math>A = 2A_0\left(\frac{h}{2}\right) - A_0(h) + O(h^2) .<math>

For the new approximation

<math>A_1(h) = 2A_0\left(\frac{h}{2}\right) - A_0(h) <math>

we can extrapolate again to obtain

<math> A = \frac{4A_1\left(\frac{h}{2}\right) - A_1(h)}{3} + O(h^3) .<math>
Navigation

  • Art and Cultures
    • Art (https://academickids.com/encyclopedia/index.php/Art)
    • Architecture (https://academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (https://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (https://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools