Квадратные корни

все те (+,–)-операции, которые ещё остаётся выполнить. Обозначим теперь через d'_j и d"_j алгебраические суммы всех параметров b_i в левой и правой скобках (9), а через d_r+1 — в (10) (даже если их кое-где в (9) и (10) нет вовсе). Перепишем теперь (9) и (10), пользуясь новыми параметрами d'_j, d"_j (1≤j≤r), d_r+1. Полученная схема будет универсальной, и предварительная обработка коэффициентов состоит в вычислении параметров b_i для исходной схемы (9), (10), а затем уже параметров d'_j, d"_j. Новая схема представляет все многочлены, что и исходная, и содержит по два параметра d', d" на каждую (×,:)-операцию плюс, возможно, ещё один параметр d_r+1.

Доказательство  для (+,–)-операций аналогично; соответствующие построения выполните самостоятельно.

§9. Параметры универсальной  схемы

Я нарочно заостряю, упрощаю и карикатурю мысль.

В. В. Маяковский. Как писать стихи

«Причина» справедливости неравенства m≥n для универсальных  схем очень проста: если схема степени n универсальна, то есть представляет все многочлены степени n, то каждому такому многочлену должен соответствовать свой набор параметров; поэтому «число» различных наборов параметров должно быть не меньше «числа» разных многочленов.

Однако, пожелай  мы придать этому объяснению точный смысл, нам не хватило бы этого  номера «Кванта». Удовлетворимся же тем, что разберём иллюстративный пример. Пусть n=2, f(x) = x² + a₁x + a₂. Каждый конкретный многочлен можно изобразить точкой на плоскости с координатами a₁, a₂. Если для схемы m<n=2, то она либо совсем не содержит параметров (m=0), либо содержит один параметр (m=1). В первом случае схема представляет единственный многочлен (точка на плоскости), во втором — семейство многочленов, которое изобразится на «плоскости многочленов» в виде некоторой «хорошей» кривой.

Скажем, схема p = (x + b)(x – b) + bx = x² + bx – b² представляет все многочлены, изображаемые точками параболы (a₁ = b, a₂ = –b²) или a₂ = –a₁².

Вся тонкость в  том, что коэффициенты выражаются через параметры (согласно схеме) арифметическими средствами — поэтому-то наша кривая многочленов, представимых схемой, и будет «нормальной» кривой, содержащей лишь «ничтожную часть» точек плоскости. Возможно, читателям известно, что существуют кривые, которые заполняют всю плоскость (см. книгу Г.Штейнгауза «Математический калейдоскоп», с.78), так что соответствующие схемы (существование их в принципе невозможно!) представляли бы все многочлены степени2 и были бы универсальными.

§10. И последний

Девочке четырех  с половиной лет прочли «Сказку  о рыбаке и рыбке».

— Вот глупый старик, — возмутилась она, —  просил у рыбки то новый дом, то новое корыто. Попросил бы сразу  новую старуху.

К. Чуковский. От двух до пяти

Итак, мы доказали (§§7–9), что достоинства универсальных схем почти исчерпаны схемой §5. Но остаётся ещё возможность искать для каждого многочлена свою схему, намного более экономную, чем та, которую можно для него получить, используя (7.k)–(8) или какую-нибудь другую универсальную схему. Правда, девочка из эпиграфа, убеждённая в силе универсальных методов, предостерегает нас от увлечения поисками всё новых и новых сверхэкономных индивидуальных схем для отдельных многочленов (вроде схем §3); сейчас мы покажем бесполезность таких поисков.

Отметим, прежде всего, что индивидуальную схему  степени n разумно считать «сверхэкономной», если она содержит «ненормально мало» (по сравнению с универсальными схемами) либо (×,:)-операций, либо (+,–)-операций и если общее число её операций не больше, скажем, 100n (для сравнения: общее число операций схемы Горнера равно 2n–1).

Возьмём любую  индивидуальную схему для конкретного  многочлена степени n и заменим в  ней все числа буквами b₁, b₂, ...; при этом получим схему, удовлетворяющую всем требованиям определения §6.

Пример. Схема  многочлена (в) из §3 после замены чисел 1, 1 буквами b₁, b₂ превращается в схему p(x) = (xⁿ⁺¹ – b₁) : (x – b₂), представляющую все многочлены вида

f(x) = xⁿ + ax^n–1 + a²x^n–2 + ... + a^n–1x + aⁿ

(при b₁ = aⁿ⁺¹, b₂ = a) и только их.

После такой  замены из всех сверхэкономных индивидуальных схем получится лишь конечное число  разных схем (см. упражнение 6), каждая из которых представляет, согласно §9, лишь «ничтожную часть» многочленов  степени n.

Итак, многочлены, которые могут быть вычислены быстрее, чем за ½(n–1) (×,:)-операций или n–1 (+,–)-операций, — исключение из общего правила. Тем не менее, при построении схемы для конкретного многочлена стóит использовать его особенности, если они бросаются в глаза.

Примечания

1. Чтобы упростить выкладки, мы ограничимся многочленами с единичным коэффициентом при старшем члене (a₀ = 1); там, где это будет необходимо, мы поясним, как поступать в общем случае (a₀ ≠ 1). назад к тексту

2. Если a₀ ≠ 1, то мы положим p₁ = a₀x + a₁ (число умножений при этом возрастает на единицу). назад к тексту

3. Читается: «плюс-минус-операции»,  «умножить-разделить-операции». назад к тексту

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

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

6. Чтобы иметь  возможность сравнивать схемы,  разумно для обозначения их параметров использовать буквы, например, из последовательности b₁, b₂, ..., b_k, ...; понятно, что тогда схемы, отличающиеся лишь названиями параметров, считаются одинаковыми.

Список  литературы

Для подготовки данной работы были использованы материалы с сайта http://ega-math.narod.ru/