1

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.

john
  • 1,268
  • 1
    Did you actually check that the limit is $1/\pi$? Or did you just noticed that * if the limit exists* it must be $1/\pi$? – PierreCarre Dec 14 '21 at 09:44
  • @PierreCarre Limit is either $0$ or $1/ \pi$ equation-wise. But, setting the interval $[1/5,1/ \pi ]$ did give me that the limit of the sequence is $1/ \pi$ – john Dec 14 '21 at 09:50
  • 1
    That does not show that the sequence converges... It just identifies the possible limits. To show convergence you can for instance use the fixed point theorem on the interval $[\frac{1}{\pi}, \frac 13]$. – PierreCarre Dec 14 '21 at 10:26
  • @PierreCarre Ah, many thanks for pointing it out. I picked the wrong interval. However, according to my textbook, I need $g(x) \in [a,b]$ for all $x \in [a,b]$ where $[a,b]$ contains the starting point to use the theorem. My textbook's theorem also doesn't hold with your interval. I think $ [1/5,1/3]$ works. – john Dec 14 '21 at 10:53
  • 1
    Yes, you are correct. Maybe a more natural interval would be $[\frac 14, \frac 13]$, as $3<\pi<4$. – PierreCarre Dec 14 '21 at 10:58

3 Answers3

3

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.

orangeskid
  • 53,909
  • 2
    What is "super-exponential" convergence? Did you mean "super-linear"? One could also just simply say "quadratic". – Lutz Lehmann Dec 14 '21 at 07:09
  • 1
    @Lutz Lehmann: something that converges like $\frac{1}{q^{2^n}}$ for some $|q|<1$. SInce the $\log$ of the inverse grows like an exponential itself. Yeah, I am not sure how to call it. From $1/n^2$, to $1/2^n$, to $1/2^{n^2}$, to $1/2^{2^n}$ there is a wide difference. quadratic convergence is just like $1/n^2$ , no? – orangeskid Dec 14 '21 at 07:14
  • 2
    When speaking of "order of convergence", then order $p$ is $q^{p^n}$, quadratic with $p=2$. The naming convention is more traditional than exact, relates more to the error iteration, here the quadratic iteration for $z_n$. – Lutz Lehmann Dec 14 '21 at 07:18
  • 1
    @Lutz Lehmann: Oh I see, thanks for the info, I will revise the answer! – orangeskid Dec 14 '21 at 07:23
3

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)$.

Lutz Lehmann
  • 126,666
2

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.

PierreCarre
  • 20,974
  • 1
  • 18
  • 34