Предыдущая страница реферата | 1  2  3  4  5  6  7  8

Теперь наш вопрос о наилучших схемах степени 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

Скачали данный реферат: Pavlenko, Безродный, Erzov, Филипов, Chervjachok, Ul'janin.
Последние просмотренные рефераты на тему: диплом купить, вопросы и ответы, реферат скачать без регистрации, реферат рф.

Предыдущая страница реферата | 1  2  3  4  5  6  7  8