Warning: include(/var/www/iill7773/data/www/wiselab.ru/wp-content/plugins/wp-super-cache/wp-cache-base.php): failed to open stream: No such file or directory in /home/u7426dd0/domains/wiselab.ru/public_html/wp-content/plugins/wp-super-cache/wp-cache.php on line 65

Warning: include(): Failed opening '/var/www/iill7773/data/www/wiselab.ru/wp-content/plugins/wp-super-cache/wp-cache-base.php' for inclusion (include_path='.:/opt/alt/php55/usr/share/pear:/opt/alt/php55/usr/share/php') in /home/u7426dd0/domains/wiselab.ru/public_html/wp-content/plugins/wp-super-cache/wp-cache.php on line 65

Warning: include_once(/var/www/iill7773/data/www/wiselab.ru/wp-content/plugins/wp-super-cache/ossdl-cdn.php): failed to open stream: No such file or directory in /home/u7426dd0/domains/wiselab.ru/public_html/wp-content/plugins/wp-super-cache/wp-cache.php on line 82

Warning: include_once(): Failed opening '/var/www/iill7773/data/www/wiselab.ru/wp-content/plugins/wp-super-cache/ossdl-cdn.php' for inclusion (include_path='.:/opt/alt/php55/usr/share/pear:/opt/alt/php55/usr/share/php') in /home/u7426dd0/domains/wiselab.ru/public_html/wp-content/plugins/wp-super-cache/wp-cache.php on line 82
решении | Учебники

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

Улучшенное разложение на простые множители — FactorlntegerECM

Улучшенное разложение на простые множители — FactorlntegerECM
Алгоритм разложения чисел на простые множители, реализованный в ядре Mathematiica 3, способен за 3 часа (на рабочих станциях) разлагать числа, имеющие до 18 цифр. Улучшенный алгоритм в подпакете FactorlntegerECM позволяет увеличить максимальное число цифр до 40. Реализуется разложение следующей функцией:

  • FactorIntegerECM[n] — возвращает один из делителей числа п. Возможны опции FactorSize->q, CurveNumber->b и CurveCountLimit->c.

Примеры применения этой функции:
<<NumberTheory`FactorlntegerECM`
FactorIntegerECM[123456789]
34227
3*5*7*9
945
FactorlntegerECM[945]
189
Функции теории чисел — NumberTheory Functions
В подпакете NumberTheoryFunctions имеется ряд функций, относящихся к теории чисел:

  • SquareFreeQ[n] — дает True, если п не имеет квадратичного фактора, и False в ином случае;
  • NextPrime [n] — дает наименьшее простое число, превосходящее п;
  • ChineseRemainderTheorem[listl, Iist2.] — дает наименьшее неотрицательное целое г, такое что Mod [r, Iist2] ==list1;
  • SqrtMod [d, n] — дает квадратный корень из (d mod п) для нечетного n;
  • PrimitiveRoot [n] — дает примитивный корень п;
  • QuadraticRepresentation [d, n] — дает решение {х,у} для уравнения х 2 + (d у) 2 ==п для нечетного п и положительного d;
  • ClassList[d] — дает список неэквивалентных квадратичных форм дискриминанта d для отрицательного и свободного от квадратов целого d вида 4n+1;
  • ClassNumber [d] — дает список неэквивалентных квадратичных форм дискриминанта d;
  • SumOf Squares [d, n] — дает число представлений целого числа п в виде суммы d квадратов;
  • SumOf SquaresRepresentations [d, n] — дает список представлений целого числа п в виде суммы d квадратов, игнорируя порядок и знаки.

Примеры применения данных функций приведены ниже:
<<NumberTheory`NumberTheoryFunctions`
SquareFreeQ[2*3*5*7]
True SquareFreeQ[50]
False
NextPrime[1000000]
1000003
ChineseRemainderTheorem[{0, 1, 2}, {4, 9,
244
ChineseRemainderTheorem[Range[16], Prime[Range[16]]]
20037783573808880093
SqrtMod[3, 11]
5
SqrtMod[2, 10^64 +57]
876504467496681643735926111996
54610040103361197677707490912
2865
PrimitiveRoot[7]
3
QuadraticRepresentation[l, 13]
{3,. 2}
ClassList[-19]
{{1, 1, 5}}
ClassNumber[-10099]
25
SumOfSquaresRepresentations[3, 100]

{{0, 0, 10}, (0, 6, 8}}

Решение линейных уравнений с трехдиагональной матрицей — Tridiagonal

Решение линейных уравнений с трехдиагональной матрицей —Tridiagonal
При решении линейных уравнений часто встречаются матрицы особой формы — трехдиагональные. Подпакет Tridiagonal имеет функцию для решения линейных уравнений с такой матрицей:

  • TridiagonalSolve [a,b, с, г] — решение системы линейных уравнений с трехдиагональной матрицей m. х==г (диагонали представлены векторами а, b и с, вектор свободных членов — г).

Пример применения данной функции:
<<LinearAlgebra` Tridiagonal`
{а, b, с} = {{1, 2, 3}, {4, 5, б, 7}, {10, 9, 8}}
{{1, 2, 3}, {4, 5, 6, 7}, {10, 9, 8}}
m = Table[Switch[ j-i, -1, a[[j]], 0, b[[jj], 1, c[[j-l]], _, 0], {i, 4}, {j, 4}]//MatrixForm
TridiagonalSolve[a, b, c, {8, 3, 4, 5}
С учетом представленных функций и функций ядра набор матричных средств системы Mathematica является одним из наиболее полных. В области решения задач в численном виде он несколько уступает лишь специализированной матричной системе MATLAB 5.0/5.3.
Расширение в теории чисел
 
Мы уже описывали уникальные возможности систем Mathematica 3/4 в области обработки чисел и численных вычислений. Эти возможности существенно расширяет пакет NumberTheory, содержащий функции, реализующие алгоритмы теории чисел. Данный раздел посвящен знакомству с этим пакетом. далее…

Линейная алгебра — пакет LinearAlgebra

Линейная алгебра— пакет LinearAlgebra
 
Пакет расширения LinearAlgebra добавляет ряд новых функций, полезных при решении сложных задач линейной алгебры.
Декомпозиция Холесского — Cholesky
Подпакет Cholesky содержит единственную функцию HoleskyDecomposition [m], которая вычисляет декомпозицию (факторизацию, разложение) Холесского для симметричной положительно определенной матрицы т.
Примеры выполнения декомпозиции Холесского даны ниже:
<<LinearAlgebra`Cholesky`
hil = Tablet l/(i + j — 1) , {i, 1, 4}, {j, 1, 4}]
Eigenvalues[ N[hil] ]
{1.50021, 0.169141, 0.00673827, 0.0000967023}
u = CholeskyDecomposition[hil]
MatrixForm[Transpose[u] . u]
 
Метод исключения Гаусса — GaussianElimination
Следующие функции обеспечивают реализацию метода исключения Гаусса при решении линейного уравнения вида А-x =b:

  • LUFactor [m] — возвращает LU-декомпозицию матрицы m;
  • LUSolve [lu, b] — решает систему линейных уравнений с матрицей коэффициентов lu и вектором свободных членов b методом исключения переменных Гаусса;
  • LU [a, pivots] — создает объект, используемый в LUSolve. Применение этих функций поясняют примеры, показанные ниже:

<<LinearAlgebra`GaussianElimination`
MatrixForm[a = {{1, 2, 3}, {4, 5, 6}, {-1, 5, -5}}]
lu = LUFactor[a]
b = {10, -3, 12}
{10, -3, 12}
LUSolve[lu, b]
Метод исключения Гаусса является хорошо апробированным методом решения систем линейных уравнений, что делает реализацию описанных функций полезным дополнением к встроенным функциям линейной алгебры.
Операции с матрицами — MatrixManipulation
Подпакет MatrixManipulation добавляет к матричным функциям ядра системы Ма-thematica ряд новых функций. Начнем с функций объединения матриц:

  • AppendColumns [ml,m2,…] — объединяет по столбцам матрицы ml,m2,…;
  • AppendRows [ml,m2,…] — объединяет по строкам матрицы ml,m2,…;
  • BlockMatrix [blocks] — объединяет по строкам и столбцам блоки blocks, создавая новую матрицу.

Данные операции с матрицами иллюстрируют следующие примеры:
<< LinearAlgebra`MatrixManipulation`
a = {{a11, a12}, {a21, a22}}; MatrixFormfa]
b = {{b11, b12}, {b21, b22}}; MatrixForm[b]
MatrixForm[AppendColumns[a, b] ]
AppendRows[a, b] //MatrixForm
BlockMatrix[{{a, b}, {b, {{0, 0}, {0, 0}}}}] //MatrixForm
Следующая группа функций вставляет или удаляет столбцы или строки матриц:

  • TakeRows [mat, n] — вставляет в матрицу mat n-ю строку;
  • TakeRows [mat, -n] — удаляет из матрицы mat п-ю строку;
  • TakeRows [mat, {m,n} ] — вставляет в матрицу mat строки от m до n;
  • TakeColumns [mat, n] — вставляет в матрицу mat п-й столбец;
  • TakeColumns [mat, -n] — удаляет из матрицы mat п-й столбец;
  • TakeColumns [mat, {m, n} ] — вставляет в матрицу mat столбцы от m до п.

Действие функции иллюстрируется следующими примерами:
mat = Array[m, 3, 4]; MatrixForm[mat]
m[l, 1] m[l, 2] m[l, 3] m[l, 4]
m[2, 1] m[2, 2] m[2, 3] m[2, 4]
m[3, 1] m[3, 2] m[3, 3] m[3, 4]
TakeRows[mat, -2] //MatrixForm
m[2, 1] m[2, 2] m[2, 3] m[2, 4]
m[3, 1] m[3, 2] m[3, 3] m[3, 4]
TakeColumns[mat, {2,3}] //MatrixForm
m[l, 2] m[l, 3] )
m[2, 2] m[2, 3]
m[3, 2] m[3, 3]
TakeMatrix[mat, {2, 3}, {3, 4}] //MatrixForm
m[2, 3] m[2, 4]
m[3, 3] m[3, 4]
SubMatrix[mat, {2, 3}, {2, 2}] //MatrixForm
m[2, 3] m[2, 4]
m[3, 3] m[3, 4]
Следующая группа функций служит для задания матриц специального вида:

  • UpperDiagonalMatrix [f, n] — формирует наддиагональную матрицу размером пхп;
  • LowerDiagonalMatrix [f, n] — формирует поддиагональную матрицу размером пхп;
  • ZeroMatrix [n] — формирует квадратную нулевую матрицу размером пхп;
  • ZeroMatrix [m, n] — формирует нулевую матрицу размером тхп;
  • HilbertMatrix [n] — формирует квадратную матрицу Гильберта размером пхп;
  • HilbertMatrix [m, n] — формирует матрицу Гильберта размером тхп;
  • HankelMatrix [n] — формирует квадратную матрицу Ганкеля размером пхп;
  • HankelMatrix [m, n] — формирует матрицу Ганкеля размером тхп.

Примеры задания матриц разного типа приведены ниже:
UpperDiagonalMatrix[f, 3] //MatrixForm
LowerDiagonalMatrix[#1 + #2 &, 4] //MatrixForm
HilbertMatrix[2, 4] //MatrixForm
HankelMatrix[{w, x, y, z}] //MatrixForm
Наконец, в подпакет входит еще одна функция, LinearEquationsToMatri-ces [eqns, vars], которая из записи линейного уравнения eqns с переменными vars формирует расширенную матрицу, содержащую матрицу коэффициентов левой части уравнения и вектор свободных членов.
Пример применения данной функции:
LinearEquationsToMatrices[
а[1,1]*х + а[1,2]*у == с[1],
а[2,1]*х + а[2,2]*у == с[2], х, у]
{{{{{a11, a12), {а21, а22}}[1, 1],
{{a11, a12), {a21, а22}}[1, 2]}, {{{a11, a12}, {a21, a22}}[2, 1],
{{a11, a12), {a21, a22}} [2, 2]}}, {c[l],c[2]}}
 
Ортогонализация и нормализация — Ortogonalization
В подпакете ортогонализации Ortogonalization имеются следующие функции:

  • GramSchmidt [ {vl, v2,…} ] — создает ортогональное множество на основе списка векторов v1, v2, …;
  • Normalize [vect] — возвращает нормированный вектор vect;
  • Projection [vectl, vect2] — дает ортогональную проекцию вектора vl на вектор v2.

В этих функциях после аргументов допустимы опции InnerProduct->exprn Normalized->False (отказ от нормировки). Примеры работы с функциями ортогонализации представлены ниже:
<<LinearAlgebra`Orthogonalization`
{wl, w2, w3} = GramSchmidt[ {{1,3,2}, {2,4,3}, {2,4,6}}]
{ wl . w2, w2 . w3, wl . w3, wl . wl, w2 . w2, w3 . w3}
{0, 0, 0, 1, 1, 1}
GramSchmidt[{1, x, x^2, x^3, x^4}, InnerProduct -> (Integrate[#l #2,{x,-l,l}]&)] //Simplify
Normalize[LegendreP[2,x], InnerProduct ->(Integrate[#l #2,{x,-l,l}]&)]
{wl, w2} = GramSchmidt[{{3,4,3}, {2,3,6}}, Normalized -> False]
{wl . wl, wl . w2}

{34, 0}

Дискретные перестановки — Permutations

Дискретные перестановки — Permutations
В подпакете Permutations определен ряд функций дискретных перестановок:

  • RandomPermutation [n] — случайные перестановки из n элементов;
  • Ordering [list] — дает перестановки в установленном списком list порядке;
  • ToCycles [perm] — дает циклическую декомпозицию для списка list;
  • FromCycles [ {cicl, cic2,…}] — возвращает перестановки из циклических декомпозиций cic1, cic2, …;
  • PermutationQ [list] — возвращает True, если список list представляет перестановки, и False в ином случае.

Работа функций поясняется следующими примерами:
<<DiscreteMath`Permutations`
RandomPermutation[16]
{16, 12, 11, 5, 3, 4, 9, 14, 2, 8, 15, I, 13, 7, 10, 6}
ToCycles[%]
{{16, 6, 4, 5, 3, 11, 15, 10, 8, 14, 7, 9, 2, 12, 1}, {13}}
FromCycles[%]
{16, 12, 11, 5, 3, 4, 9, 14, 2, 8, 15, 1, 13, 7, 10, 6}
Ordering[%]
{12, 9, 5, 6, 4, 16, 14, 10, 7, 15, 3, 2, 13, 8, 11, 1}
 
Решение рекуррентных разностных уравнений — RSolve
Для решения рекуррентных разностных уравнений в подпакет RSolve введены следующие функции:

  • RSolve [eqn, a [n] , n] — решает рекуррентное уравнение для а [n];
  • RSolve [eqn, a, n] — решает рекуррентное уравнение для функции а;
  • RSolvet {eqnl, eqn2,…}, {al, a2,…},n] — решает систему рекуррентных уравнений, представленных списками.

Ниже представлены примеры применения данных функций:
<<DiscreteMath` RSolve`
RSolve[a[n+l] == 2 a[n], a[n], n]
{{a[n] -> 2nC[l]}}
RSolve[a[n] == a[n-l] + a[n-2], a[0] == a[l] == 1, a[n], n]
RSolve[ a[0] == a[l] == 2,
(n+1) (n+2) a[n+2]- 2 (n+1) a[n+l]- 3 a[n] == 0, a[n], n]
 
Деревья—Tree
Подпакет Tree содержит функции создания и применения древовидных структур, именуемых деревьями. Вот эти функции:

  • MakeTree [list] — создает дерево по информации, представленной в списке list;
  • TreeFind [tree, x] — возвращает позицию наименьшего элемента, превосходящего х в списке list, представляющем дерево.

Действие этих функций поясняют следующие примеры:
<<DiscreteMath` Tree`
MakeTree[{el, e2, е3, е4}]
{{e2, 2), {{el, 1}, {}, {}}, {{e3, 3}, {}, {{e4, 4}, {}, {}}}}
tree = MakeTree[{8.5, 1.2, 9.1, 3.4, 5., 7.6 ,6.4}]
{{6.4, 4}, {{3.4, 2}, {{1.2, 1}, {}, {}}, {{5., 3}, {}, {}}},
{{8.5, 6}, {{7.6, 5}, {}, {}}, {{9.1, 7}, {},{}}}}
TreeFind[tree, 1.2]
1 . .
TreeFind[tree, 1]
0
Для визуализации деревьев служат следующие функции:

  • TreePlot [tree] — строит график дерева tree;
  • ExprPlot [expr] — строит график, представляющий ехрг в виде дерева.

Примеры построения графиков деревьев представлены на8. Верхнп; график построен по данным дерева tree, определенного в приведенных выи: примерах, а нижний — по данным случайного дерева.

Построение графиков деревьев по выражению ехрг с помощью функции ExprPlot демонстрирует9.

Графы и их функции

Графы и их функции
Mathematica имеет самые обширные возможности решения задач, связанных с графами. Задание графов и манипуляции с ними также включены в пакет комбинаторики. Они представлены четырьмя группами функций.

Представление графов

AddEdge

AddVertex

Breadth’FirstTraversal

ChangeEdges

ChangeVertices

CircularVertices

CompleteQ

Contract

DeleteEdge

DeieteVertex

DepthFirstTr aversal

Diameter

DilateVertices

Distribution

Eccentricity

Edges

EmptyQ

FromAd j acencyLists

FromOrderedPairs

FromUnorderedPairs

GraphCenter

GraphComplement

InduceSubgraph

M

MakeSimple

MakeUndirected

Normal! zeVerticesPointsAndLines

Pseudograph

RadialEmbedding

Radius

RankGraph

RankedEmbedding

ReadGraph

RemoveSelf Loops

RootedEmbedding

RotateVertices

ShakeGraph

ShowGraph

ShowLabe 1 edGr aph

SimpleQ

Spectrum

SpringErrbedding

ToAdjacencyLists

ToOrderedPairs

ToUnorderedPairs

TranslateVertices

UndirectedQ

UnweightedQ

Vertices

WriteGraph

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

Реализация рекурсивных и рекуррентных алгоритмов

Реализация рекурсивных и рекуррентных алгоритмов
Рассмотрим несколько простых примеров, выявляющих суть функционального программирования. Вначале это будет пример, в котором задана функция sen [х, n], вычисляющая сумму синуса в степени n и косинуса в степени n:
scn[x_, n_] := Sin[x]^n + Cos[х]^n
scn[l, 2]
1
scn[x, 2]
1
scn[x, n]
Cos[x]n+ Sin[x]n
В этом простейшем примере результат вычислений есть возвращаемое функцией sen значение — численное или символьное. В свою очередь, функция sen в своем теле имеет встроенные функции синуса и косинуса.
Важное место в решении многих математических задач занимают реализации рекурсивных и рекуррентных алгоритмов. далее…