# Iterative Root Finding

Consider a function $f(x)=g(x,h(x))$, which we know has a unique root $x^*$. The functions $f$, $g$ and $h$ are all continuous in $x$ and behave nicely. Iteratively solving $g(x_{i+1}, h(x_i))=0$ with some starting guess $x_0$, we are able to find $x^*$.

My goal is to prove that this iteration indeed works. Can one give simple sufficient conditions on $f$, $g$ and $h$, that would indeed guarantee convergence? I guess this is a pretty high level question, but perhaps people can point me in the right direction.

Example. $f(x)=x^2+\log[x]$ and take $h(x)=x^2$, then $x_{i+1}=\exp[-x_{i}^2]$ will converge to $x^*=0.652919$ for any $x_0\in \mathbb{R}$.

• Is this a contraction mapping? – Bill Bradley Nov 16 '15 at 13:14
• For some maps, if you are really unlucky, it might be that the starting point is in the Julia set of your function, meaning it will not converge at all. This is of course in general very unlikely, but even finding roots of a cubic using Newton-Raphson is not guaranteed to work for ANY starting point. – Per Alexandersson Nov 16 '15 at 14:06
• @PerAlexandersson minor nitpick: I think you mean "every" not "any" – Suvrit Nov 16 '15 at 14:14
• @Suvrit: Right, I think I made a negation in my head that only makes sense mathematically but not English-wise: the negation of "any (one point you prefer) starting point converges" is not "not 'any starting point converges' " – Per Alexandersson Nov 16 '15 at 19:04

Slightly generalizing, we may state conditions in terms of $G(x,y):=g(x,h(y))$. For instance:

Let $G$ be a continuous function on $\mathbb{R}^2$. Assume that the equation $G(x,x)=0$ has a unique solution $x^*$ and that for some $M$ any solution of $G(x,y)=0$ verifies $y\le x\le M$. Then any sequence $(x_i)$ such that $G(x_{i+1}, x_i)=0$ does converge to $x^*$.

Indeed by assumption the sequence $x_i$ must be increasing and bounded, thus convergent, and by continuity of $G$, its limit is a solution of $G(x,x)=0$, hence it's $x^*$.

Here is a variant producing oscillating sequences.

Let $G$ be a continuous function on $\mathbb{R}^2$. Assume that the system $G(x,y)=G(y,x)=0$ has a unique solution (necessarily with $x=y:=x^*$, otherwise $(y,x)$ would be a second solution). Assume further that any solution to the system $G(x,y)=G(y,z)=0$ verifies either $z \le x\le y$ or $y\le x\le z$. Then any sequence $(x_i)$ such that $G(x_{i+1}, x_i)=0$ does converge to $x^*$.

Indeed it follows by induction from the assumptions that any such sequence $(x_i)$ either verifies $$x_0\le x_2\le x_4\le \dots \le x_5\le x_3\le x_1$$ or $$x_1\le x_3\le x_5\le \dots \le x_4\le x_2\le x_0;$$ in any case, the subsequences $x_{2i}$ and $x_{2i+1}$ converge respectively to $x$ and $y$ solving $G(x,y)=G(y,x)=0$, hence $x=y=x^*$, so the whole sequence $(x_i)$ converges to $x^*$.

• Not sure if I understand your answer. Suppose $G(x,y)=y^2-2x+1$, then $x_{i+1}=\frac{1}{2}(x_i^2+1)$, which does not converge to $x^*=1$ for $x_0=2$ (but $G$ does satisfy your property?) – MthQ Nov 16 '15 at 15:39
• In this case $G$ does not, because for any $M$ the zero set of $G$ meets the region $\{x>M, y>M\}$. – Pietro Majer Nov 16 '15 at 20:02
• The preceding statement was wrong, so I edited and changed it. Now is correct, though more trivial. – Pietro Majer Nov 17 '15 at 0:47