stringtranslate.com

Итерированная функция

Итерированные преобразования объекта слева.
Сверху — поворот по часовой стрелке на 90°. Он имеет порядок 4, поскольку это наименьший положительный показатель, который производит тождество. Ниже — отображение сдвига с бесконечным порядком.
Ниже — их композиции , которые оба имеют порядок 3.

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

Например, на изображении справа:

Итеративные функции изучаются в информатике , фракталах , динамических системах , математике и физике ренормгруппы .

Определение

Ниже приведено формальное определение итерационной функции на множестве X.

Пусть X — множество, а f : XXфункция .

Определим f n как n -ю итерацию f , где n — неотрицательное целое число, следующим образом: и

где id X — это тождественная функция на X , а ( f g )( x ) = f ( g ( x )) обозначает композицию функций . Эта нотация восходит к Джону Фредерику Уильяму Гершелю в 1813 году. [1] [2] [3] [4] Гершель приписывал ее Гансу Генриху Бюрманну , но не давал конкретной ссылки на работу Бюрманна, которая остается нераскрытой. [5]

Поскольку обозначение f n может относиться как к итерации (композиции) функции f , так и к возведению в степень функции f (последнее обычно используется в тригонометрии ), некоторые математики [ требуется ссылка ] предпочитают использовать для обозначения композиционного значения, записывая f n ( x ) для n -й итерации функции f ( x ) , как, например, f ∘3 ( x ) означает f ( f ( f ( x ))) . Для той же цели f [ n ] ( x ) использовал Бенджамин Пирс [6] [4] [примечание 1] , тогда как Альфред Принсхейм и Жюль Молк предложили вместо этого n f ( x ) . [7] [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 называется последовательностью Пикара [8] [9], названной в честь Шарля Эмиля Пикара .

Для заданного x из X последовательность значений f n ( x ) называется орбитой x . ​

Если f n ( x ) = f n + m ( x ) для некоторого целого числа m > 0 , орбита называется периодической орбитой . Наименьшее такое значение m для заданного x называется периодом орбиты . Сама точка x называется периодической точкой . Задача обнаружения цикла в информатике — это алгоритмическая задача нахождения первой периодической точки на орбите и периода орбиты.

Фиксированные точки

Если x = f ( x ) для некоторого x из X (то есть период орбиты x равен 1 ), то x называется неподвижной точкой итерированной последовательности. Множество неподвижных точек часто обозначается как Fix ( f ) . Существует ряд теорем о неподвижных точках , которые гарантируют существование неподвижных точек в различных ситуациях, включая теорему Банаха о неподвижной точке и теорему Брауэра о неподвижной точке .

Существует несколько методов ускорения сходимости последовательностей, полученных с помощью итерации фиксированной точки . [10] Например, метод Эйткена, примененный к итерированной фиксированной точке, известен как метод Стеффенсена и обеспечивает квадратичную сходимость.

Ограничивающее поведение

При итерации можно обнаружить, что есть множества, которые сжимаются и сходятся к одной точке. В таком случае точка, к которой происходит сходимость, известна как притягивающая неподвижная точка . И наоборот, итерация может создать видимость точек, расходящихся от одной точки; это будет иметь место для нестабильной неподвижной точки . [11]

Когда точки орбиты сходятся к одному или нескольким пределам, множество точек накопления орбиты известно как предельное множество или ω-предельное множество .

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

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

Инвариантная мера

Если рассматривать эволюцию распределения плотности, а не динамику отдельных точек, то предельное поведение задается инвариантной мерой . Ее можно визуализировать как поведение облака точек или пылевого облака при повторяющейся итерации. Инвариантная мера является собственным состоянием оператора Рюэля-Фробениуса-Перрона или оператора переноса , соответствующим собственному значению 1. Меньшие собственные значения соответствуют нестабильным, распадающимся состояниям.

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

Дробные итерации и потоки, а также отрицательные итерации

g : RR является тривиальным функциональным корнем 5-й степени из f : R +R + , f ( x ) = sin( x ) . Показановычисление f ( π6 ) = 12 = g 5 ( π6 ).

Понятие 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 ) не обозначает уникальную функцию, так же как числа имеют несколько алгебраических корней. Тривиальный корень f всегда можно получить, если область определения f может быть достаточно расширена, см. рисунок. Выбранные корни обычно принадлежат исследуемой орбите.

Дробная итерация функции может быть определена: например, половинная итерация функции f — это функция g, такая что g ( g ( x )) = f ( x ) . [12] Эта функция 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 mf n = f m + n . Эту идею можно обобщить так, что количество итераций n станет непрерывным параметром , своего рода непрерывным «временем» непрерывной орбиты . [13] [14]

В таких случаях систему называют потоком ( см. раздел о сопряженности ниже).

Если функция биективна (и, следовательно, обладает обратной функцией), то отрицательные итерации соответствуют обратным функциям и их композициям. Например, 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 ( f 1/2 ( x )) = f 0 ( x ) = x .

Некоторые формулы для дробной итерации

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

  1. Сначала определите неподвижную точку для функции, такую, что f ( a ) = a .
  2. Определим f n ( a ) = a для всех n, принадлежащих действительным числам. Это, в некотором смысле, наиболее естественное дополнительное условие для дробных итераций.
  3. Разложим f n ( x ) вокруг неподвижной точки a в ряд Тейлора ,
  4. Расширить
  5. Подставим вместо f k ( a ) = a , для любого k ,
  6. Воспользуйтесь геометрической прогрессией для упрощения терминов. Существует особый случай, когда f '(a) = 1 ,

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

Пример 1

Например, установив f ( x ) = Cx + D, получим неподвижную точку a = D /(1 − C ) , поэтому приведенная выше формула заканчивается на , что легко проверить.

Пример 2

Найдите значение , где это сделано n раз (и, возможно, интерполированные значения, когда n не является целым числом). Имеем f ( x ) = 2 x . Неподвижная точка — это a = f (2) = 2 .

Итак, установим x = 1 и f n (1) , расширенную вокруг значения фиксированной точки 2, получим бесконечный ряд, который, если брать только первые три члена, верен до первого десятичного знака, когда n положительно. См. также Тетрация : f n (1) = n2 . Использование другой фиксированной точки a = f (4) = 4 приводит к тому, что ряд расходится.

При n = −1 ряд вычисляет обратную функцию ⁠2+ln x/в 2 .

Пример 3

Используя функцию f ( x ) = x b , разложим ее вокруг фиксированной точки 1, чтобы получить ряд , который является просто рядом Тейлора функции x ( b n ), разложенной вокруг 1.

Спряжение

Если f и g — две итерированные функции и существует гомеоморфизм h такой, что g = h −1fh , то f и g называются топологически сопряженными .

Очевидно, топологическая сопряженность сохраняется при итерации, так как g n  =  h −1  ○  f nh . Таким образом, если можно решить для одной итерированной системы функций, то также есть решения для всех топологически сопряженных систем. Например, отображение палатки топологически сопряжено с логистическим отображением . В качестве особого случая, взяв f ( x ) = x  + 1 , мы имеем итерацию g ( x ) = h −1 ( h ( x ) + 1) как

g n ( x ) = h −1 ( h ( x ) +  n ) для любой функции h .

Сделав замену x = h −1 ( y ) = ϕ ( y ), получим

g ( ϕ ( y )) = ϕ ( y +1) , форма, известная как уравнение Абеля .

Даже при отсутствии строгого гомеоморфизма вблизи фиксированной точки, здесь взятой за x = 0, f (0) = 0, часто можно решить [16] уравнение Шредера для функции Ψ, что делает f ( x ) локально сопряженной с простым растяжением, g ( x ) = f '(0) x , то есть

ж ( Икс ) знак равно Ψ -1 ( ж '(0) Ψ( Икс )) .

Таким образом, его итерационная орбита, или поток, при соответствующих условиях (например, f '(0) ≠ 1 ), представляет собой сопряженную орбиту монома,

Ψ −1 ( f '(0) n Ψ( x )) ,

где n в этом выражении служит в качестве простого показателя степени: функциональная итерация была сведена к умножению! Здесь, однако, показатель степени n больше не должен быть целым или положительным, и является непрерывным «временем» эволюции для полной орбиты: [17] моноид последовательности Пикара (ср. полугруппа преобразований ) обобщился до полной непрерывной группы . [18]

Итерации функции синуса ( синяя ) в первом полупериоде. Полуитерация ( оранжевая ), т. е. функциональный квадратный корень синуса; функциональный квадратный корень этого, четвертная итерация (черная) над ней; и дальнейшие дробные итерации до 1/64. Функции ниже ( синего ) синуса представляют собой шесть целых итераций под ним, начиная со второй итерации ( красной ) и заканчивая 64-й итерацией. Зеленый огибающий треугольник представляет собой предельную нулевую итерацию, пилообразная функция служит отправной точкой, ведущей к функции синуса. Пунктирная линия представляет собой отрицательную первую итерацию, т. е. обратную синусу (arcsin). (С веб-сайта общей педагогики. [19] Для обозначения см. [2].)

Этот метод (пертурбативное определение главной собственной функции Ψ, ср. матрицу Карлемана ) эквивалентен алгоритму предыдущего раздела, хотя на практике более мощный и систематический.

цепи Маркова

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

Примеры

Существует множество хаотических отображений . Известные итерационные функции включают множество Мандельброта и итерационные системы функций .

Эрнст Шредер [20] в 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/2 ln(1 − 2 x ) , и, следовательно, f n ( x ) = − 1/2 ((1 − 2 x ) 2 n − 1) .

Если fдействие элемента группы на множество, то итерированная функция соответствует свободной группе .

Большинство функций не имеют явных общих выражений замкнутой формы для n -й итерации. В таблице ниже перечислены некоторые [20] , которые имеют. Обратите внимание, что все эти выражения действительны даже для нецелых и отрицательных n , а также неотрицательных целых n .

Примечание: эти два особых случая ax 2 + bx + c являются единственными случаями, имеющими решение в замкнутой форме. Выбор b = 2 = – a и b = 4 = – a , соответственно, еще больше сводит их к нехаотическим и хаотическим логистическим случаям, обсуждавшимся до таблицы.

Некоторые из этих примеров связаны между собой простыми сопряжениями.

Средства обучения

Итерированные функции можно изучать с помощью дзета-функции Артина–Мазура и операторов переноса .

В области компьютерных наук

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

Определения в терминах итерационных функций

Два важных функционала можно определить в терминах итерационных функций. Это суммирование :

и эквивалентный продукт:

Функциональная производная

Функциональная производная итерированной функции определяется рекурсивной формулой:

Уравнение переноса данных Ли

Итеративные функции возникают при разложении в ряд комбинированных функций, таких как g ( f ( x )) .

Учитывая скорость итерации , или бета-функцию (физика) ,

для n итерации функции f имеем [22]

Например, для жесткой адвекции, если f ( x ) = x + t , то v ( x ) = t . Следовательно, g ( x + t ) = exp( t ∂/∂ x ) g ( x ) , действие простым оператором сдвига .

И наоборот, можно определить f ( x ) при произвольном v ( x ) с помощью общего уравнения Абеля , рассмотренного выше,

где

Это очевидно, если отметить, что

Для непрерывного индекса итерации t , теперь записанного как нижний индекс, это равнозначно знаменитой экспоненциальной реализации Ли непрерывной группы,

Начальная скорость потока v достаточна для определения всего потока, учитывая эту экспоненциальную реализацию, которая автоматически обеспечивает общее решение уравнения функционального переноса , [23]

Смотрите также

Примечания

  1. ^ в то время как f ( n ) берется для n- й производной
  2. ↑ Обозначение n f ( x ) Альфреда Прингсхайма и Жюля Молька (1907) для обозначения композиций функций не следует путать с обозначением n x Рудольфа фон Биттера Рюккера (1982) , введенным Гансом Маурером (1901) и Рубеном Луисом Гудштейном (1947) для тетрации , или с обозначением n x с предварительным надстрочным индексом для корней Дэвида Паттерсона Эллермана (1995) .

Ссылки

  1. ^ Гершель, Джон Фредерик Уильям (1813) [1812-11-12]. «О замечательном применении теоремы Котеса». Philosophical Transactions of the Royal Society of London . 103 (часть 1). Лондон: Royal Society of London , напечатано W. Bulmer and Co., Cleveland-Row, St. James's, продано G. and W. Nicol, Pall-Mall: 8–26 [10]. doi : 10.1098/rstl.1813.0005 . JSTOR  107384. S2CID  118124706.
  2. ^ Гершель, Джон Фредерик Уильям (1820). «Часть III. Раздел I. Примеры прямого метода разностей». Сборник примеров приложений исчисления конечных разностей . Кембридж, Великобритания: напечатано Дж. Смитом, продано Дж. Дейтоном и сыновьями. стр. 1–13 [5–6]. Архивировано из оригинала 2020-08-04 . Получено 2020-08-04 .[1] (Примечание. Здесь Гершель ссылается на свою работу 1813 года и упоминает более раннюю работу Ганса Генриха Бюрмана .)
  3. ^ Пеано, Джузеппе (1903). Formulaire mathématique (на французском языке). Том. IV. п. 229.
  4. ^ abc Cajori, Florian (1952) [март 1929]. "§472. Степень логарифма / §473. Повторные логарифмы / §533. Нотация Джона Гершеля для обратных функций / §535. Сохранение конкурирующих нотаций для обратных функций / §537. Степени тригонометрических функций". История математических обозначений. Т. 2 (3-е исправленное издание выпуска 1929 года, 2-е изд.). Чикаго, США: Open court publishing company . стр. 108, 176–179, 336, 346. ISBN 978-1-60206-714-1. Получено 18.01.2016 . […] §473. Повторные логарифмы […] Здесь мы отмечаем символику, использованную Прингсхаймом и Мольком в их совместной статье в Encyclopédie : « 2 log b a = log b (log b a ), …, k +1 log b a = log b ( k log b a )». [a] […] §533. Обозначение Джона Гершеля для обратных функций, sin −1 x , tan −1 x и т. д., было опубликовано им в Philosophical Transactions of London за 1813 год. Он говорит (стр. 10): «Эту запись cos. −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 x вместо sin. sin.  x , log. 3 x вместо log. log. log.  x . Так же, как мы пишем d n  V=∫ n  V , мы можем аналогично записать sin. −1 x =arc (sin.= x ), log. −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. Степени тригонометрических функций. — Для обозначения, скажем, квадрата sin 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 г.)
  5. ^ Гулик, Денни; Форд, Джефф (2024). Встречи с хаосом и фракталами (3-е изд.). CRC Press. стр. 2. ISBN 9781003835776.
  6. ^ Пирс, Бенджамин (1852). Кривые, функции и силы . Т. I (новое издание). Бостон, США. С. 203.{{cite book}}: CS1 maint: location missing publisher (link)
  7. ^ Прингсхайм, Альфред ; Молк, Жюль (1907). Энциклопедия чистых и прикладных математических наук (на французском языке). Том. И. п. 195. Часть I.
  8. ^ Кучма, Марек (1968). Функциональные уравнения с одной переменной . Монография Математическая. Варшава: PWN – Польское научное издательство.
  9. ^ Kuczma, M., Choczewski B., and Ger, R. (1990). Итеративные функциональные уравнения . Cambridge University Press. ISBN 0-521-35561-3.{{cite book}}: CS1 maint: multiple names: authors list (link)
  10. ^ Карлесон, Л.; Гамелен, TDW (1993). Сложная динамика . Университетский текст: Трактаты по математике. Спрингер-Верлаг. ISBN 0-387-97942-5.
  11. ^ Истратеску, Василе (1981). Теория неподвижной точки, Введение , Д. Рейдель, Голландия. ISBN 90-277-1224-7
  12. ^ "Нахождение f, такого что f(f(x))=g(x) при заданном g". MathOverflow .
  13. ^ Aldrovandi, R.; Freitas, LP (1998). "Непрерывная итерация динамических отображений". J. Math. Phys . 39 (10): 5324. arXiv : physics/9712026 . Bibcode : 1998JMP....39.5324A. doi : 10.1063/1.532574. hdl : 11449/65519 . S2CID  119675869.
  14. ^ Берколайко, Г.; Рабинович, С.; Хавлин, С. (1998). «Анализ представления Карлемана аналитических рекурсий». J. Math. Anal. Appl . 224 : 81–90. doi : 10.1006/jmaa.1998.5986 .
  15. ^ "Tetration.org".
  16. ^ Кимура, Тосихуса (1971). «Об итерации аналитических функций», Funkcialaj Ekvacioj Архивировано 26.04.2012 на Wayback Machine 14 , 197-238.
  17. ^ Curtright, TL ; Zachos, CK (2009). "Профили эволюции и функциональные уравнения". Journal of Physics A . 42 (48): 485208. arXiv : 0909.2424 . Bibcode :2009JPhA...42V5208C. doi :10.1088/1751-8113/42/48/485208. S2CID  115173476.
  18. ^ Для явного примера, пример 2 выше сводится просто к f n ( x ) = Ψ −1 ((ln 2) n Ψ( x )) , для любого n , не обязательно целого, где Ψ является решением соответствующего уравнения Шредера , Ψ( 2 x ) = ln 2 Ψ( x ) . Это решение также является бесконечным пределом m для ( f m ( x ) − 2)/(ln 2) m .
  19. ^ Куртрайт, Т.Л. Эволюционные поверхности и функциональные методы Шредера.
  20. ^ аб Шредер, Эрнст (1870). "Ueber iterirte Functionen". Математика. Энн . 3 (2): 296–322. дои : 10.1007/BF01443992. S2CID  116998358.
  21. Бранд, Луис, «Последовательность, определяемая разностным уравнением», American Mathematical Monthly 62 , сентябрь 1955 г., стр. 489–492. онлайн
  22. ^ Берксон, Э.; Порта, Х. (1978). «Полугруппы аналитических функций и операторы композиции». The Michigan Mathematical Journal . 25 : 101–115. doi : 10.1307/mmj/1029002009 . Curtright, TL; Zachos, CK (2010). "Хаотические отображения, гамильтоновы потоки и голографические методы". Journal of Physics A: Mathematical and Theoretical . 43 (44): 445101. arXiv : 1002.0104 . Bibcode :2010JPhA...43R5101C. doi :10.1088/1751-8113/43/44/445101. S2CID  115176169.
  23. ^ Aczel, J. (2006), Лекции по функциональным уравнениям и их приложениям (Dover Books on Mathematics, 2006), Гл. 6, ISBN 978-0486445236

Внешние ссылки