Оценка интервалов изоляции корней полиномов — 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}]
1
CountRoots[(х^2+2) х^4, {х, -I, 2 I}]
5
CountRoots[х^21- 1, {х, 0, 5 + 10*1}]
5
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.
- степени ускорения свидетельствует следующий пример:
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}.
<<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}
