Jean-Michel Muller's Iteration - consequences of rounding errors
Scaling (with 2x): x = -2 ... 5:
Iteration: (not defined if x=0 or y=0)
F(x,y) = (y, a+b+c - (ab+bc+ca - abc/x) /y )
Fixed points: (a,a), (b,b), (c,c)
Invariant curves:
y = a+b - ab/x (magenta/green)
y = b+c - bc/x, y = c+a - ca/x (red)
The red curves are attracting for (c,c)
and repelling for (a,a), (b,b)
the magenta/green curve is attracting
for (b,b) and repelling für (a,a).
Because of rounding errors in floating point
computations, iterated points cannot stay on
the magenta/green curve and converge to (b,b).
Eventually all points are attracted by (c,c),
just wait until Start/Stop stops!
For rational points on y = a+b - ab/x one can
write code which uses arbitrarily large integers
and allows the iteration to converge to (b,b).
No program iterates (pi, a+b-ab/pi) correctly.
Berkeley University used this iteration to allert students to the consequences
of rounding errors in floating point computations. It is easy to check that the
Muller iteration can be expressed on the invariant curves by far simpler formulas,
for example on the magenta/green curve by (x,y) --> (y, a+b - ab/x). Of course,
if one computes with these formulas, iterated points stay on the invariant curves,
without rounding errors showing up. But Muller's original iteration iterates all
points - except the fixed points (a,a) und (b,b) - eventually to (c,c).
in most computers real numbers are represented as binary numbers with finitely many
digits (e.g. 64 bit). This is not even exact for all rational numbers and has rounding
errors for all irrational numbers. Most real numbers are in fact transcendental, which
implies that there is no way to exactly compute with them.