FixedPoint

Iterates f from x until the result no longer changes.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageFixedPoint✓↗

FixedPoint(f, x, maxIterations?)iterates $f$ starting from $x$ until two successive values are equal, or for at most $maxIterations$ steps.

Typed signatures

Type	Package	Applies
(function, initial: any, maxIterations: integer?) -> unknown	combinatoricsreplaces compute-engine	always
(function, initial: any, maxIterations: integer?) -> unknown	compute-engine	always

Domain: Collections

Details

• compute-engine's own $FixedPoint$ does the iterating. Two successive values are the same when they are structurally identical or, for a float, agree to the working precision. It stays unevaluated when the iteration cannot converge: a value that nests the previous one, an exact number that gains digits at every step, or the default iteration limit reached without settling. A given maxIterations returns the last value instead, as Wolfram's does.
• An inexact iteration runs with ten guard digits past the engine's precision and the answer is rounded back to it, so every printed digit is right: the last step of a convergent iteration is off by a few times the stopping gap, which at the engine's own precision would reach the last digit or two.
• Newton's method for $\sqrt{2}$ on an exact rational start gains digits at every step, so it never settles and the call stays unevaluated (Wolfram aborts there too). The two exact-rational examples show the call coming back unevaluated.

Examples

Basic #

Halving and flooring until nothing changes

live ↗

In$\mathrm{FixedPoint}(\operatorname{\_1}↦\lfloor\frac{\operatorname{\_1}}{2}\rfloor, 100)$Out$0$

The Dottie number, the fixed point of cos

live ↗

In$\mathrm{FixedPoint}(\cos, 0.5)$Out$0.739\,085\,133\,215\,160\,641\,655$

Known value · mpmath 1.3.0 at 40 digits (cos iterated to its fixed point)

Iterating $n \mapsto 1 + \lfloor n/2 \rfloor$ from $1000$ settles at $2$

live ↗

In$\mathrm{FixedPoint}(\operatorname{\_1}↦1+\lfloor\frac{\operatorname{\_1}}{2}\rfloor, 1\,000)$Out$2$

live ↗

In$\mathrm{FixedPoint}(\operatorname{\_1}↦\frac{\operatorname{\_1}+\frac{2}{\operatorname{\_1}}}{2}, 1)$Out$\mathrm{FixedPoint}(\operatorname{\_1}↦\frac{\operatorname{\_1}+\frac{2}{\operatorname{\_1}}}{2}, 1)$

Scope #

A start a thousand times larger lands on the same fixed point in a few more steps

live ↗

In$\mathrm{FixedPoint}(\operatorname{\_1}↦1+\lfloor\frac{\operatorname{\_1}}{2}\rfloor, 10^6)$Out$2$

No step is taken when the start is already fixed

live ↗

In$\mathrm{FixedPoint}(\operatorname{\_1}↦\lfloor\frac{\operatorname{\_1}}{2}\rfloor, 0)$Out$0$

Applications #

Newton's method for $\sqrt{2}$, run to this engine's default precision

live ↗

In$\mathrm{FixedPoint}(\operatorname{\_1}↦\frac{\operatorname{\_1}+\frac{2}{\operatorname{\_1}}}{2}, 1.5)$Out$1.414\,213\,562\,373\,095\,048\,8$

Known value · mpmath 1.3.0 at 40 digits (sqrt(2))

Differentiating $x^{10}$ repeatedly bottoms out at $0$, the derivative's fixed point

live ↗

In$\mathrm{FixedPoint}(\operatorname{\_1}↦\frac{\mathrm{d}\operatorname{\_1}}{\mathrm{d}x}, x^{10})$Out$0$

Properties #

live ↗

In$\mathrm{FixedPoint}(x↦\frac{x+\frac{2}{x}}{2}, 1)$Out$\mathrm{FixedPoint}(x↦\frac{x+\frac{2}{x}}{2}, 1)$

live ↗

In$\mathrm{FixedPoint}(\operatorname{\_1}↦\mathrm{ReplaceAll}(\operatorname{\_1}, \bigl\lbrack\mathrm{Rule}(a, b), \mathrm{Rule}(b, c), \mathrm{Rule}(c, d)\bigr\rbrack), a^2+c^3)$Out$d^3+d^2$

About

Examples	10
Checked against	Wolfram Language 8 agree2 error
Crosswalk	Wolfram Language

See also: Nest, NestList