Fixed-point computation: Difference between revisions

Revision as of 22:51, 16 July 2024

Revision as of 22:52, 16 July 2024

Line 22:

A Lipschitz-continuous function with constant <math>L</math> is called '''[[contractive]]''' if <math>L<1</math>; it is called '''[[weakly-contractive]]''' if <math>L\le 1</math>. Every contractive function satisfying Brouwer's conditions has a ''unique'' fixed point. Moreover, fixed-point computation for contractive functions is easier than for general functions.

[[File:Fixed point anime.gif|alt=computing a fixed point using function iteration|thumb|Computing a fixed point using function iteration]]

The first algorithm for fixed-point computation was the '''[[fixed-point iteration]]''' algorithm of Banach. [[Banach fixed point theorem|Banach's fixed-point theorem]] implies that, when fixed-point iteration is applied to a contraction mapping, the error after <math>t</math> iterations is in <math>O(L^t)</math>. Therefore, the number of evaluations required for a <math>\delta</math>-relative fixed-point is approximately <math>\log_L(\delta) = \log(\delta)/\log(L) = \log(1/\delta)/\log(1/L) </math>. Sikorski and Wozniakowski<ref name=":5">{{cite journal |last1=Sikorski |first1=K |last2=Woźniakowski |first2=H |title=Complexity of fixed points, I |journal=Journal of Complexity |date=December 1987 |volume=3 |issue=4 |pages=388–405 |doi=10.1016/0885-064X(87)90008-2 |doi-access=free }}</ref> showed that Banach's algorithm is optimal when the dimension is large. Specifically, when <math>d\geq \log(1/\delta)/\log(1/L) </math>, the number of required evaluations of ''any'' algorithm for <math>\delta<\/math>-relative fixed-point is larger than 50% the number of evaluations required by the iteration algorithm. Note that when <math>L<\/math> approaches 1, the number of evaluations approaches infinity. No finite algorithm can compute a <math>\delta<\/math>-absolute fixed point for all functions with <math>L=1</math>.<ref name=":4">{{cite book |last1=Sikorski |first1=Krzysztof A. |title=Optimal Solution of Nonlinear Equations |date=2001 |publisher=Oxford University Press |isbn=978-0-19-510690-9 }}{{page needed|date=April 2023}}</ref>

When ''L'' < 1 and ''d'' = 1, the optimal algorithm is the '''Fixed Point Envelope''' (FPE) algorithm of Sikorski and Wozniakowski.<ref name=":5" /> It finds a ''δ''-relative fixed point using <math>O(\log(1/\delta) + \log \log(1/(1-L))) </math> queries, and a ''δ''-absolute fixed point using <math>O(\log(1/\delta)) </math> queries. This is faster than the fixed-point iteration algorithm.<ref>{{cite book |doi=10.1007/978-1-4615-9552-6_4 |chapter=Fast Algorithms for the Computation of Fixed Points |title=Robustness in Identification and Control |year=1989 |last1=Sikorski |first1=K. |pages=49–58 |isbn=978-1-4615-9554-0 }}</ref>

When <math>d>1<\/math> but not too large, and <math>L\le 1<\/math>, the optimal algorithm is the interior-ellipsoid algorithm (based on the [[ellipsoid method]]).<ref>{{cite journal |last1=Huang |first1=Z |last2=Khachiyan |first2=L |last3=Sikorski |first3=K |title=Approximating Fixed Points of Weakly Contracting Mappings |journal=Journal of Complexity |date=June 1999 |volume=15 |issue=2 |pages=200–213 |doi=10.1006/jcom.1999.0504 |doi-access=free }}</ref> It finds an {{mvar|ε}}-residual fixed-point using <math>O(d\cdot \log(1/\varepsilon)) </math> evaluations. When <math>L<1<\/math>, it finds a <math>\delta<\/math>-absolute fixed point using <math>O(d\cdot [\log(1/\delta) + \log(1/(1-L))]) </math> evaluations.

Shellman and Sikorski<ref>{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=A Two-Dimensional Bisection Envelope Algorithm for Fixed Points |journal=Journal of Complexity |date=June 2002 |volume=18 |issue=2 |pages=641–659 |doi=10.1006/jcom.2001.0625 |doi-access=free }}</ref> presented an algorithm called '''BEFix''' (Bisection Envelope Fixed-point) for computing an {{mvar|ε}}-residual fixed-point of a two-dimensional function with '<math>L\le 1<\/math>, using only <math>2 \lceil\log_2(1/\varepsilon)\rceil+1</math> queries. They later<ref>{{cite journal |last1=Shellman |first1=Spencer |last2=Sikorski |first2=K. |title=Algorithm 825: A deep-cut bisection envelope algorithm for fixed points |journal=ACM Transactions on Mathematical Software |date=September 2003 |volume=29 |issue=3 |pages=309–325 |doi=10.1145/838250.838255 |s2cid=7786886 }}</ref> presented an improvement called '''BEDFix''' (Bisection Envelope Deep-cut Fixed-point), with the same worst-case guarantee but better empirical performance. When <math>L<1<\/math>, '''BEDFix''' can also compute a <math>\delta<\/math>-absolute fixed-point using <math>O(\log(1/\varepsilon)+\log(1/(1-L)))</math> queries.

Shellman and Sikorski<ref name=":3" /> presented an algorithm called '''PFix''' for computing an {{mvar|ε}}-residual fixed-point of a ''d''-dimensional function with ''L ≤'' 1, using <math>O(\log^d(1/\varepsilon))</math> queries. When ''L'' < 1, '''PFix''' can be executed with <math>\varepsilon = (1-L)\cdot \delta</math>, and in that case, it computes a δ-absolute fixed-point, using <math>O(\log^d(1/[(1-L)\delta]))</math> queries. It is more efficient than the iteration algorithm when ''L'' is close to 1. The algorithm is recursive: it handles a ''d''-dimensional function by recursive calls on (''d''-1)-dimensional functions.