# Definite Integrals, Part 4: Romberg Integration

## Contents

# 25. Definite Integrals, Part 4: Romberg Integration#

**References:**

Section 5.3

*Romberg Integration*of SauerSection 4.5

*Romberg Integration*of Burden&Faires

## 25.1. Introduction#

Romberg Integration is based on repeated Richardson extrapolalation from the composite trapezoidal rule, starting with one interval and repeatedly doubling. Our notation starts with

where

and the second index will indicate the number of extapolation steps done (none so far!)

Actually we only need this \(T_n\) formula for the single trapezoidal rule, to get

because the most efficient way to get the other values is recursively, with

where \(M_n\) is the composite midpoint rule,

Extrapolation is then done with the formula

which can also be expressed as

## 25.2. An algorithm, in pseudocode#

The above can now be arranged into a basic algorithm. It does a fixed number \(M\) of levels of extrapolation so using \(2^M\) intervals; a refinement would be to use the above error estimate \(E_{i,j-1}\) as the basis for a stopping condition.

\(n \leftarrow 1\)

\(h \leftarrow b-a\)

\(\displaystyle R_{0,0} = \frac{f(a) + f(b)}{2} h\)

`for i from 1 to M:`

\(\quad\) \(R_{i,0} = \left( R_{i-1,0} + h \sum_{k=1}^n f(a + (i - 1/2)h) \right)/2\)

\(\quad\) `for j from 1 to i:`

\(\quad\quad \displaystyle R_{i,j} = \frac{4^j R_{i,j-1} - R_{i-1,j-1}}{4^j - 1}\)

\(\quad\) `end for`

\(\quad n \leftarrow 2 n\)

\(\quad h \leftarrow h/2\)

`end for`

This work is licensed under Creative Commons Attribution-ShareAlike 4.0 International