Rational polynomial from coefficents

93 Views Asked by At

Given two polynomials

$$ p(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_{n-1}x^{n-1} \\ q(x) = b_0 + b_1 x + b_2 x^2 + \ldots + b_{n}x^{n} $$

And the series expansion from their rational polynomial

$$ \frac{p(x)}{q(x)} = c_0 + c_1 x + c_2 x^2 + \ldots $$

is it possible to recover the the original polynomials $a_n$, $b_n$ from only the series $c_n$ via the solution of a linear system?

3

There are 3 best solutions below

2
On

Not uniquely. Keep in mind that $\frac{p(x)}{q(x)} = \frac{p(x)r(x)}{q(x)r(x)}$.

Also, the system of equations you would get wouldn't be linear. For instance, the first three terms, taking $b_0=1$, would be

$$ a_0 = c_0\\a_1-a_0b_1=c_1\\a_2-a_1b_1-a_0b_2+a_0b_1^2=c_2 $$

3
On

Assuming that you do not know the degrees of $p$ and $q$ beforehand, and you can look at only finitely many coefficients $c_i$, this is quite hopeless. Indeed given any $k$ initial terms of the sequence and any guess for $q$ (say with constant term $1$ to facilitate the inverse), you can just multiply out to find the first $k$ terms of $p$, say it stops there, and perform the division to find a possibility for the remaining terms of the series. They will probably not match with what you've got, but it shows that after looking at any finite piece of the series, you cannot exclude much.

On the other hand, the polynomial $q$ describes a linear recurrence relation that is satisfied ultimately by the coefficients of the series (since the coefficients of $p$ have to stop somewhere). If you can get your hands on such a recurrence (but this requires knowing the whole series), you have a candidate for $q$.

0
On

The rational function can be recovered via Padé approximation, computable by the extended Euclidean algorithm. Follow the link for details.