Вычисление многочленов — от Ньютона до наших дней
| Категория реферата: Рефераты по математике
| Теги реферата: изложение по русскому, культурология
| Добавил(а) на сайт: Krasil'nikov.
Предыдущая страница реферата | 4 5 6 7 8 9 10 11 12 13 14 | Следующая страница реферата
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. Параметры в операциях
|
|
Дама сдавала в багаж диван, чемодан, саквояж, картину, корзину, картонку и маленькую собачонку. С. Я. Маршак Рекомендуем скачать другие рефераты по теме: бесплатные курсовые работы, банк курсовых. Категории:Предыдущая страница реферата | 4 5 6 7 8 9 10 11 12 13 14 | Следующая страница реферата Поделитесь этой записью или добавьте в закладки |
|
Главная