1

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.

guitarphish
  • 495

1 Answers1

0

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?

user58697
  • 2,761
  • 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? – guitarphish Jul 07 '19 at 00:08
  • 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$? – user58697 Jul 07 '19 at 00:30
  • 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. – guitarphish Jul 07 '19 at 00:36