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

В 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) ).

5. Докажите индукцией по k≥2 универсальность схемы (7.k).

Решение

Пусть f(x) = x2k + a1x2k–1 + ... + a2k.

Нам нужно по коэффициентам a1, ..., a2k многочлена f(x) найти параметры b1, ..., b2k, превращающие последнюю строку схемы (7.k) в тождество.

Параметр b1 — единственный, для которого существует формула, причём простая.

Лемма 1. Справедливо соотношение

a1 = kb1 + 1.

(I)

Доказательство проводится индукцией по k≥2.

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



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

Поделитесь этой записью или добавьте в закладки