From: rusin@olympus.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Quotient of two Polynomials
Date: 24 Aug 1995 14:04:44 GMT
In article <41h54d$1js@sun0.urz.uni-heidelberg.de>,
Pol-Bernard Gossiaux wrote:
>
>Given P1(x) of degree > P2(x), and let say, to make life easier
> that I know the zero's of P2(x) and their multiplicity as well,
> is there a formula that gives the quotient of P1(x)/P2(x).
> I am not talking about the brute method that consist by eliminating
> degree after degree of P1(x) by just looking at each step to the
> appropriate factor. No, I would like a close - one line formula.
Um, how about ...=P1/P2 ?
No, I think I understand the problem: you want to avoid long
division for some reason and in exchange you're willing to assume
you know something extra about P2 (its factorization into linear factors).
Well, here's an alternative (I don't really claim it's better than long
division, just different in the required sense). You can form the Taylor
series of P1 around each root a of P2, say
P1(x) = P1(a) + P1'(a)*(x-a) + ...
(You can either continue all the way until the derivatives drop to zero,
or stop after the powers of (x-a) exceed the multiplicity of a as
a root of P2, including of course an error term divisible by a large
power of (x-a).) If P1 is written in this form, its's trivial
to divide by a (x-a)^r, and in particular if you're only interested in
the quotient, not the remainder, you need only retain the terms of
high degree in (x-a).
Now iterate: if P2(x) = c* Prod (x-a_i)^(r_i), then P1/P2 may be
computed by dividing by (x-a_1)^(r_1) as above, then dividing the
quotient by (x-a_2)^(r_2), and so on. It takes a little checking of
degrees to convince yourself that in order to know the final
quotient it suffices to retain only the quotient at each step.
Observe that if after the first stage, for example, you have a
quotient of the form
quotient(P1(x) / (x-a)^r ) = b1 + b2 (x-a) + b3 (x-a)^2 + ...
then in the next stage it's easy to compute the Taylor series as above:
the value at a' of the i-th derivative of (x-a)^j is
(j)(j-1)...(j-i+1)*(a'-a)^(j-i).
Of course your final answer will be expressed as a power series in
(x-a), where a is the last root of P2 which you consider. If you
want a polynomial in standard form, you'll want to compute this
answer's Taylor series around zero.
Seems to me that if the degrees of the polynomials are d1 and d2
then in the generic case of no repeated factors in P2, you're
going to need d1*d2 iterations of the procedure, "differentiate a
polynomial and plug in a value of x." Keeping in mind the number of
summands in the polynomials to differentiate, it looks like
you'll run through something on the order of d1^2*d2 steps (assuming
d1 > d2). Clearly this is inferior to long division if d2 is almost
as large as d1, but of the same order of magnitude if d1 is much
larger than d2.
dave
==============================================================================
From: israel@math.ubc.ca (Robert Israel)
Newsgroups: sci.math
Subject: Re: Quotient of two Polynomials
Date: 24 Aug 1995 18:35:24 GMT
In article <41h54d$1js@sun0.urz.uni-heidelberg.de>, gossiaux@goofy.mpi-hd.mpg.de (Pol-Bernard Gossiaux) writes:
|> Given P1(x) of degree > P2(x), and let say, to make life easier
|> that I know the zero's of P2(x) and their multiplicity as well,
|> is there a formula that gives the quotient of P1(x)/P2(x).
|> I am not talking about the brute method that consist by eliminating
|> degree after degree of P1(x) by just looking at each step to the
|> appropriate factor. No, I would like a close - one line formula.
|> I looked in several books. Lots of things are said about the remainder,
|> but few about the quotient itself.....
Well, if you write x = 1/t, what you want are the terms in t^n for n <= 0 in the Laurent series of P1(1/t)/P2(1/t). Suppose P2(x) = product_{j=1}^d2 (x - rj)
where rj are the roots (repetitions allowed), and P1(x) = sum_{j=0}^d1 aj x^j.
Then 1/(1/t - rj) = sum_{k=1}^infinity t^k rj^(k-1), so
P1(1/t)/P2(1/t) = sum r1^(k1-1) r2^(k2-1) ... rd2^(kd2-1) aj t^(k1+k2+...+kd2-j)
(sum ranging over all k1, k2, ... kd2 from 1 to infinity and j from 0 to d1).
The t^n terms are those with j=k1+k2+...+kd2-n. Since j <= d1 and n <= 0 we
restrict the sum to k1 + k2 + ... + kd2 <= d1. Thus we take k1 from 1 to
d1 - (d2-1), k2 from 1 to d1-k1-(d2-2), etc.
e.g. for P1(x) = x^8 - 2 x + 3 and P2(x) = (x-2)(x-3)(x-4) we have
Q(x) = sum_{k1=1}^6 sum_{k2=1}^{7-k1} sum_{k3=1}^{8-k1-k2} sum_{j=k1+k2+k3}^8
2^(k1-1) 3^(k2-1) 4^(k3-1) aj x^(j-k1-k2-k3)
5 4 3 2
= x + 9 x + 55 x + 285 x + 1351 x + 6069
Well, it didn't make it into one line, but it was close...
--
Robert Israel israel@math.ubc.ca
Department of Mathematics (604) 822-3629
University of British Columbia fax 822-6074
Vancouver, BC, Canada V6T 1Y4