Вычисление многочленов — от Ньютона до наших дней
Э. Г. Бeлага
§1. Многочлены — инструмент вычислителя
Ну, начнём! Когда мы доберёмся до конца этой истории, будем знать больше, чем теперь.
Г. X. Андерсен
В необозримом царстве функций многочлены занимают, на первый взгляд, очень скромное место. Однако это первое впечатление обманчиво.
Многочлены, действительно, предельно просты: алгебраическая запись
| f (x) = xn + a1xn–1 + a2xn–2 + ... + an–1x + an | (1) |
является одновременно и формулой для вычисления значений многочлена 1. Хотя выражения типа cos x, 5√ x , 10x, log 2 x намного лаконичнее, с вычислительной точки зрения они бессодержательны: для вычисления, скажем чисел cos 17°, 5√ 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. Индивидуальные схемы
| — Вы позволите мне записать эту романтическую историю, сэр? — спросил потрясенный мистер Снодграсс. — Сколько угодно, сэр, сколько угодно, ещё пятьдесят таких, если они вам по вкусу. Ч. Диккенс |
Уже в курсе школьной алгебры мы встречаемся с примерами многочленов, для которых существуют необычайно экономные схемы; единственный их недостаток — они не универсальны.
Сравнивая разные схемы по числу операций, мы будем объединять операции сложения и вычитания в группу «(+, –)-операций», а гораздо более трудоёмкие операции умножения и деления — в группу «(×, :)-операций». 3
Примеры.
(а) Многочлен f (x) = x2^k можно вычислить за k умножений (а не за 2k по Горнеру):
| p1 = x·x = x2,p2 = p1·p1 = x4, ...,pk = pk–1·pk–1, f (x) = pk. |
(б) Многочлен f (x) = x15 можно вычислить за пять (×, :)-операций, так как f (x) = x15 = x16 : x = x2^4 : x.
(в) Многочлен f (x) = xn + xn–1 + ... + x + 1 вычисляется по формуле геометрической прогрессии: f (x) = (xn+1 – 1) : (x – 1).
(г) Многочлен
| f (x) = xn + | ( | n1 | ) | xn–1 + ... + | ( | nn–1 | ) | x + 1; |
есть бином Ньютона: f (x) = (x + 1)n.
Число примеров можно, конечно, увеличить.
Упражнения
1. Докажите, что многочлены (а) и (б) не могут быть вычислены быстрее.
2. В «Задачнике «Кванта» № 12 за 1973 год была помещена задача (М240): доказать, что многочлен f (x) = xn может быть вычислен не более чем за 3/2 log2 n + 1 (×, :)-операций (n — натуральное число).
Пользуясь результатом этой задачи, оцените число операций для вычисления многочленов (в) и (г).
Решение
Для многочлена (в) — не более 3/2 log2 (n+1) + 2 (×, :)-операции и два вычитания; для многочлена (г) — не более 3/2 log2 n + 1 (×, :)-операция и одно сложение.
3. Постройте экономные схемы для многочленов:
| (I) | f (x) = x8 + x6 – x5 + 2x4 – x3 + x2 – x + 1; |
| (II) | f (x) = xn + 2xn–1 + 3xn–2 + ... + nx + n + 1; |
| (III) | f (x) = x2n + ( 2n2) x2n–2 + ( 2n4) x2n–4 + ... + (2n2n–2) x2 + 1; |
| (IV) | f (x) = 1 – x2 2! + x4 4! – x6 6! + x8 8! . |
Решение
| (I) | p1 = x·x = x2, p2 = x2·x2 = x4,f (x) = (p2 + p1 + 1)(p2 – x + 1). |
| (II) | Заметим, что x f (x) – f (x) = xn+1 + xn + ... + x – (n + 1);отсюда f (x) = [xn+1 + xn + ... + x + 1 – (n + 2)] : (x – 1) == [(xn+2 – 1) : (x – 1) – (n + 2)] : (x – 1). |
| (III) | f (x) = (x + 1)2n + (x – 1)2n 2. |
| (IV) | p1 = x·x = x2, f (x) =((( 1 8!p1 – 1 6!)p1 + 1 4!)p1 – 1 2!)p1 + 1. |
§4. Каждому многочлену — свою схему?
| Тогда я решил тем же способом разделаться и с остальными медведями. Э. Распэ. Мюнхаузен среди белых медведей. |
А что если для каждого многочлена существует своя схема, гораздо более экономная, чем схема Горнера?
Такие схемы можно было бы искать либо исходя из особенностей отдельного многочлена (искусно комбинируя его коэффициенты), либо сконструировав универсальный метод построения схем, намного более экономных, чем схема Горнера, но, возможно, для некоторых многочленов не наилучших. Недостаток первого подхода в том, что для каждого многочлена придется придумывать свои приёмы, и нет никакой гарантии, что нам это всегда удастся; позже (в §10) мы увидим, что второй путь надёжнее во всех отношениях.
Само собой разумеется, что оба эти метода уместны лишь в тех случаях, когда конкретный многочлен приходится вычислять так часто, что стоит потратить и время, и усилия, чтобы построить для него хорошую схему. Многочлены же «разового пользования» проще вычислять, скажем, по схеме Горнера.
Возможно, подобные рассуждения и привели в 1955 году к открытию универсальной схемы совершенно нового типа для многочлена шестой степени. Мы проиллюстрируем основную идею этой схемы на примере более простой схемы — для многочленов степени 4. Пусть
| f (x) = x4 + ax3 + bx2 + cx + d; | (4) |
положим
| p1 = x(x + A), p2 = (p1 + B)(p1 + x + C) + D, f (x) = p2, | (5) |
где A, B, C и D — параметры.
Пример. Многочлен x4 + 3x3 + 6x2 + 3x + 2 можно вычислять по схеме: p1 = x(x + A), f (x) = (p1 – 1)(p1 + x + 5) + 7, содержащей два умножения (вместо трёх по Горнеру) и пять (вместо четырёх) (+, –)-операций; здесь A=1, B=–1, C=5, D=7.
Выпишем явное выражение для p2(x):
p2(x) = x4 + (2A + 1)·x3 + (A2 + A + B + C)·x2 +
+ (AB + B + AC)·x + BC + D;
приравняв коэффициенты f (x) и p2(x), выразим параметры, входящие в формулу (5), через коэффициенты (4):
| A = (a – 1)/2;B = c – bA + A2(A + 1);C = b – B – A(A + 1);D = d – BC. | (6) |
Из этих формул ясно, что схема (5) универсальна.
Операции (6) мы будем называть предварительной обработкой коэффициентов многочлена; разумеется, они не включаются в число операций схемы: ведь для каждого данного многочлена они выполняются лишь однажды, а наша задача — научиться быстро считать значения произвольного, но фиксированного многочлена при разных x.
§5. Универсальная схема степени n
| — Я думаю, — сказал глубокомысленно Пятачок, — что если бы Иа встал под деревом, а Пух встал к нему на спину, а я встал на плечи Пуха... — И если бы спина Иа-Иа неожиданно треснула, то мы бы все здорово посмеялись, — сказал Иа. А. А. Милн. Винни Пух |
В 1958 году была найдена общая универсальная схема с предварительной обработкой коэффициентов. Структура этой схемы для многочлена чётной степени (n=2k) напоминает пирамиду — в основании лежит схема (5) (в её «прочности» мы уже убедились), содержащаяся в схеме степени 6, которая содержится в схеме степени 8 и т.д.:
| p1 = x(x + b1), p2 = (p1 + b2)(p1 + x + b3) + b4, p3 = p2(p1 + b5) + b6, · · · · · · · · · · · · · · · · · · pk = pk–1(p1 + b2k–1) + b2k, f (x) = pk, k≥2. | (7.k) |
схема (7.2) — это и есть схема (5). Результат схемы (7.k) — многочлен pk(x) степени n = 2k; многочлен же нечётной степени n = 2k + 1 можно представить в таком виде:
| f (x) = x(x2k + a1x2k–1 + ... + a2k) + a2k+1; | (8) |
многочлен в круглых скобках вычисляется по схеме (7.k). В итоге схема содержит k умножений и 2k+1 сложений для многочлена чётной степени n = 2k и k+1 умножений и 2k+2 сложений для многочлена нечётной степени n = 2k + 1 (с учётом (7.k) и (8) ).
Упражнения
4. Найдите формулы предварительной обработки коэффициентов, аналогичные формулам (6), для схемы (7.3) вычисления многочленов шестой степени.
5. Докажите индукцией по k≥2 универсальность схемы (7.k).
Решение
Пусть f(x) = x2k + a1x2k–1 + ... + a2k.
Нам нужно по коэффициентам a1, ..., a2k многочлена f (x) найти параметры b1, ..., b2k, превращающие последнюю строку схемы (7.k) в тождество.