Иллюстрированный самоучитель по Mathematica
Суперпозиция функций
При функциональном
программировании часто используется суперпозиция
функций. Для ее реализации
используются следующие функции:
-
Nest [expr, x, n]
— n раз применяет выражение (функцию) ехрг к заданному аргументу х,
-
NestList [f, x, n]
— возвращает список результатов (п+1)-кратного применения функции f к заданному
аргументу х;
-
Fold[f, x, list] —
дает последний элемент в FoldList [f, x, list];
-
FoldList [f, x, {a,b,...}
] — возвращает список {x,f [x,a],f [f [x,a],b],...};
-
ComposeList [ { f
, f ,...}, x] — генерирует список в форме {х,а[х] ,а[а[х] ],...}.
Примеры,
иллюстрирующие действие этих функций, представлены ниже:
Nest[f, x, 5]
f[f[f[f[f[x]]]]]
Nest[Exp[x], x, 5]
Ех[Ех[Ех[Ех[Ех[х]]]]]
NestList[f, x, 3]
{x, f[x], f[f[x]], f[f[f[x]]]}
Fold[f, x,
(-1, 2, 3}]
f[f[f[x, 1],
2], 3]
FoldList[f,
x, {1, 2, 3}]
{x, f[x, 1], f[f[x, 1], 2], f[f[f{x, 1], 2], 3]}
ComposeList[{Exp, Ln, Sin), x]
{x, Ex, Ln[Ex] , SinlLn[Ex]] ]}
Функции Fixed Point и Catch
В функциональном
программировании вместо циклов, описываемых далее, может использоваться следующая
функция:
-
FixedPoint [ f, expr
] — вычисляет expr и применяет к нему f, пока результат не перестанет изменяться;
-
FixedPoint [ f, expr,
SameTest->comp] — вычисляет expr и применяет к нему
f, пока два последовательных
результата не дадут True в тесте SameTest.
Пример применения
функции FixedPoint:
FixedPoint[Function[t, Print[t];
Floor[t/2]], 27]
27
13
6
3
1
0
0
Последний
результат (ноль) выводится в отдельной (нумерованной) ячейке вывода и означает
завершение процесса итераций — деления t на 2.
Следующий
пример показывает, как можно создать цепную дробь с помощью
функции Nest:
Nest[
Functiontt, 1/(1+t)], у, 3 ]
1/(1/(1/((1+y)+1)+1)+1)
Еще одна
функция такого рода — это Catch:
-
Catch [expr] — вычисляет
expr, пока не встретится Throw [value], затем возвращает
value;
-
Catch [expr, form]
— вычисляет expr, пока не встретится Throw [value,
tag], затем возвращает value;
-
Catch [expr, form, f] — возвращает f
[value, tag] вместо value. Ниже представлены некоторые конструкции
циклов с оператором Catch:
Catch[
x, a, f ]
х
Catch[
Throw[ x, у ], у, fun ]
fun[x, у]
Catch[ NestList[l/(#
+ 1)&, -3, 5] ]
{-3,-1/2, 2,
1/3, 3/4, 4/7}
Catch[ NestList[l/(#
+ 1)&, -3., 5] ]
{-3., -0.5,
2., 0.333333, 0.75, 0.571429}
Catch[Do[Print[i];
If[i > 4, Throw[i+2]], i, 10]]
1
2
3
4
5
7
Реализация рекурсивных и рекуррентных алгоритмов
Рассмотрим
несколько простых примеров, выявляющих суть функционального программирования.
Вначале это будет пример, в котором задана функция 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 в своем теле имеет встроенные функции
синуса и косинуса.
Важное место
в решении многих математических задач занимают реализации рекурсивных и рекуррентных
алгоритмов. Напомним, что рекурсия означает обращение функции к самой себе внутри
ее тела, а рекуррентность — получение результата на данном шаге по результатам
вычислений на предшествующих шагах.
Рассмотрим,
как это делается, с помощью описанных выше функций. Классический пример реализации
рекурсивного алгоритма — вычисление факториала путем задания функции, в теле
которой есть обращение к ней же самой:
f[n_] :=n*f[n-1];f[0]=l;f[1]=1;
Полезно,
однако, обратить внимание на возможность явного задания результата для конкретных
значений аргумента: f [ 0 ] =1 и f [ 1 ] =1. Так что рекурсия реализуется, начиная
с n=2 и выше, в соответствии с классическим определением факториала.
Для реализации
рекуррентных алгоритмов в Mathematica имеется ряд функций, таких как Nest или
FixedPoint. В следующих примерах показано вычисление
квадратного
корня из числа 5 по известному алгоритму Ньютона, записанному в виде функции
newtonS:
newtonS
[x_] := N[ 1/2 ( х + 5/х )]
Nest[newton5, 1.0, 5]
2.23607
NestList
[newtonS, 1.0, 5]
{1., 3., 2.33333,
2.2381, 2.23607, 2.23607}
FixedPoint [newtonS, 1.0]
2.23607
FixedPointList [newtonS, 1.0]
{1., 3., 2.33333,
2.2381, 2.23607, 2.23607, 2.23607, 2.23607}
FixedPointList
[newtonS, 1.0, SameTest -> (Abs[#l- #2] < 10.A-4 &)]
{1., 3., 2.33333,
2.2381, 2.23607, 2.23607}
Обратите
внимание на то, что функции Nest и FixedPoint дают единственный конечный результат,
тогда как функции NestList и FixedPointList возвращают еще и все промежуточные
результаты итераций. Последний пример иллюстрирует остановку вычислений по заданной
погрешности, равной 10
-4
.
Далее зададим
функцию, реализующую алгоритм Ньютона для нахождения корня произвольного выражения
f(x) при начальном значении х
0
= а, по следующим формулам:
x0=a;
xn=xn-1-f(xn-1)/f'(xn-1)
Эту функцию
можно записать следующим образом:
newtoniter[f_,
x0_, n_] :=Nest[(# - f [#]/f'[#]) &, N[x0] , n]
Тогда вычисления
корня из выражения е^x - 2 с начальным приближением х
0
= 0.5 при числе итераций n можно организовать с помощью функций Nest
и NestList:
newtoniter
[Function [ {х} , Ехр[х] - 2.0], 0.5, 5]
0.693147
newtoniter
[Function [ {х }, Ехр[х] - 2.0], 0.5, #] & /@ Range [5]
{0.713061, 0.693344,
0.693147, 0.693147, 0.693147}
newtoniterl[f_,x0_,n_]
:= NestList[ (#-f [#] /f ' [#] ) &,N[x0] , n]
newtoniterl
[Function [{x} , Exp[x] - 2.0], 0.5, 5]
{0.5, 0.713061,
0.693344, 0.693147, 0.693147, 0.693147}
В первом
случае возвращается только окончательный результат, а в других — еще и все промежуточные.
Функция FixedPoint позволяет осуществлять итерации
до тех пор,
пока результат не перестанет изменяться (с машинной точностью). Это иллюстрирует
следующий пример:
newtonfp[f_,
х0_] := FixedPoint[ (# - f [#]/f'[#]) &, N[xO]]
newtonfp[Function[{x}
, Exp[x] - 2.0], 0.5]
0.693147
Более сложные
примеры функционального программирования мы рассмотрим позже, при описании создания
пакетов расширения систем Mathematica.
|
