1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Is this a contraction mapping? $\endgroup$ Nov 16, 2015 at 13:14
  • $\begingroup$ 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. $\endgroup$ Nov 16, 2015 at 14:06
  • 1
    $\begingroup$ @PerAlexandersson minor nitpick: I think you mean "every" not "any" $\endgroup$
    – Suvrit
    Nov 16, 2015 at 14:14
  • $\begingroup$ @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' " $\endgroup$ Nov 16, 2015 at 19:04

1 Answer 1

1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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?) $\endgroup$
    – MthQ
    Nov 16, 2015 at 15:39
  • $\begingroup$ In this case $G$ does not, because for any $M$ the zero set of $G$ meets the region $\{x>M, y>M\}$. $\endgroup$ Nov 16, 2015 at 20:02
  • $\begingroup$ The preceding statement was wrong, so I edited and changed it. Now is correct, though more trivial. $\endgroup$ Nov 17, 2015 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.