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

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

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

Многочлен $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)$ операций.

Литература

• Munro I., Paterson M. Optimal algorithms for parallel polynomial evaluation (англ.) // Journal of Computer and System Sciences / M. Segal — Elsevier BV, 1973. — Vol. 7, Iss. 2. — P. 189—198. — ISSN 0022-0000; 1090-2724 — doi:10.1016/S0022-0000(73)80043-1
• Fiduccia C. M. Polynomial evaluation via the division algorithm the fast Fourier transform revisited (англ.) — 1972. — doi:10.1145/800152.804900
• Bostan A., Schost É. Polynomial evaluation and interpolation on special sets of points (англ.) // Journal of Complexity — Elsevier BV, 2005. — Vol. 21, Iss. 4. — P. 420—446. — ISSN 0885-064X; 1090-2708 — doi:10.1016/J.JCO.2004.09.009