## Sunday, November 6, 2016

### 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