Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Вычисление линейных рекуррентных последовательностей⇐ ПредыдущаяСтр 39 из 39 Последовательность называется линейной рекуррентной, если существуют такие коэффициенты , что для любого n справедливо равенство . Для задания линейной рекуррентной последовательности, кроме ее коэффициентов, необходимо знать первые k членов , которые называются начальными условиями. Рассмотрим задачу выражения n-го члена последовательности через его номер и начальные условия. Обозначим через вектор столбец, состоящий из k компонент , через — матрицу размерами вида . По правилу перемножения матриц имеем: . Многократным применением полученной формулы выводим . Задача вычисления n -го члена последовательности свелась, тем самым, к вычислению матрицы . Характеристический многочлен матрицы А равен . Разделим многочлен на с остатком. Пусть , где - остаток от деления. Подставив вместо λ матрицу А, получим . По теореме Гамильтона-Кэли каждая матрица является корнем своего характеристического уравнения, то есть , где 0 - нулевая матрица. Таким образом, , и задача вычисления свелась к вычислению многочлена r (λ). Разложим многочлен на линейные множители , где . Для каждого неотрицательного j строго меньшего справедливо равенство , где - j -ая производная характеристического многочлена. Продифференцировав j раз равенство и, подставив в него , получим . Этими условиями многочлен r (λ) степени k -1 определяется однозначно. В литературе задача вычисления многочлена по таким условиям носит название «интерполяционный многочлен Лагранжа-Сильвестра». В качестве примера вычислим n -ый член линейной рекуррентной последовательности , где . Положим . Характеристический многочлен равен . Остаток от деления на удовлетворяет соотношениям и . Единственный многочлен первой степени, удовлетворяющий этим условиям, равен . Таким образом, и .
|