Добавить материал

и получить 10 документов
и свидетельство автора

Изнауров Ахмед Изнаурович

способы решения рекуррентных соотношений

Научно-исследовательская работа
Образовательные программы
Повышение квалификации
Подготовка к тестированию
docx
14.02.2017

Публикация педагогических разработок

Бесплатное участие. Свидетельство автора сразу.
Мгновенные 10 документов в портфолио.

Добавить материал

основные формулы комбинаторики. Были затронуты два логических правила: правило суммы и правило произведения, биномиальная теорема(бином Ньютона),полиномиальная теорема и разбиение множеств. Теперь приступим к рассмотрению более интересного раздела дискретной математики - это рекуррентные соотношения. Рекуррентное соотношение - это соотношение(равенство, система равентсв) позволяющее свести решение комбинационной задачи для некоторого числа предметов к аналогичной задаче с меньшей размерностью. Решение комбинационных задач с помощью рекуррентных соотношений - это метод рекуррентных соотношений.

способы решения рекуррентных соотношений.docx

способы решения рекуррентных соотношений

Рекуррентные соотношения. Метод рекуррентных соотношений.

В предыдущей статье, мы рассмотрели основные формулы комбинаторики. Были затронуты два логических правила: правило суммы и правило произведения, биномиальная теорема(бином Ньютона),полиномиальная теорема и разбиение множеств. Теперь приступим к рассмотрению более интересного раздела дискретной математики - это рекуррентные соотношения. Рекуррентное соотношение - это соотношение(равенство, система равентсв) позволяющее свести решение комбинационной задачи для некоторого числа предметов к аналогичной задаче с меньшей размерностью. Решение комбинационных задач с помощью рекуррентных соотношений - это метод рекуррентных соотношений.

Рекуррентное соотношение

Пример 1: На плоскости нарисовано n - прямых, причем все прямые попарно не параллельны и никакие три прямые не пересекаются в одной точке. На сколько полуплоскостей они разобьют нашу плоскость?

Решение: Рассмотрим пару тривиальных случая и пусть функция f(n) равняется количеству полуплоскостей образованных n - прямыми. Рассмотрим сначала тривиальные случаи:

1) n = 0 => f(0) = 1

2) n = 1 => f(1) = 2

3) n = 2 => f(2) = 4

Теперь пусть на плоскости n прямых и мы проводим (n + 1) - прямую. Получим, что после проведения нашей (n + 1) - прямой общая численность полуплоскостей увеличиться на (n + 1) - полуплоскость. Отсюда получаем:

$f(n + 1) = f(n) + n + 1 , n \geq 0 => f(n + 1) - f(n) = n + 1$

при

Выражаем сначала через и получаем и подставляем полученное равенство в последнее уравнение и получаем

Теперь выражаем через и т. д. В итоге получим следующее равенство

$f(n) = n + (n - 1) + (n - 2) + . . . + 1 + f(0) = \frac{n(n+1)}{2} + 1$

Пусть $f_{n} = f(n)$ - решение комбинаторной задачи для n - предметов и для этой задачи известно рекуррентное соотношение вида

$f_{n + k} = F(f_{n} , f_{n + 1} , . . . , f_{n + k + 1})$ (1)

$F(y_{1} , y_{2} , . . . , y_{k})$ - некоторая функция k - переменных. (1) - рекуррентное соотношение k - го порядка. Последовательность чисел ${x}^{\infty}_{n+1}$ - решение (1), если при подстановке $f_{n}=x_{n}$ в (1) получается верное равенство.

Если первые k элементов $f_{1} , f_{2} , . . . , f_{k}$ рекуррентного соотношения (1) заданы произвольно(т.е. между ними нет соотношений), то (1) имеет бесконечно много решений. Если же первые k элементов определены однозначно, то все остальные элементы определяются однозначно.

Определение 1: Пусть $f_{n}$ - общее решение (1), если оно зависит от k прозвольных постоянных, т.е. $f_{n} = f_{n}(C_{1}, C_{2} , . . . , C_{k} , n)$ . И для любого решения $x_{n}$ существуют такие постоянные значения ${C}'_{1} , {C}'_{2} , . . . , {C}'_{k}$ , что $x_{n} = f_{n}({C}'_{1} , {C}'_{2} , . . . , {C}'_{k} , n).$

Характеристическое уравнение

Определение 2: Линейным однородным рекуррентным соотношением второго порядка с постоянными коэффициентами называется рекуррентное соотношение вида:

$f_{n+2} = a_{1}f_{n+1} + a_{2}f_{n} , n=1,2,...$ (2)

$a_{1} , a_{2}$ - нейкие коэффициенты, причем $a_{2}$ отлично от нуля. Уравнение вида

$\lambda^{2} = a_{1}\lambda + a_{2}$ - характеристическое уравнение рекуррентного соотношения (2).

Теорема 1: Если характеристическое уравнение рекуррентного соотношения (2) имеет два различных корня $\lambda_{1} \neq \lambda_{2}$ , то общее решение рекуррентного соотношения (2) имеет вид

$f_{n} = C_{1}\lambda_{1}^{n-1} + C_{2}\lambda_{2}^{n-1}$

Если рекуррентное соотношение имеет два равных корня $\lambda_{1} = \lambda_{2}$ , то общее решение рекуррентного соотношения (2) имеет следующий вид

$f_{n} = (C_{1} + C_{2})\lambda^{n-1} , n=1,2,...$

Утверждение 1: Пусть последовательности $g_{n}$ и $h_{n} , n=1,2,...$ являются решениями рекуррентного соотношения (2), тогда для {tex} \forall A,B{tex}

$f_{n} = Ag_{n} + Bh_{n} , n=1,2,...$ является решением рекуррентного соотношения (2).

Утверждение 2: Если $\lambda_{1}$ корень характеристического уравнения рекуррентного соотношения (2), то последовательность $1, \lambda_{1}, \lambda_{1}^{2}, . . . ,\lambda_{1}^{n-1}, . . .$ является решением рекуррентного соотношения (2).

Определение 3: Линейным рекуррентным соотношением k - го порядка(k - фиксировано) с постоянными коэффициентами называется рекуррентное соотношение следующего вида:

$f_{n+k} = a_{1}f_{n+k-1} + a_{2}f_{n+k-2} + . . . + a_{k-1}f_{n+1} + a_{k}f_{n}$ (3)

$n=1,2,... ; a_{1}, . . . , a_{k}$ - постоянные $k \epsilon \mathbb{N}$ .

Характеристическим уравнением рекуррентного соотношения (3) является уравнение вида

$\lambda^{k} = a_{1}\lambda^{k-1} + a_{2}\lambda^{k-2} + . . . + a_{k-1}\lambda^{1} a_{k}$

Теорема 2: Пусть $\lambda_{1}, \lambda_{2}, . . . , \lambda_{p}$ - все попарно различные корни характеристического уравнения рекурретного соотношения (3) $m_{i}$ - кратность корня $\lambda_{i} , i=1,2,...,p (m_{1} + m_{2} + . . . + m_{p} = k)$ . Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:

В частности, если , то

$f_{n} = C_{1}\lambda_{1}^{n-1} + C_{2}\lambda_{2}^{n-1} + . . . + C_{k}\lambda_{k}^{n-1} , n=1,2,...$

Из этой статьи Вы узнали следующее:

рекуррентные соотношения, рекуррентные соотношения 2-го порядка и k-го порядка
характеристическое уравнение рекуррентного соотношения
методы нахождения общего решения рекуррентного соотношения

В последующих статьях мы познакомим Вас с производящими функциями и булевыми функциями. Вы также можете ознакомиться со статьями математического анализа: "Степенные ряды. Радиус сходимости", "Функциональные последовательности и ряды. Теорема Вейерштрасса", "Числовые ряды. Знакопеременные и знакочередующиеся ряды" , "Предел функции. Основные понятия. Предел функции в точке".

РЕКОМЕНДУЕМ ПРОЧИТАТЬ

Свойства углов. Свойства параллельных прямых.
Экстремум функции. Необходимое и достаточное условие экстремума
Комплексные числа. Действительная и мнимая часть. Мнимая единица.
Случайные события. Элементарное событие. Алгебра событий
Полиномиальные нормальные формы. ПНФ. Полином Жегалкина.
Бесконечно малые последовательности. Бесконечно большие последовательности.

Скачано с www.znanio.ru

Рекуррентные соотношения. Метод рекуррентных соотношений

$Утверждение 1 : Пусть последовательности и являются решениями рекуррентного соотношения (2), тогда для {tex} \forall$

Материалы на данной страницы взяты из открытых источников либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.

Посмотрите также