64
$\begingroup$

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.

Figure 1.1.1 from Baker and Graves-Morris - Padé approximants (source)

$\endgroup$
3
  • 1
    $\begingroup$ What do you mean "better" approximation? Do you mean pointwise, $L^1, L^2$ etc ? $\endgroup$ Feb 21, 2013 at 18:21
  • 46
    $\begingroup$ 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. $\endgroup$ Feb 21, 2013 at 18:41
  • 20
    $\begingroup$ And indeed, Padé might not be very good if the closest singularity is a branch point rather than a pole. $\endgroup$ Feb 21, 2013 at 21:20

5 Answers 5

19
$\begingroup$

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|}\]

$\endgroup$
7
  • 1
    $\begingroup$ But doesn't the Pade approximant use only a finite section of the series? $\endgroup$ Feb 21, 2013 at 15:34
  • 7
    $\begingroup$ 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. $\endgroup$ Feb 21, 2013 at 16:35
  • $\begingroup$ I am explaining the "unreasonable effectiveness" of the Pade approximation by comparing it to continued fractions. $\endgroup$ Feb 21, 2013 at 18:20
  • 2
    $\begingroup$ 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 ... $\endgroup$ Feb 21, 2013 at 21:05
  • 5
    $\begingroup$ ... 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. $\endgroup$ Feb 21, 2013 at 21:09
14
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.