Algorithm 848: A recursive fixed-point algorithm for the infinity-norm case

ABSTRACT

We present the PFix algorithm for approximating a fixed point of a function f that has arbitrary dimensionality, is defined on a rectangular domain, and is Lipschitz continuous with respect to the infinity norm with constant 1. PFix has applications in economics, game theory, and the solution of partial differential equations. PFix computes an approximation that satisfies the residual error criterion, and can also compute an approximation satisfying the absolute error criterion when the Lipschitz constant is less than 1. For functions defined on all rectangular domains, the worst-case complexity of PFix has order equal to the logarithm of the reciprocal of the tolerance, raised to the power of the dimension. Dividing this order expression by the factorial of the dimension yields the order of the worst-case bound for the case of the unit hypercube. PFix is a recursive algorithm, in that it uses solutions to a d-dimensional problem to compute a solution to a (d + 1)-dimensional problem. A full analysis of PFix may be found in Shellman and Sikorski [2003b], and a C implementation is available through ACM ToMS.

REFERENCES

• 1: Eugene L. Allgower , Kurt Georg, Numerical continuation methods: an introduction, Springer-Verlag New York, Inc., New York, NY, 1990
• 2: Eaves, B. 1972. Homotopies for computation of fixed points. Math. Programm. 3, 1, 1--22.
• 3: Eaves, B. and Saigal, R. 1972. Homotopies for computation of fixed points on unbounded regions. Math. Programm. 3, 2, 225--237.
• 4: M. D. Hirsch , C. H. Papadimitriou, Exponential lower bounds for finding Brouwer fixed points, Journal of Complexity, v.5 n.4, p.379-416, Dec. 1989 [doi>10.1016/0885-064X(89)90017-4]
• 5: Z. Huang , L. Khachiyan , K. Sikorski, Approximating fixed points of weakly contracting mappings, Journal of Complexity, v.15 n.2, p.200-213, June 1999 [doi>10.1006/jcom.1999.0504]
• 6: A. S. Nemirovsky, On optimality of Krylov's information when solving linear operator equations, Journal of Complexity, v.7 n.2, p.121-130, June 1991 [doi>10.1016/0885-064X(91)90001-E]
• 7: Nemirovsky, A. 2000. Private communication.
• 8: Scarf, M. 1967. The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math. 15, 1328--1343.
• 9: Spencer Shellman , K. Sikorski, A two-dimensional bisection envelope algorithm for fixed points, Journal of Complexity, v.18 n.2, p.641-659, June 2002 [doi>10.1006/jcom.2001.0606]
• 10: Spencer Shellman , K. Sikorski, Algorithm 825: A deep-cut bisection envelope algorithm for fixed points, ACM Transactions on Mathematical Software (TOMS), v.29 n.3, p.309-325, September 2003 [doi>10.1145/838250.838255]
• 11: Spencer Shellman , K. Sikorski, A recursive algorithm for the infinity-norm fixed point problem, Journal of Complexity, v.19 n.6, p.799-834, December 2003 [doi>10.1016/j.jco.2003.06.001]
• 12: Krzysztof A. Sikorski, Optimal solution of nonlinear equations, Oxford University Press, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Performance

Keywords:
Fixed points, Fixed-points algorithms, economics, game theory, nonlinear partial differential equations