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

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

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

Многочлен $P$ степени $n$ над полем $𝕂$ задан своими коэффициентами. Необходимо по заданному набору точек $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)$. Используемая модель вычислений определяет, какие операции можно использовать при решении задачи. Как правило алгоритмы формулируются в терминах арифметических операций (сложение, вычитание, умножение, деление) над $𝕂$.

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

Шаблон:Основная статья Схема Горнера предполагает вычисление последовательности $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)$ операций.

Литература

• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q