Свойства итераций

Сообщение №6857 от Denis 03 февраля 2003 г. 05:09
Тема: Свойства итераций

Я замечал, что при решении некоторых задач можно было бы найти более простое решение если бы можно было сформулировать свойства итерации функции, т.е.
к чему стремится f(f(f(f(f(...f(f(f(x)))...)))) ?

Есть такой способ численного решения, что если для f(x) и x0 выполняется ряд условий, то решениение уравнения:
f(x)=x
можно получить как x=f(f(f(f(f(...f(f(f(x0)))...)))).
Нельзя ли пойти в другую сторону? Т.е. если существует решение уравнения
f(x)=x, пусть x0,
то Lim f(f(f(f(f(...f(f(f(x)))...)))) = x0 ?
Может все-таки есть какие-то свойства у итераций?


Отклики на это сообщение:

> Нельзя ли пойти в другую сторону? Т.е. если существует решение уравнения
> f(x)=x, пусть x0,
> то Lim f(f(f(f(f(...f(f(f(x)))...)))) = x0 ?
> Может все-таки есть какие-то свойства у итераций?

Чтой-то до конца непонятен вопрос или его подоплека.
Иногда можно. На простейших примерах:
Рассмотрим на плоскости графики:
y= x
y=f(x) - например правая ветвь y= x^2, где x0= 0

По условию они пересекаются в x0.
Это значит, что начав с некоторого x1 "около" x0 получим следующую чепочку уменьшающихся отрезков (эдакая спираль с прямыми углами):
[0; x1]
[0; f(x1)]
[0; f(f(x1))]
[0; f(f(f(x1)))] ...

Т.е. на графике последовательность точек должна стремиться к точке с координатами (x0; f(x0)).
Очевидно, под какими углами должны пересекаться оба графика и с какой точки можно начать, чтобы спираль свинтилась в точку.

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

Легко привести примеры, когда предел
Lim f(f(f(f(f(...f(f(f(x)))...)))) <> x0 или не существует для любой начальной x1, несмотря на наличие решения.


А Вы наверное спрашивали, какими свойствами должна обладать f(x) и с каких x1 для нее можно начинать итерации? По-мойму, это зависит от локального поведения функции в некоторой окрестности точки пересечения с прямой y= x.


> Легко привести примеры, когда предел
> Lim f(f(f(f(f(...f(f(f(x)))...)))) <> x0 или не существует для любой начальной x1, несмотря на наличие решения.

Спасибо за столь развернутый ответ :) Но я хотел узнать чему же именно будет равен Lim f(f(f(f(f(...f(f(f(x)))...)))) в зависимости от x1 ? Мне так кажется,
что функция G(x) = Lim f(f(...f(x)...))) , будет отображать в множество, в котором все точки, если они есть, ИЗОЛИРОВАННЫЕ.


> > Легко привести примеры, когда предел
> > Lim f(f(f(f(f(...f(f(f(x)))...)))) <> x0 или не существует для любой начальной x1, несмотря на наличие решения.

> Спасибо за столь развернутый ответ :) Но я хотел узнать чему же именно будет равен Lim f(f(f(f(f(...f(f(f(x)))...)))) в зависимости от x1 ? Мне так кажется,
> что функция G(x) = Lim f(f(...f(x)...))) , будет отображать в множество, в котором все точки, если они есть, ИЗОЛИРОВАННЫЕ.

Не знаю, не задумывался, возможно, что для непрерывных ф-ций так оно и будет. Ведь если непрерывная ф-ция < x в x1, то оно же верно и в некоторой окрестности x1. Стал быть все такие точки будут отделимы друг от друга на числовой прямой. Или я не прав?
Про разрывные ф. никаких мыслей не имею.


> > Легко привести примеры, когда предел
> > Lim f(f(f(f(f(...f(f(f(x)))...)))) <> x0 или не существует для любой начальной x1, несмотря на наличие решения.

> Спасибо за столь развернутый ответ :) Но я хотел узнать чему же именно будет равен Lim f(f(f(f(f(...f(f(f(x)))...)))) в зависимости от x1 ? Мне так кажется,
> что функция G(x) = Lim f(f(...f(x)...))) , будет отображать в множество, в котором все точки, если они есть, ИЗОЛИРОВАННЫЕ.

Вы не могли бы привести пару примеров того, как работает ваша функция функций?
Что будет если взять, к примеру, f(x) = 1/х ?


> Вы не могли бы привести пару примеров того, как работает ваша функция функций?
> Что будет если взять, к примеру, f(x) = 1/х ?

Пусть у нас есть последовательность:
a1=f(x0)
a2=f(f(x0))
a3=f(f(f(x0)))
...
an=f(f(...n раз...f(x0))..))

Для f(x)=1/x последовательность {an} расходится. Это очевидно, но например для f(x)=sin(x) для любого x0 Lim(an)=0, для f(x)=cos(x) для любого x0 Lim(an)=решению уравнения cos(x)-x=0.
Все что меня интересует, это в каких случаях последовательность {an} сходится, и если сходится, то к чему.


> a1=f(x0)
> a2=f(f(x0))
> a3=f(f(f(x0)))
...
> an=f(f(...n раз...f(x0))..))

Почему ты не используешь общепринятые обозначения для такого процесса?

x0
x1 = f(x0)
x2 = f(x1)
………………
xn = f(xn-1)


> > Вы не могли бы привести пару примеров того, как работает ваша функция функций?
> > Что будет если взять, к примеру, f(x) = 1/х ?

> Пусть у нас есть последовательность:
> a1=f(x0)
> a2=f(f(x0))
> a3=f(f(f(x0)))
> ...
> an=f(f(...n раз...f(x0))..))

> Для f(x)=1/x последовательность {an} расходится.

Если положить x0 = 1, то последовательность имеет вид:

1,1,1,1,1,1,1,...

Она расходится?


> Пусть у нас есть последовательность:
> a1=f(x0)
> a2=f(f(x0))
> a3=f(f(f(x0)))
> ...
> an=f(f(...n раз...f(x0))..))

> Все что меня интересует, это в каких случаях последовательность {an} сходится, и если сходится, то к чему.

Возможно всего 2 варианта: либо последовательность {a[n]} сходится, либо нет :).

В первом случае множество точек, к которым может сходится последовательность {a[n]} исчерпывается множеством действительных корней уравнения f(x)=x, дополненным "точками" "-oo" и "+oo". Проверять эти корни на устойчивость (т.е. выделять области сходимости к ним) - отдельная и сложная проблема. Например, для частного случая какие-то необходимые условия даны к упомянутому Вами методу иетраций поиска корней уравнения.

Во втором случае, последовательность может бесконечно долго "прыгать" по какой-то области, демонстрируя тем самым циклический или "странный" аттрактор. Простейшим примером здесь может служить последовательность вида a[n+1]=(2-a[n])^2, с начальным условием a[0] из отрезка (0,4). Опять же, выделять области сходимости к "аттрактору" - нетривиальная проблема.


> > Пусть у нас есть последовательность:
> > a1=f(x0)
> > a2=f(f(x0))
> > a3=f(f(f(x0)))
> > ...
> > an=f(f(...n раз...f(x0))..))

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

Что такое "аттрактор"?
Циклический "аттрактор"?
"Странный" "аттрактор"?.

Является ли этот термин математическим?
В математических энциклопедиях не нашел.
В энциклопедии общего характера есть:
"Аттрактаннты" - природные или синтетические вещества, привлекающие животных, особенно насекомых.

Уместно ли вводить новые сущности без надобности? (Лезвие....)


> Что такое "аттрактор"?
> Циклический "аттрактор"?
> "Странный" "аттрактор"?.

> Является ли этот термин математическим?
> В математических энциклопедиях не нашел.
> В энциклопедии общего характера есть:
> "Аттрактаннты" - природные или синтетические вещества, привлекающие животных, особенно насекомых.

> Уместно ли вводить новые сущности без надобности? (Лезвие....)

Термин - общепринятый и широко применяемый. Откройте Яндекс.
Пример:

Странный аттрактор


> > Что такое "аттрактор"?
> > Циклический "аттрактор"?
> > "Странный" "аттрактор"?.

> > Является ли этот термин математическим?
> > В математических энциклопедиях не нашел.
> > В энциклопедии общего характера есть:
> > "Аттрактаннты" - природные или синтетические вещества, привлекающие животных, особенно насекомых.

> > Уместно ли вводить новые сущности без надобности? (Лезвие....)

> Термин - общепринятый и широко применяемый. Откройте Яндекс.
> Пример:

> Странный аттрактор


По Яндексу тАкОе можно начитать !!!!
Особенно с учетом того, что он ВСЁ индексирует.
Энциклопедии - это более серъезно. И устоявшееся.
А ссылка ваша вообще отностися к динамическим системам.
Ссылка же про "Аттрактор в фазовом пространстве". В ФАЗОВОМ!
Причем это здесь?
Короче сущность без надобности.




> Что такое "аттрактор"?
> Циклический "аттрактор"?
> "Странный" "аттрактор"?.

См., например,
http://mathworld.wolfram.com/Attractor.html
http://mathworld.wolfram.com/StrangeAttractor.html
http://www.wfu.edu/~petrejh4/Attractor.htm

"Циклического аттрактора", похоже, нет. Вместо него - "предельные циклы" (для консервативных систем).

> Является ли этот термин математическим?

С недавнего времени "да".

> В математических энциклопедиях не нашел.

Наверное, потому, что термин относительно новый, а энциклопедия - старая.

> В энциклопедии общего характера есть:
> "Аттрактаннты" - природные или синтетические вещества, привлекающие животных, особенно насекомых.

Отсюда, видимо, и пошло название - "то к чему "сходится" динамика системы".

> Уместно ли вводить новые сущности без надобности? (Лезвие....)

Нет, не уместно, но термин это уже достаточно устоявшийся...


> > > Что такое "аттрактор"?
> > > Циклический "аттрактор"?
> > > "Странный" "аттрактор"?.

> > > Является ли этот термин математическим?
> > > В математических энциклопедиях не нашел.
> > > В энциклопедии общего характера есть:
> > > "Аттрактаннты" - природные или синтетические вещества, привлекающие животных, особенно насекомых.

> > > Уместно ли вводить новые сущности без надобности? (Лезвие....)

> > Термин - общепринятый и широко применяемый. Откройте Яндекс.
> > Пример:

> > Странный аттрактор

>
> По Яндексу тАкОе можно начитать !!!!
> Особенно с учетом того, что он ВСЁ индексирует.
> Энциклопедии - это более серъезно. И устоявшееся.
> А ссылка ваша вообще отностися к динамическим системам.
> Ссылка же про "Аттрактор в фазовом пространстве". В ФАЗОВОМ!
> Причем это здесь?
> Короче сущность без надобности.

Разве вы не понимаете, что я привел иллюстративную ссылку?
Вот вам попроще и "ближе к телу":

Притягательные арифметические аттракторы

Устроит?


> Пусть у нас есть последовательность:
> a1=f(x0)
> a2=f(f(x0))
> a3=f(f(f(x0)))
> ...
> an=f(f(...n раз...f(x0))..))

Для достаточно регулярных случаев (что значит "регулярный" в данном контексте - сам не знаю) здесь, по-видимо, должна быть аналогия с устойчивостью (по Ляпунову) дифференциальных уравнений вида x'=f(x)-x (с теми же начальными условиями).


> > > > Что такое "аттрактор"?
> > > > Циклический "аттрактор"?
> > > > "Странный" "аттрактор"?.

> > > > Является ли этот термин математическим?
> > > > В математических энциклопедиях не нашел.
> > > > В энциклопедии общего характера есть:
> > > > "Аттрактаннты" - природные или синтетические вещества, привлекающие животных, особенно насекомых.

> > > > Уместно ли вводить новые сущности без надобности? (Лезвие....)

> > > Термин - общепринятый и широко применяемый. Откройте Яндекс.
> > > Пример:

> > > Странный аттрактор

> >
> > По Яндексу тАкОе можно начитать !!!!
> > Особенно с учетом того, что он ВСЁ индексирует.
> > Энциклопедии - это более серъезно. И устоявшееся.
> > А ссылка ваша вообще отностися к динамическим системам.
> > Ссылка же про "Аттрактор в фазовом пространстве". В ФАЗОВОМ!
> > Причем это здесь?
> > Короче сущность без надобности.
>
> Разве вы не понимаете, что я привел иллюстративную ссылку?
> Вот вам попроще и "ближе к телу":

> Притягательные арифметические аттракторы

> Устроит?

Этот материал «ни в какие ворота не лезет».
Чум какой-то.
Обратили внимание. Термин притягивают «за уши». В динамических системах, может быть, и уместно. Хотя увеличение терминов, обозначающих известные сущности, в науке вряд ли полезное направление.


> > Что такое "аттрактор"?
> > Циклический "аттрактор"?
> > "Странный" "аттрактор"?.

> См., например,
> http://mathworld.wolfram.com/Attractor.html
> http://mathworld.wolfram.com/StrangeAttractor.html
> http://www.wfu.edu/~petrejh4/Attractor.htm

> "Циклического аттрактора", похоже, нет. Вместо него - "предельные циклы" (для консервативных систем).

> > Является ли этот термин математическим?

> С недавнего времени "да".

> > В математических энциклопедиях не нашел.

> Наверное, потому, что термин относительно новый, а энциклопедия - старая.

> > В энциклопедии общего характера есть:
> > "Аттрактаннты" - природные или синтетические вещества, привлекающие животных, особенно насекомых.

> Отсюда, видимо, и пошло название - "то к чему "сходится" динамика системы".

> > Уместно ли вводить новые сущности без надобности? (Лезвие....)

> Нет, не уместно, но термин это уже достаточно устоявшийся...

Но к рассматриваемой теме какое отношение этот термин имеет?


> > Пусть у нас есть последовательность:
> > a1=f(x0)
> > a2=f(f(x0))
> > a3=f(f(f(x0)))
> > ...
> > an=f(f(...n раз...f(x0))..))

> Для достаточно регулярных случаев (что значит "регулярный" в данном контексте - сам не знаю) здесь, по-видимо, должна быть аналогия с устойчивостью (по Ляпунову) дифференциальных уравнений вида x'=f(x)-x (с теми же начальными условиями).

Уже про всё поговорили, только о классическом принципе пока нет.
Причем здесь Ляпунов и дифуры?


> Но к рассматриваемой теме какое отношение этот термин имеет?

Самое прямое. Понятие аттрактора используется как для непрерывных, так и для дискретных динамических систем (см., например, http://www.cecm.sfu.ca/publications/organic/confrac/node5.html).
Вообще давайте лучше свои усилия направим собственно на вопрос, а не на обсуждение используемой (введенной и принятой не нами) терминологии.

> Уже про всё поговорили, только о классическом принципе пока нет. Причем здесь Ляпунов и дифуры?

Это всего лишь догадка, возможно неверная. Просто исследуемое дискретное отображение есть, по-существу, численное решение дифура x'=f(x)-x методом Эйлера. При определенных условиях, накладываемых на f их свойства должны быть близки.


Простейший способ выяснения вопроса об устойчивости стационарной точки может быть следующим.
Пусть x* - какой-то корень уравнения x*=f(x*). Рассмотрим поведение последовательности a[n] в окрестности x*. Полагаем a[n]=x*+e.
Тогда a[n+1] = f(x*+e) = f(x*)+e*f'(x*)+o(e) = x*+e*f'(x*)+o(e). Пренебрегая o(e), получаем, что abs(a[n+1]-x*) < abs(a[n]-x*), то есть последовательность сходится к x*, если abs(f'(x*)) < 1. Соответственно, это неустойчивая точка, если > 1. Если =1, то надо привлекать бесконечно малые более высокого порядка.

Аналогично, если имеется цикл вида a[n]=a[n+k] c соответствующими стационарными точками x*[1],...,x*[k], то стабильность цикла определяется неравенством abs(f'(x*[1]),...,f'(x*[k])) < 1.


> Простейший способ выяснения вопроса об устойчивости стационарной точки может быть следующим.

Мне представляется, что в данной теме речь идет о неподвижной точке отображения: x = f(x).
Про какую стационарность упомянули Вы?


> Мне представляется, что в данной теме речь идет о неподвижной точке отображения: x = f(x).
> Про какую стационарность упомянули Вы?

Вы совершенно правы, спасибо, всюду прилагательное "стационарная" следует заменить на "неподвижная".


> Короче сущность без надобности.

Вообще-то:

Оккам (Ockham, Occam) Уильям (около 1285, Оккам, графство Суррей, - 1349, Мюнхен), английский философ, логик и церковно-политический писатель, представитель поздней схоластики. Монах-францисканец. Учился и преподавал в Оксфорде. В 1323 в связи с обвинением в ереси был вызван папой Иоанном XXII в Авиньон, где находился в течение 4 лет. Активно поддерживал главу францисканского ордена Михаила из Цезены в его споре с папой. С 1328 жил в Мюнхене при дворе противника папы императора Людвига Баварского, которому О., по преданию, сказал: "Защищай меня мечом, а я буду защищать тебя пером". Как политический писатель О. выступал против претензий папы на светскую власть, против абсолютизма церковной и светской власти; отстаивал принцип "евангелической бедности", предвосхитив во многом идеи Реформации. О. был главным представителем номинализма 14 в. Считая, что реальным существованием обладают только единичные субстанции и их абсолютные свойства, О. полагал, что вне мышления т. н. универсалии суть только имена, термины, обозначающие классы имён: термины первой и второй интенции. Терминам первой интенции соответствуют науки "реальные" (о реальных предметах), терминам второй интенции - "рациональные" (логика, грамматика и т.п.). О. был одним из крупнейших логиков средневековья (см. Логика, раздел История логики). В частности, ему принадлежит идея о том, что значение термина всецело определяется его функцией в высказывании; в разработанной им теории консеквенции он фактически различал материальную и формальную импликацию, сформулировал двойственности принцип для конъюнкции и дизъюнкции. Первичным познанием, по О., является интуитивное, которое включает внешние восприятия и интроспекцию. Понятия, не сводимые к интуитивному знанию и не поддающиеся проверке в опыте, должны быть удалены из науки: "сущности не следует умножать без необходимости". Этот принцип, получивший название "бритвы О.", сыграл важную роль в борьбе против средне-векового реализма, теории "скрытых качеств" и т.п. Считая, что между единичными субстанциями не может существовать необходимой связи, О. ограничивал применение понятия причинности сферой эмпирических констатаций. О. выступал за разделение сфер философии и теологии (см. Двойственная истина), догматы религии - сверхразумные предписания, относящиеся не к разуму, а к вере и воле. Причём воле О., как и Иоанн Дунс Скот, отдавал приоритет перед разумом. О. оказал значительное влияние на последующее развитие логики и философии, особенно на Ж. Буридана, Николая из Отрекура и Т. Гоббса.

Соч.: Opera philosophica et theologica, ed. S. Brown, v. 1-2, St. Bonaventura (N. Y.), 1967-70; Opera politica. Accuraverunt J. G. Síkes, R. F. Bennett, H. S. Offler, v. 1-3, Manchester, 1940-63-.

Лит.: Abbagnano N., Guglieimo di Ockham, Lanciano, [1931];, Hochstetteг E., Studien zur Metaphysik und Erkenntnislehre W. von Ockham, B. - Lpz., 1927; Martin G., W. v. Ockham, B., 1949; Baudry L., Guillaume d"Occam. Sa vie, ses oeuvres, ses idées sociales et politiques, v. 1, P., 1949 (имеется лит.); Moody E. A., The logic of William of Ockham, N. Y., 1965.

Г. Г. Майоров.


Материалы предоставлены проектом Рубрикон © 2001 Russ Portal Company Ltd.
© 2001 "Большая Российская энциклопедия"
Все права защищены


Оккам


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100