==Разностное уравнение и рекуррентная последовательность ==
~~TOC~~
Будем обозначать через $ \mathbb A_{} $ какое-либо из множеств $ \mathbb Z,\mathbb Q, \mathbb R_{} $ или
$ \mathbb C_{} $.
=== Линейное уравнение ==
Пусть заданы числа $ n \in \mathbb N $ и $ \{ a_1,\dots, a_n \} \subset \mathbb A $. Уравнение
$$
x_{n+K}=a_1 x_{n+K-1}+ \dots+ a_n x_K \ npu \ K \in \{0,1,2,\dots \} \ u \ a_n \ne 0
$$
называется **линейным однородным разностным** (или **возвратным**) уравнением $ n_{} $-го порядка (над множеством $ \mathbb A_{} $). Пусть числа $ x_0,\dots,x_{n-1} $ заданы. Тогда уравнение определяет линейную **рекуррентную**[[recurrere (//лат.//) --- возвращаться]](или **возвратную**) последовательность $ \mathbf n $**-го порядка**: начиная с $ K=0 $, каждый элемент $ x_{n+K} $ этой последовательности определяется через $ n_{} $ предшествующих.
!!П!! **Пример.** Уравнение первого порядка $ x_{K+1}=qx_{K} $ определяет --- при задании $ x_{0} $ --- геометрическую прогрессию.
!!П!! **Пример.** Уравнение второго порядка
$$ x_{K+2}=x_{K+1}+x_K $$
определяет при $ x_0=1, x_1=1 $ последовательность **чисел Фибоначчи** --- они обозначаются буквой $ F_{} $
$$ \{F_K\}_{K=0}^\infty=\{1,1,2,3,5,8,13,21,34,\dots \}\ .$$
!!П!! **Пример.** Разложение рациональной функции $ g_{}(x)/f(x) $ при $ f(x)=a_0x^n+\dots+a_n $ и $ g_{}(x) $ --- полиномах, $ \deg g < \deg f\ge 1, a_n \ne 0 $ в ряд Тейлора по степеням $ x_{} $ имеет коэффициенты разложения
$$ \sum_{j=0}^{\infty} c_j x^j $$
удовлетворяющими линейному разностному уравнению $ n_{} $-го порядка
$$ c_{K}a_0+c_{K+1}a_{1}+\dots+c_{K+n}a_n = 0 $$
(подчеркнем: уравнение __не зависит__ от коэффициентов $ g_{}(x) $). Подробнее
☞
((fraction#разложения_в_ряды ЗДЕСЬ)).
!!П!! **Пример.** Примером линейной рекуррентной последовательности $ n_{} $-го порядка может служить последовательность сумм Ньютона полинома $ n_{} $-й степени. Подробнее
☞
((:dets:discrim:waring ЗДЕСЬ)).
----
**Задача.** Решить разностное уравнение, т.е. найти выражение для $ x_{K} $ в виде явной функции от номера $ K_{} $ и "начальных данных" $ x_0,\dots,x_{n-1} $. Будем говорить об **общем решении**, если $ x_0,\dots,x_{n-1} $ считаются произвольными.
----
!!П!! **Пример.** Общее решение разностного уравнения $ x_{K+1}=qx_{K} $ задается формулой $ x_K = q^K x_0 $.
!!§!! Поставленную задачу можно обобщить, рассматривая более широкие классы разностных уравнений, как, например линейные **неоднородные** уравнения **с переменными коэффициентами**
$$
x_{n+K}=a_1(K) x_{n+K-1}+ \dots+ a_n(K) x_K + b_{n}(K) , n \in \mathbb N, K \in \{0,1,2,\dots \},
$$
где $ a_1(K),\dots,a_n(K),b_n(K) $ --- некоторые функции от номера $ K_{} $. Примером таких рекуррентных последовательностей являются ((:numtheory#линейное_представление_нод континуанты)).
Можно пойти еще дальше и рассматривать разностные уравнения, решениями которых являются не числа, а полиномы:
$$kP_{k}(x)-(2k-1)\,xP_{k-1}(x)+(k-1)\,P_{k-2}(x) \equiv 0, \quad k\ge 2
\ ; P_0(x)\equiv 1, P_1(x) \equiv x .$$
Полиномы $ \{ P_{k} (x) \} $, удовлетворяющие этому уравнению, известны как ((:euclid_space#ортогонализация полиномы Лежандра)).
!!§!! Наконец, в некоторых разделах математики встречаются и нелинейные разностные уравнения, см.
☞
((:gruppe:vspom1#числа_каталана ЧИСЛА КАТАЛАНА)).
----
Настоящий раздел посвящен, в основном, линейным уравнениям с постоянными коэффициентами.
!!?!! Известны первые члены линейной рекуррентной последовательности:
$$ 0,1,2,2,0,-9,-38,-123,-360,-1004,-2728,-7303,... $$
Чему равен следующий?
!!§!! ''Общий принцип решения подобных задач'' (т.е. как установить по последовательности вид линейного уравнения, которое ее, возможно, задает)
☞
((:recurr:vspom1 ЗДЕСЬ)).
=== Идея решения ==
Решим сначала уравнение второго порядка
$$
x_{K+2}=p x_{K+1}+q x_{K} \ npu \ q\ne 0 .
$$
Сделаем из него --- формальной заменой $ x_{K+2} \rightarrow x^2, x_{K+1} \rightarrow x, x_{K} \rightarrow 1 $ --- алгебраическое:
$$x^2=p\cdot x+q\cdot 1 \ . $$
Анализируем корни:
1.
Если дискриминант квадратного уравнения $ \mathcal D=p^2+4q $ отличен от нуля, то его корни $ \lambda_1,\lambda_2 $ различны. Ищем решение разностного уравнения в виде
$$ x_K=C_1\lambda_1^K+C_2\lambda_2^K \ , $$
где $ C_1,C_2 $ --- некоторые, пока неопределенные, постоянные.
2.
Если дискриминант $ \mathcal D $ равен нулю (и при этом $ q\ne 0 $), то квадратное уравнение имеет единственный корень, который мы обозначим $ \lambda_1 $. В этом случае решение разностного уравнения ищется в виде
$$ x_K=(C_1 + C_2 K)\lambda_1^K \ , $$
где $ C_1,C_2 $ --- некоторые, пока неопределенные, постоянные.
В обоих случаях неопределенные коэффициенты $ C_1 $ и $ C_2 $ ищутся из "начальных условий":
получившиеся формулы должны оставаться справедливыми при $ K=0 $ и $ K=1 $. Таким образом, в случае
1
мы получим систему
$$
\left\{
\begin{array}{llll}
x_0&=&C_1&+C_2, \\
x_1&=&C_1\lambda_1&+C_2\lambda_2,
\end{array}
\right.
$$
решениями которой являются числа
$$
C_1=\frac{x_0\lambda_2-x_1}{\lambda_2-\lambda_1},\ C_2=
\frac{x_0\lambda_1-x_1}{\lambda_1-\lambda_2}\ .
$$
В случае
2
получаем систему
$$
\left\{
\begin{array}{lll}
x_0&=&C_1, \\
x_1&=&(C_1+C_2)\lambda_1
\end{array}
\right.
$$
с решениями:
$$
C_1=x_0,\ C_2=\frac{x_1}{\lambda_1}-x_0 \ .
$$
Теперь осталось показать, что найденные формулы действительно дают решение разностного уравнения. С этой целью формально подставим, например, первую из формул в уравнение:
$$ x_{K+2}=C_1\lambda_1^{K+2}+C_2\lambda_2^{K+2} \Rightarrow x_{K+1}=C_1\lambda_1^{K+1}+C_2\lambda_2^{K+1}, \ x_{K}=C_1\lambda_1^{K}+C_2\lambda_2^{K} \Rightarrow $$
$$
C_1\lambda_1^{K+2}+C_2\lambda_2^{K+2} =p (C_1\lambda_1^{K+1}+C_2\lambda_2^{K+1})+q(C_1\lambda_1^{K}+C_2\lambda_2^{K}) \Rightarrow
$$
$$ C_1\lambda_1^{K}(\lambda_1^2-p\lambda_1-q)+ C_2\lambda_2^{K}(\lambda_2^2-p\lambda_2-q)=0 \ . $$
Но, по предположению, $ \lambda_j $ действительно является корнем квадратного уравнения
$ x^2-px-q = 0 $. Следовательно, мы получили верное равенство, и решение может быть представлено в указанном виде. То, что это решение обеспечивает правильные "начальные данные" гарантировано тем способом, которым мы подбирали значения параметров $ C_1 $ и $ C_2 $.
!!П!! **Пример.** Найти выражение для $ K_{} $-го числа Фибоначчи.
**Решение.** Корни уравнения
$$ x^2-x-1=0 $$
различны:
$$
\lambda_1 = \frac{1+\sqrt{5}}{2}, \lambda_2=\frac{1-\sqrt{5}}{2} \ .
$$
Следовательно, решение должно иметь вид $ x_K= C_1 \lambda_1^K + C_2 \lambda_2^K $. Константы
$ C_1 $ и $ C_2 $ ищутся с помощью начальных данных:
$$ x_0=C_1+C_2=1, \ x_1= C_1 \lambda_1 + C_2 \lambda_2 =1 \ . $$
Решив эту линейную систему, получим выражение $ K $-го числа Фибоначчи по **формуле Бине**:
$$ F_K = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right)^{K+1} - \left( \frac{1-\sqrt{5}}{2} \right)^{K+1} \right] \ . $$
♦
Может показаться подозрительным, что заведомо целочисленная последовательность имеет, на первый взгляд, явно иррациональное представление. Тем не менее, целочисленность полученного решения может быть проверена с помощью разложения обоих слагаемых в квадратных скобках по формуле ((:binomial бинома Ньютона)).
Число $ \lambda_1 = (1+\sqrt{5})/2 \approx 1.618034 $, участвующее в формуле Бине, известно как **число золотого сечения**. Если поставить задачу разделить прямолинейный отрезок точкой на две части так, чтобы длина всего отрезка относилась к длине большей части,
как длина большей части относится к длине меньшей --- так вот величина этого отношения будет равна $ \lambda_1 $.
!!П!! **Пример.** Решить уравнение
$$ x_{K+2}=2\, x_{K+1}-2\, x_{K} \ .$$
при $ x_1=2,x_2=2 $.
**Решение.** Соответствующее квадратное уравнение $ x^2-2 x + 2=0 $ имеет корни мнимые $ \lambda_{1,2}=1 \pm \mathbf i $. Согласно приведенному выше алгоритму, решение представляется в виде:
$$
x_K=(1+\mathbf i)^{K-1}+(1-\mathbf i)^{K-1} \ .
$$
Здесь снова возникает парадоксальная ситуация: __вещественная__ целочисленная последовательность представляется с помощью __мнимых__ чисел. Разрешается "парадокс" теми же самыми рассуждениями, что и в предыдущем примере. Здесь можно пойти и дальше --- избавиться от мнимой единицы. Поскольку
$$
1+ \mathbf i = \sqrt{2} \left( \cos \frac{\pi}{4} + \mathbf i \sin \frac{\pi}{4} \right),
\quad
1- \mathbf i = \sqrt{2} \left( \cos \left( - \frac{\pi}{4} \right) +
\mathbf i \sin \left(-\frac{\pi}{4} \right) \right),
$$
то применением ((:complex_num#формула_муавра формулы Муавра)) получаем:
$$
x_K=2^{(K-1)/2}
\left( \cos \frac{(K-1)\pi}{4} + \mathbf i \sin \frac{(K-1)\pi}{4} \right) +
$$
$$
\qquad \qquad
+ 2^{(K-1)/2}\left( \cos \left( - \frac{(K-1)\pi}{4} \right) +
\mathbf i \sin \left(-\frac{(K-1)\pi}{4} \right) \right) =
$$
$$
=2^{(K+1)/2} \cos \frac{\pi(K-1)}{4} \ .
$$
Таким образом, мы избавились от кажущейся мнимости ответа. То, что на самом деле полученное число является числом целым подтверждается
тем, что последовательность
$$ \left\{ \cos \pi(K-1)/4 \right\}_{K=1}^{\infty} =
\left\{ 1, 2^{-1/2},0,-2^{-1/2},-1, -2^{-1/2}, 0, 2^{-1/2}, 1,\dots \right\}
$$
является циклической и выражения $ 2^{-1/2} $ возникают только при четных $ K_{} $.
При домножении на $ 2^{(K+1)/2} $ дробные степени двойки пропадают.
Резюмируем приведенные рассуждения: присутствие в ответе мнимой единицы, образно говоря,
само является //мнимым//, иллюзорным; в вычислениях она участвует, но в ответе пропадает!
♦
Остался нераскрытым секрет получения общего алгоритма решения разностного уравнения. Очевидно, что алгоритм приводит к верному ответу (что подтверждается подстановкой найденного решения в уравнение), но __откуда этот алгоритм взялся__?! :-/
Есть несколько подходов, приводящих к этому алгоритму --- и самый общий, подходящий для уравнений произвольного порядка, изложен ((#метод_производящего_ряда НИЖЕ)). А в рассмотренном выше случае уравнения второго порядка, рассуждения могут быть следующими. Сделаем в уравнении
$$
x_{K+2}=p x_{K+1}+q x_{K}
$$
замену переменных так, чтобы получилось линейное уравнение __первого__ порядка. С этой целью
подберем параметры $ t_{} $ и $ u_{} $ так, чтобы последовательность
$$ x_{K+2}- t x_{K+1} =u ( x_{K+1}- t x_{K}) $$
совпала с исходной. Очевидно, что параметры $ t_{} $ и $ u_{} $ можно найти из системы уравнений
$$ t+u=p,\ - tu=q \ . $$
Полученные формулы позволяют сделать вывод (см.
☞
((:polynomial#симметрические_функции_корней формулы Виета))), что $ t_{} $ и $ u_{} $ могут быть определены как корни квадратного уравнения
$$ x^2-px-q=0 \ , $$
которое и возникло у нас "из ниоткуда" в приведенном выше алгоритме. Предположим, что корни этого уравнения различны. Обозначив их, как и ранее, $ t= \lambda_1 $ и $ u= \lambda_2 $, и введя в рассмотрение новую последовательность $ \{y_K \}_{K=0}^{\infty} $, связанную со старой формулой
$$y_K= x_{K+1}- \lambda_1x_{K} , $$
мы получим уравнение для нее в виде
$$ y_{K+1} =\lambda_2 y_K \ . $$
Это уравнение снова разностное, но уже __первого__ порядка, его решение нам известно (геометрическая прогрессия):
$$ y_K = \lambda_2^K y_0 \ . $$
Возвращаемся к исходной переменной --- подставляем полученное в формулу, связывающую $ x_K $ и $ y_K $:
$$ x_{K+1}- \lambda_1x_{K}= \lambda_2^K y_0 \ npu \ y_0=x_1- \lambda_1 x_0 \ . $$
Мы снова получили разностное уравнение __первого__ порядка, но, к сожалению, уже неоднородное. Попробуем его решить. Распишем разностное уравнение для последовательных значений $ K $:
$$\begin{array}{ccr}
x_1-\lambda_1x_0 &= & y_0 \\
x_2-\lambda_1x_1 &= & \lambda_2y_0 \\
x_3-\lambda_1x_2 &= & \lambda_2^2y_0 \\
x_4-\lambda_1x_3 &= & \lambda_2^3y_0 \\
\dots & & \dots
\end{array}
$$
Умножим первое уравнение на $ \lambda_{1} $ и сложим со вторым, получим:
$$
x_2-\lambda_1^2 x_0 = (\lambda_1+ \lambda_2)y_0 \ .
$$
Умножим это уравнение на $ \lambda_1 $ и сложим с третьим:
$$
x_3-\lambda_1^3 x_0 = (\lambda_1^2+\lambda_1 \lambda_2 + \lambda_2)y_0 \ .
$$
Продолжив процесс далее по аналогии, на $ K_{} $-м шаге получим
$$
x_{K}-\lambda_1^K x_0 = (\lambda_1^{K-1}+\lambda_1^{K-2} \lambda_2 +\dots+ \lambda_1^{K-1-j}\lambda_2^j+\dots+ \lambda_2^{K-1})y_0 \ .
$$
В правой части полученного выражения стоит сумма геометрической прогрессии. Окончательно получаем:
$$
x_K= x_0 \lambda_1^K + \frac{\lambda_1^K-\lambda_2^K}{\lambda_1-\lambda_2}(x_1- \lambda_1 x_0)
\ ,
$$
что полностью совпадает с приведенным выше результатом.
!!?!! **[Эйлер].** Доказать, что (в обозначениях настоящего пункта) имеет место утверждение:
отношение
$$
\frac{x_{K+2}x_K-x_{K+1}^2}{(-q)^K}
$$
будет величиной постоянной, не зависящей от $ K_{} $.
=== Аналитика==
Для разностного уравнения
$$
x_{n+K}=a_1 x_{n+K-1}+ \dots+ a_n x_K
$$
алгебраическое уравнение, получающееся из него формальной заменой
$$
\begin{array}{llll}
x_{n+K} & x_{n+K-1} & \dots & x_K \\
\downarrow & \downarrow & \dots & \downarrow \\
\lambda^n & \lambda^{n-1} & \dots & 1
\end{array}
$$
то есть уравнение
$$ \lambda^n - a_1 \lambda^{n-1} - \dots - a_n =0, $$
называется **характеристическим уравнением** (соответствующим данному разностному уравнению)[[По исторической традиции переменную в характеристическом уравнении обозначают $ \lambda $.]]; полином
$$ f(\lambda)= \lambda^n - a_1 \lambda^{n-1} - \dots - a_n $$
будем называть **характеристическим полиномом** разностного уравнения. Обозначим $ \lambda_{1},\dots,\lambda_n $ все корни этого полинома, с учетом их ((:polynomial#основная_теорема_высшей_алгебры кратностей)).
!!Т!! **Теорема 1.** //Если все корни характеристического полинома различны, то решение разностного уравнения получается в виде//
$$ x_{K}= C_1\lambda_1^K + \dots+ C_n \lambda_n^K \ , $$
//числа// $ C_{1},\dots,C_n $ //не зависят от// $ K_{} $ //и определяются с помощью начальных условий из системы линейных уравнений//:
$$
\left\{\begin{array}{rrrrcl}
C_1 &+C_2 &+\dots &+ C_n &=& x_0 \\
\lambda_1 C_1 &+ \lambda_2C_2&+\dots & + \lambda_n C_n & = & x_1 \\
\lambda_1^2 C_1 &+ \lambda_2^2C_2&+\dots & + \lambda_n^2 C_n & = & x_2 \\
\dots &&&&& \dots \\
\lambda_1^{n-1}C_1 &+ \lambda_2^{n-1}C_2&+\dots & + \lambda_n^{n-1} C_n & = & x_{n-1}.
\end{array}
\right.
$$
Система линейных уравнений имеет единственное решение поскольку ее определитель отличен от нуля. (См.
☞
((:algebra2:vander#определитель определитель Вандермонда)), ((algebra2:linearsystems#формулы_крамера формулы Крамера)) ).
!!Т!! **Теорема 2.** //Если характеристический полином имеет следующее ((:polynomial#основная_теорема_высшей_алгебры разложение на линейные множители))://
$$f(\lambda)\equiv (\lambda-\lambda_1)^{{\mathfrak m}_1}\times \dots \times
(\lambda-\lambda_{\mathfrak r})^{{\mathfrak m}_{\mathfrak r}}, \quad
\lambda_k \ne \lambda_{\ell} \ \mbox{ при } \ k \ne \ell \ , {\mathfrak m}_1 + \dots + {\mathfrak m}_{\mathfrak r} =n, $$
//то общее решение разностного уравнения имеет вид://
$$
x_{K}=L_1(K)\lambda_1^{K} +\dots + L_{\mathfrak r}(K)\lambda_{\mathfrak r}^{K} ,
$$
//где// $ L_1(K),\dots,L_{\mathfrak r}(K) $ --- //полиномы от// $ K $ : $ L_p(K)\in \mathbb C[K],\ \deg L_p < {\mathfrak m}_p $.
Теперь разберем полученный результат, рассмотрев его частные случаи.
1.
Если характеристический полином имеет единственный корень $ \lambda_1 \ne 0 $, т.е.
$$ f(\lambda)\equiv (x-\lambda_1)^n , $$
то общее решение разностного уравнения имеет вид:
$$ x_{K}=(C_1+C_2K+C_3K^2+\dots+C_{n}K^{n-1})\lambda_1^K \ . $$
При заданных значениях $ x_0,x_1,\dots,x_{n-1} $ величины $ C_1,\dots,C_{n} $ могут быть определены из системы линейных уравнений, которая получается подстановкой в общее решение последовательных значений $ K \in \{0,1,\dots,n-1\} $:
$$
\left\{\begin{array}{lcllllll}
x_0 &=& \lambda_1^0&(C_1&+C_2\cdot 0& + C_3\cdot 0^2& + \dots &+ C_n\cdot 0^{n-1}) \\
x_1 &=& \lambda_1^1&(C_1&+C_2\cdot 1& + C_3\cdot 1^2& + \dots &+ C_n\cdot 1^{n-1}) \\
x_2 &=& \lambda_1^2&(C_1&+C_2\cdot 2& + C_3\cdot 2^2& + \dots &+ C_n\cdot 2^{n-1}) \\
\dots & & \dots \\
x_{n-1}&=& \lambda_1^{n-1}&(C_1&+C_2\cdot (n-1)& + C_3\cdot (n-1)^2& + \dots &+ C_n\cdot (n-1)^{n-1})
\end{array} \right.
$$
Образно говоря: если получена __общая__ закономерность, то она должна быть __универсальной__, т.е.
сохраняться и в __частных__ случаях.
И вновь мы можем гарантировать единственность решения этой системы --- на основе тех же аргументов, что и в случае теоремы 1. Фактически же мы получили классическую задачу построения ((:interpolation интерполяционного полинома)) по его значениям в равноотстоящих узлах.
!!П!!** Пример.** Решить уравнение четвертого порядка
$$x_{K+4}=4\,x_{K+3}-6\,x_{K+2}+4\,x_{K+1}-x_{K} . $$
**Решение.** Характеристический полином $ (\lambda-1)^4 $ имеет единственный корень $ \lambda_1=1 $.
Общее решение ищется в виде $ x_{K}=C_1+C_2K+C_3K^2+C_4K^3 $, а при заданных начальных данных константы $ C_p $ определяются либо из приведенной выше системы линейных уравнений, либо же
по одному из методов нахождения интерполяционного полинома. Так, для $ x_0=1,x_1=8,x_2=27,x_3=64 $ получаем $ C_1=1,C_2=3,C_3=3,C_4=1 $. Тогда выражение
для общего члена рекуррентной последовательности $ x_{K}=(K+1)^3 $ --- ответ вполне ожидаемый, если обратить внимание на начальные данные... ;-)
♦
{{users:au:scriber.jpg |}}
\\
\\
\\
Статья не закончена!
==== Метод производящего ряда==
В этом и следующем пунктах укажем два подхода, которые позволяют __вывести__ естественным путем результаты, сформулированные в теоремах предыдущего пункта.
Распишем разностное уравнение
$$
x_{n+K}=a_1 x_{n+K-1}+ \dots+ a_n x_K
$$
в бесконечную последовательность уравнений, положив $ K=0,1,2,\dots $:
$$
\begin{array}{llllcl}
x_{n}&-a_1 x_{n-1}&-a_2 x_{n-2}&- \dots- a_n x_0&=&0, \\
x_{n+1}&-a_1 x_{n}&- a_2 x_{n-1}&- \dots- a_n x_1&=&0, \\
\vdots & & & & & \vdots \\
x_{n+K}&-a_1 x_{n+K-1}&-a_2 x_{n+K-2}&- \dots- a_n x_K&=&0, \\
\dots & & &&&\dots
\end{array}
$$
и дополним эту последовательность, поставив в ее начало еще $ n $ уравнений:
$$
\begin{array}{llllcl}
x_{0}&&&&=&p_0, \\
x_{1}&-a_1 x_{0}& &&=& p_1, \\
x_{2}&-a_1 x_{1}&-a_2 x_{0}& &=& p_1, \\
\vdots && & & & \vdots \\
x_{n-1}&-a_1 x_{n-2}&-a_2 x_{n-3}&- \dots- a_{n-1} x_0 &=& p_{n-1},
\end{array}
$$
При заданных начальных данных $ \{x_0,x_1,\dots,x_{n-1} \} $ из этих уравнений можно однозначно определить числа $ \{p_0,p_1,\dots,p_{n-1} \} $.
В объединенной системе произведем домножение уравнений на степени $ \lambda $
$$
\begin{array}{lllllcl|l}
x_{0}&&&&&=&p_0, & \times 1 \\
x_{1}&-a_1 x_{0}&& &&=& p_1, & \times \lambda \\
x_{2}&-a_1 x_{1}&-a_2 x_{0}& &&=& p_1, & \times \lambda^2 \\
\vdots && & & && \vdots & \vdots \\
x_{n-1}&-a_1 x_{n-2}&-a_2 x_{n-3}&- \dots- a_{n-1} x_0 &&=& p_{n-1}, & \times \lambda^{n-1} \\
x_{n}&-a_1 x_{n-1}&-a_2 x_{n-2}&- \dots - a_{n-1} x_1 & - a_n x_0&=&0, & \times \lambda^{n} \\
x_{n+1}&-a_1 x_{n}&- a_2 x_{n-1}&- \dots - a_{n-1} x_2 & - a_n x_1&=&0, & \times \lambda^{n+1} \\
\vdots & & & \dots & & & \dots & \vdots \\
x_{n+K}&-a_1 x_{n+K-1}&-a_2 x_{n+K-2}&- \dots- a_{n-1} x_{K+1} &- a_n x_K&=&0, & \times \lambda^{n+K} \\
\dots & & && &&\dots & \dots
\end{array}
$$
и сложим эти уравнения, собирая по столбцам коэффициенты при $ a_1,\dots, a_n $.
Ряд
$$
Z(\lambda)=\sum_{j=0}^{\infty}x_{j}\lambda^j=x_0+x_1\lambda+x_2\lambda^2+\dots+x_K \lambda^K + \dots
$$
называется **производящим рядом** рекуррентной последовательности.
Мы получили для него уравнение
$$ Z(\lambda)-a_1\lambda Z(\lambda)-a_2\lambda^2Z(\lambda)-\dots - a_n\lambda^n Z(\lambda)\equiv p_0+p_1\lambda+p_2\lambda^2+\dots+p_{n-1}\lambda^{n-1} \,
$$
или
$$
Z(\lambda)(1-a_1\lambda-a_2\lambda^2-\dots- a_n\lambda^n) \equiv P(\lambda) \ ,
$$
где $ P(\lambda)=p_0+p_1\lambda+p_2\lambda^2+\dots+p_{n-1}\lambda^{n-1} $ --- известный полином. Таким образом производящий ряд получается разложением в ряд по степеням $ \lambda $ рациональной функции
$$
\frac{P(\lambda)}{1-a_1\lambda-a_2\lambda^2-\dots- a_n\lambda^n}
$$
и, если нам удастся найти явное выражение для коэффициента при $ \lambda^K $, то он и будет решением разностного уравнения.
Полином $ f^{\ast}(\lambda) = 1-a_1\lambda-a_2\lambda^2-\dots- a_n\lambda^n $ не совпадает с ((#аналитика характеристическим полиномом))
$ f(\lambda)= \lambda^n-a_1\lambda^{n-1}-a_2\lambda^{n-2}- \dots - a_n $ разностного уравнения, но очень на него похож: они связаны соотношением
$$ f^{\ast}(\lambda) \equiv \lambda^n f(1/\lambda) \ , $$
и корни $ f^{\ast}(\lambda) $ равны обратным величинам корней полинома $ f(\lambda) $, т.е. $ 1/\lambda_1,\dots,1/\lambda_n $ (см. свойство
3
☞
((polynomial#преобразования_корней ЗДЕСЬ)) ). Если все эти корни различны, то дробь $ 1/f^{\ast}(\lambda) $ может быть разложена на простейшие дроби вида:
$$
\frac{1}{f^{\ast}(\lambda)}=\frac{1}{(1-\lambda_1 \cdot \lambda)(1-\lambda_2 \cdot \lambda)\times \dots \times (1-\lambda_n \cdot \lambda)} =
$$
$$
=\frac{\gamma_1}{1-\lambda_1 \cdot \lambda}+\frac{\gamma_2}{1-\lambda_2 \cdot \lambda}+\dots+\frac{\gamma_n}{1-\lambda_n \cdot \lambda} \ ,
$$
где $ \gamma_1, \gamma_2,\dots, \gamma_n $ --- комплексные числа, которые можно однозначно выразить через $ \lambda_1,\dots,\lambda_n $ (эти выражения для дальнейшего несущественны). Теперь каждую простейшую дробь раскладываем в степенной ряд:
$$
\frac{\gamma_j}{1-\lambda_j \cdot \lambda}=\gamma_j \left(1+\lambda_j \cdot \lambda+
\lambda_j^2 \cdot \lambda^2+\dots+ \lambda_j^K \cdot \lambda^K+\dots \right)
$$
и, следовательно, получаем разложение для производящего ряда
$$
Z(\lambda)=\frac{P(\lambda)}{1-a_1\lambda-a_2\lambda^2-\dots- a_n\lambda^n}=
$$
$$
=P(\lambda) \left[ (\gamma_1+\dots+\gamma_n)+(\gamma_1\lambda_1+\dots+\gamma_n\lambda_n)\lambda+\dots+(\gamma_1\lambda_1^K+\dots+\gamma_n\lambda_n^K)\lambda^K + \dots \right] \ .
$$
Вытаскиваем из него коэффициент при $ \lambda^K $:
$$
\begin{array}{lcl}
p_0 (\gamma_1\lambda_1^K &+\dots+&\gamma_n\lambda_n^K)+ \\
+p_1(\gamma_1\lambda_1^{K-1}&+\dots+&\gamma_n\lambda_n^{K-1})+ \\
&+\dots + &\\
+p_{n-1} (\gamma_1\lambda_1^{K-n+1}&+\dots+&\gamma_n\lambda_n^{K-n+1})=
\end{array}
$$
и просуммируем по столбцам:
$$
\begin{array}{c}
= \gamma_1\lambda_1^K (p_0+p_1/\lambda_1+\dots+p_{n-1}/\lambda_1^{n-1})+\\
+ \gamma_2\lambda_2^K (p_0+p_1/\lambda_2+\dots+p_{n-1}/\lambda_2^{n-1})+ \\
+\dots + \\
+ \gamma_n\lambda_n^K (p_0+p_1/\lambda_n+\dots+p_{n-1}/\lambda_n^{n-1})=
\end{array}
$$
$$
=\gamma_1 P(1/\lambda_1)\lambda_1^K+ \gamma_2 P(1/\lambda_2)\lambda_2^K +\dots + \gamma_n P(1/\lambda_n)\lambda_n^K \ .
$$
Обозначив $ C_j = \gamma_j P(1/\lambda_j) $ при $ j\in \{1,\dots,n\} $, мы получим общее решение разностного уравнения приведенное в теореме 1 предыдущего пункта.
Метод производящего ряда позволяет решать и неоднородные разностные уравнения.
!!П!! **Пример.** Решить уравнение
$$x_{K+2}=3\,x_{K+1}-2\,x_{K}+(K+1)(K+2) \ . $$
**Ответ.** $ x_K=2^K(x_1-x_0+8)-1/3(K+3)(K^2+3\,K+8)+2\,x_0-x_1 $.
{{users:au:scriber.jpg |}}
\\
\\
\\
Статья не закончена!
==== Метод матричной степени==
Для понимания материалов настоящего пункта рекомендуется ознакомиться с разделом ((:algebra2:funmatrix#reshenie_linejnogo_raznostnogo_uravnenija ФУНКЦИЯ ОТ МАТРИЦЫ)).
Пусть рекуррентная последовательность задается уравнением
$$
x_{n+K}=a_1 x_{n+K-1}+ \dots+ a_n x_K
$$
и начальными данными $ x_0,x_1,\dots,x_{n-1} $.
Введем в рассмотрение столбцы, состоящие из $ n_{} $ последовательных элементов этой последовательности, обозначив
$$
X_0=\left( \begin{array}{l}
x_0 \\ x_1 \\ \vdots \\ x_{n-1}
\end{array}
\right),\ X_1=\left( \begin{array}{l}
x_1 \\ x_2 \\ \vdots \\ x_{n}
\end{array}
\right),\ X_2=\left( \begin{array}{l}
x_2 \\ x_3 \\ \vdots \\ x_{n+1}
\end{array}
\right),\ \dots,
X_K=\left( \begin{array}{l}
x_K \\ x_{K+1} \\ \vdots \\ x_{K+n-1}
\end{array}
\right),\dots ;
$$
а также следующую матрицу, известную как **матрица Фробениуса**:
$$
{\mathfrak F}=
\left( \begin{array}{lllllll}
0 & 1 & 0 & 0 & \dots & 0 & 0 \\
0 & 0 & 1 & 0 & \dots & 0 & 0 \\
0 & 0 & 0 & 1 & \dots & 0 & 0 \\
\dots& &&&\ddots & & \dots \\
0 & 0 & 0 & 0 & \dots & 0 & 1 \\
a_n & a_{n-1} & a_{n-2} & & \dots & a_2 & a_1
\end{array} \right)_{n \times n}
$$
Используя правило ((:algebra2#умножение_матриц умножения матриц)), а также соотношение между элементами последовательности, получаем:
$$
X_1={\mathfrak F}X_0,\ X_2={\mathfrak F}X_1,\dots, X_K={\mathfrak F}X_{K-1},\dots,
$$
откуда имеем:
$$
X_K={\mathfrak F}^KX_0 \quad npu \quad K\in \mathbb N \ .
$$
Искомое выражение для $ x_{K} $ получится умножением первой строки матрицы
$ {\mathfrak F}^K $ на столбец начальных данных $ X_{0} $. Таким образом, задача решения разностного уравнения сводится к задаче возведения в степень матрицы $ {\mathfrak F} $.
Для нахождения $ {\mathfrak F}^{K} $ воспользуемся результатами пункта ((:algebra2:funmatrix#структура_степенной_функции СТРУКТУРА СТЕПЕННОЙ ФУНКЦИИ)). Найдя
жорданову нормальную форму (**ЖНФ**) $ {\mathfrak F}_{\mathfrak J} $ и соответствующую матрицу
преобразования базиса $ C_{} $, получим
$$
{\mathfrak F}_{\mathfrak J} =C^{-1} \mathfrak F C \Longrightarrow
{\mathfrak F}^{K}=C {\mathfrak F}_{_{\mathfrak J}}^{K} C^{-1} \, .
$$
((:algebra2:charpoly#характеристический_полином Характеристический полином матрицы Фробениуса)):
$$\det ({\mathfrak F}- \lambda E)=
(-1)^n(\lambda^n-a_1 \lambda^{n-1}-\dots-a_n) \ .
$$
с точностью до знака совпадает с характеристическим полиномом последовательности.
Обозначим его корни $ \lambda_1,\dots,\lambda_n $. Если они различны, то жорданова нормальная форма $ {\mathfrak F}_{_{\mathfrak J}} $ ((:mapping:operator#диагонализуемость_матрицы_оператора диагональна)). Если же среди этих корней имеются кратные, то установление структуры **ЖНФ** потребует усилий; однако же можно заранее утверждать, что эта форма диагональной не будет.
!!§!! Подробный дальнейший анализ (с выводом теорем $ 1_{} $ и $ 2_{} $ из пункта ((#аналитика АНАЛИТИКА)))
☞
((:recurr:vspom2 ЗДЕСЬ)).
====Cистемы линейных разностных уравнений==
Подход предыдущего пункта можно успешно распространить на системы линейных разностных уравнений.
!!П!! **Пример.** Решить систему разностных уравнений
$$
\left\{\begin{array}{rrrr}
x_{K}&=&x_{K-1} &+2\,y_{K-1} \\
y_{K}&=&3\,x_{K-1}&+2\,y_{K-1}
\end{array} \qquad npu \quad \begin{array}{l} x_0=1, \\ y_0=-1. \end{array}
\right.
$$
**Решение.** Имеем:
$$
\left(
\begin{array}{r}
x_{K} \\ y_{K}
\end{array}
\right) =
\left(
\begin{array}{rr}
1 & 2 \\
3 & 2
\end{array}
\right)
\left(
\begin{array}{r}
x_{K-1} \\ y_{K-1}
\end{array}
\right)=
\left(
\begin{array}{rr}
1 & 2 \\
3 & 2
\end{array}
\right)^2
\left(
\begin{array}{r}
x_{K-2} \\ y_{K-2}
\end{array}
\right)=\dots=
\left(
\begin{array}{rr}
1 & 2 \\
3 & 2
\end{array}
\right)^K
\left(
\begin{array}{r}
x_{0} \\ y_{0}
\end{array}
\right)\ .
$$
Возводим матрицу в степень по методу, изложенному в разделе
☞
((:algebra2:funmatrix#структура_степенной_функции ВЫЧИСЛЕНИЕ ФУНКЦИИ ОТ МАТРИЦЫ)). Ее ((:algebra2:charpoly характеристический полином)) $ f(\lambda)=\lambda^2-3\, \lambda - 4 $ имеет корни $ \{-1,4\} $.
Соответствующие собственные векторы $ [1,-1]^{\top} $ и $ [2,3]^{\top} $. Следовательно:
$$
\left(
\begin{array}{rr}
1 & 2 \\
3 & 2
\end{array}
\right)^K=
\left(
\begin{array}{rr}
1 & 2 \\
-1 & 3
\end{array}
\right)
\left(
\begin{array}{cc}
(-1)^K & 0 \\
0 & 4^K
\end{array}
\right)
\left(
\begin{array}{rr}
1 & 2 \\
-1 & 3
\end{array}
\right)^{-1} =
$$
$$
=\frac{1}{5}
\left(
\begin{array}{rr}
3\cdot (-1)^K + 2 \cdot 4^K & 2 \cdot (-1)^{K+1} + 2 \cdot 4^K \\
3\cdot (-1)^{K+1} + 3 \cdot 4^K & 2 \cdot (-1)^{K} + 3 \cdot 4^K
\end{array}
\right) \ .
$$
Домножение этой матрицы на столбец $ [x_0,y_0]^{\top}=[1,-1]^{\top} $ приводит к ответу $ x_K=(-1)^K, y_K=(-1)^{K+1} $, который немедленно проверяется "вручную" ;-).
Приведем альтернативное решение настоящего примера --- "разделим" переменные. Сделаем подстановку $ K \to K+1 $ в первом уравнении:
$$ x_{K+1}=x_K+2\,y_K=(x_{K-1} +2\,y_{K-1})+2\, (3\,x_{K-1}+2\,y_{K-1})=7\,x_{K-1}+6\,y_{K-1} \ . $$
Теперь из двух уравнений --- нового и исходного --- исключим $ y_{K-1} $:
$$
\left\{
\begin{array}{rrrr}
x_{K}&-x_{K-1} &= & 2\,y_{K-1} \\
x_{K+1}&-7\,x_{K-1}&=&6\,y_{K-1}
\end{array}
\right. \quad \Rightarrow \quad x_{K+1}-3\,x_{K}-4\,x_{K-1}=0 \ .
$$
Мы получили разностное уравнение второго порядка относительно величины $ x_{K} $. Совершенно такое же уравнение получается и относительно другой переменной: $ y_{K+1}-3\,y_{K}-4\,y_{K-1}=0 $. Характеристический полином этого уравнения совпадает с характеристическим полиномом матрицы. Различие между генерируемыми этим уравнением рекуррентными последовательностями $ \{x_K\}_{K=0}^{\infty} $ и
$ \{y_K\}_{K=0}^{\infty} $ будет определяться только начальными данными.
♦
!!П!! **Пример.** Решить систему разностных уравнений
$$
\left\{\begin{array}{rrrrrr}
x_{K}&=&2\,x_{K-1} &-3\,y_{K-1}&+2\,x_{K-2}&+2\,y_{K-2} \\
y_{K}&=&-x_{K-1} &-y_{K-1}&+4\,x_{K-2}&+2\,y_{K-2}
\end{array} \qquad npu \quad
\begin{array}{ll} x_0=1, & y_0=0, \\ x_1=1, & y_1=1.
\end{array}
\right.
$$
**Решение.** Перепишем уравнения в матричном виде: пусть
$$
Z_K=
\left(
\begin{array}{r}
x_{K} \\ y_{K}
\end{array}
\right),\
\mathbf A_1 =
\left(
\begin{array}{rr}
2 & -3 \\
-1 & -1
\end{array}
\right), \
\mathbf A_2 =
\left(
\begin{array}{rr}
2 & 2 \\
4 & 2
\end{array}
\right) \ .
$$
Тогда
$$
Z_K=\mathbf A_1 Z_{K-1}+ \mathbf A_2 Z_{K-2} \quad npu
\quad Z_0=\left(
\begin{array}{r}
1 \\ 0
\end{array}
\right),\
Z_1=\left(
\begin{array}{r}
1 \\ 1
\end{array}
\right) \ .
$$
Теперь с полученным векторным разностным уравнением будем действовать --- по образу и подобию предыдущего пункта --- как если бы это уравнение было скалярным:
$$
\left(
\begin{array}{l}
Z_{K-1} \\ Z_{K}
\end{array}
\right)_{4\times 1} =
\left(
\begin{array}{ll}
\mathbb O & E \\
\mathbf A_2 & \mathbf A_1
\end{array}
\right)_{4\times 4}
\left(
\begin{array}{l}
Z_{K-2} \\ Z_{K-1}
\end{array}
\right) ;
$$
здесь $ E_{} $ --- единичная матрица $ 2_{} $-го порядка. Далее, алгоритм идет стандартным ходом.
Вычисляем ((:algebra2:charpoly характеристический полином)) получившейся блочной матрицы
$$
\left|
\begin{array}{cc}
-\lambda E & E \\
\mathbf A_2 & \mathbf A_1-\lambda E
\end{array}
\right|=\det(\mathbf A_2+ \mathbf A_1 \lambda-\lambda^2 E) =
\left|
\begin{array}{cc}
-\lambda^2+2\lambda+2 & -3\lambda+2\\
-\lambda+4 & -\lambda^2-\lambda+2
\end{array}
\right|=
$$
$$
=\lambda^4-\lambda^3-9\,\lambda^2+16\,\lambda-4 \equiv (\lambda-2)^2\left(\lambda-\left[-\frac{3}{2}+\frac{\sqrt{13}}{2} \right] \right)\left(\lambda-\left[-\frac{3}{2}-\frac{\sqrt{13}}{2} \right] \right) \ .
$$
Решение уравнения следует искать в виде
$$
(C_1+C_2K)2^K+C_3 \left[-\frac{3}{2}+\frac{\sqrt{13}}{2} \right]^K+C_4 \left[-\frac{3}{2}-\frac{\sqrt{13}}{2} \right]^K \ ;
$$
причем это утверждение справедливо как для $ \{x_K\} $, так и для $ \{y_K\} $. К примеру, установив из разностных уравнений, что при заданных начальных данных имеет место $ x_2=1,x_3=0 $, определяем значения констант $ \{C_j\} $ из системы линейных уравнений и получаем:
$$
x_K=
\left(\frac{55}{81}-\frac{2}{9} K\right)2^K+\left(\frac{13}{81}+\frac{46\sqrt{13}}{1053} \right)\left[-\frac{3}{2}+\frac{\sqrt{13}}{2} \right]^K+
$$
$$
+\left(\frac{13}{81}
-\frac{46\sqrt{13}}{1053} \right)\left[-\frac{3}{2}-\frac{\sqrt{13}}{2} \right]^K \ .
$$
♦
=== Асимптотика ==
**Задача.** Как ведет себя рекуррентная последовательность $ \{x_K\}_{K=0}^{\infty} $ при
возрастании $ K $?
Если при любых $ x_0,\dots,x_{n-1} $ решение $ x_K $ уравнения
$$
x_{n+K}=a_1 x_{n+K-1}+ \dots+ a_n x_K
$$
ограничено, то будем называть это уравнение **устойчивым**.
Устойчивое уравнение называется **асимптотически устойчивым** если
$$ x_K \to 0 \quad npu \quad K \to \infty \ .$$
Уравнение называется **неустойчивым**, если существует хотя бы один
набор $ x_0,\dots,x_{n-1} $, для которого соответствующая последовательность
$ x_K $ неограничена.
Для анализа асимптотики $ \{ x_K \} $ при $ K \to \infty $ обратимся к приведенным
☝
((#аналитика ВЫШЕ)) теоремам 1 и 2, в которых общее решение разностного уравнения выражено через корни $ \lambda_1,\dots,\lambda_n $ его характеристического уравнения.
!!Т!! **Теорема.**// Уравнение//
$$
x_{n+K}=a_1 x_{n+K-1}+ \dots+ a_n x_K
$$
//будет//
**а)** //устойчивым тогда и только тогда, когда//
$ |\lambda_j| \le 1 $ //для любого// $ j_{} $, //и собственные числа, имеющие модуль равный// $ 1_{} $,
//являются ((:polynomial#основная_теорема_высшей_алгебры простыми)) для характеристического полинома;//
**б)** //асимптотически устойчивым тогда и только тогда, когда//
$ |\lambda_j| < 1 $ для любого $ j_{} $.
Конструктивная проверка условий теоремы возможна чисто алгебраическими методами: проверкой $ n_{} $ неравенств критерия ((:polynomial#единичный_круг Шура-Кона)) на коэффициенты характеристического полинома.
!!П!! **Пример.** Найти все значения параметра $ {\color{Red}{ \alpha} } $, при которых
уравнение
$$ x_{K+5}=\frac{1}{5}(x_{K+4}-({\color{Red}{ \alpha} } -4)x_{K+3}+({\color{Red}{ \alpha} }-2)x_{K+2}+x_{K+1}+x_{K})
$$
будет устойчиво.
**Решение.** Характеристический полином уравнения равен
$$
f(\lambda)=\frac{1}{5}\left(5\,\lambda^5-\lambda^4+(-4+{\color{Red}{ \alpha} } )\,\lambda^3+
(-{\color{Red}{ \alpha} } +2)\,\lambda^2-\,\lambda-1\right)\equiv
$$
$$
\equiv \frac{1}{5}(\lambda-1)
\underbrace{\left(5\,\lambda^4+4\,\lambda^3+{\color{Red}{ \alpha} }\,\lambda^2+2\,\lambda+1 \right)}_
{f_1(\lambda)} \ .
$$
К полиному $ f_1(\lambda) $ нужно применить алгоритм теоремы Шура-Кона; и это сделано
☞
((:polynomial#единичный_круг ЗДЕСЬ)). Условие $ 0< {\color{Red}{ \alpha} } < \frac{27}{4} $
является необходимым и достаточным
для того, чтобы все корни $ f_1(\lambda) $ лежали внутри единичного круга.
При $ {\color{Red}{ \alpha} } =0 $ полином $ f_1(\lambda) $ имеет корень $ \lambda=-1 $;
при $ {\color{Red}{ \alpha} } = \frac{27}{4} $
полином $ f_1(\lambda) $ будет обладать комплексно-сопряженными корнями
с модулями равными 1: $ \lambda_{1,2}= -\frac{1}{4}\pm {\mathbf i}
\frac{\sqrt{15}}{4} $.
В обоих этих "пограничных" случаях полином $ f(\lambda) $
удовлетворяет условию **а)** теоремы.
**Ответ.** Уравнение устойчиво при $ 0\le {\color{Red}{ \alpha} } \le \frac{27}{4} $.
!!?!! **[Шеннон]**((#источники [3])). Вычислить
$$ \lim_{K\to \infty} \frac{\log_2x_K}{K} \quad npu \quad
x_{K+10}=x_{K+8}+x_{K+6}+x_{K+5}+x_{K+3}+x_{K+2}+x_{K} $$
и хотя бы одном из чисел $ \{x_0,x_2,x_3,x_5,x_6,x_8\} $ отличном от нуля.
Случай существования простого собственного числа равного $ \pm 1 $
или пары простых комплексно-сопряженных чисел равных по модулю $ 1_{} $,
при прочих меньших $ 1_{} $ по модулю,
оказывается "пограничным" при исследовании сходимости: решение уравнения
оказывается ограниченным, но существует ли у него предел?
В терминах ((#метод_матричной_степени матрицы Фробениуса)) $ \mathfrak F $
вопрос этот равносилен существованию конечного $ \displaystyle \lim_{K\to +\infty} \mathfrak F^K $.
!!?!! **[Марков]**((#источники [4])). Вычислить
$$ \lim_{K\to +\infty} x_K \quad npu \quad x_{K+3}=\frac{1}{3}(x_{K+2}+x_{K+1}+x_{K}) $$
в зависимости от $ x_0,x_1,x_2 $.
Cлучай из последнего замечания кажется исключительным, //маловероятным//: в самом деле, трудно ожидать, что //случайным// образом составленное разностное уравнение будет иметь характеристический полином с корнем равным $ 1_{} $. Здравый смысл, однако же, нас здесь подводит: реальный мир играет вероятностями --- см. следующий пункт!
=== Задача о разорении игрока ==
Для понимания материалов настоящего пункта рекомендуется ознакомиться с разделом ((:probability ТЕОРИЯ ВЕРОЯТНОСТЕЙ)).
**Задача.** Пусть игрок обладает конечным капиталом $ K\in \mathbb N $ и
участвует с ним в игре, где имеется вероятность $ p(K) $ увеличения его
капитала до $ K+1 $ и вероятность $ q(K)=1-p(K) $ сокращения его до $ K-1 $.
Пусть, кроме того, игрок согласен делать ставки до тех пор, пока он
либо накопит капитал $ N $, либо потеряет все свои деньги: $ K=0 $.
Какова вероятность того, что при заданных $ p(1),\dots,p(N-1) $
игрок достигнет своей цели прежде, чем разорится?
Введем в рассмотрение функцию
$$
u(K,N)=\left\{ \begin{array}{c} \mbox{ вероятность того, что игрок, начиная с капиталом } \ K, \\
\mbox{ накопит капитал } \ N \ \mbox{ прежде, чем разорится} \end{array} \right\}.
$$
На каждом шаге игрок либо выигрывает с вероятностью $ p(K) $ и тогда
вероятность успешного окончания игры становится равной $ u(K+1,N) $,
либо проигрывает с вероятностью $ q(K) $ и тогда
вероятность успешного окончания игры становится равной $ u(K-1,N) $.
{{ :game_ov.png?600 |}}
В соответствии с теоремами об умножении и сложении вероятностей (см.
☞
((:probability ЗДЕСЬ)) )
для вероятности $ u(K,N) $ получаем следующую формулу:
$$
u(K,N)=p(K) u(K+1,N) +q(K) u(K-1,N) .
$$
При $ K=0 $ и $ K=N $ задаются ограничения "окончания игры":
$$
u(0,N)=0 \quad (\mbox{ игрок проиграл все деньги}),
$$
$$
u(N,N)=1 \quad (\mbox{ игрок выиграл капитал } \quad N).
$$
Полученное уравнение --- разностное второго порядка :
$$u(K+1,N)=\frac{1}{p(K)} u(K,N) -\frac{q(K)}{p(K)} u(K-1,N) \ ,$$
но в отличие от предыдущих пунктов, вместо начальных условий здесь задаются граничные.
Решим задачу в ее "стационарном" варианте, т.е. считаем вероятность
$ p(K) $ не зависящей от $ K $:
$$p(K)=p,\ q(K)=q=1-p \ ;$$
тогда
$$
u(K+1,N)=\frac{1}{p} u(K,N) -\frac{q}{p} u(K-1,N) \ .
$$
Следуя ((#аналитика общей схеме)) решения такого уравнения, найдем корни
характеристического полинома
$$f(\lambda)=\lambda^2-\frac{1}{p}\lambda+\frac{q}{p}=(\lambda-1)\left(\lambda-
\frac{q}{p}\right) \ .$$
Дальнейший ход решения задачи зависит от
того, является ли $ 1 $ простым или кратным корнем этого полинома.
1.
Пусть $ q\ne p $. Применяем ((#аналитика теорему 1)):
$$u(K,N)=C_1 1^K+C_2 (q/p)^K=C_1+C_2 (q/p)^K .$$
Константы $ C_j $ находим из граничных условий:
$$ \left\{ \begin{array}{ccc}
C_1+C_2&=&0 \\
C_1+(q/p)^NC_2&=&1
\end{array} \right. \Longrightarrow
C_1=-C_2=\frac{1}{1-(q/p)^N}
$$
$$\Longrightarrow u(K,N)= \frac{1-(q/p)^K}{1-(q/p)^N} \quad npu \
K\in\{0,\dots,N\} .$$
2.
Пусть теперь $ q=p=\frac{1}{2} $ (проигрыш и выигрыш равновероятны).
Применяем ((#аналитика теорему 2)):
$$ u(K,N)=(C_1+C_2K)\cdot 1^{K-2} \, . $$
Константы
находим из граничных условий: $ C_1=0,C_2=1/N $. Следовательно:
$$u(K,N)=K/N \quad npu \ K\in\{0,\dots,N\} \ .$$
Теперь проанализируем полученные решения. Во втором случае выигрыш тем
вероятнее, чем больше стартового капитала имеет игрок, и при $ K>N/2 $
игрок скорее выиграет. В первом случае анализ ситуации несколько
сложнее, хотя зависимость вероятности выигрыша от размера стартового капитала
сохраняется. Рассмотрим более интересный случай $ p
☞