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

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

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

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

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

Основная статья: Схема Горнера

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

${\displaystyle 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 )))}$, где наиболее вложенная скобка содержит выражение ${\displaystyle a_{n-1}+x\cdot a_{n}}$, то есть, ${\displaystyle p_{n-1}}$.

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