Сегодня мы немного поговорим про гиперболические арифметики и выясним каким таким волшебным образом появляется и почему работает формула Бине:
которая позволяет вычислять в конечной форме числа Фибоначчи. На неискушённый взгляд, она вызывает недоумение: почему иррациональные корни из пяти, при возведении в какие-то степени должны давать целые числа, которые описываются простой последовательностью:
* * *
В этой серии статей мы рассматриваем различные необычные виды арифметик, которые получаются из привычных числовых систем их расширением. В качестве расширения используется решение некоторого уравнения, не решаемого в исходной системе, а новая арифметика состоит из линейных комбинаций "обычных" чисел и "необычного" расширения. Так, например, строятся хорошо известные комплексные числа или более экзотические числа Эйзенштейна, о которых мы говорили ранее.
Все арифметики, которые строятся по такому принципу, мы смогли классифицировать, используя аппарат теории представлений, и все она попадают на следующую диаграмму (Матрицы, геометрия и мультики):
В качестве примера гиперболической арифметики мы приводили двойные числа (которые, кстати, в некоторых источниках так и называются гиперболическими). Сегодня я хочу рассмотреть одну числовую систему гиперболического типа, расширяющую целые числа решением целочисленного уравнения
Корни этого уравнения вещественные, но иррациональные и равны:
Число φ называется золотым сечением и получило широкую известность за пределами математики как нечто невероятно загадочное, красивое и практически непостижимое, в общем, звезда математической попкультуры.
В этой серии статей мы отыскиваем матричные представления для всяких особенных чисел, так что давайте посмотрим на матричное представление золотого сечения. Это должна быть матрица со следом и определителем, равным 1 и –1, соответственно, тогда её характеристическое уравнение совпадёт с уравнением золотого сечения.
Простейшими целочисленными матрицами с такими свойствами будет такая пара:
Можно убедиться в том, что это именно они, вспомнив, что разность корней уравнения золотого сечения должна быть равна √5. Если мы вычислим эту разность и возведëм в квадрат, то получим матричное представление числа 5:
Поскольку собственные числа этих матриц вещественные, мы, действительно, имеем дело с числовой системой гиперболического типа. Если расширить с помощью матрицы φ кольцо целых чисел, то получится кольцо ℤ(φ), с числами, имеющими вид:
В отличие от чисел Гаусса или Эйзенштейна, они не имеют геометрического представления в виде регулярной решётки, замкнутой относительно преобразований, соответствующих сложению и умножению таких чисел. Но алгебраически это полноценное кольцо, имеющее в качестве подкольца целые числа.
Давайте внимательнее присмотримся к матрице φ и посмотрим на то, как она действует сама на себя:
Внимательный читатель легко разглядит в результатах умножения числа Фибоначчи, которые, как известно, тесно связаны с золотым сечением. Легко увидеть, откуда они тут взялись, если посмотреть на то, как матрица φ действует на вектор:
Это же и есть элементарный шаг в последовательности Фибоначчи:
его можно было сразу разглядеть в приведённом выше представлении для числа a + bφ. С помощью такого шага последовательность Фибоначчи, как правило, и программируют. Вот, например, простейшая программка на языке Julia, вычисляющая n-ное число Фибоначчи:
Выходит, что матрица, которая представляет золотое сечение, напрямую задаёт алгоритм вычисления чисел Фибоначчи! Красивая связь, правда? А как, зная это, можно выразить n-ное число Фибоначчи через золотое сечение? Отметим, сначала, что
Сопряженное с золотым сечением число тоже порождает последовательность Фибоначчи, но продолжает её влево от нуля:
Если вычислить их разницу, то получится следующая матрица:
Глядите-ка, все соседние числа Фибоначчи, кроме n-ного взаимно уничтожились, а матрицу на которую оно умножается, мы уже с вами знаем, это представление √5! Таким образом, мы получаем равенство:
из которого, очевидно, следует неочевидная формула Бине:
Иррациональные корни при вычислении этой формулы исчезают бесследно, поскольку мы работаем в арифметике ℤ(φ), содержащей целые числа ℤ и результат не примерно, а точно соответствует целому числу Фибоначчи.
Конечно, эту формулу можно вывести и иначе, не прибегая к матрицам. Однако матричные представления показывают связь между золотым сечением и числами Фибоначчи настолько очевидно, насколько это возможно. Самое же главное: этот подход легко обобщить на любую линейную рекуррентную последовательность, и получать конечные формы для таких рядов в соответствующих расширенных арифметиках!
* * *
Можно было бы тут и закончить рассказ, но я хочу добавить кое-что о том, как этой формулой пользоваться. Давайте закодируем её на языке Julia:
Функция работает, перемалывает числа с плавающей точкой и, действительно, получает целые числа. Но если мы попробуем воспользоваться ею для больших степеней (а именно для них формула Бине должна работать быстрее, чем простая итерация), то выяснится, что использование иррациональных чисел органичивает нас в возможностях.
Что же, выходит, что формула Бине имеет только теоретический интерес? Нет, не зря же мы изучали матричные представления! Они позволяют неявно использовать эту формулу эффективно и без потерь точности.
Возводить число или матрицу в n-ную степень можно не просто терпеливо перемножая n раз объект сам на себя. Можно воспользоваться так называемым методом русского крестьянина, который состоит в последовательном применении таких простых тождеств:
Вот как можно использовать их для вычисления n-ной степени какого-то числа:
А вот так мы возводим в 100-ю степень нашу матрицу, представляющую φ:
При этом мы не двести раз умножаем одну матрицу на другую, а согласно методе русского крестьянина, используем разложение
и значит, выполняем всего 6 матричных умножений, не теряем точности и можем почувствовать себя крутыми математиками!
────────────────────────
Хотите, чтобы в вашей ленте Дзена было больше интересных и глубоких материалов? Подскажите алгоритму Дзена, что там нравятся публикации, подобные этой, подпишитесь, поставьте лайк или прокомментируйте.
Давайте формировать информационную среду вместе!