Как найти общее решение разностного уравнения

Содержание

Пусть заданы числа $ 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 fge 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 kge 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 qne 0 .
$$
Сделаем из него — формальной заменой $ x_{K+2} rightarrow x^2, x_{K+1} rightarrow x, x_{K} rightarrow 1 $ — алгебраическое:
$$x^2=pcdot x+qcdot 1 . $$
Анализируем корни:

1.

Если дискриминант квадратного уравнения $ mathcal D=p^2+4q $ отличен от нуля, то его корни $ lambda_1,lambda_2 $ различны. Ищем решение разностного уравнения в виде
$$ x_K=C_1lambda_1^K+C_2lambda_2^K , $$
где $ C_1,C_2 $ — некоторые, пока неопределенные, постоянные.

2.

Если дискриминант $ mathcal D $ равен нулю (и при этом $ qne 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_1lambda_1&+C_2lambda_2,
end{array}
right.
$$
решениями которой являются числа
$$
C_1=frac{x_0lambda_2-x_1}{lambda_2-lambda_1}, C_2=
frac{x_0lambda_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_1lambda_1^{K+2}+C_2lambda_2^{K+2} Rightarrow x_{K+1}=C_1lambda_1^{K+1}+C_2lambda_2^{K+1}, x_{K}=C_1lambda_1^{K}+C_2lambda_2^{K} Rightarrow $$
$$
C_1lambda_1^{K+2}+C_2lambda_2^{K+2} =p (C_1lambda_1^{K+1}+C_2lambda_2^{K+1})+q(C_1lambda_1^{K}+C_2lambda_2^{K}) Rightarrow
$$
$$ C_1lambda_1^{K}(lambda_1^2-plambda_1-q)+ C_2lambda_2^{K}(lambda_2^2-plambda_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, $$
называется характеристическим уравнением (соответствующим данному разностному уравнению)²⁾; полином
$$ f(lambda)= lambda^n — a_1 lambda^{n-1} — dots — a_n $$
будем называть характеристическим полиномом разностного уравнения. Обозначим $ lambda_{1},dots,lambda_n $ все корни этого полинома, с учетом их кратностей.

Т

Теорема 1. Если все корни характеристического полинома различны, то решение разностного уравнения получается в виде

$$ x_{K}= C_1lambda_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_2cdot 0& + C_3cdot 0^2& + dots &+ C_ncdot 0^{n-1}) \
x_1 &=& lambda_1^1&(C_1&+C_2cdot 1& + C_3cdot 1^2& + dots &+ C_ncdot 1^{n-1}) \
x_2 &=& lambda_1^2&(C_1&+C_2cdot 2& + C_3cdot 2^2& + dots &+ C_ncdot 2^{n-1}) \
dots & & dots \
x_{n-1}&=& lambda_1^{n-1}&(C_1&+C_2cdot (n-1)& + C_3cdot (n-1)^2& + dots &+ C_ncdot (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_1lambda+x_2lambda^2+dots+x_K lambda^K + dots
$$
называется производящим рядом рекуррентной последовательности.

Мы получили для него уравнение
$$ Z(lambda)-a_1lambda Z(lambda)-a_2lambda^2Z(lambda)-dots — a_nlambda^n Z(lambda)equiv p_0+p_1lambda+p_2lambda^2+dots+p_{n-1}lambda^{n-1} ,
$$
или
$$
Z(lambda)(1-a_1lambda-a_2lambda^2-dots- a_nlambda^n) equiv P(lambda) ,
$$
где $ P(lambda)=p_0+p_1lambda+p_2lambda^2+dots+p_{n-1}lambda^{n-1} $ — известный полином. Таким образом производящий ряд получается разложением в ряд по степеням $ lambda $ рациональной функции
$$
frac{P(lambda)}{1-a_1lambda-a_2lambda^2-dots- a_nlambda^n}
$$
и, если нам удастся найти явное выражение для коэффициента при $ lambda^K $, то он и будет решением разностного уравнения.

Полином $ f^{ast}(lambda) = 1-a_1lambda-a_2lambda^2-dots- a_nlambda^n $ не совпадает с характеристическим полиномом
$ f(lambda)= lambda^n-a_1lambda^{n-1}-a_2lambda^{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_1lambda-a_2lambda^2-dots- a_nlambda^n}=
$$
$$
=P(lambda) left[ (gamma_1+dots+gamma_n)+(gamma_1lambda_1+dots+gamma_nlambda_n)lambda+dots+(gamma_1lambda_1^K+dots+gamma_nlambda_n^K)lambda^K + dots right] .
$$
Вытаскиваем из него коэффициент при $ lambda^K $:
$$
begin{array}{lcl}
p_0 (gamma_1lambda_1^K &+dots+&gamma_nlambda_n^K)+ \
+p_1(gamma_1lambda_1^{K-1}&+dots+&gamma_nlambda_n^{K-1})+ \
&+dots + &\
+p_{n-1} (gamma_1lambda_1^{K-n+1}&+dots+&gamma_nlambda_n^{K-n+1})=
end{array}
$$
и просуммируем по столбцам:
$$
begin{array}{c}
= gamma_1lambda_1^K (p_0+p_1/lambda_1+dots+p_{n-1}/lambda_1^{n-1})+\
+ gamma_2lambda_2^K (p_0+p_1/lambda_2+dots+p_{n-1}/lambda_2^{n-1})+ \
+dots + \
+ gamma_nlambda_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) $ при $ jin {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 Kin 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}
3cdot (-1)^K + 2 cdot 4^K & 2 cdot (-1)^{K+1} + 2 cdot 4^K \
3cdot (-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)_{4times 1} =
left(
begin{array}{ll}
mathbb O & E \
mathbf A_2 & mathbf A_1
end{array}
right)_{4times 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+2lambda+2 & -3lambda+2\
-lambda+4 & -lambda^2-lambda+2
end{array}
right|=
$$
$$
=lambda^4-lambda^3-9,lambda^2+16,lambda-4 equiv (lambda-2)^2left(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} Kright)2^K+left(frac{13}{81}+frac{46sqrt{13}}{1053} right)left[-frac{3}{2}+frac{sqrt{13}}{2} right]^K+
$$
$$
+left(frac{13}{81}
-frac{46sqrt{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-1right)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) $
удовлетворяет условию а) теоремы.

Ответ. Уравнение устойчиво при $ 0le {color{Red}{ alpha} } le frac{27}{4} $.

?

[Шеннон][3]. Вычислить

$$ lim_{Kto 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_{Kto +infty} mathfrak F^K $.

?

[Марков][4]. Вычислить

$$ lim_{Kto +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_{} $. Здравый смысл, однако же, нас здесь подводит: реальный мир играет вероятностями — см. следующий пункт!

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

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

Пусть $ qne 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
Kin{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 Kin{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 $) существуют
капиталы $ Kin mathbb N $, с которыми можно вступать в игру? Конечный
капитал $ Nin 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_1lambda^{n-1}-dots-a_{n-1}lambda — a_n=0 $, то одним из решений разностного уравнения будет $ u_K=Clambda_{ast}^K $ при $ Kin mathbb N $ и произвольной константе $ Cin 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} $, пришлось бы взять $ Kge 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 jin {0,1,dots, N }, h=1/N . $$
Вспомнив определение производной функции как предела:
$$
y^{prime}(x)= lim_{hto 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 jin {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 jin {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 jin {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_{Kto 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_1lambda_1^K+C_2lambda_2^K+dots+C_nlambda_n^K . $$
Тогда
$$
frac{x_{K}}{x_{K-1}} =frac{C_1lambda_1^K+C_2lambda_2^K+dots+C_nlambda_n^K }{C_1lambda_1^{K-1}+C_2lambda_2^{K-1}+dots+C_nlambda_n^{K-1} }
=frac{displaystyle{lambda_1^Kleft(C_1+C_2left(frac{lambda_2}{lambda_1}right)^K+dots+C_nleft(frac{lambda_n}{lambda_1}right)^K right) }}{displaystyle{lambda_1^{K-1}left(C_1+C_2left(frac{lambda_2}{lambda_1}right)^{K-1}+dots+C_nleft(frac{lambda_n}{lambda_1}right)^{K-1}right)}} .
$$
По условию теоремы $ |lambda_j/ lambda_1| < 1 $ при $ jin { 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 jin {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_{Kto 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_2left(frac{lambda_2}{lambda_1}-1 right)^2lambda_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_{Kto 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_{Kto infty} frac{H_{K+1}}{H_K} = lambda_1lambda_2lambda_3 .
$$

=>

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

$$ x_{K+n}=-a_1x_{K+n-1}-a_2x_{K+n-2}-dots-a_nx_{K} $$
по формуле:
$$ lim_{Kto 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

Полезная страница? Сохрани или расскажи друзьям

Поможем с решением задач и уравнений

Лекции:

• Случайная вероятность
• Эквивалентные бесконечно малые функции. Сравнение бесконечно больших функций
• Решение определённых интегралов
• Параллельные прямые
• Кривизна и кручение пространственной кривой. Формулы Френе
• Пределы в математике
• Дифференциал функции
• Объемы подобных фигур
• Алгебра логики
• Эластичность функции