УказательРазделыОбозначенияАвторО проекте


Разностное уравнение и рекуррентная последовательность

Будем обозначать через \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} заданы. Тогда уравнение определяет линейную рекуррентную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,...

Чему равен следующий?

§

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

Идея решения

Решим сначала уравнение второго порядка

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] \ .

§

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

§

Число \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),

то применением формулы Муавра получаем:

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,

называется характеристическим уравнением (соответствующим данному разностному уравнению)2); полином

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} при \ 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. Фактически же мы получили классическую задачу построения интерполяционного полинома по его значениям в равноотстоящих узлах.

П

Пример. Решить уравнение четвертого порядка

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_{} из пункта АНАЛИТИКА, ЗДЕСЬ.

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)\ .

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

П

Пример. Найти все значения параметра \alpha_{}, при которых уравнение

x_{K+5}=\frac{1}{5}(x_{K+4}-(\alpha-4)x_{K+3}+(\alpha-2)x_{K+2}+x_{K+1}+x_{K})

будет устойчиво.

Решение. Характеристический полином уравнения равен

f(\lambda)=\frac{1}{5}\left(5\,\lambda^5-\lambda^4+(-4+\alpha)\,\lambda^3+ (-\alpha+2)\,\lambda^2-\,\lambda-1\right)\equiv
\equiv \frac{1}{5}(\lambda-1) \underbrace{\left(5\,\lambda^4+4\,\lambda^3+\alpha\,\lambda^2+2\,\lambda+1 \right)}_ {f_1(\lambda)} \ .

К полиному f_1(\lambda) нужно применить алгоритм теоремы Шура-Кона; и это сделано ЗДЕСЬ. Условие 0< \alpha < \frac{27}{4} является необходимым и достаточным для того, чтобы все корни f_1(\lambda) лежали внутри единичного круга. При \alpha=0 полином f_1(\lambda) имеет корень \lambda=-1; при \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 \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_{}. Здравый смысл, однако же, нас здесь подводит: реальный мир играет вероятностями — см. следующий пункт!

Задача о разорении игрока

§

Для понимания материалов этого пункта неплохо было бы просмотреть материалы из раздела ☞ ТЕОРИЯ ВЕРОЯТНОСТЕЙ.

Задача. Пусть игрок обладает конечным капиталом 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)= вероятность того, что игрок, начиная с капиталом \ K, накопит капитал \ N прежде, чем разорится.

На каждом шаге игрок либо выигрывает с вероятностью 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 ( игрок проиграл все деньги),
u(N,N)=1 \quad ( игрок выиграл капитал \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 должен быть равен, фактически,3) 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 \ .


§

Подведем итог результатам предыдущих пунктов. Существует глубинная внутренняя связь между тремя объектами:

алгебраическое уравнение \leftrightarrow линейное разностное уравнение \leftrightarrow линейное дифференциальное уравнение.

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

Поиск корня полинома методом Бернулли

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

Кажется, что мы влипли в порочный круг4). На самом деле, ситуация не столь безнадежна. Во-первых, хотя бы в некоторых случаях решение может быть получено явно — когда корни характеристического полинома удается найти в радикалах. Во-вторых, кое-какую пользу от полученного теоретического решения задачи мы получили и для общего случая. Например, мы смогли проанализировать поведение последовательности при возрастании 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}. Повторюсь: достичь такой сходимости удалось специальными усилиями по выбору подходящих начальных данных5); стоит только их немного испортить и сходимость снова будет к корню \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 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 \ .

§

Обобщение последнего результата для нахождения оставшихся корней теперь очевидно… Существует достаточно простая вычислительная схема, реализующая последовательное вычисление представлений корней уравнения через ганкелевы определители. В литературе она известна (см. [6] ) как quotient-difference algorithm (или QD-algorithm) и применяется также для вычисления нулей и полюсов функций представленных рядами Тейлора.

Источники

[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

1) recurrere (лат.) — возвращаться
2) По исторической традиции переменную в характеристическом уравнении обозначают \lambda.
3) Копейки не считаем!
4) circulus vitiosus (лат.)
5) И выбор основывался на знании величин корней!

2016/11/25 22:11 редактировал au