Алгебра · объяснение и практика
Как пара соседних членов превращает рекурсию в матричный шаг
Как хранить два соседних члена рекурсии в одном столбце, получить следующий шаг матрицей и не перепутать номер состояния с номером члена.

В теме Матрицы и комплексные числа: углубление · Учебная карта
В маршруте Матрицы и линейные системы · 10 тем
Главная мысль
Для рекурсии uₙ₊₂=p uₙ₊₁+q uₙ удобно хранить столбец (uₙ₊₁;uₙ). Следующий столбец получается умножением на матрицу со строками (p;q) и (1;0).
Одного текущего числа не хватает
В рекурсии второго порядка следующий член зависит от двух предыдущих. Если сохранить только последнее значение, информации для нового шага может не хватить. Поэтому состоянием выбирают упорядоченную пару соседних членов. Верхняя координата будет более новым значением, нижняя — предыдущим; этот порядок нужно удерживать во всех последующих произведениях.
Для правила uₙ₊₂=2uₙ₊₁+uₙ переход задаёт матрица со строками (2;1),(1;0). Верхняя строка вычисляет новый член, а нижняя копирует прежний верхний на место предыдущего. Так одновременно выполняются вычисление и сдвиг памяти. Ноль в правом нижнем углу необходим: более старое значение не должно ещё раз добавиться при копировании.
Пример
Пусть u₀=1,u₁=2. Начальное состояние (2;1) переходит в (5;2), затем в (12;5). Значит, u₂=5 и u₃=12.
Прямая проверка рекурсией даёт 2·2+1=5 и 2·5+2=12. Это подтверждает и коэффициенты матрицы, и выбранный порядок компонент.
Степень матрицы считает число переходов
Если начальное состояние s₀=(u₁;u₀), то после k шагов получится sₖ=Mᵏs₀=(uₖ₊₁;uₖ). Сам показатель k не является автоматически номером верхнего члена: тот имеет номер k+1. Проверка при k=0 особенно полезна, поскольку единичная матрица должна вернуть исходную пару без сдвига.
Ассоциативность позволяет вычислять степени последовательным возведением в квадрат, сохраняя порядок действий. Это ускоряет получение далёкого состояния, но не отменяет рост самих чисел. Если вычисления проводят по модулю, такой выбор должен быть задан отдельно: остатки не восстанавливают точные большие значения без дополнительных данных.
Что модель предполагает о коэффициентах
Одна постоянная матрица подходит, когда p и q не меняются с номером. Если коэффициенты зависят от n, на каждом шаге действует своя матрица, и вместо Mᵏ возникает упорядоченное произведение. Переставлять эти множители нельзя: общий закон матричного умножения некоммутативен, а переходы относятся к разным этапам.
Для неоднородной рекурсии с постоянным добавлением можно расширить состояние координатой, равной единице, но это уже другая матрица. Не прячьте добавку в начальное значение: её влияние повторяется на каждом шаге. Перед ускоренным вычислением всегда проверьте два коротких перехода вручную — они обнаруживают большинство ошибок индексации.
От чтения к действию
А теперь — вы
Частые вопросы
Связана ли эта запись с числами Фибоначчи?
Да. Для правила Fₙ₊₂=Fₙ₊₁+Fₙ берут p=q=1. Начальное состояние зависит от того, с какого номера задана последовательность.
Нужна ли обратная матрица для движения вперёд?
Нет. Прямой переход определён для любых заданных p и q. Возможность однозначно восстановить прошлое — отдельный вопрос об обратимости.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как размеры матриц определяют допустимое произведение
Как до вычислений проверить размеры матриц, выбрать строку и столбец и понять, почему произведение не является попарным умножением элементов.
Открыть темуПочему перестановка матриц меняет результат
Как два допустимых матричных произведения дают разные результаты и почему порядок линейных преобразований нельзя переставлять по привычке к числам.
Открыть тему