теловычитание
Mar. 5th, 2007 03:55 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
jayrandomНа выходных к нам приезжал ![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
pikitan. За два сеанса он научился пилотировать четырёхстропного воздушного змея (чуть не улетев на нём в воскресный шторм) и наставил меня по эзотерической линейной алгебре. Теперь я могу продолжить идею, подкинутую в прошлый приезд schloenskiм.
У золотого сечения есть два, если можно так выразиться, представления: одно - это само число Фи, отношение. Другое - это алгоритм Фибоначчи (А.Ф.), который сходится к числу Фи отношениями своих последовательных членов. Из практики мы знаем, что А.Ф. чрезвычайно устойчив: его можно инициализировать практически любыми двумя числами, и он очень быстро сойдётся (в отношении) к Фи. Оказывается, самое простое представление алгоритма "таит" в себе число Фи, и ещё кое-что.
Алгоритм Фибоначчи представим в виде контекстно-свободной грамматики {start->A, A->B, B->AB}. Производя последовательность подстановок мы будем получать строку, длина которой - очередное число Фибоначчи. Деля друг на дружку две последовательных длины - будем получать всё более и более точные приближения числа Фи.
Производя подстановки, мы можем заметить, что работу по вычислению можно упростить, если от представления BABABBAB перейти к представлению 3A+5B. И мы заменяем нашу грамматику матрицей [0 1; 1 1], в которой каждой строке соответствует одно правило грамматики, а каждой ячейке в столбце - количество соответствующих букв в правой части правила. Оказывается, из этой матрицы, хотя она выражает всего один шаг алгоритма, можно узнать некоторые "секреты" алгоритма Фибоначчи.
schloenski подкинул идею рассмотреть характеристическое уравнение "грамматической матрицы". Удивительно или нет, но собственными значениями матрицы оказались 1.618033988749891 и -0.618033988749891. Очень интересно. А соответствующими собственными векторами [0.52573111211913 0.85065080835204] и [-0.85065080835204 0.52573111211913]. Здесь я подвис, пытаясь понять смысл того и другого в контексте изначально целочисленной задачи.
pikitan же показал, что вектор, будучи много раз преобразованным симметричной матрицей, постепенно сходится к одному из собственных векторов матрицы по направлению - т.е. если его каждый раз нормализовывать, то он постепенно "поворачивается" к собственному. Также выяснилось, что у матрицы поворота собственные значения - комплексные (и в их случае, очевидно, сходимость если и происходит, то вне плоскости поворота).
Матрица у нас хорошая (например, симметричная), поэтому собственные вектора ортогональны. Значит, должно существовать два перпендикулярных направления, в которых возможна сходимость. Оказалось, что устойчивость А.Ф., о которой я упомянул выше, относится только к одному из направлений, а именно - заданному собственным значением 1.618033988749891 и собственным вектором [0.52573111211913 0.85065080835204]. Словами это означает, что если у нас в какой-то момент была достигнута комбинация, пропорциональная 0.52573111211913*A+0.85065080835204*B, то она стабилизируется.
А как же второе собственное значение и второе направление? Из того, что собственное значение отрицательное и по модулю меньшее единицы, следует, что соответствующий ряд будет знакопеременным и сходиться с двух сторон к нулю. Весьма неожиданно, потому что таких рядов мне при экспериментах с З.С. не попадалось ни разу. Но я всё-таки подставил вектор и решил посмотреть, что дальше будет.
Шага до 28-29го отношение ещё держалось около -0.61, а потом всё "сломалось" - числа стали снова расти. Удивительно, что эта пара чисел продержалась так долго: до сих пор почти любая комбинация сходилась к 1.61 очень быстро, шагов за 5-6.
По всей видимости, сходимость нарушилась из-за того, что стремительно уменьшающиеся числа "вылезли" за предполагаемые пределы точности, зашитые в процессор. Мы не уважаем очень маленьких чисел. Обращаем внимание лишь на старшие разряды, в то время как для некоторых процессов важна абсолютная точность.
Хороший повод вспомнить развлечения Вольфрама: он брал простые алгоритмы и очень мощные (фактически, бесконечного объёма) носители и удивлялся, "откуда берётся сложность?". Правильнее его вопрос нужно было бы переформулировать как "куда помещается сложность?". В нашем случае сложность помещается либо в бесконечно больших числах, либо в бесконечно маленьких (но точных!).
pikitan. За два сеанса он научился пилотировать четырёхстропного воздушного змея (чуть не улетев на нём в воскресный шторм) и наставил меня по эзотерической линейной алгебре. Теперь я могу продолжить идею, подкинутую в прошлый приезд schloenskiм.У золотого сечения есть два, если можно так выразиться, представления: одно - это само число Фи, отношение. Другое - это алгоритм Фибоначчи (А.Ф.), который сходится к числу Фи отношениями своих последовательных членов. Из практики мы знаем, что А.Ф. чрезвычайно устойчив: его можно инициализировать практически любыми двумя числами, и он очень быстро сойдётся (в отношении) к Фи. Оказывается, самое простое представление алгоритма "таит" в себе число Фи, и ещё кое-что.
Алгоритм Фибоначчи представим в виде контекстно-свободной грамматики {start->A, A->B, B->AB}. Производя последовательность подстановок мы будем получать строку, длина которой - очередное число Фибоначчи. Деля друг на дружку две последовательных длины - будем получать всё более и более точные приближения числа Фи.
Производя подстановки, мы можем заметить, что работу по вычислению можно упростить, если от представления BABABBAB перейти к представлению 3A+5B. И мы заменяем нашу грамматику матрицей [0 1; 1 1], в которой каждой строке соответствует одно правило грамматики, а каждой ячейке в столбце - количество соответствующих букв в правой части правила. Оказывается, из этой матрицы, хотя она выражает всего один шаг алгоритма, можно узнать некоторые "секреты" алгоритма Фибоначчи.
schloenski подкинул идею рассмотреть характеристическое уравнение "грамматической матрицы". Удивительно или нет, но собственными значениями матрицы оказались 1.618033988749891 и -0.618033988749891. Очень интересно. А соответствующими собственными векторами [0.52573111211913 0.85065080835204] и [-0.85065080835204 0.52573111211913]. Здесь я подвис, пытаясь понять смысл того и другого в контексте изначально целочисленной задачи.pikitan же показал, что вектор, будучи много раз преобразованным симметричной матрицей, постепенно сходится к одному из собственных векторов матрицы по направлению - т.е. если его каждый раз нормализовывать, то он постепенно "поворачивается" к собственному. Также выяснилось, что у матрицы поворота собственные значения - комплексные (и в их случае, очевидно, сходимость если и происходит, то вне плоскости поворота).Матрица у нас хорошая (например, симметричная), поэтому собственные вектора ортогональны. Значит, должно существовать два перпендикулярных направления, в которых возможна сходимость. Оказалось, что устойчивость А.Ф., о которой я упомянул выше, относится только к одному из направлений, а именно - заданному собственным значением 1.618033988749891 и собственным вектором [0.52573111211913 0.85065080835204]. Словами это означает, что если у нас в какой-то момент была достигнута комбинация, пропорциональная 0.52573111211913*A+0.85065080835204*B, то она стабилизируется.
А как же второе собственное значение и второе направление? Из того, что собственное значение отрицательное и по модулю меньшее единицы, следует, что соответствующий ряд будет знакопеременным и сходиться с двух сторон к нулю. Весьма неожиданно, потому что таких рядов мне при экспериментах с З.С. не попадалось ни разу. Но я всё-таки подставил вектор и решил посмотреть, что дальше будет.
1) +0.525731112119130 / -0.850650808352040 = -0.618033988749891 2) -0.324919696232910 / +0.525731112119130 = -0.618033988749906 3) +0.200811415886220 / -0.324919696232910 = -0.618033988749866 4) -0.124108280346690 / +0.200811415886220 = -0.618033988749971 5) +0.076703135539530 / -0.124108280346690 = -0.618033988749696 6) -0.047405144807160 / +0.076703135539530 = -0.618033988750416 7) +0.029297990732371 / -0.047405144807160 = -0.618033988748532 8) -0.018107154074789 / +0.029297990732371 = -0.618033988753464 9) +0.011190836657582 / -0.018107154074789 = -0.618033988740551 10) -0.006916317417207 / +0.011190836657582 = -0.618033988774357 11) +0.004274519240374 / -0.006916317417207 = -0.618033988685852 12) -0.002641798176833 / +0.004274519240374 = -0.618033988917562 13) +0.001632721063541 / -0.002641798176833 = -0.618033988310936 14) -0.001009077113292 / +0.001632721063541 = -0.618033989899104 15) +0.000623643950248 / -0.001009077113292 = -0.618033985741226 16) -0.000385433163044 / +0.000623643950248 = -0.618033996626693 17) +0.000238210787204 / -0.000385433163044 = -0.618033968128171 18) -0.000147222375840 / +0.000238210787204 = -0.618034042738270 19) +0.000090988411365 / -0.000147222375840 = -0.618033847406505 20) -0.000056233964475 / +0.000090988411365 = -0.618034358791778 21) +0.000034754446889 / -0.000056233964475 = -0.618033019968248 22) -0.000021479517586 / +0.000034754446889 = -0.618036525057149 23) +0.000013274929304 / -0.000021479517586 = -0.618027348638548 24) -0.000008204588282 / +0.000013274929304 = -0.618051372973865 25) +0.000005070341021 / -0.000008204588282 = -0.617988477540824 26) -0.000003134247261 / +0.000005070341021 = -0.618153147416798 27) +0.000001936093761 / -0.000003134247261 = -0.617722087445325 28) -0.000001198153500 / +0.000001936093761 = -0.618850969269430 29) +0.000000737940260 / -0.000001198153500 = -0.615897929642943 30) -0.000000460213240 / +0.000000737940260 = -0.623645659240539 31) +0.000000277727020 / -0.000000460213240 = -0.603474641702431 32) -0.000000182486220 / +0.000000277727020 = -0.657070456480080 33) +0.000000095240800 / -0.000000182486220 = -0.521906806397887 34) -0.000000087245420 / +0.000000095240800 = -0.916050888283738 35) +0.000000007995381 / -0.000000087245420 = -0.091642410689153 36) -0.000000079250039 / +0.000000007995381 = -9.911978334921359 37) -0.000000071254659 / -0.000000079250039 = +0.899111966732529 38) -0.000000150504698 / -0.000000071254659 = +2.112208531306851 39) -0.000000221759356 / -0.000000150504698 = +1.473438102904209 40) -0.000000372264054 / -0.000000221759356 = +1.678684770014402 41) -0.000000594023410 / -0.000000372264054 = +1.595704457360044 42) -0.000000966287463 / -0.000000594023410 = +1.626682463276699 43) -0.000001560310873 / -0.000000966287463 = +1.614748128522672 44) -0.000002526598337 / -0.000001560310873 = +1.619291629657993 45) -0.000004086909210 / -0.000002526598337 = +1.617553985758086 46) -0.000006613507547 / -0.000004086909210 = +1.618217387984945 47) -0.000010700416757 / -0.000006613507547 = +1.617963944414929 48) -0.000017313924304 / -0.000010700416757 = +1.618060744463381 49) -0.000028014341061 / -0.000017313924304 = +1.618023769145727 50) -0.000045328265364 / -0.000028014341061 = +1.618037892315991 51) -0.000073342606425 / -0.000045328265364 = +1.618032497723921 52) -0.000118670871789 / -0.000073342606425 = +1.618034558271664 53) -0.000192013478214 / -0.000118670871789 = +1.618033771212013 54) -0.000310684350003 / -0.000192013478214 = +1.618034071841983 55) -0.000502697828217 / -0.000310684350003 = +1.618033957011543 56) -0.000813382178221 / -0.000502697828217 = +1.618034000872867 57) -0.001316080006438 / -0.000813382178221 = +1.618033984119332 58) -0.002129462184658 / -0.001316080006438 = +1.618033990518613 59) -0.003445542191096 / -0.002129462184658 = +1.618033988074305 60) -0.005575004375755 / -0.003445542191096 = +1.618033989007947 61) -0.009020546566851 / -0.005575004375755 = +1.618033988651328 62) -0.014595550942606 / -0.009020546566851 = +1.618033988787544 63) -0.023616097509457 / -0.014595550942606 = +1.618033988735514 64) -0.038211648452063 / -0.023616097509457 = +1.618033988755388 65) -0.061827745961521 / -0.038211648452063 = +1.618033988747797 66) -0.100039394413584 / -0.061827745961521 = +1.618033988750696 67) -0.161867140375105 / -0.100039394413584 = +1.618033988749589 68) -0.261906534788690 / -0.161867140375105 = +1.618033988750012 69) -0.423773675163795 / -0.261906534788690 = +1.618033988749850 70) -0.685680209952484 / -0.423773675163795 = +1.618033988749912 71) -1.109453885116279 / -0.685680209952484 = +1.618033988749888 72) -1.795134095068763 / -1.109453885116279 = +1.618033988749897 73) -2.904587980185042 / -1.795134095068763 = +1.618033988749894 74) -4.699722075253804 / -2.904587980185042 = +1.618033988749895 75) -7.604310055438846 / -4.699722075253804 = +1.618033988749895 76) -12.304032130692651 / -7.604310055438846 = +1.618033988749895 77) -19.908342186131499 / -12.304032130692651 = +1.618033988749895 78) -32.212374316824153 / -19.908342186131499 = +1.618033988749895 79) -52.120716502955652 / -32.212374316824153 = +1.618033988749895 80) -84.333090819779812 / -52.120716502955652 = +1.618033988749895 81) -136.453807322735457 / -84.333090819779812 = +1.618033988749895 82) -220.786898142515270 / -136.453807322735457 = +1.618033988749895 83) -357.240705465250699 / -220.786898142515270 = +1.618033988749895 84) -578.027603607765968 / -357.240705465250699 = +1.618033988749895 85) -935.268309073016667 / -578.027603607765968 = +1.618033988749895 86) -1513.295912680782749 / -935.268309073016667 = +1.618033988749895 87) -2448.564221753799302 / -1513.295912680782749 = +1.618033988749895 88) -3961.860134434582051 / -2448.564221753799302 = +1.618033988749895 89) -6410.424356188381353 / -3961.860134434582051 = +1.618033988749895 90) -10372.284490622963858 / -6410.424356188381353 = +1.618033988749895 91) -16782.708846811343392 / -10372.284490622963858 = +1.618033988749895 92) -27154.993337434309069 / -16782.708846811343392 = +1.618033988749895 93) -43937.702184245652461 / -27154.993337434309069 = +1.618033988749895 94) -71092.695521679968806 / -43937.702184245652461 = +1.618033988749895 95) -115030.397705925628543 / -71092.695521679968806 = +1.618033988749895 96) -186123.093227605597349 / -115030.397705925628543 = +1.618033988749895 97) -301153.490933531196788 / -186123.093227605597349 = +1.618033988749895 98) -487276.584161136765033 / -301153.490933531196788 = +1.618033988749895 99) -788430.075094667961821 / -487276.584161136765033 = +1.618033988749895 100) -1275706.659255804726854 / -788430.075094667961821 = +1.618033988749895
Шага до 28-29го отношение ещё держалось около -0.61, а потом всё "сломалось" - числа стали снова расти. Удивительно, что эта пара чисел продержалась так долго: до сих пор почти любая комбинация сходилась к 1.61 очень быстро, шагов за 5-6.
По всей видимости, сходимость нарушилась из-за того, что стремительно уменьшающиеся числа "вылезли" за предполагаемые пределы точности, зашитые в процессор. Мы не уважаем очень маленьких чисел. Обращаем внимание лишь на старшие разряды, в то время как для некоторых процессов важна абсолютная точность.
Хороший повод вспомнить развлечения Вольфрама: он брал простые алгоритмы и очень мощные (фактически, бесконечного объёма) носители и удивлялся, "откуда берётся сложность?". Правильнее его вопрос нужно было бы переформулировать как "куда помещается сложность?". В нашем случае сложность помещается либо в бесконечно больших числах, либо в бесконечно маленьких (но точных!).
