Если для значений переменной 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.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_i$ — постоянные коэффициенты, $f(x)$ — правая часть (неоднородность уравнения), $y(x)$ — искомая неизвестная функция.
Решение разностных уравнений практически полностью аналогично решению линейных дифференциальных уравнений с постоянными коэффициентами (см. тут примеры): ищется решение однородного уравнения через составление характеристического уравнения, и частное решение неоднородного уравнения по виду правой части.
Примеры решений разностных уравнений
Задача 1. Решить разностное уравнение: $y(x+2)-4y(x+1)+4y(x)=2^x$
Задача 2. Найти общее решение линейного разностного неоднородного уравнения второго порядка с постоянными коэффициентами.
Задача 3. Решить разностное уравнение третьего порядка
Задача 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\< \beginx_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\< \beginx_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-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 $: $$\beginx_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 $$ алгебраическое уравнение, получающееся из него формальной заменой $$ \beginx_ & 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\<\beginC_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\<\beginx_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 $: $$ \beginx_&-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 $ уравнений: $$ \beginx_<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 $$ При заданных начальных данных $ \ \> $ из этих уравнений можно однозначно определить числа $ \ \> $.
Ряд $$ 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 $: $$ \beginp_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 предыдущего пункта.
Метод производящего ряда позволяет решать и неоднородные разностные уравнения.
Введем в рассмотрение столбцы, состоящие из $ n_<> $ последовательных элементов этой последовательности, обозначив $$ X_0=\left( \beginx_0 \\ x_1 \\ \vdots \\ x_ \end \right),\ X_1=\left( \beginx_1 \\ x_2 \\ \vdots \\ x_ \end \right),\ X_2=\left( \beginx_2 \\ x_3 \\ \vdots \\ x_ \end \right),\ \dots, X_K=\left( \beginx_K \\ x_ \\ \vdots \\ x_ \end \right),\dots ; $$ а также следующую матрицу, известную как матрица Фробениуса: $$ <\mathfrak F>= \left( \begin0 & 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истемы линейных разностных уравнений
Подход предыдущего пункта можно успешно распространить на системы линейных разностных уравнений.
Приведем альтернативное решение настоящего примера — «разделим» переменные. Сделаем подстановку $ K \to K+1 $ в первом уравнении: $$ x_=x_K+2\,y_K=(x_ +2\,y_)+2\, (3\,x_+2\,y_)=7\,x_+6\,y_ \ . $$ Теперь из двух уравнений — нового и исходного — исключим $ y_ $: $$ \left\< \beginx_&-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\< \beginC_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\>.$$
Теперь проанализируем полученные решения. Во втором случае выигрыш тем вероятнее, чем больше стартового капитала имеет игрок, и при $ 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\< \begin3/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( \beginu_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 \ . $$ ♦
Так, в двух последних пунктах решения двух задач из теории линейных дифференциальных уравнений — задачи Коши и краевой задачи — свелись к решению линейных разностных уравнений. В следующем пункте мы упрочим связи между алгебраическим и разностным уравнениями.
Поиск корня полинома методом Бернулли
В разных разделах алгебры (и не только алгебры) слово «решить» может иметь совершенно разный смысл. Поставленная в начале настоящего раздела задача о решении линейного разностного уравнения свелась к нахождению корней его характеристического полинома. Вид общего решения найден и в этом смысле решение задачи получено. Вспомним, однако, что в общем случае нахождение корней полинома представляет собой отдельную задачу, которую также должно решать! Но известно, что корни полинома степени выше четвертой, как правило, не могут быть выражены в виде «хороших» функций от коэффициентов этого полинома (см. ☞ РЕШЕНИЕ УРАВНЕНИЙ В РАДИКАЛАХ ) ; мы можем гарантировать разве что их приближения с заданной точностью… Иными словами, мы свели решение одной задачи (решения разностного уравнения) к другой задаче (решения алгебраического уравнения), которая не имеет «красивого» решения!
Кажется, что мы влипли в порочный круг 4) . На самом деле, ситуация не столь безнадежна. Во-первых, хотя бы в некоторых случаях решение может быть получено явно — когда корни характеристического полинома удается найти в радикалах. Во-вторых, кое-какую пользу от полученного теоретического решения задачи мы получили и для общего случая. Например, мы смогли проанализировать поведение последовательности при возрастании $ K $ — и смогли сделать это «честно»: не привлекая бесконечные процессы численных методов, а только производя конечный набор элементарных операций над коэффициентами характеристического полинома.
В настоящем пункте мы «развернем» приведенную в пункте ☞ АНАЛИТИКА схему решения, сводящую разностное уравнение к алгебраическому: именно, мы будем искать корень алгебраического уравнения с помощью рекуррентной последовательности.
$$ 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_/x_ $ будет сходиться
а) к третьему по величине модуля корню полинома;
б) к минимальному по модуля корню полинома?
Как решить последнюю задачу в общем случае: модифицировать алгоритм так, чтобы находить минимальный по модулю корень полинома?
Подсказка. См. ☞ ЗДЕСЬ.
Теперь посмотрим что произойдет, если нарушается условие единственности корня с максимальным модулем. Такая ситуация может показаться исключительной для полиномов с коэффициентами мнимыми. Так оно и есть: корни такого полинома располагаются на комплексной плоскости случайным образом и вероятность того, что два из них окажутся на одной и той же окружности с центром в точке 0 пренебрежимо мала. Однако, если мы имеем дело с полиномами с коэффициентами вещественными (а этот случай чаще предыдущего встречается в практике вычислений), то ситуация равенства модулей двух корней полинома становится уже не исключительной: комплексно-сопряженные пары корней имеют одинаковые модули (см. ☞ ЗДЕСЬ )!
Пример. Вычислить максимальный по модулю корень полинома
Решение. Запускаем рекуррентную последовательность $$ x_=7\,x_-34\,x_+68\, x_-40\,x_ $$ с различными начальными данными $$ \beginx_0=0,x_1=0,x_2=0,x_3=6 \\ \hline \beginK & \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 \ . $$
$$ 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|\beginx_ & 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 \ . $$
Третий по убыванию модуля корень уравнения может быть получен с помощью линейной рекуррентной последовательности
[3]. Шеннон К.Математическая теория связи. (Shannon C.E. A Mathematical Theory of Communication. Bell System Technical Journal. — 1948. — Т. 27. — С. 379-423, 623–656.)
В частности можно взять в качестве значения независимых переменных x и x + 1 . Разность Δf (x) = f (x + 1) — f (x) называется первой разностью или разностью первого порядка. Она может рассматриваться в свою очередь как функция от x, а потому и для нее можно определить разницу: 
или 
(7.50) 
(7.51) 
(7.52) 
(7.53)
есть однородное разностное уравнение первого порядка с постоянными коэффициентами a и b, а уравнение 
— неоднородное разностное уравнение второго порядка с постоянными коэффициентами a, b, c.
(7.54)
(7.55)
и убедимся, что она будет решением уравнения (7.55). Поскольку 
. Подставим yt и yt-1 в уравнение (7.55): 
является решением уравнения (7.55).
, где А — произвольная постоянная.
— частное решение неоднородного разностного уравнения (7.54). По теореме (3) общим решением неоднородного разностного уравнения (7.54) будет функция 
где u — постоянная. Подставим в уравнение (7.54), имеем: u — au = α, откуда 
.
(7.56) 
(7.57)
будет решением уравнения (7.58). Подставим в уравнение (7.57) 
(λ ≠ 0), получим 
Поскольку λ ≠ 0, то поделим на λ t-2 , имеем λ 2 + aλ + b = 0 (7.58)
и 
и 
(7.59) 
Поэтому общим решением уравнения (7.59) является функция 
а общим решением неоднородного уравнения (7.56) функция 
Постоянные A1 и A2 определим из начальных условий: y0 = 5, y1 = 9. Тогда для t = 0 и t = 1 соответственно будем иметь: 
— общее решение заданного в условии разностного уравнения.
Это однородное разностное уравнение первого порядка. Его решением будет функция 
, где A — некоторая постоянная, которую можно найти из начальных условий.
а спрос на эту продукцию есть функция цены в этом году. Следовательно, спрос: 
а предложение 
а это разностное уравнение первого порядка.
а функция предложения — формулой 
то есть 
Решением этого уравнения является функция 
Постоянная A определяется из начальных условий, для t = 0 цена составляет p0.
Практически со стопроцентной вероятностью при выборе случайным образом начальных данных последовательность будет сходиться к максимальному по модулю корню полинома $ \lambda_1 \approx -20.291225 -2.430137 \, <\mathbf i>$.