Находим наибольший общий делитель заданных полиномов

PolynomialGCD[f[x],g[x],h[x]]

-1+x

Если Находим наибольший общий делитель заданных полиномов - student2.ru - наибольший общий делитель многочленов Находим наибольший общий делитель заданных полиномов - student2.ru и Находим наибольший общий делитель заданных полиномов - student2.ru , то всегда можно подобрать два таких новых многочлена Находим наибольший общий делитель заданных полиномов - student2.ru и Находим наибольший общий делитель заданных полиномов - student2.ru , что

Находим наибольший общий делитель заданных полиномов - student2.ru . (2.1)

Равенство (2.1) называют линейным представлением наибольшего общего делителя.

Многочлены Находим наибольший общий делитель заданных полиномов - student2.ru и Находим наибольший общий делитель заданных полиномов - student2.ru можно подобрать таким образом, что степень многочлена Находим наибольший общий делитель заданных полиномов - student2.ru будет не больше степени многочлена Находим наибольший общий делитель заданных полиномов - student2.ru , а степень многочлена Находим наибольший общий делитель заданных полиномов - student2.ru - не больше степени многочлена Находим наибольший общий делитель заданных полиномов - student2.ru . Сделать это можно, например, методом неопределённых коэффициентов.

Пример 3.3. Найти линейное представление наибольшего общего делителя следующих многочленов

Находим наибольший общий делитель заданных полиномов - student2.ru

Находим наибольший общий делитель заданных полиномов - student2.ru

Решение.

Находим наибольший общий делитель заданных полиномов - student2.ru

Находим наибольший общий делитель заданных полиномов - student2.ru

Находим наибольший общий делитель заданных полиномов

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}];

Находим наибольший общий делитель заданных полиномов - student2.ru

Находим наибольший общий делитель заданных полиномов - student2.ru

Находим наибольший общий делитель заданных полиномов - student2.ru

Находим наибольший общий делитель заданных полиномов - student2.ru

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]

Находим наибольший общий делитель заданных полиномов - student2.ru

a[6]=0;

u[x_]=u[x]/.R[[1]]

Находим наибольший общий делитель заданных полиномов - student2.ru

v[x_]=v[x]/.R[[1]]

Находим наибольший общий делитель заданных полиномов - student2.ru

Expand[f[x]*u[x]+g[x]*v[x]]

X

Та же задача может быть решена другим способом. Положим Находим наибольший общий делитель заданных полиномов - student2.ru

Находим наибольший общий делитель заданных полиномов - student2.ru Находим наибольший общий делитель заданных полиномов - student2.ru

В левом столбце- последовательность делений, которая разрешена относительно остатков. В правом столбце каждый остаток выражен в виде Находим наибольший общий делитель заданных полиномов - student2.ru Мы хотим вычислить Находим наибольший общий делитель заданных полиномов - student2.ru и Находим наибольший общий делитель заданных полиномов - student2.ru . Очевидно, что Находим наибольший общий делитель заданных полиномов - student2.ru , Находим наибольший общий делитель заданных полиномов - student2.ru . Сравнивая обе части на Находим наибольший общий делитель заданных полиномов - student2.ru м шаге, имеем

Находим наибольший общий делитель заданных полиномов - student2.ru

Отсюда получается следующая индуктивная процедура вычисления Находим наибольший общий делитель заданных полиномов - student2.ru и Находим наибольший общий делитель заданных полиномов - student2.ru :

Находим Находим наибольший общий делитель заданных полиномов - student2.ru как частное от деления Находим наибольший общий делитель заданных полиномов - student2.ru на Находим наибольший общий делитель заданных полиномов - student2.ru , затем вычисляем

Находим наибольший общий делитель заданных полиномов - student2.ru

Покажем, как описанный алгоритм нахождения линейного представления наибольшего общего делителя можно реализовать в системе Mathematica .

Вводим заданные полиномы

Находим наибольший общий делитель заданных полиномов - student2.ru

Находим наибольший общий делитель заданных полиномов - student2.ru

Задаём начальные значения параметров цикла

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]

X

v1[x]

Находим наибольший общий делитель заданных полиномов - student2.ru

a1[x]

Проверяем правильность решения задачи

Simplify[f[x]*u1[x]+g[x]*v1[x]]

Неприводимые многочлены.

Многочлен Находим наибольший общий делитель заданных полиномов - student2.ru , отличный от постоянной, называется приводимым над числовым полем Находим наибольший общий делитель заданных полиномов - student2.ru , если Находим наибольший общий делитель заданных полиномов - student2.ru разлагается на произведение двух многочленов Находим наибольший общий делитель заданных полиномов - student2.ru и Находим наибольший общий делитель заданных полиномов - student2.ru с коэффициентами из поля Находим наибольший общий делитель заданных полиномов - student2.ru , отличных от постоянных.

Если же Находим наибольший общий делитель заданных полиномов - student2.ru не может быть разложено на такое произведение, то многочлен Находим наибольший общий делитель заданных полиномов - student2.ru называется неприводимым над полем Находим наибольший общий делитель заданных полиномов - student2.ru

Произвольный многочлен с коэффициентами из поля Находим наибольший общий делитель заданных полиномов - student2.ru может быть записан в следующем виде

Находим наибольший общий делитель заданных полиномов - student2.ru , (3.3.1)

где Находим наибольший общий делитель заданных полиномов - student2.ru различные многочлены, неприводимые над полем

Находим наибольший общий делитель заданных полиномов - student2.ru , Находим наибольший общий делитель заданных полиномов - student2.ru -натуральные числа.

Может случиться, что в разложении Находим наибольший общий делитель заданных полиномов - student2.ru на неприводимые множители все Находим наибольший общий делитель заданных полиномов - student2.ru равны единице. В этом случае говорят, что Находим наибольший общий делитель заданных полиномов - student2.ru разлагается на однократные множители.

Говорят, что многочлен Находим наибольший общий делитель заданных полиномов - student2.ru входит в Находим наибольший общий делитель заданных полиномов - student2.ru с кратностью Находим наибольший общий делитель заданных полиномов - student2.ru , если Находим наибольший общий делитель заданных полиномов - student2.ru делится на Находим наибольший общий делитель заданных полиномов - student2.ru , но не делится на Находим наибольший общий делитель заданных полиномов - student2.ru .

Можно доказать, что если неприводимый многочлен Находим наибольший общий делитель заданных полиномов - student2.ru входит в Находим наибольший общий делитель заданных полиномов - student2.ru с кратностью Находим наибольший общий делитель заданных полиномов - student2.ru , то в производную Находим наибольший общий делитель заданных полиномов - student2.ru он войдёт с кратностью Находим наибольший общий делитель заданных полиномов - student2.ru .

Пусть Находим наибольший общий делитель заданных полиномов - student2.ru . Обозначим через Находим наибольший общий делитель заданных полиномов - student2.ru произведение всех однократных неприводимых множителей; через Находим наибольший общий делитель заданных полиномов - student2.ru -произведение всех двукратных неприводимых множителей , взятых по одному разу, через Находим наибольший общий делитель заданных полиномов - student2.ru -произведение всех трёхкратных неприводимых множителей, взятых по одному разу и т.д. Может случиться, что Находим наибольший общий делитель заданных полиномов - student2.ru не имеет однократных множителей. Тогда будем считать, что Находим наибольший общий делитель заданных полиномов - student2.ru . Вообще, будем считать, что Находим наибольший общий делитель заданных полиномов - student2.ru , если Находим наибольший общий делитель заданных полиномов - student2.ru не имеет Находим наибольший общий делитель заданных полиномов - student2.ru кратных множителей. Если Находим наибольший общий делитель заданных полиномов - student2.ru наивысшая кратность множителей многочлена Находим наибольший общий делитель заданных полиномов - student2.ru то имеет место соотношение

Находим наибольший общий делитель заданных полиномов - student2.ru . (3.3.2)

Процесс построения разложения (3.3.2) называется отделением кратных множителей. Он реализуется по следующему алгоритму.

Находим Находим наибольший общий делитель заданных полиномов - student2.ru наибольший общий делитель многочлена Находим наибольший общий делитель заданных полиномов - student2.ru и его производной Находим наибольший общий делитель заданных полиномов - student2.ru . Можно доказать, что

Находим наибольший общий делитель заданных полиномов - student2.ru

Наибольший общий делитель многочленов Находим наибольший общий делитель заданных полиномов - student2.ru и Находим наибольший общий делитель заданных полиномов - student2.ru будет равен

Находим наибольший общий делитель заданных полиномов - student2.ru .

Наибольший общий делитель многочленов Находим наибольший общий делитель заданных полиномов - student2.ru и Находим наибольший общий делитель заданных полиномов - student2.ru будет равен

Находим наибольший общий делитель заданных полиномов - student2.ru .

Наконец получим

Находим наибольший общий делитель заданных полиномов - student2.ru

Далее составляем

Находим наибольший общий делитель заданных полиномов - student2.ru

Находим наибольший общий делитель заданных полиномов - student2.ru

Отсюда находим

Находим наибольший общий делитель заданных полиномов - student2.ru .

Описанный алгоритм реализуется в системе Mathematica следующим образом.

Пример 3.3.1. Выделить кратные неприводимые множители для многочлена Находим наибольший общий делитель заданных полиномов - student2.ru

Решение.

Вводим заданный многочлен

f[x_]=x^8+2*x^7+5*x^6+6*x^5+

8*x^4+6*x^3+5*x^2+2*x+1;

Полагаем g[x] равным заданному многочлену

g[x_]=f[x];

Находим наибольший общий делитель заданных полиномов - student2.ru

g[x_]=PolynomialGCD[g[x],D[g[x],x]];

d=Append[d,g[x]];

While[Length[CoefficientList[g[x],x]]>1,g[x_]=

PolynomialGCD[g[x],D[g[x],x]];

d=Append[d,g[x]]];

Наши рекомендации