Polynomial

本文介绍多项式相关知识。

概述

多项式 (Polynomial) 是代数学中的基础概念，是由称为未知数的变量和称为系数的常数通过有限次加减法，乘法以及自然数幂次的乘方运算得到的代数表达式。以单变量多项式为例说明：

$$ f(x) = \sum_{i=0}^{n}a_i x^i = a_0 + a_1x + … + a_nX^n = a_0,a_1,….,a_n $$

以上是系数表示形式，系数序列确定多项式也就确定了。还有一种表示方法是使用 n+1 点值对表示 n 次多项式。

$$ f(x) = (x_0,y_0),(x_1,y_1),….,(x_n,y_n) $$

同样，这种方法也能唯一确定多项式。

两种表示方法，各有其应用场景，比如系数表示法在计算多项式相加的场合效率高，而点值表示法则应用在多项式相乘计算场合。

由于两种表示法本质是同一个东西，所以二者可以相互转化，其中 FFT 就是实现系数表达到点值表示的转换方法，而 IFFT 正好相反。关于 FFT 和 IFFT 深入解读超出本文范围，请自行查阅资料。

多项式插值法是一种数学和计算方法，用于找到通过一组给定数据点的多项式函数，以便在这些数据点上的函数值与已知数据值完全匹配。这种方法的核心思想是，通过已知数据点，可以确定一个多项式函数，使得这个多项式函数在这些点上的值与实际观测到的值一致。

下面是多项式插值法的一般步骤和核心概念：

已知数据点：首先，已知一组数据点，通常表示为 (x1, y1), (x2, y2), …, (xn, yn)，其中 xi 是独立变量的值，yi 是相应的依赖变量的观测值。
插值多项式：接下来，通过这些已知数据点来构建一个插值多项式，通常表示为 P(x)，这个多项式的形式为 P(x) = a0 + a1x + a2x^2 + … + anx^n，其中 a0, a1, a2, …, an 是多项式的系数。
满足条件：插值多项式 P(x) 被设计成满足以下条件：P(xi) = yi，即在已知数据点 xi 处，多项式的值与观测值 yi 相等。
多项式求解：通过解一个线性方程组或使用插值方法（如拉格朗日插值法或牛顿插值法）来确定多项式的系数，以使插值多项式满足已知数据点。
插值结果：一旦找到插值多项式，就可以使用它来估计在任何 x 值处的函数值，而不仅仅是已知数据点上的值。这使得插值多项式成为对数据进行估计和预测的有用工具。

常见的多项式插值方法包括：

来自 Wolfram Alpha 的巧妙在线工具可以根据输入的向量插值一个多项式！