Iterative Root Finding

Question

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

Answer 1

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^*$.