Рефераты | Рефераты по математике | Вычисление многочленов — от Ньютона до наших дней |
Наше определение схемы не накладывало никаких ограничений на форму её записи. Мы назовём элементарной запись схемы типа «одна строка — одна операция», когда запоминается (и обозначается своим символом) результат каждой операции схемы; примеры: эпиграф (хотя это и не схема, а скорее багажная квитанция), схема для многочлена 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<j. Если (×, :)-операция из qr не была заключительной операцией исходной схемы, то мы объединим в строку
|
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<n=2, то она либо совсем не содержит параметров (m=0), либо содержит один параметр (m=1). В первом случае схема представляет единственный многочлен (точка на плоскости), во втором — семейство многочленов, которое изобразится на «плоскости многочленов» в виде некоторой «хорошей» кривой.
Скажем, схема 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).
