Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) No edit summary |
||
Line 29:
Shellman and Sikorski<ref name=":3" /> presented an algorithm called PFix for computing an {{mvar|ε}}-residual fixed-point of a ''d''-dimensional function with Lipschitz constant ''L''=1, using <math>O(\log^d(1/\varepsilon))</math> queries. When ''L''<1, PFix can also compute a δ-absolute fixed-point, using <math>O(\log^d(1/[(1-L)\delta]))</math> queries (that is: a similar complexity but with <math>\varepsilon = (1-L)\cdot \delta</math>).
=== Algorithms for differentiable functions ===
When the function ''f'' is differentiable, and the algorithm can evaluate its derivative (not only ''f'' itself), the [[Newton's method in optimization|Newton method]] can be used and it is much faster.<ref>{{Cite journal |last=Kellogg |first=R. B. |last2=Li |first2=T. Y. |last3=Yorke |first3=J. |date=September 1976 |title=A Constructive Proof of the Brouwer Fixed-Point Theorem and Computational Results |url=http://epubs.siam.org/doi/10.1137/0713041 |journal=SIAM Journal on Numerical Analysis |language=en |volume=13 |issue=4 |pages=473–483 |doi=10.1137/0713041 |issn=0036-1429}}</ref><ref>{{Cite journal |last=Smale |first=Steve |date=1976-07-01 |title=A convergent process of price adjustment and global newton methods |url=https://www.sciencedirect.com/science/article/pii/0304406876900197 |journal=Journal of Mathematical Economics |language=en |volume=3 |issue=2 |pages=107–120 |doi=10.1016/0304-4068(76)90019-7 |issn=0304-4068}}</ref>
| |||