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

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

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

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

Метод ГорнераПравить

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

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

$p_0=a_0+x\cdot <!--\; \cdot \; -->p_1=a_0+x\cdot <!--\; \cdot \; -->(a_1+x\cdot <!--\; \cdot \; -->p_2)=\cdots <!--\; \cdots \; -->=a_0+x\cdot <!--\; \cdot \; -->(a_1+x\cdot <!--\; \cdot \; -->(a_2+x\cdot <!--\; \cdot \; -->(\dots <!--\; \dots \; -->)))$$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 <!--\; \cdot \; -->a_n$$a_{n-1}+x\cdot a_{n}$ , то есть, $p_{n-<!--\; -\; -->1}$$p_{n-1}$ .

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