Вернуться к списку примеров

Ряд Штурма для многочлена c рациональными коэффициентами

по материалам курсовой работы К.В.Постоленко

Предлагаем Вам программу для системы GAP, которая возвращает ряд Штурма для заданного многочлена c рациональными коэффициентами, при этом выводя на печать необходимые промежуточные вычисления. Кроме того, программа также содержит функции, которые используют ряд Штурма для определения числа положительных и отрицательных корней многочлена, числа его корней в заданном интервале, и вычисления приближенного значения корней многочлена.

Текст программы находится здесь. Для начала работы с ней загрузите предлагаемый файл и прочитайте его с помощью команды

Read("sturm.g");
Сначала зададим некоторый многочлен от одной переменной:

gap> x:=Indeterminate(Rationals,"x");
x
gap> f:=x^3-6*x+1;
x^3-6*x+1

Первой функцией, которую мы продемонстрируем, будет SturmSystem. Данная функция находит ряд функций Штурма для заданного многочлена. Заметим, что после вычисления система Штурма сохраняется в качестве атрибута многочлена, что исключает затраты времени на ее повторное вычисление. Чтобы убедиться в этом, воспользуемся функцией KnownAttributesOfObject(f), которая позволяет узнать, какими атрибутами обладает объект (в нашем случае многочлен f), до и после вычисления его системы Штурма:

gap> KnownAttributesOfObject(f);
[ "CoefficientsOfLaurentPolynomial", "IndeterminateNumberOfUnivariateRationalFunction" ]
gap> s:=SturmSystem(f);
f(x) = x^3-6*x+1
f'(x) = 3*x^2-6
x^3-6*x+1 = 3*x^2-6 * 1/3*x - 4*x-1
3*x^2-6 = 4*x-1 * 3/4*x+3/16 -93/16
4*x-1 = 93/16 * 64/93*x-16/93 -0
[ x^3-6*x+1, 3*x^2-6, 4*x-1, 93/16 ]

gap> time;
440
gap> s:=SturmSystem(f);
[ x^3-6*x+1, 3*x^2-6, 4*x-1, 93/16 ]
gap> time;
0

gap> KnownAttributesOfObject(f);
[ "CoefficientsOfLaurentPolynomial", "IndeterminateNumberOfUnivariateRationalFunction", 
  "IndeterminateOfUnivariateRationalFunction", "DegreeOfLaurentPolynomial",
  "Derivative", "SturmSystem" ]

Как видно из примера, время повторного вычисления равняется нулю, а список известных атрибутов пополняется, среди прочих, атрибутом SturmSystem.

Далее рассмотрим функцию ChangeSigns(s,a), которая определяет число перемен знаков в ряде Штурма s в заданной точке a:

gap> ChangeSigns(s,0);
2
gap> ChangeSigns(s,-3);
3
gap> ChangeSigns(s,2);
1

Функция NrRoots(f,a,b) находит число действительных корней многочлена f, которые больше чем a и не превышают b:

gap> NrRoots(f,-3,2);
2

Для подсчета количества перемен знаков в ряде Штурма s на плюс и минус бесконечности применяются функции ChangeSignsMinusInfinity(s) и ChangeSignsPlusInfinity(s):

gap> ChangeSignsPlusInfinity(s);
0
gap> ChangeSignsMinusInfinity(s);
3

С помощью этих двух функций легко можно определить количество корней многочлена f в функции NrOfRealRoots(f):

gap> NrOfRealRoots(f);
3

Функции NrOfPositiveRealRoots(f) и NrOfNonPositiveRealRoots(f) определяют соответственно количество положительных и отрицательных корней многочлена f:

gap> NrOfNonPositiveRealRoots(f);
1
gap> NrOfPositiveRealRoots(f);
2

Для нахождения корней многочлена f, сначала требуется найти интервал, на котором содержатся все корни многочлена или, что то же самое, найти верхнее ограничение модуля корней. Для этого была разработана функция UpperRootsLimit(f):

gap> UpperRootsLimit(f);
7

Функция IntervalsOfRoots(f,eps) выводит интервал на котором содержится корень многочлена f, с заданной точностью eps:

gap> IntervalsOfRoots(f,10);
[ [ -7, 0 ], [ 0, 7 ] ]

gap> IntervalsOfRoots(f,6);
[ [ -7/2, 0 ], [ 0, 7/2 ] ]

gap> IntervalsOfRoots(f,1);
[ [ -21/8, -7/4 ], [ 0, 7/8 ], [ 7/4, 21/8 ] ]

gap> IntervalsOfRoots(f,10^-3);
[ [ -1295/512, -20713/8192 ], [ 1365/8192, 343/2048 ],
[ 19341/8192, 4837/2048 ] ]

gap> List(last, r -> (r[1]+r[2])/2 );
[ -41433/16384, 2737/16384, 38689/16384 ]

gap> IntervalsOfRoots(f,10^-50);
[ [ -946180540226875416749522184033111355909143980149321/
374144419156711147060143317175368453031918731001856,
-1892361080453750833499044368066222711818287960298635/
748288838313422294120286634350736906063837462003712 ],
[ 15662545086391001699568813492298469860337205786443/
93536104789177786765035829293842113257979682750464,
125300360691128013596550507938387758882697646291551/
748288838313422294120286634350736906063837462003712 ],
[ 441765179940655704975623465031958738233897578501771/
187072209578355573530071658587684226515959365500928,
1767060719762622819902493860127834952935590314007091/
748288838313422294120286634350736906063837462003712 ] ]

В качестве приближенных значений корней можно взять середину полученных интервалов:

gap> List(last, r -> (r[1]+r[2])/2 );
[ -3784722160907501666998088736132445423636575920597277/
1496577676626844588240573268701473812127674924007424,
250600721382256027193101015876775517765395292583095/
1496577676626844588240573268701473812127674924007424,
3534121439525245639804987720255669905871180628014175/
1496577676626844588240573268701473812127674924007424 ]

Как видно из примера, с помощью функции для вычисления системы Штурма и вспомогательных функций можно вычислить рациональные приближения корней многочлена с заданной точностью. Заметим, что рациональные корни многочлена можно найти с помощью функции RootsOfUPol (см. пример по теме "Многочлены с рациональными коэффициентами").


Вернуться к списку примеров