9
$\begingroup$

Let $a_0=3$ and $a_n=a_{n-1}+\sin a_{n-1}$. Then $$\pi =\lim_{n\to\infty}a_n.$$

I encountered this algorithm a long time ago and don't remember where. It converges very quickly, which I found fascinating (digits agreeing with $\pi$ are in green): $$\begin{align}a_1&\approx\color{green}{3.141}12,\\ a_2&\approx\color{green}{3.1415926535}722,\\ a_3&\approx \color{green}{3.14159265358979323846264338327950}19.\end{align}$$

Why does it compute $\pi$? And why is the convergence so fast?

$\endgroup$
1

3 Answers 3

Reset to default
9
$\begingroup$

You are iterating the function $f(x) = x + \sin(x)$. This is a nondecreasing function because $f'(x) = 1 + \cos(x) \ge 0$, and it has fixed points at multiples of $\pi$. If $x_0 < x_1 = f(x_1)$, we will have $x_i < x_{i+1}$ for all $i$. Since it is bounded above (by the next fixed point), it has a limit, and that limit can only be a fixed point. Similarly, if $x_i > x_{i+1}$ the sequence decreases to a limit at a fixed point. The fixed points for which $f'(x) = 0$ (namely the odd multiples of $\pi$) are stable. For $x$ near $k \pi$ where $k$ is odd, the Taylor series says $$ f(x) \approx k \pi + \frac{(x - k \pi)^3}{6}$$ so the "error" in the next iteration is approximately $1/6$ the cube of the error in this iteration. That makes it converge very rapidly.

$\endgroup$
6
$\begingroup$

You're solving $\sin x=0$ which has a root at $\pi$. The fixed point iteration converges cubically due to $x+\sin x$ having the first two derivatives equal to zero at the root, hence the rapid convergence.

Now the bad news. You don't have the value of the sine function for free. The function is transcendental, and its calculation requires an unbounded number of arithmetic operations as you seek greater accuracy. Therefore the efficiency of this method is lost if you seek $\pi$ to millions or more decimal places where mathematicians are working with that constant. To maintain efficiency in high-accuracy computations requires a more subtle approach.

$\endgroup$
5
  • $\begingroup$ I see. By the way, is this algorithm computationally slower than the famous Gauss–Legendre algorithm for $\pi$? That one requires an unbounded number of arithmetic operations as well (because of the square roots of non-perfect squares) but its convergence is only quadratic. $\endgroup$ Commented Aug 9, 2020 at 23:08
  • 1
    $\begingroup$ I do not know. Square roots are more tractable because they are algebraic and thus amenable by Newton's Method (which works very well for that function) So the slower nominal convergence of the G-L method could conceal faster convergence in terms of arithmetic operations. Maybe this is another question to be answered by those more knowledgeable on numerical methods. $\endgroup$ Commented Aug 9, 2020 at 23:14
  • 1
    $\begingroup$ @sting890 Roughly speaking, computing $\sin(a_n)$ to $d$ digits will require (slightly less than) $d$ terms computed to $d$ digits if one uses the Maclaurin series. Computing the square root to $d$ digits requires roughly $\log_2(d)$ evaluations if one uses Newton's method, which is significantly faster. $\endgroup$ Commented Aug 9, 2020 at 23:39
  • $\begingroup$ @SimplyBeautifulArt So do the $\log_2 d$ evaluations compensate for the quadratic convergence, as contrasted to the cubic convergence, and make the Gauss–Legendre algorithm computationally faster than the sine algorithm? $\endgroup$ Commented Aug 9, 2020 at 23:57
  • 1
    $\begingroup$ @sting890 If one were to simply use standard methods for computing these things, then yes. I could see the $\sin$ being much faster to compute in this instance if you used Taylor expansions centered about the previous point (though this requires the previous point to be computed to desired accuracy). Likewise, the initial approximation for Newton's method in the GL method can be taken from the computations, since they likewise have quadratic convergence. I think with such optimizations the GL will still be faster though. $\endgroup$ Commented Aug 10, 2020 at 0:20
3
$\begingroup$

Part 1: Prove $0<a_n<\pi,$ for all $n.$

Part 2: Thus $\{a_n\}$ is increasing with an upper bound, and hence has a limit, $a.$

Part 3: But $a$ must satisfy $0<a\leq\pi$ and $a=a+\sin a.$ So $a=\pi.$

I’ll prove part 1, and leave the rest to you.

We will use that $0<\sin x<x$ if $0<x<\pi.$

We prove part 1 by induction.

We know it is true for $a_0=3.$

Also $$\begin{align}a_{n}&=a_{n-1}+\sin(a_{n-1})\\&=a_{n-1}+\sin(\pi-a_{n-1})\\&<a_{n-1}+\pi-a_{n-1}=\pi\end{align}$$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.