1

One of the approximations for $\sqrt3$ is $x_{n+1} = \frac{x_{n} + 3}{x_{n} + 1}$. I can see clearly why this is true, since if the sequence converges, $x_{n}$ approaches $x_{n+1}$ (then multiply out). But its really bugging me because I can't find a formal way in which this is derived. I mean does this come from Newton's procedure, the $x_{n+1} = f(x_{n})$ method.. I'm pretty sure this is a stupid question but an answer would be appreciated anyway

jg mr chapb
  • 1,502
  • 1
  • 13
  • 44
  • What do you consider a "normal way"? There is an illustrative explanation as to what Newton's method does and why it works. Specifically for the square root, there is also a geometric interpretation that explains where the recursion comes from. – Dominik Sep 04 '15 at 15:40

2 Answers2

2

By solving a separable ODE we may see that the iteration $x\mapsto\frac{x+3}{x+1}$ is just Newton's iteration for the function:

$$ f(x) = (\sqrt{3}-x)^{\frac{3+\sqrt{3}}{6}}(\sqrt{3}+x)^{\frac{3-\sqrt{3}}{6}}.$$

Jack D'Aurizio
  • 353,855
  • @uranix: I simply solved $$ x-\frac{f(x)}{f'(x)} = \frac{x+3}{x+1} $$ by bringing $x$ on the other side, inverting, integrating both sides and recovering an expression for $\log f(x)$. – Jack D'Aurizio Sep 04 '15 at 15:44
  • 1
    Thank you, Jack, it took me a while to get it – uranix Sep 04 '15 at 15:45
  • 1
    Following this idea every fixed point method $$ x_{n+1} = \varphi(x_n) $$ can be treated as a Newton's method applied to $$ f(x) = \exp\int^x \frac{dx}{x - \varphi(x)} $$ But it seems that quadratic convergence is not guaranteed in this case. That's because the function look like $|x - x_0|^{1-q}$ near the root $x_0$ – uranix Sep 04 '15 at 15:56
  • @uranix: precisely. – Jack D'Aurizio Sep 04 '15 at 16:15
1

There might be no derivation of the method. One could just take a linear fractional mapping $$ x_{n+1} = g(x_n) \equiv \frac{\alpha x_n + \beta}{x_n + \gamma} $$ with random numbers $\alpha, \beta, \gamma$, eventually it either diverges or converges to a solution of the quadratics $$ x^2 + (\gamma - \alpha) x - \beta = 0\\ x_{1,2} = \frac{\alpha - \gamma \pm \sqrt{(\alpha - \gamma)^2 + 4 \beta}}{2}. $$

Synthetically, one might derive the method in the following steps: $$ x^2 = 3\\ x^2 - 1 = 2\\ (x+1)(x-1) = 2 $$ Let the first $x$ be the $x_n$ and the second be the $x_{n+1}$: $$ x_{n+1} = 1 + \frac{2}{x_n + 1} = \frac{x_n + 3}{x_n + 1} $$

It is easy to verify that this method converges linearly with speed $q \approx 0.267$, so it does not behave like a Newton's method applied to a smooth function with a simple root.

uranix
  • 7,503