Статья: Вычисление многочленов от Ньютона до наших дней
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.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) вычисления многочленов шестой степени.
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.
Если k=2, то a1 = kb1 + 1 согласно (6) (роль b1 играет в (6) параметр A).
Пусть k≥3, и пусть в схеме (7.k)
pk–1(x) = x2k–2 + αx2k–3 + ... ;
тогда
pk = pk–1(p1 + b2k–1) + b2k =
= (x2k–2 + αx2k–3 + ...)(x2 + b1x + b2k–1) + b2k =
= x2k + (α + b1)x2k–1 + ... ,
так что, если по предположению индукции α = (k – 1)b1 + 1, то a1 = α + b1 = kb1 + 1.
Возможность вычисления значении остальных параметров по значениям коэффициентов также доказывается индукцией по k≥2.
База индукции. k=2, n=4. Схема (5), формулы (6).