5. Суперпозиция функций

Суперпозиция функций

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

• 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) при начальном значении х ₀ = а, по следующим формулам:

x0=a;

xn=xn-1-f(xn-1)/f'(xn-1)

Эту функцию можно записать следующим образом:

newtoniter[f_, x0_, n_] :=Nest[(# - f [#]/f'[#]) &, N[x0] , n]

Тогда вычисления корня из выражения е^x - 2 с начальным приближением х ₀ = 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.