Э. Г. Бeлага
§1. Многочлены — инструмент вычислителя
Ну,начнём! Когда мы доберёмся до конца этой истории, будем знать больше, чемтеперь.
Г. X. Андерсен
Внеобозримом царстве функций многочлены занимают, на первый взгляд, оченьскромное место. Однако это первое впечатление обманчиво.
Многочлены,действительно, предельно просты: алгебраическая запись
f(x) = xn + a1xn–1 + a2xn–2 +… + an–1x + an (1)
являетсяодновременно и формулой для вычисления значений многочлена1. Хотявыражения типа cosx, 5√x, 10x,log2x намного лаконичнее, с вычислительной точки зрения онибессодержательны: для вычисления, скажем чисел cos17°, 5√2, 100,13 или log27 нужны специальныеприближённые формулы (или таблицы, составленные с помощью тех же формул). Какправило, в таких формулах появляются многочлены: например,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 + (
n
1 )
xn–1 +… + (
n
n–1 ) x + 1;
естьбином Ньютона: f(x) = (x + 1)n.
Числопримеров можно, конечно, увеличить.
§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) ).
5.Докажите индукцией по k≥2универсальность схемы (7.k).
Решение
Пустьf(x) = x2k + a1x2k–1 +… + a2k.
Намнужно по коэффициентам a1, ..., a2k многочлена f(x) найтипараметры b1, ..., b2k, превращающие последнюю строкусхемы (7.k) в тождество.
Параметрb1 — единственный, для которого существует формула, причём простая.
Лемма 1. Справедливо соотношение
a1 = kb1 + 1. (I)
Доказательство проводится индукцией по k≥2.
Еслиk=2, то a1= kb1 + 1 согласно (6) (роль b1 играет в (6) параметр A).
Пустьk≥3, ипусть в схеме (7.k)
pk–1(x) = x2k–2 + αx2k–3 +… ;
тогда
pk = pk–1(p1 + b2k–1)+ b2k =
= (x2k–2 + αx2k–3+ ...)(x2 + b1x + b2k–1) + b2k =
= x2k + (α+ b1)x2k–1 +… ,
такчто, если по предположению индукции α = (k – 1)b1 + 1, то a1= α + b1 = kb1 + 1.
Возможностьвычисления значении остальных параметров по значениям коэффициентов такжедоказывается индукцией по k≥2.
Базаиндукции. k=2, n=4. Схема (5),формулы (6).
Посылкаиндукции. Пусть при некотором j=k–1≥2схема (7.k–1) универсальна, то есть любому набору чисел A1, A2,..., A2k–2 соответствуют значения b1, b2, ...,b2k–2 параметров, подставив которые в схему (7.k–1), мы получиммногочлен
pk–1(x) = x2k–2 + A1x2k–3 +… + A2k–2. (II)
Шагиндукции. Тогда схема (7.k) также универсальна. Выпишем предпоследнюю строкуэтой схемы:
pk(x) = pk–1(x)·(x2 + b1x + b2k–1) + b2k. (III)
Согласнонашему предположению (посылка индукции), для нахождения значений параметров b1,b2, ..., b2k, превращающих многочлен pk(x) из(7.k) в многочлен f(x) с данными коэффициентами a1, a2,..., a2k нам достаточно найти такой многочлен pk–1(x)(точнее, его коэффициенты A1, A2, ..., A2k–2 —см. (II)) и такие значения параметров b2k–1, b2k, чтобыпосле их подстановки в (III) выполнялось тождество pk(x) = f(x).Перемножив многочлены в правой части равенства (III) и приравняв коэффициентыполученного многочлена и многочлена f(x) = xk + a1xk–1+… + a2k, мы сможем выписать систему 2k уравнений с неизвестнымиA1, A2, ..., A2k–2, b2k–1, b2k,(a1, ..., a2k заданы, b1 находится изравенства (I)); чтобы сократить запись формул, заменим параметр b2k–1символом b:
a1 = A1 + b1,
a2 = A2 + b1·A1 + b,
a3 = A3 + b1·A2 + b·A1,
. . . . . . . . . .
a2k–2 = A2k–2 + b1·A2k–3 + b·A2k–4,
a2k–1 = b1·A2k–2 + b·A2k–3,
a2k = b1·A2k–2 + b2k. (IV)
Условимсяобозначать уравнение системы (IV) с номером j (1≤j≤2k) через (IV)-j.Тогда процесс решения системы (IV) можно описать в нескольких словах: A1выражается через a1 из (IV)-1 и (I), A2 выражается черезa1, a2 и b из (IV)-2, A3 выражается через a1,a2, a3 и b из (IV)-3 и т.д. Последним из уравнения(IV)-(2k–2) мы выразим неизвестное A2k–2; затем, подставив вуравнение (IV)-(2k–1) найденные выражения для A2k–2 и A2k–3,мы получим уравнение относительно b.
Лемма 2. Неизвестные A2j–1 и A2j выражаютсяиз системы (IV) через параметр b и коэффициенты a1, a2,..., a2k–2; согласно формулам (b1 выражается через a1согласно (I))
A2j–1 = (–1)j–1[(k – j)b1 + 1]bj–1 +
+ S1,j(a1, a2, a3)bj–2 +… + Sj–1,j(a1, a2, ..., a2j–1), (V)
A2j = (–1)jbj + T1,j(a1, a2)bj–1 +… + Tj,j(a1, a2, ..., a2j). (VI) /> /> />
Доказательство. База индукции: j=1, A1 = a1 – b1 = [(k –1)b1 + 1]b, A2 = –b + T1,1(a1, a2).
Посылка индукции — формулы (V), (VI) при 1≤j
Шагиндукции:(a)
A2j+1 = –bA2j–1 – b1A2j + a2j+1 =
= (–1)j[(k – j)b1 + 1]bj – S1,j(a1, a2, a3)bj–1 –… –
– b1(–1)jbj – b1T1,j(a1, a2)bj–1 –… + a2j+1 =
= (–1)j[(k – j – 1)b1 + 1]bj + S1,j+1(a1, a2, a3)bj–1 +… ; (b)
A2j+2 = –bA2j – b1A2j+1 + a2j+2 = (–1)j+1bj+1 + T1,j+1(a1, a2)bj + ... /> /> />
Лемма 3. Полученное после всех подстановок уравнение относительноb = b2k–1 имеет степень k–1 и единичный коэффициент при старшем члене (то есть при bk–1).
Доказательство. Предположим, что в правой частиуравнения (IV)-(2k–1) на левом крайнем месте (там, где сейчас пробел) стоитнеизвестное A2k–1, и выразим его через b, a1, ..., a2k–1по формуле (V) (она по-прежнему применима здесь):
A2k–1 = (–1)k[(k – k) + 1]bk–1 +… = (–1)kbk–1 + .... (VII)
Вспомним,что на самом деле A2k–1 ≡ 0; умножив правую и левую части(VII) на (–1)k, получим требуемое уравнение относительно b.
Решивэто уравнение*), мы найдём значение параметра b = b2k–1,а затем по формулам (V), (VI) вычислим неизвестные A2, A3,..., A2k–2; параметр b2k находится из уравнения [IV]-(2k).
*) Такназываемая «основная теорема алгебры», открытая великим К.Ф.Гауссом,утверждает, что многочлен степени n>0 всегда имеет хотя бы один корень. Несмотря на то, чтопри n≥5формул для нахождения этого корня и не существует, разработаны методы нахождениявсех корней многочлена с любой точностью.
Начинаяс третьей строки, схема (7.k) очень напоминает схему Горнера(3); разница лишь втом, что теперь после каждого умножения степень увеличивается не на единицу, ана два.
Итак,нам удалось уменьшить число умножений по сравнению со схемой Горнера вдвое.Какой ценой? Из решения упражнения 5 видно, что процесс вычисления параметров b1,b2, ..., b2n по коэффициентам a1, a2,..., a2n очень сложен, — он включает в себя решение серии уравненийс одним неизвестным степени k–1,k–2,… Этоозначает, в частности, что при k≥6 (n≥12)формул вычисления параметров нет4, хотя, разумеется, их значениямогут быть найдены приближёнными методами с любой степенью точности.
Здесьвозникает ещё одно затруднение, оказавшееся, правда, преодолимым. До сих пор мыне уточняли, значения каких — действительныхили комплексных— многочленов мы вычисляем. Схема Горнера применима и в том, и в другом случае,схема же (7.k) преимущественно «комплексная» — действительным коэффициентаммогут соответствовать комплексные параметры. Появление комплексных чисел при вычислениидействительных многочленов намного увеличивает число арифметических операций5.К счастью, в 1960году схему (7.k) небольшим усложнением удалось превратить вдействительную; однако полные доказательства в этом случае уже очень непросты.
§6. О схемах вообще...
—Минуточку, минуточку — раздались протестующие голоса. — Избегайте, пожалуйста,научных терминов, объясняйте популярно…
—Верно! — подтвердили остальные. — Говорите понятнее… Что такое лес?
Я. Осенка. Загородная прогулка в 2050 году
Пришловремя спросить, нет ли схем, более экономных, чем схема (7.k)? Но тогда неизбежени вопрос — что такое схема?
Определение. (I). Схема с предварительной обработкойкоэффициентов — это последовательность арифметических операций, в которыхучаствуют переменная x, параметры b1, b2, ..., bmи результаты предшествующих операций. Результат последней операции назовемрезультатом схемы. (II). Если при некотором наборе значений параметров b1,..., bm результат схемы есть данный многочлен степени n, то мыскажем, что схема представляет этот многочлен. (III). Если схема представляетмногочлен, то процесс вычисления по его коэффициентам соответствующего наборазначений параметров назовем предварительной обработкой коэффициентов. (IV).Схема называется универсальной степени n, если она представляет любой многочленстепени n вида (1).
Примеры. 1. Схема (7.k) — универсальная (степени n=2k); то же верно и для схемы Горнера(параметры — сами коэффициенты).
2.Схема p(x) = (xn+1 – b1)/(x – b2) представляетмногочлен (в) §3 при b1 = b2 = 1.
Упражнение6. Докажите, что общее число SN схем (всехстепеней), содержащих не более N операций, конечно и не превосходит числа6 [(3N – 1)!/(2N – 1)!]2.
Решение
Таккак в каждой операции участвует не более двух параметров, то общее числопараметров в схеме с N операциями не больше 2N–1 (хотя бы в одной операции должнаучаствовать переменная x). В первой операции участвуют два числа. Каждое из нихесть либо x, либо один из не более чем 2N–1 параметров; всего не более (2N)2возможностей. Во второй операции могут участвовать те же числа и результатпервой операции; всего не более (2N+1)2 возможностей, и так далее. Наконец, впоследней операции могут участвовать не более 3N–1 чисел (в том числе N–1 результатпредыдущих операций); всего не более (3N–1)2 возможностей. Общее число различныхвариантов не больше произведения этих чисел, то есть
SN ≤ (2N)2 (2N + 1)2…(3N – 1)2 = [(3N – 1)!/(2N – 1)!]2.
§7.… И о наилучшей из них, в частности
Положение,в котором мы находимся, заставляет нас прибегать ко всестороннему изучениюпредмета.
Платон
Теперьнаш вопрос о наилучших схемах степени n приобрёл точный смысл, и можно дать нанего точный ответ: схема из §5 почти наилучшая — любая универсальная схемастепени n содержит не менее ½(n–1) (×,:)-операций и не менее n–1 (+,–)-операций.
Справедливостьэтого утверждения можно вывести из двух важных свойств схем:
числоm параметров универсальной схемы степени n не меньше числа коэффициентов, тоесть m≥n;
впромежутке между двумя (×,:)-операциями любой (не обязательноуниверсальной) схемы может появиться не более двух по-настоящему новых параметров (все остальныебудут «лишними»), а между двумя (+,–)-операциями — не более одного.
Второесвойство стоит сформулировать более строго: если схема содержит r(×,:)-операций (или s (+,–)-операций), то число m параметров либо сразуне больше 2r+1(соответственно s+1),либо без ущерба для свойств схемы может быть уменьшено до 2r+1 (соответственно, s+1), то есть m ≤ 2r + 1 и m ≤s + 1.
Итак,n ≤ m ≤ 2r + 1 и n ≤ m ≤ s + 1, отсюда ½(n – 1) ≤r и n – 1 ≤ s.
—Но вы совсем забыли о схеме Горнера! — прервёт нас читатель, которому больше подуше классическая ясность схем без предварительной возни с коэффициентами. —Ведь она не зря кажется предельно экономной!
—Схема Горнера действительно наилучшая среди схем, в которых параметрамиявляются сами коэффициенты. Недостаток места не позволяет нам изложитькрасивое, но не очень простое доказательство этого факта, найденное в 1960году.
Атеперь займёмся двумя сформулированными выше свойствами схем, сначала вторым.
§8. Параметры в операциях
Дамасдавала в багаж
диван,чемодан, саквояж,
картину,корзину, картонку
ималенькую собачонку.
С. Я. Маршак
Нашеопределение схемыне накладывало никаких ограничений на форму её записи. Мы назовём элементарнойзапись схемы типа «одна строка — одна операция», когда запоминается (иобозначается своим символом) результат каждой операции схемы; примеры: эпиграф (хотя это и не схема,а скорее багажная квитанция), схема для многочлена x2^k (§3) — в нейкаждый результат используется больше одного раза и потому нуждается взапоминании.
Недля всех схем элементарная форма записи является единственной: если результаткакой-то операции используется лишь однажды, то эту операцию можно сразувключить в ту строку, в которой участвует её результат. (Примеры: каждая строка схемы (3),начиная со второй, включает две операции, а схемы (7.k) — не менее трёх.)Интересно, что схема (7.k) не допускает записи меньше, чем в две строки, таккак результат первого умножения используется многократно, а схема (3) —допускает (формула (2) ).
Переходяк доказательству свойства 2), рассмотрим элементарную форму записи схемы иобозначим через q1, ..., qr результаты(×,:)-операций. Перепишем схему в «(×,:)-форме»: «одна строка —одна (×,:)-операция». При этом число (+,–)-операций может заметновозрасти — мы ведь не запоминаем их результаты; но сейчас нас интересует толькочисло (×,:)-операций, а оно остаётся прежним. Первые r строк схемы в«(×,:)-форме» имеют вид
qj = (Aj ± Bj ± ...) ×: (Cj ± Dj ± ...), 1 ≤ j ≤ r, (9)
гдеAj, Bj, ..., Cj, Dj,… — это либоbi, либо x, либо qs, где s
qr+1 = A ± B ± ... (10)
всете (+,–)-операции, которые ещё остаётся выполнить. Обозначим теперь через d'jи d"j алгебраические суммы всех параметров bi влевой и правой скобках (9), а через dr+1 — в (10) (даже если ихкое-где в (9) и (10) нет вовсе). Перепишем теперь (9) и (10), пользуясь новымипараметрами d'j, d"j (1≤j≤r), dr+1.Полученная схема будет универсальной, и предварительная обработка коэффициентовсостоит в вычислении параметров bi для исходной схемы (9), (10), азатем уже параметров d'j, d"j. Новая схемапредставляет все многочлены, что и исходная, и содержит по два параметра d',d" на каждую (×,:)-операцию плюс, возможно, ещё один параметр dr+1.
Доказательстводля (+,–)-операций аналогично; соответствующие построения выполнитесамостоятельно.
§9. Параметры универсальной схемы
Янарочно заостряю, упрощаю и карикатурю мысль.
В. В. Маяковский. Как писать стихи
«Причина»справедливости неравенства m≥nдля универсальных схем очень проста: если схема степени n универсальна, то естьпредставляет все многочлены степени n, то каждому такому многочлену долженсоответствовать свой набор параметров; поэтому «число» различных наборовпараметров должно быть не меньше «числа» разных многочленов.
Однако,пожелай мы придать этому объяснению точный смысл, нам не хватило бы этогономера «Кванта». Удовлетворимся же тем, что разберём иллюстративный пример. Пусть n=2, f(x) = x2+ a1x + a2. Каждый конкретный многочлен можно изобразить точкой на плоскости скоординатами a1, a2. Если для схемы m
Скажем,схема p = (x + b)(x – b) + bx = x2 + bx – b2 представляетвсе многочлены, изображаемые точками параболы (a1 = b, a2= –b2) или a2 = –a12.
Всятонкость в том,что коэффициенты выражаются через параметры (согласно схеме) арифметическимисредствами — поэтому-то наша кривая многочленов, представимых схемой, и будет«нормальной» кривой, содержащей лишь «ничтожную часть» точек плоскости.Возможно, читателям известно, что существуют кривые, которые заполняют всюплоскость (см. книгу Г.Штейнгауза «Математический калейдоскоп», с.78), так чтосоответствующие схемы (существование их в принципе невозможно!) представляли бывсе многочлены степени2 и были бы универсальными.
§10. И последний
Девочкечетырех с половиной лет прочли «Сказку о рыбаке и рыбке».
—Вот глупый старик, — возмутилась она, — просил у рыбки то новый дом, то новоекорыто. Попросил бы сразу новую старуху.
К. Чуковский. От двух до пяти
Итак,мы доказали (§§7–9), что достоинства универсальных схем почти исчерпаны схемой §5. Но остаётсяещё возможность искать для каждого многочлена свою схему, намного болееэкономную, чем та, которую можно для него получить, используя (7.k)–(8) иликакую-нибудь другую универсальную схему. Правда, девочка из эпиграфа,убеждённая в силе универсальных методов, предостерегает нас от увлеченияпоисками всё новых и новых сверхэкономных индивидуальных схем для отдельныхмногочленов (вроде схем §3); сейчас мы покажем бесполезность таких поисков.
Отметим,прежде всего, что индивидуальную схему степени n разумно считать«сверхэкономной», если она содержит «ненормально мало» (по сравнению суниверсальными схемами) либо (×,:)-операций, либо (+,–)-операций и еслиобщее число её операций не больше, скажем, 100n (для сравнения: общее число операцийсхемы Горнера равно 2n–1).
Возьмёмлюбую индивидуальную схему для конкретного многочлена степени n и заменим в нейвсе числа буквами b1, b2, ...; при этом получим схему,удовлетворяющую всем требованиям определения §6.
Пример. Схема многочлена (в) из §3 после замены чисел 1, 1буквами b1, b2 превращается в схему p(x) = (xn+1– b1): (x – b2), представляющую все многочлены вида
f(x) = xn + axn–1 + a2xn–2+… + an–1x + an
(приb1 = an+1, b2 = a) и только их.
Послетакой замены из всех сверхэкономных индивидуальных схем получится лишь конечноечисло разныхсхем (см. упражнение 6), каждая из которых представляет, согласно §9, лишь«ничтожную часть» многочленов степени n.
Итак,многочлены, которые могут быть вычислены быстрее, чем за ½(n–1)(×,:)-операций или n–1(+,–)-операций, — исключение из общего правила. Тем не менее, при построениисхемы для конкретного многочлена стóит использовать его особенности,если они бросаются в глаза.
Примечания
1. Чтобы упростить выкладки, мыограничимся многочленами с единичным коэффициентом при старшем члене (a0= 1); там, где это будет необходимо, мы поясним, как поступать в общем случае(a0≠ 1). назад к тексту
2. Если a0≠ 1, то мыположим p1 = a0x + a1 (число умножений приэтом возрастает на единицу). назад к тексту
3. Читается: «плюс-минус-операции»,«умножить-разделить-операции». назад к тексту
4. Под формулой обычно понимают наборарифметических операций, корней, степеней. Вы, наверное, знаете, что Э.Галуа и Н.Абель,гениальные (и оба очень рано умершие) математики XIXвека, доказали, что длянахождения корней многочленов пятой и более высоких степеней таких общих формулне существует (см. «Квант», 1973, №10, с.3—12). назад к тексту
5. Одно «комплексное» сложение — это два«действительных», одно «комплексное» умножение — четыре(!) умножения и двасложения. назад к тексту
6. Чтобы иметь возможность сравниватьсхемы, разумно для обозначения их параметров использовать буквы, например, изпоследовательности b1, b2, ..., bk, ...;понятно, что тогда схемы, отличающиеся лишь названиями параметров, считаютсяодинаковыми.
Список литературы
Дляподготовки данной работы были использованы материалы с сайта ega-math.narod.ru/