# The unreasonable effectiveness of Pade approximation

I am trying to get an intuitive feel for why the Pade 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 Pade approximation does do better. So - what explains its "unreasonable effectiveness"?

UPDATE: Here is a graph from p.5 of Pade Approximants, 2nd ed., that illustrates the phenomenon that puzzles me.

-
What do you mean "better" approximation? Do you mean pointwise, $L^1, L^2$ etc ? – john mangual Feb 21 '13 at 18:21
Something to keep in mind is that the rate at which the error of the Taylor series partial sums shrink is closely related to the distance to the nearest pole/singularity from the evaluation point. If the nearest singularity is a pole, then factoring it out improves the convergence rate, since other singularities are (generically) further away. This is essentially what the Padé approximation does. It "guesses" where the nearest poles are and factors them out before proceeding with a Taylor expansion. – Igor Khavkine Feb 21 '13 at 18:41
And indeed, Padé might not be very good if the closest singularity is a branch point rather than a pole. – Robert Israel Feb 21 '13 at 21:20

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}$

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|}$

-
But doesn't the Pade approximant use only a finite section of the series? – Felix Goldberg Feb 21 '13 at 15:34
I don’t see how this answers the question. My reading of it is as follows: since the degree $m/n$ Padé approximant is uniquely determined by $T_{m+n}$, how can it possibly give a better approximation of the original function than $T_{m+n}$? And as far as I can see, the answer is that in general it does not. For example, if the function is a degree $m+n$ polynomial and $n>0$, the truncated Taylor series is exact, whereas the Padé approximant is not. – Emil Jeřábek Feb 21 '13 at 16:35
I am explaining the "unreasonable effectiveness" of the Pade approximation by comparing it to continued fractions. – john mangual Feb 21 '13 at 18:20
John, the point is that if $f$ is a degree $m+n$ polynomial, then $T_{m+n}=f$, whereas $[m/n]_f$ is a different function (if it were a polynomial, it would have degree $m-n< m+n$). Thus, any way of comparing approximations with the property that a function is better approximated by itself than by any other function will do. I guess what I am trying to point out is that the actual meaning of the vague slogan “Padé approximations are best approximations” is different than what I think the OP thinks. The meaning is that $[m/n]_f$ is the best approximation (whatever that means) among rational ... – Emil Jeřábek Feb 21 '13 at 21:05
... functions with degree $m$ and $n$ polynomials in the numerator and denominator (respectively). In contrast, $T_{m+n}$ is the best approximation by a degree $m+n$ polynomial. There is no general reason why one should be better than the other, it all depends on $f$, $m$, $n$, and the chosen method of comparing approximations. – Emil Jeřábek Feb 21 '13 at 21:09