Оценка интервалов изоляции корней полиномов — Rootlsolation

Следующие функции подпакета Rootlsotation позволяют оценивать интервалы изоляции для действительных и комплексных корней полиномов:

CountRoots [poly, {x,ml,m2} ] — возвращает число корней полинома poly от переменной х в комплексном интервале {ml, m2 };
RealRootsIntervals [poly] — возвращает разделенный интервал изоляции для вещественных корней полинома poly;
RealRootsIntervals [polyl,poly2,...] — возвращает разделенные интервалы изоляции для вещественных корней нескольких полиномов;
ComplexRootsIntervals [poly] — возвращает разделенный интервал изоляции для комплексных корней полинома;
ComplexlRootsIntervals [polyl, poly2,...] — возвращает разделенные интервалы изоляции для комплексных корней нескольких полиномов;
Contractlnterval [a,n] — возвращает интервал изоляции для числа а с точностью, задаваемой числом знаков результата п.

Применение этих функций поясняют следующие примеры:

<<Algebra`Rootlsolation`

f = (x^2- 1) (х^2- 3) (х^2- 5); CountRoots [f, {x, 1, 2}]

CountRoots[(х^2+2) х^4, {х, -I, 2 I}]

CountRoots[х^21- 1, {х, 0, 5 + 10*1}]

RealRootlntervals[f]

{{-4, -2}, {-2,.-1}, {-1, -1}, {1, 1}, {1, 2}, {2, 4}}

ComplexRootlntervals[f+5]

{{-1, 0}, {0, 1}, {-7-71, -7/4}, {-7, -7/4 + 7I},

{-7/4, -7I + 7/2}, {-7/4, -7/2 + 7I}}

ComplexRootlntervals[x^3, x^5+l]

{{{-2, 0}, {0, 0),

{-3-31, 0}, {-3, 31}, {-31, 3), {0, 3+31}}, {2, 1, 2, 2, 2, 2}}

Contractlnterval[Root[x^7- 1, 5], 5]

{ 58333/262144 + 511143I/ 524288+ 116665/524288+ 63893I/65536}

N[%]

{-0.222523+ 0.9749281, -0.222521 + 0.974931}

Операции с полиномами

Если конечные поля — понятие достаточно экзотическое, то полиномы встреча- ются сплошь и рядом во многих математических и научно-технических расчетах. В пакете расширения Algebra определен ряд новых операций над полиномами. Начнем их рассмотрение с функции PolynomialExtendedGCD:

PolynomialExtendedGCD [polyl, poly2 ] — возвращает наибольший общий делитель двух полиномов;
PolynomialExtendedGCD[polyl,poly2,Modulus->p] —возвращает наи- больший общий делитель двух полиномов по модулю р.

Примеры применения этой функции приведены ниже:

<<Algebra"PolynomialExtendedGCD

PolynomialExtendedGCDlxл2 + 3 х + 2, Expand[(x + 1)(х + 2)], Modulus->7]

{2+ Зх+х2, (0, 1}}

PolynomialExtendedGCD[

Expand[ ((12+1) z^2 + 5 z + I) (I z + 3)], Expand[ ((9+1) z + (3+1)) ((31) z +9)]]

{-31+z,

{- 2261/3341+ 710I/3341( 35/3341- 3951/10023)+ (5959/20046- 20531/20046)z}}

Далее следует функция PolynomialPowerMod [polyl, n, (poly2, р} ], которая является существенно ускоренной версией функции PolynomialMod.

степени ускорения свидетельствует следующий пример:

<<Algebra`PolynomialPowerMod`

Timing[PolynomialPowerMod[1 + х, 200, х^З + x^2 + 1, Prime[4750]]][[1]], Timing [ PolynomialMod [ (1 + x)^200, x^ + х^2 + 1, Prime [4750] ]][[1]]

{0. Second, 2.37 Second)

В данном случае вычисления по функции PolynomialPowerMod оказались вы- полненными менее чем за 0.01 с, что дает нулевой результат.

Еще одна функция в трех ее модификациях работает с симметричными полиномами:

SymmetricReduction [ {xl,...,xn}, k] — возвращает симметричный полином степени k по переменным {х1,..., хn);
SymmetricReduction [f, {xl,...,xn}] — возвращает часть полинома {p,q} по переменным {х1,...,хп}, где f=p+q, причем р есть симметричная часть, q — остаток;
SymmetricReduction [f, {xl,...,xn}, {s1,..., sn} ] — возвращает часть полинома (p,q) попеременным {xl, ...,xn}, где элементарный симметричный полином представляет список {s1,..., sn}.

Следующий пример поясняет создание симметричного полинома 4-й степени по переменным {х,у, z,w,t}:

<<Algebra` SymmetricPolynomials`

SyiranetricPolynomial[{x, y, z, w, t}, 4]

twxy+ twxz+ twyz+txyz+wxyz

Действие других функций поясняют следующие примеры:

SynraetricReduction[(х + у)^2 + (х + z)^2 + (z + у)^2, {х, у, z}]

{2 (х+у+ z)2- 2 (xy+xz+yz), 0}

SymmetricReduction[х^5 + у^5 + z^4, {х, у, z}, {s1, s2, s3}]

{s15- 5s13s2 + 5s1s22+ 5sl2s3- 5s2s3, z4-z5}

Содержание раздела