теловычитание

На выходных к нам приезжал 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, то она стабилизируется.

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

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

Хороший повод вспомнить развлечения Вольфрама: он брал простые алгоритмы и очень мощные (фактически, бесконечного объёма) носители и удивлялся, "откуда берётся сложность?". Правильнее его вопрос нужно было бы переформулировать как "куда помещается сложность?". В нашем случае сложность помещается либо в бесконечно больших числах, либо в бесконечно маленьких (но точных!).