ТГиК-2019-Лекция-21.10.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Тема лекции - реккурентные уравнения.

Что такое реккурентное уравнение?

Рассмотрим известную последовательность чисел Фибоначчи. В данном случае начнем ее с 0.

\(F_0 = 0 \\ F_1 = 1\\ F_{n+2} = F_{n+1} + F_{n} \)

Последняя строка - это реккурентное уравнение или реккурентное соотношение или разностное уравнение данной последовательности.

Общий случай

Пусть есть \(a_0, a_1, a_2 ... a_n \) - некоторая последовательность, причем \(a_0 = c_0, a_1 = c_1, ..., a_{k-1} = c_{k-1}\) - начальные условия. Последовательность задаётся следующим реккурентным уравнением\[a_{n+k} = f(a_{n+k-1}, a_{n+k-2}, ..., a_n)\]

1) Запишем реккурентное уравнение следующим образом\[a_{n+k} = \sum^{k-1}_{i=0}{a_{n+i} * c_i}\]

2) Построим характеристический многочлен по следующему принципу: номер члена переходит в степень.

Тогда\[x^{n+k} = \sum^{k-1}_{i=0}{x^{n+i} * c_i}\]

Делим на \(x^n\) и получаем\[x^{k} = \sum^{k-1}_{i=1}{x^{i} * c_i} + c_0\]

3) Из основной теоремы алгебры следует, что для полученного многочлена есть \(k\) комплексных корней с учётом их кратности:

Корень - λi, кратность - Sj
λ1 λ2 ... λn
S1 S2 ... Sr

Причём\[\sum^{r}_{j=1}{S_j} = k\]

4) Значит\[a_n = \sum^{r}_{i=1}{λ^n_i P_{S_i -1}(n)}\]

\(P_{S_i -1}(n)\) - это полином. В полиноме степени \( i \mbox{ } (i+1) \) коэффициентов. Значит, в полиноме степени \((S_i-1) \mbox{ } S_i\) коэффициентов. А во всей сумме - \(k\) коэффициентов, так как \(\sum^{r}_{j=1}{S_j} = k\)

5) Следовательно, чтобы найти коэффициенты, а их k штук, нам требуется k начальных условий\[a_0 = c'_0 \\ a_1 = c'_1 \\ ... \\ a_{k-1} = c'_{k-1} \]

Данная система - линейно независимая, значит, она обязательно имеет решение.

Пример

Вернёмся к случаю с последовательностью Фибоначчи. Запишем характеристический многочлен\[ x^2 = x+1 \]

\(x^2 - x-1=0, \mbox{ } D = 1+4=5, \mbox{ } x=\frac{1+\sqrt{5}}{2} \)

Теперь можно записать n-й член:

\( F_n = {\left (\frac{1+\sqrt{5}}{2} \right )}^n * C_0 + {\left (\frac{1-\sqrt{5}}{2} \right )}^n * C_1 \)

С помощью начальных условий найдем \(C_0, C_1\)

\(F_0 = 0 = C_0 + C_1 \)

\(F_1 = 1 = \frac{1+\sqrt{5}}{2}*C_0 + \frac{1-\sqrt{5}}{2}*C_1 \)

Решая систему, получим:

\(C_0 = \frac{1}{\sqrt{5}},\mbox{ } C_1 = -\frac{1}{\sqrt{5}}\)

Тогда можно записать окончательный ответ:

\(F_n = \frac{1}{\sqrt{5}}* \left ({\left (\frac{1+\sqrt{5}}{2} \right )}^n - {\left (\frac{1-\sqrt{5}}{2} \right )}^n \right )\)

Асимптотика последовательности Фибоначчи:

\( F_n = \frac{1}{\sqrt{5}}*{\left (\frac{1+\sqrt{5}}{2} \right )}^n \mbox{ при } n \longrightarrow \infty \)

Нахождение n-й степени числа а

Пусть \(D(n)\) - количество действий, которые нужно совершить, чтобы получить n-ю степень числа а.

1 способ

Распишем \(a^n\)

\(a^n = a^{n-1}*a = ...\)

Тогда \(D(n) = D(n-1)+1 = n + D(0)\)

2 способ

\( a^{n} = a^{ \left \lfloor \frac{n}{2} \right \rfloor } * a^{ \left \lfloor \frac{n}{2} \right \rfloor }* a^{n\bmod 2}\)

Теперь \(D(n) = D(\frac{n}{2})+2 = D(\frac{n}{2^k})+2k =\)

При каких k процесс завершится? Решим следующее уравнение \(2^k = n \), откуда \(k=\log_2 n\)

Тогда \(= D(0) + 2*\log_2 n\)

Очевидно, что второй способ эффективнее первого

3 способ

Как найти \(F_n\) через \(\log_2 n\)?

\(M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \)

\(M^n = \begin{pmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{pmatrix} \)

\(M^n * M= \begin{pmatrix} F_{n+2} & F_{n+1} \\ F_{n+1} & F_{n} \end{pmatrix} = M^{n+1}\)

Задача о тетраэдре

Рис.1. Тетраэдр на поверхности

Пусть есть тетраэдр на некоторой поверхности (рис.1). Его раз в минуту переворачивают на другую сторону - это является шагом. Какова вероятность того, что через \(n\) шагов он лежит на той же стороне, с которой начали?

Решение

Обозначим вероятность на \(n\)-ом шаге \(P_n\)

1) Рассмотрим "в лоб":

Так как в момент, когда переворота ещё не произошло, тетраэдр лежит на нужной нам стороне, то 0 шаг - \(P_0 = 1\)

Так как после первого переворота тетраэдр точно не лежит на той же стороне, что и лежал до переворота, то 1 шаг - \(P_1 = 0\)

Далее известно, что после 1 шага тетраэдр точно лежит не на той же стороне. При перевороте он может оказаться на любой из 3 оставшихся сторон. Следовательно, 2 шаг - \(P_2 = \frac{1}{3}\)

2) Получим общую формулу

Рассмотрим вероятность на \(n+1\) шаге. Вариантов 2: либо тетраэдр лежит на нужной нам стороне, либо лежит на какой-либо другой (стороны равноправны).

Вероятность того, что тетраэдр окажется на нужной нам стороне, если до этого он уже лежал на ней, \(P_n *0\)

Вероятность того, что тетраэдр лежит на любой из 3 оставшихся сторон, \((1-P_n)* \frac{1}{3}\)

То есть \(P_{n+1} = P_n *0 + (1-P_n)* \frac{1}{3} = \frac{1}{3} - \frac{P_n}{3} \)

3) Выясним, к чему стремится \(P_n\)

Для этого решим простейшее уравнение\[a=\frac{1}{3} - \frac{a}{3} \Longrightarrow a=\frac{1}{4}\]

То есть \( P_n \xrightarrow{n \longrightarrow \infty} \frac{1}{4}\)

3) В дифференциальных уравнениях для линейных однородных стационарных уравнений применяется метод вариации постоянной. В случае рекуррентных уравнений сделаем его проще с помощью замены

Пусть \(P_n = Q_n + \frac{1}{4} \). Тогда исходное рекуррентное уравнение превратится в следующее \(Q_{n+1} = -\frac{1}{3} Q_{n} \)

4) Решая полученное уравнение, заметим, что \( Q_n = {\left ( -\frac{1}{3} \right )}^n * const \)

5) \(Const\) найдем из начальных условий.

\( Q_0 = P_0 - \frac{1}{4} \Longrightarrow Q_0 = \frac{3}{4} \Longrightarrow const = \frac{3}{4} \)

6) Таким образом, \(Q_n = {\left ( -\frac{1}{3} \right )}^n * \frac{3}{4} \)

\(P_n = {\left ( -\frac{1}{3} \right )}^n * \frac{3}{4} + \frac{1}{4}\)