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

Видео:Лекция №1.1 Явная и неявная схемы для уравнения теплопроводностиСкачать

Лекция №1.1 Явная и неявная схемы для уравнения теплопроводности

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

Содержание:

Видео:6.3 Решение разностных уравненийСкачать

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

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

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

Если для значений переменной 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 запрещено. Публикация и распространение размещённых материалов не преследует за собой коммерческой и/или любой другой выгоды.

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

Видео:Разностные уравнения | Решение задачСкачать

Разностные уравнения | Решение задач

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

Видео:18+ Математика без Ху!ни. Дифференциальные уравнения.Скачать

18+ Математика без Ху!ни. Дифференциальные уравнения.

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

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

$$ 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 дня.

Видео:Математика без Ху!ни. Линейное неоднородное уравнение 1 порядка. Метод вариации постоянной.Скачать

Математика без Ху!ни. Линейное неоднородное уравнение 1 порядка. Метод вариации постоянной.

VMath

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

Основное

Информация

Действия

Содержание

Видео:Сеточные методы решения дифференциальных уравнений в частных производных.Скачать

Сеточные методы решения дифференциальных уравнений в частных производных.

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

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

Видео:7. Линейные дифференциальные уравнения первого порядка. Метод Бернулли.Скачать

7. Линейные дифференциальные уравнения первого порядка. Метод Бернулли.

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

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

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

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

$$ x_=x_+x_K $$ определяет при $ x_0=1, x_1=1 $ последовательность чисел Фибоначчи — они обозначаются буквой $ F_ $ $$ _^infty= .$$

Пример. Разложение рациональной функции $ 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 , $$ где $ a_1(K),dots,a_n(K),b_n(K) $ — некоторые функции от номера $ K_ $. Примером таких рекуррентных последовательностей являются континуанты. Можно пойти еще дальше и рассматривать разностные уравнения, решениями которых являются не числа, а полиномы: $$kP_(x)-(2k-1),xP_(x)+(k-1),P_(x) equiv 0, quad kge 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 qne 0 . $$ Сделаем из него — формальной заменой $ x_ rightarrow x^2, x_ rightarrow x, x_ rightarrow 1 $ — алгебраическое: $$x^2=pcdot x+qcdot 1 . $$ Анализируем корни:

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

2. Если дискриминант $ mathcal D $ равен нулю (и при этом $ qne 0 $), то квадратное уравнение имеет единственный корень, который мы обозначим $ lambda_1 $. В этом случае решение разностного уравнения ищется в виде $$ x_K=(C_1 + C_2 K)lambda_1^K , $$ где $ C_1,C_2 $ — некоторые, пока неопределенные, постоянные.

В обоих случаях неопределенные коэффициенты $ C_1 $ и $ C_2 $ ищутся из «начальных условий»: получившиеся формулы должны оставаться справедливыми при $ K=0 $ и $ K=1 $. Таким образом, в случае 1 мы получим систему $$ left< begin x_0&=&C_1&+C_2, \ x_1&=&C_1lambda_1&+C_2lambda_2, end right. $$ решениями которой являются числа $$ C_1=frac, C_2= frac . $$ В случае 2 получаем систему $$ left< begin x_0&=&C_1, \ x_1&=&(C_1+C_2)lambda_1 end right. $$ с решениями: $$ C_1=x_0, C_2=frac-x_0 . $$

Теперь осталось показать, что найденные формулы действительно дают решение разностного уравнения. С этой целью формально подставим, например, первую из формул в уравнение: $$ x_=C_1lambda_1^+C_2lambda_2^ Rightarrow x_=C_1lambda_1^+C_2lambda_2^, x_=C_1lambda_1^+C_2lambda_2^ Rightarrow $$ $$ C_1lambda_1^+C_2lambda_2^ =p (C_1lambda_1^+C_2lambda_2^)+q(C_1lambda_1^+C_2lambda_2^) Rightarrow $$ $$ C_1lambda_1^(lambda_1^2-plambda_1-q)+ C_2lambda_2^(lambda_2^2-plambda_2-q)=0 . $$ Но, по предположению, $ lambda_j $ действительно является корнем квадратного уравнения $ x^2-px-q = 0 $. Следовательно, мы получили верное равенство, и решение может быть представлено в указанном виде. То, что это решение обеспечивает правильные «начальные данные» гарантировано тем способом, которым мы подбирали значения параметров $ C_1 $ и $ C_2 $.

Пример. Найти выражение для $ K_ $-го числа Фибоначчи.

Решение. Корни уравнения $$ x^2-x-1=0 $$ различны: $$ lambda_1 = frac<1+sqrt>, lambda_2=frac<1-sqrt> . $$ Следовательно, решение должно иметь вид $ 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<sqrt> left[ left( frac<1+sqrt> right)^ — left( frac<1-sqrt> right)^ right] . $$ ♦

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

Решение. Соответствующее квадратное уравнение $ x^2-2 x + 2=0 $ имеет корни мнимые $ lambda_=1 pm mathbf i $. Согласно приведенному выше алгоритму, решение представляется в виде: $$ x_K=(1+mathbf i)^+(1-mathbf i)^ . $$ Здесь снова возникает парадоксальная ситуация: вещественная целочисленная последовательность представляется с помощью мнимых чисел. Разрешается «парадокс» теми же самыми рассуждениями, что и в предыдущем примере. Здесь можно пойти и дальше — избавиться от мнимой единицы. Поскольку $$ 1+ mathbf i = sqrt left( cos frac + mathbf i sin frac right), quad 1- mathbf i = sqrt left( cos left( — frac right) + mathbf i sin left(-frac right) right), $$ то применением формулы Муавра получаем: $$ x_K=2^ left( cos frac + mathbf i sin frac right) + $$ $$ qquad qquad + 2^left( cos left( — frac right) + mathbf i sin left(-frac right) right) = $$ $$ =2^ cos frac . $$ Таким образом, мы избавились от кажущейся мнимости ответа. То, что на самом деле полученное число является числом целым подтверждается тем, что последовательность $$ left_^ = left< 1, 2^,0,-2^,-1, -2^, 0, 2^, 1,dots right> $$ является циклической и выражения $ 2^ $ возникают только при четных $ K_ $. При домножении на $ 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 $, и введя в рассмотрение новую последовательность $ _^ $, связанную со старой формулой $$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_ $ и сложим со вторым, получим: $$ 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(x_1- lambda_1 x_0) , $$ что полностью совпадает с приведенным выше результатом.

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

$$ frac<x_x_K-x_^2> $$ будет величиной постоянной, не зависящей от $ K_ $.

Видео:Вычислительная математика 16 Разностные уравненияСкачать

Вычислительная математика 16 Разностные уравнения

Аналитика

Для разностного уравнения $$ 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_,dots,lambda_n $ все корни этого полинома, с учетом их кратностей.

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

$$ x_= C_1lambda_1^K + dots+ C_n lambda_n^K , $$ числа $ C_,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)^<_1>times dots times (lambda-lambda_)^<_>, quad lambda_k ne lambda_ mbox k ne ell , _1 + dots + _ =n, $$ то общее решение разностного уравнения имеет вид: $$ x_=L_1(K)lambda_1^ +dots + L_(K)lambda_^ , $$ где $ L_1(K),dots,L_(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 $: $$ left<begin x_0 &=& lambda_1^0&(C_1&+C_2cdot 0& + C_3cdot 0^2& + dots &+ C_ncdot 0^) \ x_1 &=& lambda_1^1&(C_1&+C_2cdot 1& + C_3cdot 1^2& + dots &+ C_ncdot 1^) \ x_2 &=& lambda_1^2&(C_1&+C_2cdot 2& + C_3cdot 2^2& + dots &+ C_ncdot 2^) \ dots & & dots \ x_&=& lambda_1^&(C_1&+C_2cdot (n-1)& + C_3cdot (n-1)^2& + dots &+ C_ncdot (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_&&&&=&p_0, \ x_&-a_1 x_& &&=& p_1, \ x_&-a_1 x_&-a_2 x_& &=& p_1, \ vdots && & & & vdots \ x_&-a_1 x_&-a_2 x_&- dots- a_ x_0 &=& p_, end $$ При заданных начальных данных $ <x_0,x_1,dots,x_> $ из этих уравнений можно однозначно определить числа $ <p_0,p_1,dots,p_> $.

В объединенной системе произведем домножение уравнений на степени $ lambda $ $$ begin x_&&&&&=&p_0, & times 1 \ x_&-a_1 x_&& &&=& p_1, & times lambda \ x_&-a_1 x_&-a_2 x_& &&=& 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_^x_lambda^j=x_0+x_1lambda+x_2lambda^2+dots+x_K lambda^K + dots $$ называется производящим рядом рекуррентной последовательности.

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

$$ и, если нам удастся найти явное выражение для коэффициента при $ lambda^K $, то он и будет решением разностного уравнения.

Полином $ f^(lambda) = 1-a_1lambda-a_2lambda^2-dots- a_nlambda^n $ не совпадает с характеристическим полиномом $ f(lambda)= lambda^n-a_1lambda^-a_2lambda^- dots — a_n $ разностного уравнения, но очень на него похож: они связаны соотношением $$ f^(lambda) equiv lambda^n f(1/lambda) , $$ и корни $ f^(lambda) $ равны обратным величинам корней полинома $ f(lambda) $, т.е. $ 1/lambda_1,dots,1/lambda_n $ (см. свойство 3 ☞ ЗДЕСЬ ). Если все эти корни различны, то дробь $ 1/f^(lambda) $ может быть разложена на простейшие дроби вида: $$ frac<f^(lambda)>=frac = $$ $$ =frac+frac+dots+frac , $$ где $ gamma_1, gamma_2,dots, gamma_n $ — комплексные числа, которые можно однозначно выразить через $ lambda_1,dots,lambda_n $ (эти выражения для дальнейшего несущественны). Теперь каждую простейшую дробь раскладываем в степенной ряд: $$ frac=gamma_j left(1+lambda_j cdot lambda+ lambda_j^2 cdot lambda^2+dots+ lambda_j^K cdot lambda^K+dots right) $$ и, следовательно, получаем разложение для производящего ряда $$ Z(lambda)=frac

= $$ $$ =P(lambda) left[ (gamma_1+dots+gamma_n)+(gamma_1lambda_1+dots+gamma_nlambda_n)lambda+dots+(gamma_1lambda_1^K+dots+gamma_nlambda_n^K)lambda^K + dots right] . $$ Вытаскиваем из него коэффициент при $ lambda^K $: $$ begin p_0 (gamma_1lambda_1^K &+dots+&gamma_nlambda_n^K)+ \ +p_1(gamma_1lambda_1^&+dots+&gamma_nlambda_n^)+ \ &+dots + &\ +p_ (gamma_1lambda_1^&+dots+&gamma_nlambda_n^)= end $$ и просуммируем по столбцам: $$ begin = gamma_1lambda_1^K (p_0+p_1/lambda_1+dots+p_/lambda_1^)+\ + gamma_2lambda_2^K (p_0+p_1/lambda_2+dots+p_/lambda_2^)+ \ +dots + \ + gamma_nlambda_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) $ при $ jin $, мы получим общее решение разностного уравнения приведенное в теореме 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 ; $$ а также следующую матрицу, известную как матрица Фробениуса: $$ = 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=X_0, X_2=X_1,dots, X_K=X_,dots, $$ откуда имеем: $$ X_K=^KX_0 quad npu quad Kin mathbb N . $$ Искомое выражение для $ x_ $ получится умножением первой строки матрицы $ ^K $ на столбец начальных данных $ X_ $. Таким образом, задача решения разностного уравнения сводится к задаче возведения в степень матрицы $ $.

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

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

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

Видео:Самый короткий тест на интеллект Задача Массачусетского профессораСкачать

Самый короткий тест на интеллект Задача Массачусетского профессора

Асимптотика

Задача. Как ведет себя рекуррентная последовательность $ _^ $ при возрастании $ 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 $ неограничена.

Для анализа асимптотики $ $ при $ 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. Пусть $ qne p $. Применяем теорему 1: $$u(K,N)=C_1 1^K+C_2 (q/p)^K=C_1+C_2 (q/p)^K .$$ Константы $ C_j $ находим из граничных условий: $$ left< begin C_1+C_2&=&0 \ C_1+(q/p)^NC_2&=&1 end right. Longrightarrow C_1=-C_2=frac $$ $$Longrightarrow u(K,N)= frac quad npu Kin .$$

2. Пусть теперь $ q=p=frac $ (проигрыш и выигрыш равновероятны). Применяем теорему 2: $ u(K,N)=(C_1+C_2K)cdot 1^ $; константы находим из граничных условий: $ C_1=0,C_2=1/N $. Следовательно: $$u(K,N)=K/N quad npu Kin .$$

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

При каком соотношении $ p_ $ и $ q_ $ ($ p ☞ АНАЛИТИКА общее решение разностного уравнения позволяет построить и общее решение дифференциального уравнения. В самом деле, если $ lambda_^ $ — какой-то из корней характеристического уравнения $ lambda^n — a_1lambda^-dots-a_lambda — a_n=0 $, то одним из решений разностного уравнения будет $ u_K=Clambda_^K $ при $ Kin mathbb N $ и произвольной константе $ Cin mathbb C $. Тогда ряд $$ y(x)=sum_^ u_j frac = C sum_^ frac<lambda_^jx^j>=Ce^ <lambda_x> $$ дает один из интегралов дифференциального уравнения. Если все корни $ lambda_,dots,lambda_n $ характеристического уравнения простые, то общий интеграл дифференциального уравнения будет иметь вид $$ C_1 e^ + dots + C_n e^ . $$ Если же среди корней характеристического уравнения имеются кратные, то общий интеграл записывается в виде $$ tilde L_1(x)e^ + dots + tilde L_(x) e^ <lambda_x> , $$ где $ tilde L_1(x),dots,tilde L_(x) $ — полиномы по $ x_ $, $ _^ subset mathbb C[x], deg tilde L_j ♦

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

Пример. Найти решение дифференциального уравнения $$ y^ -3, y^ + 4, y=0 , $$ удовлетворяющее условиям $ y(0)=0, y(1)=1 $, и вычислить значение $ y(0.5) $.

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

Решение. Для данного примера удается построить точное решение: $$ y(x)=frac< e^sin (sqrt/2 x )><sin (sqrt/2)> quad u quad y( 1/2) approx 0.299303 . $$ Наша задача сейчас — проиллюстрировать приближенный метод решения краевой задачи (а полученное аналитическое решение будем использовать для контроля точности). Этот метод заключается в дискретизации непрерывного процесса — вместо нахождения общего выражения для решения $ y(x) $, подобного только что представленному, мы ставим целью нахождение значений $ y(x_j) $ в некоторых точках интервала $ [0_,1] $. Разобьем этот интервал на $ N_ $ равных частей точками $$ x_j=j h quad npu quad jin , h=1/N . $$ Вспомнив определение производной функции как предела: $$ y^(x)= lim_ frac $$ будем считать, что при достаточно малых значениях $ h_>0 $, ошибка в равенствах $$ y^(x_j) approx frac quad u quad y^(x_j) approx frac $$ пренебрежимо мала. Таким образом, мы получаем приближение для производной (неизвестной нам функции) через значения этой же функции. Какое из двух этих приближений взять — не очень принципиально. С целью «сохранения равноправия» в окрестности $ x_ $, возьмем в качестве приближения $$ y^(x_j) approx frac left( frac + frac right) = frac . $$ Для значения второй производной $ y^(x) $ в точке $ x_ $ приближение строим в виде $$ y^(x_j) approx frac left( frac — frac right)= $$ $$ = frac<y(x_+h)-2y(x_j)+y(x_j-h)> . $$ С использованием этих приближений, а также обозначения $$ u_j = y(x_j) quad npu quad j in , $$ заменяем исходное дифференциальное уравнение на уравнение $$ (u_-2, u_j — u_) — frac 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 jin $$ перепишутся в виде $$ 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 approx 0.295665 , $$ что неплохо согласуется с точным ответом.

При выборе $ N = 8 $ (более мелком дроблении интервала) получаем новое разностное уравнение $$ 13 u_-31 u_ + 19 u_ = 0 quad npu quad jin , $$ которое относительно $ u_ $ будет иметь решение $$ u_4=frac 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 jin . $$ Тогда линейная рекуррентная последовательность $$ x_=-a_1x_-a_2x_-dots-a_nx_ $$ практически для любых начальных данных $ x_0,dots,x_ $ будет обладать свойством $$ lim_ frac<x_><x_> = lambda_1 , $$ т.е. отношение двух соседних членов последовательности будет стремиться к максимальному по модулю корню алгебраического уравнения.

Доказательство. Предположим сначала, что корни алгебраического уравнения все различны. Тогда это уравнение является характеристическим для рекуррентной последовательности $$ x_=-a_1x_-a_2x_-dots-a_nx_ $$ и, на основании теоремы 1 общий член этой последовательности может быть представлен в виде: $$ x_K=C_1lambda_1^K+C_2lambda_2^K+dots+C_nlambda_n^K . $$ Тогда $$ frac<x_><x_> =frac<C_1lambda_1^+C_2lambda_2^+dots+C_nlambda_n^ > =frac<displaystyle<lambda_1^Kleft(C_1+C_2left(fracright)^K+dots+C_nleft(fracright)^K right) >><displaystyle<lambda_1^left(C_1+C_2left(fracright)^+dots+C_nleft(fracright)^right)>> . $$ По условию теоремы $ |lambda_j/ lambda_1| ♦

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

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

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

При каком наборе начальных данных последовательность $ 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 x_0=0,x_1=0,x_2=1,x_3= \ hline begin approx x_/x_ \ hline 7+34 \ 4.883817+0.564315 \ 0.398454+0.417510 \ -18.958354+23.801257 \ 4.302668+0.516309 \ -0.631595+0.556795 \ 21.917361+15.773371 \ 3.407653+0.432279 \ -1.771117+0.731887 end end $$ Сходимость неочевидна. Анализируем корни полинома: $$ lambda_1=2-4 , lambda_2=2+4 ,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<y_> quad npu quad K to infty . $$

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

$$ f(x)= x^5+20,x^4-50,x^3-(6+7),x-129 $$ разностное уравнение $$ x_=-20,x_-50, x_-(6+7)x_-129x_K $$ при выборе начальных данных $$ x_0=0,x_1=0,x_2=0,x_3=1,x_4=43/149+5/2 $$ дает: $$ begin K & approx y_ & approx y_/y_ \ hline 5 & -1021.889329+3566.979865 , & \ 6 & 171845.562159+54605.729066 , & 1.392427-48.575679 , \ 7 & 3593515.455351-9699634.071978 , & 2.702763-57.302733 ,\ 8 & & 2.056010-56.461741 , \ 9 & & 1.577875-55.791210 , \ vdots & & dots \ 12 & & 1.673367-55.241399 , \ vdots & & dots \ 15 & & 1.631486-55.261773 , \ vdots & & dots \ 18 & & 1.642333-55.263835 , \ vdots & & dots \ 24 & & 1.640619-55.263355 , end $$ Видим, что имеется сходимость к какому-то мнимому числу. Оказывается, это число равно произведению двух максимальных по модулю корней полинома $ f(x) $: $$ lambda_1 lambda_2 approx (-20.291225-2.430137 ,) (0.241854+2.694544,) approx $$ $$ approx 1.640589-55.263344 , . $$ Проверим теперь полином $ 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= \ 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 , \ 19.040624+0.076125 , \ 19.769628-0.020615 , \ 20.115168-0.025721 , \ dots \ 19.991971+0.000361 , \ dots \ 19.999996+0.000032, 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 jin . $$ Тогда линейная рекуррентная последовательность $$ x_=-a_1x_-a_2x_-dots-a_nx_ $$ — практически для любых начальных данных $ x_0,dots,x_ $ будет обладать свойством $$ lim_ frac<x_x_-x_^2><x_x_-x_^2> = lambda_1 lambda_2 . $$

Доказательство. Предположим для простоты, что все корни $ lambda_3,dots,lambda_n $ различны. Тогда, используя рассуждения аналогичные приведенным в доказательстве теоремы Бернулли , получаем $$ x_x_-x_^2=C_1C_2left(frac-1 right)^2lambda_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<H_> = lambda_1lambda_2lambda_3 . $$

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

Видео:6-2. Метод сетокСкачать

6-2. Метод сеток

Задачи

Видео:Задача Коши ➜ Частное решение линейного однородного дифференциального уравненияСкачать

Задача Коши ➜ Частное решение линейного однородного дифференциального уравнения

Источники

[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

📽️ Видео

Линейное неоднородное дифференциальное уравнение второго порядка с постоянными коэффициентамиСкачать

Линейное неоднородное дифференциальное уравнение второго порядка с постоянными коэффициентами
Поделиться или сохранить к себе: