如何将多项式转换为另一个坐标系?

时间:2022-07-03 11:33:09

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

使用各种矩阵数学,我已经求解了一个方程组,得到了度数'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.

然后我在给定的x范围内调整多项式,基本上我正在渲染多项式曲线。现在这里是抓住了。我已经在一个我们称之为“数据空间”的坐标系中完成了这项工作。现在我需要在另一个坐标空间中呈现相同的曲线。很容易将输入/输出转换为坐标空间和从坐标空间转换输入/输出,但最终用户只对系数[A,B,....,Z]感兴趣,因为它们可以自己重建多项式。如何呈现第二组系数[A',B',......,Z'],它们代表不同坐标系中相同的形状曲线。

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...

如果它有帮助,我在2D空间工作。简单的旧x和y。我也觉得这可能涉及将系数乘以变换矩阵?它是否会包含坐标系之间的比例/平移因子?它会与此矩阵相反吗?我觉得我朝着正确的方向前进......

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

更新:坐标系与线性相关。本来有用的信息呃?

5 个解决方案

#1


4  

The problem statement is slightly unclear, so first I will clarify my own interpretation of it:

问题陈述有点不清楚,所以首先我要阐明自己对它的解释:

You have a polynomial function

你有一个多项式函数

f(x) = Cnxn + Cn-1xn-1 + ... + C0

f(x)= Cnxn + Cn-1xn-1 + ... + C0

[I changed A, B, ... Z into Cn, Cn-1, ..., C0 to more easily work with linear algebra below.]

[我将A,B,... Z改为Cn,Cn-1,...,C0,以便更容易使用下面的线性代数。]

Then you also have a transformation such as:   z = ax + b   that you want to use to find coefficients for the same polynomial, but in terms of z:

然后你还有一个变换,例如:z = ax + b,你想用它来找到相同多项式的系数,但就z而言:

f(z) = Dnzn + Dn-1zn-1 + ... + D0

f(z)= Dnzn + Dn-1zn-1 + ... + D0

This can be done pretty easily with some linear algebra. In particular, you can define an (n+1)×(n+1) matrix T which allows us to do the matrix multiplication

这可以通过一些线性代数很容易地完成。特别是,您可以定义一个(n + 1)×(n + 1)矩阵T,它允许我们进行矩阵乘法

  d = T * c ,

d = T * c,

where d is a column vector with top entry D0, to last entry Dn, column vector c is similar for the Ci coefficients, and matrix T has (i,j)-th [ith row, jth column] entry tij given by

其中d是具有顶部条目D0的列向量,对于最后的条目Dn,列向量c对于Ci系数是类似的,并且矩阵T具有(i,j) - 第[第i行,第j列]条目tij由下式给出:

  tij = (j choose i) ai bj-i.

tij =(j选择i)ai bj-i。

Where (j choose i) is the binomial coefficient, and = 0 when i > j. Also, unlike standard matrices, I'm thinking that i,j each range from 0 to n (usually you start at 1).

其中(j选择i)是二项式系数,当i> j时= 0。此外,与标准矩阵不同,我认为i,j的范围从0到n(通常从1开始)。

This is basically a nice way to write out the expansion and re-compression of the polynomial when you plug in z=ax+b by hand and use the binomial theorem.

当你手动插入z = ax + b并使用二项式定理时,这基本上是写出多项式的扩展和重新压缩的好方法。

#2


3  

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:

如果你必须多次计算变量z = ax + b的变化,那么Tyler的答案是正确的答案(我的意思是许多不同的多项式)。另一方面,如果你只需要做一次,那么将矩阵系数的计算与最终评估相结合要快得多。最好的方法是通过Hörner的方法在点(ax + b)处象征性地评估多项式:

  • 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 Ci.
  • 将多项式系数存储在向量V中(开头,所有系数都为零),对于i = n到0,将它乘以(ax + b)并加Ci。

  • adding Ci means adding it to the constant term
  • 添加Ci意味着将其添加到常数项

  • multiplying by (ax+b) means multiplying all coefficients by b into a vector K1, multiplying all coefficients by a and shifting them away from the constant term into a vector K2, and putting K1+K2 back into V.
  • 乘以(ax + b)意味着将所有系数乘以b乘以矢量K1,将所有系数乘以a并将它们从常数项移位到矢量K2,并将K1 + K2重新置于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.

请注意,将y更改为w = cy + d非常简单。最后,正如mattiast指出的那样,坐标的一般变化不会给出多项式。

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(由Tyler定义),您应该使用Pascal规则的加权版本来计算它(这是Hörner计算所暗示的):

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

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

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

这样,您可以从左到右简单地逐列计算它。

#3


2  

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.

如果我正确理解了您的问题,则无法保证在更改坐标后该函数将保持多项式。例如,设y = x ^ 2,新坐标系x'= y,y'= x。现在,等式变为y'= sqrt(x'),这不是多项式。

#4


0  

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'.

在xy空间中,你想要它在某个x'y'空间。你需要的是变换函数f(x)= x'和g(y)= y'(或h(x')= x和j(y')= y)。在第一种情况下,您需要求解x并求解y。一旦得到x和y,就可以将这些结果替换为原始方程并求解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

#5


-1  

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:

如果输入空间是线性相关的,则是,矩阵应该能够将一组系数变换为另一组。例如,如果您的多项式位于“原始”x空间中:

ax^3 + bx^2 + cx + d

ax ^ 3 + bx ^ 2 + cx + d

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

你想要转换成一个不同的w空间,其中w = px + q

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

然后你想要找到',b',c'和d'这样的话

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

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'

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

therefore

a = a'p^3

a = a'p ^ 3

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

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

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

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

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

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

which can be rewritten as a matrix problem and solved.

可以重写为矩阵问题并解决。

#1


4  

The problem statement is slightly unclear, so first I will clarify my own interpretation of it:

问题陈述有点不清楚,所以首先我要阐明自己对它的解释:

You have a polynomial function

你有一个多项式函数

f(x) = Cnxn + Cn-1xn-1 + ... + C0

f(x)= Cnxn + Cn-1xn-1 + ... + C0

[I changed A, B, ... Z into Cn, Cn-1, ..., C0 to more easily work with linear algebra below.]

[我将A,B,... Z改为Cn,Cn-1,...,C0,以便更容易使用下面的线性代数。]

Then you also have a transformation such as:   z = ax + b   that you want to use to find coefficients for the same polynomial, but in terms of z:

然后你还有一个变换,例如:z = ax + b,你想用它来找到相同多项式的系数,但就z而言:

f(z) = Dnzn + Dn-1zn-1 + ... + D0

f(z)= Dnzn + Dn-1zn-1 + ... + D0

This can be done pretty easily with some linear algebra. In particular, you can define an (n+1)×(n+1) matrix T which allows us to do the matrix multiplication

这可以通过一些线性代数很容易地完成。特别是,您可以定义一个(n + 1)×(n + 1)矩阵T,它允许我们进行矩阵乘法

  d = T * c ,

d = T * c,

where d is a column vector with top entry D0, to last entry Dn, column vector c is similar for the Ci coefficients, and matrix T has (i,j)-th [ith row, jth column] entry tij given by

其中d是具有顶部条目D0的列向量,对于最后的条目Dn,列向量c对于Ci系数是类似的,并且矩阵T具有(i,j) - 第[第i行,第j列]条目tij由下式给出:

  tij = (j choose i) ai bj-i.

tij =(j选择i)ai bj-i。

Where (j choose i) is the binomial coefficient, and = 0 when i > j. Also, unlike standard matrices, I'm thinking that i,j each range from 0 to n (usually you start at 1).

其中(j选择i)是二项式系数,当i> j时= 0。此外,与标准矩阵不同,我认为i,j的范围从0到n(通常从1开始)。

This is basically a nice way to write out the expansion and re-compression of the polynomial when you plug in z=ax+b by hand and use the binomial theorem.

当你手动插入z = ax + b并使用二项式定理时,这基本上是写出多项式的扩展和重新压缩的好方法。

#2


3  

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:

如果你必须多次计算变量z = ax + b的变化,那么Tyler的答案是正确的答案(我的意思是许多不同的多项式)。另一方面,如果你只需要做一次,那么将矩阵系数的计算与最终评估相结合要快得多。最好的方法是通过Hörner的方法在点(ax + b)处象征性地评估多项式:

  • 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 Ci.
  • 将多项式系数存储在向量V中(开头,所有系数都为零),对于i = n到0,将它乘以(ax + b)并加Ci。

  • adding Ci means adding it to the constant term
  • 添加Ci意味着将其添加到常数项

  • multiplying by (ax+b) means multiplying all coefficients by b into a vector K1, multiplying all coefficients by a and shifting them away from the constant term into a vector K2, and putting K1+K2 back into V.
  • 乘以(ax + b)意味着将所有系数乘以b乘以矢量K1,将所有系数乘以a并将它们从常数项移位到矢量K2,并将K1 + K2重新置于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.

请注意,将y更改为w = cy + d非常简单。最后,正如mattiast指出的那样,坐标的一般变化不会给出多项式。

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(由Tyler定义),您应该使用Pascal规则的加权版本来计算它(这是Hörner计算所暗示的):

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

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

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

这样,您可以从左到右简单地逐列计算它。

#3


2  

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.

如果我正确理解了您的问题,则无法保证在更改坐标后该函数将保持多项式。例如,设y = x ^ 2,新坐标系x'= y,y'= x。现在,等式变为y'= sqrt(x'),这不是多项式。

#4


0  

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'.

在xy空间中,你想要它在某个x'y'空间。你需要的是变换函数f(x)= x'和g(y)= y'(或h(x')= x和j(y')= y)。在第一种情况下,您需要求解x并求解y。一旦得到x和y,就可以将这些结果替换为原始方程并求解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

#5


-1  

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:

如果输入空间是线性相关的,则是,矩阵应该能够将一组系数变换为另一组。例如,如果您的多项式位于“原始”x空间中:

ax^3 + bx^2 + cx + d

ax ^ 3 + bx ^ 2 + cx + d

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

你想要转换成一个不同的w空间,其中w = px + q

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

然后你想要找到',b',c'和d'这样的话

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

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'

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

therefore

a = a'p^3

a = a'p ^ 3

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

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

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

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

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

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

which can be rewritten as a matrix problem and solved.

可以重写为矩阵问题并解决。