В математике итерированная функция — это функция, которая получается путем составления другой функции сама с собой два или несколько раз. Процесс многократного применения одной и той же функции называется итерацией . В этом процессе, начиная с некоторого исходного объекта, результат применения данной функции снова подается в функцию в качестве входных данных, и этот процесс повторяется.
Например, на изображении справа:
Итерированные функции изучаются в информатике , фракталах , динамических системах , математике и физике ренормгрупп .
Далее следует формальное определение итерированной функции на множестве X.
Пусть X — множество, а f : X → X — функция .
Определение f n как n -й итерации f (обозначение, введенное Гансом Генрихом Бюрманом [ нужна ссылка ] и Джоном Фредериком Уильямом Гершелем [1] [2] [3] [4] ), где n — неотрицательное целое число , к:
где id X — тождественная функция на X , а ( f g )( x ) = f ( g ( x )) обозначает композицию функций .
Поскольку обозначение f n может относиться как к итерации (композиции) функции f , так и к возведению в степень функции f (последнее обычно используется в тригонометрии ) , некоторые математики предпочитают использовать ∘ для обозначения композиционного значения, записывая f ∘ n ( x ) для n -й итерации функции f ( x ) , как, например, f ∘3 ( x ) что означает f ( f ( f ( x ))) . С той же целью f [ n ] ( x ) использовал Бенджамин Пирс [5] [4] [nb 1] , тогда как Альфред Прингшейм и Жюль Молк вместо этого предложили n f ( x ) . [6] [4] [количество 2]
В общем, для всех неотрицательных целых чисел m и n справедливо следующее тождество :
Это структурно идентично свойству возведения в степень , что a m a n = a m + n .
Вообще, для произвольных общих (отрицательных, нецелых и т. д.) индексов m и n это соотношение называется функциональным уравнением сдвига , ср. Уравнение Шредера и уравнение Абеля . В логарифмическом масштабе это сводится к свойству вложения полиномов Чебышева T m ( T n ( x )) = T m n ( x ) , поскольку T n ( x ) = cos ( n arccos ( x )) .
Соотношение ( f m ) n ( x ) = ( f n ) m ( x ) = f mn ( x ) также имеет место, аналогично свойству возведения в степень, что ( a m ) n = ( a n ) m = a mn .
Последовательность функций f n называется последовательностью Пикара , [7] [8] названной в честь Шарля Эмиля Пикара .
Для данного x в X последовательность значений fn ( x ) называется орбитой x . _ _
Если fn ( x ) = fn + m ( x ) для некоторого целого числа m > 0 , орбита называется периодической орбитой . Наименьшее такое значение m для данного x называется периодом орбиты . Сама точка x называется периодической точкой . Проблема обнаружения цикла в информатике — это алгоритмическая проблема поиска первой периодической точки на орбите и периода орбиты.
Если x = f ( x ) для некоторого x из X (то есть период орбиты x равен 1 ), то x называется неподвижной точкой итерированной последовательности. Набор фиксированных точек часто обозначается как Fix ( f ) . Существует ряд теорем о неподвижной точке , которые гарантируют существование неподвижных точек в различных ситуациях, включая теорему Банаха о неподвижной точке и теорему Брауэра о неподвижной точке .
Существует несколько методов ускорения сходимости последовательностей, создаваемых итерациями с фиксированной точкой . [9] Например, метод Эйткена , примененный к повторяющейся фиксированной точке, известен как метод Стеффенсена и обеспечивает квадратичную сходимость.
После итерации можно обнаружить, что существуют множества, которые сжимаются и сходятся к одной точке. В таком случае точка, к которой сходится, называется притягивающей фиксированной точкой . И наоборот, итерация может создать впечатление, что точки расходятся от одной точки; это было бы в случае нестабильной фиксированной точки . [10]
Когда точки орбиты сходятся к одному или нескольким пределам, набор точек накопления орбиты известен как предельный набор или ω-предельный набор .
Идеи притяжения и отталкивания обобщаются аналогичным образом; можно разделить итерации на стабильные множества и нестабильные множества в соответствии с поведением небольших окрестностей при итерации. Также см. бесконечные композиции аналитических функций .
Возможны и другие ограничивающие модели поведения; например, блуждающие точки — это точки, которые удаляются и никогда не возвращаются даже близко к тому месту, где они начали.
Если рассматривать эволюцию распределения плотности, а не динамику отдельных точек, то предельное поведение задается инвариантной мерой . Его можно представить как поведение облака точек или облака пыли при повторяющихся итерациях. Инвариантная мера является собственным состоянием оператора Рюэля-Фробениуса-Перрона или оператора переноса , соответствующего собственному значению, равному 1. Меньшие собственные значения соответствуют нестабильным, распадающимся состояниям.
В общем, поскольку повторная итерация соответствует сдвигу, оператору переноса и сопряженному с ним оператору Купмана можно интерпретировать как действие операторов сдвига на пространстве сдвига . Теория подсдвигов конечного типа дает общее представление о многих итерированных функциях, особенно о тех, которые приводят к хаосу.
Понятие f 1/ n следует использовать с осторожностью, когда уравнение g n ( x ) = f ( x ) имеет несколько решений, что обычно имеет место, как в уравнении Бэббиджа функциональных корней тождественного отображения. Например, для n = 2 и f ( x ) = 4 x − 6 , g ( x ) = 6 − 2 x и g ( x ) = 2 x − 2 являются решениями; поэтому выражение f 1/2 ( x ) не обозначает уникальную функцию, точно так же, как числа имеют несколько алгебраических корней. Проблема очень похожа на выражение « 0/0 » в арифметике. Тривиальный корень f всегда можно получить, если область определения f можно достаточно расширить, ср. картина. Обычно выбираются корни, принадлежащие изучаемой орбите.
Можно определить дробную итерацию функции: например, полуитерация функции f — это функция g такая, что g ( g ( x )) = f ( x ) . [11] Эту функцию g ( x ) можно записать с использованием индексного обозначения как f 1/2 ( x ) . Аналогично, f 1/3 ( x ) — это функция, определенная так, что f 1/3 ( f 1/3 ( f 1/3 ( x ))) = f ( x ) , а f 2/3 ( x ) может быть определяется как равный f 1/3 ( f 1/3 ( x )) и т. д., и все это основано на упомянутом ранее принципе, что f m ○ f n = f m + n . Эту идею можно обобщить так, что количество итераций n становится непрерывным параметром , своего рода непрерывным «временем» непрерывной орбиты . [12] [13]
В таких случаях систему называют потоком ( см. раздел о сопряжении ниже).
Если функция биективна (и, следовательно, обладает обратной функцией), то отрицательные итерации соответствуют обратным функциям и их композициям. Например, f −1 ( x ) — это нормальная инверсия f , а f −2 ( x ) — инверсия, составленная сама с собой, т.е. f −2 ( x ) = f −1 ( f −1 ( x )) . Дробно-отрицательные итерации определяются аналогично дробно-положительным; например, f −1/2 ( x ) определяется так, что f −1/2 ( f −1/2 ( x )) = f −1 ( x ) , или, что то же самое, такое, что f −1/2 ( ж 1/2 ( Икс )) знак равно ж 0 ( Икс ) знак равно Икс .
Один из нескольких методов нахождения формулы ряда для дробной итерации с использованием фиксированной точки заключается в следующем. [14]
Это можно продолжать бесконечно, хотя и неэффективно, поскольку последние условия становятся все более сложными. Более систематическая процедура описана в следующем разделе, посвященном сопряжению .
Например, установка f ( x ) = Cx + D дает фиксированную точку a = D /(1 − C ) , поэтому приведенная выше формула завершается просто
Найдите значение того, где это делается n раз (и, возможно, интерполированные значения, когда n не является целым числом). У нас есть ж ( Икс ) знак равно √ 2 Икс . Неподвижной точкой является a = f (2) = 2 .
Итак, положим x = 1 и f n (1) , развернутый вокруг значения фиксированной точки 2, тогда будет бесконечной серией,
Для n = −1 ряд вычисляет обратную функцию 2+ln х/пер. 2.
С помощью функции f ( x ) = x b разверните вокруг фиксированной точки 1, чтобы получить ряд
Если f и g — две итерированные функции и существует гомеоморфизм h такой, что g = h −1 ○ f ○ h , то f и g называются топологически сопряженными .
Очевидно, топологическая сопряженность сохраняется при итерации, поскольку g n = h −1 ○ f n ○ h . Таким образом, если можно решить одну итерированную систему функций, у него также есть решения для всех топологически сопряженных систем. Например, карта палаток топологически сопряжена с логистической картой . В качестве частного случая, принимая f ( x ) = x + 1 , можно получить итерацию g ( x ) = h −1 ( h ( x ) + 1) как
Сделав замену x = h −1 ( y ) = φ ( y ) , получим
Даже в отсутствие строгого гомеоморфизма вблизи фиксированной точки, взятой здесь за точку x = 0, f (0) = 0, часто можно решить [15] уравнение Шредера для функции Ψ, что делает f ( x ) локально сопряжено с простым расширением, g ( x ) = f '(0) x , то есть
Таким образом, его итерационная орбита, или поток, при соответствующих условиях (например, f '(0) ≠ 1 ) представляет собой сопряженную орбиту монома,
где n в этом выражении служит простым показателем степени: функциональная итерация сведена к умножению! Здесь, однако, показатель n больше не обязательно должен быть целым или положительным и представляет собой непрерывное «время» эволюции для полной орбиты: [ 16] моноид последовательности Пикара (ср. Полугруппа преобразований ) обобщился до полной непрерывной группа . [17]
Этот метод (пертурбативное определение главной собственной функции Ψ, ср. матрица Карлемана ) эквивалентен алгоритму предыдущего раздела, хотя на практике является более мощным и систематическим.
Если функция линейна и может быть описана стохастической матрицей , то есть матрицей, сумма строк или столбцов которой равна единице, то итерированная система известна как цепь Маркова .
Есть много хаотичных карт . К хорошо известным итеративным функциям относятся множество Мандельброта и системы итерированных функций .
Эрнст Шрёдер [ 19] в 1870 году разработал специальные случаи логистического отображения , такие как хаотический случай f ( x ) = 4 x (1 − x ) , так что Ψ( x ) = arcsin( √ x ) 2 , следовательно, f n ( x ) = sin(2 n arcsin( √ x )) 2 .
Нехаотический случай, который Шредер также проиллюстрировал своим методом f ( x ) = 2 x (1 − x ) , дал Ψ ( x ) = −1/2ln(1 - 2 x ) и, следовательно, f n ( x ) = -1/2((1 - 2 Икс ) 2 п - 1) .
Если f — действие элемента группы на множество, то итерированная функция соответствует свободной группе .
Большинство функций не имеют явных общих выражений в замкнутой форме для n -й итерации. В таблице ниже перечислены некоторые [19], которые это делают. Обратите внимание, что все эти выражения действительны даже для нецелых и отрицательных n , а также для неотрицательных целых n .
Примечание: эти два особых случая ax 2 + bx + c — единственные случаи, которые имеют решение в замкнутой форме. Выбор b = 2 = – a и b = 4 = – a соответственно, еще больше сводит их к нехаотичным и хаотичным логистическим случаям, обсуждавшимся перед таблицей.
Некоторые из этих примеров связаны между собой простыми сопряжениями.
Итерированные функции можно изучать с помощью дзета-функции Артина – Мазура и трансфер-операторов .
В информатике итерированные функции встречаются как частный случай рекурсивных функций , которые, в свою очередь, закрепляют изучение таких широких тем, как лямбда-исчисление , или более узких, таких как денотатационная семантика компьютерных программ.
Два важных функционала можно определить в терминах итерированных функций. Это суммирование :
и эквивалентный продукт:
Функциональная производная итерированной функции задается рекурсивной формулой:
Итерированные функции возникают при разложении в ряд комбинированных функций, таких как g ( f ( x )) .
Учитывая скорость итерации или бета-функцию (физика) ,
для n- й итерации функции f имеем [21]
Например, для жесткой адвекции, если f ( x ) = x + t , то v ( x ) = t . Следовательно, g ( x + t ) = exp( t ∂/∂ x ) g ( x ) , действие оператора простого сдвига .
И наоборот, можно указать f ( x ) для произвольного v ( x ) с помощью общего уравнения Абеля , обсуждавшегося выше:
где
Это видно, если отметить, что
Тогда для непрерывного индекса итерации t , теперь записанного в виде нижнего индекса, это равнозначно знаменитой экспоненциальной реализации Ли непрерывной группы:
Начальной скорости потока v достаточно для определения всего потока, учитывая эту экспоненциальную реализацию, которая автоматически обеспечивает общее решение функционального уравнения перевода , [22]
[…] §473. Повторные логарифмы […] Отметим здесь символику, использованную Прингсхаймом и Молком в их совместной статье в энциклопедии : « 2 log b a = log b (log b a ), …, k +1 log b a = log b ( k log b а )». [а] […] §533. Обозначения Джона Гершеля для обратных функций sin −1 x , tan −1 x и т. д. были опубликованы им в лондонском журнале Philosophical Transactions за 1813 год. Он говорит (стр. 10): «Эти обозначения потому . -1 e не следует понимать как 1/cos.e , а то, что обычно пишут так, как arc (cos.= e )». Он признает, что некоторые авторы используют cos. m A вместо (cos. A ) m , но он оправдывает свои собственные обозначения, указывая, что, поскольку d 2 x , Δ 3 x , Σ 2 x означают dd x , ΔΔΔ x , ΣΣ x , мы должны писать sin. 2 раза за грех. грех. х , лог. 3 х для журнала. бревно. бревно. Икс . Точно так же, как мы пишем d − n V=∫ n V, мы можем аналогично написать sin. −1 x = дуга (sin.= x ), лог. −1 x .=c x . Несколько лет спустя Гершель объяснил, что в 1813 году он использовал f n ( x ), f − n ( x ), sin. −1 x и т. д., «как он тогда впервые предположил. Однако в течение этих нескольких месяцев ему стала известна работа немецкого аналитика Бурмана , в которой то же самое объясняется значительно раньше. Однако он [Бурман], похоже, не заметил удобства применения этой идеи к обратным функциям tan −1и т. д., и, похоже, он вообще не осознает обратного исчисления функций, которое оно порождает». Гершель добавляет: «Симметрия этого обозначения и, прежде всего, новые и наиболее обширные взгляды, которые оно открывает на природу аналитических операций. кажется, допускают его универсальное принятие». [b] […] §535. Сохранение конкурирующих обозначений для обратной функции. — […] Использование обозначений Гершеля претерпело небольшие изменения в книгах Бенджамина Пирса , чтобы устранить главное возражение. им; Пирс писал: «cos [−1] x » , «log [−1] x ». [c] […] §537. Степени тригонометрических функций. — Для обозначения, скажем, использовались три основных обозначения квадрат греха x , а именно (sin x ) 2 , sin x 2 , sin 2 x . В настоящее время преобладающим обозначением является sin 2 x , хотя первое с наименьшей вероятностью будет неправильно истолковано. В случае sin 2 x два интерпретации напрашиваются сами собой: во-первых, sin x · sin x , во-вторых, [d] sin (sin x ). Поскольку функции последнего типа обычно не проявляются, опасность неправильной интерпретации гораздо меньше, чем в случае log 2 x , где log x · log x и log (log x ) часто встречаются в анализе. […] Обозначение sin n x для (sin x ) n широко использовалось и в настоящее время является преобладающим. […](xviii+367+1 страница, включая 1 страницу дополнений) (Примечание. ISBN и ссылка на перепечатку 2-го издания Cosimo, Inc., Нью-Йорк, США, 2013 г.)
{{cite book}}
: CS1 maint: location missing publisher (link){{cite book}}
: CS1 maint: multiple names: authors list (link)