A Two-Dimensional Bisection Envelope Algorithm for Fixed Points

In this paper we present a new algorithm for the two-dimensional fixed point problem f(x)=x on the domain 0, 1]×0, 1], where f is a Lipschitz continuous function with respect to the infinity norm, with constant 1. The computed approximation x satisfies 6f(x)−x6_∞⩽ε for a specified tolerance ε<0.5. The upper bound on the number of required function evaluations is given by 2⌈log₂(1/ε)⌉+1. Similar bounds were derived for the case of the 2-norm by Z. Huang et al. (1999, J. Complexity15, 200–213), our bound is the first for the infinity norm case.