Будем обозначать через $ \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} $ заданы. Тогда уравнение определяет линейную рекуррентную¹⁾(или возвратную) последовательность $ \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) $). Подробнее ☞ ЗДЕСЬ.

Пример. Примером линейной рекуррентной последовательности $ n_{} $-го порядка может служить последовательность сумм Ньютона полинома $ n_{} $-й степени. Подробнее ☞ ЗДЕСЬ.

Задача. Решить разностное уравнение, т.е. найти выражение для $ 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_{} $. Примером таких рекуррентных последовательностей являются континуанты. Можно пойти еще дальше и рассматривать разностные уравнения, решениями которых являются не числа, а полиномы: $$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) \} $, удовлетворяющие этому уравнению, известны как полиномы Лежандра.

Наконец, в некоторых разделах математики встречаются и нелинейные разностные уравнения, см. ☞ ЧИСЛА КАТАЛАНА.

Настоящий раздел посвящен, в основном, линейным уравнениям с постоянными коэффициентами.

Известны первые члены линейной рекуррентной последовательности:

$$ 0,1,2,2,0,-9,-38,-123,-360,-1004,-2728,-7303,\ldots $$ Чему равен следующий?

Общий принцип решения подобных задач (т.е. как установить по последовательности вид линейного уравнения, которое ее, возможно, задает) ☞ ЗДЕСЬ.

Решим сначала уравнение второго порядка $$ 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] \ . $$ ♦

Пример. Решить уравнение $$ 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), $$ то применением формулы Муавра получаем: $$ 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 \ . $$ Полученные формулы позволяют сделать вывод (см. ☞ формулы Виета), что $ 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, $$ называется характеристическим уравнением (соответствующим данному разностному уравнению)²⁾; полином $$ f(\lambda)= \lambda^n - a_1 \lambda^{n-1} - \dots - a_n $$ будем называть характеристическим полиномом разностного уравнения. Обозначим $ \lambda_{1},\dots,\lambda_n $ все корни этого полинома, с учетом их кратностей.

Теорема 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. $$

Теорема 2. Если характеристический полином имеет следующее разложение на линейные множители:

$$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. $$ Образно говоря: если получена общая закономерность, то она должна быть универсальной, т.е. сохраняться и в частных случаях.

Пример. Решить уравнение четвертого порядка $$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 $ — ответ вполне ожидаемый, если обратить внимание на начальные данные… ♦

Статья не закончена!

В этом и следующем пунктах укажем два подхода, которые позволяют вывести естественным путем результаты, сформулированные в теоремах предыдущего пункта.

Распишем разностное уравнение $$ 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 ☞ ЗДЕСЬ ). Если все эти корни различны, то дробь $ 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 $.

Статья не закончена!

Пусть рекуррентная последовательность задается уравнением $$ 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} $$ Используя правило умножения матриц, а также соотношение между элементами последовательности, получаем: $$ 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} $ воспользуемся результатами пункта СТРУКТУРА СТЕПЕННОЙ ФУНКЦИИ. Найдя жорданову нормальную форму (ЖНФ) $ {\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} \, . $$ Характеристический полином матрицы Фробениуса: $$\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}} $ диагональна. Если же среди этих корней имеются кратные, то установление структуры ЖНФ потребует усилий; однако же можно заранее утверждать, что эта форма диагональной не будет.

Подробный дальнейший анализ (с выводом теорем $ 1_{} $ и $ 2_{} $ из пункта АНАЛИТИКА) ☞ ЗДЕСЬ.

Подход предыдущего пункта можно успешно распространить на системы линейных разностных уравнений.

Пример. Решить систему разностных уравнений

$$ \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)\ . $$ Возводим матрицу в степень по методу, изложенному в разделе ☞ ВЫЧИСЛЕНИЕ ФУНКЦИИ ОТ МАТРИЦЫ. Ее характеристический полином $ 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_{} $-го порядка. Далее, алгоритм идет стандартным ходом. Вычисляем характеристический полином получившейся блочной матрицы $$ \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_{} $, являются простыми для характеристического полинома;

б) асимптотически устойчивым тогда и только тогда, когда $ |\lambda_j| < 1 $ для любого $ j_{} $.

Конструктивная проверка условий теоремы возможна чисто алгебраическими методами: проверкой $ n_{} $ неравенств критерия Шура-Кона на коэффициенты характеристического полинома.

Пример. Найти все значения параметра $ {\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) $ нужно применить алгоритм теоремы Шура-Кона; и это сделано ☞ ЗДЕСЬ. Условие $ 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\} $ отличном от нуля.

[Марков][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 $.

Задача. Пусть игрок обладает конечным капиталом $ 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) $.

В соответствии с теоремами об умножении и сложении вероятностей (см. ☞ ЗДЕСЬ ) для вероятности $ 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<q $: на каждом шаге проигрыш вероятнее выигрыша («игра наперекор судьбе»). Пусть $ N $ достаточно велико. Существуют ли капиталы $ K $ при которых $ u(K,N) $ становится больше $ \frac{1}{2} $? Оказывается, не всегда. Так, при $ N=10,p=\frac{1}{4},q=\frac{3}{4} $ размер нужного капитала $ K $ должен быть равен, фактически,³⁾ $ 10 $, но тогда можно и не играть! При $ N=100,p=\frac{2}{5},q=\frac{3}{5} $ и при капитале $ K=99 $ игроку имеет смысл вести игру: его выигрыш до $ 100 $ более вероятен, чем разорение «до нитки». А вот при $ K=98 $ лучше не рисковать!

При каком соотношении $ p_{} $ и $ q_{} $ ($ p<q $) существуют капиталы $ K\in \mathbb N $, с которыми можно вступать в игру? Конечный капитал $ N\in \mathbb N $ считается достаточно большим.

Рассмотрим линейное однородное дифференциальное уравнение $ n_{} $-го порядка с вещественными коэффициентами $$ y^{(n)}-a_1y^{(n-1)}-\dots-a_{n-1}y^{\prime} - a_ny=0 \ , a_n \ne 0. $$ Интегралы этого уравнения являются аналитическими функциями по $ x_{} $. Пусть $$ y(x)=u_0+u_1 \frac{x}{1}+u_2 \frac{x^2}{2!}+\dots+u_{n+K} \frac{x^{n+K}}{(n+K)!}+\dots $$ — разложение одного из таких интегралов в ряд Тейлора. Подставляя этот ряд в дифференциальное уравнение и приравнивая нулю коэффициент при $ x^{n+K} $ получаем соотношение между коэффициентами ряда $$ u_{n+K}-a_1u_{n+K-1}-\dots-a_{n-1}u_{K+1}-a_nu_K =0 \ , $$ которое определяет линейное однородное разностное уравнение $ n_{} $-го порядка. При любых значениях начальных данных $ u_0,u_1,\dots, u_{n-1} $ ряд с такими коэффициентами будет абсолютно сходящимся для любых значений $ x_{} $; он определяет решение дифференциального уравнения, удовлетворяющее условиям $ y(0)=u_0,y^{\prime}(0)=u_1, \dots, y^{(n-1)}(0)=u_{n-1} $ — эта задача известна как задача Коши.

Просчитав необходимое число коэффициентов ряда, мы можем найти решение дифференциального уравнения с наперед заданной точностью.

Теорема.[5]. Для остаточного члена ряда

$$ y(x)=u_0+u_1 \frac{x}{1}+u_2 \frac{x^2}{2!}+\dots+u_{n+K} \frac{x^{n+K}}{(n+K)!}+R_{n+K+1}(x) $$ справедлива следующая оценка $$ | R_{n+K+1}(x) |< \frac{B(An)^{K+2}|x|^{n+K+1}}{(n+K+1)!}e^{An|x|} \ . $$ Здесь $ A=\max \{1, |a_1|,\dots, |a_n| \} $, $ B= \max \{|c_0|,|c_1|,\dots, |c_{n-1}| \} $.

Полученное в пункте ☞ АНАЛИТИКА общее решение разностного уравнения позволяет построить и общее решение дифференциального уравнения. В самом деле, если $ \lambda_{\ast}^{} $ — какой-то из корней характеристического уравнения $ \lambda^n - a_1\lambda^{n-1}-\dots-a_{n-1}\lambda - a_n=0 $, то одним из решений разностного уравнения будет $ u_K=C\lambda_{\ast}^K $ при $ K\in \mathbb N $ и произвольной константе $ C\in \mathbb C $. Тогда ряд $$ y(x)=\sum_{j=0}^{\infty} u_j \frac{x^j}{j!} = C \sum_{j=0}^{\infty} \frac{\lambda_{\ast}^jx^j}{j!}=Ce^{\lambda_{\ast} x} $$ дает один из интегралов дифференциального уравнения. Если все корни $ \lambda_{1},\dots,\lambda_n $ характеристического уравнения простые, то общий интеграл дифференциального уравнения будет иметь вид $$ C_1 e^{\lambda_1 x} + \dots + C_n e^{\lambda_n x} \ . $$ Если же среди корней характеристического уравнения имеются кратные, то общий интеграл записывается в виде $$ \tilde L_1(x)e^{\lambda_1 x} + \dots + \tilde L_{\mathfrak r}(x) e^{\lambda_{\mathfrak r} x} \ , $$ где $ \tilde L_1(x),\dots,\tilde L_{\mathfrak r}(x) $ — полиномы по $ x_{} $, $ \{\tilde L_j(x)\}_{j=1}^{\mathfrak r} \subset \mathbb C[x], \deg \tilde L_j< \mathfrak m_j $, где $ \mathfrak m_j $ означает кратность $ \lambda_{j} $ в характеристическом полиноме.

Наличие подобных представлений для общего интеграла позволяет полностью «закрыть» проблему поиска решения дифференциального уравнения. Кажется, что по сравнению с такими красивыми (и замкнутыми) аналитическими формулами, представление решения в виде бесконечного ряда существенно менее конструктивно, и, следовательно, может быть оценено как имеющее исключительно теоретическое значение промежуточная стадия выведения окончательной вычислительной формулы.

Не будем, однако, торопиться с выводами.

Пример. Найти решение дифференциального уравнения

$$ y^{(10)}-3\,y^{(9)}+4\,y^{(7)}-5\,y^{(6)}+3\,y^{(5)}-y^{(4)}-10\,y^{\prime \prime \prime}+y^{\prime} - 2\,y=0 \ , $$ удовлетворяющее условиям $$ y(0)=0, y^{\prime}(0)=1, y^{\prime \prime}(0)=0,y^{\prime \prime \prime}(0)=1,y^{(4)}(0)= \dots=y^{(9)}(0)=0 , $$ и установить достигает ли величина $ y(3) $ значения, равного $ 8_{} $.

Решение. Рекуррентная последовательность $ \{u_j\} $ вычисляется достаточно быстро. Для соответствующего ряда получаем частичную сумму $$ U_{21}(x)= x+\frac{1}{6}x^3+\frac{1}{403200}x^{10}+\frac{29}{39916800}x^{11}+\frac{43}{239500800}x^{12}+ $$ $$ +\frac{1}{27799200}x^{13}+\frac{601}{87178291200}x^{14}+\frac{1577}{1307674368000}x^{15}+\frac{4187}{20922789888000}x^{16}+ $$ $$ +\frac{5569}{177843714048000}x^{17}+\frac{5963}{1280474741145600}x^{18}+\frac{13309}{20274183401472000}x^{19}+ $$ $$ +\frac{17837}{202741834014720000}x^{20}+\frac{1103}{98251811868672000}x^{21} \ , $$ которая и дает оценку величины $$ y(3) \approx U_{21}(3) = 7.993_{\displaystyle 8437} \ . $$ Ответ на поставленный в задаче вопрос отрицателен: $ y(3) < 8 $. Заметим, что оценка для остаточного члена, даваемая теоремой, очень грубая: в нашем примере, для того чтобы удовлетворить ей, исходя из требования $ |R_{K+11}(x)|<10^{-3} $, пришлось бы взять $ K\ge 1036 $.

Если искать решение дифференциального уравнения альтернативным методом — извлечением его из вида общего решения — то придется, во-первых, решать характеристическое уравнение над $ \mathbb C_{} $: $$ \lambda_1 \approx -1.285346,\ \lambda_{2,3}\approx -0.794503 \pm \mathbf i\, 0.172088 ,\ \lambda_{4,5}\approx 0.045504 \pm \mathbf i\, 1.163742, \dots, $$ $$ \lambda_{10} \approx 2.678622 \ . $$ Во-вторых, придется решать систему из $ 10_{} $ линейных уравнений для установления величин $ C_1,\dots,C_{10} $, выделяющих требуемое частное решение из вида общего интеграла… И всё это придется делать в поле комплексных чисел, и всё это — с необходимой точностью,… а ответ, при всём при том, должен быть вещественным! Вывод: красивая аналитическая формула вовсе не обязательно оптимальна для решения конкретной вычислительной задачи. ♦

Пример. Найти решение дифференциального уравнения

$$ y^{\prime \prime} -3\, y^{\prime} + 4\, y=0 \ , $$ удовлетворяющее условиям $ y(0)=0, y(1)=1 $, и вычислить значение $ y(0.5) $.

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

Решение. Для данного примера удается построить точное решение: $$ y(x)=\frac{ e^{ 3/2(x-1)}\sin (\sqrt{7}/2 x )}{\sin (\sqrt{7}/2)} \quad u \quad y( 1/2) \approx 0.299303 \ . $$ Наша задача сейчас — проиллюстрировать приближенный метод решения краевой задачи (а полученное аналитическое решение будем использовать для контроля точности). Этот метод заключается в дискретизации непрерывного процесса — вместо нахождения общего выражения для решения $ y(x) $, подобного только что представленному, мы ставим целью нахождение значений $ y(x_j) $ в некоторых точках интервала $ [0_{},1] $. Разобьем этот интервал на $ N_{} $ равных частей точками $$ x_j=j h \quad npu \quad j\in \{0,1,\dots, N \}, h=1/N . $$ Вспомнив определение производной функции как предела: $$ y^{\prime}(x)= \lim_{h\to 0} \frac{y(x+h)-y(x)}{h} $$ будем считать, что при достаточно малых значениях $ h_{}>0 $, ошибка в равенствах $$ y^{\prime}(x_j) \approx \frac{y(x_j+h)-y(x_j)}{h} \quad u \quad y^{\prime}(x_j) \approx \frac{y(x_j)-y(x_j-h)}{h} $$ пренебрежимо мала. Таким образом, мы получаем приближение для производной (неизвестной нам функции) через значения этой же функции. Какое из двух этих приближений взять — не очень принципиально. С целью «сохранения равноправия» в окрестности $ x_{j} $, возьмем в качестве приближения $$ y^{\prime}(x_j) \approx \frac{1}{2} \left( \frac{y(x_j+h)-y(x_j)}{h} + \frac{y(x_j)-y(x_j-h)}{h} \right) = \frac{y(x_j+h)-y(x_j-h)}{2h} \ . $$ Для значения второй производной $ y^{\prime \prime }(x) $ в точке $ x_{j} $ приближение строим в виде $$ y^{\prime \prime }(x_j) \approx \frac{1}{h} \left( \frac{y(x_j+h)-y(x_j)}{h} - \frac{y(x_j)-y(x_j-h)}{h} \right)= $$ $$ = \frac{y(x_{j}+h)-2y(x_j)+y(x_j-h)}{h^2} . $$ С использованием этих приближений, а также обозначения $$ u_j = y(x_j) \quad npu \quad j \in \{0,\dots,N \} , $$ заменяем исходное дифференциальное уравнение на уравнение $$ (u_{j+1}-2\, u_j - u_{j-1}) - \frac{3}{2} h (u_{j+1}- u_{j-1})+4 h^2 u_j \ \iff $$ $$ \iff \quad (1-3/2h) u_{j+1}+ (4\,h^2-2)u_j+ (1+3/2h) u_{j-1}= 0 \ , $$ которое является линейным разностным уравнением второго порядка. Граничные условия для дифференциального уравнения переходят в граничные условия для разностного: $ u_0=0,u_N=1 $. Можно решить это уравнение в явном виде — по аналогии с тем, как это было сделано в пункте ☞ ЗАДАЧА О РАЗОРЕНИИ ИГРОКА. Но мы пойдем другим путем и для нахождения значений $ u_1,\dots,u_{N-1} $ выпишем получившиеся линейные уравнения. Так, для $ N=6 $ уравнения $$ 3/4 u_{j+1}-17/9 u_{j} + 5/4 u_{j-1} = 0 \quad npu \quad j\in \{1,\dots, 5 \} $$ перепишутся в виде $$ \left\{ \begin{array}{rrrrrrr} 3/4 u_6 & - 17/9 u_5 &+5/4 u_4 & & & & = 0, \\ & 3/4 u_5 & - 17/9 u_4 &+5/4 u_3 & & & =0, \\ & & 3/4 u_4 & - 17/9 u_3 &+5/4 u_2 & & =0, \\ & & & 3/4 u_3 & - 17/9 u_2 &+5/4 u_1 & =0, \\ & & & & 3/4 u_2 & - 17/9 u_2 &+5/4 u_0 =0. \end{array} \right. $$ С учетом граничных условий, перепишем эту систему в матричном виде $$ \left( \begin{array}{rrrrr} - 17/9 & 5/4 & & & \\ 3/4 & - 17/9 & 5/4 & & \\ & 3/4 & - 17/9 & 5/4 & \\ & & 3/4 & - 17/9 &5/4 \\ & & & 3/4 & - 17/9 \end{array} \right) \cdot \left( \begin{array}{l} u_5 \\ u_4 \\ u_3 \\ u_2 \\ u_1 \end{array} \right)= \left( \begin{array}{r} -3/4 \\ 0 \\ 0 \\ 0 \\ 0 \end{array} \right) $$ (все неуказанные элементы матрицы равны $ 0_{} $). Матрица системы является трехдиагональной. Существуют специальные методы решения систем линейных уравнений с подобными матрицами (см. ☞ метод прогонки ). Но мы ограничимся здесь только поставленной задачей оценки величины $ y(0.5) $. Очевидно, для этого необходимо «вытащить» из системы значение неизвестной $ u_3 $. Сделаем это с помощью формул Крамера: $$ u_3= \frac{ \left| \begin{array}{rrrrr} - 17/9 & 5/4 & -3/4 & & \\ 3/4 & - 17/9 & 0 & & \\ & 3/4 & 0 & 5/4 & \\ & & 0 & - 17/9 &5/4 \\ & & 0 & 3/4 & - 17/9 \end{array} \right| }{\left| \begin{array}{rrrrr} - 17/9 & 5/4 & & & \\ 3/4 & - 17/9 & 5/4 & & \\ & 3/4 & - 17/9 & 5/4 & \\ & & 3/4 & - 17/9 &5/4 \\ & & & 3/4 & - 17/9 \end{array} \right|} = \frac{19683}{66572} \approx 0.295665 \ , $$ что неплохо согласуется с точным ответом.

При выборе $ N = 8 $ (более мелком дроблении интервала) получаем новое разностное уравнение $$ 13 u_{j+1}-31 u_{j} + 19 u_{j-1} = 0 \quad npu \quad j\in \{1,\dots, 7 \} \ , $$ которое относительно $ u_{ 4} $ будет иметь решение $$ u_4=\frac{28561}{96071} \approx 0.297290 \ . $$ ♦

В разных разделах алгебры (и не только алгебры) слово «решить» может иметь совершенно разный смысл. Поставленная в начале настоящего раздела задача о решении линейного разностного уравнения свелась к нахождению корней его характеристического полинома. Вид общего решения найден и в этом смысле решение задачи получено. Вспомним, однако, что в общем случае нахождение корней полинома представляет собой отдельную задачу, которую также должно решать! Но известно, что корни полинома степени выше четвертой, как правило, не могут быть выражены в виде «хороших» функций от коэффициентов этого полинома (см. ☞ РЕШЕНИЕ УРАВНЕНИЙ В РАДИКАЛАХ ) ; мы можем гарантировать разве что их приближения с заданной точностью… Иными словами, мы свели решение одной задачи (решения разностного уравнения) к другой задаче (решения алгебраического уравнения), которая не имеет «красивого» решения!

Кажется, что мы влипли в порочный круг⁴⁾. На самом деле, ситуация не столь безнадежна. Во-первых, хотя бы в некоторых случаях решение может быть получено явно — когда корни характеристического полинома удается найти в радикалах. Во-вторых, кое-какую пользу от полученного теоретического решения задачи мы получили и для общего случая. Например, мы смогли проанализировать поведение последовательности при возрастании $ K $ — и смогли сделать это «честно»: не привлекая бесконечные процессы численных методов, а только производя конечный набор элементарных операций над коэффициентами характеристического полинома.

В настоящем пункте мы «развернем» приведенную в пункте ☞ АНАЛИТИКА схему решения, сводящую разностное уравнение к алгебраическому: именно, мы будем искать корень алгебраического уравнения с помощью рекуррентной последовательности.

Задача. Решить алгебраическое уравнение $$ x^n+a_1x^{n-1}+a_2x^{n-2} + \dots + a_n = 0 \ . $$ Здесь коэффициенты $ a_1,\dots,a_n \ne 0 $ предполагаются комплексными.

Теорема [Бернулли]. Обозначим $ \lambda_1 $ — максимальный по модулю корень уравнения

$$ x^n+a_1x^{n-1}+a_2x^{n-2} + \dots + a_n = 0 \ . $$ Предположим, что остальные корни уравнения строго меньше этого корня по модулю: $$ |\lambda_1 | > |\lambda_j | \quad npu \ j\in \{2,3,\dots,n\} \ . $$ Тогда линейная рекуррентная последовательность $$ x_{K+n}=-a_1x_{K+n-1}-a_2x_{K+n-2}-\dots-a_nx_{K} $$ практически для любых начальных данных $ x_0,\dots,x_{n-1} $ будет обладать свойством $$ \lim_{K\to \infty} \frac{x_{K}}{x_{K-1}} = \lambda_1 \ , $$ т.е. отношение двух соседних членов последовательности будет стремиться к максимальному по модулю корню алгебраического уравнения.

Доказательство. Предположим сначала, что корни алгебраического уравнения все различны. Тогда это уравнение является характеристическим для рекуррентной последовательности $$ x_{K+n}=-a_1x_{K+n-1}-a_2x_{K+n-2}-\dots-a_nx_{K} $$ и, на основании теоремы 1 общий член этой последовательности может быть представлен в виде: $$ x_K=C_1\lambda_1^K+C_2\lambda_2^K+\dots+C_n\lambda_n^K \ . $$ Тогда $$ \frac{x_{K}}{x_{K-1}} =\frac{C_1\lambda_1^K+C_2\lambda_2^K+\dots+C_n\lambda_n^K }{C_1\lambda_1^{K-1}+C_2\lambda_2^{K-1}+\dots+C_n\lambda_n^{K-1} } =\frac{\displaystyle{\lambda_1^K\left(C_1+C_2\left(\frac{\lambda_2}{\lambda_1}\right)^K+\dots+C_n\left(\frac{\lambda_n}{\lambda_1}\right)^K \right) }}{\displaystyle{\lambda_1^{K-1}\left(C_1+C_2\left(\frac{\lambda_2}{\lambda_1}\right)^{K-1}+\dots+C_n\left(\frac{\lambda_n}{\lambda_1}\right)^{K-1}\right)}} \ . $$ По условию теоремы $ |\lambda_j/ \lambda_1| < 1 $ при $ j\in \{ 2,\dots,n \} $, следовательно для всех таких $ j $ будет выполнено: $$ (\lambda_j/ \lambda_1)^K \to 0 \quad npu \quad K \to \infty \ . $$ Но тогда $$ x_{K}/x_{K-1} \to \lambda_1 \quad npu \quad K \to \infty \ . $$ За исключением одного-единственного «плохого» случая: может так оказаться, что $ C_1=0 $ — тогда предельный переход не гарантирован. Именно эта последняя ситуация имелась в виду когда в условии теоремы мы подчеркнули слова «практически для любых». ♦

Итак, для решения алгебраического уравнения предлагается «запустить» рекуррентную последовательность. А почему бы и нет? Такая последовательность достаточно просто реализуется — пусть себе компьютер считает!

Пример. Вычислить максимальный по модулю корень полинома

$$ x^5+20\,x^4-50{\mathbf i}\,x^3-(6+7{\mathbf i})\,x-129 \, .$$

Решение. Образуем разностное уравнение пятого порядка: $$ x_{K+5}=-20\,x_{K+4}-50\, x_{K+3}-(6+7{\mathbf i})x_{K+1}-129x_K $$ и возьмем в качестве начальных данных набор значений $$ x_0=0,x_1=0,x_2=0,x_3=1,x_4=43/149+5/2{\mathbf i} \ . $$ Получаем: $$ \begin{array}{c|c|c} K & x_{K+5} & \approx x_{K+5}/x_{K+4} \\ \hline 0 & -860/149 & -0.263005+2.278364\,{\mathbf i} \\ 1 & -1425/149+2150/149 \,{\mathbf i} & 1.656976-2.5\, {\mathbf i} \\ 2 & 29394/149-84957/149 \,{\mathbf i} & -33.750155+8.697660 \, {\mathbf i} \\ 3 & -1357017/298+1630426/149 \,{\mathbf i} & -19.607285-1.202631\, {\mathbf i} \\ 4 & 17818407/149-62193575/298 \,{\mathbf i} & -20.133934-2.549861 \, {\mathbf i} \\ 5 & -438023980/149+588013250/149 \,{\mathbf i} & -20.311478-2.447384\, {\mathbf i} \\ 6 & 10315906213/149-10869371284/149 \,{\mathbf i} & -20.292875-2.427054 \, {\mathbf i} \\ 7 &-235730478967/149+390960600447/298 \,{\mathbf i} & -20.290782-2.430009 \, {\mathbf i} \\ 8 & 5258315203898/149-3393662220742/149 \,{\mathbf i} & -20.291221-2.430198 \, {\mathbf i} \\ 9 & -114944764751262/149+112166341785085/298 \,{\mathbf i} & -20.291233-2.430136 \, {\mathbf i} \end{array} $$ На рисунке голубым цветом изображены пять первых элементов последовательности $ x_{K+5}/x_{K+4} $, корни полинома обозначены красным. Практически со стопроцентной вероятностью при выборе случайным образом начальных данных последовательность будет сходиться к максимальному по модулю корню полинома $ \lambda_1 \approx -20.291225 -2.430137 \,{\mathbf i} $.

Однако выберем теперь эти данные со злобным намерением нарушить такой характер сходимости: возьмем $$ x_0=0,x_1=0,x_2=0,x_3=1,x_4=\frac{4342349801}{14910596913}+\frac{3168438244}{1303810345} \,{\mathbf i} \ . $$ Получаем: $$ \begin{array}{c|c|c} K & x_{K+5} & \approx x_{K+5}/x_{K+4} \\ \hline & & \\ 0 & -\frac{86846996020}{14910596913}+\frac{364350474}{260762069} \, {\mathbf i} & -0.280599+2.341470\, {\mathbf i} \\ & & \\ 1 & -\frac{19505007627976100120}{3888118101058892997}-\frac{52037655135964821790}{3888118101058892997} \, {\mathbf i} & 0.293181+2.368165 \, {\mathbf i} \\ & & \\ 2 & & 0.188749+2.795596 \, {\mathbf i} \\ 3 & & 0.218725+2.753605 \, {\mathbf i} \\ 4 & & 0.236295+2.719943 \, {\mathbf i} \\ 5 & & 0.254531+2.677557 \, {\mathbf i} \\ 6 & & 0.245465+2.687539 \, {\mathbf i} \\ 7 & & 0.241023+2.693688 \, {\mathbf i} \\ 8 & & 0.239440+2.696823 \, {\mathbf i} \\ \end{array} $$ и последовательность $ x_{K+5}/x_{K+4} $ начинает стремиться к следующему по величине модуля корню $ \lambda_2 \approx 0.241854+2.694544 \, {\mathbf i} $. Повторюсь: достичь такой сходимости удалось специальными усилиями по выбору подходящих начальных данных⁵⁾; стоит только их немного испортить и сходимость снова будет к корню $ \lambda_1 $.

При каком наборе начальных данных последовательность $ x_{K+5}/x_{K+4} $ будет сходиться

а) к третьему по величине модуля корню полинома;

б) к минимальному по модуля корню полинома?

♦

Как решить последнюю задачу в общем случае: модифицировать алгоритм так, чтобы находить минимальный по модулю корень полинома?

Подсказка. См. ☞ ЗДЕСЬ.

Теперь посмотрим что произойдет, если нарушается условие единственности корня с максимальным модулем. Такая ситуация может показаться исключительной для полиномов с коэффициентами мнимыми. Так оно и есть: корни такого полинома располагаются на комплексной плоскости случайным образом и вероятность того, что два из них окажутся на одной и той же окружности с центром в точке 0 пренебрежимо мала. Однако, если мы имеем дело с полиномами с коэффициентами вещественными (а этот случай чаще предыдущего встречается в практике вычислений), то ситуация равенства модулей двух корней полинома становится уже не исключительной: комплексно-сопряженные пары корней имеют одинаковые модули (см. ☞ ЗДЕСЬ )!

Пример. Вычислить максимальный по модулю корень полинома

$$ x^4-7\,x^3+34\,x^2-68\,x+40 \, .$$

Решение. Запускаем рекуррентную последовательность $$ x_{K+4}=7\,x_{K+3}-34\,x_{K+2}+68\, x_{K+1}-40\,x_{K} $$ с различными начальными данными $$ \begin{array}{c} x_0=0,x_1=0,x_2=0,x_3=6 \\ \hline \begin{array}{c|c} K & \approx x_{K+4}/x_{K+3} \\ \hline 0 & 7 \\ 1 & 2.142857 \\ 2 & -4.333333 \\ 3 & 8.138461 \\ 4 & 1.423440 \\ 5 & -10.219123 \\ 6 & 5.990253 \\ 7 & 0.672328 \\ 8 & -25.714336 \end{array} \end{array} \begin{array}{||c} x_0=0,x_1=0,x_2=1,x_3={\mathbf i} \\ \hline \begin{array}{c} \approx x_{K+4}/x_{K+3} \\ \hline 7+34 {\mathbf i} \\ 4.883817+0.564315 {\mathbf i} \\ 0.398454+0.417510 {\mathbf i} \\ -18.958354+23.801257 {\mathbf i} \\ 4.302668+0.516309{\mathbf i} \\ -0.631595+0.556795 {\mathbf i} \\ 21.917361+15.773371 {\mathbf i} \\ 3.407653+0.432279 {\mathbf i} \\ -1.771117+0.731887 {\mathbf i} \end{array} \end{array} $$ Сходимость неочевидна. Анализируем корни полинома: $$ \lambda_1=2-4 {\mathbf i}, \lambda_2=2+4 {\mathbf i},\lambda_3=2, \lambda_4=1 .$$ Имеется два максимальных по модулю корня и они комплексно-сопряженные. Теперь понятно почему не должна сходиться первая последовательность: ее начальные данные были все вещественными, вещественными же являются коэффициенты полинома (и разностного уравнения), следовательно последовательность $ x_{K+4}/x_{K+3} $ не могла генерировать мнимые числа в принципе! Вторая последовательность состоит из мнимых чисел, и доказать отсутствие сходимости хотя бы к одному из корней $ \lambda_1 $ или $ \lambda_2 $ уже посложнее. ♦

Иногда мелкий результат служит отправной точкой для крупной теории… Числа Фибоначчи просто задаются — а какую теорию порождают! Имея в виду это обстоятельство, вернемся к упражнению Эйлера в конце ☞ ПУНКТА.

Сгенерируем на основе рекуррентной последовательности $$ x_{K+n}=-a_1x_{K+n-1}-a_2x_{K+n-2}-\dots-a_nx_{K} $$ новую последовательность $$ y_{K}=x_{K}x_{K+2}-x_{K+1}^2 \ . $$ На примерах из предыдущего пункта оценим асимптотику отношения $$ \frac{y_{K+1}}{y_K} \quad npu \quad K \to \infty \ . $$

Пример. Для полинома

$$ f(x)= x^5+20\,x^4-50{\mathbf i}\,x^3-(6+7{\mathbf i})\,x-129 $$ разностное уравнение $$ x_{K+5}=-20\,x_{K+4}-50\, x_{K+3}-(6+7{\mathbf i})x_{K+1}-129x_K $$ при выборе начальных данных $$ x_0=0,x_1=0,x_2=0,x_3=1,x_4=43/149+5/2{\mathbf i} $$ дает: $$ \begin{array}{c|c|c} K & \approx y_{K} & \approx y_{K}/y_{K-1} \\ \hline 5 & -1021.889329+3566.979865 \,{\mathbf i} & \\ 6 & 171845.562159+54605.729066 \,{\mathbf i} & 1.392427-48.575679 \,{\mathbf i} \\ 7 & 3593515.455351-9699634.071978 \,{\mathbf i} & 2.702763-57.302733 \,{\mathbf i}\\ 8 & & 2.056010-56.461741 \,{\mathbf i} \\ 9 & & 1.577875-55.791210 \,{\mathbf i} \\ \vdots & & \dots \\ 12 & & 1.673367-55.241399 \, {\mathbf i} \\ \vdots & & \dots \\ 15 & & 1.631486-55.261773 \, {\mathbf i} \\ \vdots & & \dots \\ 18 & & 1.642333-55.263835 \, {\mathbf i} \\ \vdots & & \dots \\ 24 & & 1.640619-55.263355 \, {\mathbf i} \end{array} $$ Видим, что имеется сходимость к какому-то мнимому числу. Оказывается, это число равно произведению двух максимальных по модулю корней полинома $ f(x) $: $$ \lambda_1 \lambda_2 \approx (-20.291225-2.430137 \,{\mathbf i}) (0.241854+2.694544\,{\mathbf i}) \approx $$ $$ \approx 1.640589-55.263344 \, {\mathbf i} \ . $$ Проверим теперь полином $ x^4-7\,x^3+34\,x^2-68\,x+40 $, у которого два комплексно-сопряженных корня имеют одинаковое значение модуля. $$ \begin{array}{c||c} x_0=0,x_1=0,x_2=0,x_3=6 & x_0=0,x_1=0,x_2=1,x_3={\mathbf i} \\ \hline \begin{array}{c|c} K & \approx y_{K}/y_{K-1} \\ \hline 5 & 17.882352 \\ 6 & 18.988157 \\ 7 & 20.085510 \\ 8 & 20.252126 \\ \dots & \dots \\ 12 & 19.993988 \\ \dots & \dots \\ 16 & 19.999734 \end{array} & \begin{array}{c} \approx y_{K}/y_{K-1} \\ \hline 19.191066+0.225090 \, {\mathbf i} \\ 19.040624+0.076125 \, {\mathbf i} \\ 19.769628-0.020615 \, {\mathbf i} \\ 20.115168-0.025721 \, {\mathbf i} \\ \dots \\ 19.991971+0.000361 \, {\mathbf i} \\ \dots \\ 19.999996+0.000032\, {\mathbf i} \end{array} \end{array} $$ Гипотеза подтверждается: последовательность сходится к квадрату модуля корней. ♦

Теорема. Обозначим $ \lambda_1, \lambda_2 $ — максимальные по модулю корни уравнения

$$ x^n+a_1x^{n-1}+a_2x^{n-2} + \dots + a_n = 0 \ . $$ Предположим, что остальные корни уравнения строго меньше этого корня по модулю: $$ |\lambda_1 | \ge |\lambda_2 |> |\lambda_j | \quad npu \ j\in \{3,\dots,n\} \ . $$ Тогда линейная рекуррентная последовательность $$ x_{K+n}=-a_1x_{K+n-1}-a_2x_{K+n-2}-\dots-a_nx_{K} $$ — практически для любых начальных данных $ x_0,\dots,x_{n-1} $ будет обладать свойством $$ \lim_{K\to \infty} \frac{x_{K+1}x_{K+3}-x_{K+2}^2}{x_{K}x_{K+2}-x_{K+1}^2} = \lambda_1 \lambda_2 \ . $$

Доказательство. Предположим для простоты, что все корни $ \lambda_3,\dots,\lambda_n $ различны. Тогда, используя рассуждения аналогичные приведенным в доказательстве теоремы Бернулли, получаем $$ x_{K}x_{K+2}-x_{K+1}^2=C_1C_2\left(\frac{\lambda_2}{\lambda_1}-1 \right)^2\lambda_1^{K+2}\lambda_2^K + \dots \ , $$ где многоточие в правой части означает слагаемые, возрастающие при $ K \to \infty $ более медленно, чем выделенное . Перейдя от $ K $ к $ K+1 $, и составив отношение из условия теоремы, мы получим доказываемый результат. Исключительных случаев оказывается два: либо одна из констант $ C_j $ обратится в нуль за счет неудачного выбора начальных данных $ x_0,\dots,x_{n-1} $; либо же $ \lambda_2=\lambda_1 $, т.е. уравнение обладает кратным корнем. Последняя ситуация требует более тонкого анализа, но всегда может быть обезврежена предварительной проверкой уравнения на наличие кратных корней (если у уравнения имеется кратный корень, то, как правило, его можно выразить рационально через коэффициенты ). ♦

Объединим теперь результаты последней теоремы и теоремы Бернулли:

Второй по убыванию модуля корень уравнения может быть получен с помощью линейной рекуррентной последовательности

$$ x_{K+n}=-a_1x_{K+n-1}-a_2x_{K+n-2}-\dots-a_nx_{K} $$ по формуле: $$ \lim_{K\to \infty} \frac{(x_{K+1}x_{K+3}-x_{K+2}^2)x_K}{(x_{K}x_{K+2}-x_{K+1}^2)x_{K+1}} = \lambda_2 \ . $$

Как обобщить этот результат для нахождения следующих корней уравнения? — Для этого требуется аппарат ганкелевых определителей.

Теорема. Составим из элементов рекуррентной последовательности

$$ x_{K+n}=-a_1x_{K+n-1}-a_2x_{K+n-2}-\dots-a_nx_{K} $$ определитель третьего порядка: $$ H_K=\left|\begin{array}{lll} x_{K} & x_{K+1} & x_{K+2} \\ x_{K+1} & x_{K+2} & x_{K+3} \\ x_{K+2} & x_{K+3} & x_{K+4} \end{array} \right| \ . $$ Тогда, если через $ \lambda_1,\lambda_2,\lambda_3 $ обозначить максимальные по модулю корни уравнения $$ x^n+a_1x^{n-1}+a_2x^{n-2} + \dots + a_n = 0 \ , $$ то, как правило, $$ \lim_{K\to \infty} \frac{H_{K+1}}{H_K} = \lambda_1\lambda_2\lambda_3 \ . $$

Третий по убыванию модуля корень уравнения может быть получен с помощью линейной рекуррентной последовательности

$$ x_{K+n}=-a_1x_{K+n-1}-a_2x_{K+n-2}-\dots-a_nx_{K} $$ по формуле: $$ \lim_{K\to \infty} \frac{\left|\begin{array}{lll} x_{K+1} & x_{K+2} & x_{K+3} \\ x_{K+2} & x_{K+3} & x_{K+4} \\ x_{K+3} & x_{K+4} & x_{K+5} \end{array} \right|\cdot \left|\begin{array}{ll} x_{K} & x_{K+1} \\ x_{K+1} & x_{K+2} \end{array} \right|}{\left|\begin{array}{lll} x_{K} & x_{K+1} & x_{K+2} \\ x_{K+1} & x_{K+2} & x_{K+3} \\ x_{K+2} & x_{K+3} & x_{K+4} \end{array} \right|\cdot \left|\begin{array}{ll} x_{K+1} & x_{K+2} \\ x_{K+2} & x_{K+3} \end{array}\right|} = \lambda_3 \ . $$

☞ ЗДЕСЬ

.

[1]. Демидович Б.П., Марон И.А. Основы вычислительной математики. М.Наука. 1966

[2]. Гельфонд А.О. Исчисление конечных разностей. М.Наука. 1967

[3]. Шеннон К. Математическая теория связи. (Shannon C.E. A Mathematical Theory of Communication. Bell System Technical Journal. — 1948. — Т. 27. — С. 379-423, 623–656.)

[4]. Марковъ А. Исчисленie конечныхъ разностей. Mathesis. 1910

[5]. Гурса Э. Курс математического анализа. Т.2. М.-Л.ГТТИ. 1933

[6]. Henrici P. Applied and Computational Complex Analysis. V. 1. 1974., NY. Wiley