Задача 31.
Многочлен
задается набором своих коэффициентов a[i], i=0,..,n. Необходимо вычислить коэффициенты b[i] такого многочлена, что
для заданного d.
|
Решение задачи 31.
Рассмотрим следующую задачу:
Разделить полином p(x)=a[n]*xn + ... + a[1]*x+a[0] на v(x)=(x-d), т.е. найти такую константу - остаток r и такое частное s(x)=s[n-1]*x(n-1)+ ... + s[1]*x+s[0], что
p(x)=s(x)(x)+r.
Делить будем в столбик. Рассмотрим операцию деления полиномов на примере:
3x2+2x+5 x-2
3x2-6x ..3x+8
....8x+5
....8x-16
.......21
Тут r=21, s(x)=3x+8.
Видно, что коэффициент s[n-1] при старшей степени x в s равен коэффициенту при старшей степени x в p, а остальные коэффициенты в s находятся по формулам:
s[t-1]=(-d)*s[t]+p[t];
r=(-d)*s[0]+p[0].
В наглядной форме это можно записать в виде так называемой схемы Горнера:
Тогда проведенное выше деление можно записать в следующем виде:
Вернемся к исходной задаче. Приравняем полиномы: p0(x)=a[n]*xn+a[n-1]*x(n-1)+ ... +a[1]*x+a[0]=
=b[n](x-d)n+ ... +b[1]*(x-d)+b[0].
Находим остаток от деления полиномов справа и слева от знака равенства на (x-d). Слева все слагаемые, кроме последнего, делятся на (x-d) нацело. Поэтому
P0(x)=(x-d)*p1(x)+b[0].
Получаем, что
P1(x)=b[n]*(x-d)(n-1)+ ... +b[2]*(x-d)+b[1].
Аналогично находим b[1]:
P1(x)=(x-d)*p2(x)+b[1],
затем по p2(x) определяем b[2], и т.д., пока не найдем b[n].
Особенно удобно это записывается в виде схемы Горнера (обратите внимание, что в верхней строке записаны коэффициенты p0, то, что получается в строке ниже - это коэффициенты p1, к которым также можно применить схему Горнера, находя коэффициенты p2, и т.д.)
Пример: p(x)=3x2+2x+5, d=-2,
Получаем
3x2+2x+5=3(x-2)2+14(x-2)+21.
|
