Как вычислять значение многочлена по схеме Горнера?

Прямое вычисление aₙxⁿ + … + a₁x + a₀ может многократно возводить x в степень и выполнять лишние умножения. Схема Горнера переписывает многочлен во вложенной форме и обрабатывает…

Прямое вычисление aₙxⁿ + … + a₁x + a₀ может многократно возводить x в степень и выполнять лишние умножения. Схема Горнера переписывает многочлен во вложенной форме и обрабатывает коэффициенты одним проходом: каждый шаг умножает накопленное значение на x и добавляет следующий коэффициент.

Вложенная форма

Для кубического многочлена выражение становится ((a₃x + a₂)x + a₁)x + a₀. Если коэффициенты хранятся от старшей степени к свободному члену, накопитель начинают с aₙ и последовательно применяют правило result = result · x + aᵢ.

Инвариант прохода

После обработки коэффициента aₖ накопитель равен значению префиксного многочлена от aₙ до aₖ в точке x. Следующий шаг умножает все уже учтённые степени на x и добавляет новый свободный член этого префикса. Индукция доказывает итоговую формулу.

Число операций

Для степени n требуется n умножений и n сложений, поэтому время O(n), а дополнительная память O(1). Отдельные степени не строятся. Если коэффициенты поступают потоком в правильном порядке, массив вообще не нужен.

Порядок коэффициентов

Если вход перечисляет коэффициенты от a₀ к aₙ, его нужно пройти с конца или изменить форму обработки. Молчаливое предположение о порядке — типичная ошибка. Нулевые старшие коэффициенты допустимы, но фактическая степень тогда меньше заявленного размера массива.

Численная сторона

Схема обычно уменьшает число округлений по сравнению с наивным вычислением степеней, но не делает вещественный результат точным. Для больших |x| промежуточные значения могут переполниться. Проверьте многочлен в точках 0, 1 и −1: там независимый ручной ответ легко обнаруживает перепутанный порядок.

Вложенная форма устраняет повторные степени

Многочлен a₀xⁿ + a₁xⁿ⁻¹ + … + aₙ переписывают как (...((a₀x + a₁)x + a₂)x + ... + aₙ). На каждом шаге текущий result равен значению уже обработанного префикса коэффициентов. Нужны n умножений и n сложений вместо отдельного вычисления каждой степени.

def horner(coefficients: list[float], x: float) -> float:
    if not coefficients:
        raise ValueError("at least one coefficient is required")
    result = coefficients[0]
    for coefficient in coefficients[1:]:
        result = result * x + coefficient
    return result

# 2x^3 - 3x + 5; нулевой коэффициент при x^2 обязателен
assert horner([2, 0, -3, 5], 2) == 15

Порядок коэффициентов входит в контракт. Пропущенный ноль меняет степени и задаёт другой многочлен. Для вещественных вычислений схема обычно уменьшает число округлений, но всё равно возвращает машинное приближение.

Практика: значение и производная за один проход

Расширьте схему так, чтобы одновременно вычислять P(x) и P′(x), не строя массив коэффициентов производной. Проверьте результат на многочлене 2x³ − 3x + 5 в точках −1, 0 и 2, сравнив с прямой формулой. Затем посчитайте умножения в наивной реализации со степенями и в схеме Горнера. Отдельно протестируйте постоянный многочлен и объясните значение пустого списка коэффициентов в выбранном контракте.