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