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

Транскрипт

1 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Костромской государственный университет имени Н. А. Некрасова Т. Н. Матыцина ДИСКРЕТНАЯ МАТЕМАТИКА РЕШЕНИЕ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ Практикум Кострома 2010

2 ББК я73-5 М348 Печатается по решению редакционно-издательского совета КГУ им. Н. А. Некрасова Рецензент А. В. Чередникова, кандидат физико-математических наук, доцент М348 Матыцина Т. Н. Дискретная математика. Решение рекуррентных соотношений: практикум [Текст] / Т. Н. Матыцина. Кострома: КГУ им. Н. А. Некрасова, с. Практикум содержит индивидуальные задания для студентов и предназначен для обеспечения самостоятельной работы по освоению первой части курса «Дискретная математика». Для студентов 2 3 курсов физико-математического факультета, обучающихся по специальностям «Математика» с дополнительной специальностью «Информатика», «Информатика» с дополнительной специальностью «Математика». ББК я73-5 Т. Н. Матыцина, 2010 КГУ им. Н. А. Некрасова,

3 ОГЛАВЛЕНИЕ Введение Методические рекомендации по решению линейных рекуррентных соотношений Основные понятия и определения рекуррентных (возвратных) последовательностей Алгоритмы решения ЛОРС и ЛРС Примеры решения ЛОРС и ЛРС Задачи для самостоятельного решения Задачи для решения ЛОРС и ЛРС Ответы Заключение Библиографический список

4 ВВЕДЕНИЕ Первая часть курса «Дискретная математика», изучаемая студентами 2 3 курсов физико-математического факультета, обучающихся по специальностям «Информатика» с дополнительной специальностью «Математика» (IV семестр) и «Математика» с дополнительной специальностью «Информатика» (V семестр), предполагает решение рекуррентных соотношений. В настоящее издание включены задачи на вычисление однородных и неоднородных линейных рекуррентных соотношений. Поводом для написания практикума послужило то обстоятельство, что у студентов практически нет навыков решения задач по данному курсу. Одной из причин является отсутствие доступного учебника или сборника задач. Задачи из предлагаемого практикума помогут каждому из студентов (индивидуально) разобраться с основными методами и приемами решения задач. С целью более легкого освоения материала в начале пособия рассмотрены все типы задач, предлагаемых для самостоятельного решения. В конце помещен список рекомендуемой литературы, которая поможет глубже изучить данный предмет. Тема «Рекуррентные соотношения» близка к школьному курсу (арифметические и геометрические прогрессии, последовательность квадратов и кубов натуральных чисел, и т. п.), поэтому не требует от студентов предварительного изучения каких-либо других дисциплин. Основы теории рекуррентных соотношений (возвратных последовательностей) были разработаны и опубликованы в 20-х гг. XVIII в. французским математиком А. Муавром и одним из первых по времени членов Петербургской Академии наук швейцарским математиком Д. Бернулли. Развёрнутую теорию дал крупнейший математик XVIII в. 4

5 петербургский академик Л. Эйлер. Из более поздних работ следует выделить изложение теории возвратных последовательностей в курсах исчисления конечных разностей, читанных знаменитыми русскими математиками академиками П. Л. Чебышевым и А. А. Марковым. Рекуррентные соотношения (от латинского слова recurrere возвращаться) играют большую роль в дискретной математике, являясь по существу в некотором смысле дискретным аналогом дифференциальных уравнений. Кроме того, они позволяют сводить данную задачу от параметров к задаче от 1 параметров, потом к задаче от 2 параметров и т. д. Последовательно уменьшая число параметров, можно дойти до задачи, которую уже легко решить. Понятие рекуррентного соотношения (возвратной последовательности) является широким обобщением понятия арифметической или геометрической прогрессии. Как частные случаи оно охватывает также последовательности квадратов или кубов натуральных чисел, последовательности цифр десятичного разложения рационального числа (и вообще любые периодические последовательности), последовательности коэффициентов частного от деления двух многочленов, расположенных по возрастающим степеням х, и т. д. 5

6 1. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ 1.1. Основные понятия и определения рекуррентных (возвратных) последовательностей Будем записывать последовательности в виде a 1, a 2, a 3, a, (1) или, коротко, {a }. Если существует натуральное число k и числа α 1, α 2, α k (действительные или мнимые), такие, что, начиная с некоторого номера и для всех следующих номеров, a +k = α 1 a +k 1 + α 2 a +k α k a, (k 1), (2) то последовательность (1) называется рекуррентной (возвратной) последовательностью порядка k, а соотношение (2) рекуррентным (возвратным) уравнением порядка k. Таким образом, рекуррентная последовательность характеризуется тем, что каждый её член (начиная с некоторого из них) выражается через одно и то же количество k непосредственно предшествующих ему членов по формуле (2). Само название «рекуррентная» (а также возвратная) употребляется именно потому, что здесь для вычисления последующего члена возвращаются к предшествующим членам. Приведём несколько примеров рекуррентных последовательностей. Пример 1. Геометрическая прогрессия. Пусть имеем геометрическую прогрессию: a 1 = α, a 2 = α q, a 3 = α q 2, a = α q 1, ; (3) для неё уравнение (2) принимает вид: a +1 = q a. (4) 6

7 Здесь k = 1 и α 1 = q. Таким образом, геометрическая прогрессия является рекуррентной последовательностью первого порядка. Пример 2. Арифметическая прогрессия. В случае арифметической прогрессии a 1 = α, a 2 = α + d, a 3 = α + 2d, a = α + (1)d, имеем a +1 = a + d соотношение, не имеющее вида уравнения (2). Однако если мы рассмотрим два соотношения, написанные для двух соседних значений: a +2 = a +1 + d и a +1 = a + d, то получим из них путём почленного вычитания a +2 a +1 = a +1 a, или a +2 = 2a +1 a уравнение вида (2). Здесь k = 2, α 1 = 2, α 2 = 1. Следовательно, арифметическая прогрессия является рекуррентной последовательностью второго порядка. Пример 3. Рассмотрим старинную задачу Фибоначчи 1 о числе кроликов. В ней требуется определить число пар зрелых кроликов, образовавшихся от одной пары в течение года, если известно, что каждая зрелая пара кроликов ежемесячно рождает новую пару, причём новорождённые достигают полной зрелости в течение месяца. В этой задаче интересен отнюдь не результат, получить который совсем нетрудно, но последовательность, члены которой выражают общее число зрелых пар кроликов в начальный момент (a 1) через месяц (a 2), через два месяца (a 3) и, вообще, через месяцев (a +1). Очевидно, что a 1 = 1. Через месяц прибавится пара новорождённых, но число зрелых пар будет прежнее: a 2 = 1. Через два месяца крольчата достигнут зрелости и общее число зрелых пар будет равно двум: a 3 = 2. Пусть мы вычислили уже количество 1 Фибоначчи, или Леонардо Пизанский, итальянский средневековый математик (около 1200 г.) оставил после себя книгу «Об абаке», содержащую обширные арифметические и алгебраические сведения, заимствованные у народов Средней Азии и византийцев и творчески им переработанные и развитые. 7

8 зрелых пар через 1 месяцев a и через месяцев a +1. Так как к этому времени a ранее имевшихся зрелых пар дадут ещё a пар приплода, то через + 1 месяцев общее число зрелых пар будет: a +2 = a +1 + a. (6) Отсюда a 4 = a 3 + a 2 = 3, a 5 = a 4 + a 3 = 5, a 6 = a 5 + a 4 = 8, a 7 = a 6 + a 5 = 13,. Мы получили, таким образом, последовательность a 1 = 1, a 2 = 1, a 3 = 2, a 4 = 3, a 5 = 5, a 6 = 8, a 7 = 13, a 13 = 233, (7) в которой каждый последующий член равен сумме двух предыдущих. Последовательность эта называется последовательностью Фибоначчи, а члены её числами Фибоначчи. Уравнение (6) показывает, что последовательность Фибоначчи есть рекуррентная последовательность второго порядка. Пример 4. В качестве следующего примера рассмотрим последовательность квадратов натуральных чисел: a 1 = 1 2, a 2 = 2 2, a 3 = 3 2, a = 2,. (8) Здесь a +1 = (+ 1) 2 = и, следовательно, a +1 = a (9) Увеличивая на единицу, получим: a +2 = a (10) И, следовательно (вычитая почленно (9) из (10)), a +2 a +1 = a +1 a + 2, или a +2 = 2a +1 a + 2. (11) Увеличивая в равенстве (11) на единицу, будем иметь: a +3 = 2a +2 a ; (12) откуда (вычитая почленно (11) из (12)) a +3 a +2 = 2a +2 3a +1 + a, 8

9 или a +3 = 3a +2 3a +1 + a. (13) Мы получили рекуррентное уравнение третьего порядка. Следовательно, последовательность (8) есть рекуррентная последовательность третьего порядка. Пример 5. Рассмотрим последовательность кубов натуральных чисел: a 1 = 1 3, a 2 = 2 3, a 3 = 3 3, a = 3,. (14) Подобным же образом, как в примере 4, можно убедиться в том, что последовательность кубов натуральных чисел есть рекуррентная последовательность четвёртого порядка. Члены её удовлетворяют уравнению a +4 = 4a +3 6a a +1 a. (15) В случае простейших рекуррентных последовательностей, например арифметической и геометрической прогрессий, последовательности квадратов или кубов натуральных чисел, мы можем находить любой член последовательности, не прибегая к вычислению предшествующих членов. В случае же последовательности чисел Фибоначчи мы, на первый взгляд, не имеем возможности для этого и, чтобы вычислить тринадцатое число Фибоначчи a 13, находим предварительно, один за другим, все предшествующие члены (пользуясь уравнением a +2 = a +1 + a (6)): a 1 = 1, a 2 = 1, a 3 = 2, a 4 = 3, a 5 = 5, a 6 = 8, a 7 = 13, a 8 = 21, a 9 = 34, a 10 = 55, a 11 = 89, a 12 = 144, a 13 = 233. В ходе детального исследования структуры членов рекуррентной последовательности можно получить формулы, позволяющие вычислить в самом общем случае любой член рекуррентной последовательности, не прибегая к вычислению предшествующих членов. Другими словами, следующая задача состоит в том, чтобы отыскать формулу -го члена последовательности, зависящую только от номера. 9

10 Рекуррентное соотношение в общем случае может быть записано в виде a +k = F(, a +k 1, a +k 2, a), где F функция от k + 1 переменной, а число k называют порядком соотношения. Решением рекуррентного соотношения называется числовая последовательность b 1, b 2, b 3, b, для которой выполняется равенство: b +k = F(, b +k 1, b +k 2, b) при любом = 0, 1, 2,. Вообще говоря, произвольное рекуррентное соотношение имеет бесконечно много решений. Например, если рассмотреть рекуррентное соотношение второго порядка a +2 = a +1 + a, то ему, кроме последовательности Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34,..., характеризующейся тем, что здесь a 1 = a 2 = 1, удовлетворяет ещё бесконечное множество других последовательностей, получающихся при различном выборе значений a 1 и a 2. Так, например, при a 1 = 3 и a 2 = 1 получаем последовательность: 3, 1, 2, 1, 3, 4, 7, 11, 18, 29,. Чтобы однозначно определить решение рекуррентного соотношения, необходимо задать начальные условия (начальных условий должно быть ровно столько, каков порядок рекуррентного соотношения). Решить рекуррентное соотношение значит найти формулу -го члена последовательности. К сожалению, не существует общего метода решения произвольных рекуррентных соотношений. Исключением является класс так называемых линейных рекуррентных соотношений с постоянными коэффициентами. Рекуррентное соотношение вида a +k = α 1 a +k 1 + α 2 a +k α k a, где a i некоторые числа, i = 1, 2, k, называется линейным однородным рекуррентным соотношением (ЛОРС) с постоянными коэффициентами порядка k. 10

11 Рекуррентное соотношение вида a +k = α 1 a +k 1 + α 2 a +k α k a + f(), где a i некоторые числа, i = 1, 2, k, f() 0 функция от, называется линейным рекуррентным соотношением (ЛРС) с постоянными коэффициентами порядка k Алгоритмы решения ЛОРС и ЛРС Алгоритм решения ЛОРС. Имеем ЛОРС: a +k = α 1 a +k 1 + α 2 a +k α k a. 1 шаг. Каждому ЛОРС порядка k соответствует алгебраическое уравнение степени k с теми же коэффициентами, и оно называется характеристическим уравнением ЛОРС. Составляем характеристическое уравнение x k = α 1 x k 1 + α 2 x k α k x 0 и находим его корни x i, где i = 1, k. 2 шаг. Если x i корни кратности 1 (т. е. все различны между собой), то общее решение ЛОРС имеет вид: a = c 1 (x 1) + c 2 (x 2) + c 3 (x 3) + + c k (x k) = c i x i Если x i корни кратности r i, то общее решение ЛОРС имеет вид k a = i= 1 (c 1 2 ri 1 i1 + ci2 + ci cir) (например, если корень x кратности 2, то a = (c 1 + c 2) x). i x i k i= 1 3 шаг. Коэффициенты c i находятся с помощью начальных условий. 11

12 Алгоритм решения ЛРС. Имеем ЛРС: a +k = α 1 a +k 1 + α 2 a +k α k a + f(). Функцию f() можно представить в виде R m () λ, где R m () многочлен степени m от переменной. В самом деле, например: f() = 10 3= (10 3)1 = R 1 () 1, или f() = = (2 + 3) 3 = R 2 () 3. Перепишем ЛРС в виде a +k α 1 a +k 1 α 2 a +k 2 α k a = R m () λ. 1 шаг. Выписываем соответствующий ЛОРС: a +k α 1 a +k 1 α 2 a +k 2 α k a = 0 и находим его общее решение. Для этого составляем характеристическое уравнение x k α 1 x k 1 α 2 x k 2 α k x 0 = 0 и находим его корни x i, где i = 1, k. Пусть, например, x i различные корни, тогда общее решение соответствующего ЛОРС имеет вид: a = c 1 (x 1) + c 2 (x 2) + c 3 (x 3) + + c k (x k). 2 шаг. Находим a частное решение ЛРС: а) если λ не корень характеристического уравнения x k α 1 x k 1 α 2 x k 2 α k = 0, то a = Q m () λ, где Q m () многочлен степени m от переменной; б) если λ корень характеристического уравнения x k α 1 x k 1 α 2 x k 2 α k = 0 кратности r, то a = r Q m () λ, где Q m () многочлен степени m от переменной. Далее, подставляем a в исходное ЛРС и находим коэффициенты в многочлене Q m (). 12

13 3 шаг. Находим общее решение ЛРС, оно представляет собой сумму общего решения соответствующего ЛОРС a и частного решения ЛРС a, то есть a = a + a. Коэффициенты c i находятся с помощью начальных условий Примеры решения ЛОРС и ЛРС Пользуясь приведенным алгоритмом нахождения решения ЛОРС и ЛРС, разберём несколько задач. Задача 1. Найти решение линейного однородного рекуррентного соотношения второго порядка: a +2 = 6 a +1 8 a, a 0 = 3, a 1 = Составляем характеристическое уравнение x 2 = 6 x 8 x 0 и находим его корни. x 2 6x + 8 = 0; x 1 = 2, x 2 = 4 корни различные, следовательно, их кратность равна Находим общее решение ЛОРС: a = c 1 (x 1) + c 2 (x 2) = c c Так как заданы начальные условия, то коэффициенты c 1 и c 2 определяются однозначно. a 0 = c c = c 1 + c 2 = 3; a 1 = c c = 2c 1 + 4c 2 = 4. Получили систему: c1 + c2 = 3, 2c1 + 4c2 = 4. Решая её, найдём коэффициенты: c 1 = 8, c 2 = 5. Таким образом, решение ЛОРС имеет вид a = Задача 2. Найти решение линейного однородного рекуррентного соотношения: 13

14 a +2 = 6 a +1 9 a, a 0 = 5, a 1 = Составляем характеристическое уравнение x 2 = 6x 9 и находим его корни. x 2 6x + 9 = 0; (x 3) 2 = 0; x 1 = x 2 = 3 два корня, при этом x 1 и x 2 совпали, следовательно, кратность корня равна Находим общее решение ЛОРС: a = (c 1 + c 2) (x 1) = (c 1 + c 2) С помощью начальных условий определяем коэффициенты c 1 и c 2: a 0 = (c 1 + c 2 0) 3 0 = c 1 = 5; a 1 = (c 1 + c 2 1) 3 1 = (c 1 + c 2) 3 = 6. Получили систему c1 = 5, c1 + c2 = 2. Решая её, найдём коэффициенты c 1 = 5, c 2 = 3. Таким образом, решение ЛОРС имеет вид: a = (5 3) 3. Замечание. Как известно, корнями квадратного уравнения могут служить рациональные, иррациональные, комплексные числа и т. п. Метод решения линейных рекуррентных соотношений с такими корнями решается аналогично. Задача 3. Найти решение линейного однородного рекуррентного соотношения третьего порядка: a +3 = 3 a a +1 8 a, a 0 = 9, a 1 = 9, a 2 = Составляем характеристическое уравнение x 3 = 3 x x 8 и находим его корни. x 3 3x 2 6x + 8 = 0; (x 1)(x + 2)(x 4) = 0; x 1 = 1, x 2 = 2, x 3 = 4 корни различные, следовательно, их кратность равна Находим общее решение ЛОРС: a = c 1 (x 1) + c 2 (x 2) + c 3 (x 3) = c c 2 (2) + c

15 3. С помощью начальных условий, находим коэффициенты c 1, c 2 и c 3. a 0 = c c 2 (2) 0 + c = c 1 + c 2 + c 3 = 9; a 1 = c c 2 (2) 1 + c = c 1 2c 2 + 4c 3 = 9; a 2 = c c 2 (2) 2 + c = c 1 + 4c c 3 = 9. c1 + c2 + ñ3 = 9, Решая систему c1 2c2 + 4c3 = 9, получим c 1 = 7, c 2 = 4, c 3 = 2. Таким c1 + 4c2 + 16c3 = 9, образом, решение ЛОРС имеет вид: a = (2) 2 4. Задача 4. Найти решение линейного однородного рекуррентного соотношения третьего порядка: a +3 = a a +1 3 a, a 0 = 6, a 1 = 15, a 2 = Составляем характеристическое уравнение x 3 = x 2 + 5x 3 и находим его корни. x 3 + x 2 5x + 3 = 0; (x 1) 2 (x + 3) = 0; x 1 = x 2 = 1 корень кратности 2; x 3 = 3 корень кратности Находим общее решение ЛОРС: a = (c 1 + c 2) (x 1) + c 3 (x 3) = (c 1 + c 2) 1 + c 3 (3). 3. С помощью начальных условий находим коэффициенты c 1, c 2 и c 3. a 0 = (c 1 + c 2 0) c 3 (3) 0 = c 1 + c 3 = 6; a 1 = (c 1 + c 2 1) c 3 (3) 1 = c 1 + c 2 3c 3 = 15; a 2 = (c 1 + c 2 2) c 3 (3) 2 = c 1 + 2c 2 + 9c 3 = 8. c1 + ñ3 = 6, Решая систему c1 + c2 3c3 = 15, получим c 1 = 8, c 2 = 1 и c 3 = 2. Таким c1 + 2c2 + 9c3 = 8, образом, решение ЛОРС имеет вид: a = (8 +) 1 2 (3). 15

16 Задача 5. Найти решение линейного рекуррентного соотношения второго порядка: Перепишем ЛРС в виде a +2 = 18 a a + 128, a 0 = 5, a 1 = 2. a a a = () 1. Выписываем соответствующий ЛОРС: a a a = 0. Составляем характеристическое уравнение и находим его корни. x 2 18x + 81 = 0; (x 9) 2 = 0; x 1 = x 2 = 9 корни характеристического уравнения совпали, следовательно, их кратность равна 2. Тогда общее решение a = (c 1 + c 2) (x 1) = (c 1 + c 2) Находим a частное решение ЛРС. По условию f() = R m () λ = = = R 0 () λ, где R 0 () = 128 многочлен нулевой степени от переменной, а λ = 1 не корень характеристического уравнения соответствующего ЛОРС. Следовательно, a = Q m () λ = Q 0 () 1, где Q 0 () многочлен нулевой степени от переменной, в общем виде Q 0 () = с. Таким образом, a = с 1. Далее, подставляем a в исходное ЛРС () и находим коэффициент с в многочлене Q 0 (): с с с 1 = ; с 18с + 81с = 128; 64с = 128; с = 2. Следовательно, получили a = с 1 = 2 1 = 2. 16

17 3. Находим общее решение ЛРС, оно представляет собой сумму общего решения соответствующего ЛОРС a и частного решения ЛРС a, то есть a = a + a = (c 1 + c 2) Осталось с помощью начальных условий найти коэффициенты c 1, и c 2. a 0 = (c 1 + c 2 0) = c = 5; a 1 = (c 1 + c 2 1) = 9c 1 + 9c = 2; Решая систему c1 + 2 = 5, 9c1 + 9c2 + 2 = 2, получим c 1 = 3, c 2 = 3. Таким образом, решение ЛРС имеет вид: a = (3 3) Задача 6. Найти решение линейного рекуррентного соотношения: a +2 = 10 a a , a 0 = 7, a 1 = 50. Перепишем ЛРС в виде a a a = Выписываем соответствующий ЛОРС: a a a = 0; составляем характеристическое уравнение и находим его корни. x 2 10 x + 25 = 0; (x 5) 2 = 0; x 1 = x 2 = 5 корень кратности 2. Тогда общее решение ЛОРС имеет вид: a = (c 1 + c 2) (x 1) = (c 1 + c 2) Находим a частное решение ЛРС. По условию f() = R m () λ = 50 5 = R 0 () λ, где R 0 () = 50 многочлен нулевой степени от переменной, а λ = 5 совпадает с корнем x 1 кратности 2 характеристического уравнения соответствующего ЛОРС. Следовательно, a = r Q m () λ = = 2 Q 0 () 5, где Q 0 () = с многочлен нулевой степени от переменной. Таким образом, a = 2 с 5. Далее, подставляем a в исходное ЛРС и находим коэффициент с: 17

18 с (+ 2) с (+ 1) с 2 5 = 50 5 (разделим на 5 0); 25с (+ 2) 2 50с (+ 1) с 2 = 50; с () 2с () + с 2 = 2; с = 1. Следовательно, a = 2 с 5 = Выписываем общее решение ЛРС: a = a + a = (c 1 + c 2) С помощью начальных условий находим коэффициенты c 1, и c 2: a 0 = (c 1 + c 2 0) = c 1 = 7; a 1 = (c 1 + c 2 1) = 5c 1 + 5c = 50; Решая систему c1 = 7, c1 + c2 + 1 = 10, получим c 1 = 7, c 2 = 2. Таким образом, решение ЛРС имеет вид: a = (7 + 2) = () 5. Задача 7. Найти решение линейного рекуррентного соотношения: a +2 = 6 a +1 8 a , a 0 = 0, a 1 = 11. Перепишем ЛРС в виде a +2 6 a a = Выписываем соответствующий ЛОРС: a +2 6 a a = 0; составляем характеристическое уравнение и находим его корни. x 2 6x + 8 = 0; x 1 = 2, x 2 = 4 корни кратности равной 1. Тогда общее решение ЛОРС имеет вид a = c 1 (x 1) + c 2 (x 2) = c c Находим a частное решение ЛРС. По условию f() = R m () λ = = (3 + 2) 1 = R 1 () λ, где R 1 () = многочлен первой степени от переменной, а λ = 1 не корень характеристического уравнения соответствующего ЛОРС. Следовательно, a = Q m () λ = Q 1 () 1, где Q 1 () многочлен первой степени от переменной, в общем виде Q 1 () = = a + b. Таким образом, a = (a + b) 1. 18

19 a и b: Далее, подставляем a в исходное ЛРС и находим коэффициенты (a (+ 2) + b) (a (+ 1) + b) (a + b) 1 = 3 + 2; 25с (+ 2) 2 50с (+ 1) с 2 = 3 + 2; 3a + (3b 4a) = Таким образом, получили, что два многочлена равны, а тогда равны соответствующие коэффициенты: 3a = 3, a = 1, 3b 4a = 2 b = 2. Следовательно, a = (a + b) 1 = Выписываем общее решение ЛРС: a = a + a = c c (+ 2). С помощью начальных условий находим коэффициенты c 1, и c 2: a 0 = c c (0 + 2) = 0; a 1 = c c (1 + 2) = 11; Решая систему c1 + c2 = 2, 2c1 + 4c2 = 14, получим c 1 = 3, c 2 = 5. Таким образом, решение ЛРС имеет вид: a = Задача 8. Найти решение линейного рекуррентного соотношения: a +2 = 5 a +1 6 a + (10 4) 2, a 0 = 5, a 1 = 12. Перепишем ЛРС в виде a +2 5 a a = (10 4) Выписываем соответствующий ЛОРС: a +2 5 a a = 0; составляем характеристическое уравнение и находим его корни. x 2 5x + 6 = 0; x 1 = 3, x 2 = 2 корни различные кратности 1. Тогда общее решение ЛОРС имеет вид: a = c 1 (x 1) + c 2 (x 2) = c c

20 2. Находим a частное решение ЛРС. По условию имеем, что f() = = R m () λ = (10 4) 2 = R 1 () λ, где R 1 () = (10 4) многочлен первой степени от переменной, а λ = 2, то есть совпадает с корнем характеристического уравнения соответствующего ЛОРС. Следовательно, a = r Q m () λ = 1 Q 1 () 2, где Q 1 () многочлен первой степени от переменной, в общем виде Q 1 () = a + b. Таким образом, получаем a = = (a + b) 2. Далее, подставляем a в исходное соотношение и находим коэффициенты a и b. (+ 2)(a (+ 2) + b) (+ 1) (a (+ 1) + b) (a + b) 2 = = (10 4) 2. Разделим это уравнение на 2 0: 4(+ 2)(a (+ 2) + b) 10(+ 1) (a (+ 1) + b) + 6(a + b) = 10 4; 4a + (6a 2b) = Таким образом, получили, что два многочлена равны, а тогда равны соответствующие коэффициенты: 4a = 4, a = 1, 6a 2b = 10 b = 2. Следовательно, a = (a + b) 2 = (2) Выписываем общее решение ЛРС, то есть a = a + a = c c (2) 2. С помощью начальных условий находим коэффициенты c 1, и c 2. a 0 = c c (0 2) 2 0 = 5; a 1 = c c (1 2) 2 1 = 12. Решая систему c1 + c2 = 5, 3c1 + 2c2 = 14, получим c 1 = 4, c 2 = 1. Таким образом, решение ЛРС имеет вид: a = (2) 2 = () 2. 20

21 Задача 9. Найти решение линейного рекуррентного соотношения: a +2 = 8 a a , a 0 = 1, a 1 = 7. Перепишем ЛРС в виде a +2 8 a a = () Выписываем соответствующий ЛОРС: a +2 8 a a = 0; составляем характеристическое уравнение и находим его корни. x 2 8 x + 16 = 0; x 1 = x 2 = 4 корни совпали, следовательно, кратность корня равна 2. Тогда общее решение ЛОРС имеет вид: a = (c 1 + c 2) (x 1) = (c 1 + c 2) Находим a частное решение ЛРС. По условию f() = R m () λ = = () 1 = R 2 () λ, где R 2 () = многочлен второй степени от переменной, а λ = 1 не совпадает с корнем характеристического уравнения соответствующего ЛОРС. Следовательно, a = Q m () λ = Q 2 () 1, где Q 2 () многочлен второй степени от переменной, в общем виде Q 2 () = a 2 + b + c. Таким образом, a = = (a 2 + b + c) 1. Далее, подставляем a в исходное соотношение и находим коэффициенты a, b и c. (a (+ 2) 2 + b (+ 2)+ c) (a (+ 1) 2 + b (+ 1) + c) (a b + c) 1 = () 1 ; a(+ 2) 2 + b(+ 2)+ c 8a(+ 1) 2 8b(+ 1) 8c + 16a b + 16c = = ; 9a 2 12a + 9b 4a 6b + 9c = Таким образом, получили, что два многочлена равны, а тогда равны соответствующие коэффициенты: 9a = 9, 12a + 9b = 6, 4a 6b + 9c = 2 a = 1, b = 2, c = 2. 21

22 Следовательно, a = (a 2 + b + c) 1 = Выписываем общее решение ЛРС, то есть a = a + a = (c 1 + c 2) (). С помощью начальных условий, находим коэффициенты c 1, и c 2. a 0 = (c 1 + c 2 0) () = 1; a 1 = (c 1 + c 2 1) () = 7. Решая систему c1 + 2 = 1, 4c1 + 4c2 + 5 = 7, получим c 1 = 1, c 2 = 2. Таким образом, решение ЛРС имеет вид: a = (1 2)

23 2. ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ 2.1. Задачи для решения ЛОРС и ЛРС Линейные однородные рекуррентные соотношения второго порядка 1. a +2 = 9 a a, a 0 = 2, a 1 = a +2 = 3,5 a +1 2,5 a, a 0 = 3,5, a 1 = a +2 = 8 a a, a 0 = 4, a 1 = a +2 = 2 a a, a 0 = 3, a 1 = i. 5. a +2 = 10 a a, a 0 = 3, a 1 = a +2 = 6 a a, a 0 = 0, a 1 = 2i a +2 = 8 a a, a 0 = 2, a 1 = a +2 = 4 a a, a 0 = 7, a 1 = a +2 = a +1 + a, a 0 = 2, a 1 = a +2 = 8 a a, a 0 = 8, a 1 = a +2 = () a a, a 0 = 7, a 1 = a +2 = 5 a +1 4 a, a 0 = 0, a 1 = a +2 = 2 a +1 5 a, a 0 = 5, a 1 = 6i a +2 = 3 a a, a 0 = 7, a 1 = a +2 = 6 a +1 9 a, a 0 = 8, a 1 = a +2 = 6 a a, a 0 = 3, a 1 = 9 2i. 17. a +2 = a a, a 0 = 4, a 1 = a +2 = 14 a a, a 0 = 5, a 1 = a +2 = 8 a a, a 0 = 2, a 1 = a +2 = 7 a a, a 0 = 5, a 1 = a +2 = 2 a +1 + a, a 0 = 2, a 1 =

24 1 22. a +2 = a +1 a, a 0 = 4, a 1 = a +2 = 4 a +1 a, a 0 = 12, a 1 = a +2 = a a, a 0 = 2, a 1 = a +2 = 2 a a, a 0 = 8, a 1 = a +2 = 6 a +1 9 a, a 0 = 12, a 1 = a +2 = 4 a +1 5 a, a 0 = 5, a 1 = 10 i a +2 = 3 a +1 a, a 0 = 8, a 1 = a +2 = 14 a a, a 0 = 5, a 1 = a +2 = 4 a a, a 0 = 2, a 1 = a +2 = 4 a +1 5 a, a 0 = 3, a 1 = 6 7i. 32. a +2 = a a, a 0 = 5, a 1 = a +2 = 16 a a, a 0 = 7, a 1 = a +2 = 5 a +1 6 a, a 0 = 2, a 1 = a +2 = 10 a a, a 0 = 2, a 1 = 10 4i a +2 = 6 a +1 5 a, a 0 = 11, a 1 = a +2 = 2 a a, a 0 = 11, a 1 = a +2 = 6 a a ; a 0 = 3, a 1 = 0. Линейные однородные рекуррентные соотношения третьего порядка 39. a +3 = 7 a a a, a 0 = 1, a 1 = 3, a 2 = a +3 = 4 a +2 a +1 6 a, a 0 = 4, a 1 = 5, a 2 = a +3 = 6 a a a, a 0 = 5, a 1 = 8, a 2 = a +3 = 8 a a a, a 0 = 4, a 1 = 31, a 2 = a +3 = 5 a +2 3 a +1 9 a, a 0 = 1, a 1 = 3, a 2 = a +3 = 15 a a a, a 0 = 8, a 1 = 40, a 2 =

25 45. a +3 = 27 a a, a 0 = 6, a 1 = 3, a 2 = a +3 = 6 a a a, a 0 = 15, a 1 = 32, a 2 = a +3 = 15 a a a, a 0 = 1, a 1 = 20, a 2 = a +3 = 9 a a a, a 0 = 0, a 1 = 4, a 2 = a +3 = 2 a a +1 6 a, a 0 = 4, a 1 = 5, a 2 = a +3 = 4 a +2 5 a a, a 0 = 2, a 1 = 6, a 2 = a +3 = 6 a +2 5 a a, a 0 = 4, a 1 = 2, a 2 = a +3 = 3 a a a, a 0 = 2, a 1 = 17, a 2 = a +3 = 9 a a a, a 0 = 1, a 1 = 3, a 2 = a +3 = 6 a a +1 6 a, a 0 = 13, a 1 = 31, a 2 = a +3 = 5 a +2 3 a +1 9 a, a 0 = 3, a 1 = 14, a 2 = a +3 = a a +1 4 a, a 0 = 2, a 1 = 1, a 2 = a +3 = 3 a a a, a 0 = 2, a 1 = 3, a 2 = a +3 = 12 a a a, a 0 = 2, a 1 = 16, a 2 = a +3 = 4 a a a, a 0 = 0,2, a 1 = 6, a 2 = a +3 = 8 a a a, a 0 = 3, a 1 = 13, a 2 = a +3 = 4 a a a, a 0 = 3, a 1 = 29, a 2 = a +3 = 5 a +2 7 a a, a 0 = 11, a 1 = 34, a 2 = a +3 = 11 a a a, a 0 = 27, a 1 = 17, a 2 = a +3 = 12 a a a, a 0 = 1, a 1 = 37, a 2 = a +3 = 3 a a a, a 0 = 11, a 1 = 23, a 2 = a +3 = 7 a a a, a 0 = 3, a 1 = 6, a 2 = a +3 = 4 a a a, a 0 = 4, a 1 = 1, a 2 = 4.; 68. a +3 = 7 a a a, a 0 = 1, a 1 = 0, a 2 = a +3 = 5 a a a, a 0 = 6, a 1 = 0, a 2 = a +3 = 5 a +2 3 a a, a 0 = 10, a 1 = 1, a 2 = a +3 = 3 a +2 3 a +1 + a, a 0 = 2, a 1 = 4, a 2 = a +3 = 3 a a a, a 0 = 6, a 1 = 5, a 2 =

26 73. a +3 = 10 a a a, a 0 = 0, a 1 = 1, a 2 = a +3 = 8 a a a, a 0 = 8, a 1 = 23, a 2 = a +3 = 5 a +2 8 a +1 4 a, a 0 = 11, a 1 = 15, a 2 = a +3 = a a a, a 0 = 6, a 1 = 5, a 2 = a +3 = 10 a a a, a 0 = 1, a 1 = 2, a 2 = a +3 = a a a, a 0 = 1, a 1 = 14, a 2 = a +3 = 2 a +2 + a a, a 0 = 10, a 1 = 1, a 2 = a +3 = 5 a +2 8 a a, a 0 = 9, a 1 = 9, a 2 = a +3 = 8i a a +1 10i a, a 0 = 8, a 1 = 14i, a 2 = 38. Линейные рекуррентные соотношения первого порядка 82. a +1 = 4 a + 6, a 0 = a +1 = a + + 1, a 0 = a +1 = 5 a , a 0 = a +1 = 3 a + 5 2, a 0 = a +1 = 3 a + (4) 5 1, a 0 = a +1 = 4 a + 8 4, a 0 = a +1 = 3 a , a 0 = 14. Линейные рекуррентные соотношения второго порядка 89. a +2 = 7 a a + 10, a 0 = 4, a 1 = a +2 = 10 a a + 32, a 0 = 1, a 1 = a +2 = 6 a +1 9 a 2 3, a 0 = 0, a 1 = a +2 = 7 a a , a 0 = 3, a 1 = a +2 = 9 a a + (18 20) 2, a 0 = 6, a 1 = a +2 = 8 a +1 7 a , a 0 = 9, a 1 = a +2 = 4 a +1 9 a , a 0 = 15, a 1 = 27 i a +2 = 12 a a , a 0 = 13, a 1 = 6. 26

Благовещенский государственный педагогический университет кафедра алгебры, геометрии и МПМ 16 апреля 2011 г. 1 Решение рекуррентных соотношений Определение Рекуррентным соотношением называется соотношение

Лекция 3. Последовательности, определяемые рекуррентными соотношениями. Однородные и неоднородные линейные рекуррентные уравнения (ЛОРУ и ЛНРУ). Общие решения ЛОРУ и ЛНРУ. Лектор - доцент Селезнева Светлана

Лекция: Последовательности. Однородные и неоднородные линейные рекуррентные уравнения. Общие решения линейных рекуррентных однородных и неоднородных уравнений. Лектор - доцент Селезнева Светлана Николаевна

Лекция. Функции натурального аргумента (последовательности). Однородные и неоднородные линейные рекуррентные уравнения (ЛОРУ и ЛНРУ). Общие решения ЛОРУ и ЛНРУ. Примеры Лектор - доцент Селезнева Светлана

РЕШЕНИЕ РЕКУРРЕНТНЫХ УРАВНЕНИЙ Обозначим через значение некоторого выражения при подстановке в него целого числа Тогда зависимость члена последовательности от членов последовательности F F со значениями

Пензенский государственный педагогический университет им В Г Белинского О А Монахова, Н А Осьминина Рекуррентные последовательности Алгебра формальных рядов Методические рекомендации для студентов специальностей

Лекция 3. Последовательности, определяемые рекуррентными соотношениями. Однородные и неоднородные линейные рекуррентные уравнения (ЛОРУ и ЛНРУ). Общие решения ЛОРУ и ЛНРУ. Примеры Лектор - доцент Селезнева

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Сибирский государственный индустриальный университет»

Министерство транспорта Российской Федерации ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «РОССИЙСКИЙ УНИВЕРСИТЕТ ТРАНСПОРТА (МИИТ)» Кафедра «Математический анализ»

Лекции по Математике Вып ТММ- Ю В Чебраков ТЕОРИЯ МАГИЧЕСКИХ МАТРИЦ Санкт-Петербург, 00 УДК 5+5 ББК Ч35 Р е ц е н з е н т ы: Доктор физико-математических наук, профессор С-Петерб техн ун-та М А Салль Кандидат

А А КИРСАНОВ КОМПЛЕКСНЫЕ ЧИСЛА ПСКОВ ББК 57 К45 Печатается по решению кафедры алгебры и геометрии, и редакционно-издательского совета ПГПИ им СМ Кирова Рецензент: Медведева ИН, кандидат физ мат наук, доцент

Михайлова Инна Анатольевна Институт математики и естественных наук. Кафедра алгебры и фундаментальной информатики. 30 сентября 2018 г. Примеры Числа Фибоначчи Числа Фибоначчи 1, 1, 2, 3, 5, 8, 13, 21,...

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

Глава 0 ПОСЛЕДОВАТЕЛЬНОСТИ Алгоритмы А- Задание числовых последовательностей А- Арифметическая прогрессия А- Геометрическая прогрессия А- Суммирование А-5 Бесконечно убывающая геометрическая прогрессия

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СПЕЦИАЛИЗИРОВАННЫЙ УЧЕБНО-НАУЧНЫЙ ЦЕНТР Математика 0 класс МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ И БЕСКОНЕЧНЫЕ ЧИСЛОВЫЕ

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Ухтинский государственный технический университет (УГТУ) ПРЕДЕЛ ФУНКЦИИ Методические

ЧИСЛОВЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ. ГЕОМЕТРИЧЕСКАЯ ПРОГРЕССИЯ Геометрической прогрессией называется числовая последовательность b, первый член которой отличен от нуля, а каждый последующий член, начиная со второго,

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное общеобразовательное учреждение высшего профессионального образования «Тверской государственный университет» Математический факультет Кафедра алгебры

Глава 0 ТЕСТОВЫЕ ЗАДАНИЯ И ДИКТАНТЫ Т-00 Вычисление членов последовательности по рекуррентной формуле Т-00 Составление рекуррентной формулы Т-00 Формула общего члена Т-004 Составление арифметической прогрессии

6-7 уч год 6, кл Математика Комплексные числа 4 Алгебраические уравнения Квадратные уравнения В школьном курсе алгебры рассматривались квадратные уравнения ax bx c =, a, () с действительными коэффициентами

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Государственное образовательное учреждение высшего профессионального образования МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МАШИНОСТРОЕНИЯ ИИ Поспелов,

Лекция Глава Множества и операции над ними Понятие множества Понятие множество относится к наиболее первичным понятиям математики не определяемым через более простые Под множеством понимают совокупность

Лекции по Математике. Вып. ТММ-1 Ю. В. Чебраков ТЕОРИЯ МАГИЧЕСКИХ МАТРИЦ Санкт-Петербург, 010 УДК 511+51 ББК Ч345 Р е ц е н з е н т ы: Доктор физико-математических наук, профессор С.-Петерб. техн. ун-та

Прогрессии Последовательность функция натурального аргумента.. Задание последовательности формулой общего члена: a n = f(n), n N, например, a n = n + n + 4, а = 43, а = 47, а 3 = 3,. Задание последовательности

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

Оглавление Введение. Основные понятия.... 4 1. Интегральные уравнения Вольтерры... 5 Варианты домашних заданий.... 8 2. Резольвента интегрального уравнения Вольтерры. 10 Варианты домашних заданий.... 11

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н. И. ЛОБАЧЕВСКОГО Факультет вычислительной математики и кибернетики Кафедра математической

Лекция. Задача о кроликах. Числа Фибоначчи, последовательность Фибоначчи, рекуррентная формула 3. Свойства чисел Фибоначчи (a) Линейность (b) Теоретико-числовые свойства (c) Суммы: F + F +... + F n, нечетных

ЛИНЕЙНАЯ АЛГЕБРА Издательство ТГТУ Министерство образования и науки Российской Федерации ГОУ ВПО "Тамбовский государственный технический университет" ЛИНЕЙНАЯ АЛГЕБРА Методические указания для студентов

Тишин В И Основные методы решения тригонометрических уравнений г Тишин В И Математика для учителей и учащихся Материал подготовлен учителем математики Тишиным Владимиром Ивановичем года Тишин В И Основные

Дифференциальные уравнения высшего порядка. Конев В.В. Наброски лекций. Содержание 1. Основные понятия 1 2. Уравнения, допускающие понижение порядка 2 3. Линейные дифференциальные уравнения высшего порядка

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

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

Лекция 3 Ряды Тейлора и Маклорена Применение степенных рядов Разложение функций в степенные ряды Ряды Тейлора и Маклорена Для приложений важно уметь данную функцию разлагать в степенной ряд, те функцию

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

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

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Заочная школа Математическое отделение МЕТОД МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ И БЕСКОНЕЧНЫЕ ЧИСЛОВЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ 0-й класс, задание ПРАВИЛА ОФОРМЛЕНИЯ ЗАДАНИЯ Приступая

ЗАДАНИЯ К КОНТРОЛЬНОЙ РАБОТЕ По дисциплине: «Алгебра» Специальность: «Математика» заочная форма обучения 6 семестр Составитель: зав кафедрой Трофимук АА Многочлены от нескольких переменных результант алгебраические

Указания, решения, ответы УРАВНЕНИЯ В ЦЕЛЫХ ЧИСЛАХ. Уравнение с одной неизвестной.. Решение. Подставим в уравнение. Получим равенство (4a b 4) (a b 8) 0. Равенство A B 0, где А и В целые, выполняется,

ВВЕДЕНИЕ В МАТЕМАТИЧЕСКИЙ АНАЛИЗ Лекция. Понятие множества. Определение функции основные свойства. Основные элементарные функции СОДЕРЖАНИЕ: Элементы теории множеств Множество вещественных чисел Числовая

Рабочая программа по алгебре для учащихся 8-9 классов разработана на основе требований к результатам освоения основной образовательной программы основного общего образования. Рабочая программа рассчитана

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

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

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Нижегородский государственный университет им НИ Лобачевского Национальный исследовательский университет АВ Леонтьева СБОРНИК ЗАДАЧ (МЕТОД МАТЕМАТИЧЕСКОЙ

АГЕНТСТВО ОБРАЗОВАНИЯ АДМИНИСТРАЦИИ КРАСНОЯРСКОГО КРАЯ КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЗАОЧНАЯ ЕСТЕСТВЕННО-НАУЧНАЯ ШКОЛА при КрасГУ ДОПОЛНИТЕЛЬНЫЕ ГЛАВЫ МАТЕМАТИКИ 10 класс Модуль 4 МЕТОДЫ РЕШЕНИЯ

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

СТЕПЕНЬ С ДРОБНЫМ ПОКАЗАТЕЛЕМ Если показатель t степени числа является дробным, те t, N, то для неотрицательных значений (0) по определению полагают def Для отрицательных чисел (0) < операция возведения

Министерство сельского хозяйства Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Пермская государственная сельскохозяйственная академия имени

РАЦИОНАЛЬНЫЕ ЧИСЛА Обыкновенные дроби Определение Дроби вида, называются обыкновенными дробями Обыкновенные дроби, правильные и неправильные Определение Дробь, правильной, если < при, где Z, N Z, N Z,

Лекция. 5. ОПИСАНИЕ И АНАЛИЗ ДИСКРЕТНЫХ ЛИНЕЙНЫХ СИСТЕМ С ПОМОЩЬЮ РАЗНОСТНЫХ УРАВНЕНИЙ 5.. ОДНОМЕРНЫЕ СИСТЕМЫ ПРИ ДЕТЕРМИНИРОВАННЫХ ВОЗДЕЙСТВИЯХ 5... Описание сигналов и систем. Описание сигналов. Сигналы

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

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

Тема 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,

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Московский государственный университет геодезии и картографии (МИИГАиК) Факультет дистанционных форм обучения Заочное отделение `` МЕТОДИЧЕСКИЕ УКАЗАНИЯ,

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

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

ЛЕКЦИЯ КОМПЛЕКСНЫЕ ЧИСЛА РАЗЛОЖЕНИЕ МНОГОЧЛЕНОВ НА МНОЖИТЕЛИ Числовые множества Множество комплексных чисел Многочлены с вещественными коэффициентами Разложение на множители ЧИСЛОВЫЕ МНОЖЕСТВА МНОЖЕСТВО

Комбинаторные вычисления на конечных множествах

Введение в комбинаторику

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

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

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

Асимптотика

Асимптота - особая линия (чаще всего прямая), являющаяся предельной для рассматриваемой кривой.

Асимптотика - это искусство оценивания и сравнения скоростей роста функций. Говорят, что при х ®¥ функция "ведёт себя, как х ", или "возрастает с такой же скоростью, как х ", и при х ®0 "ведёт себя, как 1/x ". Говорят, что "logx при x ®0 и любом e>0 ведёт себя, как x e , и что при n ®¥ растёт не быстрее, чем n logn ". Такие неточные, но интуитивно ясные утверждения полезны при сравнении функций так же, как и соотношения <, £ и = при сравнивании чисел.

Определим три основных асимптотических соотношения.

Определение 1. Функция f (x ) эквивалентна g (x ) при х ®x 0 , если и только если =1.

В этом случае говорят, что функция f (x ) асимптотически равна функции g (x ) или что f (x ) растёт с такой же скоростью, как и g (x ).

Определение 2 . f (x )=o(g (x )) при x ®x 0 , если и только если =0.

Говорят, что при x ®x 0 f (x ) растёт медленнее, чем g (x ), или что f (x ) "есть о-малое" от g (x ).

Определение 3. f (x )=О(g (x )) при x ®x 0 , если и только если существует константа С такая, что sup =С.

В этом случае говорят, что f (x ) растёт не быстрее, чем g (x ), или что при x ®x 0 f (x ) "есть О-большое" от g (x ).

Cоотношение f (x )=g (x )+o (h (x )) при x ®¥ означает, что f (x)-g (x )=o (h (x )). Аналогично f (x )=g (x )+О (h (x )) означает, что f (x )-g (x )=О (h (x )).

Выражения О(·) и о(·) могут использоваться также и в неравенствах. Например, неравенство x +o (x )£2x при x ®0 означает, что для любой функции f (x ) такой, что f (x )=o (x ), при x ®¥ имеет место соотношение x+f (x )£2x для всех достаточно больших значений х .

Приведём некоторые полезные асимптотические равенства.

Полином асимптотически равен своему старшему члену:

при x ®¥; (4.1)

при x ®¥; (4.2)

при x ®¥ и a k ¹0. (4.3)

Суммы степеней целых чисел удовлетворяют соотношению:

при n ®¥. (4.4)

Отсюда, в частности, имеем при n ®¥

В более общем случае при n ®¥ и для любого целого k ³0

; (4.6)

. (4.7)

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

Понятие рекуррентных соотношений проиллюстрируем на классической проблеме, поставленной и изученной Фибоначчи около 1200 г.

Фибоначчи поставил свою проблему в форме рассказа о скорости роста популяции кроликов при следующих предположениях. Все начинается с одной пары кроликов. Каждая пара кроликов становится фертильной (fertile – плодовитый) через месяц, после чего каждая пара рождает новую пару кроликов каждый месяц. Кролики никогда не умирают, и их воспроизводство никогда не прекращается. Пусть F n - число пар кроликов в популяции по прошествии n месяцев и пусть эта популяция состоит из N n пар приплода и O n “старых” пар, т.е. F n = N n + O n . Таким образом, в очередном месяце произойдут следующие события:

Старая популяция в (n +1)-й момент увеличится на число родившихся в момент времени n , т.е. O n+1 = O n + N n = F n ;

Каждая старая в момент времени n пара производит в момент времени (n +1) пару приплода, т.е. N n+1 = C n .

В последующий месяц эта картина повторяется:

O n+2 = O n+1 + N n+1 = F n+1 ,

N n+2 = O n+1 ;

объединив эти равенства, получим рекуррентное соотношение Фибонначи:

O n+2 + N n+2 = F n+1 + O n+1 ,

F n+2 = F n+1 + F n . (4.8)

Выбор начальных условий для последовательности чисел Фибоначчи не важен; существенные свойства этой последовательности определяются рекуррентным соотношением (4.8). Обычно полагают F 0 =0, F 1 =1 (иногда полагают F 0 =F 1 =1).

Рекуррентное соотношение (4.8) является частным случаем однородных линейных рекуррентных соотношений с постоянными коэффициентами:

x n = a 1 x n-1 + a 2 x n-2 +…a k x n-k , (4.9)

где коэффициенты a i не зависят от n и x 1 , x 2 , …, x k считаются заданными.

Существует общий метод решения (т.е. отыскания x n как функции n ) линейных рекуррентных соотношений с постоянными коэффициентами. Этот метод рассмотрим на примере соотношения (4.8). Найдём решение в виде

F n =cr n (4.10)

с постоянными с и r . Подставляя это выражение в (4.8), получим

cr n + 2 = cr n+ 1 + cr n ,

cr n (r n -r -1)=0. (4.11)

Это означает, что F n =cr n является решением, если либо с =0, либо r = 0 (и отсюда F n =0 для всех n ), а также (и это более интересный случай) если r 2 - r -1=0, причём константа с произвольна. Тогда из (4.11) следует

r = или r = . (4.12)

Число »1,618 известно как ²золотое² сечение, поскольку с древних времен считается, что треугольник (прямоугольник) со сторонами 1 и имеет наиболее приятные для глаза пропорции.

Сумма двух решений однородного линейного рекуррентного соотношения, очевидно, также является решением, и можно на самом деле показать, что общее решение последовательности Фибоначчи имеет вид

F n = , (4.13)

где константы с и с’ определяются начальными условиями. Положив F 0 =0 и F 1 =1, получим следующую систему линейных уравнений:

, (4.14)

решение которой даёт

c = -c" = . (4.15)

Линейные рекуррентные соотношения с постоянными коэффициентами. Основные определения и примеры рекуррентных соотношений Часто решение одной комбинаторной задачи удается свести к решению аналогичных задач меньшей размерности с помощью некоторого соотношения называемого рекуррентным от латинского слова recurrere – возвращаться. Тем самым решение сложной задачи можно получить последовательно находя решение более легких задач и далее пересчитывая по рекуррентным соотношениям находить решение трудной задачи. Рекуррентным соотношением го...

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

аранов Виктор Павлович. Дискретная математика. Раздел 2. Элементы комбинаторики.

Лекция 5. Метод рекуррентных соотношений

Лекции 5. МЕТОД РЕКУРРЕНТНЫХ СООТНОШЕНИЙ

План лекции:

1. Основные определения и примеры рекуррентных соотношений.
2. Линейные рекуррентные соотношения с постоянными коэффициентами. Формула

Бине.

1. Основные определения и примеры рекуррентных соотношений

Часто решение одной комбинаторной задачи удается свести к решению аналогичных задач меньшей размерности с помощью некоторого соотношения, называемого реку р рентным (от латинского слова recurrere – возвращаться). Тем самым решение сложной задачи можно получить, последовательно находя решение более легких задач, и далее, п е ресчитывая по рекуррентным соотношениям, находить решение трудной задачи.

Рекуррентным соотношением -го порядка между элементами последовательности чисел называется формула вида

(1)

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

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

(2)

общим решением будет

. (3)

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

Так как эта система имеет решение при любых значениях и, то решение (3) действительно является общим решением соотношения (2).

Пример 1 . Числа Фибоначчи. В 1202 г. знаменитым итальянским математиком Ле о нардо Пизанским, который известен больше по своему прозвищу Фибоначчи ( Fib o nacci – сокращенное filius Bonacci , т. е. сын Боначчи), была написана книга « Liber abacci » («Кн и га об абаке»). До нас эта книга дошла во втором своем варианте, который относится к 1228 г. Рассмотрим одну из множества приведенных в этой книге задач.

Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), пр и чем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится ч е рез год, если в начале года была одна пара кроликов?

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

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

. (4)

Так как, то последовательно находим: и т. д. Эти числа составляют последовательность

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…,

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

Найти число двоичных слов длины, в которых никакие две единицы не идут по д ряд.

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

(5)

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

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

. (6)

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

Таблица 1

Первые два значения находятся непосредственно (– слова 0 и 1; – слова 000, 010, 101), а остальные – по формуле (6).

Пример 2. Задача о расстановке скобок в выражении с неассоциативной бина р ной операцией. Пусть “” обозначает некоторую бинарную операцию. Рассмотрим в ы ражение, в котором символ обозначает некоторую бинарную неассоци а тивную операцию. Сколько имеется различных способов расстановки скобок в этом в ы раж е нии?

Как пример неассоциативной операции можно привести векторное произведение. Другой пример – обычное сложение и умножение, выполняемое на компьютере. В с и лу того, что представление каждого числа в памяти компьютера ограничено определе н ным количеством разрядов, при выполнении каждой операции возникает погрешность и су м марный результат этих погрешностей зависит от расстановки скобок. Пусть – маши н ный ноль . Это означает, что. Тогда, в то время как.

Обозначим число всевозможных способов расстановки скобок через. Тогда

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

(7)

где.

По определению количество способов расстановки скобок для вычисления первых операндов равно, последних – . По правилу произведения число расстановок ск о бок для выражения (4) равно. По правилу сложения

, (8)

Например, .

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

Пусть функция в соотношении (1) является лине й ной

, (9)

где – некоторые числа. Такие соотношения называют линейными соотн о шениями -го порядка с постоянными коэффициентами.

Сначала исследуем подробно соотношения второго порядка, а затем перейдем к о б щему случаю. При из формулы (9) получим

, . (10)

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

Лемма 1. Пусть – решение соотношения (10), а – любое число. Тогда последовательность также является решен и ем этого соотношения.

Лемма 2. Пусть и – решения соотн о шения (10). Тогда последовательность также явл я ется решением этого соотношения.

Из этих двух простых лемм можно сделать следующий важный вывод. Совоку п ность всевозможных последовательностей с операциями покоо р динатного сложения и умножения на скаляр образует векторное пространство. Совоку п ность последовательностей, являющихся решениями соотношения (10), представляет с о бой подпространство этого пространства. Объемлющее пространство всевозможных п о следовательностей бесконечномерно, но подпространство решений линейного рекуррен т ного соотношения имеет конечную размерность, равную порядку уравн е ния.

Лемма 3. Размерность пространства решений рекуррентного соотношения (10) равна двум.

Из леммы 3 следует, что для определения всех решений уравнения (12) необходимо отыскать два линейно независимых решения. Любое другое решение будет представлят ь ся линейной комбинацией этих базисных решений.

Рассмотрим рекуррентное соотношение первого порядка

, (11)

где – константа.

Если, то из (11) имеем

, (12)

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

Будем искать решение рекуррентного соотношения второго порядка также в виде (12). Тогда, подставляя (12) в (9), получим

. (13)

При =0 имеем нулевое решение, которое не представляет интереса. Считая, поделим последнее соотношение на:

(14)

Таким образом, геометрическая прогрессия (12) является решением рекуррентного соотношения (10), если знаменатель прогрессии является корнем квадратного уравн е ния (14). Это уравнение называется характеристическим уравнением для рекуррентного соо т ношения (9).

Построение базисных решений зависит от корней и характеристического уравнения (14).

1. (). В этом случае имеем два решения и, которые л и нейно незав и симы. Чтобы убедиться в этом, покажем, что из формулы

(15)

путем соответствующего выбора констант можно получить любое решение соотношения (10). Рассмотрим произвольное решение. Выберем константы и так, чтобы при и:

(16)

Определитель линейной системы (16)

следовательно, система имеет единственное решение, а значит формула (15) – общее р е шения соотношения (10).

1. . В случае кратных корней характеристическое уравнение (13) имеет вид или. Тогда, а для соотношения (10) п о лучим уравнение, которое дает два базисных решения и. Общее решение представляется в виде

. (17)

В случае соотношения -го порядка (9) имеют место утверждения, аналогичные тем, которые были рассмотрены для уравнений 2-го порядка.

1. Совокупность всех решений уравнения (9) является подпространством в пр о странстве всех последовательностей.
2. Размерность этого пространства равна, то есть каждое решение однозначно определяется своими первыми значениями.
3. Для определения базиса подпространства решений составляется характеристич е ское уравнение

. (18)

Многочлен

(19)

называется характеристическим многочленом рекуррентного соотношения (9).

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

. (20)

При заданных начальных значениях решения, константы н а ходятся из системы

1. Если – корень характеристического уравнения кратности, то соотношение (9) имеет следующие решения

Пусть характеристическое уравнение (18) имеет корни: ,…, кратности с о ответственно,…, причем. Тогда характеристический мног о член и общее решение соотношения (9) представятся в виде

Пример 3 . Формула Бине . Поставим задачу получить формулу в явном виде для ч и сел Фибоначчи. Для этого найдем решение рекуррентного соотношения (4) при условии, что. Составим характеристическое уравнение, найдем его корни и получим общее решение. Константы и опред е лим из начальных условий: . Тогда или

, (21)

где – золотое сечение. Формула (21) называется формулой Бине . При этом. Из формулы Бине следует, что.

Данный метод состоит в том, что решение комбинаторной задачи с n предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, называемого рекуррентным. Говорят, что последовательность элементов u0 , u1 , … un , … над полем комплексных чисел C удовлетворяет рекуррентному соотношению порядка k, если

где a1 , … , ak - коэффициенты из C. Соотношения такого типа естественным образом возникают при решении комбинаторных задач.

Пример. Пусть имеется последовательность позиций, занумерованных числами 1, 2, … , n, … и в начальный момент предмет находится в 1-ой позиции. За один ход предмет продвигается вперед на 1 и 2 позиции. Найти число способов попадания в n-ю позицию.

♦ Пусть un - интересующее нас число. Ясно, что u2 = 1, u3 = 2 . Далее, разобьем все способы попадания в позицию с номером n на два класса: те, при которых на последнем шаге предмет передвигается на 1 шаг и те, при которых он передвигается на 2 шага. Ясно, что в первом случае имеем un-1 вариантов, во втором un-2 вариантов. Следовательно, имеем

Многочлен P(x) называется характеристическим для линейного рекуррентного соотношения (2). Заметим, что всякая рекуррентная последовательность k-го порядка однозначно определяется заданием k ее первых членов.

Пусть λ - корень характеристического многочлена P(x).

Теорема 1. Последовательность u0 , u1 , … un , … , где un = cλ n , c - произвольная константа из C, удовлетворяет линейному рекуррентному соотношению (2).

♦ Подставляя данные значения un , n = 0, 1, … в (2), имеем

cλ n - a1 cλ n-1 - a2 cλ n-2 - … - ak cλ n-k = cλ n-k (λ k - a1 λ k-1 - … - ak ) ≡ 0. ♦

Теорема 2. Пусть последовательности un , vn , n = 0, 1, … удовлетворяют линейному рекуррентному соотношению (2). Тогда этим свойством обладает последователь-

ность rn , n = 0, 1, … , где rn = α un + β vn , n , α, β - произвольные константы из C.

♦ Доказательство очевидно. ♦

Теорема 3. Пусть λ 1 , … , λ k - простые (т.е. не являющиеся кратными) корни характеристического многочлена P(x) для последовательности (2).

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

где c1 , … , ck - подходящие константы из C.

♦ Согласно предыдущему замечаем, что последовательностьun , n = 0, 1, … есть решение соотношения (2). Чтобы доказать, что любое решение имеет вид (5) достаточно показать, что для произвольной последовательности vn , n = 0, 1, … , удовлетворяющей

(2), существуют константы c1 , … , ck , такие, что un = vn , n . Для этого достаточно, чтобы выполнялось v0 = u0 , v1 = u1 , … , vk-1 = uk-1 . Рассмотрим данные условия

относительно c1 , c2 , … , ck . Определитель этой системы есть определитель Вандермонда и согласно (7, стр. 118).

согласно предположению о корнях λ 1 , … , λ k . Отсюда и следует утверждение. ♦ В качестве примера рассмотрим рекуррентное соотношение (3). Имеем характеристический многочлен

P(x) = x2 - x -1

Его корни равны λ 1 = 1 + 2 5 , λ 2 = 1 − 2 5 , Общее решение имеет вид

u n = c 1 1+ 2 5 n + c 2 1− 2 5 n

Система уравнений для констант c1 , c2 : c1 1 + 2 5 + c2 1 − 2 5 = 1

Пусть теперь λ - корень кратности r характеристического многочлена P(x). Аналогично предыдущему доказывается

Теорема 4. Последовательности c1 λ n , c2 nλ n ,K , cr n r − 1 λ n , n = 0, 1, … для про-

извольных констант c1 , … , cr из C удовлетворяют соотношению (2).

Теорема 5. Пусть характеристический многочлен P(x) имеет корни λ 1 , … , λ s кратностей r1 , … , rs (r1 + … + rs = k) . Тогда общее решение рекуррентного соотношения

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

un = a1 un-1 + … + ak un-k

с начальными условиями u1 , … , uk . Тогда справедливо соотношение при всех n ≥ k

♦ Доказательство индукцией по n. При n = k равенство (8) справедливо. Пусть оно верно при n. При n + 1 имеем

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

Теорема 7. Пусть C(n, k) - число подстановок n-элементного множества, имеющих точно k циклов. Тогда справедливо

♦ Разобьем множество подстановок множества X = {1, 2, … n,} имеющих точно k циклов, на два класса - подстановки, в которых элемент n содержится в единичном цикле, и подстановки, в которых элемент n находится в цикле длины l, l > 1. В первом случае число подстановок совпадает с числом подстановок множества X′ = {1, 2, …, n - 1}, имеющих k - 1 циклов, т.е. C(n - 1, k - 1). Во втором случае, удаляя элемент n, полу-

чаем подстановку множества X′ = {1, 2, …, n - 1} с k циклами, число которых равно C(n - 1, k). Выясним теперь, каким числом способов в подстановку степени n - 1 с k циклами можно добавить элемент n. Если имеется цикл длины i, то это можно сделать i способами. Общее число способов равно i1 + … + ik , где i1 , … , ik - длины циклов подстановки. Однако i1 + … + ik = n - 1. Значит число подстановок второго класса равно

(n - 1)C(n - 1, k). Отсюда и получаем (9). ♦

Полученные числа C(n, k) связаны с известными числами Стирлинга первого рода sn,k , которые определяются так:

sn,k = (- 1)n+k C(n, k)

Приведем таблицу нескольких первых значений чисел sn,k .

Табл. Числа Стирлинга первого рода

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

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

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

ее логарифм. Последний всегда можно представить в виде

Логарифм функции правдоподобия для совокупности данных наблю­дения без последнего значения, а

Логарифм условной плотности вероятности значения при заданных значениях и .

Представление (7,5.16) для логарифма функции правдоподобия яв­ляется основой для получения рекуррентной процедуры вычисления оценки максимального правдоподобия. Рассмотрим регулярный случай. При этом оценка максимального правдоподобия может быть найдена как решение уравнения

которое отличается от (7.1.6) только введением индекса п у логарифма функции правдоподобия.

Обозначим решение этого уравнения через подчеркнув тем са­мым, что эта оценка получена по совокупности данных наблюдения . Аналогично обозначим через решение уравнения- оценку максимального правдоподобия, полученную по совокупности данных .

Уравнение (7.5.19) можно переписать с учетом (7.5.16) в следующем виде:

Разложим левую часть (7.5.20) в ряд Тейлора в окрестности точки . При этом

(7.5.22)

Вектор градиента функции в точке ; слагаемое обращается в нуль благодаря тому, что , является решением уравнения правдоподобия для предыдущего (п - 1)-го шага:

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

где - матрица, обратная .

Это решение представлено в форме рекуррентного соотношения, определяющего очередное значение оценки через оценку на предыдущем шаге и поправку , зависящую от имеющихся данных наблюдения непосредственно и через предыдущую оценку. Поправка формируется как произведение градиента логарифма условной плотно­сти вероятности вновь полученного значения х n в точке , равной предыдущей оценке, на весовую матрицу . По­следняя определяется выражением (7.5.23) и также зависит от оценки на предыдущем шаге, а ее зависимость от новых данных наблюдения целиком определяется видом логарифма условной плотности веро­ятности .

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

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

Аналогично, в случае марковской последовательности данных на­блюдения, то есть при

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

Рассмотрим теперь структуру весовой матрицы , входящей в ре­куррентное соотношение (7.5.24). Согласно определению (7.5.23), из-за наличия слагаемого она, вообще говоря, зависит от всех значений даже при независимых значениях , что ли­шает рекуррентное соотношение (7.5.24) преимуществ, связанных с воз­можным сокращением количества запоминаемых с предыдущего шага данных. Существует несколько способов приближенного вычисления ма­трицы , которые устраняют этот недостаток.

Первый из них основан на более последовательном использовании основного предположения о малом различии двух очередных значений оценки и , которое является основой для получения рекур­рентного соотношения (7.5.24). Это позволяет получить аналогичное ре­куррентное соотношение для весовой матрицы .Действительно, используя малость из (7.5.23), имеем

Введя обозначение

из (7.5.24) и (7.5.25) получим систему рекуррентных соотношений для вектора и весовой матрицы

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

При независимых значениях система рекуррентных соотношений (7.5.27), очевидно, описывает многомерный (размерности ) марковский случайный процесс, компонента которого сходит­ся к истинному значению параметра , а компонента сходится к ин­формационной матрице Фишера (7.3.8), где - истинное значение оцениваемого параметра, и неограниченно увеличивается с ростом п. Аналогичные свойства сходимости система (7.5.27) имеет и при более общихусловиях, если последовательность явля­ется эргодической.

Второй из упомянутых способов основан на замене матрицы вторых производных от логарифма функции правдоподобия ее матема­тическим ожиданием - информационной матрицей Фишера, которая с учетом (7.5.16) может быть записана в виде:

где аналогично (7.5.26)

Заменяя в (7.5.24) матрицу матрицей , получаем ре­куррентное соотношение

для приближенного вычисления оценок максимального правдоподобия, предложенное Сакрисоном (в оригинале для независимых одина­ково распределенных , когда и . Это рекуррентное соотношение проще системы (7.5.27), поскольку оптимальная весовая матрица заменена ее мате­матическим ожиданием, и для ее нахождения не требуются имеющиеся данные наблюдения, кроме тех, которые сконцентрированы в значении оценки . В то же время очевидно, что подобная замена означает необходимость выполнения дополнительного по сравнению с (7.5.27) требования близости матрицы вторых производных к своему математи­ческому ожиданию.

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

Математическое ожидание матрицы (информационная матри­ца Фишера для одного наблюдения ), взятое в точке . Эта система отличается от (7.5.27) тем, что во втором из рекуррентных соот­ношений (7.5.31) не участвуют непосредственно данные наблюдения .

Любая из рассмотренных выше систем рекуррентных соотношений является совершенно точной, если функция квадратично зависит от , и дополнительно матрица вторых производных не зависит от . Фактически это соответствует случаю независимых нормально рас­пределенных (не обязательно одинаково) значений с неизвестным математическим ожиданием , которое и представляет собой оценивае­мый параметр.

Система рекуррентных соотношений (7.5.24) дает точное решение уравнения максимального правдоподобия в гораздо более широких условиях при единственном требовании, чтобы функция квадра­тично зависела от . При этом зависимость от произвольна, что соответствует широкому классу распределений вероятности совокуп­ности как с независимыми, так и с зависимыми значениями.

Наряду с рассмотренными общими способами существует еще ряд методов выбора матрицы весовых коэффициентов в рекуррентном соотношении (7.5.24), приспособленных к тем или иным конкретным ограничениям. Простейшим из них является выбор в виде диагональной матрицы, так что , (I - единичная матрица), где - убывающая последовательность чис­ловых коэффициентов, выбираемая независимо от свойств функции правдоподобия так же, как в процедуре стохастической аппроксимации Робинса - Монро, которая будет рассмотрена в следующих главах.

Стоит отметить, что любые итерационные или рекуррентные про­цедуры нахождения оценок максимального правдоподобия в общем случае являются приближенными. Поэтому, вообще говоря, для оценок, получающихся в результате применения этих процедур, состоятельность, асимптотическую эффективность и асимптотическую нормальность нуж­но доказывать заново. Для итеративных процедур необходимые свой­ства оценок гарантируются тем, что в принципе такие процедуры при соответствующем числе итераций дают решение уравнения правдоподо­бия с любой наперед заданной точностью. Для рекуррентных процедур типа (7.5.27), (7.5.30), (7.5.31) и других имеются специальные доказа­тельства. При этом, помимо требования регулярности, предъявляются некоторые дополнительные требования:

На поведение функции (7.2.2) при различных значениях ||, для достижения с помощью рекуррентной процедуры глобаль­ного максимума этой функции в точке , соответствующей истинно­му значению параметра;

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

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

является оценкой максимального правдоподобия и может быть пред­ставлена в рекуррентном виде:

что является самым простым частным случаем (7.5.30) при

Другой пример - это нерегулярная оценка максимального правдо­подобия для параметра - ширины прямоугольного распределения – из (7.4.2), которая также может быть определена рекуррентным соот­ношением

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

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

7.5.3. Переход к непрерывному времени. Дифференциальные уравнения для оценок максимального правдоподобия

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

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

Логарифм функционала отношения правдоподобия может быть представлен в виде

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

где - известная функция времени и параметров , а - дельта-коррелированный случайный процесс («белый» шум) со спек­тральной плотностью N o ,то, выбирая в качестве знаменателя отношения правдоподобия распределения вероятности х при , будем иметь

Пусть - оценка максимального правдоподобия параметра , построенная по реализации процесса на интервале ,то есть решение уравнения максимального правдоподобия

Дифференцируя левую часть этого уравнения по времени, получаем

Вводя обозначения

и решая уравнение (7.5.42) относительно , получаем диффе­ренциальное уравнение для оценки максимального правдоподобия

Матрица , в свою очередь, согласно (7.5.37) определяется диффе­ренциальным уравнением

Так же, как в дискретном случае, матрица в (7.5.45), (7.5.47) мо­жет быть заменена своим математическим ожиданием - информационной матрицей Фишера при значении , а диф­ференциальное уравнение (7.5.46) для весовой матрицы - урав­нением

где аналогично дискретному случаю

Математическое ожидание матрицы вторых производных .

Совокупность дифференциальных уравнений (7.5.45), (7.5.46) или (7.5.45), (7.5.48) совместно с начальными условиями, относительно вы­бора которых остается в силе все сказанное для дискретного случая, полностью определяет оценку максимального правдоподобия для любого момента времени. Эта совокупность может быть смоделирована с помощью соответствующих, вообще говоря, нелинейных аналоговых устройств или при подходящей дискретизации по времени решена с по­мощью ЭВМ. Отметим в заключение одну из модификаций этих урав­нений, позволяющую избежать необходимости обращения матрицы .

Вводя обозначение

, где I

и дифференцируя по времени соотношение , где I - единич­ная матрица, получаем с помощью (7.5.46) дифференциальное уравне­ние, определяющее непосредственно матрицу :

(и аналогично при замене на ), которое совместно с уравнением (7.5.45)

определяет оценку , не требуя обращения матриц. При этом имеет место переход от простейшего линейного дифференциального уравнения (7.5.46) к нелинейному относительно дифференциальному уравне­нию (7.5.51) типа Риккати.