Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Рекуррентные соотношения
Мы, рассматривая возвратные задачи, решили задачу о ханойской башне. Для числа перекладываний было получено следующее соотношение: . (1) Решение задачи для п дисков выражено через решение задачи с диском. Соотношение (1) является частным случаем рекуррентных соотношений. Однородное рекуррентное соотношение линейное, с постоянными коэффициентами имеет вид . (2) Рассмотрим метод решения рекуррентного соотношения (2). Будем искать решение в виде . Подставляя это решение в (2), получаем . (3) Уравнение (3) называется характеристическим из него можно найти корни . Согласно основной теореме алгебры таких корней равно k. Таким образом, решение соотношения (2) может быть записано в виде . (4) Постоянные выбираются из дополнительных условий накладываемых на функцию . Рассмотрим пример решения рекуррентного соотношения для определения чисел Фибоначчи, это соотношение имеет вид (5) Соотношение (5) примем в виде подобном (2) . (6) Характеристическое уравнение для этого случая принимает вид . (7) Корни этого уравнения следующие . (8) Общее решение, согласно (4), запишется так . (9) Постоянные и определяем из условий . Эти условия принимают вид (10) Из этой системы легко находим значения константы и (11) Частное решение изучаемых рекуррентных соотношений, с учётом (11) и (8) приводится к виду . Изучим пример решения линейного неоднородного рекуррентного соотношения с постоянными коэффициентами для случая, когда правая часть есть постоянная. . (12) Решение уравнения (12) является суммой частного решения (12) и общего решения однородного уравнения следующего из (12). Частное решение для случая ищем в виде . Последнюю величину находим из уравнения . . (13) Решение уравнения (12) окончательно принимает вид . (14)
|