Order of convergence of the sequence $\{x_n\}_{n=0}^{\infty }$ given by $x_{n+1}=2x_n-\pi {x_n}^2$ with $x_0=1/3$

I would like to find the exact order of convergence of the sequence $\{x_n\}_{n=0}^{\infty }$ given by $x_{n+1}=2x_n-\pi {x_n}^2$ with $x_0=1/3$.

I found that the limit of the sequence is $\frac{1}{\pi }$.

But, I'm not sure if this method of finding the order of convergence is right.

I gave it a try as follows.

At first, I let $F(h)=2h-\pi h^2+\frac{1}{\pi }$ so that $\lim_{h\rightarrow 0}F(h)=\frac{1}{\pi }$.

Get a Taylor expansion of $F(h)$ at $0$, then $$F(h)=F(0)+F'(0)h+F''(0)\frac{h^2}{2 } + O(h^3) \\ =\frac{1}{\pi }+2h-\pi h^2 + O(h^3) = F(h)+O(h^3) $$

Thus, the order of convergence is $O(h^3)$.

Is this the right method?

Any help would be appreciated.

Solution 1:

The iteration $x_{n+1}=2x_n-ax_n^2$ can be quadratically completed to $$ (1-ax_{n+1})=(1-ax_n)^2, $$ and from that one can directly conclude the order of convergence.

If you are examining the convergence at $\frac1\pi$, then the basis point for the Taylor expansion has to be $\frac1\pi$, not zero. Or you need to correctly insert $x_n=\frac1\pi+h$. If $x_{n+1}=g(x_n)$ and $x_*$ is the limit, then you need to find the $p$ in $g(x_*+h)=x_*+O(h^p)$.

Solution 2:

It's more convenient to make some substitutions that reduce the problem to a simpler one.

First, since you know that the limit is $\pi$, write $x_n = \pi y_n$, We get the recurrence

$$y_{n+1} = 2 y_n - y_n^2$$

Now, we know that $\lim y_n = 1$. So write $y_n = z_n+1$. We get $z_{n+1} + 1 = 2( z_n + 1) - (z_n+1)^2$, or

$$z_{n+1} = - z_n^2$$ Moreover, $z_0 = \frac{1}{3\pi} -1 \in (-1, 0)$, so $z_n\to 0$. The convergence is quadratic.

Solution 3:

This does not add to @LutzLehmann 's answer, it is based in the same Taylor expansion. If a recursion of the type $x_{n+1} = g(x_n)$ is converging to some $z$ and $g$ is regular enough then, if $$ g'(z) = \cdots = g^{(p-1)}(z) = 0, \quad g^{(p)}(z) \ne 0 $$

you can conclude that $(x_n)$ converges to $z$ with order $p$. In this case, since $g'(1/\pi) = 0$ and $g''(1/\pi)\ne 0$, the order of convergence is 2.