Koksma–Hlawka inequality

E824092

The Koksma–Hlawka inequality is a fundamental result in numerical analysis and discrepancy theory that bounds the error of quasi-Monte Carlo integration by the product of a function’s variation and the discrepancy of the sampling points.

All labels observed (6)

How this entity was disambiguated

Statements (48)

Predicate Object
instanceOf mathematical inequality ⓘ
result in discrepancy theory ⓘ
result in numerical analysis ⓘ
appliesTo deterministic numerical integration ⓘ
integration over the unit cube [0,1]^s ⓘ
assumes function of bounded variation in the sense of Hardy–Krause ⓘ
point set in the s-dimensional unit cube ⓘ
comparedWith Monte Carlo error bounds based on variance ⓘ
compares exact integral ⓘ
quasi-Monte Carlo integration error ⓘ
errorBoundDependsOn discrepancy of the sampling points ⓘ
variation of the integrand ⓘ
errorType worst-case error bound ⓘ
field discrepancy theory ⓘ
numerical analysis ⓘ
quasi-Monte Carlo methods ⓘ
generalizedBy various weighted discrepancy inequalities ⓘ
givesUpperBoundOn absolute integration error ⓘ
hasVariant Koksma–Hlawka inequality for anchored variation ⓘ
weighted Koksma–Hlawka inequality ⓘ
holdsFor any dimension s ≥ 1 ⓘ
implies quasi-Monte Carlo can achieve faster convergence than Monte Carlo for smooth low-variation functions ⓘ
influencedDevelopmentOf quasi-Monte Carlo theory ⓘ
involves supremum over axis-aligned boxes for discrepancy ⓘ
isNonProbabilistic true ⓘ
languageOfOriginalWork German ⓘ
mathematicalDomain analysis ⓘ
number theory ⓘ
motivates construction of low-discrepancy sequences ⓘ
namedAfter Edmund Hlawka ⓘ
J. F. Koksma ⓘ
relatedTo Erdős–Turán–Koksma inequality ⓘ
Faure sequence ⓘ
Halton sequence ⓘ
Sobol sequence ⓘ
low-discrepancy sequences ⓘ
relatesConcept discrepancy of point sets ⓘ
quasi-Monte Carlo integration ⓘ
variation of a function ⓘ
statesThat integration error is bounded by the product of variation and discrepancy ⓘ
timePeriod 20th century ⓘ
typicalFormulation | (1/N) Σ_{n=1}^N f(x_n) − ∫_[0,1]^s f(u) du | ≤ V_HK(f) D_N^*(x_1,…,x_N) ⓘ
usedIn analysis of quasi-Monte Carlo algorithms ⓘ
computational finance ⓘ
high-dimensional numerical integration ⓘ
uncertainty quantification ⓘ
usesConcept Hardy–Krause variation ⓘ
star discrepancy ⓘ

How these facts were elicited

Referenced by (8)

Full triples — surface form annotated when it differs from this entity's canonical label.

Johan Frederik Koksma → notableWork → Koksma–Hlawka inequality ⓘ
Johan Frederik Koksma → notableConcept → Koksma inequality ⓘ
linked to: Koksma–Hlawka inequality
Johan Frederik Koksma → notableConcept → Koksma–Hlawka inequality in numerical integration ⓘ
linked to: Koksma–Hlawka inequality
Koksma–Hlawka inequality → hasVariant → weighted Koksma–Hlawka inequality ⓘ
linked to: Koksma–Hlawka inequality
Koksma–Hlawka inequality → hasVariant → Koksma–Hlawka inequality for anchored variation ⓘ
linked to: Koksma–Hlawka inequality
theory of uniform distribution modulo 1 → basedOn → Koksma–Hlawka inequality ⓘ
theory of uniform distribution modulo 1 → hasKeyResult → Koksma–Hlawka inequality ⓘ
theory of uniform distribution modulo 1 → hasApplicationIn → discrepancy theory ⓘ
linked to: Koksma–Hlawka inequality