Задание многочлена. Действия с многочленами в системе Mathematica
Как известно, многочленом от переменной называется выражение
вида
где
натуральное
число,
-
элементы некоторого числового поля,
называемые коэффициентами этого
многочлена. Выражения
называются членами многочлена,
- свободным членом.
Многочлен называется нулевым, если все его коэффициенты равны нулю.
Если
,
то
называют степенью многочлена, а
-
старшим членом многочлена.
В системе Mathematica многочлен можно задавать, например, таким способом
Вычислить значение этого многочлена при конкретном значении переменной можно так
f[11]
4649
Если мы хотим определить произвольный многочлен четвёртой степени, не указывая конкретных значений коэффициентов, то это можно сделать так
Многочлены можно складывать, вычитать и умножать по обычным правилам раскрытия скобок и приведения подобных членов. Продемонстрируем выполнение указанных действий над многочленами в системе Mathematica.
Система Mathematica позволяет производить указанные действия над многочленами при условии, что их коэффициенты принадлежат тому или иному классу вычетов по заданному модулю. Рассмотрим , например, вычисление произведения двух многочленов в поле классов вычетов по модулю 2.
Expand[f[x]*g[x],Modulus2]
Пусть
и
-
два многочлена и многочлен
не является нулевым. Тогда можно всегда
подобрать такую пару многочленов
и
,
частное и остаток, что
,
причём или нулевой многочлен или многочлен, степень которого меньше степени многочлена . Если многочлен является нулевым, то говорят, что многочлен делится на многочлен .
В системе Mathematica частное от деления многочлена на и остаток находятся следующим образом
f[x_]=
g[x_]=
q[x_]=PolynomialQuotient[f[x],g[x],x]
r[x_]=PolynomialRemainder[f[x],g[x],x]
Рассмотрим следующие примеры
Пример
2.1. Разделить с остатком многочлен
на многочлен
Решение.
r[x_]=PolynomialRemainder[f[x],g[x],x]
-5+25 x
q[x_]=PolynomialQuotient[f[x],g[x],x]
Пример
2.2. Найти частное и остаток от деления
многочлена
на многочлен
над полем классов вычетов по модулю 3.
Решение.
r[x_]=PolynomialMod[
PolynomialRemainder[f[x],g[x],x],Modulus3]
x
q[x_]=PolynomialMod[
PolynomialQuotient[f[x],g[x],x],Modulus3]
Производим проверку
Expand[g[x]*q[x]+r[x],Modulus3]
Наибольший общий делитель и наименьшее общее кратное многочленов.
Пусть два многочлена
и
делятся на многочлен
.
В этом случае многочлен
называется общим делителем многочленов
и
.
В частности,
называется наибольшим общим делителем,
если
делится на любой общий делитель
и
.
Может случиться, что наибольшим общим
делителем будет многочлен нулевой
степени. В этом случае говорят, что
многочлены
и
взаимно просты.
Для отыскания наибольшего общего делителя двух многочленов обычно используется алгоритм Евклида.
Пусть степень
больше или в крайнем случае равна степени
.
Делим
на
;
остаток, полученный при делении обозначим
через
.
Затем делим
на
,
получаем второй остаток
.Снова
делим
на, получаем третий остаток
и т.д. Вообще мы каждый раз делим предыдущий
остаток на последующий. При этом степени
остатков
всё время убывают. Следовательно мы
неизбежно должны придти к такому остатку
,
на который целиком разделится предыдущий
остаток
.
Если бы это не имело места, то процесс
деления продолжался без конца и мы
получили бы нелепость: степени остатков
убывают без конца. Так как степени
остатков являются целыми неотрицательными
числами, то этого быть не может.
Рассмотрим теперь,
как описанный алгоритм Евклида может
быть реализован в системе Mathematica.
Пусть
многочлен.
Функция CoefficientList[r[x],x]
даёт массив из
коэффициентов многочлена
,
в том случае, если многочлен не является
нулевым. В случае нулевого многочлена
этот массив получается пустым. Функция
Lenght[CoefficientList[r[x],x]]
даёт
число
элементов рассматриваемого массива.
Это число равно нулю тогда и только
тогда, когда
-
нулевой многочлен.
Реализация алгоритма Евклида в системе Mathematica будет выглядеть следующим образом.
Пример 3.2.Найти
наибольший общий делитель многочленов
и
Решение.
f1[x_]=f[x];g1[x_]=g[x];r1[x_]=
PolynomialRemainder[f1[x],g1[x],x];
Y=Length[CoefficientList[r1[x],x]];
While[Y1,f1[x_]=g1[x];g1[x_]=r1[x];r1[x_]=
PolynomialRemainder[f1[x],g1[x],x];
Y=Length[CoefficientList[r1[x],x]]]
g1[x]
r1[x]
0
Рассматриваемые многочлены являются взаимно простыми.
Наибольший общий делитель нескольких многочленов может быть найден в системе Mathematica следующим образом
Задаём полиномы
Находим наибольший общий делитель заданных полиномов
PolynomialGCD[f[x],g[x],h[x]]
-1+x
Если
- наибольший общий делитель многочленов
и
,
то всегда можно подобрать два таких
новых многочлена
и
,
что
.
(2.1)
Равенство (2.1) называют линейным представлением наибольшего общего делителя.
Многочлены и можно подобрать таким образом, что степень многочлена будет не больше степени многочлена , а степень многочлена - не больше степени многочлена . Сделать это можно, например, методом неопределённых коэффициентов.
Пример 3.3. Найти линейное представление наибольшего общего делителя следующих многочленов
Решение.
Находим наибольший общий делитель заданных полиномов
d[x_]=PolynomialGCD[f[x],g[x]]
1+x
Так как g[x]- многочлен третьей степени, то u[x] будем искать в виде многочлена второй степени; так как f[x] многочлен четвёртой степени, то многочлен v[x] будем искать в виде многочлена третьей степени.
A=Table[a[n-1],{n,1,7}];
d1[x_]=f[x]*u[x]+g[x]*v[x];
T1=Table[Coefficient[d1[x],x,n-1],{n,1,7}];
T2=Table[Coefficient[d[x],x,n-1],{n,1,7}];
T=Table[T1[[n]]T2[[n]],{n,1,7}];
R=Solve[T,A]
a[6]=0;
u[x_]=u[x]/.R[[1]]
v[x_]=v[x]/.R[[1]]
Expand[f[x]*u[x]+g[x]*v[x]]
1+x
Та же задача может быть решена другим способом. Положим
В
левом столбце- последовательность
делений, которая разрешена относительно
остатков. В правом столбце каждый остаток
выражен в виде
Мы хотим вычислить
и
.
Очевидно, что
,
.
Сравнивая обе части на
м
шаге, имеем
Отсюда получается следующая индуктивная процедура вычисления и :
Находим
как частное от деления
на
,
затем вычисляем
Покажем, как описанный алгоритм нахождения линейного представления наибольшего общего делителя можно реализовать в системе Mathematica .
Вводим заданные полиномы
Задаём начальные значения параметров цикла
a0[x_]=f[x];a1[x_]=g[x];u0[x_]=1;v0[x_]=0;u1[x_]=0;v1[x_]=1;
q[x_]=PolynomialQuotient[a0[x],a1[x],x];
a2[x_]=a0[x]-a1[x]*q[x];u2[x_]=u0[x]-u1[x]*q[x];v2[x_]=v0[x]-v1[x]*q[x];
Находим коэффициенты линейного представления наибольшего общего делителя u1[x]и v1[x] заданных многочленов и сам наибольший общий делитель a1[x]
While[Length[CoefficientList[a2[x],x]]>0,a0[x_]=a1[x];
a1[x_]=a2[x];q[x_]=PolynomialQuotient[a0[x],a1[x],x];
u0[x_]=u1[x];u1[x_]=u2[x];v0[x_]=v1[x];v1[x_]=v2[x];
a2[x_]=Expand[a0[x]-a1[x]*q[x]];
u2[x_]=Expand[u0[x]-u1[x]*q[x]];
v2[x_]=Expand[v0[x]-v1[x]*q[x]]]
u1[x]
1-x
v1[x]
a1[x]
3
Проверяем правильность решения задачи
Simplify[f[x]*u1[x]+g[x]*v1[x]]
3