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

Из этих формул ясно, что схема (5) универсальна.

Операции (6) мы будем называть предварительной обработкой коэффициентов многочлена; разумеется, они не включаются в число операций схемы: ведь для каждого данного многочлена они выполняются лишь однажды, а наша задача — научиться быстро считать значения произвольного, но фиксированного многочлена при разных x.

§5. Универсальная схема степени n

— Я думаю, — сказал глубокомысленно Пятачок, — что если бы Иа встал под деревом, а Пух встал к нему на спину, а я встал на плечи Пуха... — И если бы спина Иа-Иа неожиданно треснула, то мы бы все здорово посмеялись, — сказал Иа. А. А. Милн. Винни Пух

В 1958 году была найдена общая универсальная схема с предварительной обработкой коэффициентов. Структура этой схемы для многочлена чётной степени (n=2k) напоминает пирамиду — в основании лежит схема (5) (в её «прочности» мы уже убедились), содержащаяся в схеме степени 6, которая содержится в схеме степени 8 и т.д.:

  p1 = x(x + b1),   p2 = (p1 + b2)(p1 + x + b3) + b4,   p3 = p2(p1 + b5) + b6,   · · · · · · · · · · · · · · · · · ·   pk = pk–1(p1 + b2k–1) + b2k, f (x) = pk, k≥2.

(7.k)

схема (7.2) — это и есть схема (5). Результат схемы (7.k) — многочлен pk(x) степени n = 2k; многочлен же нечётной степени n = 2k + 1 можно представить в таком виде:

f (x) = x(x2k + a1x2k–1 + ... + a2k) + a2k+1;

(8)

многочлен в круглых скобках вычисляется по схеме (7.k). В итоге схема содержит k умножений и 2k+1 сложений для многочлена чётной степени n = 2k и k+1 умножений и 2k+2 сложений для многочлена нечётной степени n = 2k + 1 (с учётом (7.k) и (8) ).

Упражнения

4. Найдите формулы предварительной обработки коэффициентов, аналогичные формулам (6), для схемы (7.3) вычисления многочленов шестой степени.

Рекомендуем скачать другие рефераты по теме: бесплатные курсовые работы, банк курсовых.





Предыдущая страница реферата | 3  4  5  6  7  8  9  10  11  12  13 | Следующая страница реферата