2. Пакет алгебраических функций Algebra

Пакет алгебраических функций Algebra

Решение неравенств

Пакет расширения Algebra содержит ряд новых функций для работы с неравенствами, ограниченными полями и полиномами. Для доступа сразу ко всем функциям пакета используется команда «Algebra`.

Загрузка отдельных функций показана в примерах использования этого пакета, описанных ниже.

До сих пор мы сталкивались с решениями уравнений, представленных равенствами. Пакет Algebra дает важное дополнение в виде функций, обеспечивающих работу с неравенствами. Прежде всего это функция SemialgebraicCompo-nents [ineqs, vars], которая определят комплект решений неравенств ineqs по переменной vars.

Приведенные ниже примеры иллюстрируют работу данной функции:

<<Algebra`Algebraiclnequalities`

SemialgebraicComponents[{х (х^2 - 1) (х^3 - 2) > 1}, х]

{-3, 3}

SemialgebraicComponents[{х + у ^{^} 2 < 5, х/у > 1}, {х, у}]

SanialgebraicCarpanents[(x+у ² < 5, — x/y>1}, {х, у}]

SemialgebraicComponents[{х ^{^} 2 + у ^{^} 2 < 5, х у > 0}, {х, у}]

{{-3/16,-3/16},{3/16,3/16}}

SemialgebraicComponents[{x ^{^} 2 + y ^{^} 2/4 + z ^{^} 2/9 > 1, х ^{^} 2 + (у - 1) ^{^} 2 + (2- 2) ^{^} 2 < 0}, {х, у, z}]

{}

Для решения неравенства служит функция InequalitySolve [expr, var], которая решает неравенство ехрг относительно переменной var.

Следующие примеры иллюстрируют применение данной функции:

<<Algebra` InequalitySolve`

InequalitySolve [х (х^2- 5) (х^2- 6) > 0, х]

-sqrt(6) <х<-sqrt(5) | | 0<х<sqrt(6)| | х>7sqrt(6)

InequalitySolve[x^2/Abs[х- 2] >= 0 && 1/х < х + 1, х]

-1/2(1-sqrt(5)<x<0| | 1/2(-1+sqrt(5)<x<2| | x>2

Функции для представления комплексных данных — Relm

Подпакет Relm обеспечивает переназначение функций комплексной переменно!! для более корректной их работы:

<<Algebra`ReIm`

Re[l/x+l/y]

Re[x]/(Im[x]2+Re[x]2 )+ Re[y]/( Iim[y]2+Re[y]2)

Re[(z + I)^3 + Exp[I z]]

E[mz] Cos[Re[z]] -2 (1+ Im[z])2Re[z] +

Re[z] (-(1+ Im[z])2+Re[z]2)

Im[x] ^= 0; RealValued[f, g]

{f, g)

Im[l/(l- I f[x] g[x])]

f [x] g[x]/(1+ f[x]2g[x]2 )

Im[Sin[a]]

Cos[Re[a]] Sinh[Tm[a]]

 

Операции в конечных полях — FiniteFields

Поле является алгебраическим понятием, которое может быть определено как множество, имеющее не менее двух элементов, над которыми заданы две бинарные ассоциативные и коммутативные операции — сложения и умножения. Кроме того, для существования поля нужны два особых элемента — нуль 0, задающий правило сложения а + 0 = а, и единица 1 для задания правила умножения а*1 = 1. Определено также понятие противоположного элемента -а, такого что а + (-а) = 0, и обратного элемента а-- ¹ , такого что a- ¹ а = 1. Поле характеризуется размером р и целым положительным целым d, называемым степенью расширения.

Пакет задает набор функций GF[p] [{k}], GF[p,l] [{k}], GF[p, {0,1}] [{k}], GF[p,d] HGF[p,ilist] [elist], действие которых иллюстрируют следующие примеры:

<<Algebra` FiniteFields`

GF[7][4] + GF[7][6]

{3}7

GF[3,4][1,2,1] GF[3,4][2,2,2,0]

{1, 1, 2, 0}3 GF[5,1][1] + GF[3,4][1,1,1]

{1, 1, 1, 0}3+ (1)5

Вряд ли подробное их описание заинтересует большинство читателей. Специалистов по полям не затруднит более детальное знакомство с этими функциями в разделе Add-ons справочной базы данных. Там же можно найти описание ряда других функций, относящихся к теории конечных полей.

Оценка интервалов изоляции корней полиномов — 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.

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

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

Преобразование полиномов в схему Горнера — Horner

Подпакет Horner в системе Mathematica 4 реализует хорошо известную схему вычисления полиномов — схему Горнера. При ней операции возведения в степень заменяются операциями умножения. Для этого служит функция Horner:

• Horner [poly] — устанавливает полином poly в форму Горнера;
• Horner [poly, vars] — устанавливает полином ряда переменных vars в форму Горнера.

Примеры преобразования полиномов в схему Горнера:

<<NumericalMath`Horner`

Horner[ 11 х^3 -4 х^2 + 7 х + 2 ]

2+ х (7 + х (-4 + 11х))

Horner[ а х^3 + bх^2 + с х + d, х ]

d+ х (с + х (b + ах))

Horner[ х^(1/3) + х + х^(3/2) ]

Схема Горнера может использоваться и для отношения полиномов:

Horner [polyl/poly2] и Horner [polyl/poly2, varsl,vars2] .

Эти функции можно использовать для улучшенного представления аппроксимации Паде, что демонстрирует следующий пример:

<<Calculus ` Fade`

approx = Padef Exp[Log[x] -х] , {х, 0, 3, 2}]]

Horner[ approx ]

Переход к схеме Горнера дает ряд преимуществ перед обычным вычислением полиномов: уменьшается время вычислений, повышается их точность, уменьшается вероятность расхождения численных методов, в которых используются полиномы. В системе Mathematica 3 подпакет Corner находился в пакете расширения NumberMath, что было не вполне логично.