What are Padé approximants and how are they used for series acceleration?

Question

I read an article about series acceleration on Wikipedia. I found in the non-linear acceleration section that Padé approximants can be used for series acceleration. But I am not able to understand what it is, and how it accelerates series. For understanding purposes, can someone explain to me with an example of the Leibniz series for $\pi$?

Answer 1

I'll assume you know the basics of Taylor/MacLaurin series expansion.

The Leibniz formula for $\pi$ (or rather, $\pi/4$) is obtained from substiuting $x=1$ into $$ f(x):=\arctan x=x-\frac13x^3+\frac15x^5-\frac17x^7+\dots $$ So we will try to find a way of accelerating the convergence of this series by replacing the partial sum $$ S_n=f_n(1),\quad f_n(x)=\sum_{j=0}^n \frac{(-1)^j}{2j+1}x^{2j+1} $$ by something which looks like $f_n$ for small enough $x$, namely the Padé approximants $[m/n]_f$ and taking appropriate subsequences of the doubly-indexed $([m/n]_f(1))_{m,n}$. Now there are various ways to do this, some better than others. However, it is probably a good idea to try to do it via some diagonal-ish way, so let's try $[n+1/n]_f$, the numerator having one higher degree than the denominator since $\arctan x\approx x$ is a reasonably good first approximation.

Padé approximants are quite efficiently computed by the Wynn's $\varepsilon$-algorithm: initialize $$ \varepsilon^{(n)}_{-1}=0, \varepsilon^{(n)}_0=f_n,\quad n=0,1,2,\dots $$ and compute $$ \varepsilon^{(n)}_{k+1}=\varepsilon^{(n-1)}_{k-1}+\big[\varepsilon^{(n+1)}_k-\varepsilon^{(n)}_k\big]^{-1} $$ Then $\varepsilon^{(n)}_{2k}=[n+k/k]_f$.

So we obtain, for example, \begin{align*} [1/0]_f&=x\\ [3/2]_f&=\frac{105x+40x^3-4x^5}{105+75x^2}\\ [5/4]_f&=\frac{945 x + 735 x^3 + 64 x^5}{945 + 1050 x^2 + 225 x^4}\\ [7/6]_f&=\frac{15015 x + 19250 x^3 + 5943 x^5 + 256 x^7}{15015 + 24255 x^2 + 11025 x^4 + 1225 x^6} \end{align*} which gives us approximations of $\pi$: $$ \begin{array}{c|c|c} [m/n] & 4[m/n]_f(1) & \text{rel. error}\\\hline [1/0] & 4 & 27.3\%\\ [3/2] & \frac{19}{6} = 3.166666666\dots&0.798\%\\ [5/4] & \frac{1744}{555} = 3.142342342\dots&0.024\%\\ [7/6] & \frac{2529}{805} = 3.141614906\dots&0.001\% \end{array} $$

Similarly, if you want to start at a higher degree numerator, we have \begin{align*} [3/0]_f&=x-\frac13x^3\\ [5/2]_f&=\frac{105x+40x^3-4x^5}{105+75x^2}\\ [7/4]_f&=\frac{10395x + 9765x^3 + 1344x^5 - 64x^7}{10395 + 13230x^2 + 3675x^4}\\ [9/6]_f&=\frac{225225x + 330330x^3 + 128205x^5 - 256x^7 + 9216x^9}{225225 + 405405x^2 + 218295x^4 - 33075x^6} \end{align*} and $$ \begin{array}{c|c} [m/n] & 4[m/n]_f(1)\\\hline [3/0] & \frac{8}{3}=2.666666666\dots\\ [5/2] & \frac{47}{15} = 3.133333333\dots\\ [7/4] & \frac{4288}{1365} = 3.141391941\dots\\ [9/6] & \frac{4948}{1575} = 3.141587301\dots \end{array} $$