# Library for finding fixed points of a function?

**URL:** <https://discourse.julialang.org/t/library-for-finding-fixed-points-of-a-function/8932>\
**Category:** General Usage\
**Created:** [February 8, 2018, 11:14pm UTC](https://discourse.julialang.org/t/library-for-finding-fixed-points-of-a-function/8932 "2018-02-08T23:14:37Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![jlperla](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlperla/32/34332_2.png) [@jlperla](https://discourse.julialang.org/u/jlperla)\
**Post date:** [February 8, 2018, 11:14pm UTC](https://discourse.julialang.org/t/library-for-finding-fixed-points-of-a-function/8932/1 "2018-02-08T23:14:37Z")

</div>

A large number of algorithms in my field involve finding the fixed point of an operator. Are there any good libraries out there that do this (i.e. properly generic, testing out corner cases, etc.) Of course, a simple version of this can be written within the algorithm itself, but I would rather train students to think things through mathematically, and having a library means fancier methods could be used in the future for the fixed point iteration. (Mathematica’s version is [FixedPoint—Wolfram Language Documentation](http://reference.wolfram.com/language/ref/FixedPoint.html) but I don’t think it gives enough control on the norm, in my opinion).

Is there anything? An example of a mediocre example of what I am interested in is below

```julia
function fixedpoint(f, x0; residualnorm = (x -> norm(x,Inf)), tol = 1E-10, maxiter=100)    
    residual = Inf
    iter = 1
    xold = x0
    while residual > tol && iter < maxiter
        xnew = f(xold)        
        residual = residualnorm(xold - xnew);
        xold = xnew
        iter += 1
    end
    return xold
end

#Calling it
f(x) = 0.5 * x + 1.0
fixedpoint(f, 1.0)

```

In terms of other stuff I might expect in the library: Anderson acceleration and Newton’s method of fixed point iteration would be great (where the latter might use AD).

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [February 8, 2018, 11:20pm UTC](https://discourse.julialang.org/t/library-for-finding-fixed-points-of-a-function/8932/2 "2018-02-08T23:20:25Z")

</div>

NLsolve.jl. It has an Andersson acceleration method. But also, `f(x)=x` means that `g(x) = f(x)-x = 0` is a rootfinding problem, so that’s how you’d use Newton’s method on that.

---

<div class="post-metadata">

**Author:** ![jlperla](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlperla/32/34332_2.png) [@jlperla](https://discourse.julialang.org/u/jlperla)\
**Post date:** [February 8, 2018, 11:23pm UTC](https://discourse.julialang.org/t/library-for-finding-fixed-points-of-a-function/8932/3 "2018-02-08T23:23:22Z")

</div>

But nothing standard you know of solves a standard iterative fixed point problem (assuming a contraction mapping, etc.)?

I believe Haskell also has this sort of thing ([Haskell/Fix and recursion - Wikibooks, open books for an open world](https://en.wikibooks.org/wiki/Haskell/Fix_and_recursion) but I could be wrong). Seems like the sort of thing that could really belong in the standard library for Julia, if a suitable library doesn’t already exist.

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [February 8, 2018, 11:26pm UTC](https://discourse.julialang.org/t/library-for-finding-fixed-points-of-a-function/8932/4 "2018-02-08T23:26:45Z")

</div>

> [@jlperla](#):
>
> But nothing standard you know of solves a standard iterative fixed point problem (assuming a contraction mapping, etc.)?

No, I mentioned NLsolve.jl has Anderson acceleration for this.

> **[GitHub - JuliaNLSolvers/NLsolve.jl: Julia solvers for systems of nonlinear...](https://github.com/JuliaNLSolvers/NLsolve.jl#anderson-acceleration)**
>
> Julia solvers for systems of nonlinear equations and mixed complementarity problems - GitHub - JuliaNLSolvers/NLsolve.jl: Julia solvers for systems of nonlinear equations and mixed complementarity ...

But if you want Newton, just do `x->f(x)-x`. Maybe ask for a convenience function if necessary but I think showing students how to make use of a rootfinder for fixed point acceleration is a simple (and common) enough trick that they should know or learn it. That trick is probably a good part (a) to a HW problem IMO 🙂.

---

<div class="post-metadata">

**Author:** ![antoine-levitt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/antoine-levitt/32/4008_2.png) [@antoine-levitt](https://discourse.julialang.org/u/antoine-levitt)\
**Post date:** [February 9, 2018, 7:21am UTC](https://discourse.julialang.org/t/library-for-finding-fixed-points-of-a-function/8932/5 "2018-02-09T07:21:28Z")

</div>

Note the two very different notions of fixed point: there’s the fixed point of a numerical function (with floats and tolerances, which seems to be what you’re interested in) and there’s the fixed point as a programming/theoretical language construct, see eg [Fixed-point combinator - Wikipedia](https://en.wikipedia.org/wiki/Fixed-point_combinator). One is about numbers, the other about expressions (as far as I understand)

If you really want the pure iteration xn+1 = f(xn) and you don’t want to do it by hand for some reason, you can use NLSolve’s Anderson acceleration and just set the history parameter to 0.

---

<div class="post-metadata">

**Author:** ![jlperla](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlperla/32/34332_2.png) [@jlperla](https://discourse.julialang.org/u/jlperla)\
**Post date:** [February 9, 2018, 5:03pm UTC](https://discourse.julialang.org/t/library-for-finding-fixed-points-of-a-function/8932/6 "2018-02-09T17:03:07Z")

</div>

Good point on fixed points of expressions. In mathematica the expressions and computations are tough to separate, so you can use them for both.