Вычисление значений многочлена

Вычисление значений многочлена — определение точных значений многочлена в заданном наборе точек. Одним из традиционных методов вычисления значений многочлена является метод Горнера. Помимо этого, существуют параллельные алгоритмы для решения данной задачи, а также быстрые методы для вычисления значений многочлена в нескольких точках одновременно. Существуют также специальные алгоритмы для решения частных случаев данной задачи, такие как алгоритм Блуштайна и быстрое преобразование Фурье.

Постановка задачи

Многочлен $P$ степени $n$ над полем $\mathbb {K}$ задан своими коэффициентами. Необходимо по заданному набору точек $x_{1},\dots ,x_{m}$ вычислить значения $P$ в этих точках. Если $P$ зависит только от одной переменной, он может быть представлен как $P(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n}$ . Соответственно, необходимо вычислить $P(x_{1}),\dots ,P(x_{m})$ . Используемая модель вычислений определяет, какие операции можно использовать при решении задачи. Как правило алгоритмы формулируются в терминах арифметических операций (сложение, вычитание, умножение, деление) над $\mathbb {K}$ .

Метод Горнера

Схема Горнера предполагает вычисление последовательности $p_{n},\dots ,p_{0}$ , где $p_{n}=a_{n}$ , а остальные члены определяются рекуррентно как $p_{k}=a_{k}+x\cdot p_{k+1}$ . Разворачивая схему в обратную сторону, можно получить:

p_{0}=a_{0}+x\cdot p_{1}=a_{0}+x\cdot (a_{1}+x\cdot p_{2})=\dots =a_{0}+x\cdot (a_{1}+x\cdot (a_{2}+x\cdot (\dots )))

, где наиболее вложенная скобка содержит выражение

a_{n-1}+x\cdot a_{n}

, то есть,

p_{n-1}

.

По такой схеме, $p_{k}$ равно значению в точке $x$ многочлена, составленного из коэффициентов $a_{k},\dots ,a_{n}$ — в частности, $p_{0}=P(x)$ . Алгоритм позволяет вычислить $P(x)$ за $O(n)$ сложений и умножений. Соответственно, вычисление в $m$ точках потребует $O(nm)$ операций.