Excel Recalculation: Fixed Point Iterations

When we have circular references in our Excel spreadsheet, we can have Excel do a (large) number of iterations in the hope this converges to a solution. Mathematically speaking we could say this is like:

$$x_{i,j} := f_{i,j}(X)$$

where $x_{i,j}$ is the cell in row $i$ and column $j$. This will converge to a fixed point:

$$X = F(X)$$

if the stars are aligned. Of course we can look at this as if we are solving a system of non-linear equations:

$$G(X)=F(X)-X=0$$

For a project, I am looking at some spreadsheets that have a few hundred thousand of such formulas.

Convergence can be a problem for a scheme like this. Below is a nice example of solving the equation $x^2-x-1=0$ using two different fixed point iteration schemes:

1. $x_{(k+1)} := 1 +\displaystyle\frac{1}{x_{(k)}}$, this one converges
2. $x_{(k+1)} := \displaystyle\frac{1}{x_{(k)}-1}$, this one diverges
3. $x_{(k+1)} :=  x^2_{(k)} - 1$, also diverges

Details in the YouTube video below:

Note that we can interpret a Newton algorithm as a fixed point iteration:

$$x_{(k+1)} := x_{(k)} – \frac{f(x_{(k)})}{f’(x_{(k)})}$$

See (2) and (3) for more information how Excel does these recalculations.

References

1. Oscar Veliz, Fixed point Iteration, https://www.youtube.com/watch?v=OLqdJMjzib8
2. Recalculation in Excel 2002, https://msdn.microsoft.com/en-us/library/aa140058
3. Multithreaded recalculation in Excel, https://msdn.microsoft.com/en-us/library/office/bb687899.aspx