contraction

A function that always shrinks the distance between two inputs by at least some fixed fraction k < 1 -- the property that makes fixed-point iteration provably converge.

A function $g$ is a contraction on an interval if there is a constant $k<1$ with $|g(x)-g(y)| \le k|x-y|$ for every $x,y$ in the interval; equivalently, when $g$ is differentiable, if $|g'(x)|\le k<1$ throughout. The constant $k$ is the contraction constant. A fixed-point iteration built from a contraction on an interval that $g$ maps into itself is guaranteed to converge to the unique fixed point in that interval, regardless of the starting value chosen inside it.

Examples

$g(x)=\cos x$ has $|g'(x)|=|\sin x|\le1$ everywhere, and strictly less than 1 away from $x=0$ , so it's a contraction on any interval bounded away from where $\sin x=1$ .