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:


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.


  1. Oscar Veliz, Fixed point Iteration,
  2. Recalculation in Excel 2002,
  3. Multithreaded recalculation in Excel,

No comments:

Post a Comment