Here is a screenshot from the book. Can you help me with understanding the last line with this approximation? I don't understand how it follows from the formula. Where the denominator has gone?:)
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
If $a_n \to \sqrt{\beta} = \alpha$, then $b_n = a_n - \alpha \to 0$ as $n \to \infty$. So the recurrence simplifies to $$b_n \approx \frac{b_{n-1}^2}{2\alpha},$$ which you should read as a recurrence on the deviation of $a_n$ from $\alpha$: the size of that deviation decreases quadratically with each additional step; that is to say, the precision of the approximation roughly doubles for each iteration.
-
$\begingroup$ Thank you. Yes, I didn't realize that the sign of approximate equality was used instead of proportionality sign. :) $\endgroup$– StanFeb 19, 2015 at 6:18
$\begingroup$
$\endgroup$
1
The denominator is $b_{n-1}+\alpha$. Since $b_n \to \alpha$, this tends to $2\alpha$.
Therefore $b_n \approx \frac{b_{n-1}^2}{4\alpha} $.
Your reference wanted to show that $b_n$ converges quadratically to $\sqrt{\beta}$, and ignored the approximate constant of $\frac1{4\sqrt{\beta}}$. The convergence is still quadratic no matter what constant is there in $b_n \approx c b_{n-1}^2$, but I can see why you were confused.
answered Feb 19, 2015 at 5:58
-
$\begingroup$ Great! Thank you. Looks like mr. Sedgewick skipped half of the reasoning. :) $\endgroup$– StanFeb 19, 2015 at 6:15