[d | au / b / bro / ci / cu / dev / hr / l / m / mi / mu / o / ph / r / s / sci / tran / tu / tv / vg / x | a / aa / c / fi / jp / rm / tan / to / ts / vn / vo]
- [Радио 410] [ii.booru-Архив РПГ] [acomics-cf-ost] [@] - [Архив - Каталог] [Главная]

[Назад]
Ответ
Безымянный123.JPG - (12 KB, 455x417)  
12 KB №23223   #1

Есть здесь те кто может смоделировать эту задачу на
компе?

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

Вопрос: удастся кому нибудь из них догнать таким образом
того, кто идет впереди?

>> №23225   #2

Может быть я дибил, но время на один цикл будет для всех участников одинаковым -> не взлетит

>> №23226   #3

>>23225

>После того как один из них достигает другой

вершины каждый из них меняет скорость

>один...каждый
>> №23228   #4

Нет, не удастся.
Биолололог-кун, смотрящий фурикури.

>> №23229   #5

Я могу это смоделировать, но не вижу смысла.

>> №23230   #6

А её разве не предполагается высчитать аналитически?

лень думать над задачей-кун

>> №23231   #7

Каждый оббегает 3 стороны со средней скоростью (17+16+15)/3 км/ч.

/Thread

>> №23232   #8

>>23231

Лолнет, смотри >>23226.

>> №23238   #9

>>23232
ОК.

>> №23239   #10
1.png - (13 KB, 650x389)  
13 KB

Промоделировал на досуге. За 1 000 000 итераций (одна итерация - одно достижение бегуном вершины) никто впереди идущего так и не нагнал.

Исходники не выложу по трём причинам, во-первых мне стыдно за написанный быдлокод (а что вы хотели? для меня главное посмотреть было), во-вторых дабы не провоцировать новые подобные реквесты и в-третьих, в случае если это какая-то лаба, дабы не поддерживать расп*здяя.

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

>> №23241   #11

>>23239
Я подозревал, что ответ нет. Это замечательно, теперь ясно
что задача лежит в аналитической плоскости: если уж
за 1000000 "итераций" никто никого не догнал, то и за
бесконечность никто никого не догонит. Вопрос только лишь в
том, какой раздел высшей математики поможет это доказать.
Можно ли это доказать отталкиваясь от школьных знаний?

>> №23242   #12

>>23241
Думаю, тут либо надо смотреть в сторону рядов, либо искать периодичность.

>> №23249   #13

Я не понял, в чем собственно проблема?
Первый спортсмэн пробежит круг за:
17/16 + 16/15 + 15/17
Второй за
16/15 + 15/17 + 17/16
Третий за
15/17 + 17/16 + 16/15

"Периодичность" улавливаете?

>> №23250   #14
>Я не понял, в чем собственно проблема?

Именно что не понял.
Обрати внимание - спортсмены меняют скорость, причём не только в вершинах.

>> №23251   #15

>>23250
это ты только что придумал

>> №23253   #16

>>23251
Прочитай условие, подумай, затем снова прочитай условие, потом снова подумай и наконец обрати внимание на фразу:

>После того как один из них достигает другой вершины каждый из них меняет скорость движения

крокодил

>> №23262   #17

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

>> №23263   #18

>>23262
трава уходи

>> №23264   #19

>>23262 Прочитай обсуждение, а?

>> №23267   #20

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

Я продвинулся немного дальше: если понаблюдать за результатами моделирования, а потом составить пару простых уравнений, становится очевидно, что у задачи есть предельный цикл из 9 шагов. Несложно (хотя и немного муторно, т.к. 9 шагов и числа страшные) показать, что этот цикл устойчивый.

Тем самым, если положение бегунов приблизится к этому предельному циклу, бегуны гарантированно никогда друг друга не догонят.

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

Численная модель показывает, что задача действительно к нему сходится, но это не доказательство, конечно.
Вот сам предельный цикл (I - номер участка, V - скорость, d - расстояние до следующей точки (точное и численное) )
#0 [I=0, V=17, d = 404863690/40922929 = 9.89332141890430] [I=0, V=16, d = 528443872/122768787 = 4.30438293733406] [I=2, V=15, d = 16 = 16.0000000000000]
#1 [I=0, V=16, d = 653119456/122768787 = 5.31991454798686] [I=1, V=15, d = 17 = 17.0000000000000] [I=2, V=17, d = 489628154/40922929 = 11.9646409962493]
#2 [I=1, V=15, d = 17 = 17.0000000000000] [I=1, V=17, d = 491589963/40922929 = 12.0125801112623] [I=2, V=16, d = 774945040/122768787 = 6.31223178901328]
#3 [I=1, V=17, d = 453519468/40922929 = 11.0822826978001] [I=1, V=16, d = 651390784/122768787 = 5.30583383543571] [I=0, V=15, d = 15 = 15.0000000000000]
#4 [I=1, V=16, d = 668455696/122768787 = 5.44483424764961] [I=2, V=15, d = 16 = 16.0000000000000] [I=0, V=17, d = 410284315/40922929 = 10.0257807792790]
#5 [I=2, V=15, d = 16 = 16.0000000000000] [I=2, V=17, d = 445874459/40922929 = 10.8954678928285] [I=0, V=16, d = 520618768/122768787 = 4.24064439115131]
#6 [I=2, V=17, d = 492073499/40922929 = 12.0243958832956] [I=2, V=16, d = 784465936/122768787 = 6.38978322723022] [I=1, V=15, d = 17 = 17.0000000000000]
#7 [I=2, V=16, d = 642725440/122768787 = 5.23525120436353] [I=0, V=15, d = 15 = 15.0000000000000] [I=1, V=17, d = 450544188/40922929 = 11.0095782244717]
#8 [I=0, V=15, d = 15 = 15.0000000000000] [I=0, V=17, d = 412992235/40922929 = 10.0919519959092] [I=1, V=16, d = 668736784/122768787 = 5.44712381983541]
#9 [I=0, V=17, d = 404863690/40922929 = 9.89332141890430] [I=0, V=16, d = 528443872/122768787 = 4.30438293733406] [I=2, V=15, d = 16 = 16.0000000000000]

>> №23270   #21

>>23267
В случае если есть устойчивый цикл (блин, что же я о нём то сразу не подумал?), то первый шаг в доказательстве это показать, что малое отклонение от него, приводит к возврату к этому циклу, т.е. имеется некий аналог устойчивого равновесия.
Плюс почему-то моя интуиция мне почему-то напоминает про вариационный принцип...

инб4 капитан

23239-кун

>> №23272   #22

>>23270
Да доказать устойчивость этого цикла легко, только числа неудобные. Тут-то всё просто.
Сложнее доказать, что из исходных условий система приходит именно к этому циклу. (хотя численная проверка показывает, что это так)

>> №23274   #23

>>23272
Тогда оно с неизбежностью выйдет на этот цикл (или на любой другой), так что проблема тогда доказать, что при этом не выполниться условие обгона.

>> №23275   #24

В общем, используя сказанное выше про предельный цикл, шаблон доказательства может быть таким:
1) Доказать, тчо предельный цикл учтойчив (вполне тривиально, но громоздко)
2) Найти какую-нибудь окрестность этого цикла, для которой гарантировано, что, начиная из неё, мы придём к этому циклу. Это опять же сделать принципиально несложно - нужно заменить расстояния переменными и записать условия того, что бегуны достигают вершин именно в той последовательности, в какой они достигают вершины в предельном случае. Это даст систему линейных неравенств.
3) Взять исходные начальные условия и точно (без округлений) промоделировать систему до тех пор, пока она не попадёт в область, найденную на шаге 2. Если она туда попадёт (а она попадёт, как показывает численная проверка), и если по пути бегуны ни разу не столкнутся, то они гарантированно не столкнутся никогда.

Но это доказательство, хотя и достаточно универсальное - ужасно громоздкое.

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

>> №23276   #25

Такой вброс -- а если пойти от обратного:

  1. кто-то кого-то таки догнал
  2. инвертируем время
  3. ?????
  4. PROFIT

На доработку п.3. времени сейчас нет ужизвините...

>> №23278   #26

>>23275
Может стоит подумать в направлении введения какого-то одного объекта, вместо трёх бегунов? Т.е. например аналитически вычислить результаты цикла для всех возможных начальных данных, т.е. результатом этой многомерной функции будет начальные данные для следующей итерации и флаг произошёл обгон или нет. Думаю с таким объектом будет полегче обращаться.

>> №23279   #27

Тупые перельманы, бля, теорему синусов не знают.

>> №23280   #28

>>23274

>Тогда оно с неизбежностью выйдет на этот цикл (или на любой другой),

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

>> №23281   #29

>>23276
Проблема в том, что ситуаций обгона вообще говоря бесконечное количество и это уже не говоря о том, что нужно показать, что ниодно из этих условий при обращении времени не прийдёт в начальные условия.
Видиться мне, что это наоборот на порядок усложнит решение.
>>23279
просто уходи

>> №23282   #30

>>23280
Из результатов численного моделирования следует, что цикл устойчив к малому изменению входных данных (и если верить >>23272-куну доказать это несложно), а значит единожды попав туда мы оттуда не вылезем. Единственный контрпример, что из начальных данных мы в эту область никогда не попадём, это как раз таки и нужно опровергнуть.

>> №23284   #31

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

>> №23285   #32

>>23284
Читай >>23267
@
хватит постить х*йню

>> №23287   #33

>>23285
Во-первых: я прочитал >>23267 и понял, что никто не сказал
Во-вторых: хочу и пощу хуйню
В-третьих: я хуйню не пощу
В-четртых: я вообще мимо проходил

>> №23288   #34

>>23287
Как написал >>23267 всё свалится к циклу, а т.к. мы считали на машине, то значит этот цикл устойчив, а значит в некоторой области этого цикла никакого динамического хаоса не существует.
Другой вопрос насколько велика эта область и что б ответить на него надо неплохо подумать...

>> №23328   #35

>>23288
задача для 11-классника.

>мы считали на машине
>надо неплохо подумать

мозги прут из всех щелей.

>> №23329   #36

>>23328
Ну так реши, кто же тебе мешает, мудаёбенький ты наш?

>> №23330   #37

>>23329
что это ты о себе во множественном числе пишешь? векторное расслоение личности?

>> №23331   #38
1266665072642.jpg - (132 KB, 480x546)  
132 KB

Доказательство устойчивости приведенного в >>23267 цикла действительно тривиально.

Возьмём начальное состояние, и внесём в него малые искажения:
[I=0, V=17, d = 404863690/40922929 + a] [I=0, V=16, d = 528443872/122768787 + b] [I=2, V=15, d = 16]

где |a| << 1, |b| << 1 (Другими словами, будем считать эти искажения достаточно малыми, чтобы не влиять на порядок достижения бегунами вершин).
ТОогжа после 9 итераций (тут много рассчётов, спасибо sympy) положения бегунов станут:

['[I=0, V=17, d = 404863690/40922929 - 29297782815*b/68719476736 + 3834008895*a/4294967296]', '[I=0, V=16, d = 528443872/122768787 + 1953185521*a/4294967296 + 28139988463*b/68719476736]', '[I=2, V=15, d = 16]']

То есть, новые отклонения равны:
a1 = 29297782815*b/68719476736 + 3834008895*a/4294967296
b1 = 1953185521*a/4294967296 + 28139988463*b/68719476736

Ну а так как собственные числа матрицы
[3834008895/4294967296, -29297782815/68719476736]
[28139988463/68719476736, 1953185521/4294967296]
по модулю меньше 1, отсюда следует, что при многократном повторении итераций отклонение будет экспоненциально стремиться к нулю.

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

>> №23332   #39
o tempora 1.jpg - (48 KB, 350x271)  
48 KB

>>23331
И это называется аналитическое доказательство? Пик тотали релейтед. (ибо это всё равно что заявить, что задача решена, т.к. проведено её моделирование на машине)
Алсо, даже если принять это так, то это не есть решение же, только его часть.
>>23330
С теми, кто не понимает русского языка и даже не умеет читать, общаться - бесполезно.
Правило жизни
Хинт задачу моделировало два человека, один из них я.

>> №23333   #40

А я и не говорю, что это решение всей задачи.
Это не доказательство всей задачи, а доказательство устойчивости найденного предельного цикла. И оно вполне аналитическое - все вычисления производятся точно, благо что числа рациональные.
Если я выпишу сюда 9 шагов рассчётов с 10-значными числами, что-то изменится?
Нужно как-бы понимать разницу между численным моделированием, где числа с плавающей запятой и округление н а каждом шаге, и символьной математикой, где всё точно.

Чтобы получить таким образом решение всей задачи надо определить область сходимости, и показать, что на определённом шаге система попадает в эту область.

Но это дохуя рассчётов с здоровыми 8-9 значными целыми числами. Даже с калькулятором всё это провернуть сложно. Я не верю, что авторы задачи рассчитывали на такое решение.

Хинт: а я как раз и есть второй

>> №23334   #41

>>23333
По тому как ты записывал бегунов, я и так понял, что ты второй :3
Насчёт доказательства, да, поспешил, твоя правда.

>> №23379   #42
340153.jpg - (70 KB, 295x249)  
70 KB
> аналитический метод
> на калькуляторе
>> №23384   #43

>>23379
Батюшка признаёт только на бумажке в столбик?

>> №23386   #44

>>23384
Мудоебина совершенное не отличает численную модель от аналитической.

>> №23389   #45

>>23386
Если в аналитической модели присутствуют числа вроде 404863690/40922929, мудоёбина всё равно не хочет пользоваться калькулятором и считает в столбик?

>> №23390   #46

>>23389
Если калькулятор округляет, мудоебина будет считать в столбик.
%/R смену имени на мудоебина%

>> №23391   #47
Maple13_logo.jpg - (22 KB, 193x46)  
22 KB

>>23389>>23390

>> №24965   #48
logo.png - (6 KB, 85x55)  
6 KB

>>23391
>>23331

>sympy
>> №24967   #49

лень читать что написали до меня но очевидно следующее:

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

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

>> №24968   #50

>>24967

>лень читать что написали до меня но очевидно следующее:

Признайся, ты просто не умеешь.

>находясь на 1-ом отрезке спортсмены движутся с одинаковой скоростью

Спортсмены всегда движутся с разными скоростями. Это следует из условия задачи.
Дальше не читал, извини.

>> №26176   #51

олдбамп

>> №28053   #52

Внезапно бамп.

>> №28062   #53
runners.png - (33 KB, 1280x975)  
33 KB

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

>> №28063   #54

>>28062 >>23267

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

>> №28086   #55

>>28063

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

Бро, а поясни насчет "составить пару простых уравнений".
Дело в том, что когда я беру в качестве начальных условий значения из твоего цикла, например

> #0 [I=0, V=17, d = 404863690/40922929] [I=0, V=16, d = 528443872/122768787] [I=2, V=15, d = 16]

то у меня тоже все прекрасно зацикливается и вообще все значения совпадают - то есть не похоже, что моя модель чем-то хуже твоей.
Но когда я подставляю в нее [I = 0, d = 15, v = 17] [I = 1, d = 17, v = 16] [I = 2, d = 16, v = 15], то система в этот цикл не попадает - и вообще ни в какой не попадает, как я уже говорил выше. Что, в общем-то вполне логично, поскольку в этой системе вполне можно обращать время, поэтому раз из цикла нет выхода, то в него нет и входа.
Правильно ли я понимаю, что в твоей "паре простых уравнений" начальные условия задачи никак не учитывались?

>> №28093   #56

>>28086
Ох, восстановил своё старое решение и обнаружил, что я, похоже, ошибся.
То есть решение, которое я показал в >>23267 - действительно устойчивый цикл, только из заданных начальных условий задача к нему не сходится. Похоже, я тогда что-то перепутал, или взял слишком низкую точность.
Правильный цикл начинается с
1): V=15, L=15, d=1735289213/179244147 ~~ 9.68115
2): V=17, L=15, d=821285249/179244147 ~~ 4.58194
3): V=16, L=16, d=16 ~~ 16

То есть, у этой задачи много различных устойчивых циклов.

>то есть не похоже, что моя модель чем-то хуже твоей.

Ты, как мне подсказывает libastral, производишь моделирование,пользуясь числами с плавающей запятой.
Поэтому то, что ты нашёл, с математической точки зрения является только некоторым приближением к решению.

В отличие от твоего, моё решение - точное. Оно найдено в рациональных числах (а значения с запятой приведены просто для оценки). Правда, первый раз я нашёл не то решение.

Ход решения у меня был довольно простой

1) Пользуясь числами с плавающей запятой, численно промоделировать задачу до тех пор, пока не будет достигнут цикл с некоторой достаточной точностью (я сейчас брал 1е-6, но для 1e-40 ответ получается тот же). У меня получилось, что точность 1e-6 достигается на 521-м шаге.

2) Найти точно (символьно) параметры цикла. Для этого:
2.0) Взять какое-нибудь состояние, которое близко к циклу. В нём часть параметров целочисленные и известны точно, а часть - приближения.
2.1) Заменить неизвестные параметры (оставшиеся расстояния) буквами. То есть, ввести переменные d_1, d_2, d_3.
2.2) Провести 9 шагов моделирования, производя все вычисления символьно.
На этом шаге возникает проблема: нужно сравнивать выражения, содержащие неизвестные величины d_1, d_2, d_3.
Я применил такой подход: при сравнении (и только при нём), в переменные подставляются их приближённые численные значения, найденные на шаге моделирования (1).
Естественно, после подстановки значения станут приближёнными, но (можно надеяться, что) на результат сравнения это не повлияет.
2.3) После 9 шагов новые положения бегунов будут выражены через исходные.
2.4) Остаётся приравнять новые положения старым, и найти значения переменных d_1, d_2, d_3, решив получившуюся систему уравнений.

Я восстановил скрипт, и он выдал мне такое:

==== Step N ====

1): V=d_1, L=15, d=d_1
2): V=d_2, L=15, d=d_2
3): V=d_3, L=16, d=d_3

==== Step N+9 ====

1): V=15, L=15, d=24112543/1419857 - 356726032*d_3/410338673 + 3537607920*d_1/6975757441 + 43965361904*d_2/118587876497
2): V=17, L=15, d=18600801/1419857 - 2747835119*d_1/6975757441 - 221100495*d_3/410338673 + 101356861425*d_2/118587876497
3): V=16, L=16, d=16

(заметь, тут всё точно, нет никакой плавающей запятой)

Осталось найти такие значения v_1, v_2, v_3, чтобы цикл замкнулся.
Для этого нужно решить систему из 3 (реально 2) линейных уравнений:

d_1 = 24112543/1419857 - 356726032*d_3/410338673 + 3537607920*d_1/6975757441 + 43965361904*d_2/118587876497
d_2 = 18600801/1419857 - 2747835119*d_1/6975757441 - 221100495*d_3/410338673 + 101356861425*d_2/118587876497
d_3 = 16

Решение:

d_3 = 16
d_2 = 821285249/179244147
d_1 = 1735289213/179244147

Можно проверить, что это решение обеспечивает точное повторение цикла.

То есть, по сути, из численного решения я взял только информацию о том, в каком порядке каждый из бегунов пересекает границы, а сами положения бегунов нашёл аналитически.
На всякий случай я убедился, что найденные аналитически положения бегунов действительно достаточно близки к использованным численным приближениям:
==== Compare symbolic solutions with initial approximation ====

d_1:  Numeric: 9.68115	Symbolic: 1735289213/179244147	Difference: -1.25589e-06
d_2: Numeric: 4.58193 Symbolic: 821285249/179244147 Difference: -1.35126e-06
d_3: Numeric: 16 Symbolic: 16 Difference: 0

Т.е. всё ОК.

Ещё я на всякий случай провёл моделирование исходной задачи с повышенной точностью, используя gmp, но результат это не изменило.

До сих пор не представляю, можно ли решить эту задачу без компьютера.

>> №28094   #57

>>28093

> Ты, как мне подсказывает libastral, производишь моделирование,пользуясь числами с плавающей запятой.

Нет.

> Правильный цикл начинается с

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

> Ход решения у меня был довольно простой

Понял, спасибо.

>> №28095   #58

>>28094

>Это тоже неправильный цикл - то есть из исходного положения в него не попадешь (хотя отклонения бегунов от этого цикла будет минимальным).

Я, вероятно, не совсем ясно выразился. Естественно, положения бегунов никогда не зациклятся в точности, твоя мысль об обратимости совершенно верна.
Говоря про попадание в какой-то цикл, я имел в виду попадание в область притяжения аттрактора ( http://ru.wikipedia.org/wiki/%C0%F2%F2%F0%E0%EA%F2%EE%F0 ).

В своём решении я показываю, что:
а) Цикл, начинающийся с положений:

1): V=15, L=15, d=24112543/1419857 - 356726032*d_3/410338673 + 3537607920*d_1/6975757441 + 43965361904*d_2/118587876497
2): V=17, L=15, d=18600801/1419857 - 2747835119*d_1/6975757441 - 221100495*d_3/410338673 + 101356861425*d_2/118587876497
3): V=16, L=16, d=16

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

>> №28096   #59

>>28095
Не то скопипастил

>а) Цикл, начинающийся с положений:

1): V=15, L=15, d=1735289213/179244147 ~~ 9.68115
2): V=17, L=15, d=821285249/179244147 ~~ 4.58194
3): V=16, L=16, d=16

>> №28097   #60
runners.png - (29 KB, 2261x915)  
29 KB

>>28094

> отклонения бегунов от этого цикла будет минимальным

Вот, нарисовал пикчу, на которой показаны отклонения бегунов от идеального положения "1735289213/179244147, 821285249/179244147, 16"
Первая пикча - начиная примерно с 500ой итерации, вторая - с тысячной, третья - с полуторатысячной.
>>28095

> В своём решении я показываю,

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

>> №28098   #61

>>28097

>Я, честно говоря, вижу только доказательство устойчивости цикла

Э? Ты, видимо, под устойчивостью понимаешь не совсем то, что я. Доказательства устойчивости (то есть того, что малые отклонения будут уменьшаться) у меня как раз не приведено.

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

Итак, рассмотрим начальное положение (d_1, d_2, d_3), мало отличающееся от (1735289213/179244147, 821285249/179244147, 16). (иначе говоря, достаточно малое, чтобы порядок достижения вершин был тем же самым). Опишем его в виде 3-мерного вектора D0 = [d_1; d_2; d_3]

Тогда (см >>28093) после 9 итераций новый вектор положений D1 можно записать как:

D1 = A*D0 + B

Где

A = 
[3537607920/6975757441, 43965361904/118587876497, -356726032/410338673;
-2747835119/6975757441, 101356861425/118587876497, -221100495/410338673;
0, 0, 0]
B = [24112543/1419857; 18600801/1419857; 16 ]

Ещё через 9 шагов: D2 = A*D1+ B и т.д.

Для того, чтобы этот процесс был устойчивым, достаточно того, чтобы все собственные числа матрицы A были меньше 1 по абсолютной величине. Найдём их:

lambda_{1,2} =  (+-2747835119*sqrt(863)*i + 161496196065)/237175752994
lamda_3 = 0 (это было очевидно, в общем-то)

Их абсолютные велчины:

|lambda_{1,2}| = 262144/sqrt(118587876497) = sqrt(68'719'476'736/118'587'876'497) < 1
|lambda_3| = 0 < 1

Следовательно, малые отклонения будут убывать, и цикл является аттрактором.

Кстати, любопытное наблюдение:
Знаменатели элементов матрицы A это в действительности степени 17:
410338673 = 17^7
6975757441 = 17^8
118587876497 = 17^9

>> №28099   #62

>>28098

> Ты, видимо, под устойчивостью понимаешь не совсем то

Да, сорри,

> Кстати, любопытное наблюдение:

Ваще охуеть. Интересно, откуда они там взялись.
И еще совершенно непонятно, почему цикл длится ровно 3 часа.

>> №28100   #63

Лучший тред в /sci за этот год, а возможно и дольше!

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

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

>> №28101   #64

>>28100

> при обращения времени отклонения увеличиваются?

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

> достаточно малое, чтобы порядок достижения вершин был тем же самым

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

>> №28102   #65

>>28101

>но потом оно станет достаточно большим для того, чтобы изменился порядок прохождения через вершины

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

>> №28103   #66

>>28102

> Или у каждого порядка прохождения вершин есть свой предельный цикл?

>>23267>>28093-кун уже нашел два различных предельных цикла, существующих в этой системе. Скорее всего, есть и другие.

> А доказательства того, что при обращении времени система за конечное число шагов уходит достаточно далеко от предельного цикла, чтобы изменился порядок прохождения вершин недостаточно?

Недостаточно для чего? В задаче вообще-то спрашивалось не о попадании в цикл (так что я вообще не очень понимаю, что мы хотим узнать, обращая время от момента попадания в область действия аттрактора), а об обгоне.
В приницпе, улики, собранные >>23267-куном, неопровержимо свидетельствуют, что никто никого не догонит. Есть доказательство >>28098 того, что цикл >>28093 действительно является аттрактором, и расчеты показывают, что мы подходим к этому циклу достаточно близко (правда, >>23267-кун, если я правильно понимаю, эту часть выполнил с использованием вычислений с плавающей точкой - однако точные расчеты >>28097 дают тот же результат).
Так что задача уже решена. Единственное, что может все еще представлять интерес - это простое решение, без дробей с 17^9 в числителе, без системы уравнений, не влезающей на экран, без точных вычислений, занимающих каждая итерация которых 1 длится секунду на не самом древнем компьютере. Что-нибудь типа "рассмотрим бильярд в 6-мерном фазовом пространстве. Очевидно, что..."

>> №28104   #67

>>28103

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

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

>> №28105   #68

>>28104

> за конечное время мы можем выйти из устойчивого цикла при обращении времени, значит мы также туда и попадем

"Выйти из цикла" еще не означает "придти в исходную точку".
Для наглядности: из начальной точки спирали >>28097 ты будешь неуклонно приближаться к аттрактору. При обращении времени ты из любой точки спирали, сколь угодно близкой к аттрактору, вернешься на исходную позицию. Но из любой другой точки вблизи аттрактора твой обратный путь будет проходить по совсем другой спирали, чем дальше, тем сильнее отклоняющейся от первоначальной.



Удалить сообщение []
Пароль
[d | au / b / bro / ci / cu / dev / hr / l / m / mi / mu / o / ph / r / s / sci / tran / tu / tv / vg / x | a / aa / c / fi / jp / rm / tan / to / ts / vn / vo]
- [Радио 410] [ii.booru-Архив РПГ] [acomics-cf-ost] [@] - [Архив - Каталог] [Главная]