For which $k$ we have: $|x_k-\alpha|\le10^{-16}|\alpha|$ where $\alpha$ is a solution of the equation $10x-\sin x=3$?

Question

Let iterative method which is determined by the formula $x_{n+1}=\frac{\sin (x_n)+3}{10}$ for $x_0=0.33$. For which $k$ we have: $|x_k-\alpha|\le10^{-16}|\alpha|$ where $\alpha$ is a solution of the equation $10x-\sin x=3$?

The iterative function is $F(x)=\frac{\sin (x)+3}{10}$. Let $e_k=|x_k-\alpha|$. $$e_{k+1}=|x_{k+1}-\alpha|=|F(x_k)-F(\alpha)|=|F'(\theta)|\cdot|x_k-\alpha| \text{ for } \theta \text{ between }x_k,\alpha $$ So: $|x_k-\alpha|=\frac{|x_{k+1}-\alpha|}{|F'(\theta)|}$ and we want to $\frac{|x_{k+1}-\alpha|}{|F'(\theta) \alpha|}\le10^{-16}.$

However I don't know how I can calculate $k$ because $\frac{\sin (x_k)+3-10\alpha}{\cos (\theta) \alpha}\le 10^{-16}$ is difficult to estimate...

Answer 1

We can estimate $|F(x) - F(y)| \le |x - y|/10$, so certainly $|x_k - \alpha| \le 10^{-k} |x_0 - \alpha|$. That will give us a rough (but not very big) bound, and if we want a more exact number we can compute a few iterations.

Answer 2

As Robert Israel answered, a good idea would be to perform a few iterations (this is quite easy with a spreadsheet).

Let me be very lazy perrforming four iterations with $$x_{n+1}=\frac{\sin (x_n)+3}{10}\qquad \text{with} \qquad x_0=0.33\qquad \text{and} \qquad \Delta_n=x_{n+1}-x_{n}$$ Below are the results (I included the logarithm of $\Delta_n$ since it is a typical parameter for the order of convergence)) $$\left( \begin{array}{cccc} n & x_n & \Delta_n & \log_{10}( \Delta_n) \\ 0 & 0.330000 & 2.4043 \times 10^{-3} & -2.61901 \\ 1 & 0.332404 & 2.2736 \times 10^{-4} & -3.64328 \\ 2 & 0.332632 & 2.1491 \times 10^{-5} & -4.66775 \\ 3 & 0.332653 & 2.0313 \times 10^{-6} & -5.69223 \\ 4 & 0.332655 & 1.9199 \times 10^{-7} & -6.71672 \end{array} \right)$$

Plotting $\log_{10}( \Delta_n)$ as a function of $n$ reveals an almost perfect linear relation. A quick and dirty linear regression gives $$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ a & -2.61892 & 0.000075 & \{-2.61925,-2.61860\} \\ b & -1.02444 & 0.000031 & \{-1.02457,-1.02430\} \\ \end{array}$$

So, let us use $$\log_{10}( \Delta_n)=-2.61892-1.02444\,n$$ Using if for $10^{-16}$ leads to $n = 13.0619$ so, more than likely $n=14$.

Just to check, let us continue the rigorous calculation of the sequences and effectively $$\log_{10}( \Delta_{13})=-15.9546\qquad \text{and} \qquad \log_{10}( \Delta_{14})=-16.9616$$