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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

G = Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ○○○ + ○○● + ○●○ + ○●● + ●○○ + ●○● + ●●○ + ●●● +…

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

Производя с рядом 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) = g 0 + g 1 z + g 2 z 2 +… + g n z n +… причем коэффициенты g k (не заданные в явном виде) - являются ключом к решению исходной задачи. То, что ряд является формальным, говорит о том, что z - является просто символом, то есть вместо него может быть любой объект: число, шар, кость домино и т.д. В отличие от степенных рядов в анализе формальным степенным рядам не придается числовых значений и, соответственно, нет смысла говорить о сходимости таких рядов для числовых аргументов.

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

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

Отвечая на поставленный вначале вопрос можно сказать так: успех данного метода связан с возможностью записать производящую функцию в замкнутом виде. Так, например, производящая функция для последовательности <1, 1, 1, ..., 1> в бесконечном виде представляется как 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 + g 1 z + g 2 z 2 + g 3 z 3 +….

Что же из себя представляют коэффициенты g k ? Каждый g k - это коэффициент при z k , а z k - получается как произведение каких-то одночленов z 2m , то есть g k - это в точности число разных представлений числа k в виде суммы некоторых из чисел 1, 2, 2 2 , 2 3 ,..., 2 m ,…. Другими словами g k - это число способов взвешивания груза в 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 + g 1 z + g 2 z 2 + g 3 z 3 +… с другой стороны мы только что получили . Последнее равенство есть не что иное, как сумма геометрической прогрессии, которая равна . Сопоставляя эти два равенства, получаем g 1 = g 2 = g 3 =… = 1, то есть любой груз в k грамм можно взвесить гирями в 1, 2, 4, 8,… грамм притом единственным способом.

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

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

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

Итак, имеем

F 0 = 0,
F 1 = 1,
F n = F n-1 + F n-2 , n ≥ 2

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

Z 0 ⋅ F 0 = 0,
z 1 ⋅ F 1 = z,
z n ⋅ F n = z n ⋅ F n-1 + z n ⋅ F n-2 , n ≥ 2

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

Обозначим левую часть

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

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

Производящая функция для последовательности чисел Фибоначчи.

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

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

Подставляя в это уравнение значение z = z 1 и z = z 2 , находим

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

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

По формуле находим

Но ведь мы искали G(z) в виде . Отсюда делаем вывод, что

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

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

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

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

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

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

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

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

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

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

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

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

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

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

G 0 = 1,
g 1 = 1,
g n = g n-1 + 2g n-2 + (-1) n

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

Z 0 ⋅ g 0 = 1,
z 1 ⋅ g 1 = z,
z n ⋅ g n = z n ⋅ g n-1 + 2z n ⋅ g n-2 + (-1) n ⋅ z n

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

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

Составляем уравнение:

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

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

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

С одной стороны мы искали G(z) в виде , с другой стороны .

Значит, .

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

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

в степенной ряд имеет вид , то есть справедливо равенство:

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

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

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

Числа Фибоначчи.

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

Отсюда видно, что всегда может быть сведён к факториалу от меньшего числа.

Хорошей иллюстрацией к построению рекуррентных соотношений является задача Фибоначчи. В своей книге в 1202 г. итальянский математик Фибоначчи привел следующую задачу. Пара кроликов приносит приплод раз в месяц двух крольчат (самку и самца), причём новорождённые крольчата через два месяца после рождения сами приносят приплод. Сколько кроликов появится через год, если в начале была одна пара кроликов.

Из условия задачи следует, что через месяц будет две пары кроликов, через два месяца приплод даст только первая пара кроликов, появившихся два месяца назад, поэтому всего будет 3 пары кроликов. Ещё через месяц будет уже 5 пар. И так далее.

Обозначим через количество пар кроликов по истечении месяцев с начала года. Тогда через месяц количество пар кроликов можно найти по формуле:

Эта зависимость называется рекуррентным соотношением . Слово «рекурсия» означает возврат назад (в нашем случае – возврат к предыдущим результатам).

По условию, и , тогда по соотношению имеем: , , и т.д., .

Определение 1: Числа называются числами Фибоначчи . Это – известная в математике последовательность чисел:

1, 1, 2, 3, 5, 8, 13, 21, ...

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

Установим связь между числами Фибоначчи и комбинаторной задачей. Пусть требуется найти число - последовательностей, состоящих из нулей и единиц, в которых никакие две единицы не стоят подряд.

Возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар «предков» данной пары (включая и исходную), а нулями – все остальные месяцы. Например, последовательность устанавливает такую «генеалогию» – сама пара появилась в конце 11-го месяца, ее родители в конце 7-го месяца, «дед» – в конце 5-го месяца, и «прадед» в конце 2-го месяца. Первоначальная пара шифруется последовательностью . Ни в одной последовательности две единицы не могут стоять подряд – только что появившаяся пара не может принести приплод через месяц. Очевидно, различным последовательностям отвечают различные пары и обратно.

Таким образом, число последовательностей с указанными свойствами, равно .

Теорема 1: Число находится как сумма биномиальных коэффициентов:. Если – нечетно, то . Если – четно, то . Иначе: – целая часть числа .

Доказательство: В самом деле, - число всех последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число таких последовательностей, содержащих ровно единиц и нулей, равно , при этом , тогда изменяется от 0 до . Применяя правило суммы, получаем данную сумму.

Это равенство можно доказать иначе. Обозначим:

Из равенства , следует, что . Кроме этого, ясно, что и . Так как обе последовательности и удовлетворяют рекуррентному соотношению , то , и .

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

Например, – рекуррентное соотношение второго порядка, а рекуррентное соотношение 3-го порядка. Соотношение Фибоначчи является соотношением второго порядка.

Определение 3:Решением рекуррентного соотношения является последовательность, удовлетворяющая этому соотношению.

Если задано рекуррентное соотношение ‑ го порядка, то ему удовлетворяют бесконечно много последовательностей, т.к. первые элементов можно задать произвольно. Но если первые элементов заданы, то остальные члены определяются однозначно.

Например, соотношению Фибоначчи кроме рассмотренной выше последовательности 1, 1, 2, 3, 5, 8, 13, 21, ..., могут удовлетворять также и другие последовательности. К примеру, последовательность 2, 2, 4, 8, 12,... строится по тому же принципу. Но если задать начальные члены (их в последовательности Фибоначчи - 2), то решение определяется однозначно. Начальных членов берут столько, каков порядок соотношения.

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

Мы будем говорить, что некоторая последовательность является решением данного рекуррентного соотношения, если при подстановке этой последовательности соотношение тождественно выполняется.

Например, последовательность является одним из решений соотношения: . Это легко проверить обычной подстановкой.

Определение 4: Решение рекуррентного соотношения ‑ го порядка называется общим , если оно зависит от произвольных постоянных , меняя которые, можно получить любое решение данного соотношения.

Например, для соотношения общим решение будет .

В самом деле, легко проверяется, что оно будет решением нашего соотношения. Покажем, что любое решение можно получить в таком виде. Пусть и – произвольны.

Тогда найдутся такие и , что

Очевидно, для любых , система уравнений имеет единственное решение.

Определение 5: Рекуррентное соотношение называется линейным , если оно записывается в виде:

где - числовые коэффициенты.

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

Рассмотрим сначала соотношение 2-го порядка .

Решение этого соотношения основано на следующих утверждениях.

Теорема 2: Если и - являются решением данного рекуррентного соотношения 2-го порядка, то для любых чисел и последовательность также является решением этого соотношения.

Теорема 3: Если число является корнем квадратного уравнения , то последовательность является решением рекуррентного соотношения .

Из теорем 2, 3 вытекает следующее правило решения линейных рекуррентных соотношений 2-го порядка.

Пусть дано рекуррентное соотношение .

1) Составим квадратное уравнение , которое называется характеристическим для данного соотношения. Найдём все корни этого уравнения (даже кратные и комплексные).

2) Составим общее решение рекуррентного соотношения. Его структура зависит от вида корней (одинаковые они или различные).

а) Если это соотношение имеет два различных корня и , то общее решение соотношения имеет вид .

Действительно, из теорем 2, 3 следует, что - решение и система уравнений

Имеет единое решение, т.к. при условии .

Например, для чисел Фибоначчи, имеем . Характеристическое уравнение имеет вид: . Решая последнее уравнение, получим корни.

Транскрипт

1 РЕШЕНИЕ РЕКУРРЕНТНЫХ УРАВНЕНИЙ Обозначим через значение некоторого выражения при подстановке в него целого числа Тогда зависимость члена последовательности от членов последовательности F F со значениями аргумента меньшими называется рекуррентным уравнением Примером может служить уравнение вида: F Рекуррентное уравнение имеет порядок если оно позволяет выразить член последовательности F через члены F F Таким образом уравнение имеет порядок а уравнение F 3 6 имеет порядок 3 Если задано рекуррентное уравнение -го порядка то ему удовлетворяет бесконечно много последовательностей Но если первые элементов заданы то все остальные определяются однозначно А именно элемент выражается через элемент F через элементы F и тд Алгоритм решения рекуррентного уравнения приведен на Рис Отметим что уравнение описывает так называемую последовательность чисел Фибоначчи: 3 F 4 3 F 5 5 F F 8 Фактически алгоритм решения сводится к тому что на каждом шаге пользуясь начальными членами и заданным уравнением мы вычисляем очередной член последовательности Действуя таким образом мы рано или поздно получим любой член последовательности Однако при этом нам придется вычислять и все предыдущие члены Во многих случаях удобнее иметь явную формулу для -го члена последовательности Будем говорить что некоторая последовательность является решением рекуррентного уравнения если при подстановке ее в уравнение последнее обращается в тождество Например последовательность 4 8 является одним из решений рекуррентного уравнения 3 Действительно общий член этой последовательности имеет вид Но при любом имеет место тождество Значит 3 Таким образом является решением рекуррентного уравнения Решение рекуррентного уравнения называется общим если оно зависит от произвольных постоянных C C и путем подбора этих постоянных можно получить любое решение данного уравнения Например для уравнения 5 6 общим решением будет F C C 3 3 Легко проверить что последовательность 3 обращает в тождество Поэтому достаточно показать что любое решение можно представить в виде 3 Но любое

2 решение однозначно определяется значениями и Поэтому надо показать что для любых чисел и найдутся такие и C что F C C 3C C 3 C Определитель системы равен При любых и система имеет решение Поэтому 3 действительно является решением F; F; I: FFF; FF; FF; F Рис Алгоритм формирования последовательности чисел Фибоначчи

3 ЛИНЕЙНЫЕ РЕКУРРЕНТНЫЕ УРАВНЕНИЯ Для решения произвольных рекуррентных уравнений общих правил не существует Однако есть весьма часто встречающийся класс уравнений решаемый единообразным методом Это рекуррентные уравнения вида f 4 где - некоторые числа постоянные коэффициенты а f - некоторая функция от Такие уравнения называются линейными потому что элементы последовательности F связаны линейной зависимостью Если при этом функция f то уравнения такого вида называются однородными или однородными уравнениями с постоянными коэффициентами В противном случае уравнения называются неоднородными ЛИНЕЙНЫЕ ОДНОРОДНЫЕ РЕКУРРЕНТНЫЕ УРАВНЕНИЯ Линейные однородные рекуррентные уравнения с постоянными коэффициентами имеют вид F 5 где - некоторые числа Очевидно что последовательность всегда будет решением любого однородного уравнения Такое решение называется тривиальным решением Сначала рассмотрим как решаются такие уравнения при то есть изучим уравнения вида F 6 Решение этих уравнений основывается на следующих двух утверждениях: Если F и F являются решениями рекуррентного уравнения 6 то при любых числах A и B последовательность F AF BF также является решением этого уравнения Действительно по условию F F F F Умножим эти равенства на тождества В результате получим: A и F F B соответственно и сложим полученные [ AF BF ] [ AF BF ] AF BF А это означает что F AF BF является решением уравнения 6 Если число является корнем уравнения

4 то последовательность является решением рекуррентного уравнения F Докажем это утверждение Пусть то и Подставляя эти значения в 6 получаем равенство или Оно справедливо так как по условию При имеем тривиальное решение любая последовательность вида где Заметим что наряду с последовательностью { } также является решением уравнения 6 Для доказательства этого факта достаточно использовать утверждение положив в нем A B Из утверждений и вытекает следующее правило решения линейных однородных рекуррентных уравнений второго порядка Пусть дано рекуррентное уравнение 6 F Составим квадратное уравнение 7 которое называется характеристическим уравнением данного рекуррентного уравнения Если это уравнение имеет два различных корня и то общее решение уравнения 6 имеет вид C C Докажем это утверждение Заметим сначала что согласно утверждению последовательности и являются решениями данного рекуррентного F F уравнения А тогда по утверждению и C C является его решением Надо только показать что любое решение уравнения 6 можно записать в этом виде Но любое решение уравнения второго порядка определяется значениями и Поэтому достаточно показать что система уравнений C C C C имеет решение при любых и Очевидно что этими решениями являются При C F C система всегда имеет решение Рассмотрим пример Как уже было сказано последовательность чисел Фибоначчи 3583 можно получить с помощью рекуррентного уравнения F 8 Для него характеристическое уравнение имеет вид Корнями этого квадратного уравнения являются числа

5 5 5 и Поэтому общее решение уравнения Фибоначчи имеет вид 5 5 C C 9 Начальными условиями являются значения F F В соответствии с этими начальными условиями получаем для и C систему уравнений C C C 5 C C Решая эту систему уравнений находим что C C и поэтому F 5 Таким образом это выражение при всех натуральных значениях принимает целые значения СЛУЧАЙ РАВНЫХ КОРНЕЙ ХАРАКТЕРИСТИЧЕСКОГО УРАВНЕНИЯ Рассмотрим случай когда корни характеристического уравнения совпадают: В этом случае выражение C C уже не будет являться общим решением Ведь из-за того что это решение можно записать в виде C C C В результате остается только одна константа C и выбрать ее так чтобы уравнение удовлетворяло двум начальным условиям и вообще говоря невозможно Следовательно необходимо найти какое-нибудь другое решение отличное от Таким решением является В самом деле если квадратное F уравнение имеет два совпадающих корня то по теореме Виета а Поэтому уравнение записывается следующим образом: А тогда рекуррентное уравнение имеет вид Проверим что F тождество F F действительно является его решением Подставляя значения F в уравнение получим очевидное Значит - это решение нашего рекуррентного уравнения Таким образом нам известно уже два решения данного рекуррентного уравнения: и Тогда общее решение можно записать следующим образом: F F C C C C Теперь коэффициенты Cи C можно подобрать так чтобы выполнялись любые два начальные условия для F

6 C C C C Линейные рекуррентные уравнения порядок которых больше двух решаются таким же способом Пусть уравнение имеет вид F Составим характеристическое уравнение Если все корни этого алгебраического уравнения -й степени различны то общее решение уравнения имеет вид F C C C Если же например то этому корню соответствуют решения F F F3 F рекуррентного уравнения В общем решении этому корню соответствует часть C C C Составляя такие выражения для всех корней и складывая их получаем общее решение уравнения s P где - кратность корня s - число различных корней P - полином степени относительно Пример Рассмотрим уравнение F 4 Составим характеристическое уравнение Общее решение рекуррентного уравнения имеет вид C C C C Составляем систему уравнений для нахождения и C: C C C C 4 Решая систему получаем что C и C Таким образом решение рекуррентного уравнения имеет вид

7 ПОИСК КОРНЕЙ МНОГОЧЛЕНА При отыскании корней характеристического уравнения довольно часто приходится решать уравнения степени больше Для решения этой задачи можно использовать метод подбора те брать наугад число и проверять является ли оно корнем данного многочлена При этом можно довольно быстро натолкнуться на корень а можно и никогда его не найти Ведь проверить все числа невозможно так как их бесконечно много Другое дело если бы нам удалось сузить область поиска например знать что искомые корни находятся например среди тридцати указанных чисел А для тридцати чисел можно сделать проверку А в связи с этим важным представляется утверждение Теорема Если несократимая дробь / целые числа является корнем многочлена F x с целыми коэффициентами то старший коэффициент этого многочлена делится на а свободный член на В самом деле если x x x x где - целые числа и / является его корнем то F / те / / / Умножим обе части равенства на получим Отсюда следует что Очевидно что целое число делится на Но / - несократимая дробь те числа и взаимно просты а тогда как известно из теории делимости целых чисел числа и тоже взаимно просты Итак делится на и взаимно просто с значит делится на Аналогично доказывается что делится на Доказанная теорема позволяет значительно сузить область поиска рациональных корней многочлена с целыми коэффициентами Продемонстрируем это на конкретном примере Найдем рациональные корни многочлена 4 3 F x 6x 3x 4x 8x 8 Согласно доказанной теореме рациональные корни этого многочлена находятся среди несократимых дробей вида / где - делитель свободного члена 8 а - делитель старшего коэффициента 6 4 При этом если дробь отрицательная то знак - будем относить к ее числителю Например Значит можно сказать что делитель числа 8 а - положительный делитель числа 6 Так как делители числа 8 это ± 48 а положительными делителями числа 6 будут 36 то рациональные корни рассматриваемого многочлена находятся среди чисел ± / / 3/ 6 / 344 / 388/ 3 Напомним что мы выписали только несократимые дроби Таким образом мы имеем двадцать чисел-«кандидатов» в корни Осталось только проверить каждое из них и отобрать те которые действительно являются корнями Но опять-таки придется сделать довольно много проверок Следующая теорема упрощает эту работу

8 Теорема Если несократимая дробь / является корнем многочлена F x с целыми коэффициентами то F делится на для любого целого числа при условии что Для доказательства этой теоремы разделим F x на x с остатком Получим F x x s x Так как x - многочлен с целыми коэффициентами то таким же является и s x а - целое число Пусть s x b x b x b x b Тогда x x b x b x b x b Положим в этом равенстве x / Учитывая что F / получаем / b b b b Умножим обе части последнего равенства на: b b b b Отсюда следует что целое число делится на Но так как и взаимно просты то и тоже взаимно просты а значит F делится на Теорема доказана Вернемся теперь к нашему примеру и воспользовавшись данной теоремой еще больше сузим круг поиска рациональных корней Применим теорему для значений и те если несократимая дробь является корнем многочлена x то делится на а F делится на Очевидно что в нашем случае F 5 а 5 Заметим что заодно мы исключили из рассмотрения единицу Итак рациональные корни нашего многочлена следует искать среди чисел / / 3 / 6 / / 3 8 8/3 Рассмотрим / / Тогда и F 5 делится на это число Далее 3 и 5 также делится на 3 Значит дробь / остается в числе кандидатов в корни Пусть теперь / / В этом случае 3 и F 5 не делится на -3 Значит дробь / не может быть корнем данного многочлена Выполнив проверку для каждой из выписанных выше дробей получим что искомые корни находятся среди чисел / / 3 4 Таким образом с помощью довольно простого приема удалось значительно сузить область поиска рациональных корней рассматриваемого многочлена Проверив 4 3 оставшиеся кандидаты убедимся что многочлен x 6x 3x 4x 8x 8 имеет два рациональных корня / и / 3 Описанный выше метод позволяет находить лишь рациональные корни многочлена с целыми коэффициентами Между тем многочлен может иметь и иррациональные корни Так например рассмотренный в примере многочлен имеет еще два корня: ± 5 это корни многочлена x x 4 Заметим что при испытании кандидатов в корни с помощью последней теоремы обычно рассматривают случай ± Другими словами если / - кандидат в корни то проверяют делятся ли и F на и соответственно Но может случиться так что например те единица - корень а тогда делится на любое число и наша проверка теряет смысл В этом случае следует разделить x на x те получить x x s x и производить испытания для многочлена sx При этом не следует забывать что один корень x корень x уже найден

9 В некоторых случаях когда характеристическое уравнение относится к уравнениям специального вида его корни могут быть найдены с помощью подстановки К таким уравнениям относятся например симметрические и возвратные уравнения Симметрическим называется уравнение степени - четное вида x bx cx cx bx 3 Симметрические уравнения являются частным случаем возвратных К возвратным относятся уравнения вида x bx cx / c x / / b x где - некоторый коэффициент Рассмотрим например решение симметрических и возвратных уравнений четвертой степени Пусть дано симметрическое уравнение 4 x 3 bx cx bx Сначала понизим его степень разделив обе части на x Получим уравнение x bx c b / x / x 4 Произведем следующую подстановку: t x / x 5 Тогда учитывая что t x / x выражение 4 можно записать как t bt c 6 Решив уравнение 6 как обычное квадратное уравнение получим два корня t и t Теперь подставляя поочередно корни t и t в уравнение 5 получим два квадратных уравнения x tx x t x 7 Решение уравнений 7 дает нам все четыре корня исходного уравнения 3 Таким образом решение симметрического уравнения четвертой степени сводится к решению трех квадратных уравнений Аналогично решаются и возвратные уравнения Если уравнение четвертой степени можно представить в виде 4 x 3 bx cx bx 8 то его решение может быть получено с помощью подстановки t x / x 9 Также как и в предыдущем случае понизим степень уравнения поделив обе части на x Для получившегося уравнения x bx c b / x / x воспользуемся подстановкой 9 Тогда уравнение можно переписать в виде t bt c Так же как и в предыдущем примере решим уравнение и получим два корня t и t Теперь подставляя поочередно корни t и t в уравнение 9 получим два квадратных уравнения x tx x t x Решив систему уравнений получим четыре корня исходного уравнения 8 Таким образом решение возвратного уравнения четвертой степени также сводится к решению трех квадратных уравнений

10 РЕШЕНИЕ НЕОДНОРОДНЫХ ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ УРАВНЕНИЙ Линейное рекуррентное уравнение называется неоднородным если его можно представить в следующем виде: f 3 где f - некоторая функция от Введем однородное линейное рекуррентное уравнение ОЛРУ соответствующее неоднородному линейному рекуррентному уравнению НЛРУ 3 F 4 а его общее решение обозначим через FO По аналогии с методами решения дифференциальных уравнений вначале пренебрежем начальными условиями и предположим что одно решение уравнения 3 уже найдено Назовем это решение частным и обозначим его через Будем искать общее решение НЛРУ в виде суммы F его частного решения и общего решения соответствующего ему ОЛРУ F 5 3 O Покажем что 5 действительно является решением НЛРУ 3 Подставим 5 в F F F F O O F F F F f O O но это уравнение является тождеством так как FO FO F O F F F F f где первое уравнение в системе есть общее решение ОЛРУ а второе частное решение НЛРУ Пусть НЛРУ имеет вид РЕШЕНИЕ НЛРУ ПРИ ФУНКЦИИ-КОНСТАНТЕ 6 b где b - целое число константа Будем искать частное решение уравнения 6 в виде константы F c 7 то есть c - также целое число Подставим 7 в 6 c c c c b b c 8 Константа будет частным решением уравнения 6 при условии неравенства нулю знаменателя формулы 8 Введем характеристический полином для НЛРУ 6 Если h h то очевидно что уравнение 6 имеет частное решение

11 b F h Обозначим формальную производную характеристического полинома Тогда h h через h 9 h 3 Пусть h но h Будем искать решение 6 в виде F c 3 Подставляя 3 в 6 имеем c c c c b c b c h h b но h а h и b c h Итак если h то уравнение 6 имеет частное решение b F h Обозначим -ю производную h через h По определению будем считать h h Из курса алгебры известно что если число α является -кратным корнем многочлена h то h α Теперь частное решение 6 можно записать в виде b F 3 h где - кратность корня характеристического многочлена h Пример Решить уравнение 5 при F 35 Составляем ОЛРУ F Составляем характеристическое уравнение h 3 Решаем характеристическое уравнение 4 Записываем общее решение ОЛРУ F C C C C 5 Находим частное решение НЛРУ 5 F 5 h так как h 6 Записываем общее решение НЛРУ F F C C 5 7 С учетом начальных условий находим коэффициенты в решении НЛРУ

12 C C 5 C C 5 35 получаем C C 8 Записываем решение НЛРУ F 5 Итак мы получили явную формулу для вычисления -го члена последовательности В заключение вычислим саму последовательность: Будем искать частное решение НЛРУ РЕШЕНИЕ НЛРУ ПРИ ФУНКЦИИ-МНОГОЧЛЕНЕ F b 33 в виде многочлена той же степени что и в правой части F c 34 Подставляя 34 в 33 получим правило вычисления коэффициентов многочлена j c j b 35 j Приравнивая коэффициенты в левой и правой части при членах содержащих получаем Остальные коэффициенты c c b b c при h h находятся аналогично путем приравнивания коэффициентов при в 35 Если является корнем характеристического уравнения h кратности то частное решение НЛРУ следует искать в виде F c РЕШЕНИЕ НЛРУ ПРИ ФУНКЦИИ-ЭКСПОНЕНТЕ Будем искать частное решение НЛРУ F bα 37 в виде 36 Подставляя 38 в 37 имеем То есть F cα cα bα 38

13 bα F h α если α не является корнем характеристического уравнения h Если же α является корнем характеристического уравнения кратности то частное решение 37 следует искать в виде F dα где d - некоторая константа Пример При решении одной задачи теории кодирования установлена рекуррентная зависимость числа умножений M от числа итераций при построении проверочной матрицы кода M M 4 3 при M 7 Запишем ОЛРУ M M Тогда имеем характеристическое уравнение h и общее решение ОЛРУ M C Будем искать частное решение в виде M d e Подставляя его в исходное уравнение имеем e 4 3 Левая часть уравнения не содержит d и следовательно предлагаемое частное решение определено неверно так как корень характеристического уравнения Теперь изменим вид частного решения на M d e Подставляя его в исходное уравнение имеем e 3 d Таким образом M C 3 и учитывая начальные условия C 3 Итак решение исходного уравнения M 3 3 РЕКУРРЕНТНЫЕ УРАВНЕНИЯ ОБЩЕГО ВИДА Рекуррентные уравнения отличные от линейных рекуррентных уравнений с постоянными коэффициентами не имеют общего метода решения Они могут решаться например методом проб и ошибок Рассмотрим нелинейное уравнение F F b при F b 39 Вычислим значение при подстановке в 39 некоторых констант F b b b при; F F b b b при;

14 b b b F F при 3 Теперь можно предположить что решением уравнения 39 является 4 og b F где Подставляя 4 в 39 имеем og og og b b b b b b F F og og j j b b Таким образом 4 действительно является решением уравнения 39

СИСТЕМЫ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ С ПОСТОЯННЫМИ КОЭФФИЦИЕНТАМИ Приведение к одному уравнению -го порядка С практической точки зрения очень важны линейные системы с постоянными коэффициентами

Тема 14 «Алгебраические уравнения и системы нелинейных уравнений» Многочленом степени n называется многочлен вида P n () a 0 n + a 1 n-1 + + a n-1 + a n, где a 0, a 1, a n-1, a n заданные числа, a 0,

Лекция Дифференциальные уравнения -го порядка (ДУ-) Общий вид дифференциального уравнения порядка n запишется: (n) F, = 0 () Уравнение -го порядка (n =) примет вид F(,) = 0 Подобные уравнения

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ Интегрирование рациональных дробей Рациональной дробью называется дробь вида P Q, где P и Q многочлены Рациональная дробь называется правильной, если степень многочлена P ниже степени

10 класс, базовый уровень Задание 1 Вариант 0 (демонстрационный, с решениями) Заочная математическая школа 009/010 учебный год 1 Представьте выражение в виде многочлена стандартного вида и найдите его

Занятие. Степень с произвольным действительным показателем, её свойства. Степенная функция, её свойства, графики.. Вспомнить свойства степени с рациональным показателем. a a a a a для натурального раз

Федеральное агентство по образованию Томский государственный университет систем управления и радиоэлектроники Кафедра высшей математики (ВМ) Приходовский М.А. ЛИНЕЙНЫЕ ОПЕРАТОРЫ И КВАДРАТИЧНЫЕ ФОРМЫ Практическое

ЛЕКЦИЯ N Дифференциальные уравнения высших порядков, методы решения Задача Коши Линейные дифференциальные уравнения высших порядков Однородные линейные уравнения Дифференциальные уравнения высших порядков,

ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ ПЕР- ВОГО ПОРЯДКА.. Основные понятия Дифференциальным уравнением называется уравнение, в которое неизвестная функция входит под знаком производной или дифференциала.

Тема 7 Ранг матрицы Базисный минор Теорема о ранге матрицы и ее следствия Системы m линейных уравнений с неизвестными Теорема Кронекера- Капелли Фундаментальная система решений однородной системы линейных

Министерство образования Российской Федерации Российский государственный университет нефти и газа имени ИМ Губкина ВИ Иванов Методические указания к изучению темы «ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ» (для студентов

СПРАВОЧНИК ПО МАТЕМАТИКЕ 5 9 классы МОСКВА «ВАКО» 201 УДК 32.851 ББК 4.262.22 С4 6+ Издание допущено к использованию в образовательном процессе на основании приказа Министерства образования и науки РФ

ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ Общие понятия Дифференциальные уравнения имеют многочисленные и самые разнообразные приложения в механике физике астрономии технике и в других разделах высшей математики (например

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 1 / 78 Часть I Конечные поля или поля Галуа. II ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 2 / 78 Поля вычетов по модулю

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа). II 1 / 78 Часть I Конечные поля (поля Галуа). II ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа). II 2 / 78 Поля вычетов по модулю простого

Лекция 7 2 Уравнения Фредгольма 2го рода с вырожденными ядрами Этот случай отличается тем, что решение интегрального уравнения сводится к решению линейной алгебраической системы и может быть легко получено

8 ЛИНЕЙНЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ ВТОРОГО ПОРЯДКА С ПЕРЕМЕННЫМИ КОЭФФИЦИЕНТАМИ 8 Основные понятия Линейным дифференциальным уравнением -го порядка с переменными коэффициентами называется уравнение

Лекция ИНТЕГРИРОВАНИЕ РАЦИОНАЛЬНЫХ ДРОБЕЙ Рациональные дроби Интегрирование простейших рациональных дробей Разложение рациональной дроби на простейшие дроби Интегрирование рациональных дробей Рациональные

Лекции -6 Глава Обыкновенные дифференциальные уравнения Основные понятия Различные задачи техники естествознания экономики приводят к решению уравнений в которых неизвестной является функция одной или

Лекция. Элементы теории многочленов. Многочлен (некоторые сведения справочного характера) Функция вида: 1 P (x) a0x a1x... a 1x a = + + + + (1) где натуральное число a i (i = 01...) постоянные коэффициенты

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего образования «ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНО- ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»

Занятие 4 Интегрирование рациональных функций (продолжение) Рациональной функцией (или, по-просту, дробью) называется отношение двух многочленов, то есть функция вида R() = f() g() = a 0 m + a m +...+

Тема 1-8: Комплексные числа А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для механиков (1 семестр)

Министерство образования и науки Российской Федерации Санкт-Петербургский государственный архитектурно-строительный университет В Б СМИРНОВА, Л Е МОРОЗОВА ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ Учебное

Федеральное агентство по образованию ГОУ ВПО «Уральский государственный технический университет УПИ» НМ Кравченко Дифференциальные уравнения и ряды Учебно-методическое пособие Научный редактор доц, канд

Иррациональные уравнения и неравенства Оглавление Иррациональные уравнения Метод возведения обеих частей уравнения в одну и ту же степень Задание Задание Задание Замена иррационального уравнения смешанной

Тема 2-19: Билинейные и квадратичные формы А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для механиков

I вариант 8В класс, 4 октября 007 1 Вставьте пропущенные слова: Определение 1 Арифметическим квадратным корнем из число, которого равен a из числа a (a 0) обозначается так: выражением Действие нахождения

Теоремы «пифагоровых троек» Мурсеев Михаил Петрович Существует различные методы определения вариантов «пифагоровых треугольников» Иногда их называют «пифагоровы тройки» или «египетские треугольники» К

Тема Неопределенный интеграл Основные методы интегрирования Интегрирование по частям Пусть u и v две дифференцируемые функции одного и того же аргумента Известно, что d(u v) udv vdu (77) Возьмем от обеих

Тема 4. ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ -1- Тема 4. ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ 4.0. Постановка задачи Задача нахождения корней нелинейного уравнения вида y=f() часто встречается в научных

Научно-исследовательская работа Тема работы «Разложение многочлена пятой степени на квадратичные множители с помощью интерполяционного многочлена Лагранжа» Выполнил: Шабуневич Эдуард Олегович учащийся

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

Глава Неопределенный интеграл Непосредственное интегрирование Функцию F() называют первообразной для функции f(), если выполняется равенство F"() f() Совокупность всех первообразных данной функции f()

МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ РЯЗАНСКАЯ ГОСУДАРСТВЕННАЯ РАДИОТЕХНИЧЕСКАЯ АКАДЕМИЯ ГС ЛУКЬЯНОВА АИНОВИКОВ РАЦИОНАЛЬНЫЕ И ИРРАЦИОНАЛЬНЫЕ УРАВНЕНИЯ И НЕРАВЕНСТВА Рязань Министерство

Лекция 9 Линеаризация диффе6ренциальных уравнений Линейные дифференциальные уравнения высших порядков Однородные уравнения свойства их решений Свойства решений неоднородных уравнений Определение 9 Линейным

Рассмотрим первый способ решения СЛУ по правилу Крамера для системы трех уравнений с тремя неизвестными: Ответ рассчитывается по формулам Крамера: D, D1, D2, D3 это определители Определителем третьего

Лекция 3 Экстремум функции нескольких переменных Пусть функция нескольких переменных u = f (x, x) определена в области D, и точка x (x, x) = принадлежит данной области Функция u = f (x, x) имеет

Алгебраические многочлены. 1 Алгебраические многочлены степени n над полем K Определение 1.1 Многочленом степени n, n N {0}, от переменной z над числовым полем K называется выражение вида: fz = a n z n

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

Тема 1 Действительные числа и действия над ними 4 часа 11 Развитие понятия о числе 1 Первоначально под числами понимали лишь натуральные числа, которых достаточно для счета отдельных предметов Множество

КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ ИМ. Н.И.ЛОБАЧЕВСКОГО Кафедра теории и технологий преподавания математики и информатики Фалилеева М.В. Первые шаги в решении уравнений и

95 Билинейные и квадратичные функции Билинейная функция Определение Билинейной функцией (билинейной формой) на линейном пространстве L называется функция от двух векторов из L линейная по каждому из своих

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Новосибирский национальный исследовательский государственный университет» СИСТЕМЫ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ

СПРАВОЧНИК Некоторые признаки делимости натуральных чисел Натуральные числа это числа, используемые для счёта:, Натуральные числа образуют множество, называемое множеством натуральных чисел Множество

57 Рассмотрим интегрирование простейшей рациональной дроби четвертого типа (M N) d () p q p Сделаем замену переменной, положив d. где a p q. Тогда Интеграл M N d p p p q q a, M p N Mp q d M (p q) p

1 УДК 517 96 1. Решение уравнения Риккати и его применение к линейным уравнениям второго порядка Чочиев Тимофей Захарович, кандидат физико-математических наук, старший научный сотрудник Южный Математический

Системы дифференциальных уравнений Введение Также как и обыкновенные дифференциальные уравнения системы дифференциальных уравнений применяются для описания многих процессов реальной действительности В

ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени Н.Э. Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» À.Í. Êàíàòíèêîâ,

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К РАСЧЕТНЫМ ЗАДАНИЯМ ПО КУРСУ ВЫСШЕЙ МАТЕМАТИКИ «ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ РЯДЫ КРАТНЫЕ ИНТЕГРАЛЫ» ЧАСТЬ III ТЕМА ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ ОГЛАВЛЕНИЕ

Министерство общего и профессионального образования Российской Федерации РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Е. Я. Файн МЕТОДИЧЕСКОЕ ПОСОБИЕ по курсу ЭЛЕМЕНТАРНАЯ МАТЕМАТИКА для студентов первого курса

ЛЕКЦИЯ 2 СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ ОПРЕДЕЛИТЕЛИ МАЛЫХ ПОРЯД- КОВ 1 ЭКВИВАЛЕНТНОСТЬ ЛИНЕЙНЫХ СИСТЕМ Пусть нам дана еще одна линейная система того же размера a 11x 1 + a 12x 2 + + a 1nx n = b 1, a 21x 1

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

Математический анализ Раздел: Неопределенный интеграл Тема: Интегрирование рациональных дробей Лектор Пахомова Е.Г. 0 г. 5. Интегрирование рациональных дробей ОПРЕДЕЛЕНИЕ. Рациональной дробью называется

Глава ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ Основные понятия и определения Дифференциальным уравнением называется уравнение связывающее независимую переменную х искомую функцию (у f (х и производные искомой функции

Метод разделения переменных (метод Фурье) Общие принципы метода разделения переменных Для простейшего уравнения с частными производными разделение переменных это поиски решений вида только от t. u (x,t

Тема: Общая теория систем линейных уравнений А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для

О РЕШЕНИИ В НАТУРАЛЬНЫХ ЧИСЛАХ УРАВНЕНИЙ ВИДА В диофантовом анализе уравнения вида относятся к трудно разрешимым. В настоящее время неизвестен общий метод полного решения даже простейших уравнений этого

Алгебра: 7 класс. Урок 2. Числовые выражения. Выражения с переменными Добрый день, ребята! На прошлом уроке мы повторили темы, изученные в 6 классе. Вспомнили, как выполнять действия с обыкновенными и

Г л а в а 2 ВЕКТОРНЫЕ ПРОСТРАНСТВА 9 Векторное пространство над полем 91 Аксиоматика Пусть задано поле P, элементы которого будем называть скалярами и некоторое множество V, элементы которого будем называть

Цепные дроби Конечные цепные дроби Определение Выражение вида a 0 + a + a + + a m где a 0 Z a a m N a m N/{} называется цепной дробью а m - длиной цепной дроби a 0 a a m будем называть коэффициентами цепной

Содержание Элеметарная теория погрешностей. Решение СЛАУ. 4. Нормы в конечномерных пространствах... 4. Обусловленность СЛАУ............ 5.3 Итерационные методы решения линейных систем......................

Министерство образования и науки РФ Уральский государственный экономический университет Ю. Б. Мельников Поле. Расширения полей Раздел электронного учебника для сопровождения лекции Изд. 4-е, испр. и доп.

Министерство образования и науки Российской Федерации НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ Кафедра прикладной механики и математики ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ

Глава 7 Понятие об асимптотических методах Лекция Регулярно и сингулярно возмущенные задачи При построении математических моделей физических объектов, характеризующихся различными масштабами по пространству,

Рекуррентное соотношение имеет порядок k , если оно позволяет выразить f(n+k) через f(n), f(n+1), …, f(n+k-1).

Пример.

f(n+2)=f(n)f(n+1)-3f 2 (n+1)+1 – рекуррентное соотношение второго порядка.

f(n+3)=6f(n)f(n+2)+f(n+1) – рекуррентное соотношение третьего порядка.

Если задано рекуррентное соотношение k-го порядка, то ему могут удовлетворять бесконечно много последовательностей, так как первые k элементов последовательности можно задать произвольно – между ними нет никаких соотношений. Но если первые k членов заданы, то все остальные элементы определяются однозначно.

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

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

Пример . Последовательность 2, 4, 8, …, 2 n является решением для соотношения f(n+2)=3∙f(n+1) – 2∙f(n).

Доказательство . Общий член последовательности имеет вид f(n)=2 n . Значит, f(n+2)= 2 n+2, f(n+1)= 2n+1 . При любом n имеет место тождество 2 n+2 =3∙2 n+1 – 2∙2 n . Следовательно, при подстановке последовательности 2 n в формулу f(n+2)=3f(n+1) – 2f(n) соотношение выполняется тождественно. Значит, 2 n является решением указанного соотношения.

Решение рекуррентного соотношения k-го порядка называется общим , если оно зависит от k произвольных постоянных α 1 , α 2 , … α k и путем подбора этих постоянных можно получить любое решение данного соотношения.

Пример . Дано рекуррентное соотношение: f(n+2)=5f(n+1)-6f(n). Докажем, что его общее решение имеет вид: f(n)= α 2 n + β3 n .

1. Сначала докажем, что последовательность f(n)=α 2 n + β3 n является решением рекуррентного соотношения. Подставим данную последовательность в рекуррентное соотношение.

f(n)= α 2 n + β 3 n , значит, f(n+1)= (α 2 n+1 + β 3 n +1), f(n+2)= α 2 n+2 + β 3 n +2 , тогда

5f(n+1)-6f(n)=5∙(α 2 n+1 + β 3 n +1)-6∙(α 2 n + β 3 n)= α (5 2 n+1 –6 2 n)+ β (5 3 n +1 –6 3 n)= =α2 n ∙(10–6)+ β 3 n ∙(15 – 6)= α 2 n+2 + β 3 n +2 = f(n+2).

Рекуррентное соотношение выполняется, следовательно, α 2 n + β 3 n является решением данного рекуррентного соотношения.

2. Докажем, что любое решение соотношения f(n+2)=5f(n+1)–6f(n) можно записать в виде f(n)= α 2 n + β 3 n . Но любое решение рекуррентного соотношения второго порядка однозначно определяется значениями первых двух членов последовательности. Поэтому достаточно показать, что для любых а=f(1) и b=f(2) найдутся α и β такие, что 2 α +3 β =а и 4 α +9 β =b. Легко видеть, что система уравнений имеет решение для любых значений а и b.

Таким образом, f(n)= α 2 n + β 3 n является общим решением рекуррентного соотношения f(n+2)=5f(n+1)–6f(n).

Линейные рекуррентные соотношения с постоянными коэффициентами

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

f(n+k)=c 1 f(n+k-1)+c 2 f(n+k-2)+…+c k f(n).

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

Линейное рекуррентное соотношение с постоянными коэффициентами первого порядка имеет вид: f(n+1)=c f(n).

Пусть f(1)=а, тогда f(2)=c∙f(1)=c∙a, f(3)=c∙f(2)=c 2 ∙a, аналогично f(4)=c 3 ∙a и так далее, заметим, что f(n)=c n -1 ∙f(1).

Докажем, что последовательность c n -1 ∙f(1) является решением рекуррентного соотношения первого порядка. f(n)=c n -1 ∙f(1), значит, f(n+1)=c n f(1). Подставляя это выражение в соотношение, получим тождество c n f(1)=с∙ c n -1 ∙f(1).

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

f(n+2)=C 1 ∙f(n+1)+C 2 ∙f(n). (*).

Заметим, что все рассуждения сохраняются и для соотношений более высокого порядка.

Свойства решений :

1) Если последовательность x n является решением (*), то и последовательность a∙x n тоже является решением.

Доказательство.

x n является решением (*), следовательно, выполняется тождество x n +2 =C 1 x n +1 +C 2 x n . Домножим обе части равенства на a. Получим a∙x n +2 =a∙(С 1 ∙x n +1 +С 2 ∙x n)= С 1 ∙a∙x n +1 +С 2 ∙a∙x n . Это означает, что ax n является решением (*).

2) Если последовательности x n и y n являются решениями (*), то и последовательность x n +y n тоже является решением.

Доказательство.

x n и y n являются решениями, следовательно, выполняются следующие тождества:

x n +2 =C 1 x n +1 +C 2 x n .

y n +2 =C 1 y n +1 +C 2 y n .

Выполним почленное сложение двух равенств:

x n +2 +y n +2 =С 1 ∙x n +1 +С 2 ∙x n + С 1 ∙y n +1 +С 2 ∙y n = С 1 ∙(x n +1 + y n +1)+С 2 ∙(x n +y n). Это означает, что x n +y n является решением (*).

3) Если r 1 является решением квадратного уравнения r 2 =С 1 r+С 2 , то последовательность (r 1) n является решением для соотношения (*).

r 1 является решением квадратного уравнения r 2 =С 1 r+С 2 , значит, (r 1) 2 =C 1 r 1 +C 2 . Помножим обе части равенства на (r 1) n . Получим

r 1 2 r 1 n =(С 1 r 1 +С 2) r n .

r 1 n +2 =С 1 r 1 n +1 +С 2 r 1 n .

Это означает, что последовательность (r 1) n является решением (*).

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

1. Составим характеристическое (квадратное) уравнение r 2 =С 1 r+С 2 . Найдём его корни r 1, r 2. Если корни различны, то общее решение имеет вид f(n)= ar 1 n +βr 2 n .

2. Найдём коэффициенты a и β. Пусть f(0)=a, f(1)=b. Система уравнений

имеет решение при любых а и b. Этими решениями являются

Задача. Найдем формулу для общего члена последовательности Фибоначчи.

Решение. Характеристическое уравнение имеет вид х 2 =х+1 или х 2 -х-1=0, его корнями являются числа , значит, общее решение имеет вид f(n)= . Как нетрудно видеть, из начальных условий f(0)=0, f(1)=1 вытекает, что a=-b=1/Ö5, и, следовательно, общее решение последовательности Фибоначчи имеет вид:

Что удивительно, это выражение при всех натуральных значениях n принимает целые значения.

Числа Фибоначчи.

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

Отсюда видно, что всегда может быть сведён к факториалу от меньшего числа.

Хорошей иллюстрацией к построению рекуррентных соотношений является задача Фибоначчи. В своей книге в 1202 ᴦ. итальянский математик Фибоначчи привел следующую задачу. Пара кроликов приносит приплод раз в месяц двух крольчат (самку и самца), причём новорождённые крольчата через два месяца после рождения сами приносят приплод. Сколько кроликов появится через год, если в начале была одна пара кроликов.

Из условия задачи следует, что через месяц будет две пары кроликов, через два месяца приплод даст только первая пара кроликов, появившихся два месяца назад, в связи с этим всего будет 3 пары кроликов. Ещё через месяц будет уже 5 пар. И так далее.

Эта зависимость принято называть рекуррентным соотношением . Слово «рекурсия» означает возврат назад (в нашем случае – возврат к предыдущим результатам).

По условию, и , тогда по соотношению имеем: , , и т.д., .

1, 1, 2, 3, 5, 8, 13, 21, ...

Возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар «предков» данной пары (включая и исходную), а нулями – все остальные месяцы. К примеру, последовательность устанавливает такую «генеалогию» – сама пара появилась в конце 11-го месяца, ее родители в конце 7-го месяца, «дед» – в конце 5-го месяца, и «прадед» в конце 2-го месяца. Первоначальная пара шифруется последовательностью . Ни в одной последовательности две единицы не могут стоять подряд – только что появившаяся пара не может принести приплод через месяц. Очевидно, различным последовательностям отвечают различные пары и обратно.

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, число последовательностей с указанными свойствами, равно .

Теорема 1: Число находится как сумма биномиальных коэффициентов:. В случае если – нечетно, то . В случае если – четно, то . Иначе: – целая часть числа .

Это равенство можно доказать иначе. Обозначим:

К примеру, – рекуррентное соотношение второго порядка, а рекуррентное соотношение 3-го порядка. Соотношение Фибоначчи является соотношением второго порядка.

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

К примеру, соотношению Фибоначчи кроме рассмотренной выше последовательности 1, 1, 2, 3, 5, 8, 13, 21, ..., могут удовлетворять также и другие последовательности. К примеру, последовательность 2, 2, 4, 8, 12,... строится по тому же принципу. Но если задать начальные члены (их в последовательности Фибоначчи - 2), то решение определяется однозначно. Начальных членов берут столько, каков порядок соотношения.

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

Определение 4: Решение рекуррентного соотношения ‑ го порядка принято называть общим , если оно зависит от произвольных постоянных , меняя которые, можно получить любое решение данного соотношения.

К примеру, для соотношения общим решение будет .

Тогда найдутся такие и , что

Очевидно, для любых , система уравнений имеет единственное решение.

Определение 5: Рекуррентное соотношение принято называть линейным , если оно записывается в виде:

где - числовые коэффициенты.

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

Рассмотрим сначала соотношение 2-го порядка .

Решение этого соотношения основано на следующих утверждениях.

Теорема 2: В случае если и - являются решением данного рекуррентного соотношения 2-го порядка, то для любых чисел и последовательность также является решением этого соотношения.

Теорема 3: В случае если число является корнем квадратного уравнения , то последовательность является решением рекуррентного соотношения .

Из теорем 2, 3 вытекает следующее правило решения линейных рекуррентных соотношений 2-го порядка.

Пусть дано рекуррентное соотношение .

1) Составим квадратное уравнение , ĸᴏᴛᴏᴩᴏᴇ принято называть характеристическим для данного соотношения. Найдём все корни этого уравнения (даже кратные и комплексные).

а) В случае если это соотношение имеет два различных корня и , то общее решение соотношения имеет вид .

Действительно, из теорем 2, 3 следует, что - решение и система уравнений

Имеет единое решение, т.к. при условии .

К примеру, для чисел Фибоначчи, имеем . Характеристическое уравнение имеет вид: . Решая последнее уравнение, получим корни.