迭代多项式乘法 -- Python中的切比雪夫多项式

Question

我的问题是：在Python中，迭代多项式相乘的最佳方法是什么？

我觉得写一个Python函数来生成给定次数的切比雪夫多项式的每一项的系数和指数是个有趣的项目。生成这种多项式的递归函数（用T_n(x)表示）是：

With:

T₀(x) = 1

and

T₁(x) = x:

T_n(x) = 2xT_n-1(x) - T_n-2(x)

到目前为止，我的进展不是很有用，但我有点难以理解如何开始这个项目。我希望能实现以下内容：

>> chebyshev(4)
[[8,4], [8,2], [1,0]]

这个列表表示4次切比雪夫多项式： T₄(x) = 8x⁴ - 8x² + 1

import sys
def chebyshev(n, a=[1,0], b=[1,1]):
    z = [2,1]
    result = []
    if n == 0:
        return a
    if n == 1:
        return b
    print >> sys.stderr, ([z[0]*b[0], 
                           z[1]+b[1]],
                          a) # This displays the proper result for n = 2
    return result

我在网上找到的一个解决方案没有用，所以我希望有人能给我一些启发。

附言：关于切比雪夫多项式的更多信息：CSU Fullteron，维基百科 - 切比雪夫多项式。它们非常酷/有用，并且与一些有趣的三角函数/性质紧密相关；值得一读。

Answer 1

orthopy（这是我做的一个项目）也支持计算切比雪夫多项式。通过

import orthopy

# from sympy.abc import x
x = 0.5

normalization = "normal"   # or "classical", "monic"
evaluator = orthopy.c1.chebyshev1.Eval(x, normalization)
for _ in range(10):
    print(next(evaluator))

0.5641895835477564
0.39894228040143276
-0.39894228040143265
...

你可以在 x = 0.5 的时候得到不同次数的多项式值。你可以使用一个包含多个值的列表或向量，甚至可以用 sympy 的符号。

计算是通过递推关系进行的。如果你对系数感兴趣，可以查看

rc = orthopy.c1.chebyshev1.RecurrenceCoefficients("monic", symbolic=True)

Answer 2

Chebyshev的最佳实现方式是：

// Computes T_n(x), with -1 <= x <= 1
real T( int n, real x )
{
  return cos( n*acos(x) ) ;
}

如果你把这个和其他实现方式进行比较，比如直接计算多项式和逐步计算递推关系，你会发现这个其实速度差不多。你可以自己试试。

一般来说：

• 直接计算多项式的效率最差（特别是当n很大时）
• 递归计算稍微好一点
• 使用余弦函数计算是最好的选择

Answer 3

SciPy有一个关于切比雪夫（Chebyshev）多项式的实现。

你可以在这里查看相关文档。

我建议你去看看他们的代码。