Convergence of partial inverses

The question of convergence of the different iterators can be partially answered. For functions with two occurrences of the unknown, $\char93 _x(f)=2$, in general either one or the other derived iterator converges. This is proven as follows.

Let f(x₁,x₂)=0 be the equation to be solved, identifying each occurrence of x by x₁ and x₂. Let F_i(x) be the iterator derived from inverting f on x_i. Formally this means that

f(F₁(x),x) = 0

and

f( x, F₂(x) ) = 0

Let $\alpha$ be a root of f, $f(\alpha,\alpha)=0$. The convergence of the iterators depends on $\vert F_i' (\alpha)\vert < 1$. By computing derivatives with respect to x of the above identities, we find

$$f_1'(\alpha,\alpha) F_1'(\alpha) + f_2'(\alpha,\alpha) = 0$$

$$f_1'(\alpha,\alpha) + f_2'(\alpha,\alpha) F_2'(\alpha) = 0$$

For this system of equations to have a non-null solution in $f_i'(\alpha,\alpha)$, its determinant must be zero, or

$$\left \vert \begin{array}{cc} F_1'(\alpha) & 1 \\ 1 & F_2'(\... ...a) \end{array} \right \vert = F_1'(\alpha) F_2'(\alpha) -1 = 0$$

and from this

$$\vert F_1'(\alpha) \vert = 1 / \vert F_2'(\alpha) \vert$$

So unless both absolute values are equal to one, then one iterator converges while the other diverges. This is a very encouraging result, it guarantees that one of the iterators will succeed for each of the roots.

For $\char93 _x(f) = k > 2$ the results are much weaker. For general x, the condition becomes

$$\left \vert \begin{array}{cccc} F_1'(\alpha) & 1 & \cdots & 1... ...1}{F_i'(\alpha)-1} \right ) \prod_{i=1}^k (F_i'(\alpha)-1) = 0$$

Then, if k-1 of the values $F_i'(\alpha) > 1$, the remaining one must be between 0 and 1 and hence the corresponding iterator converges. This does not guarantee convergence for every case, as all $F_i'(\alpha) = 1-k$, i.e. $\vert F_i'(\alpha)\vert = k-1 > 1$is also a possible solution and in this case all iterators will diverge.

The above theorem for two occurrences, strongly suggests that grouping variables (if possible) while building the iterators, is a good strategy.