Class ConvergenceRateEstimator

Class Documentation

class ConvergenceRateEstimator

Convergence test for a linearly converging iteration that measures the change between successive iterates.

For such an iteration the error is about change / (1 - rho), with rho the convergence rate, so a change passes a tolerance tol when change < tol (1 - rho).

The rate is estimated as the larger of the last two ratios of successive changes, so that one unusually small ratio of an irregularly converging (for example, accelerated) iteration does not end it early; it is zero for the first change. A relative change below the round-off level kRoundoffRelativeChange always passes.

An accelerated iteration can also take a single step that barely changes the iterate while its error is still large. Converged() therefore tests the larger of the latest change and the change expected from the previous one, rho times the previous change.

Public Functions

double Update(double change)

Records the change of the latest iteration and returns the rate estimate, in [0, 1].

inline double GetRate() const

Rate estimate after the last Update().

bool Passes(double change, double tolerance, double roundoff_change = kRoundoffRelativeChange) const

Whether change passes tolerance at the current rate estimate.

A change below roundoff_change, the round-off level of the measured change, passes regardless; the default suits relative changes, and a caller measuring an absolute change passes its own level.

bool Converged(double tolerance, double roundoff_change = kRoundoffRelativeChange) const

Whether the iteration has converged to tolerance: the larger of the latest change and the change expected from the previous one passes it, with roundoff_change as in Passes().

Public Static Attributes

static double kRoundoffRelativeChange = 100.0 * std::numeric_limits<double>::epsilon()

Relative change below which successive iterates differ only by round-off.