Явные решение разностных уравнений и

Разностные уравнения

Содержание:

Разностные уравнения

Понятие разницы и разностного уравнения

Если для значений переменной x1, x2, x3, . функция f (x) принимает значения f (x1), f (x2), f (x3) . , то приращения функции составляют f (x2) – f (x1), f (x3) – f (x2), .

Приращение функции при переходе от значения xi к значению xi+1 будем обозначать: В частности можно взять в качестве значения независимых переменных x и x + 1 . Разность Δf (x) = f (x + 1) — f (x) называется первой разностью или разностью первого порядка. Она может рассматриваться в свою очередь как функция от x, а потому и для нее можно определить разницу:

Введем обозначения ΔΔf (x) = Δ 2 f (x), тогда Δ 2 f (x) = f (x + 2) — 2 f (x + 1) + f (x) и называется разностью второго порядка.

Аналогично можно найти разности третьего, четвертого и т. д. порядков.

Определим разности некоторых важнейших функций.

1) Если f (x) = С, где С — постоянная величина, то
Δf (x) = f (x + 1) – f (x) = С – С = 0.

Понятно, что и все разности следующих порядков будут также равняться нулю.

2) Если f (x) = ax + b, то
Δf = Δf (x + 1) — f (x) = a (x + 1) + b — ax — b = a.

Разница первого порядка линейной функции равна постоянной, а все остальные будут равны нулю.

3) Если f (x) = ax 2 + bx + c, то

Поскольку разница первого порядка является линейной функцией, то разница второго порядка — постоянная, а все последующие разности равны нулю.

4) Если f (x) = a x , то

В экономических исследованиях часто встречаются задачи, в которых время t является независимой переменной, а зависимая переменная определяется для времени t, t + 1, t + 2 и т. д.

Обозначим yt — значение функции y в момент времени t; yt+1 — значение функции в момент, сдвинутый на одну единицу, например, на следующий час, на следующую неделю и т. д., yt+2 — значение функции y в момент, сдвинутый на две единицы и т. д.

Очевидно, что

Откуда:

За разность второго порядка, имеем или
поэтому

Аналогично можно доказать, что

Итак, любую функцию

можно представить в виде: (7.50)
и наоборот.

Определение. Уравнение
(7.51)
называется разностным уравнением n-го порядка.

Решить разностное уравнение n-го порядка — это значит найти такую ​​функцию yt, которая превращает уравнение (7.50) или (7.51) в тождество.

Решение, в котором есть произвольная постоянная, называется общим; решение, в котором постоянная отсутствует, называется частным.

Определение. Уравнение
(7.52)
где a0, a1, . an — постоянные числа, называется неоднородным разностным
уравнением n-го порядка с постоянными коэффициентами.

Если в уравнении (7.52) f (t) = 0, то уравнение называется однородным разностным уравнением n-го порядка с постоянными коэффициентами:
(7.53)

Уравнение есть однородное разностное уравнение первого порядка с постоянными коэффициентами a и b, а уравнение неоднородное разностное уравнение второго порядка с постоянными коэффициентами a, b, c.

ТЕОРЕМА 1. Если решениями однородного разностного уравнения (7.53) является y1 (t) и y2 (t), то его решением будет также функция y1 (t) + y2 (t).

ТЕОРЕМА 2. Если y (t) является решением однородного разностного уравнения (7.53), то его решением будет также функция Ay (t), где А — произвольная постоянная.

ТЕОРЕМА 3. Если y (t) — частное решение неоднородного уравнения (7.52) и y (t, A1, A2, . An) — общее решение однородного уравнения (7.53), то общим решением неоднородного разностного уравнения будет функция: y (t) + y (t, A1, A2, . An).

Эти теоремы схожи с теоремами для дифференциальных уравнений, которые были приведены нами в предыдущем разделе.

Разностные уравнения первого порядка с постоянными коэффициентами

Рассмотрим неоднородное разностное уравнение
(7.54)

Соответствующее ему однородное уравнение будет:
(7.55)

Возьмем функцию и убедимся, что она будет решением уравнения (7.55). Поскольку , тогда . Подставим yt и yt-1 в уравнение (7.55):
Итак, является решением уравнения (7.55).

По теореме (2) общее решение однородного разностного уравнения (7.55) является функция , где А — произвольная постоянная.

Пусть — частное решение неоднородного разностного уравнения (7.54). По теореме (3) общим решением неоднородного разностного уравнения (7.54) будет функция

Частное решение найти нетрудно, если f (t) = α, где α — некоторая постоянная. На самом деле, если где u — постоянная. Подставим в уравнение (7.54), имеем: u — au = α, откуда
Итак, общее решение уравнения (7.54) запишем в виде: .

Разностные уравнения второго порядка с постоянными коэффициентами

Пусть задано неоднородное разностное уравнение второго порядка с постоянными коэффициентами:
(7.56)
и соответствующее ему однородное уравнение
(7.57)

Убедимся, что функция будет решением уравнения (7.58). Подставим в уравнение (7.57) (λ ≠ 0), получим Поскольку λ ≠ 0, то поделим на λ t-2 , имеем λ 2 + aλ + b = 0 (7.58)

Это уравнение называется характеристическим уравнением для уравнения (7.57).

Здесь могут иметь место следующие три случая:

1. D = a 2 – 4b > 0, тогда уравнение (7.58) будет иметь два действительных различных корня.
Общее решение уравнения (7.57) запишется в виде:

а общее решение неоднородного уравнения (7.56) запишется так:

2. D = a 2 – 4b = 0, тогда и и

В этом случае однородное уравнение (7.57) примет вид:
(7.59)
Тогда

Легко убедиться, что решением уравнения (7.59) является также функция
Поэтому общим решением уравнения (7.59) является функция а общим решением неоднородного уравнения (7.56) функция

3. D = a 2 – 4b 2 – 5λ + 6 = 0 будет иметь действительные разные корни (D = 25 – 24 = 1 > 0), λ1 =2, λ2 = 3.
Общим решением однородного уравнения является функция

Далее положим, что yt = y — частное решение неоднородного уравнения, тогда

Таким образом, общим решением неоднородного уравнения является функция Постоянные A1 и A2 определим из начальных условий: y0 = 5, y1 = 9. Тогда для t = 0 и t = 1 соответственно будем иметь:

Решим эту систему уравнений относительно A1 и A2:

Откуда

Итак, — общее решение заданного в условии разностного уравнения.

Примеры применения разностных уравнений в экономических задачах

Пример 1. Пусть некоторая сумма средств выдается под сложный процент p, то к концу t-го года ее размер будет составлять:
Это однородное разностное уравнение первого порядка. Его решением будет функция , где A — некоторая постоянная, которую можно найти из начальных условий.

Если положить y0 = F , то A = F, откуда

Это известная формула величины фонда F, который выдается под сложный процент.

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

Цена равновесия для данной продукции определяется равенством:
а это разностное уравнение первого порядка.

Положим, что функция спроса определяется формулой а функция предложения — формулой

Цена равновесия запишется: то есть Решением этого уравнения является функция Постоянная A определяется из начальных условий, для t = 0 цена составляет p0.

Тогда p0 = A и решением уравнения является функция
Если начальная цена p0 = 0, то pt = 0 для всех значений t.

Следовательно, цена не подлежит изменению.

Вообще говоря, функция предложения — возрастающая, а потому b > 0; а функция спроса — убывающая, и поэтому a

Присылайте задания в любое время дня и ночи в ➔

Официальный сайт Брильёновой Натальи Валерьевны преподавателя кафедры информатики и электроники Екатеринбургского государственного института.

Все авторские права на размещённые материалы сохранены за правообладателями этих материалов. Любое коммерческое и/или иное использование кроме предварительного ознакомления материалов сайта natalibrilenova.ru запрещено. Публикация и распространение размещённых материалов не преследует за собой коммерческой и/или любой другой выгоды.

Сайт предназначен для облегчения образовательного путешествия студентам очникам и заочникам по вопросам обучения . Наталья Брильёнова не предлагает и не оказывает товары и услуги.

Решения разностных уравнений

Разностные уравнения для чайников

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

$$ a_0 y(x) + a_1 y(x+1) + a_2 y(x+2)=f(x), \\ a_0 y(x) + a_1 y(x+1) + a_2 y(x+2)+ a_3 y(x+3)=f(x). $$

Здесь $a_i$ — постоянные коэффициенты, $f(x)$ — правая часть (неоднородность уравнения), $y(x)$ — искомая неизвестная функция.

Решение разностных уравнений практически полностью аналогично решению линейных дифференциальных уравнений с постоянными коэффициентами (см. тут примеры): ищется решение однородного уравнения через составление характеристического уравнения, и частное решение неоднородного уравнения по виду правой части.

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

Задача 1. Решить разностное уравнение: $y(x+2)-4y(x+1)+4y(x)=2^x$

Задача 2. Найти общее решение линейного разностного неоднородного уравнения второго порядка с постоянными коэффициентами.

Задача 3. Решить разностное уравнение третьего порядка

$$ y(x+3)-16y(x+2)+83y(x+1)-140y(x)=0, \quad y(0)=3, y(1)=18, y(2)=120. $$

Задача 4. Найти частное решение однородного разностного уравнения:

Помощь с разностными уравнениями

Если вам нужна помощь с решением задач и контрольных по дифференциальным и разностным уравнениям (и другим разделам математического анализа), обращайтесь в МатБюро. Стоимость подробной консультации от 100 рублей , оформление производится в Word, срок от 1 дня.

VMath

Инструменты сайта

Основное

Навигация

Информация

Действия

Содержание

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

Будем обозначать через $ \mathbb A_<> $ какое-либо из множеств $ \mathbb Z,\mathbb Q, \mathbb R_<> $ или $ \mathbb C_<> $.

Линейное уравнение

Пусть заданы числа $ n \in \mathbb N $ и $ \ < a_1,\dots, a_n \>\subset \mathbb A $. Уравнение $$ x_=a_1 x_+ \dots+ a_n x_K \ npu \ K \in \ <0,1,2,\dots \>\ u \ a_n \ne 0 $$ называется линейным однородным разностным (или возвратным) уравнением $ n_<> $-го порядка (над множеством $ \mathbb A_<> $). Пусть числа $ x_0,\dots,x_ $ заданы. Тогда уравнение определяет линейную рекуррентную 1) (или возвратную) последовательность $ \mathbf n $-го порядка: начиная с $ K=0 $, каждый элемент $ x_ $ этой последовательности определяется через $ n_<> $ предшествующих.

Пример. Уравнение первого порядка $ x_=qx_ $ определяет — при задании $ x_ <0>$ — геометрическую прогрессию.

Пример. Уравнение второго порядка

$$ x_=x_+x_K $$ определяет при $ x_0=1, x_1=1 $ последовательность чисел Фибоначчи — они обозначаются буквой $ F_<> $ $$ \_^\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 не зависит от коэффициентов $ g_<>(x) $). Подробнее ☞ ЗДЕСЬ.

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

Задача. Решить разностное уравнение, т.е. найти выражение для $ x_ $ в виде явной функции от номера $ K_<> $ и «начальных данных» $ x_0,\dots,x_ $. Будем говорить об общем решении, если $ x_0,\dots,x_ $ считаются произвольными.

Пример. Общее решение разностного уравнения $ x_=qx_ $ задается формулой $ x_K = q^K x_0 $.

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

$$ x_=a_1(K) x_+ \dots+ a_n(K) x_K + b_(K) , n \in \mathbb N, K \in \<0,1,2,\dots \>, $$ где $ a_1(K),\dots,a_n(K),b_n(K) $ — некоторые функции от номера $ K_<> $. Примером таких рекуррентных последовательностей являются континуанты. Можно пойти еще дальше и рассматривать разностные уравнения, решениями которых являются не числа, а полиномы: $$kP_(x)-(2k-1)\,xP_(x)+(k-1)\,P_(x) \equiv 0, \quad k\ge 2 \ ; P_0(x)\equiv 1, P_1(x) \equiv x .$$ Полиномы $ \ < P_(x) \> $, удовлетворяющие этому уравнению, известны как полиномы Лежандра.

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

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

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

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

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

Идея решения

Решим сначала уравнение второго порядка $$ x_=p x_+q x_ \ npu \ q\ne 0 . $$ Сделаем из него — формальной заменой $ x_ \rightarrow x^2, x_ \rightarrow x, x_ \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 x_0&=&C_1&+C_2, \\ x_1&=&C_1\lambda_1&+C_2\lambda_2, \end \right. $$ решениями которой являются числа $$ C_1=\frac<\lambda_2-\lambda_1>,\ C_2= \frac<\lambda_1-\lambda_2>\ . $$ В случае 2 получаем систему $$ \left\< \begin x_0&=&C_1, \\ x_1&=&(C_1+C_2)\lambda_1 \end \right. $$ с решениями: $$ C_1=x_0,\ C_2=\frac<\lambda_1>-x_0 \ . $$

Теперь осталось показать, что найденные формулы действительно дают решение разностного уравнения. С этой целью формально подставим, например, первую из формул в уравнение: $$ x_=C_1\lambda_1^+C_2\lambda_2^ \Rightarrow x_=C_1\lambda_1^+C_2\lambda_2^, \ x_=C_1\lambda_1^+C_2\lambda_2^ \Rightarrow $$ $$ C_1\lambda_1^+C_2\lambda_2^ =p (C_1\lambda_1^+C_2\lambda_2^)+q(C_1\lambda_1^+C_2\lambda_2^) \Rightarrow $$ $$ C_1\lambda_1^(\lambda_1^2-p\lambda_1-q)+ C_2\lambda_2^(\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)^ — \left( \frac<1-\sqrt<5>> <2>\right)^ \right] \ . $$ ♦

Пример. Решить уравнение $$ x_=2\, x_-2\, x_ \ .$$ при $ x_1=2,x_2=2 $.

Решение. Соответствующее квадратное уравнение $ x^2-2 x + 2=0 $ имеет корни мнимые $ \lambda_<1,2>=1 \pm \mathbf i $. Согласно приведенному выше алгоритму, решение представляется в виде: $$ x_K=(1+\mathbf i)^+(1-\mathbf i)^ \ . $$ Здесь снова возникает парадоксальная ситуация: вещественная целочисленная последовательность представляется с помощью мнимых чисел. Разрешается «парадокс» теми же самыми рассуждениями, что и в предыдущем примере. Здесь можно пойти и дальше — избавиться от мнимой единицы. Поскольку $$ 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\>_^ <\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_=p x_+q x_ $$ замену переменных так, чтобы получилось линейное уравнение первого порядка. С этой целью подберем параметры $ t_<> $ и $ u_<> $ так, чтобы последовательность $$ x_— t x_ =u ( x_— t x_) $$ совпала с исходной. Очевидно, что параметры $ t_<> $ и $ u_<> $ можно найти из системы уравнений $$ t+u=p,\ — tu=q \ . $$ Полученные формулы позволяют сделать вывод (см. ☞ формулы Виета), что $ t_<> $ и $ u_<> $ могут быть определены как корни квадратного уравнения $$ x^2-px-q=0 \ , $$ которое и возникло у нас «из ниоткуда» в приведенном выше алгоритме. Предположим, что корни этого уравнения различны. Обозначив их, как и ранее, $ t= \lambda_1 $ и $ u= \lambda_2 $, и введя в рассмотрение новую последовательность $ \_^ <\infty>$, связанную со старой формулой $$y_K= x_— \lambda_1x_ , $$ мы получим уравнение для нее в виде $$ y_ =\lambda_2 y_K \ . $$ Это уравнение снова разностное, но уже первого порядка, его решение нам известно (геометрическая прогрессия): $$ y_K = \lambda_2^K y_0 \ . $$ Возвращаемся к исходной переменной — подставляем полученное в формулу, связывающую $ x_K $ и $ y_K $: $$ x_— \lambda_1x_= \lambda_2^K y_0 \ npu \ y_0=x_1- \lambda_1 x_0 \ . $$ Мы снова получили разностное уравнение первого порядка, но, к сожалению, уже неоднородное. Попробуем его решить. Распишем разностное уравнение для последовательных значений $ K $: $$\begin 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 $$ Умножим первое уравнение на $ \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_-\lambda_1^K x_0 = (\lambda_1^+\lambda_1^ \lambda_2 +\dots+ \lambda_1^\lambda_2^j+\dots+ \lambda_2^)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) \ , $$ что полностью совпадает с приведенным выше результатом.

[Эйлер]. Доказать, что (в обозначениях настоящего пункта) имеет место утверждение: отношение

$$ \fracx_K-x_^2> <(-q)^K>$$ будет величиной постоянной, не зависящей от $ K_<> $.

Аналитика

Для разностного уравнения $$ x_=a_1 x_+ \dots+ a_n x_K $$ алгебраическое уравнение, получающееся из него формальной заменой $$ \begin x_ & x_ & \dots & x_K \\ \downarrow & \downarrow & \dots & \downarrow \\ \lambda^n & \lambda^ & \dots & 1 \end $$ то есть уравнение $$ \lambda^n — a_1 \lambda^ — \dots — a_n =0, $$ называется характеристическим уравнением (соответствующим данному разностному уравнению) 2) ; полином $$ f(\lambda)= \lambda^n — a_1 \lambda^ — \dots — a_n $$ будем называть характеристическим полиномом разностного уравнения. Обозначим $ \lambda_<1>,\dots,\lambda_n $ все корни этого полинома, с учетом их кратностей.

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

$$ x_= C_1\lambda_1^K + \dots+ C_n \lambda_n^K \ , $$ числа $ C_<1>,\dots,C_n $ не зависят от $ K_<> $ и определяются с помощью начальных условий из системы линейных уравнений: $$ \left\<\begin 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^C_1 &+ \lambda_2^C_2&+\dots & + \lambda_n^ C_n & = & x_. \end \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_=L_1(K)\lambda_1^ +\dots + L_<\mathfrak r>(K)\lambda_<\mathfrak r>^ , $$ где $ L_1(K),\dots,L_<\mathfrak r>(K) $ — полиномы от $ K $ : $ L_p(K)\in \mathbb C[K],\ \deg L_p 1. Если характеристический полином имеет единственный корень $ \lambda_1 \ne 0 $, т.е. $$ f(\lambda)\equiv (x-\lambda_1)^n , $$ то общее решение разностного уравнения имеет вид: $$ x_=(C_1+C_2K+C_3K^2+\dots+C_K^)\lambda_1^K \ . $$ При заданных значениях $ x_0,x_1,\dots,x_ $ величины $ C_1,\dots,C_ $ могут быть определены из системы линейных уравнений, которая получается подстановкой в общее решение последовательных значений $ K \in \ <0,1,\dots,n-1\>$: $$ \left\<\begin x_0 &=& \lambda_1^0&(C_1&+C_2\cdot 0& + C_3\cdot 0^2& + \dots &+ C_n\cdot 0^) \\ x_1 &=& \lambda_1^1&(C_1&+C_2\cdot 1& + C_3\cdot 1^2& + \dots &+ C_n\cdot 1^) \\ x_2 &=& \lambda_1^2&(C_1&+C_2\cdot 2& + C_3\cdot 2^2& + \dots &+ C_n\cdot 2^) \\ \dots & & \dots \\ x_&=& \lambda_1^&(C_1&+C_2\cdot (n-1)& + C_3\cdot (n-1)^2& + \dots &+ C_n\cdot (n-1)^) \end \right. $$ Образно говоря: если получена общая закономерность, то она должна быть универсальной, т.е. сохраняться и в частных случаях.

Пример. Решить уравнение четвертого порядка $$x_=4\,x_-6\,x_+4\,x_-x_ . $$

Решение. Характеристический полином $ (\lambda-1)^4 $ имеет единственный корень $ \lambda_1=1 $. Общее решение ищется в виде $ x_=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+1)^3 $ — ответ вполне ожидаемый, если обратить внимание на начальные данные… ♦

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

Метод производящего ряда

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

Распишем разностное уравнение $$ x_=a_1 x_+ \dots+ a_n x_K $$ в бесконечную последовательность уравнений, положив $ K=0,1,2,\dots $: $$ \begin x_&-a_1 x_&-a_2 x_&- \dots- a_n x_0&=&0, \\ x_&-a_1 x_&- a_2 x_&- \dots- a_n x_1&=&0, \\ \vdots & & & & & \vdots \\ x_&-a_1 x_&-a_2 x_&- \dots- a_n x_K&=&0, \\ \dots & & &&&\dots \end $$ и дополним эту последовательность, поставив в ее начало еще $ n $ уравнений: $$ \begin 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_&-a_1 x_&-a_2 x_&- \dots- a_ x_0 &=& p_, \end $$ При заданных начальных данных $ \ \> $ из этих уравнений можно однозначно определить числа $ \ \> $.

В объединенной системе произведем домножение уравнений на степени $ \lambda $ $$ \begin 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_&-a_1 x_&-a_2 x_&- \dots- a_ x_0 &&=& p_, & \times \lambda^ \\ x_&-a_1 x_&-a_2 x_&- \dots — a_ x_1 & — a_n x_0&=&0, & \times \lambda^ \\ x_&-a_1 x_&- a_2 x_&- \dots — a_ x_2 & — a_n x_1&=&0, & \times \lambda^ \\ \vdots & & & \dots & & & \dots & \vdots \\ x_&-a_1 x_&-a_2 x_&- \dots- a_ x_ &- a_n x_K&=&0, & \times \lambda^ \\ \dots & & && &&\dots & \dots \end $$ и сложим эти уравнения, собирая по столбцам коэффициенты при $ a_1,\dots, a_n $.

Ряд $$ Z(\lambda)=\sum_^<\infty>x_\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_\lambda^ \, $$ или $$ 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_\lambda^ $ — известный полином. Таким образом производящий ряд получается разложением в ряд по степеням $ \lambda $ рациональной функции $$ \frac <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^-a_2\lambda^— \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>(\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<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 p_0 (\gamma_1\lambda_1^K &+\dots+&\gamma_n\lambda_n^K)+ \\ +p_1(\gamma_1\lambda_1^&+\dots+&\gamma_n\lambda_n^)+ \\ &+\dots + &\\ +p_ (\gamma_1\lambda_1^&+\dots+&\gamma_n\lambda_n^)= \end $$ и просуммируем по столбцам: $$ \begin = \gamma_1\lambda_1^K (p_0+p_1/\lambda_1+\dots+p_/\lambda_1^)+\\ + \gamma_2\lambda_2^K (p_0+p_1/\lambda_2+\dots+p_/\lambda_2^)+ \\ +\dots + \\ + \gamma_n\lambda_n^K (p_0+p_1/\lambda_n+\dots+p_/\lambda_n^)= \end $$ $$ =\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_=3\,x_-2\,x_+(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_=a_1 x_+ \dots+ a_n x_K $$ и начальными данными $ x_0,x_1,\dots,x_ $.

Введем в рассмотрение столбцы, состоящие из $ n_<> $ последовательных элементов этой последовательности, обозначив $$ X_0=\left( \begin x_0 \\ x_1 \\ \vdots \\ x_ \end \right),\ X_1=\left( \begin x_1 \\ x_2 \\ \vdots \\ x_ \end \right),\ X_2=\left( \begin x_2 \\ x_3 \\ \vdots \\ x_ \end \right),\ \dots, X_K=\left( \begin x_K \\ x_ \\ \vdots \\ x_ \end \right),\dots ; $$ а также следующую матрицу, известную как матрица Фробениуса: $$ <\mathfrak F>= \left( \begin 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_ & a_ & & \dots & a_2 & a_1 \end \right)_ $$ Используя правило умножения матриц, а также соотношение между элементами последовательности, получаем: $$ X_1=<\mathfrak F>X_0,\ X_2=<\mathfrak F>X_1,\dots, X_K=<\mathfrak F>X_,\dots, $$ откуда имеем: $$ X_K=<\mathfrak F>^KX_0 \quad npu \quad K\in \mathbb N \ . $$ Искомое выражение для $ x_ $ получится умножением первой строки матрицы $ <\mathfrak F>^K $ на столбец начальных данных $ X_ <0>$. Таким образом, задача решения разностного уравнения сводится к задаче возведения в степень матрицы $ <\mathfrak F>$.

Для нахождения $ <\mathfrak F>^ $ воспользуемся результатами пункта СТРУКТУРА СТЕПЕННОЙ ФУНКЦИИ. Найдя жорданову нормальную форму (ЖНФ) $ <\mathfrak F>_ <\mathfrak J>$ и соответствующую матрицу преобразования базиса $ C_<> $, получим $$ <\mathfrak F>_ <\mathfrak J>=C^ <-1>\mathfrak F C \Longrightarrow <\mathfrak F>^=C <\mathfrak F>_<_<\mathfrak J>>^ C^ <-1>\, . $$ Характеристический полином матрицы Фробениуса: $$\det (<\mathfrak F>— \lambda E)= (-1)^n(\lambda^n-a_1 \lambda^-\dots-a_n) \ . $$ с точностью до знака совпадает с характеристическим полиномом последовательности. Обозначим его корни $ \lambda_1,\dots,\lambda_n $. Если они различны, то жорданова нормальная форма $ <\mathfrak F>_<_<\mathfrak J>> $ диагональна. Если же среди этих корней имеются кратные, то установление структуры ЖНФ потребует усилий; однако же можно заранее утверждать, что эта форма диагональной не будет.

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

Cистемы линейных разностных уравнений

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

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

Решение. Имеем: $$ \left( \begin x_ \\ y_ \end \right) = \left( \begin 1 & 2 \\ 3 & 2 \end \right) \left( \begin x_ \\ y_ \end \right)= \left( \begin 1 & 2 \\ 3 & 2 \end \right)^2 \left( \begin x_ \\ y_ \end \right)=\dots= \left( \begin 1 & 2 \\ 3 & 2 \end \right)^K \left( \begin x_ <0>\\ y_ <0>\end \right)\ . $$ Возводим матрицу в степень по методу, изложенному в разделе ☞ ВЫЧИСЛЕНИЕ ФУНКЦИИ ОТ МАТРИЦЫ. Ее характеристический полином $ f(\lambda)=\lambda^2-3\, \lambda — 4 $ имеет корни $ \ <-1,4\>$. Соответствующие собственные векторы $ [1,-1]^ <\top>$ и $ [2,3]^ <\top>$. Следовательно: $$ \left( \begin 1 & 2 \\ 3 & 2 \end \right)^K= \left( \begin 1 & 2 \\ -1 & 3 \end \right) \left( \begin (-1)^K & 0 \\ 0 & 4^K \end \right) \left( \begin 1 & 2 \\ -1 & 3 \end \right)^ <-1>= $$ $$ =\frac<1> <5>\left( \begin 3\cdot (-1)^K + 2 \cdot 4^K & 2 \cdot (-1)^ + 2 \cdot 4^K \\ 3\cdot (-1)^ + 3 \cdot 4^K & 2 \cdot (-1)^ + 3 \cdot 4^K \end \right) \ . $$ Домножение этой матрицы на столбец $ [x_0,y_0]^<\top>=[1,-1]^ <\top>$ приводит к ответу $ x_K=(-1)^K, y_K=(-1)^ $, который немедленно проверяется «вручную» .

Приведем альтернативное решение настоящего примера — «разделим» переменные. Сделаем подстановку $ K \to K+1 $ в первом уравнении: $$ x_=x_K+2\,y_K=(x_ +2\,y_)+2\, (3\,x_+2\,y_)=7\,x_+6\,y_ \ . $$ Теперь из двух уравнений — нового и исходного — исключим $ y_ $: $$ \left\< \begin x_&-x_ &= & 2\,y_ \\ x_&-7\,x_&=&6\,y_ \end \right. \quad \Rightarrow \quad x_-3\,x_-4\,x_=0 \ . $$ Мы получили разностное уравнение второго порядка относительно величины $ x_ $. Совершенно такое же уравнение получается и относительно другой переменной: $ y_-3\,y_-4\,y_=0 $. Характеристический полином этого уравнения совпадает с характеристическим полиномом матрицы. Различие между генерируемыми этим уравнением рекуррентными последовательностями $ \_^ <\infty>$ и $ \_^ <\infty>$ будет определяться только начальными данными. ♦

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

Асимптотика

Задача. Как ведет себя рекуррентная последовательность $ \_^ <\infty>$ при возрастании $ K $?

Если при любых $ x_0,\dots,x_ $ решение $ x_K $ уравнения $$ x_=a_1 x_+ \dots+ a_n x_K $$ ограничено, то будем называть это уравнение устойчивым. Устойчивое уравнение называется асимптотически устойчивым если $$ x_K \to 0 \quad npu \quad K \to \infty \ .$$ Уравнение называется неустойчивым, если существует хотя бы один набор $ x_0,\dots,x_ $, для которого соответствующая последовательность $ x_K $ неограничена.

Для анализа асимптотики $ \ < x_K \>$ при $ K \to \infty $ обратимся к приведенным ☝ ВЫШЕ теоремам 1 и 2, в которых общее решение разностного уравнения выражено через корни $ \lambda_1,\dots,\lambda_n $ его характеристического уравнения.

Теорема. Уравнение $$ x_=a_1 x_+ \dots+ a_n x_K $$ будет

а) устойчивым тогда и только тогда, когда $ |\lambda_j| \le 1 $ для любого $ j_<> $, и собственные числа, имеющие модуль равный $ 1_<> $, являются простыми для характеристического полинома;

б) асимптотически устойчивым тогда и только тогда, когда $ |\lambda_j| ☞ ЗДЕСЬ. Условие $ 0 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 C_1+C_2&=&0 \\ C_1+(q/p)^NC_2&=&1 \end \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^ $; константы находим из граничных условий: $ C_1=0,C_2=1/N $. Следовательно: $$u(K,N)=K/N \quad npu \ K\in\ <0,\dots,N\>\ .$$

Теперь проанализируем полученные решения. Во втором случае выигрыш тем вероятнее, чем больше стартового капитала имеет игрок, и при $ K>N/2 $ игрок скорее выиграет. В первом случае анализ ситуации несколько сложнее, хотя зависимость вероятности выигрыша от размера стартового капитала сохраняется. Рассмотрим более интересный случай $ p 3) $ 10 $, но тогда можно и не играть! При $ N=100,p=\frac<2><5>,q=\frac<3> <5>$ и при капитале $ K=99 $ игроку имеет смысл вести игру: его выигрыш до $ 100 $ более вероятен, чем разорение «до нитки». А вот при $ K=98 $ лучше не рисковать!

При каком соотношении $ p_<> $ и $ q_<> $ ($ p ☞ АНАЛИТИКА общее решение разностного уравнения позволяет построить и общее решение дифференциального уравнения. В самом деле, если $ \lambda_<\ast>^<> $ — какой-то из корней характеристического уравнения $ \lambda^n — a_1\lambda^-\dots-a_\lambda — a_n=0 $, то одним из решений разностного уравнения будет $ u_K=C\lambda_<\ast>^K $ при $ K\in \mathbb N $ и произвольной константе $ C\in \mathbb C $. Тогда ряд $$ y(x)=\sum_^ <\infty>u_j \frac = C \sum_^ <\infty>\frac<\lambda_<\ast>^jx^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)\>_^ <\mathfrak r>\subset \mathbb C[x], \deg \tilde L_j ♦

Метод конечных разностей

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

При выборе $ N = 8 $ (более мелком дроблении интервала) получаем новое разностное уравнение $$ 13 u_-31 u_ + 19 u_ = 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^+a_2x^ + \dots + a_n = 0 \ . $$ Здесь коэффициенты $ a_1,\dots,a_n \ne 0 $ предполагаются комплексными.

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

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

Доказательство. Предположим сначала, что корни алгебраического уравнения все различны. Тогда это уравнение является характеристическим для рекуррентной последовательности $$ x_=-a_1x_-a_2x_-\dots-a_nx_ $$ и, на основании теоремы 1 общий член этой последовательности может быть представлен в виде: $$ x_K=C_1\lambda_1^K+C_2\lambda_2^K+\dots+C_n\lambda_n^K \ . $$ Тогда $$ \frac>> =\frac+C_2\lambda_2^+\dots+C_n\lambda_n^ > =\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^\left(C_1+C_2\left(\frac<\lambda_2><\lambda_1>\right)^+\dots+C_n\left(\frac<\lambda_n><\lambda_1>\right)^\right)>> \ . $$ По условию теоремы $ |\lambda_j/ \lambda_1| ♦

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

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

Решение. Образуем разностное уравнение пятого порядка: $$ x_=-20\,x_-50\, x_-(6+7<\mathbf i>)x_-129x_K $$ и возьмем в качестве начальных данных набор значений $$ x_0=0,x_1=0,x_2=0,x_3=1,x_4=43/149+5/2 <\mathbf i>\ . $$ Получаем: $$ \begin K & x_ & \approx x_/x_ \\ \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 $$ На рисунке голубым цветом изображены пять первых элементов последовательности $ x_/x_ $, корни полинома обозначены красным. Практически со стопроцентной вероятностью при выборе случайным образом начальных данных последовательность будет сходиться к максимальному по модулю корню полинома $ \lambda_1 \approx -20.291225 -2.430137 \, <\mathbf i>$.

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

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

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

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

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

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

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

Решение. Запускаем рекуррентную последовательность $$ x_=7\,x_-34\,x_+68\, x_-40\,x_ $$ с различными начальными данными $$ \begin x_0=0,x_1=0,x_2=0,x_3=6 \\ \hline \begin K & \approx x_/x_ \\ \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 \end \begin <||c>x_0=0,x_1=0,x_2=1,x_3= <\mathbf i>\\ \hline \begin \approx x_/x_ \\ \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 \end $$ Сходимость неочевидна. Анализируем корни полинома: $$ \lambda_1=2-4 <\mathbf i>, \lambda_2=2+4 <\mathbf i>,\lambda_3=2, \lambda_4=1 .$$ Имеется два максимальных по модулю корня и они комплексно-сопряженные. Теперь понятно почему не должна сходиться первая последовательность: ее начальные данные были все вещественными, вещественными же являются коэффициенты полинома (и разностного уравнения), следовательно последовательность $ x_/x_ $ не могла генерировать мнимые числа в принципе! Вторая последовательность состоит из мнимых чисел, и доказать отсутствие сходимости хотя бы к одному из корней $ \lambda_1 $ или $ \lambda_2 $ уже посложнее. ♦

Алгоритм «деления-вычитания» вычисления корней полинома

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

Сгенерируем на основе рекуррентной последовательности $$ x_=-a_1x_-a_2x_-\dots-a_nx_ $$ новую последовательность $$ y_=x_x_-x_^2 \ . $$ На примерах из предыдущего пункта оценим асимптотику отношения $$ \frac> \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_=-20\,x_-50\, x_-(6+7<\mathbf i>)x_-129x_K $$ при выборе начальных данных $$ x_0=0,x_1=0,x_2=0,x_3=1,x_4=43/149+5/2 <\mathbf i>$$ дает: $$ \begin K & \approx y_ & \approx y_/y_ \\ \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 $$ Видим, что имеется сходимость к какому-то мнимому числу. Оказывается, это число равно произведению двух максимальных по модулю корней полинома $ 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 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 K & \approx y_/y_ \\ \hline 5 & 17.882352 \\ 6 & 18.988157 \\ 7 & 20.085510 \\ 8 & 20.252126 \\ \dots & \dots \\ 12 & 19.993988 \\ \dots & \dots \\ 16 & 19.999734 \end & \begin \approx y_/y_ \\ \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 \end $$ Гипотеза подтверждается: последовательность сходится к квадрату модуля корней. ♦

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

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

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

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

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

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

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

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

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

Задачи

Источники

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

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

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

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

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


источники:

http://www.matburo.ru/ex_ma.php?p1=marazn

http://vmath.ru/vf5/recurr