Рефераты | Рефераты по математике | Вычисление многочленов — от Ньютона до наших дней |
Из этих формул ясно, что схема (5) универсальна.
Операции (6) мы будем называть предварительной обработкой коэффициентов многочлена; разумеется, они не включаются в число операций схемы: ведь для каждого данного многочлена они выполняются лишь однажды, а наша задача — научиться быстро считать значения произвольного, но фиксированного многочлена при разных x.
§5. Универсальная схема степени n
|
|
— Я думаю, — сказал глубокомысленно Пятачок, — что если бы Иа встал под деревом, а Пух встал к нему на спину, а я встал на плечи Пуха... — И если бы спина Иа-Иа неожиданно треснула, то мы бы все здорово посмеялись, — сказал Иа. А. А. Милн. Винни Пух |
В 1958 году была найдена общая универсальная схема с предварительной обработкой коэффициентов. Структура этой схемы для многочлена чётной степени (n=2k) напоминает пирамиду — в основании лежит схема (5) (в её «прочности» мы уже убедились), содержащаяся в схеме степени 6, которая содержится в схеме степени 8 и т.д.:
|
(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) вычисления многочленов шестой степени.
