Number of iterations required for $x_n$ to be correct to 100dp

Question

Given $a \in (0.5, 1)$, one seeks to compute $\frac 1a$ using Newton–Raphson method with $$f(x) = a − \frac 1x$$

Taking $x_0 = 1.5$, compute $x_2$ and estimate which $x_n$ is first correct to $100$ decimal places, taking the error as $|ax_k − 1|$

This is part c) of the question, part b) says a=0.7 but I am not sure if that is applicable here.

Also i know that $x_{k+1} = 2x_k - ax_k^2$

I'm really confused by this question because I really don't know what method I should be using. I know I want the error to be less than $1\times 10^{-100}$ but that's about it.

What is the Newton iteration for the given function? Is it really division-free? — Lutz Lehmann, May 17 '17 at 15:28
@LutzL the iteration is xk+1 = 2xk - 2a(xk^2). And I saw your answer to that questions but I am still really unsure about mine — Gragbow, May 17 '17 at 15:42
Please add all already known facts to your question so that it becomes clear what exactly the problem is. $\epsilon_0^{2^n}<0.5·10^{-100}$ or $\epsilon_2^{2^{n-2}}<0.5·10^{-100}$ can be solved for $n$ by taking the logarithm twice. — Lutz Lehmann, May 17 '17 at 16:14

score 0 · Answer 1 · answered May 17 '17 at 16:29

0

You know from some simple computation that $1-ax_{n+1}=(1-ax_n)^2$ and thus by induction $$ |1-ax_n|=|1-ax_0|^{2^n} $$ As $|1-ax_0|\le\frac12$ given your data and $$ \log_2(\log_2(2·10^{100}))=8.380213456543983 $$ one gets a not too large upper bound on the number of steps. Of course, close to $\frac23$ one will need less steps than that.

answered May 17 '17 at 16:29

Lutz Lehmann

126,666

don't understand any of this. But thanks, I'm assuming this is correct – Gragbow May 17 '17 at 16:58
Which part of my data said |1-ax0| < 1/2 ?? I've just done my way and I get the answer to be like 39/40 – Gragbow May 17 '17 at 17:40
With the given interval for $a$ and $x_0=\frac32$, you get $ax_0-1\in [\frac12,1]·\frac32-1=[\frac34,\frac32]-1=[-\frac14,\frac12]$. – Lutz Lehmann May 17 '17 at 18:47

Number of iterations required for $x_n$ to be correct to 100dp

1 Answers1