Статья: Вычисление многочленов от Ньютона до наших дней
всего n–1 умножений и n сложений 2.
Схема Горнера настолько совершенна, что вопрос о возможности её улучшения не возникал два с половиной века и был задан «вслух» впервые лишь в 1954 году! Постановка этого вопроса (ответ на него предполагался отрицательным) имела важные и неожиданные последствия.
§3. Индивидуальные схемы
|
— Вы позволите мне записать эту романтическую историю, сэр? — спросил потрясенный мистер Снодграсс. — Сколько угодно, сэр, сколько угодно, ещё пятьдесят таких, если они вам по вкусу. Ч. Диккенс |
Уже в курсе школьной алгебры мы встречаемся с примерами многочленов, для которых существуют необычайно экономные схемы; единственный их недостаток — они не универсальны.
Сравнивая разные схемы по числу операций, мы будем объединять операции сложения и вычитания в группу «(+, –)-операций», а гораздо более трудоёмкие операции умножения и деления — в группу «(×, :)-операций». 3
Примеры.
(а) Многочлен f (x) = x2^k можно вычислить за k умножений (а не за 2k по Горнеру):
|
p1 = x·x = x2, p2 = p1·p1 = x4, ..., pk = pk–1·pk–1, f (x) = pk. |
(б) Многочлен f (x) = x15 можно вычислить за пять (×, :)-операций, так как f (x) = x15 = x16 : x = x2^4 : x.
(в) Многочлен f (x) = xn + xn–1 + ... + x + 1 вычисляется по формуле геометрической прогрессии: f (x) = (xn+1 – 1) : (x – 1).
(г) Многочлен
| f (x) = xn + | ( |
n 1 | ) | xn–1 + ... + | ( |
n n–1 | ) | x + 1; |
есть бином Ньютона: f (x) = (x + 1)n.
Число примеров можно, конечно, увеличить.
Упражнения
1. Докажите, что многочлены (а) и (б) не могут быть вычислены быстрее.
2. В «Задачнике «Кванта» № 12 за 1973 год была помещена задача (М240): доказать, что многочлен f (x) = xn может быть вычислен не более чем за 3/2 log2 n + 1 (×, :)-операций (n — натуральное число).
Пользуясь результатом этой задачи, оцените число операций для вычисления многочленов (в) и (г).
Решение
Для многочлена (в) — не более 3/2 log2 (n+1) + 2 (×, :)-операции и два вычитания; для многочлена (г) — не более 3/2 log2 n + 1 (×, :)-операция и одно сложение.
3. Постройте экономные схемы для многочленов:
| (I) | f (x) = x8 + x6 – x5 + 2x4 – x3 + x2 – x + 1; |
| (II) | f (x) = xn + 2xn–1 + 3xn–2 + ... + nx + n + 1; |
| (III) |
f (x) = x2n + К-во Просмотров: 786
Бесплатно скачать Статья: Вычисление многочленов от Ньютона до наших дней
|