Вычисление многочленов - от Ньютона до наших дней Э. Г. Бeлага §1. Многочлены - инструмент вычислителя
    Ну, начнём! Когда мы доберёмся до конца этой истории, будем знать больше, чем теперь.
    Г. X. Андерсен
    В необозримом царстве функций многочлены занимают, на первый взгляд, очень скромное место. Однако это первое впечатление обманчиво.
    Многочлены, действительно, предельно просты: алгебраическая запись
    f (x) = xn + a1xn-1 + a2xn-2 + ... + an-1x + an (1) является одновременно и формулой для вычисления значений многочлена 1. Хотя выражения типа cos x, 5v x , 10x, log 2 x намного лаконичнее, с вычислительной точки зрения они бессодержательны: для вычисления, скажем чисел cos 17°, 5v 2 , 100,13 или log 2 7 нужны специальные приближённые формулы (или таблицы, составленные с помощью тех же формул). Как правило, в таких формулах появляются многочлены: например, cos x ? 1 - x2 2! + x4 4! - x6 6! + x8 8! (ошибка в интервале 0?x??/4 меньше одной десятимиллионной!).
    А ведь тригонометрические, степенные и т.п. (элементарные) функции - это самые простые из функций анализа, изучаемых и используемых математиками, физиками, инженерами. Известный математик-вычислитель Р. В. Хемминг в своей книге "Численные методы" (М., "Наука", 1972) пишет: "Поскольку с многочленами легко обращаться, большая часть классического численного анализа основывается на приближении многочленами".
    Так как вычислять многочлены приходится часто, то важно научиться делать это как можно проще. Мы расскажем об эволюции методов вычисления значений многочленов с момента зарождения (XVII век). Впрочем, слово "эволюция" здесь не вполне уместно: история этих методов - скорее очень длинный роман с интересной, но краткой завязкой, однообразным действием и неожиданной развязкой. §2. Схема Горнера По правде говоря, здесь возникает сомнение, или вернее вопрос, которого миновать нельзя, не поставив его и на него не ответив. А. Данте. Пир (1303 г.) Общепринятый сейчас способ вычисления многочленов восходит к Ньютону и называется схемой Горнера. Эта универсальная (то есть применимая к любому многочлену) схема предельно проста и изящна. Она получается из формулы (1) вынесением за скобки x всюду, где это возможно:
    f (x) = (...(((x + a1)·x + a2)·x + a3)...)·x + an. (2) Порядок действии при вычислении f (x) определяется скобками в (2): сначала сложение внутри самой внутренней пары скобок (его результат обозначим через p1), затем умножение и сложение внутри следующей пары скобок (результат p2) и т.д.:
    ? p1 = x + a1; ? p2 = p1x + a2; ? p3 = p2x + a3; ? · · · · · · · · · · · · · · · · · · ? pn = pn-1x + an, f (x) = pn; (3) всего n-1 умножений и n сложений 2.
    Схема Горнера настолько совершенна, что вопрос о возможности её улучшения не возникал два с половиной века и был задан "вслух" впервые лишь в 1954 году! Постановка этого вопроса (ответ на него предполагался отрицательным) имела важные и неожиданные последствия. §3. Индивидуальные схемы
     - Вы позволите мне записать эту романтическую историю, сэр? - спросил потрясенный мистер Снодграсс.
    - Сколько угодно, сэр, сколько угодно, ещё пятьдесят таких, если они вам по вкусу.
    Ч. Диккенс Уже в курсе школьной алгебры мы встречаемся с примерами многочленов, для которых существуют необычайно экономные схемы; единственный их недостаток - они не универсальны. ............