The unreasonable effectiveness of Padé approximation

Question

I am trying to get an intuitive feel for why Padé approximation works so well. Given a truncated Taylor/Maclaurin series it "extrapolates" it beyond the radius of convergence.

But what I can't grasp is how it manages to approximate the original function better than the series itself does, having only "seen" the information present in the series and without having access to the original function. My naive feeling is that if you start with the Taylor series, you can't do better than it in terms of approximation error, only in terms of, say, stability or computation time. But obviously the Padé approximation does do better. So — what explains its "unreasonable effectiveness"?

UPDATE: Here is a graph from p.5 of Baker and Graves-Morris - Padé Approximants, 2nd ed., that illustrates the phenomenon that puzzles me.

(source)

Answer 1

Walter Van Assche gives a modern account of Pade Approximation, a variant of these were used in the proof that e is transcendental.

---

In the case that $f(z)$ is the Cauchy transform of a compactly supported measure $\mu(x)$,

\[ f(z) = \int \frac{1}{z-x} d\mu(x) \]

Then $P_n(x)$ is an orthogonal polynomial with respect to $\mu(x)$ while

\[ Q_{n-1}(z) = \int_a^b \frac{P_n(z) - P_n(x)}{z-x} \, \mu(x) \]

Then we approximate $f(z)$ as a rational function

\[ P_n(z) - f(z) Q_{n-1}(z) = \int_a^b \frac{P_n(x)}{z-x}\, d\mu(x) \]

Then there exists a function $r(z)$ such that the pointwise convergence of the Pade approximants is exponential as we move along the diagonal.

\[ \lim_{n \to \infty} \left| f(z) - \frac{Q_{n-1}(z)}{ P_n(z)}\right|^{1/n} = \frac{1}{r^2} \]

---

ORIGINAL ANSWER

The coefficients of the series $a_1, a_2, a_3, \dots$ are an infinite amount of data. The radius of convergence is a property of this sequence $1/R = \limsup |a_n|^{1/n}$ using the root test.

• The Pade approximation is defined the outside the radius of convergence of the Taylor series

• The Pade $[m/n]_f(x)$ and Taylor approximations $[(m+n)/0]_f(x)$ agree up to order $O(x^{m+n+1})$.

A paper by Hubert S. Wall, dating back to 1929, relates Pade approximants the Stieltjes moment problem and continued fractions.

---

EDIT: My guess is Pade approximant is not always better than Taylor series.

As a counter example let's find $[0/1]_{z+1}$:

\[ z + 1 \approx \frac{1}{1-z} \mod z^2 \]

Taylor series is exact and the 1-1 approximant diverges.

In your example, $\sqrt{\frac{1+\frac{z}{2} }{1+2z}} \to \frac{1}{2}$ for large values and likely the 1,1 approximant does the same, making it a good global fit. The 0,2 or 2,0 approximants will have different global behavior. I was unable to find any precise comparison, overall.

---

---

Continued fractions are known to be "best approximations" in a certain sense.

A best rational approximation to a real number x is a rational number d/n, d > 0, that is closer to x than any approximation with a smaller denominator.

Wikipedia's example is to approximate

\[ 0.84375 = \cfrac{1}{1 + \cfrac{1}{5 + \cfrac{1}{2 + \cfrac{1}{2}}}} = [0;1,5,2,2]\]

We can stop in the middle of this process to get the closes fraction given an upper bound on the denominator.

\[ 0.84375 \approx 1,\frac{5}{6}, \frac{ 11}{13 } , \frac{27}{32}\]

The farey fractions up to denominator 6 are

$$0,\frac{1}{6}, \frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\mathbf{\frac{27}{32}},\frac{5}{6} 1$$

---

Pade approximants are best approximations of functions and can be calculated used a kind of continued fraction.

You get an approximation $\frac{p(x)}{q(x)}$ for given degrees $m = \deg p, n = \deg q$. You are trying to find a polynomial greatest common divisor between your Taylor series and a monomial,

\[ \gcd(T_{m+n}(x), x^{m+n+1} ) \]

You can do this Euclid algorithm doing polynomial long division and taking the remainder at each step:

\[ \frac{p(x)}{q(x)} \equiv T_{m+n}(x) \mod x^{m+n+1} \]

Here is the table for $e^z$ from Wikipedia: (also Pade approximant to exponential function)

\[ \begin{array}{c||c|c|c} & 0 & 1 & 2 \\\\ \hline \hline 0 & \frac{1}{1} & \frac{1}{1-z} & \frac{1 }{1 - z + \frac{1}{2}z^2 } \\\\ \hline 1 & \frac{1+z}{1} & \frac{1+ \frac{1}{2} z}{ 1- \frac{1}{2} z} & \frac{1 + \frac{1}{3}z }{ 1 - \frac{2}{3}z + \frac{1}{6}z^2 } \\\\ \hline 2 & \frac{1 - z + \frac{1}{2}z^2 }{1 } & \frac{ 1 - \frac{2}{3}z + \frac{1}{6}z^2 }{1 + \frac{1}{3}z } & \frac{ 1+ \frac{1}{2} z + \frac{1}{12} z^2}{ 1- \frac{1}{2} z + \frac{1}{12} z^2 } \end{array} \]

---

Let's try to work out the steps for m=2, n=2 (not in Wikipedia). This involves the GCD of the 4th Taylor polynomial $1 + z + \frac{1}{2}z^2 + \frac{1}{6}z^3 + \frac{1}{24}z^4$ and $z^{5}$.

\[ \frac{1}{24} z^5 = (z-4)\left(1 + z + \frac{1}{2}z^2 + \frac{1}{6}z^3 + \frac{1}{24}z^4\right) + \left(4 + 3z + z^2 + \frac{1}{6}z^3 \right) \]

\[ 1 + z + \frac{1}{2}z^2 + \frac{1}{6}z^3 + \frac{1}{24}z^4 = \left( \frac{1}{4}z - \frac{1}{2} \right)\left( 4 + 3z + z^2 + \frac{1}{6}z^3 \right) + \left( 3 + \frac{3}{2}z + \frac{1}{4}z^2 \right) \]

\[ 4 + 3z + z^2 + \frac{1}{6}z^3 = \frac{2}{3}z \left( 3 + \frac{3}{2}z + \frac{1}{4}z^2 \right) + (z+4) \]

\[ 3 + \frac{3}{2}z + \frac{1}{4}z^2 = \left( \frac{1}{4}z + \frac{1}{2}\right)(z+4) + 1\]

Using the 1st two long divisions, we get the (2,2) Pade approximant.

\[ 1 + z + \frac{1}{2}z^2 + \frac{1}{6}z^3 + \frac{1}{24}z^4 \approx \frac{ 3 + \frac{3}{2}z + \frac{1}{4}z^2 }{(z-4) \left( \frac{1}{4}z - \frac{1}{2} \right)+1 } = \frac{ 1+ \frac{1}{2} z + \frac{1}{12} z^2}{ 1- \frac{1}{2} z + \frac{1}{12} z^2 } \]

---

Alternatively compare coefficients of your rational approximation and polynomial $a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 \approx \frac{p_0 + p_1 x + p_2 x^2}{q_0 + q_1 x + q_2 x^2 } $ Then you can solve the system of equations: \begin{eqnarray*} a_0 &=& p_0 \\\\ a_1 + a_0 q_1 &=& p_1 \\\\ a_2 + a_1 q_1 + a_0 q_2 &=& p_2 \\\\ a_3 + a_2 q_1 + a_1 q_0 &=& 0 \\\\ a_4 + a_3 q_1 + a_2 q_0 &=& 0 \end{eqnarray*}

Cramer rule gives you the correct fraction at the end:

\[ \frac{ \left|\begin{array}{ccc} a_1 & a_2 & a_3 \\\\ a_2 & a_3 & a_4 \\\\ a_0 x^2 & a_0 x + a_1 x^2 & a_0 + a_1 x + a_2 x^2 \end{array} \right|} { \left|\begin{array}{ccc} a_1 & a_2 & a_3 \\\\ a_2 & a_3 & a_4 \\\\ x^2 & x & 1 \end{array} \right|} = \frac{ \left|\begin{array}{ccc} 1 & 1/2 & 1/6 \\\\ 1/2 & 1/6 & 1/24 \\\\ x^2 & x + x^2 & 1 + x + \frac{1}{2} x^2 \end{array} \right|} { \left|\begin{array}{ccc} 1 & 1/2 & 1/6 \\\\ 1/2 & 1/6 & 1/24 \\\\ x^2 & x & 1 \end{array} \right|}\]

Answer 2

The function used in the example has an asymptotic value of $1/2$ as $x\to \infty$

A Maclaurin expansion will only either go to infinity or negative infinity as x goes to infinity. In order to match for a little while, different powers of x have to be balanced, but that balance won't last for long.

The thing that makes Pade's expansion incredible is that a Pade expansion can match the asymptotic behavior of functions like the one given. A simple approximation like $$y=\frac{1+x}{1+2x}$$ will approach the same asymptotic and at about the same rate.

Answer 3

Your intuition is correct but the quality of any approximation lies with the remainder (of the truncated series). Pade's approx. will not be better than Taylor's in the vicinity of the approximated point (e.g. around x = a). However, the remainder/error term diverges fast the farther we are from x = a. For Taylor expansion truncated at the nth term it diverges as (x-a)^(n+1)! For pade expansion it also diverges but at much slower rate. This is why it is considered “better than” Taylor’s expansion.

Answer 4

There is plenty of mathematics, eg. by D.J. Newman, to show that analytic functions on a neighborhood of the disk can be approximated extremely well on the disk by rational functions. The pade approximation to the exponential function at zero does exceptionally well. Just because there is a power series definition of $\exp$ does not make it the best choice. For example, the $\exp$ function has no zeroes. The polynomial of degree $k$ has $k$ zeros. The pade approximation has $k/2$ zeros and poles. Turns out they are better positioned.

Why does anyone think a power series approximation that touches to maximal degree somehow do better than a rational approximation with a similar maximal touching?

Answer 5

My intuition is based on a few things. One, Pade approximants are a generalization of the Taylor series, in that by finding the Pade approximate of a rational function from its Taylor series, one might actually find the the exact rational function itself, which is not possible with Taylor series. Second, this accounts for singularities since the approximations are rational and third, if a function tends to a specific value one can use the $n/n$ approximant to obtain accurate global behavior or, if it tends to that value and then diverges from it after a while, still the approximant covers that behavior also. I think the added value comes not from the coefficient information but from the information of the cleverness put in by Pade himself. Sometimes mathematical restructuring is information enough itself.