How can a transform a polynomial to another coordinate system?

Question

Using assorted matrix math, I've solved a system of equations resulting in coefficients for a polynomial of degree 'n'

Ax^(n-1) + Bx^(n-2) + ... + Z

I then evaulate the polynomial over a given x range, essentially I'm rendering the polynomial curve. Now here's the catch. I've done this work in one coordinate system we'll call "data space". Now I need to present the same curve in another coordinate space. It is easy to transform input/output to and from the coordinate spaces, but the end user is only interested in the coefficients [A,B,....,Z] since they can reconstruct the polynomial on their own. How can I present a second set of coefficients [A',B',....,Z'] which represent the same shaped curve in a different coordinate system.

If it helps, I'm working in 2D space. Plain old x's and y's. I also feel like this may involve multiplying the coefficients by a transformation matrix? Would it some incorporate the scale/translation factor between the coordinate systems? Would it be the inverse of this matrix? I feel like I'm headed in the right direction...

Update: Coordinate systems are linearly related. Would have been useful info eh?

Answer 1

You have the equation:

y = Ax^(n-1) + Bx^(n-2) + ... + Z

In xy space, and you want it in some x'y' space. What you need is transformation functions f(x) = x' and g(y) = y' (or h(x') = x and j(y') = y). In the first case you need to solve for x and solve for y. Once you have x and y, you can substituted those results into your original equation and solve for y'.

Whether or not this is trivial depends on the complexity of the functions used to transform from one space to another. For example, equations such as:

5x = x' and 10y = y'

are extremely easy to solve for the result

y' = 2Ax'^(n-1) + 2Bx'^(n-2) + ... + 10Z

Answer 2

If the input spaces are linearly related, then yes, a matrix should be able to transform one set of coefficients to another. For example, if you had your polynomial in your "original" x-space:

ax^3 + bx^2 + cx + d

and you wanted to transform into a different w-space where w = px+q

then you want to find a', b', c', and d' such that

ax^3 + bx^2 + cx + d = a'w^3 + b'w^2 + c'w + d'

and with some algebra,

a'w^3 + b'w^2 + c'w + d' = a'p^3x^3 + 3a'p^2qx^2 + 3a'pq^2x + a'q^3 + b'p^2x^2 + 2b'pqx + b'q^2 + c'px + c'q + d'

therefore

a = a'p^3

b = 3a'p^2q + b'p^2

c = 3a'pq^2 + 2b'pq + c'p

d = a'q^3 + b'q^2 + c'q + d'

which can be rewritten as a matrix problem and solved.

Answer 3

If I understand your question correctly, there is no guarantee that the function will remain polynomial after you change coordinates. For example, let y=x^2, and the new coordinate system x'=y, y'=x. Now the equation becomes y' = sqrt(x'), which isn't polynomial.

Answer 4

Tyler's answer is the right answer if you have to compute this change of variable z = ax+b many times (I mean for many different polynomials). On the other hand, if you have to do it just once, it is much faster to combine the computation of the coefficients of the matrix with the final evaluation. The best way to do it is to symbolically evaluate your polynomial at point (ax+b) by Hörner's method:

• you store the polynomial coefficients in a vector V (at the beginning, all coefficients are zero), and for i = n to 0, you multiply it by (ax+b) and add C_i.
• adding C_i means adding it to the constant term
• multiplying by (ax+b) means multiplying all coefficients by b into a vector K₁, multiplying all coefficients by a and shifting them away from the constant term into a vector K₂, and putting K₁+K₂ back into V.

This will be easier to program, and faster to compute.

Note that changing y into w = cy+d is really easy. Finally, as mattiast points out, a general change of coordinates will not give you a polynomial.

Technical note: if you still want to compute matrix T (as defined by Tyler), you should compute it by using a weighted version of Pascal's rule (this is what the Hörner computation does implicitely):

t_i,j = b t_i,j-1 + a t_i-1,j-1

This way, you compute it simply, column after column, from left to right.