Записи с меткой «степень»

Пакеты функций комбинаторики

Пакеты функций комбинаторики
Пакет combinat
Функции комбинаторики достаточно известны из обычного курса математики. При вызове пакета выводится (если вывод не заблокирован двоеточием) список его функций:
> with(combinat);
Warning, the protected name Chi has been redefined and unprotected
[Chi,bell, binomialcartprod, character, choose, composition, conjpart, decodepart, encodepart,fibonacci,firstpart, graycode, inttovec, lastpart, multinomial, nextpart, numbcomb, numbcomp, numbpart, numbperm, partition, permute, powerset, prevpart, randcomb, randpart, randperm, Stirling], stirling2, subsets, vectoint]
Ввиду важности функций комбинаторики приведем их полные определения:

  •  Chi(x) — гиперболический косинусный интеграл;
  •  bell(n) —возвращает число ехр(ехр(х)-1) =sum(ben(n)/n!*x^n, n=0..infinity), причем для вычислении используется рекуррентное соотношение bell(n+1) = (bell(n)+1)^n;
  •  binomial (n, r) — возвращает биноминальные коэффициенты, причем, если n и r — целые числа, удовлетворяющие условию 0 <= r<= n, то функция возвращает C(n.r)=n!/(r!(n-r)!), а в общем случае С(n, r) = limit(GAMMA(N+D/ GAMMA(R+l)/GAMMA(N-R-t-l),R=r,N=n);
  •  composition(n, k) — возвращает списки композиций для целых неотрицательных n и k;
  •  fibonacci(n) — возвращает числа Фибоначчи, вычисляемые по рекуррентной формуле F(n) =F(n — 1) +F(n — 2), где F(0) =0 и F(1) =1;
  •  fibonacci(n, х) — возвращает значение полинома Фибоначчи F(n, x) =-х F(n — 1,x) + F(n — 2, х), где F(0,x) = 0 и F(l,x) = 1, при этом F(n) = F(n, 1);
  •  firstpart(n) — возвращает первую часть каноническей последовательности ряда;
  •  nextpart(l) — возвращает следующую часть канонической последовательности ряда;
  •  lastpart(n) — возвращает последнюю часть канонической последовательности ряда;
  •  prevpart(1) — возвращает предыдущую часть канонической последовательности ряда;
  •  conjpart(l) — возвращает объединенный раздел в канонической последовательности ряда;
  •  graycode(n) — возвращает список кодов Грея для габитовых чисел;
  •  multinomial (n, kl, k2, …. km) — возвращает мультиномиальные коэффициенты;
  •  numbcomb(n) и numbcomb(n. m) — возвращает число комбинаций;
  •  numbcomp(n, k) — возвращает число композиций;
  •  numbpart(n) — возвращает список всех возможных сумм, дающих п;
  •  permute(n) и permute(n, r) — возвращает numbperm(n, r) = nops(permute(n. r));
  •  powerset(s) — возвращает степень множества в множестве s;
  •  randcomb(n, m) — возвращает случайную комбинацию;
  •  randpart(n) — возвращает случайную часть;
  •  randperm(n) — возвращает случайную композицию; 
  •  stirling(n, m) — возвращает число Стирлинга первого рода;
  •  stirling2(n, m) — возвращает число Стирлинга второго рода;
  •  subsets(L) — задает итерационную процедуру над степенями множества или списка L;
  •  vectoint(l) — возвращает индекс вектора канонического упорядочения 1;
  •  inttovec(m, n) — возвращает вектор канонического упорядочения для неотрицательных целых чисел тип.

Ниже даны примеры применения некоторых из этих функций:
> choose(4,3); 
[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
> choose([a,a,b,c].3):
[[a,a,b],[a,a,c],[atb,c]] 
> composition(3,2):
{[2,1],[1,2]} 
> decodepart(4,2);
[1,1,2] 
> fibonacci(l0);
55 
> seq(fibonacci(1),i-l..l2):
1,1,2,3,5,8,13,21,34,55,89,144
 > partition(5);
[[1,1,1,1,1], [1,1,1,2], [1,2,2], [1,1,3], [2,3], [1,4], [5]] 
> firstpart(3):
[1,1,1] 
> nextpart(%);
[1,2] 
> prevpart(%);
[1,1,1] 
> 1astpart(3):
[3] 
> conjpart(%): 
[1,1,1] 
> multinomial(8,2,3,3);
560 
> numbcomp(8,5):
35  
> nuropart(3);
numpart(3) 
> numbperm(4); 
24  
> numbperm([a,b]):

 > numbperm({a,b,c},2);

> permute(3,2);
[[l,-2],[l,3],[2,l],[2,3],[3,l],[3,2]] 
> permute([a,a,b],2):
[[a,a],[a,b],(b,a]] 
> powerset([a,a,b]):
[[],[а],[b],[а,Ь],[а,а],[а,а,b-]]
> randcomb([a,b,c,d],3):
[a,c,d] 
> randcomb([a,b,c,d],3);
[a,b,d]
 > randpart(l0);
[2,8]
> randpart(l0):
[10] 
> stirling(10,5);
-269325 
> stirling2(10,5):
42525
> S:=subsets({l,2}):
 > while not S[finished] do S[nextva1ue]() od:
{ }
{1}
{2}
{1,2} 
> vectoint([l,0,0]);
1
 > inttovec(6,3);
[1,0,1]

Читателю, желающему использовать данный пакет, рекомендуется внимательно ознакомиться с этими простыми примерами и просмотреть примеры из справочной базы данных для имеющихся в пакете функций.

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

Операции в конечных полях — FiniteFields
Поле является алгебраическим понятием, которое может быть определено как множество, имеющее не менее двух элементов, над которыми заданы две бинарные ассоциативные и коммутативные операции — сложения и умножения. Кроме того, для существования поля нужны два особых элемента — нуль 0, задающий правило сложения а + 0 = а, и единица 1 для задания правила умножения а*1 = 1. Определено также понятие противоположного элемента -а, такого что а + (-а) = 0, и обратного элемента а— 1 , такого что a- 1 а = 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}

Комплектование по степеням

Комплектование по степеням
Еще одна функция общего назначения — collect — служит для комплектования выражения ехрr по степеням указанного фрагмента х (в том числе множества либо списка). Она задается в одной из следующих форм:
collect(a. x) 
  collect(a. x. form, func)
Во второй форме этой функции дополнительно задаются параметры form (форма) и func (функция или процедура). Параметр form может иметь два значения— recursive (рекурсивная форма) и distributed (дистрибутивная форма). Параметр func позволяет задать имя функции, по которой будет идти комплектование ехрr. далее…

Упрощение выражений

Упрощение выражений
Функция simplify — одна из самых мощных в системах символьной математики. Она предназначена для упрощения математических выражений. «Все гениальное просто», — любим мы повторять, хотя это далеко не всегда так. Тем не менее стремление представить многие математические выражения в наиболее простом виде поощряется в большинстве вычислений и нередко составляет их цель. В системе Maple 15 функция упрощения используется в следующем виде:

  •  simplify(expr) — возвращает упрощенное выражение ехрr или повторяет его, если упрощение в рамках правил Maple 15 невозможно;
  •  simplify(expr, nl, n2, …) —возвращает упрощенное выражение ехрr с учетом параметров с именами nl, n2, … (в том числе заданных списком или множеством);
  •  simplify(ехрг,assume=prop) — возвращает упрощенное выражение ехpr с учетом всех условий.

Функция simplify — многоцелевая. Она обеспечивает упрощение математических выражений, выполняя следующие типовые действия (для простоты обозначим их как ->):

  •  комбинируя цифровые подвыражения (3*х*5->15*х, 10*х/5->2*х);
  •   приводя подобные множители в произведениях (х^3*а*х->а*х^4); 
  •  приводя подобные члены в суммах (5*х+2+3*х->8*х+2); 
  •  используя тождества, содержащие ноль (а+0->а, х-0->х);
  •  используя тождества, содержащие единицу (1*х->х);
  •  распределяя целочисленные показатели степени в произведениях ((3*x*y^3)^2 ->9*х^2*у^6);
  •  сокращая ехрr на наибольший общий полиномиальный или иной множитель;
  •  понижая степень полиномов там, где это возможно;
  •  используя преобразования, способные упростить выражения.

Несмотря на свою гибкость, функция simplify не всегда способна выполнить возможные упрощения. В этом случае ей надо подсказать, в какой области ищутся упрощения и где можно найти соответствующие упрощающие преобразования. далее…

Преобразование выражений

Преобразование выражений
Еще одним мощным средством преобразования выражений является функция combine. Она обеспечивает объединение показателей степенных функций и преобразование тригонометрических и некоторых иных функций. Эта функция -может записываться в трех формах:
combine(f)
combinef(, n)
combine(f. n. optl. opt2. …)
Здесь f — любое выражение, множество или список выражений; n — имя, список или множество имен; optl, opt2, … — имена параметров. Во втором аргументе можно использовать следующие функции:

@@

abs

arctan

conjugate

exp

In

piecewise

polylog

power

product

Ps

radical

range

signum

trig

Примеры применения функции combine представлены ниже:

Эти примеры далеко не исчерпывают возможностей функции combine в преобразовании выражений. далее…

Сплайн-интерполяция и аппроксимация

Сплайн-интерполяция и аппроксимация
Точность полиномиальной аппроксимации катастрофически падает при увеличении степени аппроксимирующих полиномов. От этого недостатка можно избавиться, используя для аппроксимации отрезки полиномов невысокой степени, применяемые для представления части узловых точек. Самым известным методом такой аппроксимации является сплайн-аппроксимация на основе применения отрезков кубических полиномов. При этом аппарат сплайн- аппроксимации позволяет получить полиномы, которые дают в узловых точках непрерывность не только представляемой ими функции, но и ее первых и даже вторых производных.
Наглядно сплайн-функцию можно представить в виде гибкой стальной линейки, закрепленной в узловых точках и плавно изгибающейся. Благодаря указанным свойствам сплайнов они неплохо описывают функции, представленные как небольшим числом узловых точек (благодаря плавности сплайн- кривых), так и функции, представляемые очень большим числом узловых точек (поскольку порядок полиномов от этого числа уже не зависит). далее…