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