Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Производящие функции — туда и обратно

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

Введение

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

Идея производящих функций достаточно проста: сопоставим некоторой последовательности — дискретному объекту, степенной ряд g0 + g1z + g2z 2 +… + gnz n +… — объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.

История возникновения производящих функций

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

В 50-х годах XVIII века Эйлер решал следующую задачу: какие грузы можно взвесить с помощью гирь в 2 0 , 2 1 , 2 2 . 2 n грамм и сколькими способами? При решении этой задачи он использовал никому неизвестный на то время метод производящих функций, которому и посвящена данная статья. К этой задаче мы вернёмся немного позже, после того как разберёмся более подробно с устройством производящих функций.

Метод производящих функций

Изучение этого мощного механизма позволяющего решать многие задачи, мы начнём с простенькой задачи: сколькими способами можно расположить в линию чёрные и белые шары, общее количество которых равно n?

Обозначим белый шар символом ○, чёрный — ●, Tn — искомое количество расположений шаров. Символом Ø — обозначим нулевое количество шаров. Как и любое решение комбинаторной задачи начнём с тривиальных случаев:

Если n=1, то очевидно имеется 2 способа — взять либо белый шар ○, либо взять чёрный шар ●, таким образом, T2 = 2.

Если n=2, то имеется 4 способа расположений: ○○, ○●, ●○, ●●.

Рассмотрим случай для n=3. Мы можем начать белым шаром и продолжить 4-мя комбинациями, описанными выше ○○○, ○○●, ○●○, ○●●, или же мы можем начать чёрным шаром и аналогично продолжить 4-мя шарами ●○○, ●○●, ●●○, ●●●.

В итоге количество шаров удвоилось, то есть T3 = 2T2. Аналогично T4 = 2T3, то есть, обобщая для всех n, получаем рекуррентное уравнение Tn = 2Tn-1 которое и является решением для данной задачи. Решение такого уравнения можно легко угадать — Tn = 2 n (так как 2⋅2 n-1 = 2 n ).

А что если у нас плохо с угадыванием? И что делать, если уравнение будет сложнее? А вообще причём здесь производящие функции?

«Просуммируем» все возможные комбинации расположений шаров:

Вопрос о допустимости такой нелепой на первый взгляд суммы опустим. Будем складывать и умножать последовательности шаров. Со сложением всё понятно, но что значит умножить одну последовательность шаров на другую? Перемножив ○● на ●○ мы получим не что иное как ○●●○. Заметим, однако, что произведение шаров в отличие от произведения чисел не является коммутативным, так как ○●⋅●○ ≠ ●○⋅○●. Символ Ø — в произведении играет роль мультипликативной единицы, то есть Ø ⋅ ○○● = ○○● ⋅ Ø = ○○● и коммутирует с любой последовательностью шаров.

Производя с рядом G последовательность манипуляций, а именно вынося за скобки левый белый и чёрный шары

G = Ø + ○ (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + . ) + ● (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + . ) = Ø + ○G +●G

получим уравнение G = Ø + ○G +●G.

Несмотря на то, что умножение некоммутативно, и мы фактически не различаем левое и правое деление, попробуем всё же «решить» это уравнение, на свой страх и риск. Получим,

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Учитывая формулу суммы геометрической прогрессии Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений, имеем

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений.

В этой сумме так же учтены все возможные варианты разбиения в точности по одному разу. Далее воспользуемся формулой бинома Ньютона: Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений, где Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений— число сочетаний из n по k. Тогда с учетом этого имеем:

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Коэффициент при ○ k ● n-k равный числу сочетаний из n по k, показывает общее количество последовательностей из n шаров содержащих ○ шары в количеств k штук и ● шары в количестве n-k штук. Таким образом, общее количество расположений n шаров есть сумма по всем возможным значениям k. Как известно Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений.

Эту формулу можно было получить непосредственно из Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношенийзаменив Ø на 1, а ○ и ● на z (в виду их равнозначности). Получим Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношенийто есть коэффициент при z n равен 2 n .

Обсуждение метода

Так что же позволяет данному методу быть работоспособным при решении различных задач?

Алгоритм решения задачи можно описать примерно следующим образом: рассматривается некоторая бесконечная сумма, которая в конечном итоге представляет собой формальный степенной ряд G(z) = g0 + g1z + g2z 2 +… + gnz n +… причем коэффициенты gk (не заданные в явном виде) — являются ключом к решению исходной задачи. То, что ряд является формальным, говорит о том, что z — является просто символом, то есть вместо него может быть любой объект: число, шар, кость домино и т.д. В отличие от степенных рядов в анализе формальным степенным рядам не придается числовых значений и, соответственно, нет смысла говорить о сходимости таких рядов для числовых аргументов.

G(z) = g0 + g1z + g2z 2 +… + gnz n +… — называется производящей функцией для последовательности . Заметим, однако, что хотя G(z) — функция, это всё таки формальная запись, то есть мы не можем подставить вместо z любое значение z = z0, за исключением z = 0, так как G(0) = g0.

Затем производя различные преобразования с бесконечной суммой G(z) мы преобразуем её к замкнутому (компактному) виду. То есть у производящей функции есть 2 представления: бесконечное и замкнутое и, как правило, для решения задачи необходимо бесконечный вид преобразовать к замкнутому, а затем замкнутый вид разложить в степенной ряд, и тем самым получить значения для коэффициентов gk.

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

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

Итак, задача звучит следующим образом: какие грузы можно взвесить с помощью гирь в 2 0 , 2 1 , 2 2 . 2 n грамм и сколькими способам?

Я не знаю, как долго Эйлер придумывал решение для этой задачи, но оно поражает своей неожиданностью. Посудите сами. Эйлер рассматривает произведение G(z) = (1+z)(1+z 2 )(1+z 4 )… которое после раскрытия скобок представляется в виде бесконечного ряда G(z) = 1 + g1z + g2z 2 + g3z 3 +….

Что же из себя представляют коэффициенты gk? Каждый gk — это коэффициент при z k , а z k — получается как произведение каких-то одночленов z 2m , то есть g k — это в точности число разных представлений числа k в виде суммы некоторых из чисел 1, 2, 2 2 , 2 3 . 2 m ,…. Другими словами gk — это число способов взвешивания груза в k грамм заданными гирями. Как раз то, что мы искали!

Следующий шаг Эйлера поражает не менее предыдущего. Он умножает обе части равенства на (1-z).

(1-z)G(z) = (1-z)(1+z)(1+z 2 )(1+z 4 )(1+z 8 )…
(1-z)G(z) = (1-z2)(1+z 2 )(1+z 4 )(1+z 8 )…
(1-z)G(z) = (1-z 4 )(1+z 4 )(1+z 8 )…
(1-z)G(z) = 1
Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

С одной стороны G(z) = 1 + g1z + g2z 2 + g3z 3 +… с другой стороны мы только что получили Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений. Последнее равенство есть не что иное, как сумма геометрической прогрессии, которая равна Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений. Сопоставляя эти два равенства, получаем g1 = g2 = g3 =… = 1, то есть любой груз в k грамм можно взвесить гирями в 1, 2, 4, 8,… грамм притом единственным способом.

Решение рекуррентных соотношений

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

Начнем со всеми знакомой последовательностью чисел Фибоначчи. Каждый из нас знает её рекуррентный вид: F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2, n ≥ 2. Однако не каждый знает вид этой формулы в замкнутом виде и это не удивительно, ведь она содержит иррациональное число(«золотое сечение») в своём составе.

Умножим каждую строчку на z 0 , z 1 , . z n соответственно:

Просуммируем эти равенства:

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Обозначим левую часть Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Рассмотрим каждое из слагаемых в правой части:

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Имеем следующее уравнение G(z) = z + z G(z) + z 2 G(z) решая которое относительно G(z) находим

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений— производящая функция для последовательности чисел Фибоначчи.

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

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Следующим шагом является нахождение коэффициентов a и b. Для этого умножим дроби на общий знаменатель:

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Подставляя в это уравнение значение z = z1 и z = z2, находим Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Напоследок немного преобразуем выражение для производящей функции

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Теперь каждая из дробей представляет собой сумму геометрической прогрессии.

По формуле Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношенийнаходим Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Но ведь мы искали G(z) в виде Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений. Отсюда делаем вывод, что

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Эту формулу можно переписать в другом виде не используя «золотое сечение»:

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

что достаточно трудно было ожидать, учитывая красивое рекуррентное уравнение.

Давайте запишем общий алгоритм решения рекуррентных уравнений, используя производящие функции. Он записывается в 4 шага:

  1. Запишите одно уравнение, выражающее gn через другие элементы последовательности. Это уравнение должно оставаться справедливым для всех целых n с учетом того, что g-1=g-2=. =0.
  2. Умножьте обе части уравнения на z n и просуммируйте по всем n. В левой части получится сумма Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений, которая равна производящей функции G(z). Правую часть следует преобразовать так, чтобы она превратилась в какое-то другое выражение, включающее G(z).
  3. Решите полученное уравнение, получив для G(z) выражение в замкнутом виде.
  4. Разложите G(z) в степенной ряд и прочитайте коэффициент при z n , это и будет замкнутый вид для gn.

Причина, по которой данный метод работает, заключается в том, что единая функция G(z) представляет всю последовательность gn и это представление допускает многие преобразования.

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

Дифференцирование и интегрирование производящих функций

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

Пусть G = G(z) – производящая функция. Производной этой функции называется функция Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений. Дифференцирование, очевидно, линейная операция, поэтому для того, чтобы понять, как оно действует на производящих функциях, достаточно посмотреть на его действие, на степенях переменной. Имеем

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Тем самым, действие дифференцирования на произвольной производящей функции
G (z) = g0 + g1z + g2z 2 + g3z 3 +… дает G΄(z) = g1 + 2g2z + 3g3z 2 + 4g4z 3 +….

Интегралом называется функция

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Операция дифференцирования обратна операции интегрирования:

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

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

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

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

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

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

Будем следовать вышеописанному алгоритму. Первое условие алгоритма выполнено. Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

z 0 ⋅ g0 = 1,
z 1 ⋅ g1 = z,
z n ⋅ gn = z n ⋅ gn-1 + 2z n ⋅ gn-2 + (-1) n ⋅ z n

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

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

Попытаемся выразить правую часть через G(z). Рассмотрим каждое слагаемое:

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

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

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

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

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

С одной стороны мы искали G(z) в виде Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений, с другой стороны Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений.

Значит, Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений.

Вместо заключения

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

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Возводя в квадрат обе части этого равенства получим

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Приравнивая коэффициенты при x n в левой и правой частях, получаем

Метод решения систем линейных уравнений основанный на использовании рекуррентных соотношений

Эта формула имеет прозрачный комбинаторный смысл, но доказать её непросто. Еще в 80-е годы XX века появились публикации, посвященный этому вопросу.

Видео:Метод Крамера за 3 минуты. Решение системы линейных уравнений - bezbotvyСкачать

Метод Крамера за 3 минуты. Решение системы линейных уравнений - bezbotvy

Применение многочленов от матриц для решения систем рекуррентных уравнений

Рассмотрим систему линейных рекуррентных уравнений

где — коэффициенты системы , — заданные, а — неизвестные функции дискретного аргумента , . При описании дискретных динамических систем аргумент в (7.47) называют дискретным временем .

Систему (7.47) можно записать в матричном виде:

где — квадратная матрица (n-го порядка) коэффициентов системы рекуррентных уравнений, — столбец заданных функций, a — столбец неизвестных.

Решением системы (7.48) называется последовательность столбцов , при подстановке которых в (7.48) получаются верные равенства для всех .

Поставим задачу нахождения решения системы (7.48), удовлетворяющего начальным условиям

где — заданный столбец.

Рассмотрим сначала однородную систему с постоянными коэффициентами

Записывая (7.50) для , последовательно получаем

Следовательно, решение однородной системы (7.50), удовлетворяющее начальным условиям (7.49), имеет вид:

Получим теперь решение системы (7.48). Учитывая (7.49), запишем (7.48) для

и т.д. Следовательно, решение системы (7.48) имеет вид

Первое слагаемое в (7.52) — решение однородной системы (7.50) с начальными условиями (7.49), второе слагаемое — решение системы (7.48) с нулевыми начальными условиями (т.е. при ).

Видео:Численные методы. Лекция 1. Решение систем линейных уравнений. Метод ГауссаСкачать

Численные методы. Лекция 1. Решение систем линейных уравнений. Метод Гаусса

Алгоритм решения системы рекуррентных уравнений

Для нахождения решения системы (7.48) с начальными условиями (7.49) требуется выполнить следующие действия.

1. Найти выражение для степени матрицы одним из способов, рассмотренных ранее.

2. Записать по формуле (7.52) искомое решение.

1. Линейное рекуррентное уравнение с постоянными коэффициентами:

может быть сведено к эквивалентной системе рекуррентных уравнений вида (7.47). Действительно, используя обозначения

или в матричной форме (7.48): с матрицами и

Пример 7.19. Найти решение рекуррентного уравнения с начальными условиями

Решение. В соответствии с пункту 1 замечаний 7.11 составим систему уравнений

где . Требуется найти решение этой системы, удовлетворяющее начальным условиям: .

1. Составим матрицу системы и найдем ее степень , используя второй способ. Характеристический многочлен имеет вторую степень и два простых корня: . Поэтому многочлен (7.44) — линейный: . Для его коэффициентов записываем систему (7.46):

Отсюда . Таким образом,

2. По формуле (7.52) записываем решение системы (учитывая, что ):

Нас интересует только первый элемент этого столбца:

Решение совпадает с найденным в примере 2.15.

Пример 7.20. Найти решение системы рекуррентных уравнений с начальными условиями

Решение. Запишем систему в матричной форме (7.48) и начальные условия

1. Выражение для степени матрицы найдено в примерах 7.17 и 7.18:

2. Выражение, полученное для , справедливо только при 1″ png;base64,iVBORw0KGgoAAAANSUhEUgAAAC8AAAAQCAMAAACx1dbmAAAAM1BMVEVHcEwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADbQS4qAAAAEHRSTlMAiXFYMbEhAcBBoPDQoeAQ0I3cqgAAALZJREFUKM+VktsSwyAIRDWKiFf+/2uLSZvEhkxaXnTGs7KsGvN3UYrwC+ffa3D8zCMlxo+QlyfcNmg7v7A/t7VBux/jzkOe54lJURw8ZrHvop0UdM8P+3axGc89aqQ7XuxbjzybMkEUqPLAIPP6/u0g1OYUHnMpTQs02KLxq/0p0Y1O0al+RvqOCcv51CeZF1UeJBjhacoT6PJehTd9k/R7gdgPul7ei3itcWeYPp/sqv4fRhnzAuOaBpbDogV3AAAAAElFTkSuQmCC» style=»vertical-align: middle;» /> (см. пример 7.18). Поэтому для формулу (7.52) нельзя использовать. Найдем непосредственно из системы (7.53)

Далее записываем искомое решение для , выделяя в формуле (7.52) слагаемые с и

В последней сумме слагаемые не зависят от индекса суммирования, т.е. это сумма одинаковых слагаемых. Поэтому, приводя подобные члены, получаем

Таким образом, решением заданной системы является последовательность столбцов:

Видео:Решение системы уравнений методом Крамера 2x2Скачать

Решение системы уравнений методом Крамера 2x2

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

В этом разделе вы найдете бесплатные примеры решений рекуррентных соотношений методом характеристического уравнения и подбора частного решения по правой части. Также приведены краткие алгоритмы решения для двух методов и пример их использования для последовательности Фибоначчи.

Видео:Лекция 5, Итерационные методы решения систем линейных уравненийСкачать

Лекция 5, Итерационные методы решения систем линейных уравнений

Как решать рекуррентные соотношения?

Для решения рекуррентных соотношений применяют один из двух основных способов:

  • Метод производящих функций
  • Метод характеристического уравнения

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

Метод производящих функций

  1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен $k$) $$a_ = …, \ a_ = …, \ a_ = …, \ … \ a_ = …, ngeqslant k$$
  2. Домножить каждую строчку на $z$ в соответствующей степени $z^ cdot a_$ и сложить все выражения для $n ge 0$. В левой части получится сумма $displaystylesum_^ a_nz^n$ — это производящая функция, назовем ее $G(z)$. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее $G(z)$.
  3. Решить полученное уравнение относительно $G(z)$.
  4. Разложить $G(z)$ в степенной ряд, тогда коэффициент при $z_n$ будет искомым выражением для $a_n$.

Метод характеристических функций

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

  1. Записать соответствующее однородное рекуррентное уравнение (РУ): $$ p_ a_ + p_a_ + . + p_n a_n =f to \ to p_ a_ + p_a_ + . + p_n a_n =0. $$
  2. Выписать для него характеристическое уравнение и найти его корни $lambda_i$ $$ p_ lambda^ + p_lambda^ + . + p_lambda + p_n =0. $$
  3. Выписать согласно полученным корням $lambda_1, . lambda_k$ общее решение однородного рекуррентного соотношения (подробнее теорию см. по ссылке [1] ниже). $$ C_1 lambda_1^n +. +C_k lambda_k^n , mbox , $$ $$ C_1 lambda_1^n + C_2 nlambda_1^n +. +C_m n^m lambda_1^n+. +C_k lambda_k^n mbox , lambda_1 , , m. $$
  4. Подобрать частное решение неоднородного рекуррентного соотношения по виду правой части (особенно удобно для правых частей вида $mu^n*P(n)$, $P(n)$ — многочлен от $n$).
  5. Представить общее решение неоднородного РУ как сумму общего решения соответствующего однородного РУ и частного решения неоднородного РУ.
  6. Подставить начальные условия $a_0, a_1, . a_$ и получить значения констант $C_1, . C_k$.

Видео:21.04 - дискра, рекуррентные соотношенияСкачать

21.04 - дискра, рекуррентные соотношения

Решение для последовательности чисел Фибоначчи

Последовательность чисел Фибоначи — это последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:

$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 , . $$

Числа Фибоначчи растут быстро: $f_=55$, $f_=6765$, а $f_=354224848179261915075$.

Общая формула данной рекуррентной последовательности имеет вид6

Способ 1. Производящяя функция

Начинаем с второго шага алгоритма, домножаем на $z^n$:

$$begin 1cdot f_0 &= &0cdot 1,\ zcdot f_1 &= &1cdot z,\ zcdot f_n & = &(f_+f_)cdot z^n, quad ngeq2.\ end $$

Складываем все строчки:

На третьем шаге алгоритма приводим все суммы к замкнутому виду:

откуда выводим искомое выражение для производящей функции:

Теперь разложим ее в степенной ряд. Для этого сначала разложим знаменатель на множители. Найдем корни уравнения:

Чтобы разложить данные дроби в ряды, используем известное разложение для дроби:

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на $z_1$:

Аналогично (но с делением на $z_2$) действуем со второй дробью:

Преобразуем данное выражение, используя то, что

$$1/z_1=-z_2, quad 1/z_2 = -z_1, quad z_1-z_2=sqrt $$ $$f_n=frac<sqrt>left( biggl( frac<1+sqrt> biggr)^n — biggl( frac<1-sqrt> biggr)^n right). $$

Способ 2. Характеристическое уравнение

Запишем характеристический многочлен для $f_n=f_+f_$, и найдем его корни:

Тогда общее решение однородного рекуррентного уравнения имеет вид:

Осталось найти значения произвольных постоянных $C_1, C_2$ из начальных условий $f_0=0, f_1=1$.

Решая систему, найдем

Итоговое выражение для последовательности чисел Фибоначчи:

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

Видео:9 класс, 11 урок, Методы решения систем уравненийСкачать

9 класс, 11 урок, Методы решения систем уравнений

Примеры решений

Задача 1. Решить рекуррентное соотношение $f(n+2)=-6f(n+1)+7f(n)+n-3$ с начальными условиями $f(0)=2$ и $f(1)=4$, сделать проверку

Задача 2. Решить рекуррентное соотношение $f(n+2)=-2f(n+1)+3f(n)-3^n$ с начальными условиями $f(0)=1$, $f(1)=3$ и сделать проверку

Задача 3. 1. Решить рекуррентное соотношение $f(n+2) =-5f(n+1) -4f(n) + 3n^2$ с начальными условиями $f(0) = 2$, $f(1) = 3$.
2. Проверить, удовлетворяет ли найденное решение начальным условиям и обращает ли оно рекуррентное соотношение в справедливое тождество.

Задача 4. Найти последовательность $$, удовлетворяющую рекуррентному соотношению $a_ + 4 a_ + 3 a_ = 0$ и начальным условиям $a_1=2$, $a_2=4$.

📽️ Видео

Cистемы уравнений. Разбор задания 6 и 21 из ОГЭ. | МатематикаСкачать

Cистемы уравнений. Разбор задания 6 и 21 из ОГЭ.  | Математика

Решение систем линейных алгебраических уравнений методом Крамера.Скачать

Решение систем линейных алгебраических уравнений  методом Крамера.

Рекуррентное вычисление определителя порядка nСкачать

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

МЗЭ 2021 Лекция 11 Метод Ньютона для решения систем нелинейных уравненийСкачать

МЗЭ 2021 Лекция 11 Метод Ньютона для решения систем нелинейных уравнений

Решение системы уравнений методом обратной матрицы - bezbotvyСкачать

Решение системы уравнений методом обратной матрицы - bezbotvy

Решение рекуррентных уравненийСкачать

Решение рекуррентных уравнений

Как привести матрицу к ступенчатому виду - bezbotvyСкачать

Как привести матрицу к ступенчатому виду - bezbotvy

Решение системы линейных уравнений с двумя переменными способом подстановки. 6 класс.Скачать

Решение системы линейных уравнений с двумя переменными способом подстановки. 6 класс.

Решение системы линейных уравнений графическим методом. 7 класс.Скачать

Решение системы линейных уравнений графическим методом. 7 класс.

Способы решения систем нелинейных уравнений. 9 класс.Скачать

Способы решения систем нелинейных уравнений. 9 класс.

Матричный метод решения систем линейных уравнений (метод обратной матрицы)Скачать

Матричный метод решения систем линейных уравнений (метод обратной матрицы)

5 способов вычисления определителя ★ Какой способ лучше?Скачать

5 способов вычисления определителя ★ Какой способ лучше?

Вычислительная математика 3 Итерационные методы решения СЛАУСкачать

Вычислительная математика 3 Итерационные методы решения СЛАУ
Поделиться или сохранить к себе: