Текст статьи Белага Э. Г. Вычисление многочленов — от Ньютона до наших дней // Квант. — 1974. — № 7. — С. 29—35.
§ 1. Многочлены — инструмент вычислителя
Ну, начнём! Когда мы доберёмся до конца этой истории, будем знать больше, чем теперь.
Г. Х. Андерсен
В необозримом царстве функций многочлены занимают, на первый взгляд, очень скромное место. Однако это первое впечатление обманчиво.
Многочлены, действительно, предельно просты: алгебраическая запись
$$
f(x)=x^n+a_1x^{n-1}+a_2x^{n-2}+\ldots+a_{n-1}x+a_n\tag1
$$
является одновременно и формулой для вычисления значений многочлена.
Хотя выражения типа
А ведь тригонометрические, степенные и т. п. (элементарные) функции — это самые простые из функций анализа, изучаемых и используемых математиками, физиками, инженерами. Известный математик-вычислитель пишет в своей книге: «Поскольку с многочленами легко обращаться, большая часть классического численного анализа основывается на приближении многочленами».
Так как вычислять многочлены приходится часто, то важно научиться делать это как можно проще. Мы расскажем об эволюции методов вычисления значений многочленов с момента зарождения (XVII век). Впрочем, слово «эволюция» здесь не вполне уместно; история этих методов — скорее очень длинный роман с интересной, но краткой завязкой, однообразным действием и неожиданной развязкой.
§ 2. Схема Горнера
По правде говоря, здесь возникает сомнение, или вернее вопрос, которого миновать нельзя, не поставив его и на него не ответив.
А. Данте. Пир (1303 г.)
Общепринятый сейчас способ вычисления многочленов восходит к Ньютону и называется схемой Горнера. Эта универсальная (т. е. применимая к любому
многочлену) схема предельно проста и изящна. Она получается из формулы (1)
вынесением за скобки
Схема Горнера настолько совершенна, что вопрос о возможности её улучшения не возникал два с половиной века и был задан «вслух» впервые лишь в 1954 году! Постановка этого вопроса (ответ на него предполагался отрицательным) имела важные и неожиданные последствия.
§ 3. Индивидуальные схемы
— Вы позволите мне записать эту романтическую историю, сэр? — спросил потрясённый мистер Снодграсс.
— Сколько угодно, сэр, сколько угодно, ещё пятьдесят таких, если они вам по вкусу.
Ч. Диккенс
Уже в курсе школьной алгебры мы встречаемся с примерами многочленов, для которых существуют необычайно экономные схемы; единственный их недостаток — они не универсальны.
Сравнивая разные схемы по числу операций, мы будем объединять операции
сложения и вычитания в группу «
- Многочлен
$f(x)=x^{2^k}$ можно вычислить за$k$ умножений (а не зa$2^k$ по Горнеру): $$ \begin{aligned} p_1&=x\cdot x=x^2,\\ p_2&=p_1\cdot p_1=x^4,\\ {\ldots}&\,{\ldots}\,{\ldots}\,{\ldots}\,{\ldots}\\ p_k&=p_{k-1}\cdot p_{k-1},~f(x)=p_k. \end{aligned} $$ - Многочлен
$f(x)=x^{15}$ вычислить за пять$({\times},{:})$ -операций, так как$f(x)=x^{15}=x^{16}:x=x^{2^4}:x$. - Многочлен
$f(x)=x^n+x^{n-1}+\ldots+x+1$ вычисляется по формуле геометрической прогрессии$f(x)=(x^{n+1}-1):(x-1)$. - Многочлен
$f(x)=x^n+C_n^1x^{n-1}+\ldots+C_n^{n-1}x+1$ есть бином Ньютона:$f(x)=(x+1)^n$.
Число примеров можно, конечно, увеличить.
Упражнения
- Докажите, что многочлены (а) и (б) не могут быть вычислены быстрее.
В «Задачнике «Кванта» № 12 за 1973 год была помещена задача (М240): доказать, что многочлен
$f(x)=x^n$ может быть вычислен не более чем за$\dfrac32\log_2n+1$ $({\times},{:})$ -операций($n$ — натуральное число).Пользуясь результатом этой задачи, оцените число операций для вычисления многочленов (в) и (г).
- Постройте экономные схемы для многочленов:
$f(x)=x^8+x^6-x^5+2x^4-x^3+x^2-x+1$; $f(x)=x^n+2x^{n-1}+3x^{n-2}+\ldots+nx+n+1$; $f(x)=x^{2n}+C_{2n}^2x^{2n-2}+C_{2n}^4 x^{2n-4}+\ldots+C_{2n}^{2n-2}x^2+1$; $f(x)=1-\dfrac{x^2}{2!}+\dfrac{x^4}{4!}- \dfrac{x^6}{6!}+\dfrac{x^8}{8!}$.
§ 4. Каждому многочлену — свою схему?
Тогда я решил тем же способом разделаться и с остальными медведями.
Э. Распэ. Мюнхаузен среди белых медведей
А что если для каждого многочлена существует своя схема, гораздо более экономная, чем схема Горнера?
Такие схемы можно было бы искать либо исходя из особенностей отдельного многочлена (искусно комбинируя его коэффициенты), либо сконструировав универсальный метод построения схем, намного более экономных, чем схема Горнера, но, возможно, для некоторых многочленов не наилучших. Недостаток первого подхода в том, что для каждого многочлена придётся придумывать свои приёмы, и нет никакой гарантии, что нам это всегда удастся; позже (в § 10) мы увидим, что второй путь надёжнее во всех отношениях.
Само собой разумеется, что оба эти метода уместны лишь в тех случаях, когда конкретный многочлен приходится вычислять так часто, что стоит потратить и время, и усилия, чтобы построить для него хорошую схему. Многочлены же «разового пользования» проще вычислять, скажем, по схеме Горнера.
Возможно, подобные рассуждения и привели в 1955 году к открытию
универсальной схемы совершенно нового типа для многочлена шестой степени. Мы проиллюстрируем основную идею этой схемы на примере более простой схемы — для многочленов степени 4. Пусть
$$
f(x)=x^4+ax^3+bx^2+cx+d;\tag4
$$
положим
$$
\left\{\,\begin{aligned}
p_1&=x\cdot(x+A),\\
p_2&=(p_1+B)(p_1+x+C)+D,\quad f(x)=p_2
\end{aligned}\right.\tag5
$$
где
Пример. Многочлен
Выпишем явное выражение для
Операции (6) мы будем называть предварительной обработкой
коэффициентов многочлена; разумеется, они не включаются в число
операций схемы: ведь для каждого данного многочлена они выполняются лишь
однажды, а наша задача — научиться быстро считать значения произвольного, но фиксированного многочлена при разных
§ 5. Универсальная схема степени $\bm{n}$
— Я думаю, — сказал глубокомысленно Пятачок, — что если бы Иа встал под деревом, а Пух встал к нему на спину, а я встал на плечи Пуха...
— И если бы спина Иа-Иа неожиданно треснула, то мы бы все здорово посмеялись, — сказал Иа.
А. А. Милн. Винни Пух
В 1958 году была найдена общая универсальная схема с предварительной
обработкой коэффициентов. Структура этой схемы для многочлена чётной степени
Упражнения
- Найдите формулы предварительной обработки коэффициентов, аналогичные формулам (6), для схемы (7.3) вычисления многочленов шестой степени.
- Докажите индукцией по
$k\ge2$ универсальность схемы$(7.k)$.
Начиная с третьей строки, схема
Итак, нам удалось уменьшить число умножений по сравнению со схемой
Горнера вдвое. Какой ценой? Из решения упражнения 5 видно, что процесс
вычисления параметров
Здесь возникает ещё одно затруднение, оказавшееся, правда, преодолимым.
До сих пор мы не уточняли, значения каких — действительных или комплексных — многочленов мы вычисляем. Схема Горнера применима и в том, и в другом случае, схема же
§ 6. О схемах вообще...
— Минуточку, минуточку — раздались протестующие голоса. — Избегайте, пожалуйста, научных терминов, объясняйте популярно...
— Верно! — подтвердили остальные. — Говорите понятнее... Что такое лес?
Я. Осенка. Загородная прогулка в 2050 году.
Пришло время спросить, нет ли схем, более экономных, чем схема
Определение. (I). Схема с предварительной обработкой
коэффициентов — это последовательность арифметических операций, в которых участвуют переменная
Примеры. 1. Схема
2. Схема
Упражнение
- Докажите, что общее число
$S_N$ схем (всех степеней), содержащих не более$N$ операций, конечно и не превосходит числа$\left[\dfrac{(3N-1)!}{(2N-1)!}\right]^2$.
§ 7. ... И о наилучшей из в частности
Положение, в котором мы находимся, заставляет нас прибегать ко всестороннему изучению предмета.
Платон
Теперь наш вопрос о наилучших схемах степени
Справедливость этого утверждения можно вывести из двух важных свойств схем:
- число
$m$ параметров универсальной схемы степени$n$ не меньше числа коэффициентов, т. е.$m\ge n$; - в промежутке между двумя
$({\times},{:})$ -операциями любой (не обязательно универсальной) схемы может появиться не более двух по-настоящему новых параметров (все остальные будут «лишними»), а между двумя$({\pm})$ -операциями — не более одного.
Второе свойство стоит сформулировать более строго: если схема содержит
Итак,
— Но вы совсем забыли о схеме Горнера! — прервёт нас читатель, которому больше по душе классическая ясность схем без предварительной возни с коэффициентами. — Ведь она не зря кажется предельно экономной!
— Схема Горнера действительно наилучшая среди схем, в которых параметрами являются сами коэффициенты. Недостаток места не позволяет нам изложить красивое, но не очень простое доказательство этого факта, найденное в 1960 году.
А теперь займёмся двумя сформулированными выше свойствами схем, сначала вторым.
§ 8. Параметры в операциях
Дама сдавала в багаж
диван,
чемодан,
саквояж,
картину,
корзину,
картонку
и маленькую собачонку.
С. Я. Маршак
Наше определение схемы не накладывало никаких ограничений на форму её записи. Мы назовём элементарной запись схемы типа «одна
строка — одна операция», когда запоминается (и обозначается своим символом)
результат каждой операции схемы; примеры: эпиграф (хотя это и не схема, а скорее багажная квитанция), схема для многочлена
Не для всех схем элементарная форма записи является единственной: если
результат какой-то операции используется лишь однажды, то эту операцию можно
сразу включить в ту строку, в которой участвует её результат.
(Примеры: каждая строка схемы (3), начиная со второй, включает две операции, а схемы
Переходя к доказательству свойства 2), рассмотрим
элементарную форму записи схемы и обозначим через
Доказательство для
§ 9. Параметры универсальной схемы
Я нарочно заостряю, упрощаю и карикатурю мысль.
В. В. Маяковский. Как писать стихи
«Причина» справедливости неравенства
Однако, пожелай мы придать этому объяснению точный смысл, нам не хватило бы этого номера «Кванта». Удовлетворимся же тем, что разберём
Иллюстративный пример. Пусть
Скажем, схема
Вся тонкость в том, что коэффициенты выражаются через параметры (согласно схеме) арифметическими средствами — поэтому-то наша кривая многочленов, представимых схемой, и будет «нормальной» кривой, содержащей лишь «ничтожную часть» точек плоскости. Возможно, читателям известно, что существуют кривые, которые заполняют всю плоскость (см. книгу Г. Штейнгауза «Математический калейдоскоп», с. 78), так что соответствующие схемы (существование их в принципе невозможно!) представляли бы все многочлены степени 2 и были бы универсальными.
§ 10. И последний
Девочке четырёх с половиной лет прочли «Сказку о рыбаке и рыбке».
— Вот глупый старик, — возмутилась она, — просил у рыбки то новый дом, то новое корыто. Попросил бы сразу новую старуху.
К. Чуковский. От двух до пяти
Итак, мы доказали (§§ 7—9), что достоинства универсальных
схем почти исчерпаны схемой § 5. Но остаётся ещё возможность искать для каждого многочлена свою схему, намного более
экономную, чем та, которую можно для него получить, используя
Отметим, прежде всего, что индивидуальную схему степени
Возьмём любую индивидуальную схему для конкретного
многочлена степени
Пример. Схема многочлена (в) из § 3 после
замены чисел 1, 1 буквами
После такой замены из всех сверхэкономичных индивидуальных
схем получится лишь конечное число разных схем (см.
упражнение 6), каждая из которых представляет, согласно § 9,
лишь «ничтожную часть» многочленов степени
Итак, многочлены, которые могут быть вычислены быстрее, чем за
Ответы, указания, решения
- Для многочлена (в) — не более
$\dfrac32\log_2(n+1)+2$ $({\times};{:})$ -операции и два вычитания; для многочлена (г) — не более$\dfrac32\log_2n+1$ $({\times};{:})$ -операции и одно сложение. $p_1=x\cdot x=x^2$, $p_2=x^2\cdot x^2=x^4$, $$ f(x)=(p_2+p_1+1)(p_2-x+1). $$- Заметим, что
$x\cdot f(x)-f(x)=x^{n+1}+x^n+\ldots+x-(n+1)$; отсюда $$ \begin{gather*} f(x)=[x^{n+1}+x^n+\ldots+x+1-(n+2)]:(x-1)=\\ =[(x^{n+2}-1):(x-1)-(n+2)]:(x-1). \end{gather*} $$ $f(x)=\dfrac12[(x+1)^{2n}+(x-1)^{2n}]$. $p_1=x\cdot x=x^2$; $$ f(x)=\left(\left(\left(\dfrac1{8!}p_1-\dfrac1{6!}\right)p_1+\dfrac1{4!}\right) p_1-\dfrac1{2!}\right)p_1+1. $$
Пусть
$f(x)=x^{2k}+a_1x^{2k-1}+\ldots+a_{2k}$. Нам нужно по коэффициентам
$a_1$, $\ldots$, $a_{2k}$ многочлена$f(x)$ найти параметры$b_1$, $\ldots$, $b_{2k}$, превращающие последнюю строку схемы$(7.k)$ в тождество.Параметр
$b_1$ — единственный, для которого существует формула, причём простая.Лемма 1. Справедливо соотношение $$ a_1=kb_1+1.\tag{I} $$
Доказательство проводится индукцией по
$k\ge2$. При
$k=2$ $a_1=2b_1+1$ согласно (6) (роль$b_1$ играет в (6) параметр$A$). Пусть
$k\ge3$, и пусть в схеме$(7.k)$ $$ p_{k-1}=x^{2k-2}+\alpha x^{2k-3}+\ldots; $$ тогда $$ \begin{gather*} p_k=p_{k-1}(p_1+b_{2k-1})+b_{2k}=\\ =(x^{2k-2}+\alpha x^{2k-3}+\ldots)(x^2+b_1x+b_{2k-1})+b_{2k}=\\ =x^{2k}+(\alpha+b_1)x^{2k-1}+\ldots, \end{gather*} $$ так что, если по предположению индукции$\alpha=(k-1)b_1+1$, то$a_1=\alpha+b_1=kb_1+1$. Возможность вычисления значений остальных параметров по значениям коэффициентов также доказывается индукцией по
$k\ge2$. База индукции.
$k=2$, $n=4$. Схема (5), формулы (6).Посылка индукции. Пусть при некотором
$j=k-1\ge2$ схема$(7.k{-}1)$ универсальна, т. е. любому набору чисел$A_1$, $A_2$, $\ldots$, $A_{2k-2}$ соответствуют значения$b_1$, $b_2$, $\ldots$, $b_{2k-2}$ параметров, подставив которые в схему$(7.k{-}1)$, мы получим многочлен $$ p_{k-1}(x)=x^{2k-2}+A_1x^{2k-3}+\ldots+A_{2k-2}.\tag{II} $$Шаг индукции. Тогда схема
$(7.{k-1})$ также универсальна. Выпишем предпоследнюю строку этой схемы: $$ p_k(x)=p_{k-1}(x)\cdot(x^2+b_1x+b_{2k-1})+b_{2k}.\tag{III} $$ Согласно нашему предположению (посылка индукции), для нахождения значений параметров$b_1$, $\ldots$, $b_{2k}$, превращающих многочлен$p_k(x)$ из$(7.k)$ в многочлен$f(x)$ с данными коэффициентами$a_1$, $\ldots$, $a_{2k}$ нам достаточно найти такой многочлен$p_{k-1}(x)$ (точнее, его коэффициенты$A_1$, $A_2$, $\ldots$, $A_{2k-2}$ — см. (ІI)) и такие значения параметров$b_{2k-1}$, $b_{2k}$, чтобы после их подстановки в (III) выполнялось тождество$p_k(x)=f(x)$. Перемножив многочлены в правой части равенства (III) и приравняв коэффициенты полученного многочлена и многочлена$f(x)=x^n+a_1x^{n-1}+\ldots+a_{2k}$, мы сможем выписать систему$2k$ уравнений с неизвестными$A_1$, $\ldots$, $A_{2k-2}$, $b_{2k-1}$, $b_{2k}$ ($a_1$, $\ldots$, $a_n$ заданы,$b_1$ находится из равенства (I)); чтобы сократить запись формул, заменим параметр$b_{2k-1}$ символом$b$: $$ \begin{aligned} a_1&=A_1+b_1,\\ a_2&=A_2+b_1\cdot A_1+b,\\ a_3&=A_3+b_1\cdot A_2+b\cdot A_1,\\ {\ldots}&\,{\ldots}\,{\ldots}\,{\ldots}\,{\ldots}\,{\ldots}\\ a_{2k-2}&=A_{2k-2}+b_1\cdot A_{2k-3}+b\cdot A_{2k-4},\\ a_{2k-1}&=\quad b_1\cdot A_{2k-2}+b\cdot A_{2k-3},\\ a_{2k}&=b\cdot A_{2k-2}+b_{2k}. \end{aligned}\tag{IV} $$ Условимся обозначать уравнение системы (IV) с номером$j$ ($1\le j\le2k$) через (IV)-$j$. Тогда процесс решения системы (IV) можно описать в нескольких словах:$A_1$ выражается через$a_1$ из (IV)-1 и (I),$A_2$ выражается через$a_1$, $a_2$ и$b$ из (IV)-2,$A_3$ выражается через$a_1$, $a_2$, $a_3$ и$b$ из (IV)-3 и т. д. Последним из уравнения (IV)-$(2k-2)$ мы выразим неизвестное$A_{2k-2}$; затем, подставив в уравнение (IV)-$(2k-1)$ найденные выражения для$A_{2k-2}$ и$A_{2k-3}$, мы получим уравнение относительно$b$. Лемма 2. Неизвестные
$A_{2j-1}$ и$A_{2j}$ $(1\le j\le k-1)$ выражаются из системы$(\mathrm{IV})$ через параметр$b$ и коэффициенты$a_1$, $a_2$, $\ldots$, $a_{2k-2}$ согласно формулам($b_1$ выражается через$a_1$ согласно (I)) $$ \begin{gather*} A_{2j-1}=(-1)^{j-1}[(k-j)b_1+1]\,b^{j-1}+S_{1,j}(a_1,a_2,a_3)\,b^{j-2}+\ldots +S_{j-1,j}(a_1,a_2,\ldots,a_{2j-1}),\tag{V}\\ A_{2j}=(-1)^jb^j+T_{1,j}(a_1,a_2)\,b^{j-1}+\ldots+T_{j,j}(a_1,a_2,\ldots, a_{2j}).\tag{VI} \end{gather*} $$Доказательство. База индукции:
$j=1$, $A_1=a_1-b_1=[(k-1)b_1+1]b$, $A_2=-b+T_{1,1}(a_1,a_2)$. Посылка индукции — формулы (V), (VI) при
$1\le j\lt k-1$. Шаг индукции: $$ \begin{gather*} \mathrm{(a)}\quad A_{2j+1}=-bA_{2j-1}-b_1A_{2j}+a_{2j+1}= (-1)^j[(k-j)b_1+1]\,b^j-S_{1,j}(a_1,a_2,a_3)\,b^{j-1}-\ldots\\ \ldots-b_1(-1)^jb^j-b_1T_{1,j}(a_1,a_2)\,b^{j-1}-\ldots+a_{2j+1}= (-1)^j[(k-j-1)b_1+1]\,b^j+S_{1,j+1}(a_1,a_2,a_3)\,b^{j-1}+\ldots;\\[6pt] \mathrm{(b)}\quad A_{2j+2}=-bA_{2j}-b_1A_{2j+1}+a_{2j+2}= (-1)^{j+1}b^{j+1}+T_{1,j+1}(a_1,a_2)\,b^j+\ldots \end{gather*} $$
Лемма 3. Полученное после всех подстановок уравнение относительно
$b=b_{2k-1}$ имеет степень$k-1$ и единичный коэффициент при старшем члене (т. е. при$b^{k-1}$). Доказательство. Предположим, что в правой части уравнения (IV)-
$(2k-1)$ на левом крайнем месте (там, где сейчас пробел) стоит неизвестное$A_{2k-1}$ и выразим его через$b$, $a_1$, $\ldots$, $a_{2k-1}$; по формуле (V) (она по-прежнему применима здесь): $$ A_{2k-1}=(-1)^k[(k-k)+1]\,b^{k-1}+\ldots=(-1)^kb^{k-1}+\ldots \tag{VII} $$ Вспомним, что на самом деле$A_{2k-1}\equiv0$; умножив правую и левую части (VII) на$(-1)^k$, получим требуемое уравнение относительно$b$. Решив это уравнение, мы найдём значение параметра
$b=b_{2k-1}$, а затем по формулам (V), (VI) вычислим неизвестные$A_2$, $A_3$, $\ldots$, $A_{2k-2}$; параметр$b_{2k}$, находится из уравнения (IV)-$(2k)$. - Так как в каждой операции участвует не более двух параметров, то общее
число параметров в схеме с
$N$ операциями не больше$2N-1$ (хотя бы в одной операции должна участвовать переменная$x$). В первой операции участвуют два числа. Каждое из них есть либо$x$, либо один из не более чем$2N-1$ параметров; всего не более$(2N)^2$ возможностей. Во второй операции могут участвовать те же числа и результат первой операции; всего не более$(2N+1)^2$ возможностей, и т. д. Наконец, в последней операции могут участвовать не более$3N-1$ чисел (в том числе$N-1$ результатов предыдущих операций); всего не более$(3N-1)^2$ возможностей. Общее число различных вариантов не больше произведения этих чисел, т. е. $$ S_N\le(2N)^2\,(2N+1)^2\ldots(3N-1)^2=\left[\dfrac{(3N-1)!}{(2N-1)!}\right]^2. $$