Поворот на клетчатом листе

[VoloCh]

Circiter Не, ну код был у меня на предпред...предыдущем компе. Но чего тут делать то?
Ну типа такого:
while not keypressed do
begin
x1=round(x*cos(a)-y*sin(a));
y1=round(x*sin(a)+y*cos(a));
{ставим на экране точку (x1,y1)};
x=x1;y=y1;
end;
Округление нужной функцией: round, или int, или что еще...
Поиграйтесь разными углами "a" и начальной точкой (0,R).
Ну, и главное... это масштаб.
Интересны, конечно, случаи больших радиусов (большИх R), а не малых.

И вообще, я тоже уже не понял: не понял, что именно вы не поняли? Вам непонятно почему это "проблема"? Или почему она интересная? Или почему ее не решили? Или все же условие не ясно?

[gris]

Ув. VoloCh, я проделывал вычисления в Excel, пользуясь функцией ROUND(A;0), это округление до ближайшего целого. Просто строил таблицу координат очередной точки. Контролировал положение точки в полярных координатах, то есть радиус и угол.
В результате серии расчётов получено, что при больших значениях радиуса для большинства углов не происходит значительного изменения радиуса точки. Однако, существуют углы, при которых это изменение достигает существенных значений.
Вопрос. В чём состоит задача? Что надо проверить или отыскать?

[VoloCh]

gris в сообщении #301204 писал(а):

Однако, существуют углы, при которых это изменение достигает существенных значений. Вопрос. В чём состоит задача? Что надо проверить или отыскать?

Ув. gris! Посмотрите еще раз стартовый топик. Задача состоит в том, чтобы доказать (или проверить, если угодно), что никакая траектория не уйдет в бесконечность или построить контрпример, то есть отыскать (как вы выразились) начальную точку и угол, при котором траектория будет неограниченной.
Да, может, это очевидно и я чего-то не вижу из своего "Тамбова"...

[gris]

Ясно. Тогда расчёты на ординаторе не имеют смысла. Ибо видно, что почти всегда траектория зацикливается. А если удастся обнаружить нечто подобное резонансу, то его нельзя будет довести до контрпримера из-за конечной точности расчётов.

[VoloCh]

gris в сообщении #301217 писал(а):

...видно, что почти всегда траектория зацикливается.

Скажу больше: это утверждение доказано. Правда, чтобы объяснить что такое "почти всегда" на целочисленной решетке придецца писать многабукав.

gris в сообщении #301217 писал(а):

...нельзя будет довести до контрпримера из-за конечной точности расчётов

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

[gris]

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

[VoloCh]

gris в сообщении #301246 писал(а):

Запустил анимацию.... Занятное зрелище...

Ну, ваше наблюдение - это исходный посыл сформулированной гипотезы. А вот насчет анимации - попробуйте теперь на каждом шаге поворота случайно ошибаться в угле (это уже другая задача!). То есть, на каждом шаге замените $\alpha$ на $\alpha_n$, так что $|\alpha-\alpha_n|$ случайное, но ну оооооооочень маленькое )))

[gris]

А вуглускре и так идёт постоянная ошибка из-за машинного округления при вычислении синуса и косинуса. Я, собственно, это и имел в виду ранее.

[VoloCh]

gris в сообщении #301263 писал(а):

... и так идёт постоянная ошибка из-за машинного округления при вычислении синуса и косинуса. Я, собственно, это и имел в виду ранее.

если ошибка в вычислении (ко)синуса не дает ошибку в округлении (то есть если мы попадаем в тот же целочисленный квадратик), то это не то же самое, что ошибицца в значении угла!

[gris]

Ну можно так рассуждать. Каждое значение угла разбивает множество $\mathbb{N}^2$ на непересекающиеся классы эквивалентности.
(Тут есть одна тонкость. Некоторые переходы от точки к точке необратимы. И на самом деле разбиение идёт на порождённые множества, а они пересекаются. Вот объединение пересекающихся порождённых множеств и образует класс эквивалентности).
Мы предполагаем, что все классы конечны. Мы можем даже упорядочить классы по числу элементов, хотя это лишь приблизительно отражает идею о "разворачивании спирали". Но тем не менее. Если мы будем непрерывно изменять угол, то увидим, что классы тоже меняются, естественно скачками. При этом мы должны следить за миграцией чисел по классам в сторону увеличения численности класса. В новом классе надо выбрать число, которое мигрирует в следующий класс при некотором изменении угла на некоторую величину.
Мне кажется, что с начиная с некоторой численности класса можно так подобрать последовательность углов и точек, в которых угол изменяется, чтобы она сходилась к первоначальному углу при максимальном отклонении от него не больше заданной величины и чтобы начальная точка мигрировала в неограниченно возрастающий по численности класс.
Подобная задача рассматривается в теории цирциттеровых множеств. Только там рассматривается непрерывный случай. Ну тоже разбиение плоскости или пространства на цирциттеровы классы с определяющей функцией, порождающими точками, точками бифуркации, миграцией слоёв и подобными умными вещами, в которых я слабовато разбираюсь. Делал что-то типа анимации для весьма частных случаев.

[VoloCh]

gris в сообщении #301291 писал(а):

Ну можно так рассуждать. Каждое значение угла разбивает множество $\mathbb{N}^2$ на непересекающиеся классы эквивалентности. Мы предполагаем, что все классы конечны.

Почему это?

gris в сообщении #301291 писал(а):

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

Чтобясдох - ничего не понял! Вы вообще рассуждаете куда? Какое утверждение вы пытаетесь доказать (или проиллюстрировать, или указать путь к решению...) ?

gris в сообщении #301291 писал(а):

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

Кто она сходилась? Можно это утверждение как-то поточнее сформулировать? Что дано? Что предполагается? Что утверждается?

gris в сообщении #301291 писал(а):

Подобная задача рассматривается в теории цирциттеровых множеств.

Очень интересно! Что за задача? Что за множества? Почему она "подобная"?
Дяденька, пощадите, проясните неразумному!

[gris]

Вообще возможность шевелить угол поворота переводит задачу совершенно в другой разряд. Если не сочтёте за оффтоп, то я могу несколько слов сказать, только завтра, а то уже ложусь спать. В двух словах. Имеется счётное множество состояний объекта ( в Вашем случае это точки). Имеется некоторая функция перехода из одного состояния в другое. В общем случае это матрица вероятностей. В частном это просто функция $m=F(n,t)$, где $t$ некоторый управляющий параметр. В Вашем случае, это значение угла поворота. Мы можем применять эту функцию к объекту много раз, при этом в нужный момент изменять управляющий параметр. Это изменение возможно только в определённых пределах и скажем так дорогостояще. Задача: за минимальное число шагов перевести объект из одного состояния в другое при некоторых ограничениях на изменение управляющего параметра. Относительно $t$ функция кусочно-постоянна (и "куски" достаточно длинные), прямо как у Вас.

[VoloCh]

gris, да, теперь понятны ваши ассоциации. Только у вас все же оптимизационная задача. А у меня совсем другое. Но, так как я ложусь спать сильно позже, то расскажу почему я обмолвился про "шевеление углом".

Дело в том, что поворот вещь весьма "неустойчивая". Вспомните классическую систему $x''=-x$. Чуть "дернешься" - окажешься либо в нуле, либо в бесконечности. Так вот и тут вопрос: "округление" сдергивает нас с цикла или нет? А то, что вопрос тут "на тоненького" видно из того, что система может уйти в бесконечность при бесконечном малом шевелении угла. А именно: $\forall \varepsilon>0$ найдется такое начало $x_0\in\mathbb Z^2$, угол $\alpha$ и последовательность $\alpha(n)$, что, во-первых, $|\alpha(n)-\alpha|<\varepsilon$ и, во-вторых, последовательность $x_n=P(F_{\alpha(n)}(x_{n-1}))$ неограничена. Тут, как в заглавном посте $P\text{ ---}$ оператор округления, $F\text{ ---}$ оператор поворота.

[Circiter]

2VoloCh

Цитата:

И вообще, я тоже уже не понял: не понял, что именно вы не поняли? Вам непонятно почему это "проблема"? Или почему она интересная? Или почему ее не решили? Или все же условие не ясно?

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

Цитата:

Ну, и главное... это масштаб.
Интересны, конечно, случаи больших радиусов (большИх R), а не малых.

Ok, поэкспериментирую с большими радиусами и разными масштабами.

Цитата:

А именно: $\forall \varepsilon>0$ найдется такое начало $x_0\in\mathbb Z^2$, угол $\alpha$ и последовательность $\alpha(n)$, что, во-первых, $|\alpha(n)-\alpha|<\varepsilon$ и, во-вторых, последовательность $x_n=P(F_{\alpha(n)}(x_{n-1}))$ неограничена.

Кажется, достаточно слегка уменьшать угол на каждой итерации. Или я опять ошибаюсь?

Мне кажется, ваша система (итерирование композиции поворота и округления) похожа на этакий двумерный детерминированный ГПСЧ. Принцип тот-же, линейное преобразование "по-модулю" (cf. линейный конгруэнтный метод). А как известно, любой такой ГПСЧ зацикливается .

2gris

Цитата:

Занятное зрелище

Раз уж вам удалось увидеть нетривиальность динамики, то не могли бы вы поделиться подходящими параметрами, чтобы я мог повторить эксперимент? Интересуют начальные координаты, угол, точность, способ округления... Заранее благодарю.

[gris]

Вчера долго ворочался и думал о задаче.
И вот именно, что о неустойчивости. Одно дело, когда малое шевеление начальных условий приводит к большому отклонению на расстоянии. Другое, когда шевеление управляющего параметра (угла) неравнозначно по своему воздействию, причём это воздействие возрастает неограниченно.
При малых радиусах поворот на миллионную долю радиана оставляет все точки на месте. А при радиусе в один миллион переводит точку в соседнюю. При радиусе десять миллионов вообще выводит за пределы цета. Поэтому говорить о компьютерной проверке бессмысленно. Никакой точности не хватит.

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

И тут меня просто молнией поразило. Состояние объекта характеризуется величиной, обратной радиусу! Ну Вы и мистификатор! А я думаю, чего это circitter так заинтересовался задачей. Теперь всё встаёт на свои места. Я совершенно согласен, что замена переменной на обратную позволяет вместо изучения поведения объекта вблизи нуля рассматривать его поведение на бесконечности. Тогда мы не должны озабочиваться переходом точки в бесконечность. Достаточно перевести на расстояние $10^{12}-10^{15}$, хотя если это имеет отношение к теории струн, то там сами понимаете, что будет.

В общем, я так решал так. Подставил Ваши формулы в процедуру подсчёта цетов, то есть тех самых классов эквивалентности. Посчитал все цеты до радиуса в 10 тысяч для угла 0,2 радиан. Посчитал цеты для углов от 0,19 радиан до 0,21 радиан с шагом 0,0001. Определил точки бифуркации. И пожалуйста - точка $(60;0)$ за 1244805 шагов мигрировала в точку $(9454;12)$ при 8393 изменениях угла на величину не более $4/R$ радиана и конечной величине угла 0,200082 радиана.

Проблема заключается в том, что мощность цетов возрастает пропорционально квадрату радиуса и при возрастании радиуса объём массивов и время поиска точек бифуркации возрастает катастрофически. Тут уже нужны какие-то системные компьютерные методы, чем я не владею.

Возможно и вероятно и даже наверняка мой метод слишком доморощен и прямолинеен. Ну, как говорится, чем богаты. Ещё раз повторю идею. Для начальной точки и начального угла строим множество порождённых точек, то есть тех точек, которые получаются при многократном повторении поворота. Не всегда циклическая траектория содержит начальную точку. Строим аналогичное множества для близких углов, порождённые всеми точками предыдущего цета (прошу прощения, я так привык к этой терминологии, мне кажется, так проще). Определяем точки бифуркации. То есть точки первоначального множества, где изменение угла приводит к переводу точки уже в другой цет. Теперь аналогичные расчёты проводим для новой точки и нового угла. Ну и так далее в цикле, до миграции начальной точки на необходимый радиус. Контролируя величину изменения угла так, чтобы он стремился к первоначальной величине. Можно вручную продемонстрировать в том же excel, то есть уж совсем по рабоче-крестьянски.

Прошу прощения за многословие, но на любимую тему готов говорить часами. Хотя в присутствии подлинных знатоков теории несколько робею.