Вычисление многочленов — от Ньютона до наших дней
Информация - Математика и статистика
Другие материалы по предмету Математика и статистика
(p1 + B)(p1 + x + C) + D,
?
f(x) = p2,
(5)где A, B, C и D параметры.
Пример. Многочлен x4 + 3x3 + 6x2 + 3x + 2 можно вычислять по схеме: p1 = x(x + A), f(x) = (p1 1)(p1 + x + 5) + 7, содержащей два умножения (вместо трёх по Горнеру) и пять (вместо четырёх) (+,)-операций; здесь A=1, B=1, C=5, D=7.
Выпишем явное выражение для p2(x):
p2(x) = x4 + (2A + 1)x3 + (A2 + A + B + C)x2 +
+ (AB + B + AC)x + BC + D;
приравняв коэффициенты f(x) и p2(x), выразим параметры, входящие в формулу(5), через коэффициенты(4):
A = (a 1)/2;
B = c bA + A2(A + 1);
C = b B A(A + 1);
D = d BC.
(6)Из этих формул ясно, что схема (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 = pk1(p1 + b2k1) + b2k, f(x) = pk, k?2.
(7.k)схема (7.2) это и есть схема (5). Результат схемы (7.k) многочлен pk(x) степени n=2k; многочлен же нечётной степени n=2k+1 можно представить в таком виде:
f(x) = x(x2k + a1x2k1 + ... + 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 + a1x2k1 + ... + 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)
pk1(x) = x2k2 + ?x2k3 + ... ;
тогда
pk = pk1(p1 + b2k1) + b2k =
= (x2k2 + ?x2k3 + ...)(x2 + b1x + b2k1) + b2k =
= x2k + (? + b1)x2k1 + ... ,
так что, если по предположению индукции ? = (k 1)b1 + 1, то a1 = ? + b1 = kb1 + 1.
Возможность вычисления значении остальных параметров по значениям коэффициентов также доказывается индукцией по k?2.
База индукции. k=2, n=4. Схема (5), формулы (6).
Посылка индукции. Пусть при некотором j=k1?2 схема (7.k1) универсальна, то есть любому набору чисел A1, A2, ..., A2k2 соответствуют значения b1, b2, ..., b2k2 параметров, подставив которые в схему (7.k1), мы получим многочлен
pk1(x) = x2k2 + A1x2k3 + ... + A2k2.(II)Шаг индукции. Тогда схема (7.k) также универсальна. Выпишем предпоследнюю строку этой схемы:
pk(x) = pk1(x)(x2 + b1x + b2k1) + b2k.(III)Согласно нашему предположению (посылка индукции), для нахождения значений параметров b1, b2, ..., b2k, превращающих многочлен pk(x) из (7.k) в многочлен f(x) с данными коэффициентами a1, a2, ..., a2k нам достаточно найти такой многочлен pk1(x) (точнее, его коэффициенты A1, A2, ..., A2k2 см. (II)) и такие значения параметров b2k1, b2k, чтобы после их подстановки в (III) выполнялось тождество pk(x) = f(x). Перемножив многочлены в правой части равенства (III) и приравняв коэффициенты полученного многочлена и многочлена f(x) = xk + a1xk1 + ... + a2k, мы сможем выписать систему 2k уравнений с неизвестными A1, A2, ..., A2k2, b2k1, b2k, (a1, ..., a2k заданы, b1 находится из равенства (I)); чтобы сократить запись формул, заменим параметр b2k1 символом b:
a1 = A1 + b1,
a2 = A2 + b1A1 + b,
a3 = A3 + b1A2 + bA1,
. . . . . . . . . .
a2k2 = A2k2 + b1A2k3 + bA2k4,
a2k1 = b1A2k2 + bA2k3,
a2k = b1A2k2 + b2k.(IV)Условимся обозначать уравнение системы (IV) с номером j (1?j?2k) через (IV)-j. Тогда процесс решения системы (IV) можно описать в нескольких словах: A1 выражается через a1 из (IV)-1 и (I), A2 выражается через a1, a2 и b из (IV)-2, A3 выражается через a1, a2, a3 и b из (IV)-3 и т.д. Последним из уравнения (IV)-(2k2) мы выразим неизвестное A2k2; затем, подставив в уравнение (IV)-(2k1) найденные выражения для A2k2 и A2k3, мы получим уравнение относительно b.
Лемма 2. Неизвестные A2j1 и A2j выражаются из системы (IV) через параметр b и коэффициенты a1, a2, ..., a2k2; согласно формулам (b1 выражается через a1 согласно (I))
A2j1 = (1)j1[(k j)b1 + 1]bj1 +
+ S1,j(a1, a2, a3)bj2 + ... + Sj1,j(a1, a2, ..., a2j1),(V)A2j = (1)jbj + T1,j(a1, a2)bj1 + ... + Tj,j(a1, a2, ..., a2j).(VI)Доказательство. База индукции: j=1, A1 = a1 b1 = [(k 1)b1 + 1]b, A2 = b + T1,1(a1, a2).
Посылка индукции формулы (V), (VI) при 1?j<k1.
Шаг индукции:
(a)A2j+1 = bA2j1 b1A2j + a2j+1 =
= (1)j[(k j)b1 + 1]bj S1,j(a1, a2, a3)bj1 ...
b1(1)jbj b1T1,j(a1, a2)bj1 ... + a2j+1 =
= (1)j[(k j 1)b1 + 1]bj + S1,j+1(a1, a2, a3)bj1 + ... ;(b)A2j+2 = bA2j b1A2j+1 + a2j+2 = (1)j+1bj+1 + T1,j+1(a1, a2)bj + ...Лемма 3. Полученное после всех подстановок уравнение относительно b = b2k1 имеет степень k1 и единичный коэффициент при старшем члене (то есть при bk1).
Доказательство. Предположим, что в правой части уравнения (IV)-(2k1) на левом крайнем месте (там, где сейчас пробел) стоит неизвестное A2k1, и выразим его через b, a1, ..., a2k1 по формуле (V) (она по-прежнему применима здесь):
A