Русская Википедия:Вычисление значений многочлена

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

Многочлен <math>P</math> степени <math>n</math> над полем <math>\mathbb K</math> задан своими коэффициентами. Необходимо по заданному набору точек <math>x_1, \dots, x_m</math> вычислить значения <math>P</math> в этих точках. Если <math>P</math> зависит только от одной переменной, он может быть представлен как <math>P(x) = a_0 + a_1 x + \dots + a_n x^n</math>. Соответственно, необходимо вычислить <math>P(x_1), \dots, P(x_m)</math>. Используемая модель вычислений определяет, какие операции можно использовать при решении задачи. Как правило алгоритмы формулируются в терминах арифметических операций (сложение, вычитание, умножение, деление) над <math>\mathbb K</math>.

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

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

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

По такой схеме, <math>p_k</math> равно значению в точке <math>x</math> многочлена, составленного из коэффициентов <math>a_k, \dots, a_n</math> — в частности, <math>p_0=P(x)</math>. Алгоритм позволяет вычислить <math>P(x)</math> за <math>O(n)</math> сложений и умножений. Соответственно, вычисление в <math>m</math> точках потребует <math>O(nm)</math> операций.

Литература

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