Okay so given this simple looking fixed point iteration, i.e., $x_{n+1}=g(x_n)$

$$ x_{n+1} = g(x) = -b - \frac{c}{x_n}$$

The idea is to find a region in the space of $(b,c) \in \mathbb{R^2}$ that will converge for all good starting points $x_0$ (ones that are relatively close to $x$) with the error being reduced by more than $1/2$ on each iteration, in other words the iteration is $\mathcal{O}(1/2^n)$.

I understand the brute force way of computing all the possible combinations, which my computer is working on, checking the error and then plotting the points that fit the criteria on a 2-D plot. It seems like there should be a way to figure this out more concisely, I envisage there is a way to take partials of $g(x)$ or optimize a potential of some sort or other and figure out the region analytically.


Step 1: If the iteration does converge, it would converge to some equilibrium point of $x_{n+1} = -b - \dfrac{c}{x_{n}}$, which is a root of $x = -b - \dfrac{c}{x}$.

That is, possible convergence points would be $\dfrac{-b \pm \sqrt{b^2 - 4c}}{2}$.

Step2: fix one of them, say $X = \dfrac{-b + \sqrt{b^2 - 4c}}{2}$, and consider $\epsilon_{n} = x_{n} - X$. Compute $\epsilon_{n+1}$. Obviously it depends on $x_{n}$, and you want $|\epsilon_{n+1}| < |\dfrac{\epsilon_{n}}{{2}}|$. This is a condition for $x$s you are looking for.

Can you continue?

  • $\begingroup$ This doesn't seem to be any different than the brute force method. It looks like your saying pick a bunch of b's and c's and then compute? $\endgroup$ – guitarphish Jul 7 at 0:08
  • $\begingroup$ I very well might misread your question. Are you interested in $b,c$ pairs for which an iteration converges fast for certain $x$, or, given $b,c$ you are interested in an initial $x$? $\endgroup$ – user58697 Jul 7 at 0:30
  • $\begingroup$ Interested in b,c pairs. You can assume a good x to start with. When I programmed a program to do this I had to find a good starting x with a bisection method and then compute for every possible pair of b,c (well, not every possible pair, but a lot) how fast the iteration converges for that pair and then check if the error is getting cut in half each iteration or not. Pretty straight forward, but lots of computing. $\endgroup$ – guitarphish Jul 7 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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