Overview
Romberg Integration repeatedly halves the step size and combines estimates to cancel leading error terms.
SpecializedSource checked
Romberg Integration
Improves trapezoidal integration estimates with extrapolation.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Numerical Methods
- Difficulty
- Intermediate
- Family
- Numerical Integration
- Tier
- Specialized
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
trapezoidal estimatestep refinementRichardson extrapolationerror cancellation
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(log n)
When to Use
- Use when the integrand is smooth and high accuracy is needed.
- Use when accurate smooth-function integration is a central requirement.
When Not to Use
- Avoid when the integrand has discontinuities, singularities, or noisy samples.
- Avoid when roundoff, conditioning, or discontinuities dominate the result.
What It Does
- Computes numerical integration within Numerical Integration workloads (O(n) time, O(log n) space).
- Works by Improves trapezoidal integration estimates with extrapolation.
- Maintains key invariants across trapezoidal estimate, step refinement, Richardson extrapolation.
Use Cases
- Accurate smooth-function integration
- Numerical analysis
- Scientific computing
Inputs
- Function
- Integration interval
- Tolerance
Outputs
- Integral estimate
Key Formulas (1)
Romberg extrapolation
R[k,j] = R[k,j−1] + (R[k,j−1] − R[k−1,j−1]) / (4j − 1)
R[k,j] = R[k,j-1] + (R[k,j-1] - R[k-1,j-1]) / (4^j - 1)Combines estimates to cancel lower-order integration error.
Pseudocode
- 1.Compute an initial trapezoidal estimate
- 2.Halve the step size
- 3.Fill a Romberg table with extrapolated estimates
- 4.Stop when adjacent estimates differ by tolerance
Canonical Example
- Input
- integrate x^2 from 0 to 1
- Output
- estimate approaches 0.3333
- Explanation
- Refined trapezoid estimates are extrapolated toward the exact value.
Implementation Notes
- Stop based on both tolerance and a maximum refinement level.
- Compare against a small hand-checkable case before scaling up.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Extrapolation can look precise while failing on nonsmooth functions.
- Ignoring conditioning can make a correct method return unreliable numbers.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow a table of integration estimates becoming more accurate down and across.
Step 1 of 4: Compute an initial trapezoidal estimate
numeric-iterationNotes
Romberg works best on smooth functions over finite intervals.
Sources (1)
What each reference supports for this entry.
Numerical Recipes
BookNumerical methods reference covering Romberg integration and Richardson extrapolation.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toAdaptive Quadrature
Both refine numerical integration estimates.
Improves onTrapezoidal Rule
Romberg integration extrapolates repeated trapezoidal estimates.
Related Algorithms
Tags
Numerical MethodsQuadratureNumerical Integration