85236 (763975), страница 3
Текст из файла (страница 3)
§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 (+, –)-операций, — исключение из общего правила. Тем не менее, при построении схемы для конкретного многочлена стóит использовать его особенности, если они бросаются в глаза. Список литературы Для подготовки данной работы были использованы материалы с сайта http://www.ega-math.narod.ru/
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
