Вычисление многочленов — от Ньютона до наших дней

29

§ 1. Многочлены — инструмент вычислителя

Ну, начнем! Кодда мы доберемся до конца этой истории, будем знать больше, чем менее.

Г. Х. Андерсен

В небозримом царстве функций многочлены занимают, на первый взгляд, очень скромное место. Однако это первоое впечатление обманчиво.

Многочлены, действительно, предельно просты: алгебраическая запись
$$f(x) = x^n + a_1x^{n-1} + a_2x^{n-2} + \dots + a_{n-1}x + a_n$$ (1)
является одновременно и формулой для вычисления значений многочлена$^*$). Хотя выражения типа $\cos x$, $\sqrt[5]{x}$, $10^x$ или $\log_2 x$ намного лаконинее, с вычислительной точки зрения они бессодержательны: для вычисления, скажем чисел $\cos 17^\circ$, $\sqrt[5]{2}$, $10^{0.13}$ или $\log_2 7$ нужны специальные приближенные формулы (или таблицы, составленные с помощью тех же формул). Как правило, в таких формулах появляются многочлены: например,
$$\cos x \approx 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + \frac{x^8}{8!}$$

(ошибка в интервале $0 \leq x \leq \pi/4$ меньше одной десятимиллюнной!).

*) Что бы упростить выкладки, мы ограничимся многочленами с единичным коэффициентом при старшем член ($a_0 = 1$); там, где это будет необходимо, мы появим, как поступать в общем случае ($a_0 \neq 1$).

А ведь тригонометрические, степенные и т. п. (элементарные) функции — это самые простые из функций анализа, изучаемых и использовых математиками, физики, инженерами. Известный математик-вычислитель пишет в своей книге *): «Поскольку с многочленами легко обращаться, больше часть классического численного анализа основывается на приближении многочленами».

Так как вычислить многочлены приходится часто, то важно научиться делать это как можно проще. Мы раскажем об эволюции методов вычисления значений многочленов с момента зарождания (XVII век). Впрочем, слово «эволюция» здесь не вполнеуместно: история этих методов — скорее очень длинный роман с интересной, но краткой завязкой, однообразным действием и неожиданной развязкой.

§ 2. Схема Горнера

По праваде говоря, здесь возникнет сомнение, или вернее вопрос, который минимать нельзя, не поставив его и на него не ответив.

А. Данте. Пир (1303 г.)

Общеприятный сейчас способ вычисления многочленов восходит к Ньютону и называется схемой Горнера. Эта универсальная (то есть применняя к любому многочлену) схема предельно проста и изящна. Она получается из формулы (1) вы-

*) Р. В. Хемминг. Численные методы. М., «Наука», 1972.

31

Такие схемы можно было бы искать либо исходя из особенностей отдельного многочлена (искусно комбиниру его коэффициенты), либо сконструировав универсальный метод построения схем, намного более экономных, чем схема Горнера, но, возможно, для некоторых многочленов не наилучших. Недостаток первого подхода в том, что для каждого многочлена придется придувать свои приемы, и нет никакой гарантии, что нам это всегда удался; позже (в § 10) мы увидим, что второй надежнее во всех отношениях.

Само собой разумеется, что оба эти методы уменьшает лишь в тех случаях, когда конкретный многочлен приходит в время, и усилия, чтобы построить для него хорошего схему. Многочлены же «разового пользования» проще вычислять, скажем, по схеме Горнера.

Возможно, подобные рассуждения и привели в 1955 году к открытию универсальной схемы совершенного типа для многочлена шестой степени. Мы проиллюстрируем основную идею этой схемы на примере более простой схемы — для многочленов степени 4. Пусть
$$f(x) = x^4 + ax^3 + bx^2 + cx + d;$$
положим
$$\begin{cases} p_1 = x \cdot (x + A); \\ p_2 = (p_1 + B)(p_1 + x + C) + D \\ f(x) = p_2 \end{cases}$$
где A, B, C и D — параметры.

Пример. Многочлен $x^4 + 3x^3 + 6x^2 + 3x + 2$ можно вычислять по схеме: $p_1 = x(x + 1), f(x) = (p_1 - 1)(p_1 + x + 5) + 7$, содержащей два (вместо трех по Горнеру) умножения и пять (вместо четырех) $(\pm)$-операции; здесь A = 1, B = -1, C = 5, D = 7.

Выпишем явное выражение для $p_2(x)$:
$$p_2(x) = x^4 + (2A + 1)x^3 + (A^2 + A + B + C)x^2 + (AB + B + AC)x + BC + D;$$
приравняя коэффициенты $f(x)$ и $p_2(x)$, выразим параметры, входящие в форму (5), через коэффициенты (4):
$$A = (a - 1)/2;$$
$$B = c - b \cdot A + A^2(A + 1);$$
$$C = b - B - A(A + 1);$$
$$D = d - BC.$$
Из этих формул ясно, что схема (5) универсальная.

Операции (6) мы будем назвать превращимый обработкой коэффициентов многочлена; разумеется, они не включаются в число операций схемы: ведь для каждого данного многочлена они выполняются лишь однажды, а наша задача — научиться быстро считать значения произвольного, но фиксированного многочлена при разных $x$.

§ 5. Универсальная схема степени n

—Я думало, — сказал глубокомысленно Пятанок, — что если бы На всем под деревом, а Пух вставал к нему на спину, а я вставал на плещи Пуха…
—И если бы спина На-На неожиданно преснула, то мы бы все здорово посмелись, — сказал На.

A. A. Милл. Винни Пух

В 1958 году была найдена общая универсальная схема с превращительным обработкой коэффициентов. Структура этой схемы для многочлена четной степени ($n = 2k$) напоминает пирамиду — в основании лежит схема (5) (в ее «прочности» мы уже убедились), содержащаяся в схеме степени 6, которая содержится в схеме степени 8 и т. д.:
$$\begin{cases} p_1 = x(x + b_1), \\ p_2 = (p_1 + b_2)(p_1 + x + b_3) + b_4, \\ p_3 = p_2(p_1 + b_5) + b_6, \\ \dots \\ p_k = p_{k-1}(p_1 + b_{2k-1}) + b_{2k}, \\ f(x) = p_k, \end{cases}$$

схема (7.2) — это и есть схема (5). Результат схемы (7.k) — многочлен $p_k(x)$ степени $n = 2k$; многочлен же нечетной степени $n = 2k + 1$ можно представить в таком виде:
$$f(x) = x(x^2k + a_1x^{2k-1} + \dots + a_{2k}) + a_{2k-1};$$
многочлен в круглых скобках вычисляется по схеме (7.k). В итоге

32

схема содержит $k$ умножений и $2k+1$ сложений для многочлена четной степени $n=2k$ и $k+1$ умножений и $2k+2$ сложений для многочлена нечетной степени $n=2k+1$ (с учетом (7.k) и (8.)).

Упражнения
4. Найдите формулы предварительной обработки коэффициентов, аналогичные формулам (6), для схемы (7.3) вычисления многочленов шестой степени.
5. Докажите индукцией по $k \geq 2$ универсальной схемы (7.k).

Начиная с третьей строки, схема (7.k) очень напоминает схему Горнера (3); разница лишь в том, что теперь после каждого умножения степень увеличивается не на единицу, а на два.

Итак, нам удалось уменьшить число умножений по сравнению со схемой Горнера вдвое. Какой ценой? Из решения упражнения 5 видно, что процесс вычисления параметров $b_1, b_2, \dots, b_{2k}$ по коэффициентам $a_1, a_2, \dots, a_n$ очень сложен, — он включает в себя решение серии уравнений с одним неизвестным степенью $k-1, k-2, \dots$. Это означает, в частности, что при $k \geq 6$ ($n \geq 12$) формул вычисления параметров нет *), хотя, разумеется, их значения могут быть найдены приближенными методами с любой степенью точности.

Здесь возникает еще одно затруднение, оказывается, правда, предполимым. До сх пор мы не уточняли, значения каких — действительны или комплиексны — многочленов мы вычисляем. Схема Горнера применима и в том, и в другом случае, схема же (7.k)

*) Под формулой обычно понимают набор арифметических операций, корней, степеней. Вы, наверное, знаете, что Э. Галу и Н. Абель, генциальные (и оба очень рано умершие) математики XIX века, доказали, что для нахождения корней многочленов пятой и более высоких степеней таких общих формул не существует (см. «Квант», 1973, № 10, с. 3—12).

премущественно «комплексная» — действительным коэффициентам могут соответствовать комплисные параметры. Появление комплисных чисел при вычислении действительных многочленов намного увеличивает число арифметических операций *). К счастью, в 1960 году схему (7.k) необходим усложненем удалось превращать в действительную; однако полные доказательства в этом случае уже очень непросты.

§ 6. О схемах вообще…

— Минуточку, минуточку — раздались проместующие колоса. — Избегайте, пожалуйста, научных терминов, обязывайте популярно…
— Верно! — подтвердили остальные.— Говорите понятнее. Что такое лес?
Я. Осенка. Загородная прогулка в 2050 году.

Пришло время спросить, нет ли схем, более экономных, чем схему (7.k)? Но тогда неизбежен и вопрос — что такое схема?

Определене. (I). Схема с предварительной обработкой коэффициентов — это последовательность арифметических операций, в которых участвуют переменная $x$, параметры $b_1, b_2, \dots, b_m$ и результаты прешвестующих операций. Результат последней операции называем результатом схемы. (II). Если при некотором наборе значений параметров $b_1, \dots, b_m$ результат схемы есть данный многочлен степени $n$, то мы скажем, что схема представляем этот многочлен. (III). Если схема представляется многочлен, то процесс вычисления по его коэффициентам соответствующего набора значений параметров называем предварительной обработкой коэффициентов. (IV). Схема называется `упервсальной степени $n$, если она представляется любой многочлен степени $n$ вида (1).

*) Одно «комплексное» сложение — это два «действительных», одно «комплексное» умножение — четые (!) умножения и два сложения.