След матрицы. Случай, когда A = TUT^{-1}. Нахождение n-го числа Фибоначчи за O(log(n))

Потренировались раскладывать на множители выражения, состоящие из матриц. Рассмотрели основные свойства следа и решили задачу. Научились работать с матрицей, которую можно разложить в произведение трех матриц вида A = TUT^{-1}. Убедились, что такие матрицы легко возводить в степень, считать значение многочлена на них. Также посмотрели, что со следом таких матриц тоже легко работать. Рассмотрели понятие нильпотентных матриц и примеры. В конце применили алгоритм быстрого возведения в степень и матричное умножение к задаче нахождение n-го числа Фибоначчи за O(log(n)).