A recursive algorithm for the infinity-norm fixed point problem
We present the PFix algorithm for the fixed point problem f (x) = x on a nonempty domain [a, b], where d greater than or equal to 1, a, b epsilon R-d and f is a Lipschitz continuous function with respect to the infinity norm, with constant q less than or equal to 1. The computed approximation (x) over tilde satisfies the residual criterion parallel tof ((x) over tilde) - (x) over tilde parallel to (infinity) less than or equal toepsilon, where epsilon > 0. In general, the algorithm requires no more than Sigma(i=1)(d) s(i) function component evaluations, where s equivalent to [ max(1, log(2) parallel tob - aparallel to(infinity) /epsilon))] +1 . This upper bound has order O([log(2)(d) as epsilon-->0. For the domain [0, 1] with epsilon infinity (epsilon-->0) and O(d(r+1)/r+1)!) as d-->infinity. We show that when q  1 the absolute criterion problem has infinite worst-case complexity when information consists of function evaluations. Finally, we report several numerical tests in which the actual number of evaluations is usually much smaller than the upper complexity bound. (C) 2003 Elsevier Inc. All rights reserved.
fixed point bisection algorithm computational complexity lipschitz functional