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}$.



Iterative Root Finding
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^\*$.


